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

《数据结构》上机题（C语言程序）

1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。 例如输入：2 6 4 7 3 0（0为结束符），建立：

所求结果=4

程序结构： 类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( )

{ 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止 }

上机题1：

#include #include

typedef int datatype; //设当前数据元素为整型 typedef struct node //节点类型 {

datatype data; //节点的数据域 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; do { c=(fflush(stdin),scanf(\ //判断输入的是否是整数 a=(int)b; if(c!=1||a!=b||a>-2^16||a<2^16-1) printf(\非法输入!请重新输入!\\n\ }while(c!=1||a!=b||a>-2^16||a<2^16-1); while(a!=0) { P=(Link)malloc(sizeof(Linknode));//申请新节点 P->data=a; //存入数据

r->next=P; //新节点链入表尾 r=P; do { c=(fflush(stdin),scanf(\ //判断输入的是否是整数 a=(int)b; if(c!=1||a!=b||a>-2^16||a<2^16-1) printf(\非法输入!请重新输入!\\n\ }while(c!=1||a!=b||a>-2^16||a<2^16-1); } r->next=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时返回 i=p->data+q->data; //相邻两节点data值之和 while(q->next) { p=q;q=q->next; //取下一对相邻节点的指针 j=p->data+q->data; if(j>i) { p1=p; i=j; //取和为最大的第一节点指针 } } return (p1); }

void main() //主函数 { Link A,B,p,q; int a,b; do { printf(\请输入一组整数(以0为结束符，数之间回车):\\n\ p=A=Createlist(); //创建新链表

B=Adjmax(A); //求链表中相邻两节点data值之和为最大的第一节点的指针

a=(int)(B->data); //取第一节点的data值 printf(\第一节点的data值为:%d\\n\

while(p->next) //释放链表空间 { q=p; p=p->next; free(q); }

free(p);

printf(\是否继续输入下一组整数:是:1,否:0\\n\ scanf(\ }while(b); }

上机题2. 实现算术表达式求值程序（栈的运用）。 设操作数：0，1，2，??，8，9（可扩充）； 运算符：+，—，*，/，（，），#（#号为结束）。

输入中缀表达式，如：5+(4—2)*3 #，将其转换成后缀表达式：542—3*+#， 然后计算，本例结果为11。 程序结构： 类型说明； 两套：Clearstack(S)、Emptystack(S)、 Getstop(S) 、 Push(S)、Pop(S)； 中缀到后缀转换的函数：Mid-post(E[n]，B[n])； 后缀表达式求值的函数：Postcount(B[n])； main（） { 变量说明； 输入中缀表达式，存入E[n]； 调用Mid-post(E，B)； 调用Postcount(B)； 打印表达式结果； Y 继续？

N 停止 }

上机题2：

#include #include #include typedef struct node { char data; struct node *next; }snode,*slink;

typedef struct node1 { int data; struct node1 *next; }snode1,*slink1;

void Clearstack(slink s) //置栈空 { s=NULL; }

int Emptystack(slink s) //判断栈是否为空 { if(s==NULL) return(1); //栈空返回1 else 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; //存入新元素 p->next=*s; //p节点作为新的栈顶链入 *s=p; }

char Pop(slink*s) //出栈 { char x; slink p; if(Emptystack(*s)) return (-1); //栈空，返回-1 else { x=(*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; }

int Pop1(slink1*s) //出栈 { int x; slink1 p; if(Emptystack1(*s)) return (-1); //栈空，返回-1 else { x=(*s)->data; p=*s; *s=(*s)->next; free(p); return (x); //成功 } }

int Emptystack1(slink1 s) //判断栈是否为空 { if(s==NULL) return(1); //栈空返回1 else return(0); //栈非空返回0 }

void Clearstack1(slink1 s) //置栈空 { s=NULL; }

int Getstop1(slink1 s) //取栈顶元素 { if(s!=NULL) 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[],char B[]) //中缀表达式B到后缀表达式E的转换 { int i=0,j=0; char x; int a; slink s=NULL; //置空栈 Clearstack(s); Push(&s,'#'); //结束符入栈 do { x=B[i++]; //扫描当前表达式分量x switch(x) { case ' ':break; case '#': { while(!Emptystack(s)) { E[j++]=' '; //栈非空时 E[j++]=Pop(&s); } }break; case ')': { while(Getstop(s)!='(') { E[j++]=' '; E[j++]=Pop(&s); } //反复出栈直到遇到'(' Pop(&s); //退掉'('

}break; case '+': case '-': case '*': case '/': case '(': { while(Precede(Getstop(s),x)) //栈顶运算符（Q1）与x比较 { E[j++]=' '; E[j++]=Pop(&s); } //E[j++]=' '; Push(&s,x); //Q1

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(E[i]!='#') { x=E[i]; switch(x) { case ' ':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; case '/':b=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break; default: { g=0;g1=0; while(E[i]!=' ')

{ g1=E[i]-'0'; g=g*10+g1; i++; } Push1(&s,g); } } i++; } if(!Emptystack1(s)) return(Getstop1(s)); Clearstack1(s); }

