北科大数据结构上机题代码

1、数据结构上机题（C语言程序）1输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。例如输入：2 6 4 7 3 0（0为结束符），建立： 所求结果=4 程序结构： 类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( ) 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止 上机题1：#include#includetypedef int datatype; /设当前数据元素为整型 typedef struct node /节点类型 datatype data

2、; /节点的数据域 struct node *next; /节点的后继指针域 Linknode,*Link; /linknode为节点说明符，link为节点指针说明符 Link Createlist() /创建单链表的算法 int a,c;float b;Link H,P,r; /H,P,r分别为表头，新节点和表尾节点指针 H=(Link)malloc(sizeof(Linknode); /建立头节点 r=H;doc=(fflush(stdin),scanf(%f,&b); /判断输入的是否是整数a=(int)b;if(c!=1|a!=b|a-216|a-216|adata=a; /存入数据

3、r-next=P; /新节点链入表尾 r=P;doc=(fflush(stdin),scanf(%f,&b); /判断输入的是否是整数a=(int)b;if(c!=1|a!=b|a-216|a-216|anext=NULL; /将尾节点的指针域置空 return(H); /返回已创建的头节点 Link Adjmax(Link H) /求链表中相邻两节点data值之和为最大的第一节点的指针的算法 Link p,p1,q;int i,j;p=p1=H-next;if(p1=NULL) return(p1); /表空返回 q=p-next;if(q=NULL) return(p1); /表长=1时返

4、回 i=p-data+q-data; /相邻两节点data值之和 while(q-next)p=q;q=q-next; /取下一对相邻节点的指针 j=p-data+q-data;if(ji)p1=p;i=j; /取和为最大的第一节点指针 return (p1);void main() /主函数 Link A,B,p,q;int a,b;doprintf(请输入一组整数(以0为结束符，数之间回车):n);p=A=Createlist(); /创建新链表 B=Adjmax(A); /求链表中相邻两节点data值之和为最大的第一节点的指针 a=(int)(B-data); /取第一节点的data值

5、printf(第一节点的data值为:%dn,a); while(p-next) /释放链表空间 q=p; p=p-next; free(q); free(p); printf(是否继续输入下一组整数:是:1,否:0n); scanf(%d,&b); while(b); 上机题2. 实现算术表达式求值程序（栈的运用）。 设操作数：0，1，2，8，9（可扩充）； 运算符：+，*，/，（，），#（#号为结束）。 输入中缀表达式，如：5+(42)*3 #，将其转换成后缀表达式：5423*+#，然后计算，本例结果为11。程序结构： 类型说明；两套：Clearstack(S)、Emptystack(S)

6、、 Getstop(S) 、 Push(S)、Pop(S)； 中缀到后缀转换的函数：Mid-post(En，Bn)； 后缀表达式求值的函数：Postcount(Bn)； main（） 变量说明； 输入中缀表达式，存入En； 调用Mid-post(E，B)； 调用Postcount(B)； 打印表达式结果； Y 继续？ N 停止 上机题2：#include#include#includetypedef struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *n

7、ext;snode1,*slink1;void Clearstack(slink s) /置栈空 s=NULL;int Emptystack(slink s) /判断栈是否为空if(s=NULL) return(1); /栈空返回1else return(0); /栈非空返回0 char Getstop(slink s) /取栈顶元素if(s!=NULL) return (s-data); return (0); void Push(slink*s,char x) /元素x进栈slink p;p=(slink)malloc(sizeof(snode); /生成进栈p节点 p-data=x; /

8、存入新元素 p-next=*s; /p节点作为新的栈顶链入 *s=p;char Pop(slink*s) /出栈char x;slink p;if(Emptystack(*s) return (-1); /栈空，返回-1 elsex=(*s)-data;p=*s;*s=(*s)-next;free(p);return (x); /成功 void Push1(slink1*s,int x) /元素x进栈slink1 p;p=(slink1)malloc(sizeof(snode1); /生成进栈p节点 p-data=x; /存入新元素 p-next=*s; /p节点作为新的栈顶链入 *s=p;i

9、nt Pop1(slink1*s) /出栈int x;slink1 p;if(Emptystack1(*s) return (-1); /栈空，返回-1 elsex=(*s)-data;p=*s;*s=(*s)-next;free(p);return (x); /成功 int Emptystack1(slink1 s) /判断栈是否为空if(s=NULL) return(1); /栈空返回1else return(0); /栈非空返回0 void Clearstack1(slink1 s) /置栈空 s=NULL;int Getstop1(slink1 s) /取栈顶元素if(s!=NULL)

10、 return (s-data); return (0); int Precede(char x,char y) int a,b;switch(x)case #:/case （:case (:a=0;break;case +: case -:a=1;break; case *: case /:a=2;break; switch(y)case +:case -:b=1;break;case *:case /:b=2;break; /case （:case (:b=3;break;if(a=b) return (1);else return (0); void Mid_post(char E,ch

11、ar B) /中缀表达式B到后缀表达式E的转换 int i=0,j=0;char x; int a;slink s=NULL; /置空栈 Clearstack(s);Push(&s,#); /结束符入栈 dox=Bi+; /扫描当前表达式分量x switch(x) case :break; case #:while(!Emptystack(s) Ej+= ; /栈非空时 Ej+=Pop(&s);break; case ):while(Getstop(s)!=() Ej+= ; Ej+=Pop(&s); /反复出栈直到遇到( Pop(&s); /退掉( break;case +:case -:c

12、ase *:case /:case (:while(Precede(Getstop(s),x) /栈顶运算符（Q1）与x比较 Ej+= ; Ej+=Pop(&s);/Ej+= ;Push(&s,x); /Q1x时，x进栈Ej+= ; break; default:Ej+=x;while(x!=#); Ej=0;Clearstack(s);int Ecount(char E) /后缀表达式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL;while(Ei!=#)x=Ei;switch(x)case :break;case +:

13、b=Pop1(&s);a=Pop1(&s);z=a+b;Push1(&s,z);break;case -:b=Pop1(&s);a=Pop1(&s);z=a-b;Push1(&s,z);break;case *:b=Pop1(&s);a=Pop1(&s);z=a*b;Push1(&s,z);break;case /:b=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break;default: g=0;g1=0; while(Ei!= ) g1=Ei-0; g=g*10+g1; i+; Push1(&s,g); i+;if(!Emptystack1(s) retu

14、rn(Getstop1(s);Clearstack1(s);int pd(char B) int i=0,c,j,k; c=strlen(B); while(Bi!=#) switch(Bi) case :break; case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: j=i+1; if(Bj= ) while(Bj= ) j+; switch(Bj) case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: cas

15、e 8: case 9:printf(1非法输入!请重新输入!n);return(0);break; break; case +: case -: case *: case /: j=i-1; while(Bj= ) j-;switch(Bj)case +:case -:case *:case /:case (:case #:printf(2非法输入!请重新输入!n);return(0);break; k=i+1; while(Bk= ) k+; switch(Bk)case +:case -:case *:case /:case ):case #:printf(3非法输入!请重新输入!n);

16、return(0);break; break;case (: j=i-1; while(Bj= ) j-;switch(Bj)case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9:case #:case ):printf(4非法输入!请重新输入!n);return(0);break; k=i+1; while(Bk= ) k+; switch(Bk)case +:case -:case *:case /:case #:printf(5非法输入!请重新输入!n);return(0);break

17、; break;case ): j=i-1; while(Bj= ) j-; switch(Bj) case (:printf(6非法输入!请重新输入!n);return(0);break; k=i+1; while(Bk= ) k+; switch(Bk)case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9:printf(7非法输入!请重新输入!n);return(0);break; break; case 0:break; default:printf(8非法输入!请重新输入!n);re

18、turn(0); i+; if(B0=#) printf(表达式为空!请重新输入!n);return(0); else if (Bc-1!=#) printf(9非法输入!请重新输入!n);return(0); void main() int a,b,c,d;char B100,E100;dodo printf(请输入中缀表达式:n);B100=fflush(stdin); gets(B); while(B0=0) B100=fflush(stdin); gets(B); b=pd(B); while(b=0); Mid_post(E,B); printf(后缀表达式为:n); printf(

19、%sn,E); a=Ecount(E); printf(结果=%dn,a); printf(是否继续?是:1否:0n); scanf(%d,&c); while(c=1); 上机题3. 实现链式队列运算程序（队列的运用）。 程序结构： 类型说明； Clearqueue(q)、Emptyqueue(q)、Enqueue(q)、Dequeue(q)； main（） 变量说明； 上机题3：#include #include #includetypedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *

20、front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空队列q-front-next=NULL;q-rear=q-front;void Creatqueue(linkqueue *q) /创建队列 q-front=(Qlink)malloc(sizeof(Qnode);q-front-next=NULL;q-rear=q-front;int Emptyqueue(linkqueue *q) /判断队列是否为空if(q-front=q-rear) return (1);else return (0);void Enqueue(linkqueu

21、e *q,char e) /元素进队Qlink p;p=(Qlink)malloc(sizeof(Qnode);p-data=e;p-next=NULL;q-rear-next=p;q-rear=p;char Dequeue(linkqueue *q) /元素出队Qlink p;if(Emptyqueue(q) return(NULL);elsep=q-front;q-front=p-next;free(p);return(q-front-data);void main()char a,b;int c;linkqueue q;Creatqueue(&q);doa=getchar();switc

22、h (a)case 0: if(Emptyqueue(&q) printf(队列为空!n); printf(请继续输入!n);c=1; else b=Dequeue(&q); printf(%c出队n,b); printf(请继续输入!n);break; case : if(Emptyqueue(&q) printf(队列为空!n);return; elseprintf(全部元素出队:n); while(Emptyqueue(&q)!=1) b=Dequeue(&q); printf(%c,b); printf(n); return;break; case n:break; default :

23、Enqueue(&q,a);c=1;break;while(c);上机题4设电文字符集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编码。程序结构：类型说明；构造Huffman树的函数：Huffman_tree(Hm+1)；求Huffman编码的函数：Huffman_code(coden+1)；main() 变量说明； 输入字符集D及频率F； 调用Huffman_tree(H)； 调用Huffman_code(code)；

24、 打印编码； Y 继续？ N停止 上机题4：#include#define n 20 #define m 2*n-1 /H树的节点数#define max 99typedef structint wi;char data;int parent,Lchild,Rchild;huffm;void Huffman_tree(huffm HT,int F,int p,int q)int i,j,p1,p2;int w,s1,s2;for(i=1;i=q;i+) /初始化HTi.wi=0;HTi.parent=0;HTi.Lchild=HTi.Rchild=0;for(i=1;i=p;i+)HTi.wi

25、=Fi-1;for(i=p+1;i=q;i+)p1=p2=0;s1=s2=max;for(j=1;j=i-1;j+)if(HTj.parent=0)if(HTj.wis1)s2=s1;s1=HTj.wi;p2=p1;p1=j;else if(HTj.wis2)s2=HTj.wi;p2=j;HTp1.parent=HTp2.parent=i;HTi.Lchild=p1;HTi.Rchild=p2;HTi.wi=HTp1.wi+HTp2.wi;typedef structchar bitsn+1;int start;char ch;ctype;void Huffman_code(ctype cod

26、e,huffm HT,char D,int F,int p,int q)int i,j,a,s;ctype md;for(i=1;i=p;i+) codei.ch=Di-1;HTi.data=codei.ch;for(i=1;i=p;i+)md.ch=codei.ch;md.start=p+1;s=i;a=HTi.parent;while(a!=0)md.start-;if(HTa.Lchild=s)md.bitsmd.start=0;elsemd.bitsmd.start=1;s=a;a=HTa.parent;codei=md;void main()int F30;int i,j,k,p0=

27、0,p1=0,q,d,f,p,i1,w;char D50;huffm HTm+1;ctype coden+1;dodododo p0=0;D50=fflush(stdin); printf(请输入字符集D!(最多20个字符,以#为结束符)n); scanf(%s,&D); for(k=0;kn) printf(超出范围!n); d=1; D50=fflush(stdin); else d=0;while(d); printf(请输入各字符出现的概率集F!(每个数直接要回车!以-1为结束符)n); for(i=0;i50;i+) / scanf(%d,&Fi); w=(fflush(stdin)

28、,scanf(%d,&Fi); if(w!=1) printf(非法输入!n); d=1;break; if(Fi=-1) d=0;break; /if(Fi=-1) / break;while(d);p1=0;i1=0;for(k=0;k50;k+) if(Fk!=-1) +p1; else break; if(F0=-1) printf(非法输入!n); d=1; else if(Fp1!=-1) printf(非法输入!n);d=1; else if(p!=p1)printf(D的元素个数与F的元素个数不等!n请重新输入!n);d=1;/for(i=0;i=p1;i+)/printf(%

29、d ,Fi);while(d); q=2*p-1; /huffm HTq+1; Huffman_tree(HT,F,p,q); /*for(i=1;i=q;i+) printf(%dt,HTi.wi); printf(%dt,HTi.parent); printf(%dt,HTi.Lchild); printf(%dt,HTi.Rchild); printf(n); */ printf(打印编码:n); /ctype codep+1; Huffman_code(code,HT,D,F,p,q); /printf(%s,D); printf(字符tbitsn); for(i=1;i=p;i+)

30、printf(%ct,codei.ch); for(j=codei.start;j=p;j+) printf(%c,codei.bitsj); printf(n); printf(是否继续?是:1 否:0n); scanf(%d,&f);while(f);上机题5：设英文句子：“everyone round you can hear you when you speak.”，试编写完成下面任务的程序。（1）依次读入句中各单词，构造一棵二叉排序树；即：（2）按LDR遍历此二叉排序树。LDR： can everyone hear round speak when you（有序）上机题5：/*#in

31、clude #include #include#define max 200 typedef struct nodechar key20;int w;Retype;typedef struct BsnodeRetype data;struct Bsnode *Lchild,*Rchild;BSN,*BSP;BSP BSTinsert(BSP T,BSP S)BSP q,p;if(T=NULL) return(S);p=T;q=NULL;while(p)q=p;if(strcmp(S-data.key,p-data.key)=0)free(S);return(T);if(strcmp(S-dat

32、a.key,p-data.key)Lchild;else p=p-Rchild; if(strcmp(S-data.key,q-data.key)Lchild=S;else q-Rchild=S;return(T);BSP CreateBst(char A)int i,j,k=0,p=0;char b15,B150;BSP T,S;doif(A0=0) gets(B);A=B;while(A0=0);T=NULL;dowhile(Ak= ) k+; /while(Ak!= )/ / p=0; /switch(Ak)/case :break;/default:bp+=Ak;/ bp+=Ak;/k

33、+;/printf(sdfjkl);p=0;while(Ak!= )switch(Ak)case :break;default:bp+=Ak;k+;if(bp-1=.) bp-1=0;bp=0; S=(BSP)malloc(sizeof(BSN);for(i=0;idata.keyi=bi;S-data.w=i;else break; printf(%sn,b);S-Lchild=S-Rchild=NULL;/printf(dfd);T=BSTinsert(T,S);/scanf(%s,&key);/while(bp-1=.); return(T);void visit(BSP T)int i; for(i=0;idata.w;i+) printf(%c,T-data.keyi); / else break;printf( );void inorder(BSP T)int i;if(T)inorder(T-Lchild);visit(T);inorder(T-Rchild); /printf(n);void main()int a; char A150;do a=0;printf(请输入一句英文!(以.结束)n);gets(A);do/scanf(%s,&key);if(A0=.) printf(句子为空!请重新输入!n);gets(A);while(A0