第一讲线性表 jsio.ppt

《第一讲线性表 jsio.ppt》由会员分享，可在线阅读，更多相关《第一讲线性表 jsio.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第一讲线性表第一讲线性表 JSIO2011 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学计算机的基本工作方式计算机的基本工作方式l将编好的程序和原始数据，输入并存储在将编好的程序和原始数据，输入并存储在计算机的内存储器中（即计算机的内存储器中（即“存储程序存储程序”）；）；l计算机按照程序逐条取出指令加以分析，计算机按照程序逐条取出指令加以分析，并执行指令规定的操作（即并执行指令规定的操作（即“程序控制程序控制”）。）。l这一原理称为这一原理称为存贮程序存

2、贮程序和和程序控制程序控制,是现代是现代计算机的基本工作方式。计算机的基本工作方式。程序程序是计算机的灵魂是计算机的灵魂 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学什么是数据结构（什么是数据结构（data structure）什么是算法（什么是算法（algorithm）程序=数据结构+算法是数据在计算机中的组织方式及相应的是数据在计算机中的组织方式及相应的基本访问操作。基本访问操作。是解决问题的方法（数据处理）或者步骤是解决问题的方法（数据处理）或者步骤

3、程序是什么？江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学线性表图书馆书目表数据元素 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学计算机和人对奕问题计算机和人对奕问题树树.江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A

4、)A 层 次 教 学层 次 教 学网络布线网络布线图图 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学三种基本数据结构三种基本数据结构l线性结构线性结构数据元素之间存在一对数据元素之间存在一对一的线性关系一的线性关系l树形结构树形结构数据元素之间存在一对数据元素之间存在一对多的层次关系多的层次关系l图状结构图状结构数据元素之间存在多对数据元素之间存在多对多的网状关系多的网状关系 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少

5、 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学顺序顺序存储结构存储结构链式链式存储结构存储结构数据在计算机中如何存储？数据在计算机中如何存储？江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺顺序序存存储储M：每个元素：

6、每个元素占用的存储单占用的存储单元元 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学元素元素2 2元素元素1 1元素元素3 3 元素元素4 4 链式存储链式存储 head1345140015361346140015361346 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 数据的逻辑结构数据的逻辑结构 数据的存储结构数据

7、的存储结构 数据结构的基本运算：查找、插入、删除数据结构的基本运算：查找、插入、删除 线性结构线性结构 顺序存储顺序存储 链式存储链式存储 树形结构树形结构图形结构图形结构小结：数据结构的三个方面：小结：数据结构的三个方面：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 快过新年了，小快过新年了，小L又要设计和大又要设计和大J玩的扑克玩的扑克牌游戏了。大牌游戏了。大J比较相信运气的说法，想让小比较相信运气的说法，想让小L设设计一种玩法测测明年的运气，当然没什

8、么科学性，计一种玩法测测明年的运气，当然没什么科学性，纯属娱乐。游戏规则如下：纯属娱乐。游戏规则如下：小小L和大和大J各准备一副牌各准备一副牌(去掉大小王去掉大小王)并相并相互交换洗好牌，将牌背面朝上各放成一排，小互交换洗好牌，将牌背面朝上各放成一排，小L翻开大翻开大J从左向右数的第从左向右数的第n张牌，如果牌面数为奇张牌，如果牌面数为奇数数a，小，小L将大将大J的第的第n张开始的张开始的a张牌取出按原次张牌取出按原次序依次放在自己的牌的最右边；如果牌面数为偶序依次放在自己的牌的最右边；如果牌面数为偶数数b，则将自己从左边向右数的，则将自己从左边向右数的b张牌取出按原张牌取出按原序放到大序放到

9、大J的牌的最左边。然后大的牌的最左边。然后大J也做同样的操也做同样的操作，两人轮流操作，谁最先将牌脱手，来年运气作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。时仍保持背面朝上。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学链式结构链式结构什么是指针什么是指针 指针是以存储单元的地址作为其值的一种数指针是以存储单元的地址作为其值的一种数据类型。据类型。100 p1

10、p134F234F234F234F2定义方式：定义方式：Type Type 指针类型标识符指针类型标识符=类型标识符；类型标识符；var var 指针变量名：指针类型标识符；指针变量名：指针类型标识符；江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学newnew（p1p1）向计算机申请内存地址向计算机申请内存地址 链式结构链式结构如何申请、释放存储单元如何申请、释放存储单元 p1p134F234F234F234F2typetype p=integer;p=in

