《数据结构实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告.doc（25页珍藏版）》请在三一办公上搜索。
1、实验一 实验名称：一元多项式相加（报告中浅蓝色的为修改或补充功能的代码）实验目的：练习并掌握如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。实验要求：能实现一元多项式的输入、输出，以及两个一元多项式相加及结果显示。实验内容：首先定义一个一元多项式的链表结构体，然后创建初始化链表函数initlink()、创建一个非空链表函数creatlink（）、求链表长度函数length（）、显示链表函数display（）、比较指数函数cmpexpn（）和两个一元多项式相加函数addPloyn（）留待在主函数中调用。在主函数中，首先定义需要的整数和整数数组、浮点数和浮点数数组和三个链表（本实验程
2、序实现的就是C=A+B），初始化这三个链表，然后分别输入这两个一元多项式的项数、每项的系数和指数，利用creatlink（）函数将这两个一元多项式的项数和每项的系数、指数分别装进链表A和B，然后将链表A和B存储的链式结构数据显示出来，最后调用addPloyn（）函数将两个链表中的数相加得到相加后的一元多项式，并显示出来。实验程序代码及运行结果：实验程序代码：#include#include#includeStdAfx.h#include #define null 0/*定义一元多项式的链表结构体*/typedef struct lnode float num; int expn; struct
3、 lnode *next;*linklist,lnode;/*创建一个空链表*/linklist initlink() linklist p; p=(lnode*)malloc(sizeof(lnode); p-next=null; return p;/*创建一个非空链表*/linklist creatlink(linklist p,float a,int b,int n) linklist r,s; int i; r=p; for(i=0;inum=ai; s-expn=bi; r-next=s; r=s; r-next=null; return p;/*求链表的长度*/int length
4、(linklist p) int n=0; linklist q=p-next; while(q!=null) n+; q=q-next ; return n;/*显示链表*/void display(linklist p) int n=length(p),i; linklist q=p-next; if(n=0) printf(The Polymial is nulln); else if(n=1) printf(%3.1f%3d,q-num,q-expn); else for(i=1;i,q-num,q-expn); q=q-next; printf(%3.1f%3d,q-num,q-ex
5、pn); printf(n);/*比较指数*/int cmpexpn(int expn1,int expn2) if(expn1expn2) return -1; else if(expn1=expn2) return 0; else return 1;/*两个一元多项式相加*/linklist addPolyn(linklist ha,linklist hb,linklist hc) linklist la,lb,lc,r; float sum; la=ha-next; lb=hb-next; lc=hc; while(la & lb) switch (cmpexpn(la-expn,lb-
6、expn) case -1: r=(lnode*)malloc(sizeof(lnode); r-num=lb-num; r-expn=lb-expn; lc-next=r; lc=r; r-next=null; lb=lb-next; break; case 0: sum=la-num+lb-num; if(sum!=0) r=(lnode*)malloc(sizeof(lnode); r-num=sum; r-expn=la-expn; lc-next=r; lc=r; r-next=null; la=la-next; lb=lb-next; else la=la-next; lb=lb-
7、next; break; case 1: r=(lnode*)malloc(sizeof(lnode); r-num=la-num; r-expn=la-expn; lc-next=r; lc=r; r-next=null; la=la-next; break; while(la) r=(lnode*)malloc(sizeof(lnode); r-num=la-num; r-expn=la-expn; lc-next=r; lc=r; r-next=null; la=la-next; while(lb) r=(lnode*)malloc(sizeof(lnode); r-num=lb-num
8、; r-expn=lb-expn; lc-next=r; lc=r; r-next=null; lb=lb-next; return lc;/*对链表进行排序*/linklist sortPolyn(linklist L) /此函数支持对乱序输入的多项式进行排序并且可以将同一个多项式中相同指数的项合并，实验结果请看最后一个截图 linklist p,q,r; for(p=L-next;p!=NULL;p=p-next) for(q=p-next;q!=NULL;q=q-next) if(p-expnq-expn) r=(lnode*)malloc(sizeof(lnode); r-num=p-
9、num; r-expn=p-expn; p-num=q-num; p-expn=q-expn; q-num=r-num; q-expn=r-expn; r-next=null; if(p-expn=q-expn)sum=p-num+q-num; if(sum!=0) p-num=sum; q-num=null; return L;/*主函数*/void main() int len1,len2; int i,n,a2100,b2100; float m,a1100,b1100; linklist A,B,C; A=initlink(); B=initlink(); C=initlink();
10、printf(Please input Polynomial As length:n); scanf(%d,&len1); printf(Please input Polynomial As num and expn:n); for(i=0;ilen1;i+) scanf(%f,&m); scanf(%d,&n); a1i=m; a2i=n; printf(Please input Polynomial Bs length:n); scanf(%d,&len2); printf(Please input Polynomial Bs num and expn:n); for(i=0;ilen2;
11、i+) scanf(%f,&m); scanf(%d,&n); b1i=m; b2i=n; creatlink(A,a1,a2,len1);creatlink(B,b1,b2,len2);sortPolyn(A);sortPolyn(B); printf(The Polynomial A is;n); display(A); printf(The Polynomial B is;n); display(B); addPolyn(A,B,C); printf(The Polynomials result is;n); display(C);运行结果如下三个图所示：实验二实验名称：栈的基本操作（报
12、告中浅蓝色的为修改或补充功能的代码）实验目的：掌握栈的结构特点并熟悉栈的基本操作。实验要求：编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能（两个选一个）：1、 采用链式存储实现栈的初始化、判空、入栈、出栈操作。2、 采用顺序存储实现栈的初始化、判空、入栈、出栈、求栈的长度操作。实验内容：首先定义一个栈结构，然后定义判断输入的数据非法问题的函数JudgeData（）、初始化栈函数InitStack（）、入栈函数Push（）、出栈函数Pop（）、显示栈顶函数Peek（）、显示栈中所有元素函数DisplayStack（）、判断栈空函数EmptyStack（）、清空栈函数Clea
13、rStack（）留待在主函数中调用。在主函数中，首先定义一个栈并且初始化栈，然后输入5个入栈元素，显示这5个入栈的元素，然后再输入一个入栈的元素，显示这个元素入栈后的栈顶，接着弹出栈中的两个元素，最后在显示栈中剩下的元素后清空栈。实验程序代码及运行结果：实验程序代码：#include stdafx.h#include#includeusing namespace std;typedef int ElemType;/*定义一个栈结构*/struct StackElemType *stack;int top;int MaxSize;/*判断输入的数据是否非法*/int JudgeData()cha
14、r c100;Judge:cinc; if(c0=-|c0=0&c0=9)for(int i=1;ci!=0;i+)if(ci9)cout您输入的数据非法！endl;cout请重新输入合法类型数据：;goto Judge;return atoi(c);elsecout您输入的数据非法！”endl;cout请重新输入合法类型数据：;goto Judge;/*栈的初始化*/void InitStack(Stack &S)S.MaxSize=10;S.stack=new ElemTypeS.MaxSize;if(!S.stack)cerr动态存储分配失败！endl;exit(1);elsecout栈
15、初始化成功！endl;S.top=-1;/*入栈操作*/void Push(Stack &S,ElemType item)if(S.top=S.MaxSize-1)int k=sizeof(ElemType);S.stack=(ElemType *)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;S.top+;S.stackS.top=item;coutitem 入栈成功endl;/*出栈操作*/ElemType Pop(Stack &S)if(S.top=-1)cerrStack is empty!endl;exit(1);S.top
16、-;return(S.stackS.top+1);/*显示栈顶元素*/void Peek(Stack &S)if(S.top=-1)cerrStack is empty!endl;exit(1);cout栈顶元素为：S.stackS.topendl;/*显示栈中的所有元素*/void DisplayStack(Stack S)if(S.top=-1)cout栈为空！endl;exit(1);else cout栈中所有元素为：endl;while(S.top!=-1)coutPop(S) ;coutendl;/*判断栈空*/void EmptyStack(Stack &S)if(S.top=-1
17、)cout栈已为空！endl;elsecout栈不为空！endl;/*清空栈*/void ClearStack(Stack &S)if(S.stack)delete S.stack;S.stack=NULL;S.top=-1;S.MaxSize=0;cout清空栈成功！endl;/*主函数*/int main(int argc, _TCHAR* argv) /修改后的主函数能够支持操作者选择要进行的操作，实验结果请看倒数两个截图int n,select;Stack S;InitStack(S);cout select:1-初始化栈；2-入栈操作；3-出栈操作；4-显示所有元素；5-显示栈顶元素
18、；6-清空栈endl;while(1)cout请输入下面要进行的操作，对应地选择1-6的一个值： select;switch(select)case 1:InitStack(S);break;case 2:cout请依次输入入栈的个数n：n;cout请依次输入入栈的n个元素：endl; for(int i=0;in;i+) Push(S,(ElemType)JudgeData();break;case 3:cout栈顶元素 Pop(S) 出栈成功！ endl;break;case 4:DisplayStack(S);break;case 5:Peek(S);break;case 6:Clear
19、Stack(S);break;default:return 0;break;return 0;运行结果如下三个图所示：实验三 实验名称：排序、查找的应用实验目的：学会如何应用排序算法和查找算法实现排序、查找。实验要求：先从键盘上输入26个字母生成无序数组，对数组进行排序，再从键盘输入一个字符进行查找。实验内容：跟前面程序一样，首先需要定义在主函数中需要调用的函数：结构体SequeList、冒泡排序函数BubbleSort（）、折半查找函数BinSearch（）和打印输出元素函数PrintLink（）；在主函数中，首先定义需要用到的整数、字符和顺序表L，然后输入26个字符（注意在编写输入字符的个
20、数时加上空格号，实际上输入了27个字符，所以for语句的结束句应该是i27），然后调用冒泡排序函数并显示排序后的字符，接着输入一个字符，调用折半查找函数找到这个字符在这组字符中的位置，如果这组字符中没有这个字符，给出提示。实验程序代码及运行结果：实验程序代码：#include stdafx.h#include#include#define MAX 50typedef char DataType;typedef struct /定义结构体SequeListDataType dataMAX;int length;SequeList;SequeList *Initist(SequeList *L)
21、/顺序表的初始化L=(SequeList *)malloc(sizeof(SequeList);L-length=-1;return L;SequeList *BubbleSort(SequeList *L) /冒泡排序int i,j;DataType temp;for(i=0;ilength;i+)for(j=i+1;jlength;j+)if(L-dataiL-dataj)temp=L-datai;L-datai=L-dataj;L-dataj=temp;return L;int BinSearch(SequeList *L,DataType k) /折半查找int low=0,high=
22、L-length-1,mid;while(lowdatamid=k)return mid;else if(L-datamidk)high=mid-1;elselow=mid+1;return -1;void PrintList(SequeList *L) /打印输出元素int i;for(i=0;ilength;i+)printf(%c ,L-datai);printf(n);int main() int i,t=0; DataType cc;SequeList *L;L=(SequeList *)malloc(sizeof(SequeList); L=Initist(L);L-length=
23、26;printf(请输入26个字符：n);for(i=0;idatai);L=BubbleSort(L);printf(此组字符排完序后为：n); PrintList(L);printf(请输入要查找的字符：n); scanf(%c,&cc); t=BinSearch(L,cc)+1;if(t=0) printf(此顺序表中没有该字符!n);else printf(此字符在顺序表中的第%d个位置n,t);return 0;运行结果如下三个图所示：实验四 实验名称：Huffman 编码实验目的：了解前缀编码的概念，理解数据压缩的基本方法； 掌握Huffman编码的设计思想并能熟练应用。实验要求
24、：对有字符集A，B，C，D，各字符在电文中出现的次数集为1,3,4,7；要求编程实现Huffman树的构造，并在此基础上编程实现Huffman编码。实验内容：本实验的程序依然跟前面的程序一样，定义调用的函数，然后再主函数中调用。而本实验中是先定义主函数然后再定义调用函数，这两者顺序颠倒没有影响。首先说一下，定义的调用函数有生成哈夫曼树函数CreatHuffmanTree（）、哈夫曼编码函数HuffmanCoding（）、PrintHuffmanCode（）和选择权值最小的两个结点的函数Select（）。然后再主函数中，先定义哈夫曼树HT、哈弗曼编码表HC、叶子节点数和存放叶子节点权值；然后给出
25、一个使用说明（这里使用有字符集A，B，C，D，各字符在电文中出现的次数集为1,3,4,7为例来引导读者怎样使用本程序来实现哈夫曼编码）；接着输入需要进行编码的字符个数和每个字符的权值，然后调用定义好的函数来实现输入字符的哈夫曼编码并显示出来。实验程序代码及运行结果：实验程序代码：#include stdafx.h#include #include #include #include #include #include#includeusing namespace std;typedef struct /定义哈夫曼树 int weight; /结点权值 int parent,lchild,rch
26、ild; /结点的父指针，左右孩子指针HTNode,*HuffmanTree;typedef char *HuffmanCode; /数组存储哈弗曼编码表void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); /生成哈夫曼树void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); /哈夫曼树编码void PrintHuffmanCode(HuffmanCode,unsigned int*,int); /显示编码结果void Select(HuffmanTree,int,int&,int&)
27、; /在数组中寻找权值最小的两个结点void main()HuffmanTree HT; /哈夫曼树HTHuffmanCode HC; /哈弗曼编码表HCint n,i; /n是哈夫曼树叶子节点数unsigned int *w; /w存放叶子结点权值couthuffman编码使用说明endl ; /使1用?说明cout例如：输入需要进行编码的字符个数：4endl;cout然后输入每个字符的权值（整数）：endl;cout例如：1 3 4 7 endl;cout则构造一棵哈夫曼书，哈弗曼编码如下endl;cout1-110endl 3-111endl4-10endl7-0endl;printf(
28、请输入需要进行编码的字符个数:);scanf(%d,&n); w=(unsigned int*)malloc(n*sizeof(unsigned int);printf(输入每个字符的权值（整数）:n);for(i=0;in;i+) scanf(%d,&wi); /输入个字符出现的次数/权值CreateHuffmanTree(HT,w,n); /生成哈夫曼树HuffmanCoding(HT,HC,n); /进行哈夫曼编码PrintHuffmanCode(HC,w,n); /显示哈弗曼编码void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w
29、,int n)/构造哈夫曼树int i,m;int s1,s2;HuffmanTree p;if(n=1) return;m=2*n-1; /n个叶子节点共需2*n-1个结点HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /开辟空间for(p=HT+1,i=1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0; for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0; for(i=n+1;i=m;+i) /建哈夫曼树 Select(HT,i-1,s1,s2); HTs1.par
30、ent=i; HTs2.parent=i; /修改s1和s2结点的父指针parent HTi.lchild=s1; HTi.rchild=s2; /修改i结点的左右孩子指针 HTi.weight=HTs1.weight+HTs2.weight; /修改权值指向在数组中的位置 void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)/将哈夫曼树进行编码，所编的码存放在HC，从叶子到根逆向求每个叶子结点的哈弗曼编码int i,c,f,start;char *cd;HC=(HuffmanCode)malloc(n+1)*sizeof(char
31、*); /分配n个编码的头指针向量cd=(char *)malloc(n*sizeof(char); /开辟一个求编码的工作空间cdn-1=0; /编码结束符for(i=1;i=n;+i) /逐个地求哈弗曼编码 start=n-1; /编码结束位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c) cd-start=0; /若是左孩子编为0else cd-start=1; /若是右孩子编为1 HCi=(char *)malloc(n-start)*sizeof(char); /为第i个编码分配空间 s
32、trcpy(HCi,&cdstart); /将编码从cd复制到HC中 free(cd); void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)/显示出入的n个叶子结点的哈夫曼树的编码表int i;printf(HuffmanCode is :n);for(i=1;i=n;i+) printf( %3d-,wi-1); puts(HCi); printf(n);/在HT1t中选择parent为0且权值最小的两个结点，器序号分别为s1和s2void Select(HuffmanTree HT,int t,int&s1,int&s2) int i,m,n;m=n=10000; for(i=1;i=t;i+) if(HTi.parent=0&(HTi.weightm|HTi.weightn)if(ms2) /s1放较小的序号 i=s1;s1=s2;s2=i;运行结果如下三个图所示：
