初阶数据结构【单链表及其接口的实现】

目录1. 链表的概念及结构2. 链表的分类2.1. 带头或者不带头2.2. 单向或者双向2.3. 循环或者非循环3. 单链表接口实现3.1. 单链表基本功能接口3.1.1. 打印输出3.1.2. 空间的开辟接口3.1.3. 单链表销毁3.2. 单链表的增加节点接口3.2.1. 单链表的尾插3.2.2. 单链表的头插3.2.3. 单链表在pos后插入接口3.3. 单链表的删除节点接口3.3.1. 单链表的尾删3.3.2. 单链表的头删3.3.3. 单链表删除pos后一结点3.4. 删除pos结点3.5. 单链表的修改接口3.6. 单链表的查找接口1. 链表的概念及结构概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。假设在32位系统上结点中值域为int类型则一个节点的大小为8个字节则也可能有下述链表:2. 链表的分类实际中链表的结构非常多样以下情况组合起来就有8种链表结构![[Pasted image 20261018111027.png|379]]2.1. 带头或者不带头带头链表最前面有一个头节点称作“哨兵位”它不存储数据用来指向第一个存储有效数据的节点不带头链表直接从第一个节点开始没有额外的头节点。带头链表不带头链表2.2. 单向或者双向单向链表每个节点只包含一个指向下一个节点的地址。它只能从前往后遍历不能从后往前遍历双向链表每个节点包含两个地址一个指向前一个节点一个指向后一个节点。它可以从任一节点开始向前或向后遍历。2.3. 循环或者非循环循环链表链表的最后一个节点的地址域指向链表的第一个节点形成一个闭环;非循环链表链表的最后一个节点的地址域为空null表示链表的结束。虽然有这么多的链表的结构但是我们实际中最常用还是两种结构3. 单链表接口实现我们先定义一个以下的单链表typedefintSListDataType;typedefstructSListNode{SListDataType data;structSListNode*next;}SListNode;使用接口的时候我们将单链表的第一个节点的地址传个接口 刚开始的时候我们还没有对单链表开辟空间所以是个空链表即头指针为NULL//头指针SListNode*pListNULL;3.1. 单链表基本功能接口3.1.1. 打印输出为了方便我们进行对其他接口的验证我们先写一个打印单链表的接口voidSListPrint(SListNode*phead){//如果这个链表是空链表那头指针就是指向NULL所以此处无需加断言SListNode*curphead;if(curNULL){printf(空链表!);}while(cur!NULL){printf(%d-,cur-data);curcur-next;}printf(NULL\n);}注这里可能你会觉得为什么要重新定义一个pcur来遍历直接用phead不就可以了吗如果我们用phead来遍历那等我们下次再来使用phead的时候就不是链表的头的位置了所以这里我们将phead给pcur就是为了让phead一直指向我们链表的头3.1.2. 空间的开辟接口我们在实现单链表的增加和插入的时候我们肯定会开辟一个新的节点容易让程序冗余所以我们写一个开辟一个新节点的函数接口方便后面的使用//创造节点函数SListNode*CreateSListNode(SListDataType x){SListNode*newNode(SListNode*)malloc(sizeof(SListNode));if(newNodeNULL){perror(malloc);exit(-1);}newNode-datax;//放入数据xnewNode-nextNULL;returnnewNode;}3.1.3. 单链表销毁当我们在程序彻底结束的时候要对我们开辟的空间进行一个释放我们可以使用这个接口 我们在写这个接口的时候我们要注意我们在释放一个节点后下一个节点的地址就丢失了所以我们要定义个指针变量cur来存储地址 cur plist 先将plist指向下一个节点plist plist-next; 再释放cur的空间free(cur); 最后将cur指向的空间更新为此时的plist当cur为空的时候全部的节点被释放结束循环voidSListDestroy(SListNode*plist){assert(plist);//防止plist为NULLSListNode*curplist;while(cur){plistplist-next;free(cur);curplist;}}3.2. 单链表的增加节点接口3.2.1. 单链表的尾插因为链表不能和顺序表一样直接定位到最后一个元素我们无法得知最后一个节点的地址所以我们要进行找尾的操作这个时候跳出循环的tail就是最后一个节点的地址这个时候我们不难写出下面的代码但是如果我们测试在一个空链表执行尾插操作时我们会发现结果并不如我们所料想的一样这是为什么呢通过调试我们发现newNode的确把值赋给了形式参数phead但是phead的改变却没有影响实参pList所以这里我们是“传值调用”但是有人会说这里的pList不是指向一个结点的地址吗为什么是传值调用呢当我们要修改pList时尽管pList本来就是指向一个结点的地址地址本身是一个值形参只是实参的拷贝我们如果只传pList那么改变的只是形参phead并不会改变外面的实参pList;所以我们要传pList的地址也就是一个二级指针;所以我们将pList的地址(pList)传入函数得到下面的答案//尾插voidSListPushBack(SListNode**pphead,SListDataType x){SListNode*newNodeCreateSListNode(x);//如果phead为空if(*ppheadNULL){*ppheadnewNode;}else{//找尾SListNode*tail*pphead;while(tail-next!NULL){tailtail-next;}tail-nextnewNode;}}3.2.2. 单链表的头插我们首先用开辟新节点的接口来开辟一个新节点newNode首先这里我们要注意先后顺序我们要先将新节点的next置为第一个节点的地址即plist 再将头指针指向新节点newNode-next *pphead; *pphead newNode;如果相反会造成原来的第一个节点地址丢失其次这里我们要对plist的值做修改同理我们要传plist的指针才可以达到此效果//头插voidSListPushFront(SListNode**pphead,SListDataType x){assert(pphead);SListNode*newNodeCreateSListNode(x);newNode-next*pphead;*ppheadnewNode;}3.2.3. 单链表在pos后插入接口//插入在后面voidSListInsertAfter(SListNode*pos,SListDataType x){assert(pos);SListNode*newNodeCreateSListNode(x);newNode-nextpos-next;pos-nextnewNode;}3.3. 单链表的删除节点接口3.3.1. 单链表的尾删尾删我们要注意在释放最后一个结点后倒数第二个结点的next如果我们没有将它置空那它将会变成一个野指针所以我们必须要将其置空那我们必须知道倒数第二个结点的地址才可以修改它的next值所以我们在找尾操作中要定义一个prev指针总是指向我们找尾指针的前一个结点voidSListPopBack(SListNode**pphead){//1.空if(*ppheadNULL){return;}//2.只有一个elseif((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}//3.一个以上else{//定义个指针prev来指向tail指向的节点的前一个节点SListNode*prevNULL;SListNode*tail*pphead;while(tail-next!NULL){prevtail;tailtail-next;}free(tail);prev-nextNULL;}}3.3.2. 单链表的头删//头删voidSListPopFront(SListNode**pphead){//1.为空不删if(*ppheadNULL)//防止我们对空指针进行解引用{return;}//2.如果只有1个节点 或 3.有一个以上的节点else{SListNode*next(*pphead)-next;free(*pphead);*ppheadnext;}}3.3.3. 单链表删除pos后一结点这个不难写我们先讲要删除的结点指针记录下来给next方便后面释放再将pos指向下下一个结点最后释放要删除的next结点//删除pos位置的节点voidSListEraseAfter(SListNode*pos){assert(pos);SListNode*nextpos-next;//下一个节点的地址SListNode*nextnextnext-next;//下下一个节点地址pos-nextnextnext;free(next);}3.4. 删除pos结点有了单链表删除pos后一节点做铺垫我们知道想要删除pos结点我得先找到pos的前一个结点所以我们先通过遍历来找到pos前一个结点才可以删除pos结点这个时候要考虑到pos为头结点的时候了这个时候问题就变成头删了//删除pos位置的结点voidSListErase(SListNode**pplist,SListNode*pos){assert(pospplist*pplist);if(pos*pplist){SListPopFront(pplist);}else{SListNode*prev*pplist;while(prev-next!pos){prevprev-next;}prev-nextpos-next;free(pos);posNULL;}}3.5. 单链表的修改接口这个实现比较简单,直接修改对应的值就可以了//修改pos指向的节点值voidSListUpdata(SListNode*pos,SListDataType x){assert(pos);pos-datax;}3.6. 单链表的查找接口为方便后面的插入接口我们需要找到单链表的某个节点的地址以方便插入和修改我们采取遍历的方式如果没有此节点我们返回NULLSListNode*SListFind(SListNode*plist,SListDataType x){SListNode*curplist;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}