《第二章第3节 线性表的链式表示和实现.ppt》由会员分享，可在线阅读，更多相关《第二章第3节 线性表的链式表示和实现.ppt（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、23线性表的链式表示和实现线性表的链式表示和实现链式分配链式分配线性表数据元素的存储单元可以不连续，存放数据元素的结点至少包括两个域（数据域、指针域），也可以包含若干个数据域、指针域。1.单链表：每个结点只有一个指针域a.链表链接的顺序和数据元素的逻辑顺序一致，结点的物理位置可任意安排b.头指针：存放第一个结点的存储地址c.（附加）头结点：在单链表第一个结点之前附设一个结点a1headheada2a6a57a41a26a13a32a6null1 12 23 34 45 56 67 78 85 5headheadheadheada1a6头结点头结点头指针头指针头指针空表headhead1存储表示
2、存储表示typedef struct Lnode elemtype data;/数据域数据域 struct Lnode *next;/指针域指针域Lnode,*linklist;其中其中linklist等价于等价于Lnode*若设若设 LNode*p,*q;LinkList H;则则p,q,H都是指针变量都是指针变量,p-data 表示数据域表示数据域p-next 表示指针域表示指针域2.3.1线性表的单链表线性表的单链表指针赋值的操作指针赋值的操作指针指向结点指针指向结点p=qq p指针指向后继指针指向后继p=q-next指针移动指针移动p=p-nextqppppq指针赋值的操作指针赋值的操
3、作p-next=qp-next=q-nextpqStatus listinsert_L(linklist L,int i,elemtype e)p=L;j=0;while(p&jnext;j+;if(!p|ji-1)return error;/!p/!p和和ji-1ji-1各代表什么？各代表什么？s=(linklist)malloc(sizeof(Lnode);/生成新结点生成新结点 s-data=e;s-next=p-next;p-next=s;/插入插入 return ok;1.在带头结点的单链表在带头结点的单链表L中第中第i元素之前插入元素元素之前插入元素e2 2单链表的基本运算单链表的
4、基本运算2.在带头结点的单链表在带头结点的单链表L中，查找值中，查找值x的元素，删除之。的元素，删除之。（假设（假设L中元素不重复）中元素不重复）Status listdelete_L(linklist L,elemtype x)p=L;while(p-next&p-next-data!=x)/找找x x的前驱的前驱p=p-next;if(!p-next)return error;q=p-next;p-next=q-next;free(q);/删除删除x x结点结点return ok;单链表的基本运算单链表的基本运算单链表的基本运算单链表的基本运算3.逆序建立带表头结点的单链表逆序建立带表头结
5、点的单链表LLinklist createlist_L()L=(linklist)malloc(sizeof(Lnode);/L/L指头结点指头结点 L-next=null;printf(“input length=?”);scanf(“%d”,&n);for(i=n;i0;i-)p=(linklist)malloc(sizeof(Lnode);/生成新结点生成新结点 printf(“a%d=?”,i);scanf(&p-data);p-next=L-next;L-next=p;/插入表头插入表头 return L;单链表的基本运算单链表的基本运算单链表的基本运算单链表的基本运算2.3.2循环
6、链表循环链表n最后一个结点的指针域的指针又指回第一个结最后一个结点的指针域的指针又指回第一个结点的链表点的链表n和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个链表中最后一个结点的结点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后继是否为头结点后继是否为头结点”。a1a2anH(a)H(b)单循环链表p=Anext;Anext=Bnextnext;q=Bnext;Bnext=p;A=B;free(q);操作和线性链表基本一致，有时在循环链表中设立尾操作和线性链表基本一致，有时在循环链表中设立尾指针可使操作简化。见下图指针可使操作简化。见下图ABAB2.3.
7、3双向链表双向链表/-/-线性表的双向链表存储结构线性表的双向链表存储结构 -typedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/指向前驱的指针域 struct DuLNode*next;/指向后继的指针域 DuLNode,*DuLinkList;双向链表双向链表a1a2anheadheadai-1aies-prior=p-prior;psai-1ai插入插入p-prior-next=s;s-next=p;p-prior=s;ai-1删除删除aiai+1p-prior-next=p-next;p-next-prior=p-prior;free(p);pai-1