第一讲线性表-JSIO课件

江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学计算机的基本工作方式计算机的基本工作方式l将编好的程序和原始数据，输入并存储在将编好的程序和原始数据，输入并存储在计算机的内存储器中（即计算机的内存储器中（即“存储程序存储程序”）；）；l计算机按照程序逐条取出指令加以分析，计算机按照程序逐条取出指令加以分析，并执行指令规定的操作（即并执行指令规定的操作（即“程序控制程序控制”）。）。l这一原理称为这一原理称为存贮程序存贮程序和和程序控制程序控制,是现代是现代计算机的基本工作方式。计算机的基本工作方式。程序程序是计算机的灵魂是计算机的灵魂 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学什么是数据结构（什么是数据结构（data structure）什么是算法（什么是算法（algorithm）程序=数据结构+算法是数据在计算机中的组织方式及相应的是数据在计算机中的组织方式及相应的基本访问操作。基本访问操作。是解决问题的方法（数据处理）或者步骤是解决问题的方法（数据处理）或者步骤程序是什么？江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学线性表图书馆书目表数据元素 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学计算机和人对奕问题计算机和人对奕问题树树.江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学网络布线网络布线图图 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学三种基本数据结构三种基本数据结构l线性结构线性结构数据元素之间存在一对数据元素之间存在一对一的线性关系一的线性关系l树形结构树形结构数据元素之间存在一对数据元素之间存在一对多的层次关系多的层次关系l图状结构图状结构数据元素之间存在多对数据元素之间存在多对多的网状关系多的网状关系 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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：每个元素：每个元素占用的存储单占用的存储单元元 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学元素元素2 2元素元素1 1元素元素3 3 元素元素4 4 链式存储链式存储 head1345140015361346140015361346 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据结构的基本运算：查找、插入、删除数据结构的基本运算：查找、插入、删除 线性结构线性结构 顺序存储顺序存储 链式存储链式存储 树形结构树形结构图形结构图形结构小结：数据结构的三个方面：小结：数据结构的三个方面：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 快过新年了，小快过新年了，小L又要设计和大又要设计和大J玩的扑克玩的扑克牌游戏了。大牌游戏了。大J比较相信运气的说法，想让小比较相信运气的说法，想让小L设设计一种玩法测测明年的运气，当然没什么科学性，计一种玩法测测明年的运气，当然没什么科学性，纯属娱乐。游戏规则如下：纯属娱乐。游戏规则如下：小小L和大和大J各准备一副牌各准备一副牌(去掉大小王去掉大小王)并相并相互交换洗好牌，将牌背面朝上各放成一排，小互交换洗好牌，将牌背面朝上各放成一排，小L翻开大翻开大J从左向右数的第从左向右数的第n张牌，如果牌面数为奇张牌，如果牌面数为奇数数a，小，小L将大将大J的第的第n张开始的张开始的a张牌取出按原次张牌取出按原次序依次放在自己的牌的最右边；如果牌面数为偶序依次放在自己的牌的最右边；如果牌面数为偶数数b，则将自己从左边向右数的，则将自己从左边向右数的b张牌取出按原张牌取出按原序放到大序放到大J的牌的最左边。然后大的牌的最左边。然后大J也做同样的操也做同样的操作，两人轮流操作，谁最先将牌脱手，来年运气作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。时仍保持背面朝上。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学链式结构链式结构什么是指针什么是指针 指针是以存储单元的地址作为其值的一种数指针是以存储单元的地址作为其值的一种数据类型。据类型。100 p1p134F234F234F234F2定义方式：定义方式：Type Type 指针类型标识符指针类型标识符=类型标识符；类型标识符；var var 指针变量名：指针类型标识符；指针变量名：指针类型标识符；江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学newnew（p1p1）向计算机申请内存地址向计算机申请内存地址 链式结构链式结构如何申请、释放存储单元如何申请、释放存储单元 p1p134F234F234F234F2typetype p=integer;p=integer;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;指针变量所指向的类型不同，指针变量所指向的类型不同，计算机所给予的存储单元的多计算机所给予的存储单元的多少也不相同。少也不相同。指指针针类类型型定定义义中中的的基基类类型型只只能能是是类类型型标标识识符符，不不能能是是具具体体的的类型定义。类型定义。p1p1 p2p2i链式结构链式结构什么是指针什么是指针 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 begin begin new(p1);p1:=100;new(p1);p1:=100;new(p2);p2:=200;new(p2);p2:=200;p1:=p2;p1:=p2;end.end.30103011402040214022402340243011p11001004024p22002004024p1 (1)(1)同一基类型的指针变量可以互相赋值。同一基类型的指针变量可以互相赋值。链式结构链式结构指针变量的基本操作指针变量的基本操作 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学(2)(2)指针变量指针变量p1p1置空置空 （nilnil）p1:=nilp1:=nil当希望某个指针变量不指向任何存贮空间时，可以当希望某个指针变量不指向任何存贮空间时，可以赋值为空即赋值为空即 NIL NIL。(3)对指针变量可以进行关系运算对指针变量可以进行关系运算 如如:if P1P2 then 语句语句1 else 语句语句2;while P3 NIL do .end;关系运算的结果关系运算的结果,仍是仍是 FALSE,TRUE。链式结构链式结构指针变量的基本操作指针变量的基本操作 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学Type p=stu;stu=record 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 层 次 教 学层 次 教 学游戏规则如下：游戏规则如下：小小L和大和大J各准备一副牌各准备一副牌(去掉大小王去掉大小王)并相并相互交换洗好牌，将牌背面朝上各放成一排，小互交换洗好牌，将牌背面朝上各放成一排，小L翻开大翻开大J从左向右数的第从左向右数的第n张牌，如果牌面数为奇张牌，如果牌面数为奇数数a，小，小L将大将大J的第的第n张开始的张开始的a张牌取出按原次张牌取出按原次序依次放在自己的牌的最右边；如果牌面数为偶序依次放在自己的牌的最右边；如果牌面数为偶数数b，则将自己从左边向右数的，则将自己从左边向右数的b张牌取出按原张牌取出按原序放到大序放到大J的牌的最左边。然后大的牌的最左边。然后大J也做同样的操也做同样的操作，两人轮流操作，谁最先将牌脱手，来年运气作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。时仍保持背面朝上。例例1：扑克游戏：扑克游戏 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学元素元素2 2元素元素1 1元素元素3 3 元素元素4 41345head140015361346140015361346将独立的多个存储单元连接在一起，形成了一个将独立的多个存储单元连接在一起，形成了一个“链链”，链中每一个单元称为，链中每一个单元称为“链链”中的一个中的一个“数据元素数据元素”。我们将它们通过指针域连在一起形成的链，称为线性链我们将它们通过指针域连在一起形成的链，称为线性链表。表。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学小小L翻开大翻开大J从左向右数的第从左向右数的第n张牌张牌查找链表的第查找链表的第n个元素个元素 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学小小L将大将大J的第的第n张开始的张开始的a张牌取出张牌取出链表元素的删除链表元素的删除 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表中删除：表中删除：r:=p.next;p.next:=r.next;dispose(r);表中删除表中删除headnilrp线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学将自己从左边向右数的将自己从左边向右数的b张牌取出张牌取出 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表头删除：表头删除：p:=head;r:=p.next;p.next:=r.next;dispose(r);表头删除表头删除headnilrp三种情况：三种情况：删除删除p结点后的结点后的r结点结点线性链表线性链表删除删除 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学表尾删除：表尾删除：r:=p.next;p.next:=nil;dispose(r);表尾删除表尾删除headnilrpnil线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学按原次序依次放在自己的牌的最右边按原次序依次放在自己的牌的最右边链表元素的插入链表元素的插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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线性链表线性链表插入插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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;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(s);readln(x);s.data:=x;s.next:=p.next;p.next:=sheadpsnilx表中插入将将s s结点插在结点插在p p结点之后结点之后线性链表线性链表插入插入 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学线性链表应用的三种模式：线性链表应用的三种模式：（1）数据元素的查找数据元素的查找（2）数据元素的插入数据元素的插入（3）数据元素的删除。数据元素的删除。线性链表的访问基本方法是：线性链表的访问基本方法是：（1 1）从头结点开始沿线性链表方向进行探求，一）从头结点开始沿线性链表方向进行探求，一般用于指向刚查过的结点地址，另一个用于指向下般用于指向刚查过的结点地址，另一个用于指向下一个待查的结点地址。一个待查的结点地址。（2 2）结束访问的条件有两个：一个是结点地址为）结束访问的条件有两个：一个是结点地址为Nil,Nil,另一个是找到了相应的结点。另一个是找到了相应的结点。容易出错的是：当容易出错的是：当p p为为nilnil时，取时，取p.datap.data时出错，因为时出错，因为p p是是nilnil，p.datap.data的值无意义。的值无意义。小结：小结：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学输入一个正整数序列输入一个正整数序列,遇遇0 0时停止，按输入数据的顺时停止，按输入数据的顺序建立如下链表序建立如下链表:（从表头插入结点）（从表头插入结点）（1 1）初始化）初始化（2 2）申请一个结点并赋值，然后将结点插入表头）申请一个结点并赋值，然后将结点插入表头（3 3）重复（）重复（2 2），直到输入的值为等于），直到输入的值为等于0 0结束。结束。分析：分析：实战演练实战演练 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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）可以用表尾插入来改变链表）可以用表尾插入来改变链表结点的顺序吗？程序怎样完成？结点的顺序吗？程序怎样完成？江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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;q:=p;end;read(x);end;head 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学顺序表顺序表顺序表顺序表 链链链链 表表表表 空间空间分配分配静态分配。程序执行前静态分配。程序执行前须确定存储规模。估计须确定存储规模。估计过大造成空间浪费，估过大造成空间浪费，估计太小使空间溢出机会计太小使空间溢出机会增多。增多。动态分配动态分配,只要内存空间尚有空只要内存空间尚有空闲，就不会产生溢出。当线性表闲，就不会产生溢出。当线性表的长度变化较大，难以估计存储的长度变化较大，难以估计存储规模时，宜采用动态链表作存储规模时，宜采用动态链表作存储结构为好结构为好。时间时间存取存取随机存取结构，查找方随机存取结构，查找方便，但插入和删除操作便，但插入和删除操作很费时。很费时。顺序存取结构，链表中的结点，顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取需从头指针起顺着链扫描才能取得。得。插入插入删除删除操作操作在顺序表中进行插入和在顺序表中进行插入和删除，平均要移动表中删除，平均要移动表中近一半的结点，尤其是近一半的结点，尤其是当每个结点的信息量较当每个结点的信息量较大时，移动结点的时间大时，移动结点的时间开销就相当可观。开销就相当可观。在链表进行插入和删除，只需要在链表进行插入和删除，只需要修改指针。对于频繁进行插入和修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存删除的线性表，宜采用链表做存储结构。若表的插入和删除主要储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。指针表示的单循环链表为宜。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学实战演练：线性链表的归并运算：实战演练：线性链表的归并运算：将下列两个有序线性表进行归并。将下列两个有序线性表进行归并。线性表（线性表（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、归并、归并问题分析：问题分析：（2 2）当两个线性）当两个线性链链表中有一个已归并完毕，则另一个线表中有一个已归并完毕，则另一个线性性链链表的剩余部分全部复制到所建立的新线性表的剩余部分全部复制到所建立的新线性链链表中。表中。（3 3）如果出现同值时，则选一个值。）如果出现同值时，则选一个值。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学p1:=head1;p2:=head2;p1:=head1;p2:=head2;while(p1nil)and(p2nil)dowhile(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)剩余结点连到新表的后面剩余结点连到新表的后面;归并算法：归并算法：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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);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;end 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;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学本算法在构建链表本算法在构建链表3 3时申请了新结点，能否时申请了新结点，能否不申请新结点来实现线性链表的归并？不申请新结点来实现线性链表的归并？想一想：想一想：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)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 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;if p2nil then if p2nil then 操操 作作 4;end;end;江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学不带附加不带附加头结点的头结点的链表链表heada1 a2 a3 a4a1 a2 a3 a4带附加头结带附加头结点的链表点的链表线性链表的几种形式：线性链表的几种形式：其特点如下：其特点如下：单向链表、双向链表、循环链表单向链表、双向链表、循环链表 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学单循环链表单循环链表双循环链表双循环链表 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学 （1 1）尾结点指向第一个结点；尾结点指向第一个结点；（2 2）从表中任一个结点出发可以找到链表中的其他结点。）从表中任一个结点出发可以找到链表中的其他结点。（3 3）遍历操作的结束条件是：）遍历操作的结束条件是：（4 4）其他操作与单链表一样。）其他操作与单链表一样。循环链表循环链表注意：注意：带附加头结点带附加头结点 p=head.nextp=head.next不带附加头结点不带附加头结点p=headp=head 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学双向链表双向链表双链表的操作与单链表基本一致：双链表的操作与单链表基本一致：123412type type poi=node;poi=node;node=record node=record data:datatypedata:datatype;pre,next:poi;pre,next:poi;end;end;（1）每个结点有两个指针域，）每个结点有两个指针域，一个指向其前驱结点，一个一个指向其前驱结点，一个指向其后继结点。指向其后继结点。（2）从任一结点出发可以访）从任一结点出发可以访问其他结点。问其他结点。便于访问、插入和删除。便于访问、插入和删除。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学双向循环链表：最后一个结点的指针指向头结点，双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：且头结点的前趋指向最后一个结点。如下图：江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学问题描述：设有问题描述：设有n n个人围成一圈，并按顺个人围成一圈，并按顺时针方向从时针方向从1 1到到n n编号；从第编号；从第s s个人开始进个人开始进行行1 1到到m m报数，数到报数，数到m m的人出圈；接着再从的人出圈；接着再从他后面一个人重新开始他后面一个人重新开始1 1到到m m报数，直到报数，直到所有人出圈为止。输出出圈人的次序。所有人出圈为止。输出出圈人的次序。例例2：约瑟夫问题。：约瑟夫问题。约瑟夫问题。约瑟夫问题。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学分析分析:(1)(1)N N 个个人人按按序序号号围围坐坐一一圈圈，即即第第 1 1 个个人人后后是是第第 2 2 个个人人.第第N N 个个人人的的后后继继是是第第 1 1 个个人人,形形成成循循环环链表的结构，链表的结构，所以可采用循环链表表示这所以可采用循环链表表示这 N N 个人个人;(2)(2)每每一一个个结结点点有有两两个个域域:数数据据域域人人的的编编号号,指针域指针域指向下一个人的地址指向下一个人的地址;(3)(3)报报数数 :即即数数人人个个数数,每每当当数数到到 M M 时时,则则该该号号人走出圈内人走出圈内删除该结点删除该结点,输出人编号输出人编号;(4)(4)重复重复(3)(3)过程过程,直到只有一个人为止。直到只有一个人为止。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学数据结构：数据结构：type poiman;manrecord num:integer;next: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 层 次 教 学层 次 教 学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 :);writeln(head.num);END.begin q.next:=p.next;write(p.num:8);dispose(p);end 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学例3：营业额统计给定给定N（1N32767）天的营业额）天的营业额a1,a2,an.定义一天的最小波动值等于定义一天的最小波动值等于 min|该天以前某一天的营业额该天以前某一天的营业额-该天营业该天营业额额|特别地，第一天的最小波动值即为特别地，第一天的最小波动值即为a1 试求试求N天的最小波动值之和天的最小波动值之和例如：例如：N=3,a1=9,a2=3,a3=8，则各天最小波动值，则各天最小波动值依次为依次为9，6，1，和为，和为16 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学分析穷举：穷举：O(N2)算法低效算法低效树树基本数据结构能否在这里得到应用呢？基本数据结构能否在这里得到应用呢？没有高效地将数据组织起来，而是松散地存储在数组没有高效地将数据组织起来，而是松散地存储在数组中，导致对于每一个营业额都需要检查前面所有的营中，导致对于每一个营业额都需要检查前面所有的营业额。业额。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学1、将这、将这N个元素进行排序，得到序列个元素进行排序，得到序列c，同，同时时 记录原来第记录原来第i个元素在排序后的位置个元素在排序后的位置bi2、将排序后的序列在静态数组中建成一、将排序后的序列在静态数组中建成一 个双向链表个双向链表 3、按照从、按照从an到到a1的顺序依次处理每个元的顺序依次处理每个元素素 算法分析 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学双向链表3.1 对于对于an，查看，查看bn的前驱的前驱prebn与后继与后继nextbn 所指的数所指的数3.2 最小波动值必然是最小波动值必然是an与这两个数中的某一与这两个数中的某一个的差的绝对值个的差的绝对值3.3 处理完处理完an后，我们把它从双向链表中删除，后，我们把它从双向链表中删除，接着处理接着处理an-1 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学动画演示9 3 8a:3 8 9c:3 1 2b:389最小波动值为min|8-3|,|8-9|=min6,1=139最小波动值为min|3-9|=6最小波动值为9最小波动值总和为1+6+9=16 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学A:9 3 8 5 7排序得 c:3 5 7 8 9建双向链表 a在c中的位置b：5 1 4 2 3下标12345data35789pre01234next23450对b操作，从后往前,b5=3,c3=7，处理7，在双向表中删除7，再取b4=2,c2=5,江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学1、输入、输入N，a1，a2，a3，an2、将将a1，a2，a3，an按按照照从从小小到到大大的的顺顺序序排排序序，得得到到序序列列c1，c2，c3，cn，并并记记录录下下每每个个ai在在新新序列中的位置序列中的位置bi3、在新的序列上建立双向链表、在新的序列上建立双向链表4、按照从、按照从an到到a1的顺序依次处理每个元素：的顺序依次处理每个元素：result：=0;for i:=n downto 2 do begin result:=resul+min|ai-c|,|ai-c|;（如果（如果prebi=0或或nextbi=0则不予考虑）则不予考虑）end;result:=result+a1;5、输出、输出result伪代码伪代码 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学时间复杂度分析排序O(Nlog2N)建表O(N)处理O(N)O(Nlog2N)江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学小结树树编程复杂度高编程复杂度高基本数据结构基本数据结构双向链表双向链表没有增加时间复杂度没有增加时间复杂度大大降低编程复杂度大大降低编程复杂度思路清晰思路清晰见解独到见解独到 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学转眼就到除夕了，一边欣赏精彩的电视节目转眼就到除夕了，一边欣赏精彩的电视节目一边玩扑克牌是小一边玩扑克牌是小L最开心的事，不过今年的最开心的事，不过今年的游戏玩得有点不过瘾，为了增强游戏玩得有点不过瘾，为了增强“科学性科学性”，小小L想增加扑克牌的数量，并把原来移动的想增加扑克牌的数量，并把原来移动的a张为张为a6张，张，b张改为张改为b6张。可是玩一局太慢了。张。可是玩一局太慢了。他说：他说：“大大J，你不是编程高手吗，你编个程，你不是编程高手吗，你编个程序在电脑上玩，就算有几百万张牌，上万次序在电脑上玩，就算有几百万张牌，上万次的操作，一秒钟就完成。的操作，一秒钟就完成。”大大J汗汗，这个，这个难题就交给你了，帮她出个主意吧。难题就交给你了，帮她出个主意吧。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学数数组链表表定位定位O(1)O(N)添加或添加或删除除O(N)O(1)分析题意：1、在指定位置添加指定长度信息；2、从指定位置开始删除指定长度的信息；在整体上用链表，具体每一个链表节点改为一个大小适当（比如1000、1500）的数组，那么就可以“优势互补”，得到两种操作更加平衡的数据结构，也就是“块状链表”。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学两个内部基本操作：定位：从第一个分块开始向后直到找到指定位置所在的分块和他在分块内的位置。分裂：将指定分块从指定位置分裂成为两个分块。江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学1、Insert：找到指定位置，分裂块，添加新块直到添加完成。从这里开始插入分裂 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学2、Erase：找到起始位置，分裂首尾块，删掉中间的所有节点。删除虚线之间的文本 江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营江 苏 省 青 少 年 信 息 学 奥 林 匹 克 冬 令 营(镇 江 营镇 江 营)A)A 层 次 教 学层 次 教 学还有一个问题：频繁的分裂操作可能会导致很多连续的块实际储存的数据都很少，大大降低了块状链表的效率，我们可以在每次操作后把过于小的连续分块合并起来。END