11、teger;var p1:p;var p1:p;p1:=200p1:=200 给给p1p1指向的单元赋值指向的单元赋值dispose(p1)释放存储单元释放存储单元200200 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 p1:integer;arrp=array1.10 of real；Type p=integer;arr=array1.4 of char;arrp=arr;Var p1:p;p2:arrp;指针变量所指向的类型不同，指针变量所指向的类

12、型不同，计算机所给予的存储单元的多计算机所给予的存储单元的多少也不相同。少也不相同。指指针针类类型型定定义义中中的的基基类类型型只只能能是是类类型型标标识识符符，不不能能是是具具体体的的类型定义。类型定义。p1p1 p2p2i链式结构链式结构什么是指针什么是指针 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 begin begin new(p1);p1:=100;new(p1);p1:=100;new(p2);p2:=200;new(p2);p2:=200

13、;p1:=p2;p1:=p2;end.end.30103011402040214022402340243011p11001004024p22002004024p1 (1)(1)同一基类型的指针变量可以互相赋值。同一基类型的指针变量可以互相赋值。链式结构链式结构指针变量的基本操作指针变量的基本操作 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学(2)(2)指针变量指针变量p1p1置空置空 （nilnil）p1:=nilp1:=nil当希望某个指针变量不指向任何

14、存贮空间时，可以当希望某个指针变量不指向任何存贮空间时，可以赋值为空即赋值为空即 NIL NIL。(3)对指针变量可以进行关系运算对指针变量可以进行关系运算 如如:if P1P2 then 语句语句1 else 语句语句2;while P3 NIL do .end;关系运算的结果关系运算的结果,仍是仍是 FALSE,TRUE。链式结构链式结构指针变量的基本操作指针变量的基本操作 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学Type p=stu;stu=re

15、cord name:string10;number:integer;next:p；end;var p1,p2:p链式结构链式结构数据元素的定义数据元素的定义limingliming9090p1p1p1.namep1.namep1.numberp1.numberp1.nextp1.nextlimingliming9090p2p2p2.namep2.namep2.numberp2.numberp2.nextp2.next 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次

16、教 学游戏规则如下：游戏规则如下：小小L和大和大J各准备一副牌各准备一副牌(去掉大小王去掉大小王)并相并相互交换洗好牌，将牌背面朝上各放成一排，小互交换洗好牌，将牌背面朝上各放成一排，小L翻开大翻开大J从左向右数的第从左向右数的第n张牌，如果牌面数为奇张牌，如果牌面数为奇数数a，小，小L将大将大J的第的第n张开始的张开始的a张牌取出按原次张牌取出按原次序依次放在自己的牌的最右边；如果牌面数为偶序依次放在自己的牌的最右边；如果牌面数为偶数数b，则将自己从左边向右数的，则将自己从左边向右数的b张牌取出按原张牌取出按原序放到大序放到大J的牌的最左边。然后大的牌的最左边。然后大J也做同样的操也做同样的

17、操作，两人轮流操作，谁最先将牌脱手，来年运气作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。时仍保持背面朝上。例例1：扑克游戏：扑克游戏 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学元素元素2 2元素元素1 1元素元素3 3 元素元素4 41345head140015361346140015361346将独立的多个存储单元连接在一起，形成了一个将独立的多个存储单

18、元连接在一起，形成了一个“链链”，链中每一个单元称为，链中每一个单元称为“链链”中的一个中的一个“数据元素数据元素”。我们将它们通过指针域连在一起形成的链，称为线性链我们将它们通过指针域连在一起形成的链，称为线性链表。表。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学小小L翻开大翻开大J从左向右数的第从左向右数的第n张牌张牌查找链表的第查找链表的第n个元素个元素 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学

19、 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学线性链表线性链表查找查找(1)(1)设临时工作变量设临时工作变量p p指针指向链表的头结点指针指向链表的头结点(头结点的头结点的地址不能丢失和改变，地址不能丢失和改变，否则会丢失整个链表否则会丢失整个链表););p:=head;p:=head;(2)x:=0;(2)x:=0;while xn do while xn do begin begin inc(x);p:=p.next;inc(x);p:=p.next;end;end;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少

20、 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学小小L将大将大J的第的第n张开始的张开始的a张牌取出张牌取出链表元素的删除链表元素的删除 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表中删除：表中删除：r:=p.next;p.next:=r.next;dispose(r);表中删除表中删除headnilrp线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点 江 苏 省 青 少 年 信 息 学

