北京科技大学数据结构试验报告(附录含代码).docx

一、1)功能描述输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。2)详细设计遵循链表建立的基本思想，建立一个新的链表，H为表头，r为新节点，p为表尾节点指针，没存入一个新的数据则申请一个新的节点，知道没有数据输入，利用循环和打擂台法，比较和的大小，并输出。3)测试分析程序调试完成后，选取两组数据进行测试，都得出了正确结果（数据以0为结束符，若有相同和，则取第一组）结果截图4)心得体会通过做第一题，学习到链表的建立以及链表里指针的使用，并且复习了比较法里面的打擂台法。二、1)功能描述实现算术表达式求值程序（栈的运用），输入中缀表达式，可将其转换成后缀表达式2)详细设计本题目的程序是根据课本上的程序改进之后得出的，课本上有完整的程序，但是有bug，按照课本上的程序，结果会出现“烫烫烫烫烫”，原因是对于优先级的比较没有处理好，因此加了两行代码，将优先级的比较处理好，即现在的程序。3)测试分析程序调试完成后，选取题目所给的式子进行测试，得出了正确后缀表达式结果结果截图4)心得体会通过做第二题，对于课本上的知识表示得出“实践出真知”的真理，即使书上的东西也不一定就是正确的，尤其是代码，最好是个人自己真正实践一下。三、1)功能描述实现链式队列运算程序（队列的运用）2)详细设计本题目是队列相关应用，队列和栈是相反的，队列是先进的先出，因此输入12345，先出的是1，本着队列的这一特性，根据课本所学的队列的算法，设计了如下程序。3)测试分析程序调试完成后，选取12345进行测试，后缀加0，则一个字符出队，只输入0，则继续出队，输入，则打印剩余全部元素。结果截图4)心得体会通过做第三题，对于队列的特点有了更加深刻的认识，尤其区分队列与栈的不同点，需要特别注意。四、1)功能描述构造关于F的Huffman树；求出并打印D总各字符的Huffman编码。2)详细设计本题目是Huffman树的应用以及Huffman编码的应用，参照课本上关于Huffman树的建立以及Huffman编码的应用的实现，将所给数据依权值最小原则建立Huffman树，并实现Huffman编码。3)测试分析程序调试完成后，给出数据abcdefgh，相应频率为12345678，运行代码得出结果如图。同时选取另一组数据测试也得出了正确结论 结果截图4)心得体会通过做第四题，对于Huffman树有了更加深刻的体会，同时练习也使得对课本知识进行实践，有助于更好的理解Huffman树的算法。五、1)功能描述设英文句子：“everyone round you can hear you when you speak.”（1） 依次读入句中各单词，构造一棵二叉排序树；（2） 按LDR遍历此二叉排序树。LDR： can everyone hear round speak when you（有序）2)详细设计本题目是有关二叉树的建立和中序遍历的，二叉树作为数据存储一个很重要的结构，它的建立也是很重要的。本题目代码设计上采用课本上的对于二叉树建立的方法，将所给单词以二叉树形式建立并存储，然后中序遍历的到字典顺序。3)测试分析程序调试完成后，给出单词串everyone round you can hear you when you speak，运行代码得出中序遍历结果如图。结果截图4)心得体会通过做第五题，练习运用二叉树模型解决了一些实际问题如现实中字典的编排问题，在熟悉算法的基础上，同时得出结论，好的算法可以应用与实际生活生产，使之更为便捷。附录 程序代码实验一：#includestdio.h#includemalloc.htypedef struct node int data; struct node *next;list,*List;List Creatlist() /建立链表函数List H,p,r; /H为表头，r为新节点，p为表尾节点指针H=(List)malloc(sizeof(list); /建立头节点r=H; p=(List)malloc(sizeof(list); /申请新节点while(scanf(%d,p)&p-data!=0) /输入数据，直到为零（结束标志）r-next=p; /新节点链入表尾r=p;p=(List)malloc(sizeof(list); r-next=NULL; /将尾节点的指针域置空return H; /返回已创建的头节点List Adjmax(List H) /比较相邻两数之和 /返回相邻两数之和最大的第一个数指针List p,r,q;int sum=0;p=H-next;if(H-next =NULL) /判断是否为空printf(Empty List!);q=(List)malloc(sizeof(list);q-data =0;while(p!=NULL) /比较相邻两数之和r=p-next ;if(p&r)if(r-data+p-datasum)q=p;sum=r-data +p-data ;/不断赋给sum新的最大值else;p=p-next ;return q;int main()char ch;printf(/ 请输入整形数据，以空格隔开，0结束。/ n);printf(Ready? nY/N (enter y or Y to continue) n);while(scanf(%c,&ch)&(ch=Y|ch=y) List H,pmax;H=Creatlist(); pmax=Adjmax(H); printf(相邻两数之和最大的第一个数为：%dnContinue? Y/N ,pmax-data );free(H);scanf(%c,&ch);return 0;实验二：#include#include#includetypedef struct node /栈节点类型char data; /存储一个栈元素struct node *next; /后继指针snode,*slink;int Emptystack(slink S) /检测栈空if(S=NULL) return(1);else return(0);char Pop(slink*top) /出栈char e;slink p;if(Emptystack(*top) return(-1); /栈空返回elsee=(*top)-data; /取栈顶元素p=*top; *top=(*top)-next; /重置栈顶指针free(p);return(e);void Push(slink*top,char e) /进栈slink p;p=(slink)malloc(sizeof(snode); /生成进栈p节点p-data=e; /存入元素ep-next=*top; /p节点作为新的栈顶链入*top=p;void Clearstack(slink*top) /置空栈slink p;while(*top!=NULL)p=(*top)-next;Pop(top); /依次弹出节点直到栈空*top=p;*top=NULL;char Getstop(slink S) /取栈顶if(S!=NULL)return(S-data);return(0);/符号优先级比较int Precede(char x,char y) /比较x是否大于yswitch(x) case (:x=0;break;case +:case -:x=1;break;case *:case /:x=2;break;default: x=-1;switch(y)case +:case -:y=1;break;case *:case /:y=2;break;case (:y=3;break;default: y=100;if (x=y)return(1);else return(0);/中后序转换void mid_post(char post,char mid)/中缀表达式mid到后缀表达式post的转换的算法int i=0,j=0;char x;slink S=NULL;/置空栈Push(&S,#);/结束符入栈dox=midi+;/扫描当前表达式分量xswitch(x) case #: while(!Emptystack(S)postj+=Pop(&S);break;case ):while(Getstop(S)!=()postj+=Pop(&S);/反复出栈直至遇到（Pop(&S);/退掉（break;case +:case -:case *:case /:case (: while(Precede(Getstop(S),x)/栈顶运算符（Q1）与x比较postj+=Pop(&S);/Q1=x时，输出栈顶符并退栈Push(&S,x);/Q1front=Q-rear;int Emptyqueue(sq Q)if(Q-rear=Q-front)return 1;else return 0;void Enqueue(sq Q,char ch)if(Q-rear=max)printf(FULL QUEUE!);else Q-ch Q-rear=ch; Q-rear +;void Dequeue(sq Q)if(Emptyqueue(Q)printf(Empty QUEUE!n);elseprintf(出队：%cn,Q-chQ-front); Q-front +;void Printqueue(sq Q)if(Emptyqueue(Q) ; elseprintf(队列中全部元素：n);while(Q-front!=Q-rear-1)printf(%c,Q-chQ-front);Q-front+;printf(n);int main() sq Queue; char f; printf(*n); printf(请输入字符XnX 并且 X 字符入队；n); printf(X=0,字符出队；n); printf(X=,打印队列中各元素。n); printf(*n); Queue=(sq)malloc(sizeof(squeue); Queue-front =Queue-rear=0; while(scanf(%c,&f)&f!=) if(f!=0) Enqueue(Queue,f); else Dequeue(Queue); if(f=) Printqueue(Queue); else;return 0;实验四：#includestdio.h#includemalloc.h#define N 8#define MAX 100#define M 2*N-1typedef structchar letter;int w;int parent,lchild,rchild;Huffm;typedef structchar bitsN+1;int start;char ch;ctype;void inputHT(Huffm HTM+1)int i;for(i=1;i=M;i+)HTi.w=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0; printf(请输入电文字符集：);for(i=1;i=N;i+)scanf(%c,&HTi.letter ); printf(请输入字符出现的频率：);for(i=1;i=N;i+)scanf(%d,&HTi.w );void CreatHT(Huffm HTM+1)int i,j,min1,min2;int tag1,tag2; /权值最小两个点标号； for(i=N+1;i=M;i+)tag1=tag2=0;min1=min2=MAX;for(j=1;j=i-1;j+)if(HTj.parent =0)if(HTj.w min1)min2=min1;min1=HTj.w;tag2=tag1;tag1=j;elseif(HTj.w min2)min2=HTj.w;tag2=j;HTtag1.parent =HTtag2.parent =i;HTi.lchild =tag1;HTi.rchild =tag2;HTi.w =HTtag1.w +HTtag2.w; void Huffmcode(Huffm HTM+1) / Huffm编码函数 int i,j,p,tag;ctype mcode,codeN+1;for(i=1;i=N;i+) codei.ch=HTi.letter;for(i=1;i=N;i+)mcode.ch =codei.ch;mcode.start=N+1; tag=i;p=HTi.parent ;for(j=0;j=N;j+)mcode.bits j= ;while(p!=0)mcode.start-;if(HTp.lchild =tag)mcode.bitsmcode.start =0;elsemcode.bits mcode.start =1;tag=p;p=HTp.parent ;codei=mcode;for(i=1;i=N;i+)printf( %c的Huffm编码为：,codei.ch ); for(j=0;jword,p-word)=0 )free(s);return T;if( strcmp(s-word,p-word)lchild ;elsep=p-rchild ;if(strcmp(s-word ,f-word)lchild=s ;elsef-rchild=s ;return T;BST CreatBst()BST T,s;char keyword20;T=NULL;gets(keyword);while(keyword0!=0)s=(BST)malloc(sizeof(BStree);strcpy(s-word,keyword);s-lchild=s-rchild=NULL;T=BSTinsert(T,s);gets(keyword);return T;void Inorder(BST T)if(T)Inorder(T-lchild );printf(%s ,T-word );Inorder(T-rchild );int main()char ch;BST T;printf(*n);printf(请输入英文句子，每输入一个单词以回车结束，句子结束以0结束。n); printf(*n);ch=y;while(ch=Y|ch=y)T=CreatBst();printf(按LDR遍历此二叉排序树(字典顺序):n);Inorder(T);free(T);printf(nContinue? Y/N );scanf(%c,&ch);