数据结构实验报告

1、实验一输入数据(设为整型)建立单链表，并求相邻两节点data值之和为最大的第一节点。例如输入：264730(0为结束符)运行代码：#include"stdio.h”#include"malloc.h”typedefstructnode{intdata;structnode*next;}list,*List;ListCreatlist() 〃建立链表函数{ListH,p,r;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;returnH;}ListAdjmax(ListH)〃比较相邻两数之和{ 〃返回相邻两数之和最大的第一个数指针Listp,r,q;intsum=0;p=H->next;if(H->next==NULL)//判断是否为空{printf("EmptyList!");q=(List)malloc(sizeof(list));q->data=0;}while(p!=NULL)〃比较相邻两数之和{r=p->next;if(p&&r)if(r->data+p->data>sum){q=p;sum=r->data+p->data;}else;p=p->next;}returnq;}intmain(){charch;printf("///请输入整形数据，以空格隔开，0结束。///\n");printf("Ready?Y/N");while(scanf("%c”,&ch)&&(ch=='Y'||ch=='y')){ListH,pmax;H=Creatlist();pmax=Adjmax(H);printf("相邻两数之和最大的第一个数为：%d\nContinue?Y/N",pmax->data);free(H);scanf("%c",&ch);}return0;}运行结果：2、实验二实现算术表达式求值程序（栈的运用）设操作数：0，1，2,……，8,9（可扩充）；运算符：+，—，*，/，（，），#（#号为结束）。输入中缀表达式，如：5+（4-2）*3#，将其转换成后缀表达式：542-3*+#，然后计算，本例结果为11。运行代码：#include"stdio.h"#include"string.h"#include"stdlib.h"#defineMAX100typedefstruct〃定义操作符结构体{charop; //操作符intlevel;//操作符优先顺序}opt;typedefstruct//表达式栈{optst[MAX];inttop;}op_stack;typedefstruct//双精度操作数栈{doubled[MAX];inttop;}data_stack;optget(op_stack*s)〃栈顶字符函数{opterror={'$',-2};if(s->top>=0)returns->st[s->top];elsereturnerror;}intIsEmpty(op_stack*s)//判断栈是否为空{if(s->top<0)return0;elsereturns->st[s->top].op;}charpush(op_stack*s,optc)〃进栈函数{s->top++;s->st[s->top]=c;returnc.op;}optpop(op_stack*s)〃出栈函数{opti;opterror={'$',-2};if(s->top>=0){i=s->st[s->top];s->st[s->top].op='\0';s->top--;returni;}elsereturnerror;}voidclear(op_stack*s)//清空栈{s->top=-1;}doubledget(data_stack*s)//双精度操作数栈取栈顶{if(s->top>=0)returns->d[s->top];elsereturn0;}intDIsEmpty(data_stack*s)//判断操作数栈是否为空{if(s->top<0)return0;elsereturn(int)(s->d[s->top]);}doubledpush(data_stack*s,doublec)//操作数进栈{s->top++;s->d[s->top]=c;returnc;}doubledpop(data_stack*s)//操作数出栈{doublei;if(s->top>=0){i=s->d[s->top];s->d[s->top]='\0';s->top--;returni;}elsereturn0;}voiddclear(data_stack*s)//操作数栈清空s->top=-1;}voidmidpost(char*str,char*expr,char*kkk)/中缀转换后缀{optA={'+',1};optR={'-',1};optM={'*',2};optD={'/',2};optB={'(',-1};op_stackos;clear(&os);while(*str!='#'){while(*str>='0'&&*str<='9'||*str='.')//筛选数字与.{ 〃存入后缀表达式*expr=*str;expr++;str++;}*expr++='';//数字之间以空格隔开switch(*str)//处理操作符{case'+':while(get(&os).level>=A.level&&IsEmpty(&os)){*expr++=pop(&os).op;〃优先顺序高进栈}push(&os,A);str++;break;case'-':while(get(&os).level>=R.level&&IsEmpty(&os)){*expr++=pop(&os).op;//栈顶元素优先级高出栈}push(&os,R);〃进栈str++;break;case'*':while(get(&os).level>=M.level&&IsEmpty(&os)){*expr++=pop(&os).op;//栈顶元素优先级高出栈}push(&os,M);//进栈str++;break;case'/':while(get(&os).level>=D.level&&IsEmpty(&os)){*expr++=pop(&os).op;//栈顶元素优先级高出栈}push(&os,D);//否则进栈str++;break;case'(':push(&os,B);//进栈str++;break;case')':while(get(&os).op!='(')〃出栈直到遇到(’{*expr++=pop(&os).op;}pop(&os);str++;break;}}while(IsEmpty(&os))〃输出余下字符{*expr++=pop(&os).op;}*expr++='#';〃结束标志}doublecount(char*ch)〃计算后缀表达式值{data_stackData;inti,len,j=0;doubleresult=0;doubletmpdata,tmp1;chartmp[MAX]={'\0'};dclear(&Data);while(*ch!='#'){j=0;if(*ch=='')ch++;else{while(*ch>='0'&&*ch<='9'll*ch=='.')//将数字字符与.拼成数字{tmp[j++]=*ch++;}tmp[j++]='\0';tmp1=atof(tmp);//字符串转化成浮点数if(j!=1)dpush(&Data,tmp1);〃只有转化成浮点数之后进操作数栈len=strlen(tmp);for(i=0;i<len;i++)tmp[i]='\0';}if(*ch=='+'){result=dpop(&Data)+dpop(&Data);dpush(&Data,result);ch++;}elseif(*ch=='-'){tmpdata=dpop(&Data);result=dpop(&Data)-tmpdata;/冼出栈为减数，后出栈为被减数dpush(&Data,result);ch++;}elseif(*ch=='*'){result=dpop(&Data)*dpop(&Data);dpush(&Data,result);ch++;}elseif(*ch=='/'){tmpdata=dpop(&Data);result=dpop(&Data)/tmpdata;//先出栈为除数，后出栈为被除数dpush(&Data,result);ch++;}}returnresult;}intmain()charc;c='y';while(c=='y'llc=='Y'){charstring[MAX];charexp[MAX]={'\0'};char*myexp;myexp=exp;puts("请输入表达式以‘#’结束：，gets(string);midpost(string,exp,myexp);printf("后缀表达式：％s\n”,exp);printf("表达式结果：%f\n",count(exp));printf("continue?y/n\n");fflush(stdin);scanf("%c”,&c);fflush(stdin);}}运行结果：情输入表达式以F'蜻束：后缀表达式：132^+23/+tt关达式结果！7.65G667continue?y/n蓄输入表达式以W结束：1+3x(2.5/0.5)tt后嫌表达式！132.50.5彩+首表达式结果：16.眄腿continue?y/nnPreGSanykeytocontinue3、实验三实现队列运算程序(队列的运用)运行代码：#include"stdio.h”#include"malloc.h”#definemax1000typedefstructnode{charch[max];intfront,rear;}squeue,*sq;voidClearqueue(sqQ){Q->front=Q->rear;}intEmptyqueue(sqQ){if(Q->rear==Q->front)return1;elsereturn0;}voidEnqueue(sqQ,charch){if(Q->rear>=max){printf("FULLQUEUE!");}else{Q->ch[Q->rear]=ch;Q->rear++;}}voidDequeue(sqQ){if(Emptyqueue(Q)){printf("EmptyQUEUE!\n");}else{printf("出队：%c\n",Q->ch[Q->front]);Q->front++;}}voidPrintqueue(sqQ){if(Emptyqueue(Q));else{printf("队列中全部元素:\n");while(Q->front!=Q->rear-1)printf("%c”,Q->ch[Q->front]);Q->front++;}printf("\n");}}intmain(){sqQueue;charf;printf("*******************************************\n");printf（"请输入字符X\nX己'@'并且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);elseDequeue(Queue);}if(f=='@')Printqueue(Queue);else;return0;}运行结果：■1'I;僵据蜡构kMbugkt吕13.由出,请输入字符XkH且X兰宜字符八队；字符出队;卜W,打印队列中各元素。123450LjFa：1D2abcdef队礼，”宝答元素：345abcd&fPressanykeytocontinue4、实验四设电文字符集D及各字符出现的概率F如下：D={a,b,c,d,e,f,g,h}(字符数n=8)F={5,29,7,8,14,23,3,11}(%)编写完成下列功能的程序：构造关于F的Huffman树；求出并打印D中各字符的Huffman编码。运行代码：#include"stdio.h”#include"malloc.h”#defineN8#defineMAX100#defineM2*N-1typedefstruct{charletter;intw;intparent,lchild,rchild;}Huffm;typedefstruct{charbits[N+1];intstart;charch;}ctype;voidinputHT(HuffmHT[M+1]){inti;for(i=1;i<=M;i++){HT[i].w=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}printf(-请输入电文字符集：”)；for(i=1;i<=N;i++){scanf("%c”,&HT[i].letter);}printf("请输入字符出现的频率：”)；for(i=1;i<=N;i++){scanf("%d”,&HT[i].w);}voidCreatHT(HuffmHT[M+1]){inti,j,min1,min2;inttag1,tag2; 〃权值最小两个点标号；for(i=N+1;i<=M;i++){tag1=tag2=0;min1=min2=MAX;for(j=1;j<=i-1;j++){if(HT[j].parent==0)if(HT[j].w<min1){min2=min1;min1=HT[j].w;tag2=tag1;tag1=j;}elseif(HT[j].w<min2){min2=HT[j].w;tag2=j;}}HT[tag1].parent=HT[tag2].parent=i;HT[i].lchild=tag1;HT[i].rchild=tag2;HT[i].w=HT[tag1].w+HT[tag2].w;}}voidHuffmcode(HuffmHT[M+1])//Huffm编码函数{inti,j,p,tag;ctypemcode,code[N+1];for(i=1;i<=N;i++){code[i].ch=HT[i].letter;}for(i=1;i<=N;i++){mcode.ch=code[i].ch;mcode.start=N+1;tag=i;p=HT[i].parent;for(j=0;j<=N;j++)mcode.bits[j]='';while(p!=0){mcode.start--;if(HT[p].lchild==tag)mcode.bits[mcode.start]='0';elsemcode.bits[mcode.start]='1';tag=p;p=HT[p].parent;}code[i]=mcode;}for(i=1;i<=N;i++){printf("'%c'的Huffm编码为：”,code[i].ch);for(j=0;j<=N;j++)printf("%c”,code[i].bits[j]);printf("\n");}}intmain(){charch;c*/1f*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1* tf\pnntT(******************************************************\n);printf（-电文字符集含8个字符，连续输入，不同频率之间以空格隔开\n"）;c*/1f*1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1**1* tf\pnntT(******************************************************\n);ch='y';while(ch=='y'){HuffmHT[M+1];inputHT(HT);CreatHT(HT);Huffmcode(HT);printf("Continue?Y/N");fflush(stdin);scanf("%c”,&ch);fflush(stdin);}}运行结果："C:\Users\Administrator.ZGC-20110213KXS\Deslctcip嗽健百陌Debug\test4.exe'电文字符集含日个字符，连续输入,F同频率之间以空格隔开请输入电文字符第!abcdwfgh至咆入字寿门现率；12345G78的Hufm蝙码为: 11110的HuFfm园坯'小 11111的Huffin病口为： 1110F'仙伫灼： 100•寸的Nu"ni务臼为： 101•F'的HuFfin击:内为： 110P'仙Hilf刊辟门为； 0001Continue?V/Ny请输入电文字符果!abiinpqxy定前入字芍昌戋的■:率：1243G587・/的HllffH编码为: 1111011111密’仙Huf预薛门为； 100・L的Huffn编码为, 1110•p'的Huffin窝伺：妇： 11Q•q'的Hiiffin病.口却： 101I'tljHiiF和坛口为： 01,『的Nu"m如但廿 00Continue??/NnPressmnqkeijtocontinue5、实验五设英文句子：“everyoneroundyoucanhearyouwhenyouspeak试编写完成下面任务的程序。运行代码：#include"stdio.h”#include"malloc.h”#include"string.h”typedefstructbsnode{charword[20];structbsnode*lchild,*rchild;}BStree,*BST;BSTBSTinsert(BSTT,BSTs){BSTf,p;if(T==NULL)returns;p=T;f=NULL;while(p){f=p;if(strcmp(s->word,p->word)==0){free(s);returnT;}if(strcmp(s->word,p->word)<0)p=p->lchild;elsep=p->rchild;}if(strcmp(s->word,f->word)<0)f->lchild=s;elsef->rchild=s;returnT;}BSTCreatBst(){BSTT,s;charkeyword[20];T=NULL;gets(keyword);while(keyword[0]!='0'){s=(BST)malloc(sizeof(BStree));strcpy(s->word,keyword)