线性表——单链表的增删查改操作

一.认识单链表目录一.认识单链表1.什么是单链表呢2.结点的初始化二.单链表的增删查改操作1.单链表的头插操作2.单链表的尾插操作3.指定位置的前方和后方进行插入1.在p1的前面插入ps4.单链表的删除操作1.中间位置删除2.头删3.尾删1.什么是单链表呢单链表也属于线性表中的一种它是物理上不连续存储逻辑上用指针按次单向序链接的线性表。如各个结点之间并无物理上的链接。各个结点由两部分组成——数据域和指针域各个结点的指针指向它的下一个结点若没有下一个节点则使该结点的指针赋为空。如此就是一个单向、不连续存储、不循环的线性表——单链表。2.结点的初始化单链表虽然物理上不连续但是并代表它的各个结点的数据类型可以各不相同和顺序表一样各个储存的是相同的数据类型。1 struct SListNode 2 { 3 int data; //节点数据 4 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 5 };每当我们插入一个结点时都需要开辟一块空间用来存储结点但是插入结点后我们基本上只知道第一个结点的指针后面的结点都时匿名的 。头结点也叫哨兵位。只是一个放哨的不存储任何数据指针域的指针指向第一个有效结点的地址。当然头结点可用可不用。我们先在头文件对结点的结构体进行声明同时我们还定义了结构体的指针*PNode相当于typedef struct SLNode* PNode;此时PNode就是一个指针类型注意是类型而不是变量当我们再声明一个指针变量时就可以这样声明了PNode L; //相当于struct SLNode* L;现在我们来完成各个结点的初始化函数,当然在那之前我们先完成头节点的初始化思考一下我们初始化一个结点应该返回是什么或者应该什么都不返回吗我们的选择是要如果不反回结点的地址就需要二级指针进行操作这里我们希望使用一级指针我们选择返回初始化的结点的地址我们知道头结点的数据是不用初始化的我们只管初始化后把地址返回去即可。如果初始化成功就返回开辟好的地址如果初始化失败就返回空。同时在头文件上声明在test.c文件中进行调用注意我们创建的头结点是不存放数据的当然刚初始化头节点它后面还没有有效的结点所以node的next要置为空二.单链表的增删查改操作1.单链表的头插操作前面我们已经创建了一个头节点但是头插法指的是在第一个有效数据前面插入而不是头节点的前面插入。理解这个后我们开始实现头插函数我们来分析应该怎么插入假设ps指针指向的就是我们要插入的结点我们最直接的想法就是让phead指向ps,然后ps指向p1,当然这没错只不过需要注意顺序问题。如果先让phead的next先指向ps,那么我们就失去了p1的地址也就是这种写法phead-next ps; ps-next phead-next;这样就容易造成了死循环也就变成了这样虽然看似简单稍不注意就会犯这样的错误那么正确的操作应该是这样//先让ps找到下个结点的地址 ps-next phead-next; //再让头节点的next指向ps phead-next ps;这里也能体现出带头节点的好处假如头节点指向的下一个位置为空我们也不用进行额外的操作依然和正常头插一样即可。如果是不带头节点的头插你还得判断头指针是否为空操作不慎还会使得头指针变成野指针导致越权访问。现在头插的基本逻辑已经搞定头插函数就可以这么写了我们需要头指针你既然要插入肯定要有值吧所以还得有value下面就是用上面的逻辑来实现这样我们就完成了头插让我们来测试一下当然为了只管观察过程我么设计一个打印函数这里不细讲来我们看测试结果没有问题我们继续看尾插2.单链表的尾插操作我们来看图进行分析为了方便解说我们给最后一个结点取名为p1在实际操作过程中它是匿名的我们只能通过头节点开始从头遍历找到它。现在我们想把ps插入到p1的后面和头插法的逻辑很像先让ps指向p1的next再让p1指向ps即可那就是这样由于逻辑和头插几乎一直故不再过多解释我们直接测试结果很简单现在我们来看指定位置的前后面插入3.指定位置的前方和后方进行插入这里我们先来解决传入头节点传入的情况假设我要在p1这个位置的前面进行插入操作现在我们有两种方法进行寻值操作第一种是按需要进行寻值插入第二种是先查询值的位置再进行操作。这两种既然都涉及查询我就先完成查询函数吧然后再进行插入操作查询函数比较简单这里直接给出这样得到要查询的值的地址后就方便进行前后插入操作了。1.在p1的前面插入ps假设查找到了p1的地址现在要在p1的前面插入ps,但是现在不传入头指针了这就意味着我没有办法从头开始遍历找到p1的前一个结点就没有办法让p1的前一个结点的next指针直接指向ps能想到的一个办法是先把ps插入到p1的后面做它的直接后继结点然后把p1的data与ps的data交换以实现在值value前插入结点ps的操作用代码实现就是同时在头文件声明后测试出现了随机值说明插入函数又未定义值就进行运算的情况检查函数bool InsertFront(PNode p1, ElemType value) { PNode temp (PNode)malloc(sizeof(Node)); if (temp) { temp-next p1-next; p1-next temp; p1-data temp-data; p1-data value; return true; } return false; }我发现在两个结点完成指针指向链接后temp的data并没有进行初始化就与p1的data进行了交换值操作因此交换后temp的值为确实值而p1的data为随机值只需要开在交换值前给temp的成员data赋值即可修改完成测试运行结果在4的前面插入11再于2的前面插入12均没有问题。在p1的后方插入值value和前插中的操作如出一辙直接插入值不需要进行交换操作在头文件声明后测试分别于4的后面插入11再于2的后面插入12 。代码正常进行插入操作基本完成既然后插入肯定也要又删除操作。4.单链表的删除操作1.中间位置删除删除操作和插入操作很像都是注意结点的指针域的指向释放空间后不要让表断链假设传入参数是只传了p1指向的地址就无法从头开始找到p1的前驱结点不能简单地去修改p1前驱结点的next指向这个时候只能接着运用偷梁换柱的方法把删掉p1修改为删掉p1后继结点因为这里讨论的是p1不为最后一个结点的情况所以不用担心p1后面没有值和p1前驱结点的next会成为野指针的情况。把p1后继结点的data赋值给p1的data在让p1的next等于p1后继结点的next这样就完成了偷梁换柱就变成了这样测试一下看效果出问题了目前不知道哪里有bug通过调试检查试试发现我们要删除值为4的结点进行删除操作后访问错误检查后发现是删除时空间释放的逻辑有问题当完成交换后node指向的已经时原来直接后继的next再进行释放操作就会释放到原直接后继结点的next现在只需要另起一个变量存储原直接后继结点的地址然后释放就不会释放错空间了在来测试看结果结点4和结点2都被正常删除没有造成内存泄漏的情况。2.头删因为讨论的时有带头节点的单链表所以头山的时候完全不用考虑头节点是否为空的情况大大方便了删除操作的执行。结合前面的经验每把phead的next修改前先把要释放的空间临时存起来然后free但是头删要注意phead的next为空的情况所以进行头删操作前要先判断phead的next是否为空为空则返回。同时在头文件进行声明测试看结果如何结果正常接着继续处理尾删3.尾删尾删就是从最后一个结点挨个往前删除结点但是单向链表是不可以逆向访问的每一次尾删只能从头循环遍历到最后一个结点再进行删除操作。同样尾删时如果只有一个元素时或者链表为空头指针的next就为空所以尾删也要判断phead的next是否为空。如果我的pos时最后一个结点我释放掉pos后pos的直接前驱结点的next就变成了也指针如果我把循环条件改为while (pos-next pos-next-next)确实可以解决这个问题但是有效元素为1的时候如何判断我的pos是倒数第一个元素还是倒数第二个元素只需要让pos是从phead的位置出发即可这里再一次体现出带头节点的单向链表的优势循环结束后pos的next才是最后一个结点所以要释放的是pos-next然后把pos的next置为空这样我们就完成了尾插操作。至此我们就完成了单链表的基本增删查改操作