具有线性关系的数据可以选择链式存储，链式存储每个环上要有自己的数据和下一个数据的地址
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(phead==NULL)//有效性判断 { return -1; } node_t *pnew = malloc(sizeof(node_t));//创建新节点并判断是否创建成功 if(pnew==NULL) { printf("pnew malloc fail\n"); return -1; } pnew->data = data;//新节点创建成功把要插入的数据放到它的数据域里 node_t *q = phead->next;//记录一下原先的首节点 pnew->next = q;//新节点指向原先的首节点 phead->next = pnew;//头节点指向pnew，pnew成为新的首节点 return 0; } //特殊情况分析：向空链表头插，q=NULL，pnew的next指向NULL成为了尾节点，phead的next指向pnew 结果正确没有问题，上面的一般情况适用不需要做代码调整3.判断单向链表是不是空链表
思路：空链表的头节点指针域指向NULL。
int is_empty(node_t *phead)//返回1表示空 0为非空 { if(phead==NULL)//有效性判断 { return 0; } if(phead->next==NULL) { return 1; } return 0; }4.单向链表的打印
思路：首先无效链表和空链表不能打印，如果可以打印，定义一个指针p，从首节点开始打印，每次打印完p后移一位到下一个节点，直到将尾节点打印完，p后移一位变为NULL时不能打印了
int linklist_print(node_t *phead)//返回0表示成功打印，非0表示失败 { if(phead==NULL||is_empty(phead)==1)//无效和空链表不打印 { return -1; } node_t *p = phead->next;//从首元素开始 while(p!=NULL) //没有将所有数据打印完，打印完p==NULL { printf("%d ",p->data); p = p->next;//这个数据打印完准备去打印下一个节点 } putchar('\n'); return 0; }5.计算单向链表长度
思路：无效链表没有长度，定义一个num初始为0，计算有效节点数量，定义一个指针p，从首节点开始，当这个节点不为NULL，sum++，然后p再后移一个节点，当所有有效节点计算完后，p==NULL，退出返回sum
int length(node_t *phead)//返回有效节点个数 { if(phead==NULL)//有效性判断 { return -1; } int sum = 0;//初始为0 node_t *p = phead->next;//从首节点开始 while(p!=NULL) { sum++;//是有效节点sum+1 p = p->next;//准备去判断下一个节点 } return sum; } //特殊情况：空链表p = phead->next = NULL,直接跳过while循环，返回sum的初值0，正确。不需要对上面的 代码进行调整6.单链表尾插
思路：先创建一个新链表，将要插入的数据存到新链表的数据域中，找到链表中的尾节点（p->next==NULL），原先尾节点的next指向新节点，让新节点的next=NULL成为新的尾节点
int linklist_insert_tail(node_t *phead,data_t data)//成功插入返回0，非0不成功 { if(phead==NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t));//创建新节点 if(pnew==NULL)//判断是否创建成功 { 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.在单向链表中查找数据
思路：无效链表和空链表不用找。我们不关心头节点里的数据，从首节点一直找到尾节点，看这些节点数据域里的数据和要查的数据是否相等，相等就是找到了，返回这个节点的地址，一直找完所有有效节点p=NULL，说明所有的这个链表里没有要找的数，返回NULL。
node_t *linklist_find_key(node_t *phead,data_t key) { if(phead==NULL||is_(phead)==1) { return NULL; } node_t *p = phead->next;//从首节点开始找 while(p!=NULL)//所有的数找完时p=NULL 没找完继续找 { if(p->data == key)//判断是不是要找的数 { return p;//找到了返回这个节点的地址 } p = p->next;//没找到后移一位继续找 } return NULL;//全部有效节点找完还是没有找到返回NULL }8.修改单向链表中的值
思路：无效和空链表不能修改。先找到这个数所在的节点，然后修改它的数据域为新值。修改成功返回这个节点的地址，不成功返回NULL
node_t *linklist_updata(node_t *phead,data_t old,data_t new) { if(phead==NULL||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.删除单向链表中的某个节点
思路：无效链表和空链表不能删。正常思路是找到这个要删的节点，但是删除这个节点后我们还要把这个节点前面的节点和它后面的节点链接起来，如果一直找到要删的节点，因为链表是单向的，无法表达出它前面的那个节点，所以我们要一直找到要删节点的前一个节点p（p->next->data==key）,节点q = p->next是要删除的节点，q->next是要删节点的后一个节点，这样找到并表达出三个节点后，让要删节点的前一个节点的next指向要删节点的后一个节点，这样那两部分就链接起来了，然后我们释放掉要删除的节点。有可能我们要删除的是只有一个有效节点链表的首节点，那么头节点就是p，所以p要从头节点开始找。
int linklist_delete_key(node_t *phead,data_t data)//返回0表示成功删除 非0不成功 { if(phead==NULL||is_empty(phead)==1) { return -1; } node_t *p = phead; while(p->next!=NULL)//当一直找完所有数据找到尾节点时，p->next==NULL 没找完继续找 { if(p->next->data==key)//找到了 { node_t *q = p->next;//记录要删除的节点 p->next = q->next;//要删的前一个指向要删的后一个 链接起来 free(q);//释放要删节点的空间 q = NULL; return 0; } p=p->next;//没找到继续找 } return -1;//全部有效数据都找完了还是没有返回-1 }10.销毁单向链表
思路：无效不用销毁。从头节点开始删，最后将这个指向头节点的指针的地址也释放掉，因为我们要操作这个指针的地址，所以我们要把头节点指针传参进来，进行修改。
int linklist_destory(node_t **pphead)//返回0表示成功销毁 非0表示失败 { if(pphead==NULL) { return -1; } node_t *p = *pphead;//要销毁的节点，从头节点开始，但是如果直接把他销毁了就找不到下一个要销毁 的节点了，所以下面定义一个q指向下一个待删的节点 node_t *q = NULL; while(p!=NULL) { q = p->next;//下一个待删的节点 free(p);//释放这个节点 p = NULL; p = q;//准备去处理下一个节点 } *pphead==NULL;//将指向头节点的指针也释放掉 return 0； }11.找到单向链表的中间节点
思路：无效链表和空链表不用找。定义一对快慢指针，都从头节点开始走，快指针p一次走两步，慢指针q一次走一步，这样快指针走的总长度是慢指针的二倍，当快指针走完时，慢指针停下的位置就是中间节点。那快指针什么时候停下呢，对于有效节点数是奇数的链表，快指针走到NULL时，慢指针停下来的位置是中间节点；对于有效节点数是偶数的链表，快指针走到尾节点时，慢指针停下的位置是中间节点。
node_t *linklist_find_mid(node_t *phead)//找到了返回中间节点的地址 { if(phead==NULL||is_empty(phead)==1) { return NULL; } node_t *p = phead;//快指针 node_t *q = phead;//慢指针 while(p!=NULL&&p->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(phead==NULL||is_empty(phead)==1) { return NULL; } node_t *p = phead;//先走的指针 node_t *q = phead; int i; for(i=0;i<key;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(phead==NULL||is_empty(phead)==1) { return 0; } node_t *p = phead; node_t *q = phead; while(p!=NULL&&p->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(phead==NUL||is_empty(phead)==1||phead->next->next==NULL) { 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(phead==NULL||is_empty(phead)==1||phead->next->next==NULL) { 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(phead==NULL||is_empty(phead)==1||phead->next->next==NULL) { return; } node_t *p = phead->next; node_t *q = phead->next; for(p = phead->next;p->next!=NULL;p=p->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(phead==NULL||is_empty(phead)==1||phead->next->next==NULL) { 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(phead==NULL||is_empty(phead)==1||phea->next->next==NULL) { 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.单向链表的插入排序（无效，空链表和只有一个有效节点的链表不用排序）
思路：与数组的插入排序思路相同，将无序区中的数据插入到有序区中。首先让首节点的next=NULL，将整个链表分为有序区和无序区，头节点和首节点看作有序区，后面的节点看作无序区，将无序区的节点ptemp与有序区的节点从首节点开始依次比较，找到比它大的节点的前一个节点p，让p的next指向ptemp，然后让ptemp的next指向比它大的那个节点。
void linklist_insert_sort(node_t *phead) { if(phead==NULL||is_empty(phead)==1||phead->next->next==NULL) { return; } node_t *ptemp = phead->next->next;//无序区里要来插入的节点的第一个节点是首节点后的节点 phead->next->next = NULL;//让原先的首节点的next=NULL，使整个链表分为有序区和无序区 while(ptemp!=NULL)无序区的节点还没处理完 { node_t *pnext = ptemp->next;//先记录一下下一个要来插入的节点 node_t *p = phead;//每次判断要插入的位置都要从头开始 while(p->next!=NULL&&p->next->data < ptemp->data)//没找到比这个数大的节点的前一个节点 { p = p->next;//继续找 } ptemp->next = p->next;//让要插入的节点的next指向比它大的那个节点 p->next = ptemp;//让p的next指向要插入的节点实现链接 ptemp = pnext;//去处理下一个节点 }
