线性表及应用ppt课件

2010/3/4南京树人国际学校09初一信息奥赛 线性链表及应用 单双向链表、有序链表 循环链表、线性表的应用 一、顺序表中结点ai 的存储地址 假设表中每个结点占用c个存储单元，其中开 始结点a1的存储地址（简称为基地址）是LOC （a1），那么结点ai的存储地址 LOC（ai）为： LOC（ai）= LOC（a1）+（i-1）*c 1in 二、线性表的链接存储 o1、单向线性链表 o2、有序链表 o3、双向线性链表 o4、循环链表 read(ch); head:=nil; while ch# do begin new(p); p.data:=ch; p.next:=nil; if head=nil then begin head:=p; q:=p; end else begin q.next:=p; q:=p; end; read(ch); end; 2、用表尾插入法建立链表 3、单链表的遍历与输出 PROCEDURE print ( head : point ) ; 带带表头头指针针 var p : point ; BEGIN p := head while p nil do begin write ( p.data : 8 ) ; p := p.next ; end ; end; 打印链表的过程 4、线性表的查找算法 oProcedure search( head :point, ch:char ); oVar p:point ; oBegin o p:=head; while (pch) do p:=p.next; if pnil) and ( chp.data) do 查找位置 begin q:=p ; p:=p.next ; end; 表尾 If p=nil then q.next:=s Else if p=head then 插入表头： Begin S.next :=head; head:=s ; end; else 插入表内 begin s.next:=q.next ;q.next :=s ; q:=q.next ; end ; end ; 6、单链表的删除 o前提：删除p结点后的r结点 o表头删除： o表中删除： o表尾删除： head.next:=p.next; dispose(p); q.next:=p.next; dispose(p); q.next:=nil; dispose(p); 删除操作 ： 删除头结点 删除某一个结点 P：=head ; q.next := p.next ; Head:=head.next; dispose ( p ) ; Dispose (p); PROCEDURE dele ( var head :point ; ch:char ) ; var p , q : point ; BEGIN p := head ; q := p ; while ( p.data ch ) and ( p p.data ) and ( phead do begin write(p.da:5); p:=p.next; end; end; 例题1 建立一个若干个学生姓名的循环链接表，并 输出，完成以下功能： （1）建立按字典顺序排列的顺序链表，并输出 （2）输入一个学生姓名，若该学生姓名在链表中， 则删除该结点，若不在链接表中，则插入该学生姓 名，并使其仍然有序。 （3）要有判断链表为空的功能 问题分析： （1）建立循环链表的过程，其实质是不断插入结点的 过程，所以首先建立一个头结点，不断插入结点。 （2）在插入结点的过程中，需要判断插入结点的定位 问题。总是从表头的下一个结点开始搜索位置。 （3）删除结点的过程，需要寻找删除结点位置（用两 个指针变量完成），当找到删除结点，则进行删除否 则插入该结点。 （4）打印循环线性表的过程：从头结点的下一个结点 开始输出. program xunhuanlianbiao; type point=stu; stu= record da:string8 ; link: point ; end; var head,p,q : point ; st1:string8; len,x: integer ; procedure print( head1:point); var p:point ; begin p:=head1.link ; while phead1) and (p.dahead1) and (p.da# do begin inser1(head,st1); readln(st1); end; print(head); repeat write(please input 1-3 ); readln(x); case x of 1: begin readln(st1);inser1(head,st1);print(head); end; 2: begin readln(st1);dele(head,st1);print(head);end; end; until x=3 ; end. 例题2、猴子选大王 o链表实现： 教材“数据结构及应用”p 22 牵涉知识：建立循环链表，结点计数及删除结点 操作 type point=node; node=record data:integer; next:point; end; var m,n,s:integer;p,q,head:point; begin readln(m,n); new(head);q:=head;head.data:=1; for s:=2 to m do begin new(p);p.data:=s;q.next:=p;q:=p; end; q.next:=head; s:=1;q:=head; if n=1 then writeln(m) else begin repeat p:=q.next; s:=s+1; if s mod n=0 then begin q.next:=p.next; dispose(p); end else q:=p; until q.next=q; write(q.data); end; end. 例题3 有两个多项式Y1、Y2编写一个程序，将两个多项 式合并同类项。 Y1= 3x7+5x6-4x5-3x2-8x-2 Y2=9x12-6x8-5x7-5x6+x4-8x3+6x2+7x+3 问题分析： （1）多项式合并同类项的方法，系数相加减，指数不变 。 （2）多项式的每一项的表示方法可以有两种： 用记录数组 ： A1.cof ,A1.exp 用指针变量表示每一个结点：指针类型指向一个记录 ，其结构为： 系数域、指数域、指向下一项的地址域 此时选择数据的结构为线性链接表的结构处理该问题比较 方便。教材p23 （3）建立两个多项式的线性链表（按降幂排列L1，L2） （4）每个线性表有头指针、过渡指针等（head,p,q) （5）分别从两个表头开始，找到第一个插入点（指数最 高的那个结点，将该结点插入到表L的第一个结点。 指数相同，指数不变，系数相加减 指数不同，将指数高的结点先插入表L中，指针向下移 最后不论哪个链表插入先结束，则将另一链表，接入 尾部。 指数域系数域地址域 program exp2_1 ; 用数组完成多项式合并同类项 const max=100 ; type number =record coef :integer ; exp : 0100 ; arr= array1max of number ; var S,R,A :arr ; n,m,j,k , x,y : integer ; Procedure input ( var h: arr; t:integer ); Var k,j :integer ; Begin For k:=1 to t do Read(hk.coef, hk.exp); Write(y=); For k:=1 to t do begin If ( hk.coef0 ) and (k1) then write(+) Write( hk.coef,X, hk.exp, ) ; End; Writeln ; End; Begin 主程序 Write( input number n, m : ); Read(n,m)；Writeln; Input( S,n ); input (R,m ); x:=1 ; y:=1; k:=1 ; while (x0 then begin ak.exp:=sx.exp; ak.coef:=j; x:=x+1 ; y:=y+1 ; k:=k+1 ; end else begin x:=x+1; y:=y+1 ; end ; end else if sx.expry.exp then begin ak.exp:=sx.exp; ak.coef:=sx.coef ; x:=x+1 ; k:=k+1 ; end else begin ak.exp:=ry.exp; ak.coef:=ry.coef ; y:=y+1 ; k:=k+1 ; end ; end; while ( x m) do begin ak.exp:=sx.exp; ak.coef:=sx.coef ; x:=x+1 ; k:=k+1 ; end; while ( yn) do begin ak.exp:=ry.exp; ak.coef:=ry.coef ; y:=y+1 ; k:=k+1 ; end; write( y3=); 输出合并同类项以后的多项式 for j:=1 to k-1 do begin If ( Aj.coef0 ) and (j1) then write(+); Write(Aj.coef, X, Aj.exp, ) ; end; Writeln ; End. 1、双（向）链表中有两条方向不同的链，即每 个结点中除next域存放后继结点地址外，还增 加一个指向其直接前趋的指针域front。 2、双向链表的结点结构和形式描述 3、双向链表的前插和删除本结点操作 双向链表双向链表 双向链表类型定义 Type point= stu ; stu=record num: integer ; Llink, Rlink : point ; end; var head, p,q : point ; x: integer ; procedur print ( head1:point); var p:point ; begin p:=head1 ; while p0 do begin new(p) ; p.num:=x; p.Llink :=nil；p.rlink := nil; if head1=nil then being head1:=p ; q:=p; end else begin q.rlink:= p ; p.Llink :=q ; q:=q.rlink ; end; read(x); end; r: = p ; print( head1); end; Procedure dele( var head1 :point ; x : integer) ; var p,q : point ; begin p:=head1 ; q:=p ; while ( p.numnil) do p:=p.rlink ; if p=head1 then begin head1:= head1.rlink ;head1.Llink:=nil p:=head1 ; end else if pnil then begin p.Llink.rlink:=p.rlink; p.rlink.Llink:=p.Llink ; end else writeln( error) ; print( head1); End; begin head:=nil ; create( head ); writeln( input dele number x:); read( x); dele( head, x) ; end. 作业 1、将两个有序链表合并为一个有序链表。 表head1： （34，56，68，79，90，100） 表head2： （12，25，48，74，85） 算法1：建立一个新链表head3,通过大小比较选择 将值小的结点复制到head3，当有一个表已处理 完毕，则将另一表的顺序部分全部复制到head3 中。 如果不建立第三个链表，想一想程序该如何编辑 2、猴子选大王：有n只猴子，按顺时针方向 围成一圈选大王。从第一号开始报数 1,2,数到m时该猴子退出圈外，再如此 报数直到圈内只剩下一个猴子时，此猴子 便是大王。由键盘输入n,m，打印出走出圈 外的猴子序号及大王序号。 用循环链表完成 3、围绕着山顶有10个洞，一只兔子和一只狐 狸各住一个洞，狐狸总想吃掉兔子。一天兔子 对狐狸说，你想吃我有一个条件，第一次隔一 个洞找我，第二次隔两个洞找我，以后依此类 推，次数不限。若能找