信息管理与信息系统专业数据结构实验指导书实验一线性表的.doc

北京邮电大学远程教育信息管理与信息系统专业数据结构实验指导书实验一 线性表的插入和删除一、 实验目的1、 掌握使用Turbo Pascal上机调试线性表的基本方法；2、 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、 实验要求1、 认真阅读和掌握本实验的程序。2、 上机运行本程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、 实验内容程序1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找。程序如下：PROGRAM seqlist(input,output);线性表可能达到的最大长度CONST maxlen = 1024;TYPE elemtp = integer;线性表的顺序存储结构TYPE seqlisttp = RECORD用一维数组来描述线性表的顺序存储结构elem: ARRAY1.maxlen OF elemtp;定义子界类型last，它的取值范围是0到maxlenlast: 0.maxlen 线性表长度 END;初始化线性表PROCEDURE initlist(VAR v:seqlisttp; ml:integer);BEGINv.last:=0;END;向线性表的第i个元素之前插入一个元素xPROCEDURE insertlist(VAR v:seqlisttp; i:integer; b:elemtp);VAR j:integer;BEGINIF (iv.last+1)THEN writeln(error!)ELSE IF v.last=maxlenTHEN writeln(overflow)ELSE BEGINFOR j:=v.last DOWNTO i DOv.elemj+1:=v.elemj;v.elemi:=b;v.last:=v.last+1; END;END;从线性表中删除第i个位置的元素PROCEDURE deletelist(VAR v:seqlisttp; i:integer);VAR j:integer;BEGINIF (iv.last+1)THEN writeln(error!)ELSE IF v.last=maxlenTHEN writeln(overflow)ELSE BEGINFOR j:=i+1 TO v.last DOv.elemj-1:=v.elemj;v.last:=v.last-1; END;END;从线性表中查找元素FUNCTION findlist(v:seqlisttp; x:elemtp):integer;VAR i:integer;BEGINi:=1;WHILE (i=v.last) AND (v.elemix) DOi:=i+1;IF i0 THEN writeln(The location of first ,x, is ,k)ELSE writeln(not found);writeln(a.last);END.实验二 单链表操作一、 实验目的1 掌握握单链表的基本操作：插入、删除、查找等运算。二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下：PROGRAM linklist(input,output);TYPE elemtp = char;单链表中结点的类型TYPEpointer=node;node=RECORDdata:elemtp;next:pointer; END;头插法建表,先进后出PROCEDURE createlistf(VAR v:pointer);VAR ch:elemtp;head:pointer; 头指针p:pointer; 工作指针BEGINhead:=NIL;write(Please input chars: );read(ch); 上一条语句会输出一个换行符，我们先把它读出来，丢掉 read(ch);WHILE (ord(ch)13) DOBEGINnew(p);p.data:=ch;p.next:=head;head:=p;read(ch);END;v:=head;END;尾插法建表,先进先出PROCEDURE createlistr(VAR v:pointer);VAR ch:elemtp;head:pointer; 头指针last:pointer; 尾指针p:pointer; 工作指针BEGINhead:=NIL;last:=NIL;write(Please input chars: );read(ch); read(ch);WHILE (ord(ch)13) DOBEGINnew(p);p.data:=ch;IF head=NIL THEN head:=pELSE last.next:=p;last:=p; read(ch);END;IF lastNIL THENlast.next:=NIL;v:=head;END;按序号查找操作PROCEDURE getnode(v:pointer; VAR listnode:pointer; i:integer);VARp:pointer;j:integer;BEGINp:=v; j:=1;WHILE (p.nextNIL) AND (ji) DOBEGINp:=p.next;j:=j+1;END;IF j=i THEN listnode:=pELSE listnode:=NIL;END;插入操作，在第i个元素之后插入x,i大于等于0PROCEDURE insertlist(VAR v:pointer; x:elemtp; i:integer);VAR p,s:pointer; 工作指针j:integer;BEGINnew(p);p.data:=x;IF i=0 THEN 如果i=0，则把p结点插入表头BEGINp.next:=v;v:=pENDELSE BEGINgetnode(v,s,i); 返回第i个结点的指针IF sNIL THENBEGINp.next:=s.next;s.next:=p;ENDELSE writeln(not found); END;END;删除操作，删除第i个结点,i大于等于1PROCEDURE deletelist(VAR v:pointer; i:integer);VAR p:pointer; 工作指针BEGIN IF vNIL THENBEGIN IF i=1 THEN 如果i=1，则删除头结点 v:=v.next ELSE BEGIN getnode(v,p,i-1); 返回第i-1个结点的指针 IF pNIL THEN p.next:=p.next.next ELSE writeln(erroe); END;END ELSE writeln(The list is null.);END;遍历单链表PROCEDURE traverlist(v:pointer);VARp:pointer;BEGINp:=v;WHILE (pNIL)DOBEGINwrite(p.data, );p:=p.next;END;END;建立线性表VARla,lb:pointer;listnode:pointer;c:elemtp;m:integer;BEGINcreatelistf(la);writeln(la.data);createlistr(lb);writeln(lb.data);getnode(la,listnode,3);IF listnodeNIL THEN writeln(listnode.data)ELSE writeln(null);traverlist(la); writeln();traverlist(lb); writeln();writeln(Input a char and an integer:);read(c); read(c,m);insertlist(la,c,m);traverlist(la);writeln();deletelist(lb,3); traverlist(lb);END.实验三 二叉树操作一、 实验目的1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1： 按先序次序输入二叉树中结点的值（一个字符），0表示空树，生成二叉树的二叉链表存储结构， bt为指向根结点的指针。然后按层次顺序遍历二叉树。算法思想：本算法采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，遍将右子树根结点入队列，直到队列空为止。因为队列是先进先出，从而达到按层次顺序遍历二叉树的目的。程序如下：PROGRAM btreed(input,output);CONSTM = 100;TYPE elemtp = char;二叉树的链式存储结构TYPEbtree = node;node = RECORD data:elemtp; lchild,rchild:btree; END;TYPEvector=ARRAY0.M OF btree;生成二叉树 VARroot:btree;que:vector;front,rear:integer;PROCEDURE create(VAR bt:btree);VAR x:elemtp;BEGINread(x);IF (ord(x)=48) THEN bt:=NILELSE BEGIN new(bt); bt.data:=x; 建根结点 create(bt.lchild); 建左子树 create(bt.rchild); 建右子树 END;END;PROCEDURE inorder(bt:btree);BEGINIF btNIL THENBEGINinorder(bt.lchild);write(bt.data, );inorder(bt.rchild);END;END;PROCEDURE enqueue(bt:btree);BEGINIF front(rear+1) MOD M) THENBEGINrear:=(rear+1) MOD M);querear:=bt;END;END;PROCEDURE delqueue(VAR bt:btree);BEGINIF front=rear THEN bt:=NILELSEBEGINfront:=(front+1) MOD M);bt:=quefront;END;END;PROCEDURE levorder(bt:btree);VAR p:btree;BEGIN IF btNIL THENBEGIN enqueue(bt); WHILE frontrear DO BEGIN delqueue(p); write(p.data, ); IF p.lchildNIL THEN enqueue(p.lchild); IF p.rchildNIL THEN enqueue(p.rchild); END;END;END;主程序BEGINwriteln(Please input the tree: );create(root);inorder(root);writeln();front:=0;rear:=0;levorder(root);END.实验四 图的操作一 实验目的1 掌握图的基本存储方法。2 掌握有关图的操作算法并用高级语言编程实现；3 熟练掌握图的两种搜索路径的遍历方法。二 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三 实验内容以邻接矩阵和邻接表的方式存储连通图。然后分别用优先深度算法遍历邻接居真方式存储的图和邻接表方式存储的图。这里假设图只有4个顶点，在实验的时候可以根据需要更改vtxnum的值。程序如下：PROGRAM graphd(input,output); CONST edge边,vertex顶点,digraph向，weight权 vtxnum=4; 图中顶点数 k1=0; 是否有向，0为无，非0为有 k2=0; 是否有权，0为无，非0为有 maxvalue=10000; 定义无穷大 TYPE elemtp=integer; TYPE bool=ARRAY0.vtxnum OF boolean; 邻接矩阵存储无向无权图 TYPE vtxptr=1.vtxnum; bit=0.1; TYPE vertex=RECORD data:elemtp; 顶点信息 END; TYPE arc=RECORD adj:bit; 表示两个顶点之间是否存在关系 END; TYPE graph=RECORD vexs: ARRAYvtxptr OF vertex; arcs: ARRAYvtxptr,vtxptr OF arc; END; 邻接表存储无向无权图 TYPE edgeptr=edgenode; edgenode=RECORD adjvex:1.vtxnum; next:edgeptr; END; vexnode=RECORD data:elemtp; link:edgeptr; END; adjlist=ARRAY1.vtxnum OF vexnode; PROCEDURE create(VAR ga:graph); 用邻接矩阵建立无向无权图VAR n,e:integer; i,j,k:integer;BEGIN n:=vtxnum; write(input value:); FOR i:=1 TO n DO read(ga.vexsi.data); 输入n个顶点的信息 FOR i:=1 TO n DOFOR j:=1 TO n DO ga.arcsi,j.adj:=0; write(Please input the sum of arcs:); read(e); FOR k:=1 TO e DO BEGIN writeln(input two vertexs:); read(i,j); 输入一条无向无权的边的两个顶点的序号 ga.arcsi,j.adj:=1; ga.arcsj,i.adj:=1 END; FOR i:=1 TO n DO write(ga.vexsi.data, ); writeln(); FOR i:=1 TO n DO BEGIN FOR j:=1 TO n DO write(ga.arcsi,j.adj, ); writeln();END;END; 优先深度算法遍历图,邻接矩阵 PROCEDURE dfsmatrix(ga:graph;VAR visited:bool;i,n:integer); VAR j:integer; BEGIN write(i, ); write(ga.vexsi.data,; ); visitedi:=true; FOR j:=1 TO n DO BEGIN IF (ji) AND (ga.arcsi,j.adj0) AND (visitedjtrue) THEN dfsmatrix(ga,visited,j,n); END; END; 初始化邻接表 PROCEDURE initgadjoin(VAR ga:adjlist;n:integer); VAR j:integer; BEGIN FOR j:=1 TO n DO BEGIN gaj.link:=NIL; write(input value:); read(gaj.data); END; FOR j:=1 TO n DO BEGIN writeln(gaj.data); END; END; PROCEDURE createadjoin(VAR ga:adjlist;n:integer); 用邻接矩阵建立无向无权图 VAR e:integer; i,j,k:integer; p,q:edgeptr; BEGIN write(Please input the num of edges:); read(e); FOR k:=1 TO e DO BEGIN writeln(input two vertexs:); read(i,j); 输入一条无向无权的边的两个顶点的序号 向序号为i的单链表的表头插入一个边结点 new(p); p.adjvex:=j; p.next:=gai.link; gai.link:=p; 向序号为j的单链表的表头插入一个边结点 new(q); q.adjvex:=i; q.next:=gaj.link; gaj.link:=q; END; END; 优先深度算法遍历图，邻接表 PROCEDURE dfsadjoin(ga:adjlist;VAR visited:bool;i,n:integer); VAR j:integer; p:edgeptr; BEGIN write(i, ); write(gai.data,; ); visitedi:=true; p:=gai.link; WHILE pNIL DO BEGIN j:=p.adjvex; IF (visitedjtrue) THEN dfsadjoin(ga,visited,j,n); p:=p.next; END; END; VAR myga:graph; myvisited:bool; i:integer; gl:adjlist; BEGIN create(myga); 用邻接矩阵建立无向无权图 邻接矩阵，优先深度算法遍历图 FOR i:=1 TO vtxnum DO myvisitedi:=false; dfsmatrix(myga,myvisited,1,vtxnum); 用邻接表建立无向无权图 initgadjoin(gl,vtxnum); IF gl1.link=NIL THEN write(null) ELSE write(not null); createadjoin(gl,vtxnum); 邻接表，优先深度算法遍历图 FOR i:=1 TO vtxnum DO myvisitedi:=false; dfsadjoin(gl,myvisited,1,vtxnum); END.袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