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

1北京邮电大学远程教育信息管理与信息系统专业《数据结构》实验指导书实验一线性表的插入和删除一、实验目的1、掌握使用TurboPascal上机调试线性表的基本方法；2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验要求1、认真阅读和掌握本实验的程序。2、上机运行本程序。3、保存和打印出程序的运行结果，并结合程序进行分析。4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、实验内容程序1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找。程序如下：PROGRAMseqlist(input,output);{线性表可能达到的最大长度}CONSTmaxlen=1024;TYPEelemtp=integer;{线性表的顺序存储结构}TYPE2seqlisttp=RECORD{用一维数组来描述线性表的顺序存储结构}elem:ARRAY[1..maxlen]OFelemtp;{定义子界类型last，它的取值范围是0到maxlen}last:0..maxlen{线性表长度}END;{初始化线性表}PROCEDUREinitlist(VARv:seqlisttp;ml:integer);BEGINv.last:=0;END;{向线性表的第i个元素之前插入一个元素x}PROCEDUREinsertlist(VARv:seqlisttp;i:integer;b:elemtp);VARj:integer;BEGINIF(i1)OR(iv.last+1)THENwriteln('error!')ELSEIFv.last=maxlenTHENwriteln('overflow')ELSEBEGINFORj:=v.lastDOWNTOiDOv.elem[j+1]:=v.elem[j];v.elem[i]:=b;v.last:=v.last+1;END;END;{从线性表中删除第i个位置的元素}PROCEDUREdeletelist(VARv:seqlisttp;i:integer);VARj:integer;BEGIN3IF(i1)OR(iv.last+1)THENwriteln('error!')ELSEIFv.last=maxlenTHENwriteln('overflow')ELSEBEGINFORj:=i+1TOv.lastDOv.elem[j-1]:=v.elem[j];v.last:=v.last-1;END;END;{从线性表中查找元素}FUNCTIONfindlist(v:seqlisttp;x:elemtp):integer;VARi:integer;BEGINi:=1;WHILE(i=v.last)AND(v.elem[i]x)DOi:=i+1;IFi=v.lastTHENfindlist:=iELSEfindlist:=0;END;{遍历线性表}PROCEDUREtraverlist(v:seqlisttp);VARi:integer;BEGINFORi:=1TOv.lastDOBEGINwriteln(v.elem[i]);END;END;4{建立线性表}VARa:seqlisttp;i,k:integer;x:elemtp;BEGIN{初始化线性表}InitList(a,maxlen);{相线性表a的末尾插入5个元素}writeln('Input5integers:');FORi:=1TO5DOBEGINreadln(x);insertlist(a,a.last+1,x);END;{遍历线性表a}traverlist(a);{删除线性表的第三个元素}deletelist(a,3);{遍历线性表a}traverlist(a);{在线性表中查找元素}writeln('Inputtheintegertobefound:');readln(x);k:=findlist(a,x);IFk0THENwriteln('Thelocationoffirst',x,'is',k)ELSEwriteln('notfound');writeln(a.last);END.5实验二单链表操作一、实验目的1．掌握握单链表的基本操作：插入、删除、查找等运算。二、实验要求1．认真阅读和掌握本实验的程序。2．上机运行本程序。3．保存和打印出程序的运行结果，并结合程序进行分析。4．按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、实验内容程序1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下：PROGRAMlinklist(input,output);TYPEelemtp=char;{单链表中结点的类型}TYPEpointer=^node;node=RECORDdata:elemtp;next:pointer;END;{头插法建表,先进后出}PROCEDUREcreatelistf(VARv:pointer);VARch:elemtp;head:pointer;{头指针}p:pointer;{工作指针}6BEGINhead:=NIL;write('Pleaseinputchars:');{read(ch);}{上一条语句会输出一个换行符，}{我们先把它读出来，丢掉}read(ch);WHILE(ord(ch)13)DOBEGINnew(p);p^.data:=ch;p^.next:=head;head:=p;read(ch);END;v:=head;END;{尾插法建表,先进先出}PROCEDUREcreatelistr(VARv:pointer);VARch:elemtp;head:pointer;{头指针}last:pointer;{尾指针}p:pointer;{工作指针}BEGINhead:=NIL;last:=NIL;write('Pleaseinputchars:');read(ch);read(ch);WHILE(ord(ch)13)DO7BEGINnew(p);p^.data:=ch;IFhead=NILTHENhead:=pELSElast^.next:=p;last:=p;read(ch);END;IFlastNILTHENlast^.next:=NIL;v:=head;END;{按序号查找操作}PROCEDUREgetnode(v:pointer;VARlistnode:pointer;i:integer);VARp:pointer;j:integer;BEGINp:=v;j:=1;WHILE(p^.nextNIL)AND(ji)DOBEGINp:=p^.next;j:=j+1;END;IFj=iTHENlistnode:=pELSElistnode:=NIL;END;{插入操作，在第i个元素之后插入x,i大于等于0}PROCEDUREinsertlist(VARv:pointer;x:elemtp;i:integer);VAR8p,s:pointer;{工作指针}j:integer;BEGINnew(p);p^.data:=x;IFi=0THEN{如果i=0，则把p结点插入表头}BEGINp^.next:=v;v:=pENDELSEBEGINgetnode(v,s,i);{返回第i个结点的指针}IFsNILTHENBEGINp^.next:=s^.next;s^.next:=p;ENDELSEwriteln('notfound');END;END;{删除操作，删除第i个结点,i大于等于1}PROCEDUREdeletelist(VARv:pointer;i:integer);VARp:pointer;{工作指针}BEGINIFvNILTHENBEGIN9IFi=1THEN{如果i=1，则删除头结点}v:=v^.nextELSEBEGINgetnode(v,p,i-1);{返回第i-1个结点的指针}IFpNILTHENp^.next:=p^.next^.nextELSEwriteln('erroe');END;ENDELSEwriteln('Thelistisnull.');END;{遍历单链表}PROCEDUREtraverlist(v:pointer);VARp:pointer;BEGINp:=v;WHILE(pNIL)DOBEGINwrite(p^.data,'');p:=p^.next;END;END;{建立线性表}VARla,lb:pointer;listnode:pointer;10c:elemtp;m:integer;BEGINcreatelistf(la);writeln(la^.data);createlistr(lb);writeln(lb^.data);getnode(la,listnode,3);IFlistnodeNILTHENwriteln(listnode^.data)ELSEwriteln('null');traverlist(la);writeln('');traverlist(lb);writeln('');writeln('Inputacharandaninteger:');read(c);read(c,m);insertlist(la,c,m);traverlist(la);writeln('');deletelist(lb,3);traverlist(lb);END.实验三二叉树操作一、实验目的1．进一步掌握指针变量的含义。2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3．掌握用指针类型描述、访问和处理二叉树的运算。11二、实验要求1．认真阅读和掌握本实验的程序。2．上机运行本程序。3．保存和打印出程序的运行结果，并结合程序进行分析。4．按照你二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、实验内容程序1：按先序次序输入二叉树中结点的值（一个字符），`0`表示空树，生成二叉树的二叉链表存储结构，bt为指向根结点的指针。然后按层次顺序遍历二叉树。算法思想：本算法采用一个队列q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，遍将右子树根结点入队列，直到队列空为止。因为队列是先进先出，从而达到按层次顺序遍历二叉树的目的。程序如下：PROGRAMbtreed(input,output);CONSTM=100;TYPEelemtp=char;{二叉树的链式存储结构}TYPEbtree=^node;node=RECORDdata:elemtp;lchild,rchild:btree;END;TYPEvector=ARRAY[0..M]OFbtree;12{生成二叉树}VARroot:btree;que:vector;front,rear:integer;PROCEDUREcreate(VARbt:btree);VARx:elemtp;BEGINread(x);IF(ord(x)=48)THENbt:=NILELSEBEGINnew(bt);bt^.data:=x;{建根结点}create(bt^.lchild);{建左子树}create(bt^.rchild);{建右子树}END;END;PROCEDUREinorder(bt:btree);BEGINIFbtNILTHENBEGINinorder(bt^.lchild);write(bt^.data,'');inorder(bt^.rchild);END;END;13PROCEDUREenqueue(bt:btree);BEGINIFfront((rear+1)MODM)THENBEGINrear:=((rear+1)MODM);que[rear]:=bt;END;END