单链表专题
前言
顺序表和单链表都是两种常见的数据结构，他们的区别究竟在哪里？
顺序表：顺序表是一种连续的存储结构，数据元素在内存中占据一块连续的空间。因为连续空间存储的特性，顺序表可以直接通过下表遍历元素。
单链表：单链表是一种离散的存储结构，数据元素存储在节点中，节点中包含数据和下一节点的指针。
总结：顺序表和单链表的区别在于他们的存储方式不同，顺序表是连续存储，单链表则是离散存储，单链表相对于顺序表的优势是，单链表可以降低操作时的时间复杂度。
1.链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序使通过链表中的指针链接次序实现的。
链表的结构就像这个小火车，每一个车厢就是一个节点，节点包括数据（车厢里的货物）和下一个节点的指针（车厢之间的抓钩）。
在链表中的小火车就像这样
每个节点对应的结构体代码就可以这样写出（假设当前保存的节点为整型）
typedef struct SListNode { int data; //节点数据 struct SListNode* next； //指针变量 用来保存下一个节点的地址 }SLTNode;我们想要保存⼀个数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存数
据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址就可以了。
那在链表结构中，如何实现节点从头到尾的打印？
void SLTPrint(SLTNode* phead){ SLTNode *pcur = phead; while(pcur) { printf("%d ",pcur->data); pcur = pcur->next; } printf("\n"); }测试样例：
void SlistTest01(){ SLTNode* node1 = (SLTNode* )malloc(sizeof(SLTNode)); node1->data = 1; SLTNode* node2 = (SLTNode* )malloc(sizeof(SLTNode)); node1->data = 2; SLTNode* node3 = (SLTNode* )malloc(sizeof(SLTNode)); node1->data = 3; SLTNode* node4 = (SLTNode* )malloc(sizeof(SLTNode)); node1->data = 4; //此时创建好了节点数据 但还没有实现节点链接 node1-> = node2; node2-> = node3; node3-> = node4; node4-> = NULL; } void SLTPrint(SLTNode* phead){ SLTNode *pcur = phead; while(pcur) { printf("%d ",pcur->data); pcur = pcur->next; } printf("NULL\n"); } SLTNode* plist = node1; SLtPrint(plist);测试结果
2.单链表的实现
2.1单链表的尾插
typedef char SLTDataType; SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode = (SLTNode* )malloc(sizeof(SLTNode)); if(newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = NULL; return newnode; } void SLTPushBack(SLTNode** pphead,SLTDataType x){ assert(pphead); SLTNode* newnode = SLTBuyNode(x); //链表为空 新节点为phead if(*pphead == NULL) { *pphead = newnode; return; } //链表不为空 找尾结点 //为了不改变头结点 设置临时结构体变量 SLTNode* ptail = *pphead; while(ptail->next) { ptail = ptail->next; } //ptail就是尾结点 ptail->next = newnode; }测试样例：
void SlistTest02() { SLTnode* plist = NULL; SLTPushback(&plist,1); SLTPushback(&plist,2); SLTPushback(&plist,3); SLTPushback(&plist,4); SLTPrint(plist); //结果 1->2->3->4->NULL }运行结果
2.2单链表的头插
void SLTPushFront(SLTNode** pphead,SLTDataType x) { assert(pphead); SLTNode* newnode = SLTBuyNode(x); new->next=*pphead; *pphead = newnode; }测试样例
void SlistTest03(){ SLTPushFront(&plist,5); SLTPrint(plist); SLTPushFront(&plist,6); SLTPrint(plist); SLTPushFront(&plist,7); SLTPrint(plist); }结果
7->6->5->NULL
2.3 链表的头删和尾删
//单链表的尾删 void SLTPopBack(SLTNode** pphead){ assert(pphead); //pphead链表不能为空 *phead首节点也不能为空 assert(*pphead); //链表不为空 //链表只有一个节点，有多个节点 if((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; return; } SLTNode* ptail = *pphead; SLTNode* prev = NULL; //存放前区节点 while(ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; //销毁尾结点 free(ptail); ptail = NULL; } //单链表的头删 void SLTPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); //链表不能为空 //让第二个节点成为新的头 同时把旧的头结点释放掉 SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } //测试 SLTPopBack(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist);2.4 链表的查找
SLTNode* SLTFind(SLTNode** pphead,SLTDataType x) { assert(pphead); //遍历链表 SLTNode* pcur = *pphead； while(pcur) //等价于pcur != NULL { if(pcur->data == x){ return pcur;} } //没有找到 return NULL; } //测试 SLTNode* FindRet = SLTFind(&plist); if(FindRet) { printf("找到了!"); } else{ printf("未找到!"); }2.5 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x){ assert(pphead); assert(pos); assert(*pphead); //链表也不能为空 因为传入的指定节点也不能为空 SLTNode* newnode = SLTBuyNode(x); //当pos刚好是头结点时 if(pos == *pphead) { SLTPushFront(pphead,x);/头插 return; } //以下为pos不是头结点的情况 SLTNode* prev = *pphead; while(prev->next!=pos) { prev = prev->next; } } //测试 SLTNode* FindRet = SLTFind(&plist,4); SLTInsert(&plist,FindRet,100); SLTPrint(plist);2.6 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos,SLTDataType x) { assert(pos); //传入节点不能为空 SLTNode* newnode = SLTBuyNode(x); //创建新节点 newnode->next = pos->next; //先接新节点后 再接新节点前 pos->next = newnode; } //测试 void SlistTest03(){ SLTNode* plist = NULL; SLTPushBack(&plist,1); SLTPushBack(&plist,2); SLTPushBack(&plist,3); SLTPushBack(&plist,4); SLTPrint(plist); //1->2->3->4->NULL SLTNode* FindRet = SLTFind(&plist,1); SLTInsertAfter(FindRet,100); SLTPrint(plist); //1->100->2->3->4->NULL }