数据结构上机实验答案

数据结构实验指导书答案实验一：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 ，要求用指针进行设计。即设计函数intfun(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 ，intn), 函数的功能是把数组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,intn)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,intn)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、请编写函数intfun(inta44), 函数的功能是把矩阵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(inta4,intn)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 50 typedef 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 0 typedef 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 50 typedef 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 50 typedef 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 0 typedef 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;/isreverse8、编写一个函数将一般算术表达式转化为逆波兰表达式。解：假设表达式中的符号以字符形式由键盘输入（为简单起见，设算术表达式中的参加运算的数都只有一位数字），该算术表达式存放在字符型数组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 maxsize100/* 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 ；/* 获取用户输入的表达式*/ doi+ ；scanf(%c ， &stri) ； while (stri!=# & i= 0 & ch= 9)/* 判定为数字 */expt=ch ； t+ ； elseif (ch= ()/*判定为左括号*/top+ ； stacktop=ch； elseif (ch= )/* 判定为右括号*/while (stacktop!=()expt=stacktop； top- ；t+ ； top- ；else if (ch=+| ch= -)/*判定为加减号*/while (top!=0 & stacktop!=() expt=stacktop； top- ；t+ ； top+ ； stacktop=ch；elseif (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；elseprintf( 除零错误 !n) ； break;top- ；c=expt ； t+ ；printf( 计算结果是 :%g ，stacktop) ；实验四：4、请编写函数intfun(char*a, char*b), 函数的功能是求在字符串a 中出现字符串b 次数。在主函数中输入两个字符串、调用函数fun 、输出结果。#include #include #define null 0intfun(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 %sin %s is %dn,cp2,cp1,fun(cp1,cp2);6、请编写函数voidfun(chara20, intn), 函数的功能是把n个字符串中所有空格删除。在主函数中输入、调用函数fun 、输出结果。#include voidfun1(char*a)int i=0;char *p1,*p2; p1=p2=a;while (*p1)if (*p1!= )*p2=*p1; p2+; p1+;*p2=0;voidfun(chara20, intn)int i;for (i=0;in;i+) fun1(ai);main()int i;char str20=aaaa a,b bbb , c c; fun(str,3);printf(the string of result is:n); for (i=0;i3;i+)puts(stri); getch();7、请编写函数voidfun(chara20, intn), 函数的功能是把n 个字符串排序。 在主函数中输入、调用函数fun、输出结果。#include voidfun(chara20, intn)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 bbb ,aaaa a,c c; fun(str,3);printf(the string of result is:n);for (i=0;i3;i+) puts(stri);getch();实验五：7、对于二维数组amn ，其中m 80， n 80 ，先读入m和 n，然后读该数组的全部元素，对如下三种情况分别编写相应函数：（ 1 ）求数组a 靠边元素之和；（ 2 ）求从a00 开始的互不相邻的各元素之和；（ 3 ）当m=n时，分别求两条对角线上的元素之和，否则打印出m n 的信息。解： （ 1）本小题是计算数组a 的最外围的4 条边的所有元素之和，先分别求出各边的元素之和，累加后减除4 个角的重复相加的元素即为所求。（ 2）本小题的互不相邻是指上、下、左、右、对角线均不相邻，即求第0 ， 2 ， 4 ， . 的各行中第0 ， 2 ，4， . 列的所有元素之和，函数中用i 和 j 变量控制即可。（ 3 ）本小题中一条对角线是aii ，其中（ 0 im-1 ），另一条对角线是am-i-1 ，i ，其中（ 0 i m-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-1-am-10-am-1n-1;/* 减去4 个角的重复元素值*/printf(s=%dn， s); /* 实现 (2) 小题功能的函数*/ void proc2(maxix a)int s=0 ， i， j; i=0;whi