网站建设和前端开发的区别,慈溪市网站开发,企业网站搭建及优化,微信免费下载2023新版目录
前言#xff1a;
1.概念
链表定义
结点结构体定义
结点的创建
2.链表的头插法
动画演示
代码实现
3.链表的尾插
动画演示
代码实现
4.链表的头删
动画演示
代码实现
5.链表的尾删
动画演示
代码实现
6.链表从中间插入结点
动画演示
代码实现
7.从单…
目录
前言
1.概念
链表定义
结点结构体定义
结点的创建
2.链表的头插法
动画演示
代码实现
3.链表的尾插
动画演示
代码实现
4.链表的头删
动画演示
代码实现
5.链表的尾删
动画演示
代码实现
6.链表从中间插入结点
动画演示
代码实现
7.从单链表中删除任意结点
动画演示
代码实现
8.销毁链表
动画演示
代码实现
完整代码 前言 前面我们已经把顺序表的优点和缺点讲了那么这篇文章就是单链表的这种数据结构的实现和理解。 1.概念
链表定义 链表是一种离散存储的数据结构它只有一个指针域下一个指针保存着前一个数据的地址像链子一样串起来的结构就叫做单链表。
n个节点离散分配 彼此通过指针相连每个节点只有一个前驱节点每个节点只有一个后续节点。首节点没有前驱节点尾节点没有后续节点。
结点结构体定义
struct ListNode {DataType data; //数据域struct ListNode*next; //指针域
}ListNode;
结点的创建
为链表创建新结点并分配内存把传进来的值赋给data, next置为空指针并返回新结点。
ListNode *ListCreateNode(DataType data) {ListNode *node (ListNode *) malloc ( sizeof(ListNode) );if (node NULL){perror(malloc);exit(-1);}node-data data;node-next NULL;return node;
}
2.链表的头插法
动画演示 链表的头插有两种情况 1.如果链表为空 执行头部插入 2.链表不为空需要找到链表的头再进行插入
情况 1的处理
当前是空链表插入之后成为头结点。
情况 2
当前链表不为空则需要找到当前头结点让新结点指向头结点头结点再指向新结点。
代码实现
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
3.链表的尾插
动画演示 代码实现
1. 如果当前链表为空 那么尾插 等于 头插
2. 如果当前链表不为空则需要找到最后一个结点让最后一个结点的指针指向新结点新结点再指向尾结点、
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;}
}4.链表的头删
函数接口
void SListPopFront(SLTNode** pphead)
动画演示 代码实现
1.如果当前链表是空的不用删
2. 如果当前链表还有结点则继续删。
void SListPopFront(SLTNode** pphead)
{assert(*pphead ! NULL);//if (*pphead NULL)// return;SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}
5.链表的尾删 函数接口
void SListPopBack(SLTNode** pphead)
动画演示 代码实现
1. 链表内只有一个结点的情况将当前结点的指针置为NULL再释放当前结点。最后置空
2.如果链表内有多个结点存在则需要遍历链表找到尾结点然后释放尾结点最后将指针置为NULL防止空指针异常。
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;}
}6.链表从中间插入结点
在第 i 个结点后面插入一个数据数据值为 v 规则说明
Head 为链表头并且头结点内有数据 i 0
动画演示 代码实现
先分析情况
1.如果当前链表为空则链表不需要删除。
2.如果链表不为空则需要让新结点指向要插入的结点再让前一个结点指向新结点。
ListNode *ListInsertNode(ListNode *head, int i, DataType v) {ListNode *pre, *aft, *vtx; // (1) 插入完毕后 pre - vtx - aft int j 0; // (2) 定义一个计数器当 j i 时表明找到要插入的位置 pre head; // (3) 从链表头开始while(pre j i) { // (4) 如果还没有到链表尾或者没有找到插入位置则继续循环 pre pre-next; // (5) 游标指针指向它的后继结点 j; // (6) 计数器加 1 }if(!pre) { return NULL; // (7) 元素个数不足无法找到给定位置返回 NULL }vtx ListCreateNode(v); // (8) 创建一个值为 v 的鼓孤立结点 aft pre-next; // (9) - (11) 为了串成 pre - vtx - aft vtx-next aft; // (10)pre-next vtx; // (11)return vtx; // (12) 返回插入的那个结点
} 7.从单链表中删除任意结点
删除任意结点跟任意位置插入结点的思路是一致的只是反着来。
动画演示 代码实现
分情况讨论
1.如果当前链表为空不需要删除
2.不为空先找到要删除结点的前一个结点让前一个结点指向要删除的结点的后一个结点然后释放要删除结点的内存再让后一个结点的指针指向前一个结点.
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos){SListPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
8.销毁链表
函数接口
void ListDestroyList(ListNode **pHead)
动画演示 代码实现
1.链表为空不删除。
2.链表不为空遍历链表释放结点最后指针置空。
void ListDestroyList(ListNode **pHead) { // (1) 这里必须用二级指针因为删除后需要将链表头置空普通传参无法影响外部变量 ListNode *head *pHead; // (2) 给链表头解引用 while(head) { // (3) 如果链表非空则继续循环 head ListDeleteNode(head, 0); // (4) 产出链表头部并且返回 后继结点 ListPrint(head);}*pHead NULL; // (5) 将链表头置空
}
完整代码
#include SList.hvoid SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode-data x;newnode-next NULL;return newnode;
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);if (*pphead NULL){*pphead newnode;}else{// 找尾节点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}void SListPopBack(SLTNode** pphead)
{assert(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;}
}void SListPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead ! NULL);//if (*pphead NULL)// return;SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x)return cur;cur cur-next;}return NULL;
}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);// 头插if (pos *pphead){SListPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos){SListPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}// 单链表在pos位置之后插入x
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;
}// 分析思考为什么不删除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;
}
