数据结构实验汇总

1、实验一：针对链式或顺序存储的线性表实现指定的操作题1 问题描述：有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。基本要求：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。#include <iostream>using namespace std;typedef struct Poly/定义一个多项式float coef;/多项式系数int exp;/多项式指数struct Poly *next;Poly;typedef Poly *Polynomi

2、al;/重定义一个多项式名字 void creatPoly(Polynomial &P,int n)P = new Poly;P->next=NULL; Poly *p,*q;p=P; for(int i=1;i<=n;i+)q=new Poly; cout<<"第"<<i<<"项的系数："cin>>q->coef;/输入系数 cout<<"第"<<i<<"项的指数："cin>>q->ex

3、p;q->next=NULL;p->next=q;p=q; int lengthPoly(Polynomial &P)/计算多项式项数的函数Poly *p;int i; p=P->next;i=0; while(p!=NULL)p=p->next;i+;return i; void outputPoly(Polynomial &P)/输出合并后的多项式Poly *p;p=P->next; int i;for(i=0;i<lengthPoly(P);i+)cout<<p->coef<<" "&l

4、t;<p->exp<<" +"p=p->next;cout<<"0"<<endl; Poly * addPoly(Polynomial &Pa,Polynomial &Pb)/A与B相加Poly *p,*q,*h,*s; p=Pa->next;q=Pb->next; h=Pa; while (p&&q)/A与B都不为0if(p->exp<q->exp)/A的指数小于B的指数Pb->next=q->next;s=q;h->n

5、ext=s;s->next=p;h=s; q=Pb->next;else if(p->exp > q->exp)/A的指数大的话h=p;p=p->next;else/A与B的指数相等的话p->coef=p->coef+q->coef;/A与B对应项系数求和if(p->coef=0)/系数和为0Poly *temp1;Poly *temp2;temp1=p;temp2=q;h->next=p->next;/删除该项数p=p->next;q=q->next;delete temp1;delete temp2;els

6、e/A与B的指数相等的话,系数和不为0Poly *temp;temp=q; h=p;p=p->next;q=q->next;delete temp;if(q) h->next=q; delete Pb;return Pa;void main()Polynomial Pa,Pb,Pc;/定义三个多项式类型的变量int a,b;/a,b为两个多项式的整体的项数cout<<"请输入第一个一元多项式的项数:"cin>>a;cout<<"请输入第二个一元多项式的项数:"cin>>b;cout<

7、<"请输入一元"<<a<<"项式(先输入系数，再输入指数):"creatPoly(Pa,a); cout<<"请输入一元"<<b<<"项式(先输入系数，再输入指数):"creatPoly(Pb,b);Pc=addPoly(Pa,Pb);cout<<"相加得到的多项式:"outputPoly(Pc);#include <iostream>using namespace std;t

8、ypedef struct Poly/定义一个多项式float coef;/多项式系数int   exp;/多项式指数struct Poly *next;Poly;typedef Poly *Polynomial;/重定义一个多项式名字  void creatPoly(Polynomial &P,int n)P = new Poly;P->next=NULL; Poly *p,*q;

9、p=P; for(int i=1;i<=n;i+)q=new Poly;cout<<"第"<<i<<"项的系数："cin>>q->coef;cout<<"第"<<i<<"项的指数："cin>>q->exp;q->next=NULL;p->next=q;p=q; int lengthPoly(Polynomial &P)/计算

10、多项式项数的函数Poly *p;int i; p=P->next;i=0; while(p!=NULL)p=p->next;i+;return i; void outputPoly(Polynomial &P)/输出合并后的多项式Poly *p;p=P->next; int i;for(i=0;i<lengthPoly(P);i+)cout<<p->coef<<" "<<p->

11、exp<<" +"p=p->next;cout<<"0"<<endl; Poly * addPoly(Polynomial &Pa,Polynomial &Pb)/A与B相加Poly *p,*q,*h,*s; p=Pa->next;q=Pb->next; h=Pa; while (p&&q)/A与B都不为0if(p->exp<q->exp)/A

12、的指数小于B的指数Pb->next=q->next;s=q;h->next=s;s->next=p;h=s; q=Pb->next;else if(p->exp > q->exp)/A的指数大的话 h=p;p=p->next;else/A与B的指数相等的话p->coef=p->coef+q->coef;/A与B对应项系数求和if(p->coef=0)/系数和为0Poly *temp1;Poly *temp2;temp1=p;temp2=q;h->nex

