本文共 4084 字，大约阅读时间需要 13 分钟。

顺序表

顺序表就是用一段连续的物理地址连续的存储单元存放的线性结构.

typedef struct seqList{   	SLDataType* _data;		//需要进行动态开辟的一个数组	size_t _size;			//有效元素的个数	size_t _capacity;		//当前我们可以存放的最大元素个数}seqList;			//别名

如果你对这个使用动态存储的结构体,只能看到12个字节,但是对于下面的静态就不一样了,大家可以试一下(很简单,利用sizeof实现)

静态顺序表:

#define N 10struct seqList2{   	SLDataType _data[N];			size_t _size;			//有效元素的个数	size_t _capacity;		//当前我们可以存放的最大元素个数}seqList2;			//别名

接口声明

//1.初始化void initSeqList(seqList * sl);//2.检查内存是否够用void checkCapacity(seqList* sl);//3.函数打印void printSeqList(seqList* ls);//4.头插void pushFront(seqList* sl, SLDataType val);//5.头删void popFront(seqList* sl);//6.尾插void pushBack(seqList* sl, SLDataType val);//7.尾删 void popBack(seqList* ls);//8.指定插入void insert(seqList* sl, int pos, SLDataType val);//9.指定删除void erase(seqList* sl, int pos);//10.查找对应的值int findIdx(seqList* sl, SLDataType val);//11.内存大小int size(seqList* sl);//12.销毁void destorySeqList(seqList* sl);

这里有12个对应头文件的声明,量比较多,但是都大体相似,希望能坚持看下去,一起加油!

接口实现

1.初始化

void initSeqList(seqList * sl){   		sl->_data = NULL;		//指针指向空间变为0	sl->_size = sl->_capacity = 0;	//内存大小和最大容量也变为0,相当于int i=0;操作,很好理解}

2.检查内存是否够用

void checkCapacity(seqList* sl){   	if (sl == NULL)		//基本的判断是否为空指针,是则直接返回		return;			if (sl->_size == sl->_capacity){   		//在所存储的size和最大的容量相等时,我们就需要扩大内存空间				//当需要扩大内存时,我们的最大容量也需要变化,这里的条件运算符:如果这两个相等则+1,不等开辟二倍的内存		int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;		//写入一个新的指针,进行动态内存的申请		SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);		//将原始的数据进行拷贝过来		memcpy(tmp, sl->_data, sizeof(SLDataType)*sl->_size);		//释放原有的内存,否则会造成内存泄漏		free(sl->_data);		//更新代码		sl->_data = tmp;		sl->_capacity = newCapacity;	}}

在这里唯一有点疑惑的可能就是为啥要申请二倍的内存,当两个内存相等的时候,我们只用申请一个,当不等的时候,我们并不能确定要申请多少个空间才能将其覆盖,所以我们直接申请二倍的内存,绝对够用,而且不用不停地进行申请,比较方便.

void printSeqList(seqList* ls){   	for (int i = 0; i < ls->_size; ++i){   	//for将内存进行循环		printf("%d ",ls->_data[i]);			//然后挨个打印	}	printf("\n");}

4.头插

void pushFront(seqList* sl, SLDataType val){   	if (sl == NULL)		return;			//判断是否空指针	checkCapacity(sl);	//内存大小检查	int end = sl->_size;	//这里最后一个内存就应该是size的大小,直接利用	while (end > 0){   		//在while里面从后往前循环依次将数据往后移一位		sl->_data[end] = sl->_data[end - 1];		--end;			}		sl->_data[0] = val;		//将要插入的数据放在最前面	sl->_size++;			//更新代码}

5.头删

void popFront(seqList* sl){   		if (sl == NULL||sl->_size==0)		return;	checkCapacity(sl);			//前三行基本操作,不过多解释,后面的话	int start = 1;				//第二个变量	while (start < sl->_size){   	//循环[2,size)			sl->_data[start-1]=sl->_data[start];  //依次向前一位				++start;		//循环	}	--sl->_size;		//更新}

6.尾插

void pushBack(seqList* sl,SLDataType val){   		checkCapacity(sl);		sl->_data[sl->_size] = val;				//直接将数据插入到最后		++sl->_size;	//更新	}

7.尾删

void popBack(seqList* ls){   	if (ls == NULL)		return;			if (ls->_size > 0)	//对于尾删这里并不是真正的删除,而是将size直接-1,从而达到了尾删的效果		ls->_size--;}

8.指定插入

void insert(seqList* sl,int pos,SLDataType val){   	if (sl == NULL)		return;	if (pos >= 0 && pos <= sl->_size){   		//判断输入的位置是否在有效区域		checkCapacity(sl);		int end = sl->_size;	//定义最后一个数据				while (end > pos){   		//在插入数后面的数据进行循环!!!!!!			sl->_data[end] = sl->_data[end - 1];		//向后移一位			--end;		//依次循环		}		sl->_data[pos] = val;	//指定位置进行插入		sl->_size++;		//更新	}}

9.指定删除

void erase(seqList* sl, int pos){   	if (sl == NULL || sl->_size == 0)		return;	if (pos >= 0 && pos < sl->_size){   		//有效范围内				int start = pos + 1;		//定义要插入后面一位的数开始		while (start < sl->_size){   		//后面的范围内					sl->_data[start - 1] = sl->_data[start];	//依次向前一格			++start;		//循环		}		--sl->_size;		//更新	}}

10.查找对应的值

int findIdx(seqList* sl, SLDataType val){   		int i = 0;	for (; i < sl->_size; ++i){   		//内存内循环		if (sl->_data[i] == val)	//当值相等的时候			return i;				//输出位置	}	return -1;		//找不到,返回-1}

11.内存大小

int size(seqList* sl){   	if (sl == NULL)		return 0;		//如果为空,返回0	else		return sl->_size;	//不为空,返回其长度}

12.销毁

void destorySeqList(seqList* sl){   	if (sl){   		if (sl->_data){   		//指向空间			free(sl->_data);	//空间释放			sl->_data = NULL;	//指针变为空		}	}}

对于顺序表有下面几个特点: