《数据结构》实验指导书

1、数据结构实验指导书实验一 线性表实验目的1了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。2了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。实验内容1顺序表的实践。1) 建立4个元素的顺序表list=2，3，4，5，实现顺序表建立的基本操作。2) 在list=2，3，4，5的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。3) 在list=2，3，4，9，5中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。2单链表的实践。1) 建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。2) 在已建好

2、的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。3) 在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。实验要点及说明线性表（linear list）是n（n0）个数据元素a1，a2，an组成的有限序列。其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，,an），其中的数据元素ai（1in）是一个抽象的符号， ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的

3、类型设定为elemtype，表示某一种具体的已知数据类型。顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。可定义顺序表如下： #define maxnum elemtype listmaxnum; int num=-1;线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到

4、计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问。常用的链表有单链表、循环链表和双向链表、多重链表等。单链表是线性表的链式存贮结构中每个结点只有一个指针域的链表。可定义单链表的结点结构如下： typedef struct node elemtype data; struct node *next; slnode;必做顺序表、单链表的建立，选作顺序表、单链表的插入或删除。参考程序1建立顺序表#include#define max 10main()int i=0,x,*num,ch; int listmax; printf(input lis

5、t:); while(ch= getchar()!=n) listi; i+; *num=i-1; for(i=0;i=*num;i+) printf(list%d=%c,i,listi);2顺序表插入#include#define max 5#define true 1#define false 0int insertq(int list,int *num,int i,int x) int j; if(i*num+1) printf(mistake.); return(false);if(*num=max-1)printf(list is full.); return(false);for(

6、j=*num+1;ji;j-) listj=listj-1;listi=x;(*num)+;return(true);main() int i=0,x,*num,ch; int listmax; printf(input list:); while(ch=getchar()!=n) listi=ch; i+; *num=i-1; printf(insert No.i:); scanf(%d,&i); getchar(); printf(insert data:); x=getchar(); getchar(); insertq(list,num,i,x); for(i=0;i=*num;i+)

7、 printf(list%d=%c,i,listi); printf(n); 3单链表插入#include #define null 0typedef struct nodeint data; struct node *next;slnode;void *initiate(slnode *h) *h=(slnode*)malloc(sizeof(slnode); (*h)-next=null;slnode append(slnode *p,int x) slnode *s; s=(slnode*)malloc(sizeof(slnode); s-data=x; s-next=p-next; p

