第一讲 线性表

1、计算机的基本工作方式l将编好的程序和原始数据，输入并存储在将编好的程序和原始数据，输入并存储在计算机的内存储器中（即计算机的内存储器中（即“存储程序存储程序”）；）；l计算机按照程序逐条取出指令加以分析，计算机按照程序逐条取出指令加以分析，并执行指令规定的操作（即并执行指令规定的操作（即“程序控制程序控制”）。）。l这一原理称为这一原理称为存贮程序存贮程序和和程序控制程序控制,是现代是现代计算机的基本工作方式。计算机的基本工作方式。程序程序是计算机的灵魂是计算机的灵魂什么是数据结构（什么是数据结构（data structure）什么是算法（什么是算法（algorithm）程序程序=数据结构数据

2、结构+算法算法是数据在计算机中的组织方式及相应的基本访问操作。是解决问题的方法（数据处理）或者步骤程序是什么？001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02线性表图书馆书目表数据元素计算机和人对奕问题计算机和人对奕问题树树.网络布线网络布线图图三种基本数据结构l线性结构线性结构数据元素之间存在一对数据元素之间存在一对一的线性关系一的线性关系l树形结构树形结构数据元素之间存在一对数据元素之间存在一对多的层次关系多的层次关系l图状结构图状结构数据元素之间存在多对数据元素之间存在多对多的网状关系多的网状关系问题问题归并两个有序线性表。归并两个

3、有序线性表。如：将下列两个有序线性表进行归并：如：将下列两个有序线性表进行归并：线性表（线性表（1 1）是：）是：33，5 5，8 8，1111，1313线性表（线性表（2 2）是：）是：11，4 4，5 5，9 9，1515问题问题2 2：归并后的线性表为：归并后的线性表为：11，3 3，4 4，5 5，8 8，9 9，1111，1313，1515问题问题1 1：归并后的线性表为：归并后的线性表为：11，3 3，4 4，5 5，5 5，8 8，9 9，1111，1313，1515顺序存储结构链式存储结构数据在计算机中如何存储？数据在计算机中如何存储？元素元素n n.元素元素i i.元素元素2

4、 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺顺序序存存储储M：每个元素占用的存储单元元素元素2 2元素元素1 1元素元素3 3 元素元素4 4 链式存储链式存储 head13451400153613461400153613461、数据的逻辑结构与存储结构、数据的逻辑结构与存储结构之间有怎样的关系？之间有怎样的关系？讨论：讨论：2、从两种结构看如何组织数据？、从两种结构看如何组织数据？ 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据结构的基本运算：查找、插入、删除数据结构的基本

5、运算：查找、插入、删除 线性结构线性结构 顺序存储顺序存储 链式存储链式存储 树形结构树形结构图形结构图形结构小结：数据结构的三个方面：小结：数据结构的三个方面：链式结构链式结构什么是指针什么是指针指针是以存储单元的地址作为其值的一种指针是以存储单元的地址作为其值的一种数据类型。数据类型。 100 p1p13434F2F23434F2F2定义方式：定义方式：Type Type 指针类型标识符指针类型标识符=类型标识符；类型标识符； var var 指针变量名：指针类型标识符；指针变量名：指针类型标识符；newnew（p1p1） 向计算机申请内存地址向计算机申请内存地址 链式结构链式结构如何申请

6、、释放存储单元如何申请、释放存储单元 p1p13434F2F23434F2F2typetype point=integer; point=integer;var var p1:point;p1:point;p1:=200p1:=200 给给p1p1指向的单元赋值指向的单元赋值dispose(p1) 释放存储单元释放存储单元200200 p1:integer;arrpoint = array1.10 of real；Type point=integer; arr=array1.4 of char; arrpoint = arr; Var p1:point; p2:arrpoint;指针变量所指向

7、的类型不同，指针变量所指向的类型不同，计算机所给予的存储单元的多计算机所给予的存储单元的多少也不相同。少也不相同。指针类型定义中的基类型只能指针类型定义中的基类型只能是类型标识符，不能是具体的是类型标识符，不能是具体的类型定义。类型定义。 p1p1 p2p2i链式结构链式结构什么是指针什么是指针 begin begin new(p1);p1:=100; new(p1);p1:=100; new(p2);p2:=200; new(p2);p2:=200; p1:=p2; p1:=p2; end. end.30103011402040214022402340243011p14024p24024p1

