数据结构-2(线性表链式结构)

1、. 线性表的链式存贮结构线性表的链式存贮结构线性表的链式存贮结构，也称为链表。线性表的链式存贮结构，也称为链表。用一组任意的存贮单元用一组任意的存贮单元( (可连续，也可以不连续可连续，也可以不连续) )来存来存 放线性表的数据元素值及它在内存的地址，放线性表的数据元素值及它在内存的地址，常用的链表常用的链表: : 单链表、单链表、循环链表、循环链表、双向链表、双向链表、多重链表等。多重链表等。. 单链表结构单链表结构 只含有一个指针域来存放下一个元素地址，称这只含有一个指针域来存放下一个元素地址，称这 样的链表为单链表或线性链表。样的链表为单链表或线性链表。 线性链表中的结点结构可描述为线性

2、链表中的结点结构可描述为: : Data next next data 域：用来存放结点本身信息，类型由具体问题域：用来存放结点本身信息，类型由具体问题 而定，本书中将其设定为而定，本书中将其设定为elemtype类型，表示某一类型，表示某一 种具体的已知类型，种具体的已知类型， next域用来存放下一个元素地址。域用来存放下一个元素地址。 a2 180 a4 170 a6 NULL a1 110 a5 140 a3 130 150 地址 data 域 next 域 110 120 130 140 150 160 170 180 head 头指针 图 2-5 单链表示意图 a1 a2 a3 a

3、4 a5 a6 图-6 单链表的逻辑表示 单链表可用单链表可用+描述为描述为:struct link elemtype data; /元素类型元素类型 link *next; /指针类型指针类型,存放下一个元素地址存放下一个元素地址 (a) 不带头结点的单链表 a1 head a2 an (b) 带头结点的单链表 head an 头 a1 a2 图 2-7 不带头结点和带头结点的单链表 232 单链表运算单链表运算 头插法建立单链表头插法建立单链表(如下图所示如下图所示)执 行 的 语 句 组 为 :s next L next； L next s；L(a) 建空表c1ss 指向新申请的结点s

4、data c1(b) 申请新结点并赋值Lci1s(c) 插入第一个结点Lc2c1cic1s(d) 插入第i个元素232 单链表运算单链表运算 头插法建立单链表头插法建立单链表(从左边插入结点从左边插入结点)link *hcreat( ) link *s,*p; int c1; /指针指针S，指针，指针P，变量，变量C1 cinc1; /输入结点数值，为输入结点数值，为0时算法结束时算法结束 p=NULL; /线性表为空表线性表为空表 while(c1) s=new link; /生成新结点生成新结点S s-data=c1; /新结点新结点S的值为的值为C1 s-next=p; /S的后继结点的

5、地址为的后继结点的地址为P p=s; return p; /返回返回P结点的地址结点的地址2 尾插法建立单链表尾插法建立单链表(如下图所示如下图所示)rs；r 始终指向单链表的表尾L(a) 建空表c1ss 指向新申请的结点空间sdatac1(b) 申请新结点并赋值Lc1s(c) 插入第一个结点Lc2c1rrr nexts；(d) 插入第二个结点sr2 尾插法建立单链表尾插法建立单链表(从右边插入结点从右边插入结点) link *rcreat( ) link *s,*r,*p; /指针类型指针类型 int c1; p=r=new link; /生成新结点生成新结点 p，r p-next=NULL

6、; /p结点的后继结点为空结点的后继结点为空 cinc1; while(c1) s=new link; /生成新结点生成新结点 s s-data=c1; /s结点的数据值为结点的数据值为c1 r-next=s; /r结点的后继结点为结点的后继结点为s r=s; /s结点的地址传给结点的地址传给r结点结点 cinc1; r-next=NULL; /r的后继结点为空的后继结点为空 return p; 3 单链表上的查找运算单链表上的查找运算(1) 按值查找按值查找Locate(head,x)在单链表在单链表head中，查找值为中，查找值为x的结点，若找到，返回它的结点，若找到，返回它的地址，否则返

