数据结构试验指导书.doc

实验一 线性表程序11、实验目的 使学生熟练掌握单链线性表的基本操作 2、实验内容设计程序完成一元稀疏多项式计算器的功能。用带表头结点的单链表存储多项式，设计一个一元稀疏多项式简单计算器，多项式的项数存放在头结点中。 3、实验要求 一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）多项式的输出形式为整数序列：n，c1,e1，c2，e2 ，cn ，en ，其中n 是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式的输出形式为类数学表达式。例如：多项式-3x8+6x3-18的输出形式为-3x8+6x3-18，x15+(-8)x7-14的输出形式为x15-8x7-14。注意：系数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x8，项-1x3的输出形式为-x3（4）多项式a和b相加，建立多项式a+b； 4、测试数据 （1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) （2）（1+x+x2+x3+x4+x5）+(-x3-x4)=(1+x+x2+x5) （3）（x+x3）+(x-x3)=0 （4）（x+x100）+(x100+x200)=(x+2x100+x200) (5)(x+x2+x3)+0=x+x2+x35、参考程序1：#define NULL 0#include stdio.htypedef 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;icoef=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 (xnext; 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-coef0) 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 %.0fn,p-coef); q=p-next; while (q) printf( %.0f, q-coef); printf( %dn, 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();程序21、实验目的 使学生熟练掌握单链线性表的基本操作 2、实验内容该程序的功能是创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删除一个元素，均保持链表的正序。在执行完每个操作后将其输出。3、实验要求 所使用的单链表最好带有附加的头节点，这样所涉及的程序比较简洁。参考程序2#include stdio.h#include alloc.h#include stdlib.h#include stddef.h/*节点定义*/typedef int datatype;typedef struct nodedatatype 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-datanext; 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-datanext; 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-quitn);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 isnt 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 dataMAXSIZE+1; /*非零元三元组表,data0未用*/ int mu,nu,tu;/*矩阵的行数、列数和非零元个数*/ tsmatrix; typedef struct triple dataMAXSIZE+1; /*非零元三元组表,data0未用*/ int rposMAXRC+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 en); for(k=1;k=M.tu;+k) scanf(%d %d %d,&M.datak.i,&M.datak.j,&M.datak.e); return(M);rlsmatrix rlcreate(int m,int n,int t) /*建立稀疏矩阵M的三元组顺序表*/ rlsmatrix M; int numMAXRC; int k,row; M.mu=m;M.nu=n;M.tu=t; printf(n please input %d data,M.tu); printf(ni j en); for(k=1;k=M.tu;+k) scanf(%d %d %d,&M.datak.i,&M.datak.j,&M.datak.e); for(row=1; row=M.mu;+row) numrow=0; /*求M中每一行含非零元个数*/ for(k=1;k=M.tu;+k) +numM.datak.i; M.rpos1=1; /* 求第row行中第一个非零元在 M.data中的序号*/ for(row=2; row=M.mu;+row) M.rposrow=M.rposrow-1+numrow-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.datak.i,M.datak.j,M.datak.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.datak.i,M.datak.j,M.datak.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.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return(T); tsmatrix fasttrans(tsmatrix M) /*快速转置*/ tsmatrix T; int col,p,q,t; int numMAXRC; int cpotMAXRC; T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu) for(col=1; col=M.nu;+col) numcol=0; for(t=1;t=M.tu;+t) +numM.datat.j; /*求M中每一列含非零元个数*/ cpot1=1; /* 求第col列中第一个非零元在 b.data中的序号*/ for(col=2; col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=M.tu;+p) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; return(T); rlsmatrix mult(rlsmatrix M, rlsmatrix N)/*求矩阵乘积QM*N,采用行逻辑链接存储表示*/ rlsmatrix Q; int arow,brow,ccol; int t,tp,p,q; int ctempMAXRC; 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) ctempccol=0; /*M当前行各元素累加器清零*/ Q.rposarow=Q.tu+1; if(arowM.mu) tp=M.rposarow+1; else tp=M.tu+1; for(p=M.rposarow;ptp;+p) brow=M.datap.j; if(browN.mu)t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt;+q) ccol=N.dataq.j; ctempccol+=M.datap.e*N.dataq.e; /*for q*/ /*for p*/ for(ccol=1;ccoldata=ch; s-lchild=s-rchild=NULL; rear+;qrear=s;if(rear=1) root=s;else if (s&qfront) if(rear%2=0)qfront-lchild=s; else qfront-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 0typedef char vextype;typedef int adjtype;/*定义邻接矩阵存放的图*/typedef struct vextype vexsn; adjtype arcsnn;graph;graph *ga1;/*定义邻接表存放的图*/typedef struct nodeint adjvex;struct node *next;edgenode;typedef structvextype vertex;edgenode *link;vexnode;vexnode ga2n;/*建立邻接矩阵*/creatgraph(ga)graph *ga;int i,j,k;printf(please input %d vexs for the graph!n,n);for(i=0;ivexsi=getchar();for(i=0;in;i+) for(j=0;jarcsij=0;for(k=0;karcsi