13、t=p->next;/删除该项数p=p->next;q=q->next;delete temp1;delete temp2;else/A与B的指数相等的话,系数和不为0Poly *temp;temp=q; h=p;p=p->next;q=q->next;delete temp;if(q)  h->next=q;   delete Pb;return Pa;Poly * mulPoly(Polynomial &a

14、mp;Pa,Polynomial &Pb)/A与B相乘Poly *p,*q,*h,*m;    Poly *a,*b,*c;Polynomial Pc=new Poly;Polynomial Pd=new Poly;Pd->next=NULL;c=Pd; p=Pa->next;q=Pb->next;    m=Pc;if(p&&q)/A与B都不为0while(q)  

15、0;     p=Pa->next;    while(p)/A的每一项与B的第一项相乘         h=new Poly;                 h->coef=p->coef*q->coef;/系数相乘

16、60;            h->exp=p->exp+q->exp;/指数相加                 m->next=h; h->next=NULL; m=h;     p=p->next;

17、           if(!Pd->next)/当Pd为空，将Pc的值复制到Pd中               a=Pc->next;            while(a)  

18、0;           b=new Poly;             b->coef=a->coef;              b->exp=a->exp;    

19、60;        b->next=NULL;             c->next=b;c=b;a=a->next;                q=q->next;    &#

20、160;         else                  Pd=addPoly(Pd,Pc);       q=q->next;       return Pd;

21、void main()Polynomial Pa,Pb,Pd;/定义三个多项式类型的变量int a,b;/a,b为两个多项式的整体的项数cout<<"请输入第一个一元多项式的项数:"cin>>a;cout<<"请输入第二个一元多项式的项数:"cin>>b;cout<<"请输入一元"<<a<<"项式(先输入系数，再输入指数):"creatPoly(Pa,a);    

22、;cout<<"请输入一元"<<b<<"项式(先输入系数，再输入指数):"creatPoly(Pb,b);    Pd=mulPoly(Pa,Pb);cout<<"相乘得到的多项式:"outputPoly(Pd);实验二：使用栈或队列解决一个应用问题问题描述 设计一个模拟计算器功能的程序，它读入一个表达式，如果是一个正确的表达式（即它由操作数、圆括号和+、-、*、/四种运算符组成），则求出该表达式的值；否则给出某种错误信息。基本要求：读入一个以字符

23、序列形式给出的以等号（=）结尾的表达式；程序中应考虑运算符的优先级、运算的合法性。#include<iostream>#include <stdio.h> #include <stdlib.h> #include <string.h> #define OK 1#define ERROR 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20using namespace std;typedef struct /定义字符类型栈 int stacksize; char *base; char *

24、top; Stack1; typedef struct / 定义整型栈 int stacksize; int *base; int *top; Stack2;Stack1 OPTR; / 定义运算符栈Stack2 OPND; / 定义操作数栈char InitStack1(Stack1 &S) /构造运算符栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S.base) exit(1); S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK;int InitStac

25、k2(Stack2 &S)S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); /构造操作数栈if(!S.base) exit(1);S.top=S.base;S.stacksize = STACK_INIT_SIZE;return OK;bool In(char ch) /判断字符是否是运算符，运算符即返回1 if(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='=') return

26、true; else return false; char Push1(Stack1 &S,char ch) /运算符栈插入ch为新的栈顶元素 *S.top+=ch; return 0; int Push2(Stack2 &S,int ch) /操作数栈插入ch为新的栈顶元素 *S.top+=ch;return 0;char Pop1(Stack1 &S,char&e) /删除运算符栈s的栈顶元素，用e返回其值 e = *-S.top; return e;int Pop2(Stack2 &S,int&e) /删除操作数栈s的栈顶元素，用e返回其值

27、e = *-S.top;return e;char GetTop1(Stack1 &S) /用e返回运算符栈s的栈顶元素 char e;if(S.top=S.base) exit(1);e=*(S.top-1); return e; int GetTop2(Stack2 &S) /用e返回操作数栈s的栈顶元素int e;if(S.top=S.base) exit(1); e=*(S.top-1); return e; char OPSET7='+' , '-' , '*' , '/' ,'(' ,