8、 (1) (1) 同一基类型的指针变量可以互相赋值。同一基类型的指针变量可以互相赋值。链式结构链式结构指针变量的基本操作指针变量的基本操作(2)(2)指针变量指针变量p1p1置空置空 （nilnil）当希望某个指针变量不指向任何存贮空间时，可以当希望某个指针变量不指向任何存贮空间时，可以赋值为空即赋值为空即 NIL NIL 。(3)对指针变量可以进行关系运算对指针变量可以进行关系运算 如如:if P1P2 then 语句语句1 else 语句语句2; while P3 NIL do . . end; 关系运算的结果关系运算的结果,仍是仍是 FALSE , TRUE 。链式结构链式结构指针变量的

9、基本操作指针变量的基本操作Type pppp= stu ; stu= record name : string10 ; number : integer ; next:pppp； end; var p1, p2 : pppp链式结构链式结构数据元素的定义数据元素的定义p2.numberp2.numberp2.nextp2.next元素元素2 2元素元素1 1元素元素3 3 元素元素4 41345h

10、ead140015361346140015361346将独立的多个存储单元连接在一起，形成了一个将独立的多个存储单元连接在一起，形成了一个“链链”，链中每一个单元称为链中每一个单元称为“链链”中的一个中的一个“数据元素数据元素”。我。我们将它们通过指针域连在一起形成的链，称为线性链表。们将它们通过指针域连在一起形成的链，称为线性链表。 （1 1）查找结点）查找结点 （2 2）插入结点）插入结点 （3 3）删除结点）删除结点 链表的三种应用模式：链表的三种应用模式：线性链表线性链表查找查找(1)(1)设临时工作变量设临时工作变量p p指针指向链表的头结点指针指向链表的头结点( (头结点头结点的地

11、址不能丢失和改变，的地址不能丢失和改变，否则会丢失整个链表否则会丢失整个链表);); p:=head; p:=head;(2)while pnil do (2)while pnil do begin begin If x=p.data then 相关操作相关操作 p:=p.next;p:=p.next; end; end;n表头插入 n表中插入n表尾插入new(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=s；headpsnilx表头插入这两步操作这两步操

12、作顺序能颠倒顺序能颠倒吗？为什么？吗？为什么？将将s s结点插在结点插在p p结点之后结点之后线性链表线性链表插入插入三种情况：三种情况：想一想：表中插入结点如何实现？想一想：表中插入结点如何实现？new(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=sn表头插入 n表中插入n表尾插入 new(s);readln new(s);readln(x);s.data:=x;s.next:=p.next; p.next:=s(x);s.data:=x;s.next

13、:=p.next; p.next:=sheadpsnilx表中插入将将s s结点插在结点插在p p结点之后结点之后线性链表线性链表插入插入 表尾插入结点又如何实现呢？表尾插入结点又如何实现呢？nil new(s);readln new(s);readln(x);s.data:=x;s.next:=p.next;p.next:=s(x);s.data:=x;s.next:=p.next;p.next:=snew(s);readlnnew(s);readln(x);s.data:=x; s.next:=head; head:=s(x);s.data:=x; s.next:=head; head:=

14、s将将s s结点插在结点插在p p结点之后结点之后n表头插入 n表中插入n表尾插入 new(s);readln new(s);readln(x);s.data:=x;s.next:=nil; p.next:=s(x);s.data:=x;s.next:=nil; p.next:=sheadpsx表尾插入nil线性链表线性链表插入插入表头删除：表头删除：表中删除：表中删除：表尾删除：表尾删除：p:=head;r:=p.next;p.next:=r.next; dispose(r);表头删除表头删除headnilrp三种情况：三种情况：删除删除p结点后的结点后的r结点结点线性链表线性链表删除删除表

15、头删除：表头删除：表中删除：表中删除：表尾删除：表尾删除：p:=head;r:=p.next;p.next:=r.next; dispose(r);r:=p.next;p.next:=r.next; dispose(r);表中删除表中删除headnilrp线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点表头删除：表头删除：表中删除：表中删除：表尾删除：表尾删除：p:=head;r:=p.next;p.next:=r.next;dispose(r);r:=p.next;p.next:=r.next; dispose(r);r:=p.next;p.next:=nil; dispose(

16、r);表尾删除表尾删除headnilrpnil线性链表线性链表删除删除删除删除p结点后的结点后的r结点结点（1 1）怎样建立链表？怎样建立链表？（2 2）应该注意什么？）应该注意什么？讨论：讨论：输入一个正整数序列输入一个正整数序列, ,遇遇0 0时停止，按输入数据的时停止，按输入数据的顺序建立如下链表顺序建立如下链表: :（从表头插入结点）（从表头插入结点） （1 1）初始化）初始化（2 2）申请一个结点并赋值，然后将结点插入表头）申请一个结点并赋值，然后将结点插入表头（3 3）重复（）重复（2 2），直到输入的值为等于），直到输入的值为等于0 0结束。结束。分析：分析：实战演练实战演练 r

17、eadln(n) ; head:=nil; while n 0 do插入表头插入表头,形成链表形成链表 begin new ( p ) ; p.data:=n; p.next:=head; head:= p ; read ( n ) ; end ; 参考程序：参考程序：讨论讨论（1）这样插入的链表有什么特点？）这样插入的链表有什么特点？（2）可以用表尾插入来改变链表）可以用表尾插入来改变链表结点的顺序吗？程序怎样完成？结点的顺序吗？程序怎样完成？ head:=nil; read(x); while x0 do begin if head=nil then begin new(p); p.dat

18、a:=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线性链表应用的三种模式：线性链表应用的三种模式： （1）数据元素的查找数据元素的查找 （2）数据元素的插入数据元素的插入 （3）数据元素的删除。数据元素的删除。线性链表的访问基本方法是：线性链表的访问基本方法是：（1 1）从头结点开始沿线性链表方向进行探求，一）从头结点开始沿线性链表方向进行探求，一般用于指向刚查过的结点地址，另一个用于指向下般用于指向刚查过的结点

19、地址，另一个用于指向下一个待查的结点地址。一个待查的结点地址。（2 2）结束访问的条件有两个：一个是结点地址为）结束访问的条件有两个：一个是结点地址为Nil,Nil,另一个是找到了相应的结点。另一个是找到了相应的结点。容易出错的是：当容易出错的是：当p p为为nilnil时，取时，取p.datap.data时出错，因为时出错，因为p p是是nilnil，p.datap.data的值无意义。的值无意义。 空间空间分配分配静态分配。程序执行前静态分配。程序执行前须确定存储规模。估计须确定存储规模。估计过大造成空间浪费，估过大造成空间浪费，估计太小使空间溢出机会计太小使空间溢出机会增多。增多。 动态

20、分配动态分配, ,只要内存空间尚有空只要内存空间尚有空闲，就不会产生溢出。当线性表闲，就不会产生溢出。当线性表的长度变化较大，难以估计存储的长度变化较大，难以估计存储规模时，宜采用动态链表作存储规模时，宜采用动态链表作存储结构为好结构为好。 时间时间存取存取随机存取结构，查找方随机存取结构，查找方便，但插入和删除操作便，但插入和删除操作很费时。很费时。顺序存取结构，链表中的结点，顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取需从头指针起顺着链扫描才能取得。得。 插入插入删除删除操作操作在顺序表中进行插入和在顺序表中进行插入和删除，平均要移动表中删除，平均要移动表中近一半的结点，尤其是

21、近一半的结点，尤其是当每个结点的信息量较当每个结点的信息量较大时，移动结点的时间大时，移动结点的时间开销就相当可观。开销就相当可观。 在链表进行插入和删除，只需要在链表进行插入和删除，只需要修改指针。对于频繁进行插入和修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存删除的线性表，宜采用链表做存储结构。若表的插入和删除主要储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。指针表示的单循环链表为宜。 实战演练：线性链表的归并运算：实战演练：线性链表的归并运算：将下列两个有序线性表进行归并。将下列两个有序线性表进行归并。线性表（线性

22、表（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）当两个线性）当两个线性

23、链链表中有一个已归并完毕，则另一个线表中有一个已归并完毕，则另一个线性性链链表的剩余部分全部复制到所建立的新线性表的剩余部分全部复制到所建立的新线性链链表中。表中。（3 3）如果出现同值时，则选一个值。）如果出现同值时，则选一个值。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)当前结点加到新链表中当前结点加

24、到新链表中,p1,p1指针后移指针后移; ; else else 将链表将链表(1)(1)当前结点加到新链表中当前结点加到新链表中,p2,p2指针后移指针后移; ; end; end;if p1nil then if p1nil then 将链表将链表(1)(1)剩余的结点连接到新表的后面剩余的结点连接到新表的后面; ;if p1nil then if p1nil then 将链表将链表(1)(1)剩余结点连到新表的后面剩余结点连到新表的后面; ;归并算法：归并算法：procedure combine(varprocedure combine(var head3:point;head1,hea

25、d2:point); head3:point;head1,head2:point); var var p1,p2,q,r:point; p1,p2,q,r:point; 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 n

26、ew(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 th

27、en r.next:=p1; if p1nil then r.next:=p1; if p2nil then r.next:=p2; if p2nil then r.next:=p2; end; end;本算法在构建链表本算法在构建链表3 3时申请了新结点，能否时申请了新结点，能否不申请新结点来实现线性链表的归并？不申请新结点来实现线性链表的归并？想一想：想一想： 小结：小结： （1 1）单向线性链表只能向后遍历，不能向前，）单向线性链表只能向后遍历，不能向前，不能随机访问任一元素。不能随机访问任一元素。 （2 2）表头结点很重要，如果表头结点丢失，）表头结点很重要，如果表头结点丢失，则线性链

28、表将无法找回。则线性链表将无法找回。（3 3）在进行插入和删除结点的操作时，不需要）在进行插入和删除结点的操作时，不需要移动大量的数据，但是要注意不能断链。移动大量的数据，但是要注意不能断链。不带附加不带附加头结点的头结点的链表链表heada1 a2 a3 a4a1 a2 a3 a4带附加头结带附加头结点的链表点的链表线性链表的几种形式：线性链表的几种形式： 其特点如下：其特点如下：单向链表、双向链表、循环链表单向链表、双向链表、循环链表单循环链表双循环链表双向链表双向链表双链表的操作与单链表基本一致：双链表的操作与单链表基本一致：123412type type point=node; poi

29、nt=node; node=record node=record data:datatype data:datatype; ; pre,next:point; pre,next:point; end; end;（1）每个结点有两个指针）每个结点有两个指针域，一个指向其前驱结点，域，一个指向其前驱结点，一个指向其后继结点。一个指向其后继结点。（2）从任一结点出发可以）从任一结点出发可以访问其他结点。访问其他结点。 便于访问、插入和删除。便于访问、插入和删除。 （1 1） 尾结点指向第一个结点；尾结点指向第一个结点；（2 2）从表中任一个结点出发可以找到链表中的其他结点。）从表中任一个结点出发可以

30、找到链表中的其他结点。（3 3）遍历操作的结束条件是：）遍历操作的结束条件是：（4 4）其他操作与单链表一样。）其他操作与单链表一样。循环链表循环链表注意：注意：带附加头结点带附加头结点 p=head.nextp=head.next不带附加头结点不带附加头结点p=headp=head双向循环链表：最后一个结点的指针指向头结点，双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：且头结点的前趋指向最后一个结点。如下图： 问题描述：设有问题描述：设有n n个人围成一圈，并按顺个人围成一圈，并按顺时针方向从时针方向从1 1到到n n编号；从第编号；从第s s个人开始进

31、个人开始进行行1 1到到m m报数，数到报数，数到m m的人出圈；接着再从的人出圈；接着再从他后面一个人重新开始他后面一个人重新开始1 1到到m m报数，直到报数，直到所有人出圈为止。输出出圈人的次序。所有人出圈为止。输出出圈人的次序。例例2约瑟夫问题。约瑟夫问题。分析分析: :(1) N (1) N 个人按序号围坐一圈，即第个人按序号围坐一圈，即第 1 1 个人后是第个人后是第 2 2 个人个人.第第N N 个人的后继是第个人的后继是第 1 1 个人个人, ,形成循环形成循环链表的结构，链表的结构， 所以可采用循环链表表示这所以可采用循环链表表示这 N N 个人个人; ;(2) (2) 每一

32、个结点有两个域每一个结点有两个域: : 数据域数据域人的编号人的编号, , 指针域指针域指向下一个人的地址指向下一个人的地址; ;(3) (3) 报数报数 : : 即数人个数即数人个数, , 每当数到每当数到 M M 时时, , 则该号则该号人走出圈内人走出圈内删除该结点删除该结点, , 输出人编号输出人编号 ; ; (4) (4) 重复重复 (3)(3)过程过程, , 直到只有一个人为止。直到只有一个人为止。例2约瑟夫问题。数据结构：数据结构： type pointman ; manrecord num : integer ; next : point ; end ; var head ,

33、p , q : point ; n , m : integer ; 建立循环链表建立循环链表Procedure creat(var head:point); var p,q:point; 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;Procedure select(var head:point); var （选举大王的过程）（选举大王的过程） p,q:point;

34、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例例3 营业额统计营业额统计给定给定N（1N32767）天的营业额）天的营业额a1,a2,an. 定义一天的最小波动值等于定义一天的最小波动值等于 min|该天以前某一天的营业额该天以前某一天的营业额-该天营业额该天营业额|特别地，第一天的最小波动值即为特别地，第一天