您所在的位置:希力药业 > 企业实力 > 企业规模 >

发布日期:2021-04-01 09:35:18       作者:希力药业       浏览:167

逻辑结构上一个挨一个数据,在实际存储时,并没有像顺序那样也相互紧挨着。恰恰相反,数据随机分布在内存中各个位置,这种存储结构称为线性的链式存储

由于分散存储,为了能够体现出数据元素之间的逻辑关系,每个数据元素在存储的同时,要配备一个指针,用于指向它的直接后继元素,即每一个数据元素都指向下一个数据元素(最后一个指向NULL(空))。


图1 链式存储存放数据


如图1所示,当每一个数据元素都和它下一个数据元素用指针链接在一起时,就形成了一个链,这个链子的头就位于第一个数据元素,这样的存储方式就是链式存储。

线性表的链式存储结构生成的表,称作“链表”

链表中数据元素的构成 每个元素本身由两部分组成:

本身的信息,称为“数据域”

指向直接后继的指针,称为“指针域”

 


图2 结点的构成

这两部分信息组成数据元素的存储结构,称之为“结点”。n个结点通过指针域相互链接,组成一个链表。


图3 含有n个结点的链表
 

图 3 中,由于每个结点中只包含一个指针域,生成的链表又被称为 线性链表 或 单链表

链表中存放的不是基本数据类型,需要用结构体实现自定义: typedef struct Link{ char elem;//代表数据域 struct Link * next;//代表指针域,指向直接后继元素 }link; 头结点、头指针和首元结点 头结点:有时,在链表的第一个结点之前会额外增设一个结点,结点的数据域一般不存放数据(有些情况下也可以存放链表的长度等信息),此结点被称为头结点。

若头结点的指针域为空(NULL),表明链表是空表。头结点对于链表来说,不是必须的,在处理某些问题时,给链表添加头结点会使问题变得简单。

首元结点:链表中第一个元素所在的结点,它是头结点后边的第一个结点。

头指针:永远指向链表中第一个结点的位置(如果链表有头结点,头指针指向头结点;否则,头指针指向首元结点)。

头结点和头指针的区别:头指针是一个指针,头指针指向链表的头结点或者首元结点;头结点是一个实际存在的结点,它包含有数据域和指针域。两者在程序中的直接体现就是:头指针只声明而没有分配存储空间,头结点进行了声明并分配了一个结点的实际物理内存。


图 4 头结点、头指针和首元结点

单链表中可以没有头结点,但是不能没有头指针!

链表的创建和遍历 万事开头难,初始化链表首先要做的就是创建链表的头结点或者首元结点。创建的同时,要保证有一个指针永远指向的是链表的表头,这样做不至于丢失链表。

例如创建一个链表(1,2,3,4): link * initLink(){ link * p=(link*)malloc(sizeof(link));//创建一个头结点 link * temp=p;//声明一个指针指向头结点,用于遍历链表 //生成链表 for (int i=1; i<5; i++) { link *a=(link*)malloc(sizeof(link)); a->elem=i; a->next=NULL; temp->next=a; temp=temp->next; } return p; } 链表中查找某结点 一般情况下,链表只能通过头结点或者头指针进行访问,所以实现查找某结点最常用的方法就是对链表中的结点进行逐个遍历。

实现代码: int selectElem(link * p,int elem){ link * t=p; int i=1; while (t->next) { t=t->next; if (t->elem==elem) { return i; } i++; } return -1; } 链表中更改某结点的数据域 链表中修改结点的数据域,通过遍历的方法找到该结点,然后直接更改数据域的值。

实现代码: //更新函数,其中,add 表示更改结点在链表中的位置,newElem 为新的数据域的值 link *amendElem(link * p,int add,int newElem){ link * temp=p; temp=temp->next;//在遍历之前,temp指向首元结点 //遍历到被删除结点 for (int i=1; i<add; i++) { temp=temp->next; } temp->elem=newElem; return p; } 向链表中插入结点

链表中插入头结点,根据插入位置的不同,分为3种:

插入到链表的首部,也就是头结点和首元结点中间;

插入到链表中间的某个位置;

插入到链表最末端;