【学习课件】第一讲线性表JSIO

1、2011年冬令营计算机的基本工作方式将编好的程序和原始数据，输入并存储在计算机的内存储器中（即“存储程序”）；计算机按照程序逐条取出指令加以分析，并执行指令规定的操作（即“程序控制”）。这一原理称为存贮程序和程序控制,是现代计算机的基本工作方式。程序是计算机的灵魂什么是数据结构（data structure）什么是算法（algorithm）程序=数据结构+算法是数据在计算机中的组织方式及相应的基本访问操作。是解决问题的方法（数据处理）或者步骤程序是什么？线性表图书馆书目表数据元素计算机和人对奕问题树.网络布线图三种基本数据结构线性结构数据元素之间存在一对一的线性关系树形结构数据元素之间存在一对

2、多的层次关系图状结构数据元素之间存在多对多的网状关系顺序存储结构链式存储结构数据在计算机中如何存储？元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储M：每个元素占用的存储单元元素2元素1元素3 元素4 链式存储 head1345140015361346140015361346 数据的逻辑结构 数据的存储结构 数据结构的基本运算：查找、插入、删除 线性结构 顺序存储 链式存储 树形结构图形结构小结：数据结构的三个方面： 快过新年了，小L又要设计和大J玩的扑克牌游戏了。大J比较相信运气的说法，想让小L设计

3、一种玩法测测明年的运气，当然没什么科学性，纯属娱乐。游戏规则如下： 小L和大J各准备一副牌(去掉大小王)并相互交换洗好牌，将牌背面朝上各放成一排，小L翻开大J从左向右数的第n张牌，如果牌面数为奇数a，小L将大J的第n张开始的a张牌取出按原次序依次放在自己的牌的最右边；如果牌面数为偶数b，则将自己从左边向右数的b张牌取出按原序放到大J的牌的最左边。然后大J也做同样的操作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。链式结构什么是指针 指针是以存储单元的地址作为其值的一种数据类型。 100 p1p134F234F2定义方式：Type 指针类型标

4、识符=类型标识符； var 指针变量名：指针类型标识符；new（p1） 向计算机申请内存地址 链式结构如何申请、释放存储单元 p1p134F234F2type p=integer;var p1:p;p1:=200给p1指向的单元赋值dispose(p1) 释放存储单元200 p1:integer;arrp = array1.10 of real；Type p=integer; arr=array1.4 of char; arrp = arr; Var p1:p; p2:arrp;指针变量所指向的类型不同，计算机所给予的存储单元的多少也不相同。指针类型定义中的基类型只能是类型标识符，不能是具体的

5、类型定义。 p1p1 p2p2i链式结构什么是指针 begin new(p1);p1:=100; new(p2);p2:=200; p1:=p2; end.30103011402040214022402340243011p11004024p22004024p1 (1) 同一基类型的指针变量可以互相赋值。链式结构指针变量的基本操作(2)指针变量p1置空 （nil）p1:=nil当希望某个指针变量不指向任何存贮空间时，可以赋值为空即 NIL 。(3)对指针变量可以进行关系运算 如:if P1P2 then 语句1 else 语句2; while P3 NIL do . . end; 关系运算的结果

6、,仍是 FALSE , TRUE 。链式结构指针变量的基本操作Type p= stu ; stu= record name : string10 ; number : integer ; next:p； end; var p1, p2 : p链式结构数据元素的定义p2.numberp2.next游戏规则如下： 小L和大J各准备一副牌(去掉大小王)并相互交换洗好牌，将牌背面朝上各放成一排，小L翻开大J从左向右数的第n张牌，如果牌面数为奇数a，小L将大J的第n张开始的a张牌取出按原次序依次放在自己的

