线性表的链式存储结构

《线性表的链式存储结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3线性表的链式存储结构线性表顺序存储结构的特点它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。暴露的问题l在做插入或删除元素的操作时，会产生大量的数据元素移动；l对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；l线性表的容量难以扩充。1线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一

2、个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2所示的形式存储：2线性表链式存储结构示意图3术语表示每个数据元素的两部分信息组合在一起被称为结点；其中表示数据元素内容的部分被称为数据域（data）；表示直接后继元素存储地址的部分被称为指针或指针域（next）。单链表简化为下图描述形式headd^^cba单链表结构示意图4其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（^）符号表示。带头结点的单链表为了简化对链表的操作，

3、人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。（头结点中数据域根据需要存放一些便于操作的信息，如元素个数等；或不存放任何信息。其引入使得所有链表（即使是空表）的值都不为NULL。）如下图所示：headd^cba带头结点的单链表结构示意图5链式存储结构的特点（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。6在C语言中，实现

4、线性表的链式存储结构的类型定义typedefstrcutLNode{//结点类型ElemTypedata;structLNode*next;}LNode;typedefstruct{//链表类型LNode*head;}LinkList;72.3.2典型操作的算法实现1.初始化链表L：创建带头结点的空链表。intInitList(LinkList*L){L->head=(*LNode)malloc(sizeof(LNode));//为头结点分配存储单元if(L->head){L->head->next=NULL;returnOK;}elsereturnERROR;}82.销毁链表L

5、：删除链表中包括头结点在内所有结点。voidDestoryList(LinkList*L){LNode*p;while(L->head){//依次删除链表中的所有结点p=L->head;L->head=L->head->next;free(p);}}//从头结点开始删，直到删完为止。93.清空链表L：删除链表中除头结点外的所有结点。voidClearList(LinkList*L){LNode*p;while(L->head->next){p=L->head->next;//p指向链表中头结点后面的第一个结点L->head->next=p->next;//删除p结点free(p)

6、;//释放p结点占据的存储空间}}//从头结点后的第一个结点开始删，直到删完为止。104.求链表L的长度intListLength(LinkListL){LNode*p;intlen;for(p=L.head,len=0;p->next==NULL;p=p->next,len++);return(len);循环条件表达式重复执行的语句}115.判断链表L是否为空。intListEmpty(LinkListL){if(L.head->next==NULL)returnTRUE;elsereturnFALSE;}126.通过e返回链表L中第i个数据元素的内容voidGetElem(L

7、inkListL,inti,EntryType*e){LNode*p;intj;//j为计数器，记载所经过的结点数目if(i<1

8、

9、i>ListLength(L))exitERROR;//检测i值的合理性for(p=L.head,j=0;j!=i;p=p->next,j++);//找到第i个结点*e=p->data;//将第i个结点的内容赋给e指针所指向的存储单元中}137.在链表L中检索值为e的数据元素LNode*LocateELem(LinkListL,EntryTypee)