目录
1.线性表
2.顺序表
2.1概念及结构
1. 静态顺序表:使用定长数组存储元素。
2. 动态顺序表:使用动态开辟的数组存储。
2.2接口实现
typedef int SLDataType;//本篇博客以存放整型数据为例typedef struct SeqList { SLDataType* a;//声明了一个指向顺序表的指针,姑且称它为“顺序表指针” int size;//记录当前顺序表内元素个数 int capacity;//记录当前顺序表的最大容量 }SeqList;
接着开始初始化
//初始化顺序表 void SeqListInit(SeqList* ps) { assert(ps); ps->a = NULL;//刚开始时顺序表为空,顺序表指针为NULL ps->size = 0;//起始时元素个数为0 ps->capacity = 0;//容量为0 }
销毁顺序表
因为顺序表所用的内存空间是动态开辟在堆区的,所以我们在使用完后需要及时对其进行释放,避免造成内存泄漏。
//销毁顺序表 void SeqListDestory(SeqList* ps) { assert(ps); free(ps->a);//释放顺序表指针指向的空间 ps->a = NULL;//及时置空 ps->size = 0;//元素个数置0 ps->capacity = 0;//容量置0 }
打印顺序表
循环打印size个元素即可
//打印顺序表 void SeqListPrint(SeqList* ps) { assert(ps); int i = 0; //循环打印顺序表指针指向的数据 for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("\n"); }
增加数据
仔细想想,我们每次需要增加数据的时候,首先都应该先检查顺序表内元素个数是否已达顺序表容量上限。若已达上限,那么我们就需要先对顺序表进行扩容,然后才能增加数据。
//检查顺序表容量是否已满,若已满,则增容 void SeqCheckCapacity(SeqList* ps) { if (ps->size == ps->capacity)//满了,需要增容 { //判断顺序表容量是否为0,若为0,则先开辟用于存放4个元素的空间大小,若不为0,则扩容为原来容量的两倍 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; SLDataType* newA = realloc(ps->a, newcapacity*sizeof(SLDataType)); if (newA == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = newA;//开辟成功,将顺序表指针更新 ps->capacity = newcapacity;//容量更新 } }
若传入realloc的指针为空指针(NULL),则realloc函数的作用相当于malloc函数,这样也不会对新开辟的空间进行初始化
头插
要想在顺序表的表头插入数据,那么就需要先将顺序表原有的数据从后往前依次向后挪动一位,最后再将数据插入表头。
//头插 void SeqListPushFront(SeqList* ps, SLDataType x) { assert(ps); SeqCheckCapacity(ps);//检查容量 int i = 0; for (i = ps->size; i > 0; i--)//将数据从后往前依次向后挪 { ps->a[i] = ps->a[i - 1]; } ps->a[0] = x; ps->size++;//顺序表元素个数加一 }
挪动数据的时候应从后向前依次挪动,若从前向后挪动,会导致后一个数据被覆盖。
尾插
尾插相对于头插就比较简单了,直接在表尾插入数据即可
//尾插 void SeqListPushBack(SeqList* ps, SLDataType x) { assert(ps); SeqCheckCapacity(ps);//检查容量 ps->a[ps->size] = x; ps->size++;//顺序表元素个数加一 }
指定下标位置插入
要做到在指定下标位置插入数据,首先我们需要得到一个下标位置,然后从该下标位置开始(包括该位置),其后的数据从后往前依次向后挪动一位,最后将数据插入到该下标位置。
//指定下标位置插入 void SeqListInsert(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);//检查输入下标的合法性 SeqCheckCapacity(ps);//检查容量 int i = 0; for (i = ps->size; i > pos; i--)//从pos下标位置开始,其后的数据从后往前依次向后挪 { ps->a[i] = ps->a[i - 1]; } ps->a[pos] = x; ps->size++;//顺序表元素个数加一 }
观察到,头插和尾插实际就是再下标为0和下标为size的地方进行插入,意味着我们可以统一使用该函数来实现
//头插 void SeqListPushFront(SeqList* ps, SLDataType x) { SeqListInsert(ps, 0, x);//在下标为0的位置插入数据 } //尾插 void SeqListPushBack(SeqList* ps, SLDataType x) { SeqListInsert(ps, ps->size, x);//在下标为ps->size的位置插入数据 }
删除数据
删除数据,其实可以理解为:从某个位置开始,数据依次向前覆盖。这样一来,该位置的数据就相当于删除了
头删
要删除表头的数据,我们可以从下标为1的位置开始,依次将数据向前覆盖即可。
//头删 void SeqListPopFront(SeqList* ps) { assert(ps); assert(ps->size > 0);//保证顺序表不为空 int i = 0; for (i = 0; i < ps->size - 1; i++)//将数据从前往后依次向前覆盖 { ps->a[i] = ps->a[i + 1]; } ps->size--;//顺序表元素个数减一 }
注意:数据覆盖的时候应从前向后依次覆盖,若从后向前覆盖,会导致前一个数据被覆盖。
尾删
尾删就更简单了,直接将顺序表的元素个数减一即可
//尾删 void SeqListPopBack(SeqList* ps) { assert(ps); assert(ps->size > 0);//保证顺序表不为空 ps->size--;//顺序表元素个数减一 }
指定下标位置删除
要删除指定下标位置的数据,我们只需要从下标位置开始,其后的数据从前向后依次覆盖即可。
//指定下标位置删除 void SeqListErase(SeqList* ps, int pos) { assert(ps); assert(ps->size > 0);//保证顺序表不为空 assert(pos >= 0 && pos < ps->size); int i = 0; for (i = pos; i < ps->size - 1; i++)//从pos下标位置开始,其后的数据从前往后依次向前覆盖 { ps->a[i] = ps->a[i + 1]; } ps->size--;//顺序表元素个数减一 }
同样的道理,头删和尾删实际上也就是删除下标为0的位置和下标为ps->size - 1的位置的数据,也就意味着我们可以统一使用该函数来实现头删和尾删。
//头删 void SeqListPopFront(SeqList* ps) { SeqListErase(ps, 0);//删除下标为0的位置的数据 } //尾删 void SeqListPopBack(SeqList* ps) { SeqListErase(ps, ps->size - 1);//删除下标为ps->size - 1的位置的数据 }
查找数据
查找数据也相对简单,直接遍历一次顺序表即可,若找到了目标数据,则停止遍历,并返回该数据的下标,否则返回-1。
//查找元素,若有,返回下标,否则返回-1 int SeqListFind(SeqList* ps, SLDataType x) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++)//遍历顺序表进行查找 { if (ps->a[i] == x) return i;//找到该数据,返回下标 } return -1;//未找到,返回-1 }
修改数据
修改数据,就直接对该位置的数据进行再次赋值即可。
//修改指定下标位置元素 void SeqListModify(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size);//检查输入下标的合法性 ps->a[pos] = x;//修改数据 }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)