文章目录
- 一、单向链表是什么?
- 二、功能代码实现
- 三、代码实现单向链表
- 四、总结
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;(下图来自百度)
二、功能代码实现 1.包含头文件
#include2.结构体(结点)#include #include #include
typedef int SLTDataType;//宏定义成员为整形 typedef struct SListNode { SLTDataType data;//资料 struct SListNode* next;//连接下一个节点的链子 }SLTNode;3.定义
SLTNode* BuyNewNode(SLTDataType X);//创建新节点 void SListPrint(SLTNode* phead);//打印 void SListDestory(SLTNode**phead);//销毁 void SListPushFront(SLTNode** pphead, SLTDataType X);//头插 void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插 void SListPopFront(SLTNode** pphead);//头删 void SListPopBack(SLTNode** pphead);//尾删 SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询 void SListInsert(SLTNode** pphead,SLTNode*pos, SLTDataType X);//插入-在pos之前插入 void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入4.各类功能实现
SLTNode* BuyNewNode(SLTDataType X);//创建新节点-结构体指针类型函数-传值
SLTNode* BuyNewNode(SLTDataType X) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先开辟一块空间给新节点 if (newnode == NULL)//如果新节点为空-即开辟失败则报错 { perror("malloc fail"); exit(-1); } newnode->data = X;//把X的值赋给新节点的data newnode->next = NULL;//把链子设为空指针 return newnode;//把节点传回去 }
void SListPrint(SLTNode* phead);//打印
void SListPrint(SLTNode* phead) { SListNode* cur = phead;//新建一个结构体指针为表头 while (cur != NULL)//如果指针指向的内容不为空则打印内容 { printf("%d->", cur->data); cur = cur->next; } printf("NULLn");//为空则打印空指针 }
void SListDestory(SLTNode**phead);//销毁
void SListDestory(SLTNode** pphead) { assert(pphead);//指向节点的指针不能为空 SLTNode* cur = *pphead;//新建一个临时节点为链表头 while (cur)//临时节点不为空时 { SLTNode* next = cur->next;//链表下一个节点为临时节点的的下一个节点 free(cur);//释放当前节点 cur = next;//当前节点为下一个节点 } *pphead = NULL;//最后释放完链表后置指针为空 }
void SListPushFront(SLTNode** pphead, SLTDataType X);//头插
void SListPushFront(SLTNode** pphead, SLTDataType X)//头插-链表吧不为空,要改变的是SList-用地址 { assert(pphead); SLTNode* newnode = BuyNewNode(X);//新建其含有对应内容的新节点 newnode->next = *pphead;//新节点的下一个节点为表头 *pphead = newnode;//新节点充当表头 }
void SListPopFront(SLTNode** pphead);//头删
void SListPopFront(SLTNode** pphead)//头删 { assert(pphead); // if (*pphead == NULL)//温柔检查 // { // return; // //} assert(*pphead != NULL);//暴力检查 SLTNode* del = *pphead;//建立新节点为表头 *pphead = (*pphead)->next;//表头的下一个节点为表头 free(del);//释放表头 del = NULL;//新节点指针置为空 }
void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插
void SListPushBack(SLTNode** pphead, SLTDataType X)//尾插-链表不为空,要改变的是SList 的成员-用结构体指针即可 { assert(pphead); SLTNode* newnode = BuyNewNode(X);//新建 if (*pphead == NULL)//一种情况为表头为空-即链表只有一个空节点 { *pphead = newnode; } else//另一种情况要找尾巴 { //找尾 SLTNode* tail = *pphead;//建立新节点为表头,依次找到表尾 while(tail->next != NULL) { tail = tail->next; } tail->next = newnode;//表尾替换为含有对应内容的新节点 } }
void SListPopBack(SLTNode** pphead);//尾删
A-单指针法
void SListPopBack(SLTNode** pphead)//尾删 { // if (*pphead == NULL)//温柔检查 // { // return; // //} assert(*pphead != NULL);//暴力检查 assert(pphead); //对应链表只有一个节点-直接释放 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//对应链表有多个节点 { //找尾 SLTNode* tail = *pphead;//新建节点为表头-开始找尾 if (tail->next->next != NULL)//表尾为空指针-即要删除表尾前一个节点 { tail = tail->next; } free(tail->next); tail->next = NULL; } }
B-双指针(快慢指针法)
void SListPopBack(SLTNode** pphead)//尾删 { assert(pphead); //找尾 SLTNode* tail = *pphead; SLTNode* open = NULL; while (tail->next != NULL) { open = tail; tail = tail->next; } open->next = NULL; free(tail->next); tail = NULL; }
SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询
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);//插入-在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之前插入 { assert(pphead); assert(pos); if (pos == *pphead)//pos为表头直接用头插 { SListPushFront(pphead,X); } else { SListNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; assert(pre);//找到NULL还没找到pos说明pos传错了 } SListNode* newnode = BuyNewNode(X);//串连起来 pre->next = newnode; newnode->next = pos; } }
void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之后插入 { assert(pos); SListNode* newnode = BuyNewNode(X); newnode->next = pos->next; pos->next = newnode; }三、代码实现单向链表
SList.h
#include#include #include #include typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; SLTNode* BuyNewNode(SLTDataType X);//创建新节点 void SListPrint(SLTNode* phead);//打印 void SListDestory(SLTNode**phead);//销毁 void SListPushFront(SLTNode** pphead, SLTDataType X);//头插 void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插 void SListPopFront(SLTNode** pphead);//头删 void SListPopBack(SLTNode** pphead);//尾删 SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询 void SListInsert(SLTNode** pphead,SLTNode*pos, SLTDataType X);//插入-在pos之前插入 void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入 void SListEarse(SLTNode** pphead,SLTNode*pos);//删除-删除pos
SList.cpp
//顺序表的缺点 //1.中间或中部的插入和删除,时间复杂度为o(n) //2.增容需要申请空间,拷贝数据,释放旧空间,会有消耗 //3.扩容一般以2倍的增长,易造成空间浪费 //链表 //无头单向非循环单链表:结构简单,一般不会单独用来存数据,实际上更多作为其他数据结构的子结构,如哈希表,图的邻接表 #include"SList.h" void SListPrint(SLTNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULLn"); } SLTNode* BuyNewNode(SLTDataType X) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = X; newnode->next = NULL; return newnode; } void SListPushFront(SLTNode** pphead, SLTDataType X)//头插-链表吧不为空,要改变的是SList-用地址 { assert(pphead); SLTNode* newnode = BuyNewNode(X); newnode->next = *pphead; *pphead = newnode; } void SListPushBack(SLTNode** pphead, SLTDataType X)//尾插-链表不为空,要改变的是SList 的成员-用结构体指针即可 { assert(pphead); SLTNode* newnode = BuyNewNode(X); if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SLTNode* tail = *pphead; while(tail->next != NULL) { tail = tail->next; } tail->next = newnode; } } void SListPopFront(SLTNode** pphead)//头删 { assert(pphead); // if (*pphead == NULL)//温柔检查 // { // return; // //} assert(*pphead != NULL);//暴力检查 SLTNode* del = *pphead; *pphead = (*pphead)->next; free(del); del = NULL; } //void SListPopBack(SLTNode** pphead)//尾删 //{ // assert(pphead); // //找尾 // SLTNode* tail = *pphead; // SLTNode* open = NULL; // while (tail->next != NULL) // { // open = tail; // tail = tail->next; // } // open->next = NULL; // free(tail->next); // tail = NULL; // //} void SListPopBack(SLTNode** pphead)//尾删 { // if (*pphead == NULL)//温柔检查 // { // return; // //} assert(*pphead != NULL);//暴力检查 assert(pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else//多个节点 { //找尾 SLTNode* tail = *pphead; if (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } } void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; } 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)//插入-在pos之前插入 { assert(pphead); assert(pos);//在pos之前插入 if (pos == *pphead) { SListPushFront(pphead,X); } else { SListNode* pre = *pphead; while (pre->next != pos) { pre = pre->next; assert(pre);//找到NULL还没找到pos说明pos传错了 } SListNode* newnode = BuyNewNode(X); pre->next = newnode; newnode->next = pos; } } void SListEarse(SLTNode** pphead, SLTNode* pos)//删除-删除pos { } void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之后插入 { assert(pos); SListNode* newnode = BuyNewNode(X); newnode->next = pos->next; pos->next = newnode; }
test.cpp
#include"SList.h" void TestSList1() { SLTNode* plist = NULL; SListPushFront(&plist, 1); SListPushFront(&plist, 2); SListPushFront(&plist, 3); SListPushFront(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 4); if (pos) { pos->data *= 2; printf("找到了n"); } else { printf("没找到n"); } SListPrint(plist); SListInsert(&plist,pos, 20); SListPrint(plist); SListDestory(&plist); SListPrint(plist); } int main() { TestSList1(); return 0; }
以上只实现了部分功能,具体可以参考上功能代码实现,或者进到我的链接看噢
https://github.com/divertlee/opening.git
四、总结
本人纯新手昂,有啥问题评论区cue我噢,谢谢观看!!!