1.首先认识什么是单链表,知道其基本的定义:
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
结构图如下:
2.了解其来源(背景)
1.在顺序表中,对于整体空间的大小,在一定条件下会出现需要扩容的情况,而之前的顺序表在进行次操作时会出现一定的代价;
2.在对表中的元素进行相应的插入和删除操作时,顺序表往往存在一定的效率缺陷。
3.单链表的实现及其相应的操作,主要包括以下的函数,
// 动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x);
//插入多个同时
SLTNode* CreateSList(int n);
// 单链表打印
void SLTPrint(SLTNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入?
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置?
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SList* plist);
//在pos之前插入
void SListInsert(SListNode* pphead, SListNode* pos, SLTDateType x);
//删除pos位置
void SListEraseAfter((SListNode** pphead ,SListNode* pos);
4.具体操作如下:
(1) 动态申请一个节点,次操作相当于对其初始化的操作,我们可以动态对其进行初始化,这样的好处相比静态初始化后期的操作可能会更方便
void SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newHead = (SLTNode*)malloc(sizeof(SLTNode)); if (newHead == NULL) { perror("malloc fail"); exit(-1); } newHead->data = x; newHead->next = NULL; return newHead; }
(2)插入多个同时
SLTNode* CreateSList(int n) { SLTNode* phead = NULL, *ptail = NULL; for (int i - 0; i < n; i++) { SLTNode* newnode = BuySLTNode(i); if (phead == NULL) { ptail = phead = newhead; } else { ptail->next = newnode; ptail = newnode; } } return phead; }
(3) 单链表打印
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
(4)单链表尾插,在对表链表进行尾删的操作时,只需要两个节点,这里最难的是找尾,我们定义tail->next为尾,同时还要注意链表为空和顺序表为空的区别,同时使用二级指针来进行传递形参指向的内容
// 单链表尾插 void SListPushBack(SListNode** pphead, SLTDateType x) { SLTNode* newnode = BuySLTNode(x); //判链表开始是否为空 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; // 找尾 while (tail->next) { tail = tail->next; } tail->next = newnode; } }
注意:
1.改变int,传递int*给形参,形参进行交换改变
2.改变int,传递int**给形参,*形参进行交换改变
(5)单链表的头插,创建新节点newnode 指向第一个,对于第一个元素,又可以用地址来找到,这里为空时不需要单独处理
void SListPushFront(SListNode** pphead, SLTDateType x) { SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
(6)
单链表的尾删,这里有两种写法:
1.第一种我们可以在tail在往下继续指向时定义一个prev,双指针,tail再走之前给到prev,在依次执行,最后在找到tail时,tail的前一个也可以找得到(这里不写出来,大家可以试试!)
2.可以直接通过tail->->next来判断,但需要考虑其中tail->为空的情况
void SListPopBack(SListNode** pphead) { // 暴力的检查 assert(*pphead); // 温柔的检查 //if (*pphead == NULL) // return; //判断开始时链表是否只有一个元素 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
(7)单链表头删,删除时需要断言一下,不能直接删,不然的话找不到下一个的地址,我们可以保存下一个,之后指向下一个就解决了,这就是单链表的优势所在
// 单链表头删 void SListPopFront(SListNode** pphead) { assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
(8)单链表查找
// 单链表查找 SListNode* SListFind(SListNode* pphead, SLTDateType x) { SListNode* cur = pphead; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; }
(9)单链表在pos位置之后插入x,给出的位置不再是下标,而是指针,注意地址的衔接情况,这里可以不用二级指针,这里改变的是结构体,只需要结构体指针就可以了
void SListInsertAfter(SListNode* pos, SLTDateType x) { assert(pos); SListNode* next = pos->next; // pos newnode next SListNode* newnode = BuySListNode(x); newnode->next = next; pos->next = newnode; }
(10)单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos) { assert(pos); //SListNode* next = pos->next; if (pos->next == NULL) { return; } else { SListNode* nextNode = pos->next; pos->next = nextNode ->next; free(nextNode ); } }
(11) 单链表的销毁
// 单链表的销毁 void SListDestroy(SList* pphead) { SListNode* cur = *pphead; while (cur) { SListNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
(12)在pos之前插入
(13)删除pos位置
//删除pos位置 void SListEraseAfter((SListNode** pphead ,SListNode* pos) { assert(pos); if (pos == *pphead) { SListPopFront(pphead); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
5.代码块如下:
test.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
6.总结
数据结构与算法比较复杂,需要多画图。链表题多判断边界,勤加练习。