單鏈表

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

1. 單向、雙向
2. 帶頭、不帶頭
3. 循環、非循環

雖然有這么多的鏈表的結構，但是我們實際中最常用還是兩種結構：

1. 無頭單向非循環鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結 構，如哈希桶、圖的鄰接表等等。另外這種結構在學校的考試中出現很多。
2. 帶頭雙向循環鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向 循環鏈表。另外這個結構雖然結構復雜，但是使用代碼實現以后會發現結構會帶來很多優勢，實現反而 簡單了

實現不帶頭單鏈表以及相關操作

頭文件

#pragma oncetypedef int SLDateType;//一個結點
typedef struct SLNode{SLDateType value;struct SLNode *next;
}	SListNode;//不帶頭動態鏈表
typedef struct SList{SListNode *first;
}SList;//初始化
void SListInit(SList *list);
//銷毀
void SListDestroy(SList *list);
//增
//頭插
void SListPushFront(SList *list, SLDateType value);
//尾插
void SListPushBack(SList *list, SLDateType value);//刪
//頭刪
void SListPopFront(SList *list);
//尾刪
void SListPopBack(SList *list);//打印
void SListPrint(const SList *list);//改
void SListUpdata(SListNode *node, SLDateType value);//查
//去查找鏈表中遇到的第一個value，如果沒找到，返回NULL
SListNode *SListFind(const SList *list, SLDateType value);//打印
void SListPrint(const SList *list);void SListInsertBefore(SList *list, SListNode *pos, SLDateType value);
// 在pos的后面插入
void SListInsertAfter(SListNode *pos,SLDateType value); 
// 刪除pos位置的節點 
void SListEraseAfter(SListNode *pos); 
void ListRemove();

功能實現

#include"SList.h"
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<stdio.h>//初始化
void SListInit(SList *list){assert(list != NULL);list->first = NULL;
}//申請新結點
SListNode* BuyNode(SLDateType value){SListNode *node = (SListNode*)malloc(sizeof(SListNode));assert(node);node->value = value;node->next = NULL;return node;
}
//頭插
void SListPushFront(SList *list, SLDateType value){SListNode *node = (SListNode*)malloc(sizeof(SListNode));assert(node);node->value = value;node->next = list->first;list->first = node;
}//頭刪
void SListPopFront(SList *list){assert(list != NULL);       //鏈表存在assert(list->first != NULL);  //鏈表不為空，里面有結點SListNode *old_first = list->first;list->first = list->first->next;free(old_first);
}
//尾插
void SListPushBack(SList *list, SLDateType value){assert(list != NULL);if (list->first == NULL){ //鏈表中沒有結點的情況就跟頭插的情況是一樣的SListPushFront(list, value);return;}//鏈表中有結點的情況SListNode *cur;for (cur = list->first; cur->next != NULL; cur = cur->next);//cur就是最后一個結點SListNode *node = BuyNode(value);cur->next = node;
}//尾刪
void SListPopBack(SList *list){assert(list != NULL);assert(list->first != NULL);//只有一個結點if (list->first->next == NULL){SListPopFront(list);return;}SListNode *cur = list->first;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL; 
}//銷毀
void SListDestroy(SList *list){assert(list != NULL);SListNode *cur = list->first;SListNode *next;while (cur!=NULL){next = cur->next;free(cur);cur = cur->next;}list->first = NULL;
}//打印
void SListPrint(const SList *list){for (SListNode *cur = list->first; cur != NULL; cur = cur->next){printf("%d--->", cur->value);}printf("\n");
}//改
void SListUpdata(SListNode *node, SLDateType value){node->value = value;
}//去查找鏈表中遇到的第一個value，如果沒找到，返回NULL
SListNode *SListFind(const SList *list, SLDateType value){for (SListNode *cur = list->first; cur != NULL; cur = cur->next){if (cur->value == value){return cur;}}return NULL;
}//pos 一定是鏈表中有效結點
//向后面插入
void SListInsertAfter(SListNode *pos, SLDateType value){SListNode *node = BuyNode(value); //申請結點node->next = pos->next;pos->next = node;
}// 刪除pos后面位置的節點 
void SListEraseAfter(SListNode *pos){SListNode *next = pos->next;pos->next = next->next;free(next);}//向pos前面插入
void SListInsertBefore(SList *list, SListNode *pos, SLDateType value){SListNode *cur;SListNode *node = BuyNode(value);for (cur = list->first; cur->next != pos; cur = cur->next);node->next = pos;cur->next = node;
}

測試用例

#include"SList.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>void TestList1(){SList list;SListInit(&list);assert(list.first == NULL);/*SListPushFront(&list, 1);SListPushFront(&list, 2);SListPushFront(&list, 3);//3 2 1*/SListPushBack(&list, 11);SListPushBack(&list, 12);SListPushBack(&list, 13);//3 2 1 11 12 13/*SListPopBack(&list);SListPopBack(&list);SListPopBack(&list);*/SListNode *n12 = SListFind(&list, 12);assert(n12 != NULL);SListPrint(&list);SListInsertAfter(n12, 103);SListPrint(&list);SListEraseAfter(n12);SListPrint(&list);SListInsertBefore(&list,n12, 101);SListPrint(&list);printf("大成功\n");
}int main()
{TestList1();system("pause");return 0;
}