7、牌的最右边；如果牌面数为偶数b，则将自己从左边向右数的b张牌取出按原序放到大J的牌的最左边。然后大J也做同样的操作，两人轮流操作，谁最先将牌脱手，来年运气就特别好。为了增强神秘感，被翻开的牌放进去时仍保持背面朝上。例1：扑克游戏元素2元素1元素3 元素41345head140015361346140015361346将独立的多个存储单元连接在一起，形成了一个“链”，链中每一个单元称为“链”中的一个“数据元素”。我们将它们通过指针域连在一起形成的链，称为线性链表。 小L翻开大J从左向右数的第n张牌查找链表的第n个元素线性链表查找(1)设临时工作变量p指针指向链表的头结点(头结点的地址不能丢失和改

8、变，否则会丢失整个链表); p:=head;(2)x:=0; while xn do begin inc(x);p:=p.next; end; 小L将大J的第n张开始的a张牌取出链表元素的删除表中删除：r:=p.next;p.next:=r.next; dispose(r);表中删除headnilrp线性链表删除删除p结点后的r结点将自己从左边向右数的b张牌取出表头删除：p:=head;r:=p.next;p.next:=r.next; dispose(r);表头删除headnilrp三种情况：删除p结点后的r结点线性链表删除表尾删除：r:=p.next;p.next:=nil; dispos

9、e(r);表尾删除headnilrpnil线性链表删除删除p结点后的r结点按原次序依次放在自己的牌的最右边链表元素的插入 表尾插入结点又如何实现呢？nil将s结点插在p结点之后表尾插入 new(s);readln(x);s.data:=x;s.next:=nil; p.next:=sheadpsx表尾插入nil线性链表插入按原序放到大J的牌的最左边表头插入 new(s);readln(x);s.data:=x; s.next:=head; head:=s；headpsnilx表头插入这两步操作顺序能颠倒吗？为什么？想一想：将s结点插在p结点之后线性链表插入三种情况：想一想：表中插入结点如何实现

10、？ 表中插入 new(s);readln(x);s.data:=x;s.next:=p.next; p.next:=sheadpsnilx表中插入将s结点插在p结点之后线性链表插入线性链表应用的三种模式： （1）数据元素的查找 （2）数据元素的插入 （3）数据元素的删除。线性链表的访问基本方法是：（1）从头结点开始沿线性链表方向进行探求，一般用于指向刚查过的结点地址，另一个用于指向下一个待查的结点地址。（2）结束访问的条件有两个：一个是结点地址为Nil,另一个是找到了相应的结点。容易出错的是：当p为nil时，取p.data时出错，因为p是nil，p.data的值无意义。小结：输入一个正整数序列

