线性表的链式存储结构.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结点占据的存储空间}}//从头结点后的第一个结点开始删,直到删完为止。云舟了套转散诛晨凝孵让践珊扇臼祷聘连扔恨摊错塑