int pd(char B[]) { int i=0,c,j,k; c=strlen(B);

while(B[i]!='#') { switch(B[i]) { 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(B[j]==' ') { while(B[j]==' ') j++; switch(B[j]) { case '0': case '1': case '2': case '3': case '4': case '5':

case '6': case '7': case '8':

case '9':printf(\非法输入!请重新输入!\\n\ } } }break; case '+': case '-': case '*': case '/': { j=i-1; while(B[j]==' ') j--; switch(B[j]) { case '+': case '-': case '*': case '/': case '(': case '#':printf(\非法输入!请重新输入!\\n\ } k=i+1; while(B[k]==' ') k++; switch(B[k]) { case '+': case '-': case '*': case '/': case ')': case '#':printf(\非法输入!请重新输入!\\n\ } }break; case '(': { j=i-1; while(B[j]==' ') j--; switch(B[j]) { case '0': case '1': case '2':

case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '#': case ')':printf(\非法输入!请重新输入!\\n\ } k=i+1; while(B[k]==' ') k++; switch(B[k]) { case '+': case '-': case '*': case '/': case '#':printf(\非法输入!请重新输入!\\n\ } }break; case ')': { j=i-1; while(B[j]==' ') j--; switch(B[j]) { case '(':printf(\非法输入!请重新输入!\\n\ } k=i+1; while(B[k]==' ') k++; switch(B[k]) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8':

case '9':printf(\非法输入!请重新输入!\\n\ }

}break;

case '\\0':break;

default:printf(\非法输入!请重新输入!\\n\ } i++; }

if(B[0]=='#') {

printf(\表达式为空!请重新输入!\\n\ }

else if (B[c-1]!='#') {

printf(\非法输入!请重新输入!\\n\ } }

void main() {

int a,b,c,d; char B[100],E[100]; do { do { printf(\请输入中缀表达式:\\n\ B[100]=fflush(stdin); gets(B); while(B[0]=='\\0') { B[100]=fflush(stdin); gets(B); } b=pd(B); }while(b==0); Mid_post(E,B); printf(\后缀表达式为:\\n\ printf(\ a=Ecount(E); printf(\结果=%d\\n\ printf(\是否继续?是:1否:0\\n\ scanf(\ }while(c==1); }

上机题3. 实现链式队列运算程序（队列的运用）。 程序结构：

类型说明； Clearqueue(q)、Emptyqueue(q)、Enqueue(q)、Dequeue(q)； main（） { 变量说明；

上机题3：

#include #include #include typedef struct node { char data; struct node *next; }Qnode,*Qlink; typedef struct { Qnode *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(linkqueue *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); else { p=q->front; q->front=p->next; free(p); return(q->front->data); } }

void main() { char a,b;int c; linkqueue q; Creatqueue(&q); do{ a=getchar(); switch (a) { case '0': { if(Emptyqueue(&q)) { printf(\队列为空!\\n\ printf(\请继续输入!\\n\ } else

{ b=Dequeue(&q); printf(\出队\\n\ printf(\请继续输入!\\n\ } }break; case '@': { if(Emptyqueue(&q)) {printf(\队列为空!\\n\ else { printf(\全部元素出队:\\n\ while(Emptyqueue(&q)!=1) { b=Dequeue(&q); printf(\ } printf(\ return; } }break; case '\\n':break; default :{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(H[m+1])； 求Huffman编码的函数：Huffman_code(code[n+1])； main() { 变量说明； 输入字符集D及频率F； 调用Huffman_tree(H)； 调用Huffman_code(code)； 打印编码；

Y 继续？ N 停止 }

上机题4：

#include #define n 20

#define m 2*n-1 //H树的节点数 #define max 99 typedef struct { int 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++) //初始化 { HT[i].wi=0; HT[i].parent=0; HT[i].Lchild=HT[i].Rchild=0; } for(i=1;i<=p;i++) { HT[i].wi=F[i-1]; } for(i=p+1;i<=q;i++) { p1=p2=0; s1=s2=max; for(j=1;j<=i-1;j++) if(HT[j].parent==0) if(HT[j].wi

{ s2=HT[j].wi; p2=j; } HT[p1].parent=HT[p2].parent=i; HT[i].Lchild=p1; HT[i].Rchild=p2; HT[i].wi=HT[p1].wi+HT[p2].wi; } }

typedef struct { char bits[n+1]; int start; char ch; }ctype;

void Huffman_code(ctype code[],huffm HT[],char D[],int F[],int p,int q) { int i,j,a,s; ctype md; for(i=1;i<=p;i++) { code[i].ch=D[i-1]; HT[i].data=code[i].ch; } for(i=1;i<=p;i++) { md.ch=code[i].ch; md.start=p+1; s=i; a=HT[i].parent; while(a!=0) { md.start--; if(HT[a].Lchild==s) md.bits[md.start]='0'; else md.bits[md.start]='1'; s=a; a=HT[a].parent; } code[i]=md;

} }

void main() { int F[30]; int i,j,k,p0=0,p1=0,q,d,f,p,i1,w; char D[50]; huffm HT[m+1]; ctype code[n+1]; do { do{do{ do { p0=0; D[50]=fflush(stdin); printf(\请输入字符集D!(最多20个字符,以#为结束符)\\n\ scanf(\ for(k=0;k<50;k++) if(D[k]!='\\0') { ++p0; p=p0-1; } else break; //printf(\ if(D[0]=='#') { printf(\非法输入!\\n\ d=1; D[50]=fflush(stdin); } else if(D[p]!='#') { printf(\非法输入!\\n\ d=1;D[50]=fflush(stdin); } else if(p>n) { printf(\超出范围!\\n\ d=1; D[50]=fflush(stdin);

} else d=0; }while(d);

printf(\请输入各字符出现的概率集F!(每个数直接要回车!以-1为结束符)\\n\ for(i=0;i<50;i++) // scanf(\ { w=(fflush(stdin),scanf(\ if(w!=1) { printf(\非法输入!\\n\ d=1;break; } if(F[i]==-1) { d=0;break; } } //if(F[i]==-1) // break; }while(d); p1=0; i1=0; for(k=0;k<50;k++) if(F[k]!=-1) ++p1; else break; if(F[0]==-1) { printf(\非法输入!\\n\ d=1; } else if(F[p1]!=-1) {

printf(\非法输入!\\n\ d=1; } else if(p!=p1) { printf(\的元素个数与F的元素个数不等!\\n请重新输入!\\n\ } //for(i=0;i<=p1;i++) //printf(\ }while(d); q=2*p-1; //huffm HT[q+1];

Huffman_tree(HT,F,p,q); /* for(i=1;i<=q;i++) { printf(\ printf(\ printf(\ printf(\ printf(\ }*/ printf(\打印编码:\\n\ //ctype code[p+1];

Huffman_code(code,HT,D,F,p,q); //printf(\

printf(\字符\\tbits\\n\ for(i=1;i<=p;i++) { printf(\ for(j=code[i].start;j<=p;j++) printf(\ printf(\ } printf(\是否继续?是:1 否:0\\n\ scanf(\ }while(f); }

上机题5：设英文句子：“everyone round you can hear you when you speak.”，试编写完成下面任务的程序。 （1）依次读入句中各单词，构造一棵二叉排序树； 即： （2）按LDR遍历此二叉排序树。 LDR： can everyone hear round speak when you（有序）

上机题5：

/*#include #include #include #define max 200 typedef struct node { char key[20]; int w; }Retype;

typedef struct Bsnode { Retype 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->data.key,p->data.key)<0) p=p->Lchild; else p=p->Rchild; } if(strcmp(S->data.key,q->data.key)<0) q->Lchild=S; else q->Rchild=S; return(T); }

BSP CreateBst(char A[]) {int i,j,k=0,p=0; char b[15],B[150]; BSP T,S; do{ if(A[0]=='\\0') {gets(B);A=B;} }while(A[0]=='\\0'); T=NULL; do { while(A[k]=' ') k++; //while(A[k]!=' ') // {

// p=0; //switch(A[k]) //{

// case ' ':break;

// default:b[p++]=A[k]; //}

// b[p++]=A[k]; // k++; // } printf(\ p=0; while(A[k]!=' ') { switch(A[k]) { case ' ':break; default:b[p++]=A[k]; } k++; if(b[p-1]=='.') b[p-1]='\\0'; b[p]='\\0'; S=(BSP)malloc(sizeof(BSN)); for(i=0;i<20;i++) if(b[i]!='\\0') { S->data.key[i]=b[i]; S->data.w=i; } else break; printf(\ S->Lchild=S->Rchild=NULL; //printf(\ T=BSTinsert(T,S); //scanf(\ } // }

}while(b[p-1]='.'); return(T); }

void visit(BSP T) {

int i;

for(i=0;i<=T->data.w;i++) printf(\ // else break; printf(\}

void inorder(BSP T) {int i; if(T) { inorder(T->Lchild); visit(T); inorder(T->Rchild); } //printf(\}

void main() { int a;

char A[150]; do { a=0; printf(\请输入一句英文!(以.结束)\\n\ gets(A); do{ //scanf(\ if(A[0]=='.') printf(\句子为空!请重新输入!\\n\ gets(A); }while(A[0]=='.'); BSP T; T=CreateBst(A); printf(\遍历输出:\\n\ inorder(T); printf(\ printf(\是否继续?是:1否:0\ scanf(\ }while(a);

}*/

/*#include #include #include #define max 200 typedef struct node { char key[20]; int w; }Retype;

typedef struct Bsnode { Retype 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->data.key,p->data.key)<0) p=p->Lchild; else p=p->Rchild; } if(strcmp(S->data.key,q->data.key)<0) q->Lchild=S; else q->Rchild=S; return(T);

}

BSP CreateBst() {int i,j,c; BSP T,S; char key[20]; T=NULL; do{ scanf(\ c=strlen(key); if(key[0]=='.') printf(\句子为空!请重新输入!\\n\}while(key[0]=='.'); while(key[c-1]!='.') { S=(BSP)malloc(sizeof(BSN)); for(i=0;i<20;i++) if(key[i]!='\\0') { S->data.key[i]=key[i];S->data.w=i;} else break; // printf(\ S->Lchild=S->Rchild=NULL; //printf(\ T=BSTinsert(T,S); scanf(\ c=strlen(key); } if(key[c-1]=='.') { key[c-1]='\\0'; S=(BSP)malloc(sizeof(BSN)); for(i=0;i<20;i++) if(key[i]!='\\0') { S->data.key[i]=key[i];S->data.w=i;} else break; //printf(\ S->Lchild=S->Rchild=NULL;

T=BSTinsert(T,S); } return(T); }

void visit(BSP T) { int i;

//if(T->data.key[0]!='0')

for(i=0;i<=T->data.w;i++) // if(T->data.key[i]!='\\0') printf(\ // else break; printf(\}

void inorder(BSP T) { if(T==NULL) return; inorder(T->Lchild); visit(T); inorder(T->Rchild); //printf(\}

void main() { int a; do { a=0; printf(\请输入一句英文!(以.结束)\\n\ BSP T; T=CreateBst(); printf(\遍历输出:\\n\ inorder(T);printf(\ printf(\是否继续?是:1否:0\\n\ scanf(\

}while(a); }*/

#include #include #include #define max 200 typedef struct node { char key[20]; int w; }Retype;

typedef struct Bsnode { Retype 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->data.key,p->data.key)<0) p=p->Lchild; else p=p->Rchild; } if(strcmp(S->data.key,q->data.key)<0) q->Lchild=S; else q->Rchild=S; return(T);

}

BSP CreateBst() {int i,j; BSP T,S; char key[20]; T=NULL; do{ scanf(\ if(key[0]=='.') printf(\句子为空!请重新输入!\\n\}while(key[0]=='.'); // j=0; //while(key[j+1]!=' '||key[j+1]!='\\0') j++; //printf(\ while(key[0]!='.') { S=(BSP)malloc(sizeof(BSN)); for(i=0;i<20;i++) if(key[i]!='\\0') { S->data.key[i]=key[i];S->data.w=i;} else break; //printf(\ S->Lchild=S->Rchild=NULL; //printf(\ T=BSTinsert(T,S); scanf(\ //j=0; // while(key[j+1]!=' '||key[j+1]!='\\0') j++; } /* S=(BSP)malloc(sizeof(BSN)); for(i=0;i<20;i++) if(key[i]!='\\0') { S->data.key[i]=key[i];S->data.w=i;} else break;

//printf(\ S->Lchild=S->Rchild=NULL; T=BSTinsert(T,S);*/ return(T); }

void visit(BSP T) { int i;

//if(T->data.key[0]!='0')

for(i=0;i<=T->data.w;i++) // if(T->data.key[i]!='\\0') printf(\ // else break; printf(\}

void inorder(BSP T) {int i; if(T) { inorder(T->Lchild); visit(T); inorder(T->Rchild); } //printf(\}

void main() { int a; do { a=0; printf(\请输入一句英文!(以.结束)\\n\ BSP T; T=CreateBst(); printf(\遍历输出:\\n\ inorder(T);printf(\ printf(\是否继续?是:1否:0\ scanf(\

}

}while(a);

本文来源：https://www.bwwdw.com/article/8mor.html