顺序表的实现

顺序表存储结构

结构体List用来管理动态分配的内存空间。
顺序表的初始分配空间大小为LIST_INIT_SIZE，当空间满时，再重新分配多增加LIST_INCREMENT的空间，listsize为当前最大的容量，length为使用的容量；基地址为base，相当于数组的名称。

#define LIST_INIT_SIZE 10	// 线性表存储空间的初始分配量
#define LIST_INCREMENT 2	// 线性表存储空间的分配增量

typedef int ElemType;	//顺序表元素类型

struct List {
	ElemType* base;		 // 存储空间基址
	int length;			 // 当前长度
	int listsize;	 // 当前分配的存储容量(以sizeof(ElemType)为单位)
};

注意：
动态分配的内存，数组是从下标是从0开始的，所以第i个数据元素是L.base[i-1]。

基本操作

1.初始化

分配初始大小的内存空间，base指向分配的内存空间基地址，长度为0，容量为LIST_INIT_SIZE。

void InitList(List& L) {
	L.base = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
	if (!L.base)	exit(-1);
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
}

2.销毁

释放分配的存储空间，长度和容量都为0，基地址为空。

void DestroyList(List& L) {
	free(L.base);
	L.base = NULL;
	L.length = 0;
	L.listsize = 0;
}

3.清空
长度为0，不用释放空间。

void ClearList(List& L) {
	L.length = 0;
}

4.为空

bool ListEmpty(List L) {
	if (L.length == 0)
		return true;
	else
		return false;
}

5.长度

int ListLength(List L) {
	return L.length;
}

6.获取元素
第i个元素数组下标为i-1。

bool GetElem(List L, int i, ElemType& e) {
	if (i<1 || i>L.length)
		return false;
	e = *(L.base + i - 1);	
	return true;
}

7.定位元素
compare()是数据元素判定函数(满足为1，否则为0)，返回L中第1个与e满足关系compare()的数据元素的位序。p指针为指向第i个元素。

int LocateElem(List L, ElemType e, bool (*compare)(ElemType, ElemType)) {
	ElemType* p=L.base;
	int i = 1;
	while (i <= L.length && !compare(*p++, e))
		++i;
	if (i <= L.length)
		return i;
	else
		return 0;
}

8.前驱

前驱只能从第二个元素开始找，第一个元素没有前驱。

ElemType PriorElem(List L, ElemType cur_e, ElemType& pre_e)
{ 
	int i = 2;
	ElemType* p = L.base + 1;
	while (i <= L.length && *p != cur_e)
	{
		p++;
		i++;
	}
	if (i > L.length)
		return false; // 操作失败
	else
	{
		pre_e = *--p;
		return true;
	}
}

9.后继

最后一个元素没有后继，找到倒数第二个元素。

ElemType NextElem(List L, ElemType cur_e, ElemType& next_e)
{ 
	int i = 1;
	ElemType* p = L.base;
	while (i < L.length && *p != cur_e)
	{
		i++;
		p++;
	}
	if (i == L.length)
		return false; // 操作失败
	else
	{
		next_e = *++p;
		return true;
	}
}

10.插入

在第i个元素之前插入新的数据元素val，长度加一。注意插入位置i的范围，1<=i<=length+1，length+1是因为可以在最后一个元素之后插入，即在最后一个元素的下一个元素之前插入。空间满时，要增加内存分配。

bool ListInsert(List& L, int i, int val) {
	ElemType* newbase, * p, * q;
	if (i<1 || i>L.length+1)	return false;	// i值不合法
	if (L.length >= L.listsize) {	//当前存储空间已满，增加空间分配
		newbase = (ElemType*)realloc(L.base, L.listsize + LIST_INCREMENT);
		if (!newbase)	exit(-1);
		L.base = newbase;	//新基址
		L.listsize +=LIST_INCREMENT;	//增加存储容量
	}
	q=L.base+i-1;	//q为插入位置
	for (p=L.base+L.length-1; p >=q; --p) {	//插入位置及之后的位置右移
		*(p+1) = *p;
	}
	*q = val;	//插入
	++L.length;		//表长加一
	return true;
}

