cms系统首页,优化seo是什么,网站设计开发方案,wordpress添加购买按钮C语言实现 -- 单链表 1.顺序表经典算法1.1 移除元素1.2 合并两个有序数组 2.顺序表的问题及思考3.链表3.1 链表的概念及结构3.2 单链表的实现 4.链表的分类 讲链表之前#xff0c;我们先看两个顺序表经典算法。 1.顺序表经典算法
1.1 移除元素
经典算法OJ题1#xff1a;移除… C语言实现 -- 单链表 1.顺序表经典算法1.1 移除元素1.2 合并两个有序数组 2.顺序表的问题及思考3.链表3.1 链表的概念及结构3.2 单链表的实现 4.链表的分类 讲链表之前我们先看两个顺序表经典算法。 1.顺序表经典算法
1.1 移除元素
经典算法OJ题1移除元素
思路双指针法 不是真的定义指针而是两个变量。 执行步骤 定义两个变量src 和 dst 如果src指向的值等于valsrc 如果src指向的值不等于valarr[dst] arr[src],src,dst 图示
代码实现
1.2 合并两个有序数组
经典算法OJ题2合并两个有序数组
思路 从两个数组的最后一个有效数据开始从后往前比较找大谁大就从num1数组的最后一个位置从后往前放。 代码如下
2.顺序表的问题及思考
问题 1.中间/头部的插入删除时间复杂度为O(N)
增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。
3.链表
3.1 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 逻辑结构是线性的物理结构不是线性的。
链表的结构跟火车车厢相似淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上不会影响其他车厢每节车厢都是独立存在的。车厢是独立存在的且每节车厢都有车门。想象一下这样的场景假设每节车厢的车门都是锁上的状态需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾
最简单的做法每节车厢里都放一把下一节车厢的钥匙。 在链表里每节“车厢”是什么样的呢 1.与顺序表不同的是链表里的每节车厢都是独立申请下来的空间我们称之为“结点/节点”链表是由一个一个的节点(结点)组成的。 2.节点的组成主要有两个部分data:当前节点要保存的数据和*next:保存下一个节点的地址指针变量它指向的是一个结构体所以是结构体指针那这个结构体就是我们链表中的结点。 3.图中指针变量plist保存的是第⼀个节点的地址我们称plist此时“指向”第一个节点如果我们希望plist“指向”第二个节点时只需要修改plist保存的内容0x0012FFA0。 4.为什么还需要指针变量来保存下一个节点的位置 链表中每个节点都是独立申请的即需要插入数据时才去申请⼀块节点的空间 我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。 结合前面学到的结构体知识我们可以给出每个节点对应的结构体代码 假设当前保存的节点为整型 当我们想要保存⼀个整型数据时实际是向操作系统申请了一块内存这个内存不仅要保存整型数据也需要保存下一个节点的地址当下一个节点为空时保存的地址为空。 当我们想要从第一个节点走到最后一个节点时只需要在前一个节点拿上下一个节点的地址下一个节点的钥匙就可以了。 给定的链表结构中如何实现节点从头到尾的打印 思考当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时该如何修改 typedef int SLTDataType; 直接把int 换成char ,float 等等 补充说明 1、链式机构在逻辑上是连续的在物理结构上不⼀定连续 2、节点⼀般是从堆上申请的 3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续。
3.2 单链表的实现
1.首先在头文件中定义一个结构体 其次要明白
2. 链表的打印 3.申请新节点
4. 尾插 首先我们要知道一级指针和二级指针的关系 指针变量plist 存放的是第一个结点node的地址所以plist指向第一个结点的指针。 二级指针变量pplist存放的是一级指针变量plist的地址,所以pplist 指向一级指针的变量。
代码 5.头插 代码 6.尾删 代码 7.头删 代码 8.查找 9.在指定位置之前插入数据 代码 10.在指定位置之后插入数据 代码 11.删除pos节点 代码 12.删除pos之后的节点 代码 13.销毁链表 代码
下面是完整代码 SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//typedef struct SListNode 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** pphead, 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);SList.c
#includeSList.h
void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur){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);SLTNode* newnode SLTBuyNode(x);//链表为空新节点作为pheadif (*pphead NULL) {*pphead newnode;return;}//链表不为空找尾节点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);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点有多个节点if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;return;}SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;//销毁尾结点free(ptail);ptail NULL;
}
void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-data x) {return pcur;}pcur pcur-next;}//没有找到return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode SLTBuyNode(x);//pos刚好是头结点if (pos *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev - newnode - posprev-next newnode;newnode-next pos;
}
//在指定位置之后插入数据
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);assert(*pphead);assert(pos);//pos刚好是头结点没有前驱节点执行头删if (*pphead pos) {//头删SLTPopFront(pphead);return;}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不能为空assert(pos-next);//pos pos-next pos-next-nextSLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}test.c
#includeSList.h//void 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-NULL//SLTPushFront(plist, 5);//SLTPrint(plist); //5-1-2-3-4-NULL//SLTPushFront(plist, 6);//SLTPrint(plist); //6-5-1-2-3-4-NULL//SLTPushFront(plist, 7);//SLTPrint(plist); //7-6-5-1-2-3-4-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULL
}void SlistTest03() {SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist); //1-2-3-4-NULLSListDesTroy(plist);头删//SLTPopFront(plist);//SLTPrint(plist); //2-3-4-NULL//SLTPopFront(plist);//SLTPrint(plist); //3-4-NULL//SLTPopFront(plist);//SLTPrint(plist); //4-NULL//SLTPopFront(plist);//SLTPrint(plist); //NULL//SLTPopFront(plist);//SLTPrint(plist); //assert////SLTNode* FindRet SLTFind(plist, 3);//if (FindRet) {// printf(找到了\n);//}//else {// printf(未找到\n);//}//SLTInsert(plist, FindRet, 100);//SLTInsertAfter(FindRet, 100);////删除指定位置的节点//SLTErase(plist, FindRet);//SLTPrint(plist); //1-2-3-NULL
}
int main() {//SlistTest01();//SlistTest02();SlistTest03();return 0;
}4.链表的分类
链表的结构非常多样以下情况组合起来就有8种2x2x2链表结构 链表说明 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构单链表和双向带头循环链表。 1.无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2.带头双向循环链表结构最复杂⼀般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 完
