深圳福田区住房和建设局网站官网/国际新闻界官网
目录
1.前言
2.了解单链表
3.单链表代码实现
3.1 单链表结构体实现
3.2 创建节点
3.3 打印单链表
3.4 尾插
3.5 头插
3. 6 头删
3.7 尾删
3.8 查找
3.9 插入
3.9.1 在pos位置之前插入
3.9.2 在pos位置之后插入（主要使用这种功能）---不需要找pos前一个
3.10 删除
3.10.1 删除pos位置的值
3.10.2 删除pos后一个（主要使用这种功能）---不需要找pos前一个
3.11 单链表总结
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 nextpos->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位置之后的值可知，单链表没有完全解决顺序表的缺陷，所以我们后面学习双向的链表来提高效率。