数据结构实验指导书
原慧琳 编写
东北大学秦皇岛分校
二○○四年十二月
前 言
数据结构课程是信息管理与信息系统专业的一门专业平台课。它是数据库、计算机网络、软件工程等课程的先修课。这门课程要求学生不但要学会针对实际问题，快速的建立起数学模型，而且还要有效地解决实际问题，这是单独的课堂教学所无法达到的。
课程的特点决定了学生必须加强实践，亲自输入算法、运行程序、输出结果，有了一定基础后，亲自进行算法设计。学中练、练中学，在模拟环境中学会用理论知识解决实际问题的能力。
本实验指导书针对课程和学生的特点和时间安排，设计了三个试验，它们是：线性表的插入和删除、单链表的操作、栈和队列的操作。其中线性表的插入和删除、单链表的操作是为了学生熟悉C++环境而设计，栈和队列的操作要求学生针对实际问题进行数学建模与算法设计。
目 录
实验一 线性表的插入和删除 ……………………………4
未找到目录项。实验二 单链表的操作 ……………………………………7
实验三 栈和队列 …………………………………………11
实验一 线性表的插入和删除
[实验目的]
1. 掌握使用MinGW Developer上机调试线性表的基本方法；
2. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
[实验要求]
1. 认真阅读和掌握本实验的程序。
2. 上机运行本程序。
3. 保存和打印出程序的运行结果，并结合程序进行分析。
4. 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
[注意事项]
在磁盘上创建一个目录，专门用于存储数据结构实验的程序。
[实验内容]
线性表基本操作的实现：这个程序中演示了顺序表的创建、插入、删除和查找。
程序如下：
PROGRAM seqlist(input,output);
{线性表可能达到的最大长度}
CONST
maxlen = 1024;
TYPE
elemtp = integer;
{线性表的顺序存储结构}
TYPE
seqlisttp = RECORD
{用一维数组来描述线性表的顺序存储结构}
elem: ARRAY[1..maxlen] OF elemtp;
{定义子界类型last，它的取值范围是0到maxlen}
last: 0..maxlen {线性表长度}
END;
{初始化线性表}
PROCEDURE initlist(VAR v:seqlisttp; ml:integer);
BEGIN
v.last:=0;
END;
{向线性表的第i个元素之前插入一个元素x}
PROCEDURE insertlist(VAR v:seqlisttp; i:integer; b:elemtp);
VAR j:integer;
BEGIN
IF (i<1) OR (i>v.last+1)
THEN writeln('error!')
ELSE IF v.last>=maxlen
THEN writeln('overflow')
ELSE BEGIN
FOR j:=v.last DOWNTO i DO
v.elem[j+1]:=v.elem[j];
v.elem[i]:=b;
v.last:=v.last+1;
END;
END;
{从线性表中删除第i个位置的元素}
PROCEDURE deletelist(VAR v:seqlisttp; i:integer);
VAR j:integer;
BEGIN
IF (i<1) OR (i>v.last+1)
THEN writeln('error!')
ELSE IF v.last>=maxlen
THEN writeln('overflow')
ELSE BEGIN
FOR j:=i+1 TO v.last DO
v.elem[j-1]:=v.elem[j];
v.last:=v.last-1;
END;
END;
{从线性表中查找元素}
FUNCTION findlist(v:seqlisttp; x:elemtp):integer;
VAR i:integer;
BEGIN
i:=1;
WHILE (i<=v.last) AND (v.elem[i]<>x) DO
i:=i+1;
IF i<=v.last THEN findlist:=i
ELSE findlist:=0;
END;
{遍历线性表}
PROCEDURE traverlist(v:seqlisttp);
VAR i:integer;
BEGIN
FOR i:=1 TO v.last DO
BEGIN
writeln(v.elem[i]);
END;
END;
{建立线性表}
VAR
a:seqlisttp;
i,k:integer;
x:elemtp;
BEGIN
{初始化线性表}
InitList(a,maxlen);
{相线性表a的末尾插入5个元素}
writeln('Input 5 integers: ');
FOR i:=1 TO 5 DO
BEGIN
readln(x);
insertlist(a,a.last+1,x);
END;
{遍历线性表a}
traverlist(a);
{删除线性表的第三个元素}
deletelist(a,3);
{遍历线性表a}
traverlist(a);
{在线性表中查找元素}
writeln('Input the integer to be found: ');
readln(x);
k:=findlist(a,x);
IF k>0 THEN writeln('The location of first ',x,' is ',k)
ELSE writeln('not found');
writeln(a.last);
END.
实验二 单链表的操作
[实验目的]
1. 掌握握单链表的基本操作：插入、删除、查找等运算。
[实验要求]
1. 认真阅读和掌握本实验的程序。
2. 上机运行本程序。
3. 保存和打印出程序的运行结果，并结合程序进行分析。
4. 按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
[实验内容]
单链表基本操作的实现
这个程序中演示了单链表的创建、插入、删除和查找。
程序如下：
PROGRAM linklist(input,output);
TYPE
elemtp = char;
{单链表中结点的类型}
TYPE
pointer=^node;
node=RECORD
data:elemtp;
next:pointer;
END;
{头插法建表,先进后出}
PROCEDURE createlistf(VAR v:pointer);
VAR
ch:elemtp;
head:pointer; {头指针}
p:pointer; {工作指针}
BEGIN
head:=NIL;
write('Please input chars: ');
{read(ch);} {上一条语句会输出一个换行符，}
{我们先把它读出来，丢掉}
read(ch);
WHILE (ord(ch)<>13) DO
BEGIN
new(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; {工作指针}
BEGIN
head:=NIL;
last:=NIL;
write('Please input chars: ');
read(ch);
read(ch);
WHILE (ord(ch)<>13) DO
BEGIN
new(p);
p^.data:=ch;
IF head=NIL THEN head:=p
ELSE last^.next:=p;
last:=p;
read(ch);
END;
IF last<>NIL THEN
last^.next:=NIL;
v:=head;
END;
{按序号查找操作}
PROCEDURE getnode(v:pointer; VAR listnode:pointer; i:integer);
VAR
p:pointer;
j:integer;
BEGIN
p:=v; j:=1;
WHILE (p^.next<>NIL) AND (jBEGINp:=p^.next;
j:=j+1;
END;
IF j=i THEN listnode:=p
ELSE listnode:=NIL;
END;
{插入操作，在第i个元素之后插入x,i大于等于0}
PROCEDURE insertlist(VAR v:pointer; x:elemtp; i:integer);
VAR
p,s:pointer; {工作指针}
j:integer;
BEGIN
new(p);
p^.data:=x;
IF i=0 THEN {如果i=0，则把p结点插入表头}
BEGIN
p^.next:=v;
v:=p
END
ELSE
BEGIN
getnode(v,s,i); {返回第i个结点的指针}
IF s<>NIL THEN
BEGIN
p^.next:=s^.next;
s^.next:=p;
END
ELSE writeln('not found');
END;
END;
{删除操作，删除第i个结点,i大于等于1}
PROCEDURE deletelist(VAR v:pointer; i:integer);
VAR
p:pointer; {工作指针}
BEGIN
IF v<>NIL THEN
BEGIN
IF i=1 THEN {如果i=1，则删除头结点}
v:=v^.next
ELSE
BEGIN
getnode(v,p,i-1); {返回第i-1个结点的指针}
IF p<>NIL THEN
p^.next:=p^.next^.next
ELSE writeln('erroe');
END;
END
ELSE writeln('The list is null.');
END;
{遍历单链表}
PROCEDURE traverlist(v:pointer);
VAR
p:pointer;
BEGIN
p:=v;
WHILE (p<>NIL)DO
BEGIN
write(p^.data,' ');
p:=p^.next;
END;
END; {建立线性表}
VAR
la,lb:pointer;
listnode:pointer;
c:elemtp;
m:integer;
BEGIN
createlistf(la);
writeln(la^.data);
createlistr(lb);
writeln(lb^.data);
getnode(la,listnode,3);
IF listnode<>NIL 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.
实验三 栈和队列
[实验目的]
用数据结构知识解决实际问题，掌握栈和队列算法设计。
[实验要求]
设计一个算法，保证货架每次上货后始终保持生产日期越近的越靠近货架里侧。
[实验内容]
商店货架以栈的方式摆放商品。生产日期越近的越靠近占地，出货是从栈顶取货。一天营业结束，如果货架不满，则需上货。如果直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，仍使生产日期越近的越靠近栈底。
自主设计此算法，并上机运行，输出结果。
