营销型网站建设制作推广,好男人hd免费观看,响应式网站建设信息,重庆seo职位链表 1.链表1.1 链表概念及其结构1.2 链表的分类 2.单链表代码实现2.1 单链表的定义2.2 单链表的初始化2.3 单链表的新增结点2.4 单链表的打印2.4 单链表的插入2.4.1 头插2.4.2 尾插2.4.3 任意位置插入 2.5 单链表的删除2.5.1 头删2.5.2 尾删2.5.3 任意位置删除 2.6 单链表的查… 链表 1.链表1.1 链表概念及其结构1.2 链表的分类 2.单链表代码实现2.1 单链表的定义2.2 单链表的初始化2.3 单链表的新增结点2.4 单链表的打印2.4 单链表的插入2.4.1 头插2.4.2 尾插2.4.3 任意位置插入 2.5 单链表的删除2.5.1 头删2.5.2 尾删2.5.3 任意位置删除 2.6 单链表的查找及其修改 1.链表
1.1 链表概念及其结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表结构如图所示
1.2 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 单向或者双向 带头或者不带头 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 2.单链表代码实现
2.1 单链表的定义
我们在了解线性结构最重要的就是明白这个结构是如何定义的是怎样的一种结构。这里单链表的定义我们考虑的是我们需要这个结构中包含什么这里我们需要的是一个数据域和一个指针域数据域用于存储数据指针域用于链接每个单链表节点。行我们来rua一下
typedef int SLTDateType;//typedef 一下方便我们更改所需存储的类型
typedef struct SListNode
{SLTDateType data;//数据域用于存储数据struct SListNode* next;//指针域用于链接下一个结点
}SLTNode;2.2 单链表的初始化
单链表一般不直接提供初始化接口是因为单链表的初始化不需要额外的方法来完成可以通过其他操作来实现。
一般而言单链表的初始化可以分为两种方式
首先创建一个空链表然后逐个插入节点直到构建完整的链表。
SLTNode* plist NULL;//后续只需要不断插入新的结点就可以直接在创建链表的过程中完成节点的插入操作不需要单独的初始化方法。
因此为了简化接口设计和操作复杂度单链表通常不提供单独的初始化接口而是通过其他操作来实现链表的构建和初始化。
2.3 单链表的新增结点
这里就可以看到我们在为一个指针开辟空间后就立马初始化了和上述第二种初始化的方法相同。
SLTNode* SLTNewNode(SLTDateType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));//开辟一个链表结点大小的空间if (node NULL)//检测是否开辟成功{perror(malloc fail);return NULL;}node-data x;node-next NULL;return node;
}2.4 单链表的打印
为了方便测试一般我们会使用链表打印接口来查看检测。
void SLTPrint(SLTNode* pa)
{SLTNode* cur pa;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}2.4 单链表的插入
这里涉及到单链表的一个难点就是这里需要二级指针我们需要更改一级指针内的元素数据所以需要用二级指针来更改。就例如我们要改变一个数据类型的值需要一级指针一样。 2.4.1 头插
在链表第一个结点前插入。
void SLTPushFront(SLTNode** ppa, SLTDateType x)
{assert(ppa);//plist(ppa)不可能为空所以需要检测SLTNode* newnode SLTNewNode(x);newnode-next *ppa;//新节点的next指针指向链表开头*ppa*ppa newnode;//更新头指针
}2.4.2 尾插
在链表最后结点后插入
void SLTPushBack(SLTNode** ppa, SLTDateType x)
{assert(ppa); SLTNode* newnode SLTNewNode(x);if (*ppa NULL) //判断链表是否为空{*ppa newnode;}else{//找尾操作这里单链表我们只能使用遍历来实现当找到一个节点的next指针指向null时就代表找到尾了。SLTNode* tail *ppa;while (tail-next){tail tail-next;}tail-next newnode;}
}2.4.3 任意位置插入
pos前位置插入我们知道了尾插这里就相当于把pos位置当做尾去找pos位置然后再用头插的思路完成。
//任意位置插入(pos前插入)
void SLTInsertF(SLTNode** ppa, SLTNode* pos, SLTDateType x)
{assert(ppa);assert(pos);if (pos *ppa){SLTPushFront(ppa, x);}else {SLTNode* tmp SLTNewNode(x);SLTNode* prev *ppa;while (prev-next ! pos){prev prev-next;}prev-next tmp;tmp-next pos;}
}pos位置后插入学习了任意位置插入我们其实可以把头插和尾插的实现过程改成调用任意位置插入接口
void SLTInsertB(SLTNode** ppa, SLTNode* pos, SLTDateType x)
{assert(ppa);if (pos NULL){SLTPushBack(ppa, x);}else{SLTNode* newnode SLTNewNode(x);SLTNode* cur *ppa;while (cur ! pos-next){cur cur-next;}pos-next newnode;newnode-next cur;}
}
2.5 单链表的删除
2.5.1 头删
头删的思路就是把头指针指向下一个结点然后释放开始的结点。
void SLTPopFront(SLTNode** ppa)
{assert(ppa);assert(*ppa);SLTNode* tmp *ppa;*ppa tmp-next;free(tmp);tmp NULL;
}2.5.2 尾删
尾删道理是相通的找到尾指针但也要保留尾指针的前一个指针因为需要在删除尾指针后把前一个尾指针的next指向空。
void SLTPopBack(SLTNode** ppa)
{assert(ppa);assert(*ppa);if ((*ppa)-next NULL){free(*ppa);*ppa NULL;}else{SLTNode* prev *ppa;SLTNode* tail prev-next;while (tail-next){prev prev-next;tail tail-next;}prev-next tail-next;free(tail);tail NULL;}
}2.5.3 任意位置删除
意思相近与尾删。
void SLTEraser(SLTNode** ppa, SLTNode* pos)
{assert(ppa);assert(*ppa);if ((*ppa)-next NULL||pos*ppa) {SLTPopFront(ppa);}else{SLTNode* prev *ppa;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}2.6 单链表的查找及其修改
链表查找就是对应data然后遍历返回比较简单修改的话就是根据返回访问data进行赋值修改
SLTNode* SLTFind(SLTNode* pa, SLTDateType x)
{SLTNode* cur pa;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
