




已阅读5页,还剩44页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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个洞,一只兔子和一只狐 狸各住一个洞,狐狸总想吃掉兔子。一天兔子 对狐狸说,你想吃我有一个条件,第一次隔一 个洞找我,第二次隔两个洞找我,以后依此类 推,次数不限。若能找
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 如何设计轻质普通型铝合金轮椅项目可行性研究报告技术工艺+设备选型+
- 中国卷铝涂料项目商业计划书
- 2024年成都彭州市事业单位招聘真题
- 培训营协议书
- 船艇考试题库及答案
- 初中中药考试题型及答案
- 急诊骨科考试试题及答案
- 起诉离婚协议书离婚
- 2025年合同执行保障金
- 汽车指标租赁协议书
- 恩度的不良反应及注意事项
- GB/T 10599-2023多绳摩擦式提升机
- 第2课春秋战国的历史巨变【中职专用】《中国历史》(高教版2023基础模块)
- 护理思政课课件
- 智能制造中的云计算与大数据分析技术
- 文华财经“麦语言”函数手册
- 【历年真题】2019年10月00688设计概论自考试卷(含答案)
- 硅营养作用与作物抗逆
- 工程联系单格式
- 大中小学思政课内容一体化研究
- 长沙150米超甲级写字楼成本测算20121210
评论
0/150
提交评论