7、回的地址，否则返回NULL。(2) 按序号查找按序号查找get(head,i)在单链表在单链表head中查找第中查找第i个位置上的元素，若找到，个位置上的元素，若找到，则返回它的地址，否则返回则返回它的地址，否则返回NULL。按值查找：按值查找：Link *Locate(link *head,elemtype x) link *p; p=head-next; while(p!=NULL)&(p-data!=x) p=p-next; return p; 算法的时间复杂度都为算法的时间复杂度都为(n)。 按序号查找：按序号查找：Link *get(link *head,int i) int

8、 j; link *p; j=1; p=head-next; while(jnext; return p; 算法的时间复杂度都为算法的时间复杂度都为(n)。 4 单链表上的插入运算单链表上的插入运算 若将若将x插入插入a和和b 之间，插入结点的指针变化如图之间，插入结点的指针变化如图-8所示。所示。 s a b x p 图 2-8 插入结点时的指针修改 void insert(link *head,elemtype x,elemtype y)/头指针头指针head所指单链表中所指单链表中,在值为在值为y的结点之后插入值为的结点之后插入值为x的结点的结点 link *p,*s; s=new li

9、nk; s-data=x; if(head-next=NULL) /链表为空链表为空 head-next=s; s-next=NULL; p=Locate(head,y) /调用查找算法调用查找算法 if(p=NULL) coutnext=p-next; p-next=s; 单链表上的删除运算单链表上的删除运算若将若将x删除，删除结点的指针变化如图删除，删除结点的指针变化如图2-9所示。所示。 p q a1 x a2 图 2-9 删除结点的指针修改 void delete(link *head,elemtype x)/在在head为头指针的单链表中为头指针的单链表中,删除值为删除值为x的结点的

10、结点 link *p,*q; q=head; p=head-next; while(p!=NULL)&(p-data!=x) q=p; p=p-next; if(p=NULL) coutnext=p-next; delete(p); 输出单链表输出单链表 若需将单链表按逻辑顺序输出若需将单链表按逻辑顺序输出(见图见图-10)，则必须从头，则必须从头到尾访问单链表中每一个结点，到尾访问单链表中每一个结点， an 头 a1 head a2 ( a )单链表示意图 a1 a2 an (b )单链表输出结果示意图 图 2-10 单链表按逻辑结构输出示意图 void print(link *he

11、ad) link *p; p=head-next; while(p-next!=NULL) coutdata”; /输出表中非最后一个元素输出表中非最后一个元素 p=p-next; coutdata; /输出表中最后一个元素输出表中最后一个元素 coutprior-next = p = p-next-prior 双向循环链表（见下图所示）双向循环链表（见下图所示） 头 a1 a2 an 尾 head rear (a) 双向链表示意图 双向循环链表（见下图所示）双向循环链表（见下图所示）La1a2a3L(a) 空的双向循环链表(b) 非空的双向循环链表双向循环链表示意图双向循环链表示意图 双向链

12、表可用双向链表可用C+描述如下：描述如下：struct dulink elemtype data; /结点的数据域结点的数据域,类型设定为类型设定为elemtype dulink * next, *prior; /定义指向直接后继和直接定义指向直接后继和直接 前驱的指针前驱的指针 2 2双向链表插入运算双向链表插入运算 duinsert (head,x,y) (head,x,y) 在双向链表中，在值为在双向链表中，在值为a a的结点之后的结点之后,b,b的结点之间的结点之间插入值为插入值为c c的结点，插入结点的指针变化见下图的结点，插入结点的指针变化见下图 所示所示 abspc双向链表插入操作图双向链表插入操作图 插入算法描述为：插入算法描述为： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; 3 。双向链表的删除运算。双向链表的删除运算 dudelete(head ,x)在以在以head为头的双向链表中删除值为为头的双向链表中删除值为x的结点，删的结点，删除算法的指针变化见图除算法的指针变化见图2-17。 p a x b 图 2-17 删除 P 指针所指结 点示意图 删除算法描述为删除算法描述为:void dudelete(dulink *