28、')' , '='char Precede(char c1,char c2) / 判断运算符优先权，返回优先权高的 int i=0,j=0; static char array77='>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', &

29、#39;>', '>','>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>','<', '<', '<',

30、 '<', '<', '=', '!','>', '>', '>', '>', '!', '>', '>','<', '<', '<', '<', '<', '!', '=' switch(c1)case '+' :

31、i=0; break;case '-' : i=1; break;case '*' : i=2; break;case '/' : i=3; break;case '(' : i=4; break;case ')' : i=5; break;case '=' : i=6; break; switch(c2)case '+' : j=0; break;case '-' : j=1; break;case '*' : j=2; break;case 

32、9;/' : j=3; break;case '(' : j=4; break;case ')' : j=5; break;case '=' : j=6; break; return (arrayij); /返回运算符int Operate(int a,char op,int b) /运算执行函数 switch(op)case '+' : return (a+b);case '-' : return (a-b);case '*' : return (a*b);case '/'

33、 : return (a/b);return 0;int main( ) printf("请输入正确的表达式以'='结尾:"); char c,x,theta;int a,b;Stack1 OPTR;Stack2 OPND;InitStack1(OPTR); Push1(OPTR,'=');InitStack2(OPND); c=getchar(); while(c!='='|GetTop1(OPTR)!='=') if(!In(c) Push2(OPND,c-'0');c=getchar();

34、 else switch(Precede(GetTop1(OPTR),c) case '<': Push1(OPTR,c);c=getchar(); break; case '=':Pop1(OPTR,x); c=getchar(); break; case '>':Pop1(OPTR,theta);Pop2(OPND,b); Pop2(OPND,a); Push2(OPND,Operate(a,theta,b); break; cout<< GetTop2(OPND)<<endl; return 0;实验三：

35、实现对二叉树的一个指定的操作或用二叉树解决一应用问题问题描述：对任意输入的一段英文，为每个字符编制其相应的赫夫曼编码；并利用该编码为任意输入的0、1序列进行解码 基本要求：一个完整的系统应具有以下功能：（1）初始化 从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件；（2）编码 利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中； （3）解码 利用保存的赫夫曼编码，对任意输入的0，1序列能正确解码； #include<stdio.h>#define n 6 /叶子数目#define m (2*n-1) /结点总数#

36、define maxval 10000.0#define maxsize 100 /哈夫曼编码的最大位数typedef struct char ch; float weight; int lchild,rchild,parent;hufmtree;typedef struct char bitsn; /位串 int start; /编码在位串中的起始位置 char ch; /字符codetype;void huffman(hufmtree tree)/建立哈夫曼树 int i,j,p1,p2;/p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标 float small1,small2

37、,f; char c; for(i=0;i<m;i+) /初始化 treei.parent=0; treei.lchild=-1; treei.rchild=-1; treei.weight=0.0; printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】n",n); for(i=0;i<n;i+) /读入前n个结点的字符及权值 printf("输入第%d个字符为和权值",i+1); scanf("%c %f",&c,&f); getchar(); treei.ch=c; treei.wei

38、ght=f; for(i=n;i<m;i+) /进行n-1次合并，产生n-1个新结点 p1=0;p2=0; small1=maxval;small2=maxval; /maxval是float类型的最大值 for(j=0;j<i;j+) /选出两个权值最小的根结点 if(treej.parent=0) if(treej.weight<small1) small2=small1; /改变最小权、次小权及对应的位置 small1=treej.weight; p2=p1; p1=j; else if(treej.weight<small2) small2=treej.weig

39、ht; /改变次小权及位置 p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; /最小权根结点是新结点的左孩子 treei.rchild=p2; /次小权根结点是新结点的右孩子 treei.weight=treep1.weight+treep2.weight; /huffmanvoid huffmancode(codetype code,hufmtree tree)/根据哈夫曼树求出哈夫曼编码/codetype code为求出的哈夫曼编码/hufmtree tree为已知的哈夫曼树 int i,c,p; codetype cd; /

40、缓冲变量 for(i=0;i<n;i+) cd.start=n; cd.ch=treei.ch; c=i; /从叶结点出发向上回溯 p=treei.parent; /treep是treei的双亲 while(p!=0) cd.start-; if(treep.lchild=c) cd.bitscd.start='0' /treei是左子树，生成代码'0' else cd.bitscd.start='1' /treei是右子树，生成代码'1' c=p; p=treep.parent; codei=cd; /第i+1个字符的编码

41、存入codei /huffmancodevoid decode(hufmtree tree)/依次输入，根据哈夫曼树译码 int i,j=0; char bmaxsize; char endflag='2' /结束标志取2 i=m-1; /从根结点开始往下搜索 printf("输入发送的编码(以'2'为结束标志)："); gets(b); printf("译码后的字符为"); while(bj!='2') if(bj='0') i=treei.lchild; /走向左孩子 else i=tr

42、eei.rchild; /走向右孩子 if(treei.lchild=-1) /treei是叶结点 printf("%c",treei.ch); i=m-1; /回到根结点 j+; printf("n"); if(treei.lchild!=-1&&bj!='2') /读完，但尚未到叶子结点 printf("nERRORn"); /输入有错/decode void main() printf(" 哈夫曼编码n"); printf("总共有%d个字符n",n); h

43、ufmtree treem; codetype coden; int i,j;/循环变量 huffman(tree);/建立哈夫曼树 huffmancode(code,tree);/根据哈夫曼树求出哈夫曼编码 printf("【输出每个字符的哈夫曼编码】n"); for(i=0;i<n;i+) printf("%c: ",codei.ch); for(j=codei.start;j<n;j+) printf("%c ",codei.bitsj); printf("n"); printf("【输

44、入代码，并进行译码】n"); decode(tree);/依次输入，根据哈夫曼树译码实验四：实现对图的一个指定的操作或用图解决一个应用问题问题描述：n个村庄之间的无向图，边上的权值w(i,j)表示村庄i和j之间道路长度现要从这n个村庄中选择一个村庄新建一所医院，使离医院最远的村庄到医院的路程最短设计一程序求解此问题 基本要求：用邻接矩阵表示无向网，应显示所选中的村庄到各村庄的最短距离。#include<iostream>#include<string>using namespace std;#define INFINITY

45、0; 100000 /最大值，表示两顶点不邻接#define MAX_VERTEX_NUM 30  /最大顶点个数typedef struct Arcelldouble adj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/定义邻接矩阵typedef struct string verxMAX_VERTEX_NUM;/定义顶点向量AdjMatrix arcs;int vexnum,arcnum;MGraph;/

46、定义无向图int LocateVex(MGraph &G,string v)      int i=0;      for(i;i<G.vexnum;i+)             if(G.verxi=v)       &#

47、160;   return i;        return -1;int CreateUDN(MGraph &G)        int i,j,k; string v1,v2;double w;      cout<<"请输入村庄的数目

48、"<<endl;      cin>>G.vexnum;      cout<<"请输入村庄之间直接相通的道路数"<<endl;      cin>>G.arcnum;      for( i=0;i<G.vexnum;i+)  &#

49、160;     cout<<"请输入村庄"<<i+1<<"的名称"<<endl;      cin>>G.verxi;        for(i=0;i<G.vexnum;i+)          &#

50、160;  for(j=0;j<G.vexnum;j+)        G.arcsij.adj=INFINITY;      /初始化邻接矩阵      for(k=0;k<G.arcnum;k+)          cout<<"请输入第"&

51、lt;<k+1<<"线路的起点，终点，以及权值"<<endl;          cin>>v1>>v2>>w;          i=LocateVex(G,v1);j=LocateVex(G,v2);         &

52、#160;G.arcsij.adj=w;          G.arcsji.adj=G.arcsij.adj;       return 0;void ShortestPathFLOYD(MGraph G,string P20,double D20)       int v,w,u; &

53、#160;     for(v=0;v<G.vexnum v+)       for(w=0;w<G.vexnum w+)               Dvw=G.arcsvw.adj          &#

54、160;         if(Dvw<INFINITY)            Pvw=G.verxv+"->"+G.verxw;/初始化路径数组          for(u=0;u<G.vexnum u+)  

55、60;    for(v=0;v<G.vexnum v+)       for(w=0;w<G.vexnum w+)            if(Dvu+Duw<Dvw)                  Dvw=Dvu+Duw;