具有线性关系的数据可以选择链式存储链式存储每个环上要有自己的数据和下一个数据的地址1.单向链表的创建思路创建一个头节点代表这个链表开始的地方不关心头节点的数据头节点指向NULL同时要返回头节点的地址后续对链表的增删改等操作要通过这个地址实现。#include stdio.h #include stdlib.h typedef int data_t;//后续如果要更改数据类型只需要在这里修改 typedef struct node { data_t data;//节点的数据阈 存放的是这个节点的数据 struct node *next;//节点的指针域 指向下一个节点的地址 }node_t; node_t *linklist_creat(void)//返回链表的指针 { node_t *head malloc(sizeof(node_t)); if(head NULL)//判断malloc是否成功 { printf(listlist_creat fail\n); return NULL; } head-next NULL;//空链表头节点的next指向NULL return head; }2.单向链表的头插思路要创建一个新节点要插入的数据存在这个新节点的数据域中将这个新节点插入头节点后成为新的首节点新节点的next指向原本的首节点的地址。int linkist_insert_head(node_t *phead,data_t data)//返回0表示插入成功 非0失败 { if(pheadNULL)//有效性判断 { return -1; } node_t *pnew malloc(sizeof(node_t));//创建新节点并判断是否创建成功 if(pnewNULL) { printf(pnew malloc fail\n); return -1; } pnew-data data;//新节点创建成功把要插入的数据放到它的数据域里 node_t *q phead-next;//记录一下原先的首节点 pnew-next q;//新节点指向原先的首节点 phead-next pnew;//头节点指向pnewpnew成为新的首节点 return 0; } //特殊情况分析向空链表头插qNULLpnew的next指向NULL成为了尾节点phead的next指向pnew 结果正确没有问题上面的一般情况适用不需要做代码调整3.判断单向链表是不是空链表思路空链表的头节点指针域指向NULL。int is_empty(node_t *phead)//返回1表示空 0为非空 { if(pheadNULL)//有效性判断 { return 0; } if(phead-nextNULL) { return 1; } return 0; }4.单向链表的打印思路首先无效链表和空链表不能打印如果可以打印定义一个指针p从首节点开始打印每次打印完p后移一位到下一个节点直到将尾节点打印完p后移一位变为NULL时不能打印了int linklist_print(node_t *phead)//返回0表示成功打印非0表示失败 { if(pheadNULL||is_empty(phead)1)//无效和空链表不打印 { return -1; } node_t *p phead-next;//从首元素开始 while(p!NULL) //没有将所有数据打印完打印完pNULL { printf(%d ,p-data); p p-next;//这个数据打印完准备去打印下一个节点 } putchar(\n); return 0; }5.计算单向链表长度思路无效链表没有长度定义一个num初始为0计算有效节点数量定义一个指针p从首节点开始当这个节点不为NULLsum然后p再后移一个节点当所有有效节点计算完后pNULL退出返回sumint length(node_t *phead)//返回有效节点个数 { if(pheadNULL)//有效性判断 { return -1; } int sum 0;//初始为0 node_t *p phead-next;//从首节点开始 while(p!NULL) { sum;//是有效节点sum1 p p-next;//准备去判断下一个节点 } return sum; } //特殊情况空链表p phead-next NULL,直接跳过while循环返回sum的初值0正确。不需要对上面的 代码进行调整6.单链表尾插思路先创建一个新链表将要插入的数据存到新链表的数据域中找到链表中的尾节点p-nextNULL原先尾节点的next指向新节点让新节点的nextNULL成为新的尾节点int linklist_insert_tail(node_t *phead,data_t data)//成功插入返回0非0不成功 { if(pheadNULL) { return -1; } node_t *pnew malloc(sizeof(node_t));//创建新节点 if(pnewNULL)//判断是否创建成功 { return -1; } pnew-data data;//新节点创建成功将数据放进来 node_t *p phead;//从头节点开始判断因为空链表也能尾插空链表的头节点也相当于它 的尾节点满足p-next如果不从头节点开始这种情况会被忽略 while(p-next!NULL)//一直找到尾节点 { p p-next; } //程序走到这个位置就已经找到尾节点了 p-next pnew;//原先的尾节点指向pnew pnew-next NULL;//pnew成为新的尾节点 return 0 }7.在单向链表中查找数据思路无效链表和空链表不用找。我们不关心头节点里的数据从首节点一直找到尾节点看这些节点数据域里的数据和要查的数据是否相等相等就是找到了返回这个节点的地址一直找完所有有效节点pNULL说明所有的这个链表里没有要找的数返回NULL。node_t *linklist_find_key(node_t *phead,data_t key) { if(pheadNULL||is_(phead)1) { return NULL; } node_t *p phead-next;//从首节点开始找 while(p!NULL)//所有的数找完时pNULL 没找完继续找 { if(p-data key)//判断是不是要找的数 { return p;//找到了返回这个节点的地址 } p p-next;//没找到后移一位继续找 } return NULL;//全部有效节点找完还是没有找到返回NULL }8.修改单向链表中的值思路无效和空链表不能修改。先找到这个数所在的节点然后修改它的数据域为新值。修改成功返回这个节点的地址不成功返回NULLnode_t *linklist_updata(node_t *phead,data_t old,data_t new) { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p linklist_find_key(phead,old);//接收查找的结果 NULL表示没找到 非NULL是找到的 这个数据的节点的地址 if(p!NULL)//找到了更新数据域 { p-data new; } return NULL;//没找到返回NULL }9.删除单向链表中的某个节点思路无效链表和空链表不能删。正常思路是找到这个要删的节点但是删除这个节点后我们还要把这个节点前面的节点和它后面的节点链接起来如果一直找到要删的节点因为链表是单向的无法表达出它前面的那个节点所以我们要一直找到要删节点的前一个节点pp-next-datakey,节点q p-next是要删除的节点q-next是要删节点的后一个节点这样找到并表达出三个节点后让要删节点的前一个节点的next指向要删节点的后一个节点这样那两部分就链接起来了然后我们释放掉要删除的节点。有可能我们要删除的是只有一个有效节点链表的首节点那么头节点就是p所以p要从头节点开始找。int linklist_delete_key(node_t *phead,data_t data)//返回0表示成功删除 非0不成功 { if(pheadNULL||is_empty(phead)1) { return -1; } node_t *p phead; while(p-next!NULL)//当一直找完所有数据找到尾节点时p-nextNULL 没找完继续找 { if(p-next-datakey)//找到了 { node_t *q p-next;//记录要删除的节点 p-next q-next;//要删的前一个指向要删的后一个 链接起来 free(q);//释放要删节点的空间 q NULL; return 0; } pp-next;//没找到继续找 } return -1;//全部有效数据都找完了还是没有返回-1 }10.销毁单向链表思路无效不用销毁。从头节点开始删最后将这个指向头节点的指针的地址也释放掉因为我们要操作这个指针的地址所以我们要把头节点指针传参进来进行修改。int linklist_destory(node_t **pphead)//返回0表示成功销毁 非0表示失败 { if(ppheadNULL) { return -1; } node_t *p *pphead;//要销毁的节点从头节点开始但是如果直接把他销毁了就找不到下一个要销毁 的节点了所以下面定义一个q指向下一个待删的节点 node_t *q NULL; while(p!NULL) { q p-next;//下一个待删的节点 free(p);//释放这个节点 p NULL; p q;//准备去处理下一个节点 } *ppheadNULL;//将指向头节点的指针也释放掉 return 0 }11.找到单向链表的中间节点思路无效链表和空链表不用找。定义一对快慢指针都从头节点开始走快指针p一次走两步慢指针q一次走一步这样快指针走的总长度是慢指针的二倍当快指针走完时慢指针停下的位置就是中间节点。那快指针什么时候停下呢对于有效节点数是奇数的链表快指针走到NULL时慢指针停下来的位置是中间节点对于有效节点数是偶数的链表快指针走到尾节点时慢指针停下的位置是中间节点。node_t *linklist_find_mid(node_t *phead)//找到了返回中间节点的地址 { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p phead;//快指针 node_t *q phead;//慢指针 while(p!NULLp-next!NULL)//既没有到达奇数节点结束结束条件也没有到达偶数节点结束条件 { p p-next-next;//快指针走两步 q q-next;//慢指针走一步 } return q;//返回结束时慢指针指向的节点地址就是中间节点的地址 }12.找到单向链表中的倒数第K个节点思路无效链表和空链表不用找。定义一对指针都从头节点开始走p指针先走k步后p指针再和q指针一起走每次一步这样p指针与q指针始终相隔k个节点当p指针走向NULL时q指针指向的节点就是链表中倒数第k个节点。node_t *linklist_find_behind_key(node_t* phead,int k)//找到了返回节点地址 { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p phead;//先走的指针 node_t *q phead; int i; for(i0;ikey;i)//先走k步 { p p-next; } while(p!NULL)//没有到达结束条件 { p p-next;//p和q一起每次走一步 q q-next; } return q;//到达结束条件了返回q指向节点的地址 }13.判断单向链表中是否有环思路单线链表和空链表不用判断。如果一个链表是有环的那在这个链表中不会有节点的next指向NULL这可以作为判断条件。定义一对快慢指针从头结点开始走快指针每次走两步慢指针每次走一步就像两个人在操场跑步一个慢一个快因为操场是个环总归有跑的快的多跑了一整圈与跑的慢的相遇的时候在链表表中如果快指针p在走的过程中没有走到NULL并且在某一刻与慢指针q相等那这个链表就是有环的。int linklist_is_circle(node_t *phead)//返回1说明有环 返回0无环 { if(pheadNULL||is_empty(phead)1) { return 0; } node_t *p phead; node_t *q phead; while(p!NULLp-next!NULL)//奇数偶数节点条件下都还没有找到NULL 说明目前还可能有环 { p p-next-next;//快指针走两步 q q-next;//慢指针走一步 if(p q)//判断是否相遇相遇说明有环返回1 不相遇判断是否到达结束条件没有就继续找 { return 1; } } return 0;//在走的过程中发现了有节点的next指向NULL说明无环 返回0 }14.将单向链表逆序无效空链表和只有一个有效节点的链表不用逆序思路①先将首节点的next指向NULL头节点和首节点断开整个链表变成一个空链表和一个没有头节点全是有效节点的链表将无头链表中的节点从首到尾依次头插到空链表中这样当尾节点插入完毕后整个链表就逆序了。void linklist_reverse(node_t *phead) { if(pheadNUL||is_empty(phead)1||phead-next-nextNULL) { return;//无效空链表只有一个有效节点的链表不用逆序 } node_t *p phead-next;//从首节点开始但如果不保存一下下一个要处理的节点首节点头插结束就 //无法表达下一个要处理的节点所以下面定义一个指针p指向要处理的节点 //的下一个节点 node_t *q NULL; while(p!NULL)//所有节点还没处理好 { q p-next;//先处理一下下一个节点 p-next phead-next;//头插 phead-next p; p q;//去处理下一个位置 } }思路②先忽略头节点从方向上看正序的链表是每个节点的next向后值那逆序的链表就是每个节点的next向前指向前面处理好的链表的最后一个节点这样结束后再让头节点的next指向逆序好的无头链表的最后一个节点这样就实现了链表的逆序。在操作时由于链表是单向的我们需要表示当下要处理的节点curr前面逆序操作后的链表的最后一个节点prev下一个要处理的节点next。curr从首节点开始它的next要指向prev但是在它之前还没有过逆序操作并且可以知道它会成为逆序后的链表的尾节点所以我们要设prev的初值为NULL。结束条件是要处理完了所有有效节点curr走到了NULL。void linklist_reverse_threePoints(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *curr phead-next;//从首节点开始处理 node_t *prev NULL; node_t *next NULL; while(curr!NULL)//没有到达结束条件还有节点没有参与逆序 { next curr-next;//下一个要处理的节点 curr-next prev;//当下节点的next指向前面逆序了一部分完成的链表的最后一个节点prev prev curr;//上一步结束后这个处理后的链表的最后有一个节点已经变为了curr要更新一下 curr next;//去处理下一个节点 } phead-next prev;//上面的循环结束后prev来到了原先的尾节点现在它成为了新链表的首节点 //让头节点的next指向它完成链接这样整个链表的逆序就完成了 }15.单向链表的选择排序无效空链表和只有一个有效节点的链表不用排序思路与数组选择排序的思路相同就是定位擂台打擂台最小的数据留在擂台上如果有n个数据只需要打前n-1个擂台每次比较后擂台后移前面决胜出来的数不需要比较了剩下所有的数都要参与比较。void linklist_select_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; for(p phead-next;p-next!NULL;pp-next)//控制打擂台的位置从首节点到尾节点的前一个节点 { for(q p-next;q!NULL;q q-next)//控制每轮打擂台的数从擂台的下一个节点到尾节点 //都要参与比较 { if(q-data p-data)//判断这个节点的数据域是不是擂台节点的数据域小 //小的话交换它们的数据域 { data_t t q-data; q-data p-data; p-data t; } } } }16.单向链表的冒泡排序无效空链表和只有一个有效节点的链表不用排序思路与原先数组的冒泡排序思路相同从首节点开始依次与它后面的节点比较比较大的数放在后面这样比完一轮最后一个节点的数据域就是最大的数下次比较排除到这个这个节点剩下的节点再进行一轮冒泡……如果有n个数据一共要比n-1轮冒出n-1个数剩下的那个数自然就是最小的数。void linklist_bubble_sort(phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; node_t *end NULL; for(p phead-next;p-next!NULL;p p-next)//控制比较的轮数 从首节点到尾节点的前一节点 //比较n-1轮 { for(q phead-next;q-next!end;q q-next)//控制每轮比较的数 { if(q-next-data q-data)//后一个数比前一个数小交换数据 { data_t t q-next-data; q-next-data q-data; q-data t; } } end q-next;//更新下一轮冒泡需要停止的位置 } }如果比较过程中需要交换将大的数据放在后面但是不想要交换数据域想要交换整个节点在链表中的顺序。参与比较的这两个节点分别是curr我们叫做当前节点和它后面的节点next我们叫做后节点要交换他们两个在链表中的顺序我们需要让前节点的前一个节点prev指向后节点前节点指向后节点的下一个节点最后让后节点指向前节点这样就完成了这两个节点顺序的交换。但是在每轮冒泡中我们需要依次让每个数与它后面的数相比较比如这次比较的前节点是链表中的第一个节点node1下次我们希望比较的前节点是链表中的第二个节点node2。我们规定前节点用curr表示那node1表示为curr这次比较后该比较下一组了下一组的前节点位置应该在链表中的第二个节点node2那node2能直接用上一轮curr-next表示吗这样是不对的因为在上一轮比较交换节点后curr在链表中的顺序已经变了变成了链表中的第二个节点了它的next是链表中第三个节点用它来表示node2当然是错的。所以为了解决这个问题我们需要载定义一个指针n在两个节点交换顺序前将下一组参与比较的两个节点的前节点存下来在比较后再把这个值赋给curr保证在每轮冒泡中是依次比较每个位置的。void linklist_bubble_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phea-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; node_t *end NULL; node_t *curr NULL; node_t *next NULL; for(p phead-next;p-next!NULL;p p-next)//控制冒泡的轮数 { node_t *prev phead;//每轮冒泡参与的数都要从头开始prev也就是头节点 for(q phead-next;p-next!end;q q-next)//控制每轮冒泡参与比较的数 { curr q; next curr-next; node_t *m q-next;//存一下下一组比较的前节点应该处于的位置 if(q-next-data q-data) { //节点顺序交换 prev-next next; curr-next next-next; next-next curr; q m;//下一对比较的前节点应该处于的位置 } prev prev-next;这次比较后prev应该后移一个节点 } end q; } }这提醒我们在操作指针时我们不仅要关注指针指向的位置还要关注指针自身的位置17.单向链表的插入排序无效空链表和只有一个有效节点的链表不用排序思路与数组的插入排序思路相同将无序区中的数据插入到有序区中。首先让首节点的nextNULL将整个链表分为有序区和无序区头节点和首节点看作有序区后面的节点看作无序区将无序区的节点ptemp与有序区的节点从首节点开始依次比较找到比它大的节点的前一个节点p让p的next指向ptemp然后让ptemp的next指向比它大的那个节点。void linklist_insert_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *ptemp phead-next-next;//无序区里要来插入的节点的第一个节点是首节点后的节点 phead-next-next NULL;//让原先的首节点的nextNULL使整个链表分为有序区和无序区 while(ptemp!NULL)无序区的节点还没处理完 { node_t *pnext ptemp-next;//先记录一下下一个要来插入的节点 node_t *p phead;//每次判断要插入的位置都要从头开始 while(p-next!NULLp-next-data ptemp-data)//没找到比这个数大的节点的前一个节点 { p p-next;//继续找 } ptemp-next p-next;//让要插入的节点的next指向比它大的那个节点 p-next ptemp;//让p的next指向要插入的节点实现链接 ptemp pnext;//去处理下一个节点 }
具有线性关系的数据可以选择链式存储链式存储每个环上要有自己的数据和下一个数据的地址1.单向链表的创建思路创建一个头节点代表这个链表开始的地方不关心头节点的数据头节点指向NULL同时要返回头节点的地址后续对链表的增删改等操作要通过这个地址实现。#include stdio.h #include stdlib.h typedef int data_t;//后续如果要更改数据类型只需要在这里修改 typedef struct node { data_t data;//节点的数据阈 存放的是这个节点的数据 struct node *next;//节点的指针域 指向下一个节点的地址 }node_t; node_t *linklist_creat(void)//返回链表的指针 { node_t *head malloc(sizeof(node_t)); if(head NULL)//判断malloc是否成功 { printf(listlist_creat fail\n); return NULL; } head-next NULL;//空链表头节点的next指向NULL return head; }2.单向链表的头插思路要创建一个新节点要插入的数据存在这个新节点的数据域中将这个新节点插入头节点后成为新的首节点新节点的next指向原本的首节点的地址。int linkist_insert_head(node_t *phead,data_t data)//返回0表示插入成功 非0失败 { if(pheadNULL)//有效性判断 { return -1; } node_t *pnew malloc(sizeof(node_t));//创建新节点并判断是否创建成功 if(pnewNULL) { printf(pnew malloc fail\n); return -1; } pnew-data data;//新节点创建成功把要插入的数据放到它的数据域里 node_t *q phead-next;//记录一下原先的首节点 pnew-next q;//新节点指向原先的首节点 phead-next pnew;//头节点指向pnewpnew成为新的首节点 return 0; } //特殊情况分析向空链表头插qNULLpnew的next指向NULL成为了尾节点phead的next指向pnew 结果正确没有问题上面的一般情况适用不需要做代码调整3.判断单向链表是不是空链表思路空链表的头节点指针域指向NULL。int is_empty(node_t *phead)//返回1表示空 0为非空 { if(pheadNULL)//有效性判断 { return 0; } if(phead-nextNULL) { return 1; } return 0; }4.单向链表的打印思路首先无效链表和空链表不能打印如果可以打印定义一个指针p从首节点开始打印每次打印完p后移一位到下一个节点直到将尾节点打印完p后移一位变为NULL时不能打印了int linklist_print(node_t *phead)//返回0表示成功打印非0表示失败 { if(pheadNULL||is_empty(phead)1)//无效和空链表不打印 { return -1; } node_t *p phead-next;//从首元素开始 while(p!NULL) //没有将所有数据打印完打印完pNULL { printf(%d ,p-data); p p-next;//这个数据打印完准备去打印下一个节点 } putchar(\n); return 0; }5.计算单向链表长度思路无效链表没有长度定义一个num初始为0计算有效节点数量定义一个指针p从首节点开始当这个节点不为NULLsum然后p再后移一个节点当所有有效节点计算完后pNULL退出返回sumint length(node_t *phead)//返回有效节点个数 { if(pheadNULL)//有效性判断 { return -1; } int sum 0;//初始为0 node_t *p phead-next;//从首节点开始 while(p!NULL) { sum;//是有效节点sum1 p p-next;//准备去判断下一个节点 } return sum; } //特殊情况空链表p phead-next NULL,直接跳过while循环返回sum的初值0正确。不需要对上面的 代码进行调整6.单链表尾插思路先创建一个新链表将要插入的数据存到新链表的数据域中找到链表中的尾节点p-nextNULL原先尾节点的next指向新节点让新节点的nextNULL成为新的尾节点int linklist_insert_tail(node_t *phead,data_t data)//成功插入返回0非0不成功 { if(pheadNULL) { return -1; } node_t *pnew malloc(sizeof(node_t));//创建新节点 if(pnewNULL)//判断是否创建成功 { return -1; } pnew-data data;//新节点创建成功将数据放进来 node_t *p phead;//从头节点开始判断因为空链表也能尾插空链表的头节点也相当于它 的尾节点满足p-next如果不从头节点开始这种情况会被忽略 while(p-next!NULL)//一直找到尾节点 { p p-next; } //程序走到这个位置就已经找到尾节点了 p-next pnew;//原先的尾节点指向pnew pnew-next NULL;//pnew成为新的尾节点 return 0 }7.在单向链表中查找数据思路无效链表和空链表不用找。我们不关心头节点里的数据从首节点一直找到尾节点看这些节点数据域里的数据和要查的数据是否相等相等就是找到了返回这个节点的地址一直找完所有有效节点pNULL说明所有的这个链表里没有要找的数返回NULL。node_t *linklist_find_key(node_t *phead,data_t key) { if(pheadNULL||is_(phead)1) { return NULL; } node_t *p phead-next;//从首节点开始找 while(p!NULL)//所有的数找完时pNULL 没找完继续找 { if(p-data key)//判断是不是要找的数 { return p;//找到了返回这个节点的地址 } p p-next;//没找到后移一位继续找 } return NULL;//全部有效节点找完还是没有找到返回NULL }8.修改单向链表中的值思路无效和空链表不能修改。先找到这个数所在的节点然后修改它的数据域为新值。修改成功返回这个节点的地址不成功返回NULLnode_t *linklist_updata(node_t *phead,data_t old,data_t new) { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p linklist_find_key(phead,old);//接收查找的结果 NULL表示没找到 非NULL是找到的 这个数据的节点的地址 if(p!NULL)//找到了更新数据域 { p-data new; } return NULL;//没找到返回NULL }9.删除单向链表中的某个节点思路无效链表和空链表不能删。正常思路是找到这个要删的节点但是删除这个节点后我们还要把这个节点前面的节点和它后面的节点链接起来如果一直找到要删的节点因为链表是单向的无法表达出它前面的那个节点所以我们要一直找到要删节点的前一个节点pp-next-datakey,节点q p-next是要删除的节点q-next是要删节点的后一个节点这样找到并表达出三个节点后让要删节点的前一个节点的next指向要删节点的后一个节点这样那两部分就链接起来了然后我们释放掉要删除的节点。有可能我们要删除的是只有一个有效节点链表的首节点那么头节点就是p所以p要从头节点开始找。int linklist_delete_key(node_t *phead,data_t data)//返回0表示成功删除 非0不成功 { if(pheadNULL||is_empty(phead)1) { return -1; } node_t *p phead; while(p-next!NULL)//当一直找完所有数据找到尾节点时p-nextNULL 没找完继续找 { if(p-next-datakey)//找到了 { node_t *q p-next;//记录要删除的节点 p-next q-next;//要删的前一个指向要删的后一个 链接起来 free(q);//释放要删节点的空间 q NULL; return 0; } pp-next;//没找到继续找 } return -1;//全部有效数据都找完了还是没有返回-1 }10.销毁单向链表思路无效不用销毁。从头节点开始删最后将这个指向头节点的指针的地址也释放掉因为我们要操作这个指针的地址所以我们要把头节点指针传参进来进行修改。int linklist_destory(node_t **pphead)//返回0表示成功销毁 非0表示失败 { if(ppheadNULL) { return -1; } node_t *p *pphead;//要销毁的节点从头节点开始但是如果直接把他销毁了就找不到下一个要销毁 的节点了所以下面定义一个q指向下一个待删的节点 node_t *q NULL; while(p!NULL) { q p-next;//下一个待删的节点 free(p);//释放这个节点 p NULL; p q;//准备去处理下一个节点 } *ppheadNULL;//将指向头节点的指针也释放掉 return 0 }11.找到单向链表的中间节点思路无效链表和空链表不用找。定义一对快慢指针都从头节点开始走快指针p一次走两步慢指针q一次走一步这样快指针走的总长度是慢指针的二倍当快指针走完时慢指针停下的位置就是中间节点。那快指针什么时候停下呢对于有效节点数是奇数的链表快指针走到NULL时慢指针停下来的位置是中间节点对于有效节点数是偶数的链表快指针走到尾节点时慢指针停下的位置是中间节点。node_t *linklist_find_mid(node_t *phead)//找到了返回中间节点的地址 { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p phead;//快指针 node_t *q phead;//慢指针 while(p!NULLp-next!NULL)//既没有到达奇数节点结束结束条件也没有到达偶数节点结束条件 { p p-next-next;//快指针走两步 q q-next;//慢指针走一步 } return q;//返回结束时慢指针指向的节点地址就是中间节点的地址 }12.找到单向链表中的倒数第K个节点思路无效链表和空链表不用找。定义一对指针都从头节点开始走p指针先走k步后p指针再和q指针一起走每次一步这样p指针与q指针始终相隔k个节点当p指针走向NULL时q指针指向的节点就是链表中倒数第k个节点。node_t *linklist_find_behind_key(node_t* phead,int k)//找到了返回节点地址 { if(pheadNULL||is_empty(phead)1) { return NULL; } node_t *p phead;//先走的指针 node_t *q phead; int i; for(i0;ikey;i)//先走k步 { p p-next; } while(p!NULL)//没有到达结束条件 { p p-next;//p和q一起每次走一步 q q-next; } return q;//到达结束条件了返回q指向节点的地址 }13.判断单向链表中是否有环思路单线链表和空链表不用判断。如果一个链表是有环的那在这个链表中不会有节点的next指向NULL这可以作为判断条件。定义一对快慢指针从头结点开始走快指针每次走两步慢指针每次走一步就像两个人在操场跑步一个慢一个快因为操场是个环总归有跑的快的多跑了一整圈与跑的慢的相遇的时候在链表表中如果快指针p在走的过程中没有走到NULL并且在某一刻与慢指针q相等那这个链表就是有环的。int linklist_is_circle(node_t *phead)//返回1说明有环 返回0无环 { if(pheadNULL||is_empty(phead)1) { return 0; } node_t *p phead; node_t *q phead; while(p!NULLp-next!NULL)//奇数偶数节点条件下都还没有找到NULL 说明目前还可能有环 { p p-next-next;//快指针走两步 q q-next;//慢指针走一步 if(p q)//判断是否相遇相遇说明有环返回1 不相遇判断是否到达结束条件没有就继续找 { return 1; } } return 0;//在走的过程中发现了有节点的next指向NULL说明无环 返回0 }14.将单向链表逆序无效空链表和只有一个有效节点的链表不用逆序思路①先将首节点的next指向NULL头节点和首节点断开整个链表变成一个空链表和一个没有头节点全是有效节点的链表将无头链表中的节点从首到尾依次头插到空链表中这样当尾节点插入完毕后整个链表就逆序了。void linklist_reverse(node_t *phead) { if(pheadNUL||is_empty(phead)1||phead-next-nextNULL) { return;//无效空链表只有一个有效节点的链表不用逆序 } node_t *p phead-next;//从首节点开始但如果不保存一下下一个要处理的节点首节点头插结束就 //无法表达下一个要处理的节点所以下面定义一个指针p指向要处理的节点 //的下一个节点 node_t *q NULL; while(p!NULL)//所有节点还没处理好 { q p-next;//先处理一下下一个节点 p-next phead-next;//头插 phead-next p; p q;//去处理下一个位置 } }思路②先忽略头节点从方向上看正序的链表是每个节点的next向后值那逆序的链表就是每个节点的next向前指向前面处理好的链表的最后一个节点这样结束后再让头节点的next指向逆序好的无头链表的最后一个节点这样就实现了链表的逆序。在操作时由于链表是单向的我们需要表示当下要处理的节点curr前面逆序操作后的链表的最后一个节点prev下一个要处理的节点next。curr从首节点开始它的next要指向prev但是在它之前还没有过逆序操作并且可以知道它会成为逆序后的链表的尾节点所以我们要设prev的初值为NULL。结束条件是要处理完了所有有效节点curr走到了NULL。void linklist_reverse_threePoints(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *curr phead-next;//从首节点开始处理 node_t *prev NULL; node_t *next NULL; while(curr!NULL)//没有到达结束条件还有节点没有参与逆序 { next curr-next;//下一个要处理的节点 curr-next prev;//当下节点的next指向前面逆序了一部分完成的链表的最后一个节点prev prev curr;//上一步结束后这个处理后的链表的最后有一个节点已经变为了curr要更新一下 curr next;//去处理下一个节点 } phead-next prev;//上面的循环结束后prev来到了原先的尾节点现在它成为了新链表的首节点 //让头节点的next指向它完成链接这样整个链表的逆序就完成了 }15.单向链表的选择排序无效空链表和只有一个有效节点的链表不用排序思路与数组选择排序的思路相同就是定位擂台打擂台最小的数据留在擂台上如果有n个数据只需要打前n-1个擂台每次比较后擂台后移前面决胜出来的数不需要比较了剩下所有的数都要参与比较。void linklist_select_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; for(p phead-next;p-next!NULL;pp-next)//控制打擂台的位置从首节点到尾节点的前一个节点 { for(q p-next;q!NULL;q q-next)//控制每轮打擂台的数从擂台的下一个节点到尾节点 //都要参与比较 { if(q-data p-data)//判断这个节点的数据域是不是擂台节点的数据域小 //小的话交换它们的数据域 { data_t t q-data; q-data p-data; p-data t; } } } }16.单向链表的冒泡排序无效空链表和只有一个有效节点的链表不用排序思路与原先数组的冒泡排序思路相同从首节点开始依次与它后面的节点比较比较大的数放在后面这样比完一轮最后一个节点的数据域就是最大的数下次比较排除到这个这个节点剩下的节点再进行一轮冒泡……如果有n个数据一共要比n-1轮冒出n-1个数剩下的那个数自然就是最小的数。void linklist_bubble_sort(phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; node_t *end NULL; for(p phead-next;p-next!NULL;p p-next)//控制比较的轮数 从首节点到尾节点的前一节点 //比较n-1轮 { for(q phead-next;q-next!end;q q-next)//控制每轮比较的数 { if(q-next-data q-data)//后一个数比前一个数小交换数据 { data_t t q-next-data; q-next-data q-data; q-data t; } } end q-next;//更新下一轮冒泡需要停止的位置 } }如果比较过程中需要交换将大的数据放在后面但是不想要交换数据域想要交换整个节点在链表中的顺序。参与比较的这两个节点分别是curr我们叫做当前节点和它后面的节点next我们叫做后节点要交换他们两个在链表中的顺序我们需要让前节点的前一个节点prev指向后节点前节点指向后节点的下一个节点最后让后节点指向前节点这样就完成了这两个节点顺序的交换。但是在每轮冒泡中我们需要依次让每个数与它后面的数相比较比如这次比较的前节点是链表中的第一个节点node1下次我们希望比较的前节点是链表中的第二个节点node2。我们规定前节点用curr表示那node1表示为curr这次比较后该比较下一组了下一组的前节点位置应该在链表中的第二个节点node2那node2能直接用上一轮curr-next表示吗这样是不对的因为在上一轮比较交换节点后curr在链表中的顺序已经变了变成了链表中的第二个节点了它的next是链表中第三个节点用它来表示node2当然是错的。所以为了解决这个问题我们需要载定义一个指针n在两个节点交换顺序前将下一组参与比较的两个节点的前节点存下来在比较后再把这个值赋给curr保证在每轮冒泡中是依次比较每个位置的。void linklist_bubble_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phea-next-nextNULL) { return; } node_t *p phead-next; node_t *q phead-next; node_t *end NULL; node_t *curr NULL; node_t *next NULL; for(p phead-next;p-next!NULL;p p-next)//控制冒泡的轮数 { node_t *prev phead;//每轮冒泡参与的数都要从头开始prev也就是头节点 for(q phead-next;p-next!end;q q-next)//控制每轮冒泡参与比较的数 { curr q; next curr-next; node_t *m q-next;//存一下下一组比较的前节点应该处于的位置 if(q-next-data q-data) { //节点顺序交换 prev-next next; curr-next next-next; next-next curr; q m;//下一对比较的前节点应该处于的位置 } prev prev-next;这次比较后prev应该后移一个节点 } end q; } }这提醒我们在操作指针时我们不仅要关注指针指向的位置还要关注指针自身的位置17.单向链表的插入排序无效空链表和只有一个有效节点的链表不用排序思路与数组的插入排序思路相同将无序区中的数据插入到有序区中。首先让首节点的nextNULL将整个链表分为有序区和无序区头节点和首节点看作有序区后面的节点看作无序区将无序区的节点ptemp与有序区的节点从首节点开始依次比较找到比它大的节点的前一个节点p让p的next指向ptemp然后让ptemp的next指向比它大的那个节点。void linklist_insert_sort(node_t *phead) { if(pheadNULL||is_empty(phead)1||phead-next-nextNULL) { return; } node_t *ptemp phead-next-next;//无序区里要来插入的节点的第一个节点是首节点后的节点 phead-next-next NULL;//让原先的首节点的nextNULL使整个链表分为有序区和无序区 while(ptemp!NULL)无序区的节点还没处理完 { node_t *pnext ptemp-next;//先记录一下下一个要来插入的节点 node_t *p phead;//每次判断要插入的位置都要从头开始 while(p-next!NULLp-next-data ptemp-data)//没找到比这个数大的节点的前一个节点 { p p-next;//继续找 } ptemp-next p-next;//让要插入的节点的next指向比它大的那个节点 p-next ptemp;//让p的next指向要插入的节点实现链接 ptemp pnext;//去处理下一个节点 }
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
