数据结构试验指导书.doc

实验一 线性表程序1
1、实验目的
使学生熟练掌握单链线性表的基本操作
2、实验内容
设计程序完成一元稀疏多项式计算器的功能。
用带表头结点的单链表存储多项式，设计一个一元稀疏多项式简单计算器，多项式的项数存放在头结点中。
3、实验要求
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式；
（2）多项式的输出形式为整数序列：n，c1,e1，c2，e2 ，…，cn ，en ，其中n 是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
（3）多项式的输出形式为类数学表达式。例如：多项式-3x^8+6x^3-18的输出形式为-3x^8+6x^3-18，x^15+(-8)x^7-14的输出形式为x^15-8x^7-14。注意：系数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x^8，项-1x3的输出形式为-x^3
（4）多项式a和b相加，建立多项式a+b；
4、测试数据
（1）（2x+5x^8-3.1x^11）+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)
（2）（1+x+x^2+x^3+x^4+x^5）+(-x^3-x^4)=(1+x+x^2+x^5)
（3）（x+x^3）+(x-x^3)=0
（4）（x+x^100）+(x^100+x^200)=(x+2x^100+x^200)
(5)(x+x^2+x^3)+0=x+x^2+x^3
5、参考程序1：
#define NULL 0
#include "stdio.h"
typedef struct Lnode {/*结点类型*/
float coef ;/*系数*/
int expn;/*指数*/
struct Lnode *next;
}Lnode, *link;
typedef link polynomail;
/*用带表头结点的有序键表表示多项式*/
polynomail pa,pb,pc;
void creatpolyn( polynomail p, int m)
{/* 输入 m项的系数和指数,建立表示一元多项式的有序链表 p */
int i;
float coef;
int expn;
polynomail tail,new;
p->coef=m;
p->expn=-1;
tail=p;
for(i=1;i<=m;i++) {
new=(link)malloc(sizeof(Lnode));
printf("please input coef and expn ");
scanf("%f", &coef);
scanf("%d", &expn);
new->coef=coef;
new->expn=expn;
new->next=NULL;
tail->next=new;
tail=new;
}
}
void addpolyn(polynomail pa, polynomail pb)
{ /* 完成多项式相加运算,即:pc=pa+pb,并销毁一元多项式pb */
int x,len;
float y;
polynomail pre,p,q,u;
pc=pa;
len=0;
pre=pa;
p=pa->next;
q=pb->next;
while (p && q)
{ x=p->expn - q->expn;
if (x<0)
{ pre=p;len ++;
p=p->next;
}
else if (x==0)
{ y=p->coef + q->coef;
if (y!=0.0)
{ p->coef=y;
pre=p;len ++;
}
else
{ pre->next=p->next;
free (p);
}
p=pre->next;
u=q;
q=q->next;
free (u);
}
else
{
u=q->next;
q->next=p;
pre->next=q;
pre=q; len ++;
q=u;
}
}
if (q) pre->next=q;
while(pre)
{ pre=pre->next;
if(pre) len ++;
}
pc->coef=len;
free (pb);
}
void printpoly(polynomail q)
{ /* 按类数学表达式的格式输出一元多项式的任意一项q */
if (q->expn==0)
printf("%.0f", q->coef);
else if (q->expn==1)
{ if (q->coef==1)
printf("x");
else if (q->coef==-1)
printf("-x");
else
{ printf("%.0f", q->coef);
printf("x");
}
}
else if (q->coef==1)
printf("x^%d", q->expn);
else if( q->coef==-1)
printf("-x^%d", q->expn);
else printf("%.0fx^%d", q->coef, q->expn);
}
void printpolyn(polynomail p)
{ /* 按类数学表达式的格式输出一元多项式p */
int n;
polynomail q;
q=p->next;
n=0;
while (q)
{ n++;
if (n==1)
printpoly(q);
else if (q->coef>0)
{printf("+");
printpoly(q);
}
else
printpoly(q);
q=q->next;
}/*while*/
}/*printpolyn*/
void print(polynomail p)
{ /* 按输出形式为整数序列：n，c1,e1，c2，e2 ，…，cn ，en ，打印输出一元多项式 p */
polynomail q;
printf("\n %.0f\n",p->coef);
q=p->next;
while (q)
{ printf(" %.0f,", q->coef);
printf(" %d\n", q->expn);
q=q->next;
}
printf("\b \n");/*去掉最后一个逗号并换行*/
}
main()
{
int m,n;
printf("\n please input n:");
scanf("%d",&n);
pa=(link)malloc(sizeof(Lnode));
creatpolyn(pa,n);
printf("\n pa=");
printpolyn(pa);
printf("\n please input m:");
scanf("%d",&m);
pb=(link)malloc(sizeof(Lnode));
creatpolyn(pb,m);
printf("\n pb=");
printpolyn(pb);
addpolyn(pa,pb);
printf("\n pc=pa+pb=");
printpolyn(pc);
print(pc);
getchar();
getchar();
}
程序2
1、实验目的
使学生熟练掌握单链线性表的基本操作
2、实验内容
该程序的功能是创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删除一个元素，均保持链表的正序。在执行完每个操作后将其输出。
3、实验要求
所使用的单链表最好带有附加的头节点，这样所涉及的程序比较简洁。