11、,遇0时停止，按输入数据的顺序建立如下链表:（从表头插入结点） （1）初始化（2）申请一个结点并赋值，然后将结点插入表头（3）重复（2），直到输入的值为等于0结束。分析：实战演练 readln(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

12、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顺序表 链 表 空间分配静态分配。程序执行前须确定存储规模。估计过大造成空间浪费，估计太小使空间溢出机会增多。 动态分配,只要内存空间尚有空闲，就不会产生溢出。当线性表的长度变化较大，难以估计存储规模时，宜采用动态链表作存储结构为好。 时间存取随机存取结构，查找方便，但插入和删除操作很费时。顺序存取

13、结构，链表中的结点，需从头指针起顺着链扫描才能取得。 插入删除操作在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。 在链表进行插入和删除，只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 实战演练：线性链表的归并运算：将下列两个有序线性表进行归并。线性表（1）是：3，5，8，11，13线性表（2）是：1，4，5，9，15归并后的线性表为：1，3，4，5，8，9，11，13，15（1）线性链表中的结点是按数据域由小到大进行排列的，根据

14、两个线性链表中结点数据域的大小进行归并运算；哪个表中的数据小就归并哪一个；1、建立链表2、归并问题分析：（2）当两个线性链表中有一个已归并完毕，则另一个线性链表的剩余部分全部复制到所建立的新线性链表中。（3）如果出现同值时，则选一个值。p1:=head1;p2:=head2;while (p1nil) and (p2nil) do begin if p1.data=p2.data then 将链表(1)当前结点加到新链表中,p1指针后移; else 将链表(1)当前结点加到新链表中,p2指针后移; end;if p1nil then 将链表(1)剩余的结点连接到新表的后面;if p2nil t

15、hen 将链表(2)剩余结点连到新表的后面;归并算法：procedure combine(var head3:poi;head1,head2:poi); var p1,p2,q,r:poi; begin new(head3);r:=head3; p1:=head1;p2:=head2; while (p1nil) and (p2nil) do if p1.data=p2.data then begin new(q);r.next:=q;q.data:=p1.data; r:=q; p1:=p1.next; if p1.data=p2.data then p2:=p2.next; end els

16、e begin new(q);r.next:=q;q.data:=p2.data;r:=q; p2:=p2.next; end; if p1nil then r.next:=p1; if p2nil then r.next:=p2; end;本算法在构建链表3时申请了新结点，能否不申请新结点来实现线性链表的归并？想一想：procedure combine(var head3:poi;head1,head2:poi); var p1,p2,q,r:poi; begin p1:=head1;p2:=head2; while (p1nil) and (p2nil) do if p1.data=p2.

17、data then begin 操 作 1 end else begin 操 作 2 end; if p1nil then 操 作 3; if p2nil then 操 作 4; end;不带附加头结点的链表heada1 a2 a3 a4a1 a2 a3 a4带附加头结点的链表线性链表的几种形式： 其特点如下：单向链表、双向链表、循环链表单循环链表双循环链表 （1） 尾结点指向第一个结点；（2）从表中任一个结点出发可以找到链表中的其他结点。（3）遍历操作的结束条件是：（4）其他操作与单链表一样。循环链表注意：带附加头结点 p=head.next不带附加头结点p=head双向链表双链表的操作与单

18、链表基本一致：123412type poi=node; node=record data:datatype; pre,next:poi; end;（1）每个结点有两个指针域，一个指向其前驱结点，一个指向其后继结点。（2）从任一结点出发可以访问其他结点。 便于访问、插入和删除。双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图： 问题描述：设有n个人围成一圈，并按顺时针方向从1到n编号；从第s个人开始进行1到m报数，数到m的人出圈；接着再从他后面一个人重新开始1到m报数，直到所有人出圈为止。输出出圈人的次序。例2：约瑟夫问题。约瑟夫问题。分析:(1) N 个人按序

19、号围坐一圈，即第 1 个人后是第 2 个人.第N 个人的后继是第 1 个人,形成循环链表的结构， 所以可采用循环链表表示这 N 个人;(2) 每一个结点有两个域: 数据域人的编号, 指针域指向下一个人的地址;(3) 报数 : 即数人个数, 每当数到 M 时, 则该号人走出圈内删除该结点, 输出人编号 ; (4) 重复 (3)过程, 直到只有一个人为止。数据结构： type poiman ; manrecord num : integer ; next : poi ; end ; var head , p , q : poi ; n , m : integer ; 建立循环链表Procedure

20、 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;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 mo

21、d m = 0 then else q := p ; until p=p.next;（只剩一个结点）writeln ; head := p ; end ;（Q 为 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. 定义一天的最小波动值等于 mi

22、n|该天以前某一天的营业额-该天营业额|特别地，第一天的最小波动值即为a1 试求N天的最小波动值之和例如：N=3,a1=9,a2=3,a3=8，则各天最小波动值依次为9，6，1，和为16分析穷举：O(N2) 算法低效树基本数据结构能否在这里得到应用呢？没有高效地将数据组织起来，而是松散地存储在数组中，导致对于每一个营业额都需要检查前面所有的营业额。1、将这N个元素进行排序，得到序列c，同时 记录原来第i个元素在排序后的位置bi2、将排序后的序列在静态数组中建成一 个双向链表 3、按照从an到a1的顺序依次处理每个元素 算法分析双向链表3.1 对于an，查看bn的前驱prebn与后继nextbn

23、 所指的数3.2 最小波动值必然是an与这两个数中的某一个的差的绝对值3.3 处理完an后，我们把它从双向链表中删除，接着处理an-1动画演示938a:389c:312b:389最小波动值为min|8-3|,|8-9|=min6,1=139最小波动值为min|3-9|=6最小波动值为9最小波动值总和为1+6+9=16A: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,1、输入N，a1，a2，a3，an2、将a1，a2，a3，an按照从小到大的顺序排序，得到序列c1，c2，c3，cn，并记录下每个ai在新序列中的位置bi3、在新的序列上建立双向链表4、按照从an到