8、-next=s; slnode *search(slnode *p,int x) slnode *s;s=p-next;while(s!=null) if(s-data=x) return(s); s=s-next; return(null); int insert(slnode *p,int x,int y) slnode *m,*n; n=(slnode*)malloc(sizeof(slnode); n-data=y;m=search(p,x); if(m!=null) n-next=m-next; m-next=n; return(0); else printf( %c not fou

9、nd.n,x); return(-1); void travel(slnode *p)slnode *s;s=p-next;while(s!=null) putchar(s-data); s=s-next;putchar(n);main()int i,ch1,ch2,n; slnode *q,*p; initiate(&p); for(i=1;i4;i+)printf(ch%d=,i);ch1=getchar();getchar();append(p,ch1);printf(point ch%d=%cn,i,ch1);travel(p);printf(ch1=);ch1=getchar();g

10、etchar();printf(ch2=);ch2=getchar();getchar();insert(p,ch1,ch2);travel(p);实验二 栈和队列实验目的1了解顺序栈的结构特点及有关概念，掌握顺序栈建立及入栈的基本操作。2了解顺序栈共用的含义及优点，掌握顺序战的基本操作。实验内容进行顺序栈初始化及入栈、出栈、共用，实现顺序栈建立及入栈、出栈、共用的基本操作。实验要点及说明栈(stack)：是限定仅在表尾进行插入或删除操作的线性表。 栈顶(Top)：允许插入和删除的一端，为变化的一端。 栈底(Bottom):栈中固定的一端。 空栈：栈中无任何元素。特点：根据栈的定义可知，最先放

11、入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。栈的运算：1.初始化栈： Void initstack(s) 将栈S置为一个空栈(不含任何元素)。2.进栈： Void Push(&s,x) 将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。3.出栈： elemtype Pop(&s) 删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。4.取栈顶元素： Elemtype gettop(s) 取栈S中栈顶元素。5.判栈空：

12、 Int empty(s) 判断栈S是否为空，若为空，返回值为1，否则返回值为0。6. 置空栈：void clearstack(&s)顺序栈的数据类型：#define stacksize 100 /定义栈的最大容量为maxlenTypedef int elemtype; typedef Struct elemtype datastacksize+1; /将栈中元素定义为elemtype类型 int top; /:指向栈顶位置的指针 sqstack;参考程序1顺序栈初始化及入栈#include #define max 10typedef struct char stackmax; int top

13、; qstype;void initiateqs(qstype *s) s-top=- 1; int push(qstype *s,int x) if(s-top=max- 1) return(0); else s-top+; s-stacks-top=x; return(1); main() int ch,sign;qstype *s;initiateqs(s);printf();scanf(%d,&ch);while(ch!=-1) if(sign=push(s,ch)=0) printf( overflown ); break; else scanf( %d,&ch);while(s-t

14、op!= 1)s-top-;printf(stack=%dn,s-stacks-top+ 1);printf(n);2顺序栈初始化及出栈#include #define max 10typedef struct char stackmax; int top; qstype;void initiateqs(qstype *s) s-top= 1; int push(qstype *s,int x) if(s-top=max- 1) return(0); else s-top+; s-stacks-top=x; return(1); int pop(qstype *s)if(s-toptop-;

15、return(s-stacks-top+1);main()int ch,sign;qstype *s;initiateqs(s);printf();scanf(%d,&ch);while(ch!= -1 ) if(sign=push(s,ch)!=1) break; scanf( %d,&ch);while(ch=pop(s)!=0) printf(%d,ch);printf(n);3顺序栈的共用#include#define m 40typedef structint top2; int stackm; dqstype;void initiatedqs(dqstype *s) s-top0=

16、 1; s-top1=m;int pushdqs(dqstype *s,int i,int x) if(s-top0=s-top1-1) printf(full); return(-1); if(i!=0&i!=1) printf(mistake); return(-1); if(i=0) s-topi+; s-stacks-topi=x; else s-topi-; s-stacks-topi =x;return(1);int popdqs(dqstype *s,int i)if(i!=0&i!=1) printf(mistake); return(0); if(i=0) if(s-topi

17、topi-; return(s-stacks-topi+ 1); elseif(s-topi=m) printf(nstrack1 empty.); return(0); s-topi+;return(s-stacks-topi-1);main()int sign,i,ch;dqstype *s;initiatedqs(s);printf(please enter stack i=);scanf( %d,&i);getchar();printf(%);while(ch=getchar() !=n) if(sign=pushdqs(s,i,ch) != 1 ) break;printf(plea

18、se enter other stack i=);scanf(%d,&i);getchar();printf();while(ch=getchar() !=n) if(sign=pushdqs(s,i,ch)!= 1 ) break;printf(nstack0 data out:n);while(ch=popdqs(s,0)!=0) printf( %c,ch); printf(n);printf(nstack1 data out:n);while(ch=popdqs(s,1)!=0) printf(%c,ch); printf( n); 实验三 稀疏矩阵的转置实验目的熟悉数组的有关概念，学

19、习掌握稀疏矩阵的三元组存储结构的转置方法。实验内容已知一稀疏矩阵，用三元组a103存储此矩阵，然后将其转置并存储到b103。实验要点及说明1 矩阵的压缩存储：所谓压缩存储是指为多个值相同的元只分配一个存储空间；对零元不分配空间。2 如何进行稀疏矩阵的压缩存储？按照压缩存储的概念，只存储稀疏矩阵的非零元。因此，除了存储非零元的值之外，还必须同时记下它所在行和列的位置（i, j）。反之，一个三元组（i, j, aij）唯一确定了矩阵A的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其列数唯一确定。实验要求与步骤1 基本要求：将矩阵的行列值相互交换，将每个三元组中的i和j相互调换，重排三元组之间

20、的次序，这样便可实现矩阵的转置；0120 345112321313211432253412 测试数据：0 3 1 0 M= 1 0 0 0 0 2 0 1矩阵M与其对应的三元组a3 实现提示：三元组a中，a00、a01和a02分别代表稀疏矩阵的行数、列数和非零元素个数，ai0、ai1和ai2（1ia02）分别代表非零元素的行数、列数和非零元素值。三元组b代表转置矩阵，其含义与三元组a相同；4 按要求编写程序；5 上机录入程序，并进行编辑、编译、调试，直到运行成功。参考程序1带回溯的转置程序#include stdio.hmain()int a103=3,4,5,1,2,3,1,3,1,2,1,

21、1,3,2,2,3,4,1;int b103;int i,j,q,l,p;b00=a01;b01=a00;b02=a02;if(b02!=0)q=1;for (l=1;l=a01;l+)for (p=1;p=a02;p+)if(ap1=l)bq1=ap0;bq0=ap1;bq2=ap2;q+;printf(nn output data:n);for(i=0;i=b02;i+)for(j=0;j=2;j+)printf( %d,bij);printf(n);2不带回溯的转置程序#include stdio.hint a103=3,4,5,1,2,3,1,3,1,2,1,1,3,2,2,3,4,1

22、;int b103,pot10;int i,j,q,col;main()b00=a01;b01=a00;b02=a02;if(b02!=0)for (col=2;col=a01+1;col+)potcol=0;for(i=1;i=a02;i+)col=ai1;potcol+1=potcol+1+1;pot1=1;for(i=2;i=a01;i+)poti=poti-1+poti;for(i=1;i=a02;i+)col=ai1;q=potcol;bq0=ai1;bq1=ai0;bq2=ai2;potcol=potcol+1;printf(nnoutput data:n);for(i=0;i=b

23、02;i+)for(j=0;j=2;j+)printf( %d,bij);printf(n);实验四 用递归算法遍历二叉树实验目的学习掌握二叉树各种遍历方法的基本操作算法。实验内容建立一棵二叉树，并用递归算法分别用前序、中序和后序遍历之。实验要点及说明由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。前序遍历二叉树的操作定义为：若二叉树为空，则空操作；

24、否则（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。实验要求与步骤1 基本要求：采用递归算法实现前序、中序和后序遍历；2 测试数据：3 实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次；4 按要求编写程序；5 上机录入程序，并进行编辑、编译、调试，直到运行成功。参考程序#include#define

25、null 0int counter=0;typedef struct btreenodeint data;struct btreenode *lchild;struct btreenode *rchild;bnode;bnode *p;bnode *creat(int x,bnode *lbt, bnode *rbt)bnode *p;p=(bnode*)malloc(sizeof(bnode);p-data=x;p-lchild=lbt;p-rchild=rbt;return(p);bnode *ins_lchild(bnode *p,int x)bnode *q;if(p=null)pri

26、ntf(Illegal insert.);elseq=(bnode*)malloc(sizeof(bnode);q-data=x;q-lchild=null;q-rchild=null;if(p-lchild!=null)q-rchild=p-lchild;p-lchild=q;bnode *ins_rchild(bnode *p,int x)bnode *q;if(p=null)printf(Illegal insert.);elseq=(bnode*)malloc(sizeof(bnode);q-data=x;q-lchild=null;q-rchild=null;if(p-rchild!

27、=null)q-lchild=p-rchild;p-rchild=q;void prorder(bnode*p)if(p=null)return;printf(%dt%ut%dt%ut%un,+counter,p,p-data,p-lchild,p-rchild);if(p-lchild!=null)proder(p-lchild);if(p-rchild!=null)proder(p-rchild);void preorder(bnode *p)if(p=null)return;printf(%d,p-data);if(p-lchild!=null)preoder(p-lchild);if(

28、p-rchild!=null)preoder(p-rchild);void inorder(bnode *p)if(p=null)return;if(p-lchild!=null)inoder(p-lchild);printf(%d,p-data);if(p-rchild!=null)inoder(p-rchild);void postorder(bnode *p)if(p=null)return;if(p-lchild!=null)postoder(p-lchild);if(p-rchild!=null)postoder(p-rchild);printf(%d,p-data);main()b

29、node *bt,*p,*q;int x;printf(Input root:);scanf(%d,&x);p=creat(x,null,null);bt=p;scanf(%d,&x);while(x!=-1)p=bt;q=p;wihle(x!=p-data&q!=null)p=q;if(xdata)q=p-lchild;elseq=p-rchild;if(x=p-data)printf(The data is exit.);return;else if(xdata) ins_lchild(p,x); else ins_rchild(p,x); scanf(%d,&x); p=bt;print

30、f(structure of the binary tree:n);printf(numbertaddresstdatatlchildtrchildn);prorder(p);printf(preorder:);preorder(p);printf(n);printf(inorder:);inorder(p);printf(n);printf(postorder:);postorder(p);printf(n);实验五 求哈夫曼编码实验目的学习掌握构造哈夫曼树的方法及哈夫曼编码的生成。实验内容输入一串叶结点的权值，建立一棵哈夫曼树，并求出每个叶结点的哈夫曼编码。实验要点及说明1结点路径长度：由

31、根结点到某个结点所经过的树的分支个数。2二叉树路径长度：由根结点到所有叶结点的路径长度之和。3二叉树的带权路径长度：设二叉树具有n个带权值的叶结点，那么从根结点到各叶结点的路径长度与相应结点权值的乘积的和即为二叉树的带权路径长度。4哈夫曼树：对于一组带有确定权值的叶结点，其构造出的不同的二叉树其带权路径长度并不相同，我们把其中具有最小带权路径长度的二叉树称作哈夫曼树。实验要求与步骤1基本要求：哈夫曼编码规则：在所构造的哈夫曼树中，所有向左路径的分支规定为0，所有向右路径的分支规定为1；2测试数据：叶结点个数： n=4 ； 叶结点权值： 7 5 3 1 ；3 实现提示：写程序时每次都选取未构造过

32、的权值最小的叶子结点来构造哈夫曼树，最后根据哈夫曼编码规则求出哈夫曼编码；4 按要求编写程序；5 上机录入程序，并进行编辑、编译、调试，直到运行成功。参考程序#include #define max 1000#define maxsymbs 30#define maxbits 10#define maxnode 59typedef struct int weight; int flag; int parent; int lchild; int rchild; huffnode;typedef struct int bitsmaxbits; int start; huffcode; main()

33、 huffnode huff_nodemaxnode; huffcode huff_codemaxsymbs,cd; int i,j,m1,m2,x1,x2,n,c,p; char symbsmaxsymbs,symb; printf(n=); scanf(%d,&n); for(i=0;i); for(i=0;in;i+) scanf(%d,&huff_nodei.weight); for(i=0;in-1;i+) m1=m2=max; x1=x2=0; for(j=0;jn+i;j+) if(huff_nodej.weightm1&huff_nodej.flag=0) m2=m1; x2=

34、x1; m1=huff_nodej.weight; x1=j; elseif(huff_nodej.weightm2&huff_nodej.flag=0) m2=huff_nodej.weight; x2=j; huff_nodex1.parent=n+i; huff_nodex2.parent=n+i; huff_nodex1.flag=1; huff_nodex2.flag=1; huff_noden+i.weight=huff_nodex1.weight+huff_nodex2.weight; huff_noden+i.lchild=x1; huff_noden+i.rchild=x2;

35、 for(i=0;in;i+) cd.start=n; c=i; p=huff_nodec.parent; while(p!=-1) if(huff_nodep.lchild=c) cd.bitscd.start=0; else cd.bitscd.start=1; cd.start=cd.start-1; c=p; p=huff_nodep.parent; for(j=cd.start+1;j=n;j+) huff_codei.bitsj=cd.bitsj; huff_codei.start=cd.start; for(i=0;in;i+) printf(%d,huff_nodei.weig

36、ht); for(j=huff_codei.start+1;j=n;j+) printf(%d,huff_codei.bitsj); printf(n); 实验六 图遍历的演示实验目的学习掌握图的两种搜索路径的遍历。实验内容试写一个程序，演示在连通的无向图上遍历全部结点的操作实验要点及说明1 深度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3，依次类推，直到一个所有邻接点都被访问过为止。2 广度优先搜索遍历图的算法：首先访问指定的起始

37、顶点 v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，wk，然后再依次从w1，w2，wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。实验要求与步骤1 基本要求：采用邻接表作存储结构，实现连通无向图的深度优先搜索遍历和广度优先搜索遍历。2 测试数据：如下图： 3 实现提示：根据广度优先搜索的规则，在其算法实现中，借助一个队列g-queque来存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依次类推，直至队列为空且图中结点均被访问过为止；4

38、按要求编写程序；5 上机录入程序，并进行编辑、编译、调试，直到运行成功。参考程序1、深度优先搜索遍历图#include#include#define maxnode 40#define null 0typedef struct st_arcint adjvex;int weight;struct st_arc *nextarc;arcnode;typedef structint vertex;struct st_arc *firstarc;vernode;typedef vernode adjlistmaxnode;void trave(adjlist g,int n)int i,visite

39、dmaxnode;void dfs();for(i=0;in;i+)visitedi=0;for(i=0;iadjvex;if(visitedw=0)dfs(g,w,visited);p=p-nextarc;main()int i,j,n,k,v;arcnode *p,*q;adjlist g;printf(Input node: );scanf(%d,&n);for(k=0;kadjvex=j;q-nextarc=gi.firstarc;gi.firstarc=q;p=(arcnode*)malloc(sizeof(arcnode);p-adjvex=i;p-nextarc=gj.first

40、arc;gj.firstarc=p;printf(dfs:);trave(g,n);printf(n);2、广度优先搜索遍历图#include#include#define null 0#define maxnode 40typedef struct st_arcint adjvex;int weight;struct st_arc *nextarc;arcnode;typedef structint vertex;struct st_arc *firstarc;vernode;typedef vernode adjlistmaxnode;typedef structint queuemaxn

41、ode;int front,rear;qqtype;void initiate(qqtype *q)q-front=-1;q-rear=-1;int enter(qqtype *q, int x)if(q-rear=maxnode-1)return(-1);elseq-rear+;q-queueq-rear=x;return(0);int delete(qqtype *q )if(q-front=q-rear)return(null);elseq-front+;return(q-queueq-front);int emtype(qqtype *q)if(q-front=q-rear)retur

42、n(-1);return(0);void bfs(adjlist g,int k,int visited)arcnode *p;int w;initiate(g);visitedk=1;printf(%d,gp-adjvex.vertex);enter(g,k);while(emtype(g)=0)w=delete(g);p=gw.firstarc;while(p!=null)if(visitedp-adjvex=0)printf(%d,gp-adjvex.vertex);visitedp-adjvex=1;enter(g,p-adjvex);p=p-nextarc;void trave(ad

43、jlist g,int n)int i, visitedmaxnode;for(i=0;in;i+)visitedi=0;for(i=0;in;i+)if(visitedi=0)bfs(g,i,visited);main()int i,j,n,k,v;arcnode *p,*q;adjlist g;printf(Input node:);scanf(%d,&n);for(k=0;kadjvex=j;q-nextarc=gi.firstarc;gi.firstarc=q;p=(arcnode*)malloc(sizeof(arcnode);p-adjvex=i;p-nextarc=gj.firstarc;gj.firstarc=p;printf(bfs:);trave(g,n);printf(n);实验七 查找实验目的学习掌握查找的过程及方法。实验内容1 实现顺序查找，在输入的数组纪录中顺序查找所需的纪录。2 用