数据结构—单链表

目录

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位置之后的值可知，单链表没有完全解决顺序表的缺陷，所以我们后面学习双向的链表来提高效率。