数据结构上机实验答案.doc

_数据结构实验指导书答案实验一：1、 请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。#include int fun(int *a, int *b) if (*a*(*b)0) return(1); else return(0);main()int x,y;scanf(%d%d,&x,&y);if (fun(&x,&y) printf(yesn);else printf(no);2、 计算1+2+3+100，要求用指针进行设计。即设计函数int fun(int *n)实现求1+2+3+*n，在主函数中输入、调用、输出结果。#include int fun(int *n) int i,sum=0; for (i=1;i=*n;i+) sum+=i; return(sum);main()int x,sum;scanf(%d,&x); printf(the sum is %dn,fun(&x);3、 函数的功能是求数组a中最大数的位置（位序号）。在主函数中输入10个整数、调用函数fun、输出结果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/int fun(int *a,int n)int i,*max;max=a;for (i=1;i*max) max=a+i;return(max-a);main()int aN,maxi;input(a,N);maxi=fun(a,N);printf(n the max position is %dn,maxi);4、请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a中所有奇数之和和所有偶数之和。形参n给出数组中数据的个数；利用指针odd和even分别返回奇数之和和偶数之和。在主函数中输入10个整数、调用函数fun、输出结果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void fun(int *a,int n, int *odd, int *even)int i,sum1=0,sum2=0;for (i=0;in;i+)if (ai%2=0) sum1+=ai; else sum2+=ai;*odd=sum1;*even=sum2;main()int aN,odd,even;input(a,N);fun(a,N, &odd, &even);printf(the odd is %dtthe even is %dn,odd,even);5、请编写函数int fun(int *a, int *b，int n),函数的功能是把数组a中所有为偶数的数，放在另一个数组中b。在主函数中输入10个整数、调用函数fun、输出结果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void output(int *a,int n)int i;printf(nthe odd is:n);for (i=0;in;i+) printf(%5d,*(a+i); /*printf(%d,ai);*/int fun(int *a, int *b,int n)int i,j=0;for (i=0;in;i+)if (ai%2=0) bj=ai; j+;return(j);main()int aN,bN,m;input(a,N);m=fun(a,b,N);output(b,m);6、请编写函数int fun(int *a,，int n),函数的功能是把数组a中最大数和最小数交换。在主函数中输入10个整数、调用函数fun、输出结果。#define N 10#include void input(int *a,int n)int i; for (i=0;in;i+) scanf(%d,a+i); /*scanf(%d,&ai);*/void output(int *a,int n)int i;printf(nthe result is:n);for (i=0;in;i+) printf(%5d,*(a+i); /*printf(%d,ai);*/void fun(int *a,int n)int i,*max,*min,temp;max=min=a;for (i=1;i*max) max=a+i;if (ai*min) min=a+i;printf(the max is %d,the position is %dn,*max,max-a);printf(the min is %d,the position is %dn,*min,min-a);if (max!=min)temp=*max;*max=*min;*min=temp;main()int aN,m;input(a,N);fun(a,N);output(a,N);7、请编写函数int fun(int a44),函数的功能是把矩阵a转置。在主函数中输入、调用函数fun、输出结果。#define N 4#include void input(int a4,int n)int i,j; for (i=0;in;i+) for (j=0;jn;j+) scanf(%d,&aij);void output(int a4,int n)int i,j;printf(nthe result is:n);for (i=0;in;i+) printf(n); for (j=0;jn;j+)printf(%4d,*(*(a+i)+j); /*printf(%d,aij);*/ void fun(int a4,int n)int i,j,temp;for (i=0;in;i+)for (j=0;ji;j+) temp=aij;aij=aji;aji=temp;main()int aNN;input(a,N);fun(a,N);output(a,N);8、 请编写函数int fun(char *a),函数的功能是分别求出字符串a 的长度。在主函数中输入1个字符串、调用函数fun、输出结果。#include int fun(char *a)int i=0;char *p;p=a;while (*p) i+; p+;return(i);main()char str20,*cp;cp=str;gets(cp);printf(the length of %s is %dn,cp,fun(cp);9、10、#include #include #define N 2typedef struct student /*定义数据结构（数据类型）*/ long num; char name10; int score3; /*存放三门课成绩 */ float average; /*/平均成绩*/ stu;void intput(stu s,int n) /*输入数据 */int i,j; /*i表示处理学生的下标，J表示成绩编号 */ for (i=0;in;i+) printf(input num:n); scanf(%ld,&si.num); printf(input name:n); scanf(%s,); printf(input 3 score:n); for (j=0;j3;j+) scanf(%d,&si.scorej); void stu_av(stu s,int n)/*求每个学生的平均成绩*/ int i,j,sum; for (i=0;in;i+) sum=0; for (j=0;j3;j+) sum+=si.scorej ; si.average=sum/3.0; float av(stu s,int n)/*求总平均成绩*/ int i; float sum=0.0,ave; for (i=0;in;i+) sum+=si.average; ave=sum/n; return(ave);int max(stu s,int n)/*求平均成绩最高学生的下标*/ int i,maxi=0; for (i=1;ismaxi.average) maxi=i; return(maxi);main()int maxi,j; stu aN;/*定义变量 */ intput(a,N); stu_av(a,N); printf(the score average is %fn, av(a,N); maxi=max(a,N); printf(the max average student data:n); printf(%10ld,amaxi.num); printf(%10s,); for (j=0;j3;j+) printf(%5d,amaxi.scorej); printf(%5.1f,amaxi.average); getch();实验二 1、#include #define MaxLen 50typedef int elemtype;struct datatypeelemtype *elem; int length;typedef struct datatype sqlist;void create (sqlist *a)int i,n;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(创建一个顺序表n);printf(输入元素个数n);scanf(%d,&a-length);for (i=0;ilength;i+) printf(输入第%d个元素值:,i+1); scanf(%d,a-elem+i);void invert(sqlist *a) int m=a-length/2,i;elemtype temp;for (i=0;ielem+i); *(a-elem+i)=*(a-elem+a-length-1-i); *(a-elem+a-length-1-i)=temp; void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%dn,i+1,*(a-elem+i);getch();void main()sqlist a;create(&a);disp(&a);invert(&a);disp(&a);2、#include #include #define NULL 0typedef int elemtype;typedef struct linknodeelemtype data;struct linknode *next;nodetype;nodetype *create()elemtype d;nodetype *h,*s,*t;int i=1;h=NULL;printf(建立一个单链表n);while (1) printf(输入第%d节点data域值:,i); scanf(%d,&d);if (d=0) break ; /*以0表示输入结束*/if(i=1) /*建立第一个结点*/h=(nodetype *)malloc(sizeof(nodetype);h-data=d;h-next=NULL;t=h;elses=(nodetype *)malloc(sizeof(nodetype);s-data=d;s-next=NULL;t-next=s;t=s; /*t始终指向生成的单链表的最后一个结点*/i+;return h;void disp(nodetype *h)nodetype *p=h;printf(输出一个单链表：n);if (p=NULL) printf(空表);while (p!=NULL)printf(%d,p-data);p=p-next;printf(n);getch();int len(nodetype *h)int i=0;nodetype *p=h;while (p)i+;p=p-next;return(i);nodetype *invert(nodetype *h)nodetype *p,*q,*r;if (len(h)next;while (q!=NULL)r=q-next;q-next=p;p=q;q=r;h-next=NULL;h=p;return h;void main()nodetype *head;head=create();disp(head);head=invert(head);disp(head);4、（1）#include #define MaxLen 50typedef structlong num; int score; elemtype;typedef struct datatypeelemtype *elem; int length;sqlist;void create (sqlist *a)long i=0,n;int s;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(创建一个顺序表n);printf(输入学生学号和成绩：0作为结束标志n);scanf(%ld%d,&n,&s);while (n!=0) (a-elem)i.num=n; (a-elem)i.score=s; i+; scanf(%ld%d,&n,&s);a-length=i;void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%ld %dn,i+1,(a-elem)i.num,(a-elem)i.score);getch();void main()sqlist a;create(&a);disp(&a);（2）见5（2）5、（1）#include #define MaxLen 50typedef structlong num; int score; elemtype;typedef struct datatypeelemtype *elem; int length;sqlist;void create (sqlist *a)long i=0,n;int s;a-elem=(elemtype *)malloc(MaxLen*sizeof(elemtype);printf(创建一个顺序表n);printf(输入学生学号和成绩：0作为结束标志n);scanf(%ld%d,&n,&s);while (n!=0) (a-elem)i.num=n; (a-elem)i.score=s; i+; scanf(%ld%d,&n,&s);a-length=i;void sort(sqlist *a) int i,j,k,s; long n; for (i=0;ilength-1;i+) k=i; for (j=i+1;jlength;j+) if (a-elem)j.scoreelem)k.score) k=j; if (k!=i) n=(a-elem)i.num;(a-elem)i.num=(a-elem)k.num; (a-elem)k.num=n; s=(a-elem)i.score;(a-elem)i.score=(a-elem)k.score; (a-elem)k.score=s; void disp(sqlist *a) int i;for (i=0;ilength;i+) printf(%5d:%ld %dn,i+1,(a-elem)i.num,(a-elem)i.score);getch();void main()sqlist a;create(&a);disp(&a);sort(&a);disp(&a);（2）#include #include #define NULL 0typedef struct linknodelong num;int score;struct linknode *next;nodetype;nodetype *create()long n;int sc;nodetype *h,*s,*t;h=(nodetype *)malloc(sizeof(nodetype);h-next=NULL;t=h;printf(创建一个顺序表n);printf(输入学生学号和成绩：0作为结束标志n);scanf(%ld%d,&n,&sc); while (n!=0) s=(nodetype *)malloc(sizeof(nodetype); s-num=n;s-score=sc;t-next=s;t=s; scanf(%ld%d,&n,&sc); t-next=NULL;return h;void disp(nodetype *h)nodetype *p=h-next;printf(输出一个单链表：n);while (p!=NULL) printf(%ld %dn,p-num,p-score);p=p-next;printf(n);getch();nodetype *insertorder(nodetype *h,nodetype *s)nodetype *p,*q;q=h;p=q-next;while (p!=NULL & s-scorep-score) q=p; p=p-next; s-next=p;q-next=s;return(h);nodetype *sort(nodetype *h) nodetype *p,*s; p=h-next; h-next=NULL; while (p!=NULL) s=p-next; h=insertorder(h,p); p=s; return h;void main()nodetype *head;head=create();disp(head);head=sort(head);disp(head);实验三：7、试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中不包含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属于该模式的字符序列，而1+2&2-1则不是。int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return 0;if(!StackEmpty(s) return 0;return 1;/IsReverse 8、编写一个函数将一般算术表达式转化为逆波兰表达式。 解：假设表达式中的符号以字符形式由键盘输入（为简单起见，设算术表达式中的参加运算的数都只有一位数字），该算术表达式存放在字符型数组 str 中，其逆波兰表示式依次存放在字符型数组 exp 中，在处理函数中用一个字符型数组 stack 作为栈。设字符“#”为表达式的终止符，将算术表达式转换成逆波兰表示的方法如下： 依次从键盘输入表达式中的字符 c，对于每一个 c： 若 c 为数字，则将 c 依次存入数组 exp 中； 若 c 为左括弧“(”，则将此括弧压入栈 stack； 若 c 为右括弧“)”，则将栈 stack 中左括弧“(”以前的字符依次弹出存入数组 exp中，然后将左括弧“(”弹出； 若 c 为“+”或“-”，则将当前栈 stack 中“(”以前的所有字符（运算符）依次弹出存入数组 exp 中；如果没有“（”，则将栈stack中的所有字符依次弹出存入数组exp中,然后将 c 压入栈 stack 中； 若 c 为“*”或“/”，则将当前栈 stack 中的栈顶端连续的“*”或“/”弹出并依次存入数组 exp 中，然后将 c 压入栈 stack 中； 若 c 为“#”，则将栈 stack 中的所有运算符依次弹出并存入数组 exp 中，然后再将c 存入数组 exp 中，最后可得到表达式的波兰表示在数组 exp 中。 根据上述转换原理得到的函数如下： #define Maxsize 100 /* Maxsize 为算术表达式中最多字符个数 */ void trans() char strMaxsize； /*存储原算术表达式*/ char expMaxsize； /*存储转换成的逆波兰表达式*/ char stackMaxsize； /*作为栈使用*/ char ch； int i，j，t，top=0；/*t 作为 exp 的下标，top 作为 stack 的下标，i 作为 str 的下标*/ i=0； /*获取用户输入的表达式*/ do i+； scanf(%c，&stri)； while (stri!=# & i=0 & ch=9) /*判定为数字*/ expt=ch；t+； else if (ch=() /*判定为左括号*/ top+；stacktop=ch； else if (ch=) /*判定为右括号*/ while (stacktop!=() expt=stacktop；top-；t+； top-； else if (ch=+ | ch=-) /*判定为加减号*/ while (top!=0 & stacktop!=() expt=stacktop；top-；t+； top+； stacktop=ch； else if (ch=* | ch=/) /*判定为*或/号*/ while (stacktop=* | stacktop=/) expt=stacktop；top-；t+； top+； stacktop=ch； ch=stri；i+； while (top!=0) expt=stacktop；t+；top-； expt=#； for (j=1；j=t；j+) printf(%c，expj)； printf(n)； 9、编写一个函数求逆波兰表达式的值，其中波兰表达式是在该函数中输入的。 解：对逆波兰表达式求值函数中要用到一个数栈 stack，其实现函数如下：先用户以字符形式由键盘输入一个逆波兰表达式（为简单起见，设逆波兰表达式中的参加运算的数都只有一位数字），该逆波兰表达式存放在字符型数组 exp 中，从逆波兰表示式的开始依次扫描这个波兰表示式，当遇到运算对象时，就把它压入数栈 stack；当遇到运算符时，就执行两次弹出数栈 stack 中的数的操作，对弹出的数进行该运算符所指定的运算，再把结果压入数栈 stack，重复上述过程，直至扫描到表达式的终止符“#”，在数栈顶得到表达式的值。 根据上述计算原理得到的函数如下： #define Maxsize 100 /* Maxsize 为算术表达式中最多字符个数 */ void compvalue() char expMaxsize； /*存储用户输入的逆波兰表达式*/ float stackMaxsize，d； /*作为栈使用*/ char c； int i=0，t=0，top=0； /*t 作为 exp 的下标，top 作为 stack 的下标*/ do /*获取用户输入的逆波兰表达式*/ i+； scanf(%c，&expi)； while (expi!=# & i=0 & c=9) /*判定为数字字符*/ d=c-0； /*将数字字符转换成对应的数值*/ top+； stacktop=d； else /*判定是运算符*/ switch (c) case +:stacktop-1=stacktop-1+stacktop；break；case -:stacktop-1=stacktop-1-stacktop；break；case *:stacktop-1=stacktop-1*stacktop；break； case/:if(stacktop!=0) stacktop-1=stacktop-1/stacktop； else printf(除零错误!n)；break; top-； c=expt；t+； printf(计算结果是:%g，stacktop)； 实验四：4、请编写函数int fun(char *a, char *b),函数的功能是求在字符串a中出现字符串b次数。在主函数中输入两个字符串、调用函数fun、输出结果。#include #include #define NULL 0int fun(char *a,char *b) int num=0,len;/*num计数，len为b串的长度*/ char *p,*s;/*p为源串，s为子串位置*/ p=a; len=strlen(b); while (strlen(p)len) s=strstr(p,b); if (s!= NULL) num+; else break; p=s+len; return(num);main()char str181,str281,*cp1,*cp2;cp1=str1;cp2=str2;gets(cp1);gets(cp2);printf(the number of %s in %s is %dn,cp2,cp1,fun(cp1,cp2);6、请编写函数void fun(char a20, int n),函数的功能是把n个字符串中所有空格删除。在主函数中输入、调用函数fun、输出结果。#include void fun1(char *a)int i=0;char *p1,*p2;p1=p2=a;while (*p1)if (*p1!= )*p2=*p1;p2+; p1+;*p2=0;void fun(char a20, int n)int i;for (i=0;in;i+) fun1(ai);main()int i;char str20=aa aa a,b bb b , c c ;fun(str,3);printf(the string of result is:n);for (i=0;i3;i+) puts(stri);getch();7、请编写函数void fun(char a20, int n),函数的功能是把n个字符串排序。在主函数中输入、调用函数fun、输出结果。#include void fun(char a20, int n)int i,j,k;char *temp;for (i=0;in-1;i+) for (j=0;j0) strcpy(temp,aj); strcpy(aj,aj+1); strcpy(aj+1,temp); main()int i;char str20=b bb b ,aa aa a,c c ;fun(str,3);printf(the string of result is:n);for (i=0;i3;i+) puts(stri);getch();实验五：7、对于二维数组 Amn，其中 m80，n80，先读入 m 和 n，然后读该数组的全部元素，对如下三种情况分别编写相应函数： （1）求数组 A 靠边元素之和； （2）求从 A00开始的互不相邻的各元素之和； （3）当 m=n 时，分别求两条对角线上的元素之和，否则打印出 mn 的信息。解： （1）本小题是计算数组 A 的最外围的 4 条边的所有元素之和，先分别求出各边的元素之和，累加后减除 4 个角的重复相加的元素即为所求。 （2）本小题的互不相邻是指上、下、左、右、对角线均不相邻，即求第 0，2，4，.的各行中第 0，2，4，.列的所有元素之和，函数中用 i 和 j 变量控制即可。 （3）本小题中一条对角线是 Aii，其中（0im-1），另一条对角线是 Am-i-1，i，其中（0im-1），因此用循环实现即可。实现本题功能的程序如下： #include /*实现(1)小题功能的函数*/ void proc1(maxix A) int s=0，i，j; for (i=0;im;i+) /*第一列*/ s=s+Ai1; for (i=0;im;i+) /*最后一列*/ s=s+Ain; for (j=0;jn;j+) /*第一行*/ s=s+A1j; for (j=0;jm;j+) /*最后一行*/ s=s+Amj; for (j=0;jn;j+) /*第一行*/ s=s+A1j; for (j=0;jm;j+) /*最后一行*/ s=s+Amj; s=s-A00-A0n-