21、 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学将自己从左边向右数的将自己从左边向右数的b张牌取出张牌取出 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表头删除：表头删除：p:=head;r:=p.next;p.next:=r.next;dispose(r);表头删除表头删除headnilrp三种情况：三种情况：删除删除p结点后的结点后的r结点结点线性链表

22、线性链表删除删除 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表尾删除：表尾删除：r:=p.next;p.next:=nil;dispose(r);表尾删除表尾删除headnilrpnil线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学按原次序依次放在自己的牌的

23、最右边按原次序依次放在自己的牌的最右边链表元素的插入链表元素的插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 表尾插入结点又如何实现呢？表尾插入结点又如何实现呢？nil将将s s结点插在结点插在p p结点之后结点之后n表尾插入 new(s);readln(x);s.data:=x;s.next:=nil;p.next:=s new(s);readln(x);s.data:=x;s.next:=nil;p.next:=sheadpsx表尾插入nil线性链

24、表线性链表插入插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学按原序放到大J的牌的最左边 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学n表头插入 new(s);readln(x);s.data:=x;s.next:=head;head:=snew(s);readln(x);s.data:=x;s.next:=head

25、;head:=s；headpsnilx表头插入这两步操作这两步操作顺序能颠倒顺序能颠倒吗？为什么吗？为什么？想一想：想一想：想一想：想一想：将将s s结点插在结点插在p p结点之后结点之后线性链表线性链表插入插入三种情况：三种情况：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学想一想：表中插入结点如何实现？想一想：表中插入结点如何实现？n表中插入 new(s);readln(x);s.data:=x;s.next:=p.next;p.next:=s new(

26、s);readln(x);s.data:=x;s.next:=p.next;p.next:=sheadpsnilx表中插入将将s s结点插在结点插在p p结点之后结点之后线性链表线性链表插入插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学线性链表应用的三种模式：线性链表应用的三种模式：（1）数据元素的查找数据元素的查找（2）数据元素的插入数据元素的插入（3）数据元素的删除。数据元素的删除。线性链表的访问基本方法是：线性链表的访问基本方法是：（1 1）从头

27、结点开始沿线性链表方向进行探求，一）从头结点开始沿线性链表方向进行探求，一般用于指向刚查过的结点地址，另一个用于指向下般用于指向刚查过的结点地址，另一个用于指向下一个待查的结点地址。一个待查的结点地址。（2 2）结束访问的条件有两个：一个是结点地址为）结束访问的条件有两个：一个是结点地址为Nil,Nil,另一个是找到了相应的结点。另一个是找到了相应的结点。容易出错的是：当容易出错的是：当p p为为nilnil时，取时，取p.datap.data时出错，因为时出错，因为p p是是nilnil，p.datap.data的值无意义。的值无意义。小结：小结：江 苏 省 青 少 年 信 息 学 奥 林

28、匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学输入一个正整数序列输入一个正整数序列,遇遇0 0时停止，按输入数据的顺时停止，按输入数据的顺序建立如下链表序建立如下链表:（从表头插入结点）（从表头插入结点）（1 1）初始化）初始化（2 2）申请一个结点并赋值，然后将结点插入表头）申请一个结点并赋值，然后将结点插入表头（3 3）重复（）重复（2 2），直到输入的值为等于），直到输入的值为等于0 0结束。结束。分析：分析：实战演练实战演练 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏

29、 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 readln(n);head:=nil;while n 0 do插入表头插入表头,形成链表形成链表 begin new(p);p.data:=n;p.next:=head;head:=p;read(n);end;参考程序：参考程序：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学（1）这样插入的链表有什么特点？）这样插入的链表有什么特点？（2）

30、可以用表尾插入来改变链表）可以用表尾插入来改变链表结点的顺序吗？程序怎样完成？结点的顺序吗？程序怎样完成？江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 head:=nil;read(x);while x0 do begin if head=nil then begin new(p);p.data:=x;p.next:=nil;q:=p;head:=p end else begin new(p);p.data:=x;pnext:=nil;q.next:=p;

31、q:=p;end;read(x);end;head 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学顺序表顺序表顺序表顺序表 链链链链 表表表表 空间空间分配分配静态分配。程序执行前静态分配。程序执行前须确定存储规模。估计须确定存储规模。估计过大造成空间浪费，估过大造成空间浪费，估计太小使空间溢出机会计太小使空间溢出机会增多。增多。动态分配动态分配,只要内存空间尚有空只要内存空间尚有空闲，就不会产生溢出。当线性表闲，就不会产生溢出。当线性表的长度变化较大，难以

