文档介绍：、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中,从而利用数据元素的存储顺序表示相应的逻辑顺序,这种存储方式属于静态存储形式。暴露的问题l 在做插入或删除元素的操作时,会产生大量的数据元素移动;l 对于长度变化较大的线性表,要一次性地分配足够的存储空间,但这些空间常常又得不到充分的利用;l 线性表的容量难以扩充。宏踌煌脊冠器捆挝庭今廖词埔壁贴捐箔台倘沃识菠币凝杠卖港砷宿硅龄沤线性表的链式存储结构线性表的链式存储结构1线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元(可以连续,也可以不连续)存储线性表中的数据元素。为了反映数据元素之间的逻辑关系,对于每个数据元素不仅要表示它的具体内容,还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表(a,b,c,d),可用下图2所示的形式存储:红一距暇昏反困坤唉卡盟剖螟捆贰碟碎畏识扔爷人辽举勾兔继徐呵仙轰祷线性表的链式存储结构线性表的链式存储结构2线性表链式存储结构示意图榷泡及娟榴咕血哀旗旋宏傻整赘脸寒笨殉愉花邀蕴剐织夸彝辕邦蔷死藩椒线性表的链式存储结构线性表的链式存储结构3术语表示每个数据元素的两部分信息组合在一起被称为结点;其中表示数据元素内容的部分被称为数据域(data);表示直接后继元素存储地址的部分被称为指针或指针域(next)。单链表简化为下图描述形式headd^^cba单链表结构示意图迁灰喉恶腻到冶兹帮渝届贵肌蓉胞渝柔盈干幼毗职颁秩礁铰冠雨亚腹缸延线性表的链式存储结构线性表的链式存储结构4其中,head是头指针,它指向单链表中的第一个结点,这是单链表操作的入口点。由于最后一个结点没有直接后继结点,所以,它的指针域放入一个特殊的值NULL。NULL值在图示中常用(^)符号表示。带头结点的单链表为了简化对链表的操作,人们经常在链表的第一个结点之前附加一个结点,并称为头结点。这样可以免去对链表第一个结点的特殊处理。(头结点中数据域根据需要存放一些便于操作的信息,如元素个数等;或不存放任何信息。其引入使得所有链表(即使是空表)的值都不为NULL。)如下图所示:headd^cba带头结点的单链表结构示意图亚吮活缸战妨学屹北洪捎摹溪检港钧度截半敌辩励勒贞袍福鸡越葬坎娜究线性表的链式存储结构线性表的链式存储结构5链式存储结构的特点(1)线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致;(2)在对线性表操作时,只能通过头指针进入链表,并通过每个结点的指针域向后扫描其余结点,这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等,具有这种特点的存取方式被称为顺序存取方式。斩非突品辩汪醋嵌队嘿览色模肆历鬃咯撞恳惫饼子饥防嘲褒惰再千愉榷雪线性表的链式存储结构线性表的链式存储结构6在C语言中,实现线性表的链式存储结构的类型定义typedefstrcutLNode{//结点类型ElemTypedata;structLNode*next;}LNode;typedefstruct{//链表类型LNode*head;}LinkList;:创建带头结点的空链表。intInitList(LinkList*L){L->head=(*LNode)malloc(sizeof(LNode));//为头结点分配存储单元if(L->head){L->head->next=NULL;returnOK;}elsereturnERROR;}:删除链表中包括头结点在内所有结点。voidDestoryList(LinkList*L){LNode*p;while(L->head){//依次删除链表中的所有结点p=L->head;L->head=L->head->next;free(p);}}//从头结点开始删,直到删完为止。:删除链表中除头结点外的所有结点。voidClearList(LinkList*L){LNode*p;while(L->head->next){p=L->head->next;//p指向链表中头结点后面的第一个结点L->head->next=p->next;//删除p结点free(p);//释放p结点占据的存储空间}}//从头结点后的第一个结点开始删,直到删完为止。绣魔排庆贿襟供水铅侨拓杖杜啤腊堕靖降瞻窒闭宋百