数据结构实验指导书.doc

《数据结构实验指导书.doc》由会员分享，可在线阅读，更多相关《数据结构实验指导书.doc（11页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导书原慧琳 编写东北大学秦皇岛分校二四年十二月前 言数据结构课程是信息管理与信息系统专业的一门专业平台课。它是数据库、计算机网络、软件工程等课程的先修课。这门课程要求学生不但要学会针对实际问题，快速的建立起数学模型，而且还要有效地解决实际问题，这是单独的课堂教学所无法达到的。课程的特点决定了学生必须加强实践，亲自输入算法、运行程序、输出结果，有了一定基础后，亲自进行算法设计。学中练、练中学，在模拟环境中学会用理论知识解决实际问题的能力。本实验指导书针对课程和学生的特点和时间安排，设计了三个试验，它们是：线性表的插入和删除、单链表的操作、栈和队列的操作。其中线性表的插入和删除、单链

2、表的操作是为了学生熟悉C+环境而设计，栈和队列的操作要求学生独立针对实际问题进行数学建模与算法设计。目 录实验一 线性表的插入和删除 4实验二 单链表的操作 7实验三 栈和队列 11实验一 线性表的插入和删除实验目的1. 掌握使用MinGW Developer上机调试线性表的基本方法；2. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。实验要求1. 认真阅读和掌握本实验的程序。2. 上机运行本程序。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果注意事项在磁盘上

3、创建一个目录，专门用于存储数据结构实验的程序。实验内容线性表基本操作的实现：这个程序中演示了顺序表的创建、插入、删除和查找。程序如下：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 i

4、nitlist(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.las

5、t:=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

6、: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. 按照你对单链表的操作需要，重新改写主程序

7、并运行，打印出文件清单和运行结果实验内容单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下：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 inp

8、ut 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

9、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.nextNI

10、L) 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个结

11、点的指针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

12、 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(l

13、b.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.实验三 栈和队列实验目的用数据结构知识解决实际问题，掌握栈和队列算法设计。实验要求设计一个算法，保证货架每次上货后始终保持生产日期越近的越靠近货架里侧。实验内容商店货架以栈的方式摆放商品。生产日期越近的越靠近占地，出货是从栈顶取货。一天营业结束，如果货架不满，则需上货。如果直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，仍使生产日期越近的越靠近栈底。自主设计此算法，并上机运行，输出结果。