企业网站建设与网络营销的关系,福田欧辉广东工厂,网商之窗官网,网站建设公司有哪目录
数据结构之链表#xff1a;#xff1a; SList.h 1.链表的概念及结构 2.链表的分类 SList.c 3.动态申请一个结点 4.单链表打印 5.单链表销毁 6.单链表头插 7.单链表头删 8.单链表尾插 9.单链表尾删 10.单链表查找 11.单链表在pos之前插入…目录
数据结构之链表 SList.h 1.链表的概念及结构 2.链表的分类 SList.c 3.动态申请一个结点 4.单链表打印 5.单链表销毁 6.单链表头插 7.单链表头删 8.单链表尾插 9.单链表尾删 10.单链表查找 11.单链表在pos之前插入 12.单链表在pos之后插入 13.删除pos位置 14.删除pos后面位置 数据结构之链表
SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
SListNode* next为C中的语法 将其封装成了类
void SListPrint(SLTNode* phead);
void Destory(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
删除pos后面位置
void SListEraseAfter(SLTNode* pos);1.链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 注意
1.从上图可以看出链式结构在逻辑上是连续的但是在物理上不一定连续.
2.现实中的结点一般都是从堆上申请出来的.
3.从堆上申请的空间,是按照一定的策略来分配的两次申请的空间可能连续也可能不连续.
2.链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构.
1.单向或者双向 2.带头或者不带头 3.循环或者非循环 虽然有这么多的链表结构但是我们实际中最常用还是两种结构. 无头单向非循环链表 结构简单一般不会用来单独存数据实际上更多是作为其他数据结构的子结构如哈希桶,图的邻接表等.带头双向循环链表 结构最复杂一般用来单独存储数据,实际中使用到的链表数据结构都是带头双向循环链表这个结构虽然复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了.
SList.c
3.动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
4.单链表打印
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
5.单链表销毁
void Destory(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur ! NULL){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
6.单链表头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}
7.单链表头删
void SListPopFront(SLTNode** pphead)
{assert(pphead);温柔的检查if (*pphead NULL){return;}暴力的检查//assert(*pphead ! NULL);SLTNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;
}
8.单链表尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{1.链表是空2.链表非空链表为空 插入第一个结点 要改变的是SListNode* 用的是结构体指针的指针链表不为空 尾插要改变的是结构体SListNode的成员 用的是结构体指针assert(pphead);SLTNode* newnode BuySLTNode(x);if (*pphead NULL){*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
9.单链表尾删
void SListPopBack(SLTNode** pphead)
{assert(pphead);温柔的检查——为空不删if (*pphead NULL){return;}暴力的检查//assert(*pphead ! NULL);1.一个结点 2.多个结点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{找尾SLTNode* prev NULL;/*SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}prev-next NULL;free(tail);tail NULL;*/SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}prev-next NULL;free(tail-next);tail-next NULL;}
}
10.单链表查找
链表中的查找函数可以替代其修改函数
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
11.单链表在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SListPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;pos不在链表中 pos不在链表中 prev为空还没有找到pos 说明pos传错了assert(prev);}SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}
12.单链表在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);newnode-next pos-next;pos-next newnode;
}
13.删除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;检查pos不是链表中结点 参数传错的情况assert(prev);}prev-next pos-next;free(pos);//pos NULL;此代码并不会改变pos 使用人在main函数将其置空}
}
14.删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos-next NULL){return;}else{SLTNode* next pos-next;pos-next next-next;free(next);}
}
单链表:只适合头插头删——O(1)
任意位置高效插入删除——双向链表
进阶:删除pos位置 要求是O(1) 替换法删除
缺陷:pos不能是尾结点 解决方法:将链表改成循环链表
进阶:在pos位置之前插入 要求是O(1)
方法:在pos位置后创造结点替换法
newnode BuySListNode(pos-val);
pos-val x;