参考程序2
#include "stdio.h"
#include "alloc.h"
#include "stdlib.h"
#include "stddef.h"
/*节点定义*/
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}linklist;

/*创建链表函数*/
linklist *creatlist()
{
datatype d;
linklist *p,*s,*head;
head=malloc(sizeof(linklist));
head->next=NULL;
printf("please input the integer!(0---return)");
scanf("%d",&d);
while (d!=0)
{
s=malloc(sizeof(linklist));
s->data=d;
p=head;
while(p->next!=NULL)
if (p->next->data<d)
p=p->next;
else break;
s->next=p->next;
p->next=s;
printf("please input the integer!0----return");
scanf("%d",&d);
}
return head;
}

/*输出链表中的所有元素*/
void output(head)
linklist *head;
{
linklist *p;
p=head->next;
while(p!=NULL)
{
printf("%6d",p->data);
p=p->next;
}
printf("\n");
}

/*插入一个元素，标志链表的正序性。*/
void insert(head,x)
linklist *head;
datatype x;
{
linklist *p,*s;
s=malloc(sizeof(linklist));
s->data=x;
p=head;
while (p->next!=NULL)
if (p->next->data<x)
p=p->next;
else break;
s->next=p->next;
p->next=s;
printf("%d has been inserted into the linklist!\n",x);
}

/* 删除链表中的一个元素*/
delete(head,x)
linklist *head;
datatype x;
{
linklist *p,*s;
p=head;
while (p->next!=NULL)
if (p->next->data!=x)
p=p->next;
else break;
if(p->next!=NULL)
{s=p->next;
p->next=s->next;
printf("%d has been deleted!\n",x);
}
else
printf("%d isn,t in thelinklist!\n",x);
}

/*查找元素x,找到则返回其位置，否则返回空。*/
linklist *search(head,x)
linklist *head;
datatype x;
{linklist *p;
p=head->next;
while(p!=NULL)
if(p->data!=x)
p=p->next;
else break;
return p;
}

