设计优秀的企业网站,做行测的网站,英文seo优化包年费用,济南城市建设集团 网站单项链表的操作及其实现
很好我们已经明白了顺序表的实现了
如果不明白请看我的数据结构专栏中顺序表的文章
我们来简单的复习一下顺序表
顺序表#xff1a;
1.物理上连续的空间#xff0c;下标作为索引号#xff0c;按位置访问效率高。
2.逻辑上连续的#xff0c;查…单项链表的操作及其实现
很好我们已经明白了顺序表的实现了
如果不明白请看我的数据结构专栏中顺序表的文章
我们来简单的复习一下顺序表
顺序表
1.物理上连续的空间下标作为索引号按位置访问效率高。
2.逻辑上连续的查找某个值从头到尾依次查找。
3.尾插入/删除效率高任意位置的插入/删除后续数据的向后/向前搬移效率低。
4.物理上连续空间条件苛刻 会有内存碎片 申请连续空间可能失败
为啥连续的空间条件苛刻我简单的来个比喻你就明白了如果你想要再一条步行街上买上十间商铺那如果这个步行街已经有一段时间了你买十间连续的商铺肯定比你买十间不连续的商铺要难的多为什么这还用说肯定是其他的商铺主了你无法将十间商铺连这买但是你要是将十间商铺分开买就简单的多了。
依次类推我们的内存也是这样一个道理而在数据结构中我们将这种方法称之为链表。
那么我们正式来开始我们的链表学习
单项链表的结构说明
链式存储
1.利用物理上不连续的空间表示逻辑上的连续
上面商铺的比喻很是形象的说明了这个特性
2.节点结构 也就是数据指针域
也就是我们经常看见的图 3.按位置查找值查找效率低只能按顺序逐一查找
为啥因为你没法一下子定位位置只能一步步的向前走
走到一你才知道二走到二你才知道三这叫真正的走一步看一步
4.插入删除效率高
一般我们的书上都会写效率高但是效率高是有条件的因为我们今天讲的链表叫做单向链表何为单向一句话开弓没有回头箭一旦向前走了就没有办法退回来所以我们在向前移动的时候一定要先考虑清楚。
好的现在我们如果在x位置插入元素必须在x的前一个位置上守着所以如果是寻找值插入删除效率其实也不见得高多少但是如果是头插那效率肯定很高。
如何插入/删除
根据刚才讲的你要思考清楚然后再去插入/删除那么如何思考呢
先说插入
其实插入和做菜一样首先我们要找到插入的位置的前一个你直接指向插入位置没法删其次我们要先准备一个新节点新节点需要数据指针域数据好处理那指针域是哪里的呢
很显然我相信聪明的你一定可以想到用前一个节点的指针域这样我们就制作完成了一个全新的节点而后插入的操作很简单直接将前一个节点的指针域指向新的节点就完成了一个插入操作了。
很好我相信你一定已经被绕晕了
来个图搭配食用 总结一下
插入新节点
1.引入辅助指针pp找到待插入位置的前一个位置。
2.创建新节点。
3.更新新节点。
4.最后更新老节点。
再说删除
还是熟悉的套路先找到删除的前一个位置然后从新定义一个指针将要删除的节点地址先复制一份到新节点上将所选位置的前一个指向它删除位置的下一个节点最后释放掉你需要删除的位置的空间。
很好其实这个过程有点像倒垃圾你先找到垃圾然后找个垃圾桶将你不需要的垃圾放入垃圾桶然后收拾好自己的东西最后再将垃圾倒掉。
转化为代码就是
tmpp-next;
p-nexttemp-next;
free(tmp);总结一下
删除某个节点
1.引入辅助指针pp找到待删除的前一个节点
2.引入辅助指针备份待删除位置tmp。
3.更新前一个节点然后释放位置。
我们思想方面也可以总结一下
1.核心结构节点
2.开弓没有回头箭不要轻易的pp-next
3.备份思想
带头节点vs带头指针
带头节点
何为带头节点其实所谓带带头结点其实就是在头上多加一个没有值的节点用这个节点来作为链表的开始虽然可能会浪费一点空间但是使用起来很方便。
如图 那么其实我们会发现一个问题当一个节点的使用的空间很大的时候我们用带头结点的方式会有一点浪费空间但是比较好的一点就是它其实比较好操作。
为了解决浪费空间的问题
人们就想出了一个办法用一个指针来表示头节点。
带头指针
其实就是用一个指针来表示头节点虽然方便但是需要时刻的变换
如图 你需要时刻的判断好你的头节点是否指向正确的地方对于初学者来说有些难度。
所以我们还是建议使用带头节点的链表。
单项链表的实现代码
很顺序表的实现一样先写结构定义然后写结构操作的接口而后一一实现这些接口最后对这些接口进行测试。
这样的一套丝滑小连招是我们必不可少的
好的我们来一一的实现吧
结构定义结构操作的接口 #ifndef LINKLIST_H
#define LINKLIST_H
typedef int Element_t;//实现节点
typedef struct _node {Element_t data;struct _node*next;
}node_t;//实现头节点
typedef struct {node_t head;int cout;
}Linklist_t;
//初始化
Linklist_t* createlinklist();
//释放空间
void releaselinklist(Linklist_t* list);//插入
int insertLinklistHeader(Linklist_t* table, Element_t data);//头插法
int insertLinklistpos(Linklist_t* table,int number, Element_t data);//按位置插入//删除
int deleteLinklistHeader(Linklist_t* table, Element_t data);//打印
void printLinklist(const Linklist_t* table);#endif //LINKLIST_H
对结构定义的实现 #include stdio.h
#includelinkList.h#include stdlib.hLinklist_t * createlinklist() {Linklist_t*takeNULL;take(Linklist_t*)malloc(sizeof(Linklist_t));if (takeNULL) {return NULL;}take-cout0;take-head.data0;take-head.nextNULL;return take;
}int insertLinklistHeader(Linklist_t *table, Element_t data) {node_t *ptable-head;node_t* newnode(node_t*)malloc(sizeof(node_t));if (newnodeNULL) {return -1;}newnode-datadata;newnode-nextp-next;p-nextnewnode;;table-cout;return 0;
}int insertLinklistpos(Linklist_t *table, int number, Element_t data) {//判断边界条件if (number0||numbertable-cout) {return -1;}//寻找到插入位置node_t *ptable-head;int node-1;while (nodenumber-1) {pp-next;node;}//插入node_t *newnode(node_t*)malloc(sizeof(node_t));newnode-datadata;newnode-nextp-next;p-nextnewnode;table-cout;return 0;
}int deleteLinklistHeader(Linklist_t *table, Element_t data) {node_t *ptable-head;//找while (p-next) {if (p-next-datadata) {break;}pp-next;}//判断是否为空if (p-nextNULL) {printf(No find);return-1;}//删除node_t*nodep-next;p-nextnode-next;free(node);table-cout--;return 0;}void releaselinklist(Linklist_t *list) {if (list) {node_t* plist-head;node_t* node;while (p-next) {nodep-next;p-nextnode-next;free(node);list-cout--;}printf(link list number %d,list-cout);free(list);}}void printLinklist(const Linklist_t *table) {node_t* ptable-head.next;printf(link list number %d\n:,table-cout);while (p) {printf( %d ,p-data);pp-next;}printf(\n);
}
测试
#include stdio.h#include linkList.hint main() {printf(Hello linkList\n);Linklist_t*tablecreatelinklist();if (tableNULL)return -1;for (int i0;i10;i) {insertLinklistHeader(table,i100);}insertLinklistpos(table,3,300);deleteLinklistHeader(table,109);printLinklist(table);releaselinklist(table);return 0;
}
e);return 0;
}
测试结果 好得这篇博客到这里就结束了喜欢记得点一个小小的赞哦(๑′ᴗ‵๑) Lᵒᵛᵉᵧₒᵤ❤