11.删除

删除第i个位置的元素，并用返回其值val，长度减1。注意删除位置i的范围，1<=i<=length。第i个元素的下标为i-1。

bool ListDelete(List& L, int i, int& val) {
	if (i<1 || i>L.length)	return false;	// i值不合法
	val = L.base[i - 1];	//被删除元素的赋值
	for (int j = i; j < L.length; j++) {	//被删除元素之后的元素左移
		L.base[j-1] = L.base[j];
	}
	--L.length;		// 表长减1
	return true;
}

12.遍历

void ListTraverse(List L) {
	ElemType* p = L.base;
	for (int i = 1; i <= L.length; i++) {
		printf("%d ", *(p++));
	}
	printf("\n");
}

测试函数

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//判断相等，用于元素定位LocateElem
bool equal(ElemType c1, ElemType c2){ 
	if (c1 == c2)
		return true;
	else
		return false;
}
//元素访问，用于元素遍历ListTraverse
void visit(ElemType &e)
{
	printf("%d ", e);
}

int main() {
	List L;
	ElemType n;
	InitList(L);	//初始化
	printf("初始化L后：L.base=%u L.length=%d L.listsize=%d\n", L.base, L.length, L.listsize);
	for (int j = 1; j <= 5; j++)	
		n = ListInsert(L, 1, j);	//插入
	printf("在L的表头依次插入1～5后：");
	ListTraverse(L, visit);
	printf("L.base=%u L.length=%d L.listsize=%d ", L.base, L.length, L.listsize);
	printf("L是否空：i=%d(1:是 0:否)\n", ListEmpty(L));
	ClearList(L);	//清空
	printf("清空L后：L.base=%u L.length=%d L.listsize=%d ", L.base, L.length, L.listsize);
	printf("L是否空：i=%d(1:是 0:否)\n", ListEmpty(L));
	for (int j = 1; j <= 10; j++)	//插入
		ListInsert(L, j, j);
	printf("在L的表尾依次插入1～10后：");
	ListTraverse(L, visit);
	printf("L.elem=%u L.length=%d L.listsize=%d\n", L.base, L.length, L.listsize);
	ListInsert(L, 1, 0);	//插入
	printf("在L的表头插入0后：");
	ListTraverse(L, visit);
	printf("L.elem=%u(有可能改变) L.length=%d(改变) L.listsize=%d(改变)\n", L.base, L.length,L.listsize);

	if(GetElem(L, 5, n))	//获取元素
		printf("第5个元素的值为%d\n", n);
	else
		printf("没有第5个元素\n");
	if (GetElem(L, 13, n))
		printf("第13个元素的值为%d\n", n);
	else
		printf("没有第13个元素\n");

	if (n=LocateElem(L, 8, equal))	//定位元素
		printf("元素8的位置为%d\n",n);
	else
		printf("没有值为8的元素\n");
	if (n = LocateElem(L, 11, equal))
		printf("元素11的位置为%d\n", n);
	else
		printf("没有值为11的元素\n");

	if (PriorElem(L, 10, n))	//前驱
		printf("元素10的前驱为%d\n", n);
	else
		printf("元素10无前驱\n");
	if (NextElem(L, 10, n))
		printf("元素10的后继为%d\n", n);
	else
		printf("元素10无后继\n");

	if (PriorElem(L, 0, n))		//后继
		printf("元素0的前驱为%d\n", n);
	else
		printf("元素0无前驱\n");
	if (NextElem(L, 0, n))
		printf("元素0的后继为%d\n", n);
	else
		printf("元素0无后继\n");

	ListTraverse(L, visit);
	printf("表长为%d\n", ListLength(L));
	if (ListDelete(L, 3, n))	//删除
		printf("删除第3个元素成功，其值为%d\n", n);
	else
		printf("删除第3个元素失败\n");
	ListTraverse(L, visit);
	DestroyList(L);	//销毁
	printf("销毁L后：L.elem=%u L.length=%d L.listsize=%d\n", L.base, L.length, L.listsize);

	return 0;
}

测试结果