32、估计存储的长度变化较大，难以估计存储规模时，宜采用动态链表作存储规模时，宜采用动态链表作存储结构为好结构为好。时间时间存取存取随机存取结构，查找方随机存取结构，查找方便，但插入和删除操作便，但插入和删除操作很费时。很费时。顺序存取结构，链表中的结点，顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取需从头指针起顺着链扫描才能取得。得。插入插入删除删除操作操作在顺序表中进行插入和在顺序表中进行插入和删除，平均要移动表中删除，平均要移动表中近一半的结点，尤其是近一半的结点，尤其是当每个结点的信息量较当每个结点的信息量较大时，移动结点的时间大时，移动结点的时间开销就相当可观。开销就相当可观。在

33、链表进行插入和删除，只需要在链表进行插入和删除，只需要修改指针。对于频繁进行插入和修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存删除的线性表，宜采用链表做存储结构。若表的插入和删除主要储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。指针表示的单循环链表为宜。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学实战演练：线性链表的归并运算：实战演练：线性链表的归并运算：将下列两个有序线性表进行归

34、并。将下列两个有序线性表进行归并。线性表（线性表（1 1）是：）是：33，5 5，8 8，1111，1313线性表（线性表（2 2）是：）是：11，4 4，5 5，9 9，1515归并后的线性表为：归并后的线性表为：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515（1 1）线性链表中的结点是按数据域由小到大进行排）线性链表中的结点是按数据域由小到大进行排列的，根据两个线性列的，根据两个线性链链表中结点数据域的大小进行归表中结点数据域的大小进行归并运算；哪个表中的数据小就归并哪一个；并运算；哪个表中的数据小就归并哪一个；1 1、建立链表、建立链表2 2、归并、归并问题分

35、析：问题分析：（2 2）当两个线性）当两个线性链链表中有一个已归并完毕，则另一个线表中有一个已归并完毕，则另一个线性性链链表的剩余部分全部复制到所建立的新线性表的剩余部分全部复制到所建立的新线性链链表中。表中。（3 3）如果出现同值时，则选一个值。）如果出现同值时，则选一个值。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学p1:=head1;p2:=head2;p1:=head1;p2:=head2;while(p1nil)and(p2nil)dowhile

36、(p1nil)and(p2nil)do begin begin if p1.data=p2.data if p1.data=p2.data then then 将链表将链表(1)(1)当前结点加到新链表中当前结点加到新链表中,p1,p1指针后移指针后移;else else 将链表将链表(1)(1)当前结点加到新链表中当前结点加到新链表中,p2,p2指针后移指针后移;end;end;if p1nil then if p1nil then 将链表将链表(1)(1)剩余的结点连接到新表的后面剩余的结点连接到新表的后面;if p2nil then if p2nil then 将链表将链表(2)(2)剩

37、余结点连到新表的后面剩余结点连到新表的后面;归并算法：归并算法：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学procedure combine(var head3:poi;head1,head2:poi);procedure combine(var head3:poi;head1,head2:poi);var p1,p2,q,r:poi;var p1,p2,q,r:poi;begin begin new(head3);r:=head3;new(head3)

38、;r:=head3;p1:=head1;p2:=head2;p1:=head1;p2:=head2;while(p1nil)and(p2nil)do while(p1nil)and(p2nil)do if p1.data=p2.data if p1.data=p2.data then begin then begin new(q);r.next:=q;q.data:=p1.data;new(q);r.next:=q;q.data:=p1.data;r:=q;p1:=p1.next;r:=q;p1:=p1.next;if if p1.data=p2.data then p2:=p2.next;e

39、nd end else begin else begin new(q);r.next:=q;q.data:=p2.data;r:=q;new(q);r.next:=q;q.data:=p2.data;r:=q;p2:=p2.next;p2:=p2.next;end;end;if p1nil then r.next:=p1;if p1nil then r.next:=p1;if p2nil then r.next:=p2;if p2nil then r.next:=p2;end;end;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹

