线性表的链式存储结构.ppt

、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中,从而利用数据元素的存储顺序表示相应的逻辑顺序,这种存储方式属于静态存储形式。暴露的问题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结点占据的存储空间}}//从头结点后的第一个结点开始删,直到删完为止。勒辽主穿触檀捂化组钢势厅锭念抉泞啄赴娄烤腹姆拈