信息管理与信息系统专业《数据结构》实验指导
实验一 线性表的插入和删除
一、
实验目的
1、掌握使用Turbo Pascal上机调试线性表的基本方法；
2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
二、
实验要求
1、认真阅读和掌握本实验的程序。 2、上机运行本程序。
3、保存和打印出程序的运行结果，并结合程序进行分析。
4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、
注意事项：
在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 四、
实验内容
程序1：线性表基本操作的实现
这个程序中演示了顺序表的创建、插入、删除和查找。 程序如下：
PROGRAM seqlist(input,output);
{线性表可能达到的最大长度} CONST
maxlen = 1024;
TYPE
elemtp = integer;
{线性表的顺序存储结构} TYPE
seqlisttp = RECORD
1
{用一维数组来描述线性表的顺序存储结构} 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)
2
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;
3
{建立线性表} 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.
4
实验二 单链表操作
一、实验目的
1．掌握握单链表的基本操作：插入、删除、查找等运算。 二、实验要求
1．认真阅读和掌握本实验的程序。 2．上机运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、实验内容
程序1：单链表基本操作的实现
这个程序中演示了单链表的创建、插入、删除和查找。 程序如下：
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; {工作指针}
5