1.前言
学习了顺序表发现有以下缺点：
1.1 空间不够，需要扩容（扩容有一定的空间浪费）。
1.2 头插、头删（需要移动数据）时间复杂度是O(N)，效率低。
所以我们学习单链表来按需申请释放空间，不需要移动数据，提高效率。
2.了解单链表
概念：单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
特点：每个结点除了存放数据元素外，还要存储指向下一个节点的指针
优点：不要求大片连续空间，改变容量方便。。
缺点：不可随机存取，要耗费一定空间存放指针。
单链表逻辑及重要性：
3.单链表代码实现
3.1 单链表结构体实现
typedef int SLTDataType; typedef struct SListNode { SLTDataType data;//存放数据 struct SListNode* next;//指向下一个结构体的指针 }SLTNode;
3.2 创建节点
void TestSList1() { //struct SListNode* SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode)); assert(n1); SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode)); assert(n2); SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode)); assert(n3); SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode)); assert(n4); n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; }
3.3 打印单链表
cur = cur->next理解:
第一次进来cur指向的是链表的头，cur=cur—>next说明把下一个节点的地址赋给cur，现在的cur指向的是第二个结构体，是第二个结构体的地址.......
循环下去就可以打印出节点里的data数据，直到cur=NULL。
void SListPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
3.4 尾插
注意点:
当链表为空的时候，newnode给phead时，由于phead是一个形参，函数中形参的改变不会改变实参。
这时要改变指针变量（plist）就要传指针变量的地址——就要传二级指针。
void SListPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点 SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
3.5 头插
单链表头插不需要和尾插一样要特殊处理
void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
3. 6 头删
void SListPopFront(SLTNode** pphead) { assert(*pphead != NULL);//暴力检查 //if (*pphead == NULL) //温柔检查 // return; SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
3.7 尾删
void SListPopBack(SLTNode** pphead) { assert(*pphead); // 1、只有一个节点 // 2、多个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //两种方法 /*SLTNode* tailPrev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { tailPrev = tail; tail = tail->next; } free(tail); tailPrev->next = NULL;*/ // SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
3.8 查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
3.9 插入
3.9.1 在pos位置之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); assert(ppheart); //头插 if (pos= *pphead) { SListPushFront(pphead.x)； } else { SLTNNode* prev= *ppheart; while(prev->next !=pos) { prev=prev->next; } SLTNode* newnode=BuySListNode(x); prev->next=newnode; newnode->next=pos; }
3.9.2 在pos位置之后插入（主要使用这种功能）---不需要找pos前一个
void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); /*SLTNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode;*/ // 不在乎链接顺序 SLTNode* newnode = BuySListNode(x); SLTNode* next = pos->next; // pos newnode next pos->next = newnode; newnode->next = next; }
3.10 删除
3.10.1 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pos); assert(ppheart); //头删 if (pos= *pphead) { SListPopFront(pphead); } else { SLTNode* prev= *pphesd; while(prev->next !=pos) { prev=prev->next; } prev->next= pos->next; free(pos); }
3.10.2 删除pos后一个（主要使用这种功能）---不需要找pos前一个
void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) return; SLTNode* del = pos->next; //pos->next = pos->next->next;//这样就释放不了节点 pos->next = del->next; free(del); del = NULL; }
3.11 单链表总结
由单链表的在pos位置之后插入和删除pos位置之后的值可知，单链表没有完全解决顺序表的缺陷，所以我们后面学习双向的链表来提高效率。