40、克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学本算法在构建链表本算法在构建链表3 3时申请了新结点，能否时申请了新结点，能否不申请新结点来实现线性链表的归并？不申请新结点来实现线性链表的归并？想一想：想一想：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学procedure combine(var head3:poi;head1,head2:poi);procedure combine(var head3:poi;head1,hea

41、d2:poi);var p1,p2,q,r:poi;var p1,p2,q,r:poi;begin begin p1:=head1;p2:=head2;p1:=head1;p2:=head2;while(p1nil)and(p2nil)do while(p1nil)and(p2nil)do if p1.data=p2.data if p1.data=p2.data then begin then begin 操操 作作 1 1 end end else begin else begin 操操 作作 2 end;end;if p1nil then if p1nil then 操操 作作 3 3;

42、if p2nil then if p2nil then 操操 作作 4;end;end;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学不带附加不带附加头结点的头结点的链表链表heada1 a2 a3 a4a1 a2 a3 a4带附加头结带附加头结点的链表点的链表线性链表的几种形式：线性链表的几种形式：其特点如下：其特点如下：单向链表、双向链表、循环链表单向链表、双向链表、循环链表 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青

43、少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学单循环链表单循环链表双循环链表双循环链表 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 （1 1）尾结点指向第一个结点；尾结点指向第一个结点；（2 2）从表中任一个结点出发可以找到链表中的其他结点。）从表中任一个结点出发可以找到链表中的其他结点。（3 3）遍历操作的结束条件是：）遍历操作的结束条件是：（4 4）其他操作与单链表一样。）其他操作与单链表一

44、样。循环链表循环链表注意：注意：带附加头结点带附加头结点 p=head.nextp=head.next不带附加头结点不带附加头结点p=headp=head 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学双向链表双向链表双链表的操作与单链表基本一致：双链表的操作与单链表基本一致：123412type type poi=node;poi=node;node=record node=record data:datatypedata:datatype;pre,nex

45、t:poi;pre,next:poi;end;end;（1）每个结点有两个指针域，）每个结点有两个指针域，一个指向其前驱结点，一个一个指向其前驱结点，一个指向其后继结点。指向其后继结点。（2）从任一结点出发可以访）从任一结点出发可以访问其他结点。问其他结点。便于访问、插入和删除。便于访问、插入和删除。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学双向循环链表：最后一个结点的指针指向头结点，双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个

46、结点。如下图：且头结点的前趋指向最后一个结点。如下图：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学问题描述：设有问题描述：设有n n个人围成一圈，并按顺个人围成一圈，并按顺时针方向从时针方向从1 1到到n n编号；从第编号；从第s s个人开始进个人开始进行行1 1到到m m报数，数到报数，数到m m的人出圈；接着再从的人出圈；接着再从他后面一个人重新开始他后面一个人重新开始1 1到到m m报数，直到报数，直到所有人出圈为止。输出出圈人的次序。所有人出圈为止

47、。输出出圈人的次序。例例2：约瑟夫问题。：约瑟夫问题。约瑟夫问题。约瑟夫问题。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学分析分析:(1)(1)N N 个个人人按按序序号号围围坐坐一一圈圈，即即第第 1 1 个个人人后后是是第第 2 2 个个人人.第第N N 个个人人的的后后继继是是第第 1 1 个个人人,形形成成循循环环链表的结构，链表的结构，所以可采用循环链表表示这所以可采用循环链表表示这 N N 个人个人;(2)(2)每每一一个个结结点点有有两两个个

48、域域:数数据据域域人人的的编编号号,指针域指针域指向下一个人的地址指向下一个人的地址;(3)(3)报报数数 :即即数数人人个个数数,每每当当数数到到 M M 时时,则则该该号号人走出圈内人走出圈内删除该结点删除该结点,输出人编号输出人编号;(4)(4)重复重复(3)(3)过程过程,直到只有一个人为止。直到只有一个人为止。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学数据结构：数据结构：type poiman;manrecord num:integer;nex

49、t:poi;end;var head,p,q:poi;n,m:integer;建立循环链表建立循环链表Procedure creat(var head:poi);var p,q:poi;i:integer;begin new(p);head:=p;p.num:=1;q:=p;for i:=2 to n do begin new(p);end;q.next:=head;end;p.num:=i;q.next:=p;q:=p;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层

50、次 教 学Procedure select(var head:poi);var（选举大王的过程）（选举大王的过程）p,q:poi;i,x:integer;begin p:=head;x:=1;q:=p;repeat p:=q.next;x:=x1;if x mod m=0 then else q:=p;until p=p.next;（只剩一个结点）（只剩一个结点）writeln;head:=p;end;（Q Q 为为 P P 的前趋指针）的前趋指针）BEGIN 主程序主程序 readln(n,m);creat(head);select(head);write(the king :);write