怎么对一个网站做优化,wordpress+子主题+教程,网络推广公司徽宿,做商城网站外包单链表专题 1.链表的概念及结构2. 实现单链表3. 链表的分类 1.链表的概念及结构 概念#xff1a;链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟火车车厢相似#xff0c;淡季时⻋次的⻋厢… 单链表专题 1.链表的概念及结构2. 实现单链表3. 链表的分类 1.链表的概念及结构 概念链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 链表的结构跟火车车厢相似淡季时⻋次的⻋厢会相应减少旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上不会影响其他⻋厢每节⻋厢都是独⽴存在的。
⻋厢是独⽴存在的且每节⻋厢都有⻋⻔。想象⼀下这样的场景假设每节⻋厢的⻋⻔都是锁上的状态需要不同的钥匙才能解锁每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾 最简单的做法每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 在链表⾥每节“⻋厢”是什么样的呢 与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点/节点”
节点的组成主要有两个部分当前节点要保存的数据和保存下⼀个节点的地址指针变量。
图中指针变量 plist保存的是第⼀个节点的地址我们称plist此时“指向”第⼀个节点如果我们希望plist“指向”第⼆个节点时只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下⼀个节点的位置 链表中每个节点都是独⽴申请的即需要插⼊数据时才去申请⼀块节点的空间我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
结合前⾯学到的结构体知识我们可以给出每个节点对应的结构体代码 假设当前保存的节点为整型
struct SListNode
{
int data; //节点数据
struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};当我们想要保存⼀个整型数据时实际是向操作系统申请了⼀块内存这个内存不仅要保存整型数据也需要保存下⼀个节点的地址当下⼀个节点为空时保存的地址为空。 当我们想要从第⼀个节点⾛到最后⼀个节点时只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙就可以了。
给定的链表结构中如何实现节点从头到尾的打印 补充说明 1、链式机构在逻辑上是连续的在物理结构上不⼀定连续 2、节点⼀般是从堆上申请的 3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续
2. 实现单链表
Slist.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//定义节点的结构
//数据 指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);Sllist.c
#includeSList.h
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur)//pcur ! NULL{printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}SLTNode* SLTBuyNode(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 SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead 就是指向第一个节点的指针//空链表和非空链表SLTNode* newnode SLTBuyNode(x);if (*pphead NULL){*pphead newnode;}else {//找尾SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail指向的就是尾结点ptail-next newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//newnode *ppheadnewnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead *pphead);//链表只有一个节点if ((*pphead)-next NULL) //- 优先级高于*{free(*pphead);*pphead NULL;}else {//链表有多个节点SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}//prev ptailfree(ptail);ptail NULL;prev-next NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{//链表不能为空assert(pphead *pphead);SLTNode* next (*pphead)-next; //- 优先级高于*free(*pphead);*pphead next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;while (pcur)//等价于pcur ! NULL{if (pcur-data x){return pcur;}pcur pcur-next;}//pcur NULLreturn NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead *pphead);assert(pos);SLTNode* newnode SLTBuyNode(x);//若pos *pphead;说明是头插if (pos *pphead){SLTPushFront(pphead, x);}else {SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev - newnode - posnewnode-next pos;prev-next newnode;}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//pos - newnode - pos-nextnewnode-next pos-next;pos-next newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *pphead);assert(pos);//pos是头结点/pos不是头结点if (pos *pphead){//头删SLTPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;//pos del del-nextpos-next del-next;free(del);del NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}//pcur*pphead NULL;
}test.c
#includeSList.hvoid SListTest01()
{//链表是由一个一个的节点组成//创建几个节点SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;//将四个节点连接起来node1-next node2;node2-next node3;node3-next node4;node4-next NULL;//调用链表的打印SLTNode* plist node1;SLTPrint(plist);
}void SListTest02()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist); // 1-2-3-4-NULLSListDesTroy(plist);SLTPrint(plist);//测试查找//SLTNode* find SLTFind(plist, 1);//SLTInsert(plist, find, 11);//SLTInsertAfter(find, 11);//删除pos节点//SLTErase(plist, find);//SLTEraseAfter(find);//SLTPrint(plist);//if (find NULL)//{// printf(没有找到\n);//}//else {// printf(找到了\n);//}//SLTPushBack(NULL, 5);////测试头插//SLTPushFront(plist, 6);//SLTPrint(plist);//SLTPushFront(plist, 7);//SLTPrint(plist);//SLTPushFront(plist, 8);//SLTPrint(plist);//测试头删//SLTPopFront(plist);//SLTPrint(plist);// 2-3-4-NULL//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);}int main()
{//SListTest01();SListTest02();return 0;
}3. 链表的分类
链表的结构⾮常多样以下情况组合起来就有8种2 x 2 x 2链表结构 链表说明 虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构单链表和双向带头循环链表
⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带 来很多优势实现反⽽简单了后⾯我们代码实现了就知道了。
完。。。