main()
{
linklist *head,*p;
datatype x; int i=0;
char choice=' ';
while (choice!='0')

{
printf("1-----create the list!\n");
i++ ;
printf("2-----output the list!\n");
i++;
printf("3-----find a element in the list!\n");
i++;
printf("4-----insert a element to the list!\n");
i++;
printf("5-----delete a element in the list!\n");

i++;
printf("0------quit\n");
printf("input your choice(0-----5)");
scanf("%c",&choice);
printf("\n");
switch(choice)
{
case '1':head=creatlist();break;
case '2':output(head);break;
case '3':printf("please input a element you want to find in the list!\n");
scanf("%d",&x);
p=search(head,x);
if (p!=NULL)
printf("%d has been found!\n",x);
else printf("%d isn't in the list!\n",x);
break;
case '4':printf("please input a element you want to insert into the list!\n");
scanf("%d",&x);
insert(head,x);
break;
case '5':printf("please input a element you want to delete!\n");
scanf("%d",&x);
delete(head,x);
break;
case '0':break;
实验五 数组和广义表
1、实验目的
深入了解数组的存储表示和实现，熟悉广义表的存储结构的特性
2、实验内容
稀疏矩阵运算器
3、实验要求
（1）稀疏矩阵以三元组表输入，以通常的阵列形式输出；
（2）实现稀疏矩阵的转置
（3）实现两个稀疏矩阵的乘法运算
4、原代码程序
#include "stdio.h"
#define MAXSIZE 50 /*假设非零元个数的最大值为 50*/
#define MAXRC 10
typedef struct{
int i,j; /*该非零元的行下标和列下标*/
int e;
}triple;
typedef struct{
triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int mu,nu,tu;/*矩阵的行数、列数和非零元个数*/
}tsmatrix;
typedef struct{
triple data[MAXSIZE+1]; /*非零元三元组表,data[0]未用*/
int rpos[MAXRC+1]; /*各行第一个非零元的位置表*/
int mu,nu,tu;/*矩阵的行数、列数和非零元个数*/
}rlsmatrix;
tsmatrix tcreate(int m,int n,int t)
{ /*建立稀疏矩阵M的三元组顺序表*/
tsmatrix M; int k;
M.mu=m;M.nu=n;M.tu=t;
printf("\nplease input %d data",M.tu);
printf("\ni j e\n");
for(k=1;k<=M.tu;++k)
scanf("%d %d %d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
return(M);
}
rlsmatrix rlcreate(int m,int n,int t)
{ /*建立稀疏矩阵M的三元组顺序表*/
rlsmatrix M;
int num[MAXRC];
int k,row;
M.mu=m;M.nu=n;M.tu=t;
printf("\n please input %d data",M.tu);
printf("\ni j e\n");
for(k=1;k<=M.tu;++k)
scanf("%d %d %d",&M.data[k].i,&M.data[k].j,&M.data[k].e);
for(row=1; row<=M.mu;++row) num[row]=0;
/*求M中每一行含非零元个数*/
for(k=1;k<=M.tu;++k) ++num[M.data[k].i];
M.rpos[1]=1;
/* 求第row行中第一个非零元在 M.data中的序号*/
for(row=2; row<=M.mu;++row)
M.rpos[row]=M.rpos[row-1]+num[row-1];
return(M);
}
void tprint(tsmatrix M)
{/*输出M.data即M的三元组表*/
int k;
for(k=1;k<=M.tu;++k)
{
printf("\n");
printf("%d %d %d",M.data[k].i,M.data[k].j,M.data[k].e);
}
printf("\n");
}
void rlprint(rlsmatrix M)
{/*输出M.data即M的三元组表*/
int k;
for(k=1;k<=M.tu;++k)
{
printf("\n");
printf("%d %d %d",M.data[k].i,M.data[k].j,M.data[k].e);
}
printf("\n");
}
tsmatrix transpose( tsmatrix M){
/*采用三元组表存储表示,求稀疏矩阵M的转量矩阵T*/
tsmatrix T;
int col,p,q;
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
if(T.tu){
q=1;
for(col=1; col<=M.nu;++col)
for(p=1;p<=M.tu;++p)
if(M.data[p].j==col){
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++q;}
}
return(T);
}
tsmatrix fasttrans(tsmatrix M)
{/*快速转置*/
tsmatrix T; int col,p,q,t;
int num[MAXRC]; int cpot[MAXRC];
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
if(T.tu){
for(col=1; col<=M.nu;++col) num[col]=0;
for(t=1;t<=M.tu;++t) ++num[M.data[t].j];
/*求M中每一列含非零元个数*/
cpot[1]=1;
/* 求第col列中第一个非零元在 b.data中的序号*/
for(col=2; col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p){
col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col]; }
}
return(T);
}
rlsmatrix mult(rlsmatrix M, rlsmatrix N)
{/*求矩阵乘积Q＝M*N,采用行逻辑链接存储表示*/
rlsmatrix Q;
int arow,brow,ccol;
int t,tp,p,q;
int ctemp[MAXRC];
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0;/*Q初始化*/
if(M.tu*N.tu!=0){/*Q是非零矩阵*/
for (arow=1;arow<=M.mu;++arow){ /*处理M的每一行*/
for(ccol=1;ccol<=Q.nu;++ccol) ctemp[ccol]=0;
/*M当前行各元素累加器清零*/
Q.rpos[arow]=Q.tu+1;
if(arow<M.mu) tp=M.rpos[arow+1];
else tp=M.tu+1;
for(p=M.rpos[arow];p<tp;++p){
brow=M.data[p].j;
if(brow<N.mu)t=N.rpos[brow+1];
else t=N.tu+1;
for(q=N.rpos[brow];q<t;++q){
ccol=N.data[q].j;
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}/*for q*/
}/*for p*/
for(ccol=1;ccol<=Q.nu;++ccol)
if(ctemp[ccol]){
++Q.tu;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}
}
}
return(Q);
}/*mult*/
main()
{ int m,n,t,m1,m2,n1,n2,t1,t2;
rlsmatrix M,N,Q;
tsmatrix E,F;
printf("\n please input m,n,t:");
scanf("%d %d %d",&m,&n,&t);
E=tcreate(m,n,t);
tprint(E);
F=transpose(E);
tprint(F);
printf("\n please input m1,n1,t1:");
scanf("%d %d %d",&m1,&n1,&t1);
M=rlcreate(m1,n1,t1);
rlprint(M);
printf("\n please input m2,n2,t2:");
scanf("%d %d %d",&m2,&n2,&t2);
N=rlcreate(m2,n2,t2);
rlprint(N);
Q=mult(M,N);
rlprint(Q);
getchar();
getchar();
}

试验七 二叉树的建立及输出
试验目的：
熟悉二叉链表表示的二叉树结构及其递归遍历，掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。
试验内容：
建立一颗二叉链表表示的二叉树。
对其进行前序，中序，后序输出。
试验要求：
先将二叉树通过加入虚节点的方式使其完全化，然后按层将其输入。可以用二叉树中不会出现字符表示虚节点例如@，另一二叉树中不会出现的字符表示输入序列结束例如#。如下二叉树须输入序列a@b@@c# 。或以广义表的形式输入二叉树的节点。

按先序，中序，后序序列将其遍历输出。
参考程序：
#include "stdio.h"
#include "alloc.h"
#include "stdlib.h"
#include "stddef.h"
#define maxsize 100
typedef int datatype;
/*定义二叉树节点*/
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;

bitree q[maxsize];/*定义全局队列*/
/*建立二叉树*/
bitree *creatree()
{char ch;
int front,rear;
bitree *s,*root;
root=NULL;
front=1;
rear=0;
printf("please input a tree's string ended with #!\n");
ch=getchar();
while(ch!='#')
{s=NULL;
if (ch!='@')
{s=malloc(sizeof(bitree));
s->data=ch;
s->lchild=s->rchild=NULL;
}
rear++;
q[rear]=s;
if(rear==1)
root=s;
else
{if (s&&q[front])
if(rear%2==0)q[front]->lchild=s;
else q[front]->rchild=s;
if (rear%2==1) front++;
}
ch=getchar();
}
return root;
}

/*中序遍历二叉树*/
inorder(t)
bitree *t;
{
if (t)
{inorder(t->lchild);
printf("%6c",t->data);
inorder(t->rchild);
}
}

/*先序遍历二叉树*/
preorder(t)
bitree *t;
{
if (t)
{ printf("%6c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}

/*后序遍历二叉树*/
postorder(t)
bitree *t;
{
if (t)
{postorder(t->lchild);
postorder(t->rchild);
printf("%6c",t->data);
}
}

main()
{
bitree *t;
int i;
do
{

printf("1---------creat the binary tree!\n");
printf("2---------traverse the tree in inorder!\n");
printf("3---------traverse the tree in preorder!\n");
printf("4---------traverse the tree in postorder!\n");
printf("0-------quit!\n");
scanf("%d",&i);
switch(i)
{
case 1:t=creatree();
break;
case 2:inorder(t);
printf("\n");
break;
case 3:preorder(t);
printf("\n");
break;
case 4:postorder(t);
printf("\n");
break;
case 0:break;
default:puts("again");
}

}while (i!=0);
}



试验八：图及其遍历
1． 试验目的：
1） 熟悉图的邻接矩阵及邻接表的表示方法。
2） 掌握建立图的邻接矩阵算法，并由邻接矩阵转化为邻接表
3） 熟悉对图遍历算法。
2． 试验内容：
1） 建立图的邻接表及邻接矩阵。
2） 对其进行深度优先及广度优先遍历。
3． 试验要求：
将如下图以邻接矩阵的存储形式存入计算机，然后输出其深度优先及广度优先序列。

4． 参考程序：
#include "stddef.h"
#include "stdlib.h"
#include "stdio.h"
#include "alloc.h"
#define n 6
#define e 8
#define TRUE 1
#define FALSE 0
typedef char vextype;
typedef int adjtype;

/*定义邻接矩阵存放的图*/

typedef struct
{ vextype vexs[n];
adjtype arcs[n][n];
}graph;
graph *ga1;
/*定义邻接表存放的图*/

typedef struct node
{int adjvex;
struct node *next;
}edgenode;
typedef struct
{vextype vertex;
edgenode *link;
}vexnode;
vexnode ga2[n];

/*建立邻接矩阵*/

creatgraph(ga)
graph *ga;
{int i,j,k;
printf("please input %d vexs for the graph!\n",n);
for(i=0;i<n;i++)
ga->vexs[i]=getchar();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ga->arcs[i][j]=0;
for(k=0;k<e;k++)
{printf("please input the %dth edge for the graph at the order ROW,COL!",k);
scanf("%d,%d",&i,&j);
printf("\n");
ga->arcs[i