数据结构试验(cdut)练习题

1、实验一c+语言编程一、实验目的：复习、巩固c+语言上机操作的基本技能和方法，熟悉：框图（或流程图）代码调试修改运行这一基本上机过程。二、实验要求：1 认真阅读和掌握本实验的程序。2. 上机运行程序。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：编写一个程序实现下列目标:1. 从键盘输入集合a、b，长度随机，以-9999表示输入结束，集合a、b的并集和交集，从大到小输出，不能有同样的。#include void intersection(int a,int b,int m,int n) /求交集 for(int i=0;im;i

2、+) for(int j=0;jn;j+) if(ai=bj) coutai ; void union(int a,int b,int m,int n) /求并集 int i=0,j=0; while(im&jn) if(ai=bj) coutaibj) coutai ; i+; else coutbj ; j+;int main()int a100=0,b100=0,m,n,i,j; coutm; cout请输入第一个数组中的元素:; for(i=0;iai; if(ai=-9999) break; coutn; cout请输入第二个数组中的元素:; for(j=0;jbj; if(bj=-

3、9999) break; for(i=0;im;i+) /将数组a按从小到大排序 for(j=i+1;jm+1;j+) if(aiaj) int temp; temp=ai; ai=aj; aj=temp; for(i=0;im;i+)/将数组b按从小到大排序 for(j=i+1;jm+1;j+) if(bibj) int temp; temp=bi; bi=bj; bj=temp; cout交集：; intersection(a,b,m,n); coutendl; cout并集：; union(a,b,m,n); coutendl; return 0;2.分别输入圆柱体的半径和高，求其体积；

4、输入球半径，求其表面积；输入长方体的长、宽、高，求其体积。#includeint main()const double pi=3.1415926;double r1,h,v1,r2,area,length,wide,height,v2;couth;cinr1;v1=pi*r1*r1*h;cout圆柱体的体积:v1endl;coutr2;area=4*pi*r2*r2;cout球的表面积:areaendl;coutlength;cinwide;cinheight;v2=length*wide*height;cout长方体的体积:v2endl;return 0;实验二线性表的应用一、实验目的：掌握

5、线性表的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。二、实验要求：1 认真阅读和掌握本实验的程序。2. 上机运行程序。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：1. 运行下述程序。说明它所实现的功能。程序如下：#include #include /*顺序表的定义：*/#define listsize 100typedef structint datalistsize;/*向量data用于存放表结点*/int length;/*当前的表长度*/seqlist;void main()void createlis

6、t(seqlist *l,int n);void printlist(seqlist *l,int n);int locatelist(seqlist *l,int x);void insertlist(seqlist *l,int x,int i);void deletelist(seqlist *l,int i); seqlist l;int i,x;int n=10;/*the length of list*/l.length=0;createlist(&l,n);/*creat the list*/printlist(&l,n);/*print the list*/printf(inp

7、ut the research element);scanf(%d,&x);i=locatelist(&l,x);printf(the research position is %dn,i);/*顺序表查找*/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);insertlist(&l,x,i);/*顺序表插入*/printlist(&l, l.length);/*打印顺序表*/printf(input the position of delet

8、en);scanf(%d,&i);deletelist(&l,i);/*顺序表删除*/printlist(&l,n);getchar();/*打印顺序表*/*顺序表的建立：*/void createlist(seqlist *l,int n)int i;printf(please input n numbersn);for(i=1;idatai);l-length=n;/*顺序表的打印：*/void printlist(seqlist *l,int n)int i;printf(the sqlist isn);for(i=1;idatai);/*顺序表的查找：*/int locatelist(

9、seqlist *l,int x)int i;for(i=1;idatai)=x) return(i);break; return(0);/*顺序表的插入：*/void insertlist(seqlist *l,int x,int i)int j;for(j=l-length;j=i;j-)l-dataj+1=l-dataj;l-datai=x;l-length+;/*顺序表的删除：*/void deletelist(seqlist *l,int i) int j;for(j=i;jlength)-1;j+)l-dataj=l-dataj+1;2. 设计一个100位以内的长整数加减运算的程序

10、。#include#includeint getlength(char *ch) int i; for(i=0;i100;i+) if(chi=0)break; return i;void plusdata(int *dt,int *pdt,int k,int kk) int i; for(i=0;i9) dti-=10; dti+1+; if(dti9) dti-=10; dti+1+; if(dtkk!=0) i=kk; else i=kk-1; for(;i=0;i-) coutdti; coutendl;void minusdata(int *dt,int *mdt,int k,int

11、 kk,int signal) int i; for(i=0;ik;i+) dti=dti-mdti; if(dti0) dti+=10; dti+1-; if(dti0) dti+=10; dti+1-; while(dtkk=0) kk-; if(signal=0) cout=0;i-) coutdti; coutendl;void main() char ch1100,ch2100,ch02,ch; int data1100,data2100; int i,j,k1,k2,flag=0; for(i=0;i100;i+) data1i=0; data2i=0; coutyou can i

12、nput the first datach1; coutyou can input the second datach2; coutwhat operation you want?( + or - )ch; ch01=0; j=0; while(ch1j=0) j+; for(i=0;i99-j;i+) ch1i=ch1i+j; j=0; while(ch2j=0) j+; for(i=0;i99-j;i+) ch2i=ch2i+j; k1=getlength(ch1); k2=getlength(ch2); j=k1; for(i=0;ik1;i+) j-; ch00=ch1j; data1

13、i=atoi(ch0); if(ch1i9) flag=1; j=k2; for(i=0;ik2;i+) j-; ch00=ch2j; data2i=atoi(ch0); if(ch2i9) flag=1; if(flag=0) if(ch=+) if(k1data2k1-1) minusdata(data1,data2,k2,k2,1); else minusdata(data2,data1,k2,k2,0); else if(k1k2) minusdata(data1,data2,k2,k1,1); else minusdata(data2,data1,k1,k2,0); else cou

14、tyou have input a invaluable char!endl;四、 注意事项：1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序；2. 输入输出要求：每四位一组，组间用逗号分隔；3. 加和减分别用不同的程序实现；4. 程序应考虑输入数据的符号。实验三单链表操作一、实验目的：掌握握单链表的基本操作：插入、删除、查找等运算。二、实验要求：1 认真阅读和掌握本实验的程序。2. 上机运行程序。3. 保存和打印出程序的运行结果，并结合程序进行分析。4. 按照操作需要，打印出文件清单和运行结果。三、实验内容：1. 运行下述程序。说明它所实现的功能。#include#include#

15、include#includetypedef struct node int data; struct node *next; node;/*/node *create()node *p,*head;int x;head=(node *)malloc(sizeof(node);head-next=null;printf(input data,-1 to end!n);scanf(%d,&x);while(x!=-1) p=(node *)malloc(sizeof(node); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x);retu

16、rn(head);/*/void output(node *head) node *p; p=head; printf(begin to dump the linklist.n); while(p-next!=null) printf(-%d,p-next-data); p=p-next; printf(nthe linklist ended!n);/*/int listlen(node *head) int i=0; node *p=head; while(p-next!=null) i+; p=p-next; return(i);/*/int get(node *head,int i)in

17、t j=0;node *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void del(node *head,int i)node *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void ins(node *head,int i,int e)node *p=head,*q;int j=0;while(p-next&jnext

18、;if(!p-next&ji-1) printf(wrong positionn );else q=(node *)malloc(sizeof(node); q-data=e; q-next=p-next; p-next=q;/*/void main() node *head; int length; int i,element; head=create(); output(head); length=listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d

19、,&i); element=get(head,i);printf(the element of the order is %dn,element); printf(input the del position n); scanf(%d,&i); del(head,i); output(head); printf(input the insert posion and element:n); scanf(%d%d,&i,&element); ins(head,i,element); output(head); getchar();2. 编写一个程序实现下列目标:1) 建立一个链表，用于存放成绩（

20、整型）；2) 输出链表中的所有数据、平均成绩和最高成绩。#includeusing namespace std;struct node int id;int score;node* next;void display(const node*);node* create();void main() node* head = null;head = create();if(head != null) display(head);else cout学生人数为0endl;node* create() node *head, *temp;int n;coutn;if(n = 0) return null

21、;head = new node; temp = head;for(int i = 1; i = n; i+) cout请输入第itemp-id;cout请输入第itemp-score;if(i != n) temp-next = new node; temp = temp-next; temp-next = null;return head;/display函数void display(const node* head) int i = 1;int sum = 0;int max = head-score;coutendl;while(head) cout第i个学生成绩: scorescor

22、e;if(head-score max) max = head-score;head = head-next;i+;cout平均分：sum/(i-1)endl;cout最高分：maxendl;四、 注意事项：1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。2. 数据个数和数据从键盘输入，每个结点包括学号和成绩。实验四 栈的基本操作一、 实验目的：掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求：1 认真阅读和掌握本实验的算法；2 上机将本算法实现； 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容：利用栈的基本操作实现将任意一个十进制整数转化为r

23、进制整数。算法为：1 定义栈的顺序存取结构2 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3 定义一个函数用来实现上面问题：十进制整数x和r作为形参初始化栈只要不为重复做下列动作将入栈x=x/r只要栈不为空重复做下列动作栈顶出栈输出栈顶元素四、 注意事项：1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。#include#define maxsize 100#includestruct stack int datamaxsize; int top;void init(struct stack *s) s-top=-1;int empty(struct stack *s)

24、if(s-top=-1) return 1; else return 0; void push(struct stack *s,int i) if(s-top=maxsize-1) printf(stack is fulln); return; s-top+; s-datas-top=i;int pop(struct stack *s) if(empty(s) printf(stack is empty); return -1; return(s-datas-top-);void trans(int num) struct stack s; int k; int(&s); while(num)

25、 k=num%16; push(&s,k); num=num/16; while(!empty(&s) k=pop(&s); if(k10) printf(%d,k); else printf(%c,k+55); printf(n);void main() int num; int r; printf(input r); scanf(%d,&r); /clrscr(); printf(input a num,-1 to quit:n); scanf(%d,&num); while(num!=-1) trans(num); scanf(%d,&num); 实验五 数组的基本操作一、实验目的：回顾

26、c+语言中数组的定义和基本应用；二、 实验要求：1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。三、 实验内容：有m个学生，学习n门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩。四、 注意事项：1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。#define m 5#define n 4#include stdio.hvoid main() int i,j; static float scorem+1n+1=78,85,83,65, 88,91,89,93, 72,65,54,75,86,88

27、,75,60, 69,60,50,72; for(i=0;im;i+) for(j=0;jn;j+) scorein += scoreij; scoremj += scoreij; scorein /= n; for(j=0;jn;j+) scoremj /= m; /clrscr();printf(学生编号 课程1 课程2 课程3 课程4 个人平均n);for(i=0;im;i+) printf(学生%dt,i+1); for(j=0;jn+1;j+) printf(%6.1ft,scoreij); printf(n); for(j=0;j8*(n+2);j+) printf(-); pri

28、ntf(n课程平均); for(j=0;jn;j+) printf(%6.1ft,scoremj); printf(n); getchar(); 实验六稀疏矩阵运算一、实验目的：掌握三元组法存储稀疏矩阵的方法及相关的基本操作。二、 实验要求：1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容：编写一个程序实现下列目标。1，用三元组法存放稀疏矩阵；2，求出矩阵相乘结果；3，输出结果矩阵。#include #include #define ok 1 #define error 0 #define maxsize 100 /最多非0元

29、素的个数 #define maxr 50 /rpos所能处理的最大行数 #define maxc 50 /系数矩阵相乘时，保留临时列结果的数组tempmaxc typedef struct node /定义稀疏矩阵结点 int i; int j; int data; node; typedef struct matrix /定义稀疏矩阵（可以快速访问） int mu, nu, tu; node matrixmaxsize+1; int rposmaxr+1; matrix; int creatsmatrix( matrix* m ); /创建一个矩阵（由用户输入原始矩阵，转化为稀疏矩阵方式储存

30、） int print( matrix m ); /打印一个稀疏矩阵 int mul_smatrix( matrix m, matrix n, matrix *q); /两个稀疏矩阵相乘 int main() matrix a1, a2, a3; /定义矩阵 creatsmatrix( &a1 ); creatsmatrix( &a2 ); if( a1.nu=a2.mu ) /判断能否相乘 mul_smatrix( a1, a2, &a3 ); printf(两矩阵相乘得：n); print(a3); system(pause); return 0; /构建稀疏矩阵 int creatsma

31、trix( matrix* m ) int temp, i,j; printf(输入矩阵的行列数：); scanf(%d%d, &m-mu, &m-nu); m-tu=0; printf(按行序输入矩阵：n); for( i=1; imu; i+) m-rposi=m-tu+1; /每计算完一行，给rpos赋值 for( j=1; jnu; j+) scanf(%d,&temp); if( temp ) /非0值保存 m-matrixm-tu+1.i= i; m-matrixm-tu+1.j= j; m-matrixm-tu+1.data=temp; m-tu+; return ok; /打印

32、稀疏矩阵 int print( matrix m) int i; if(m.tu=0) printf(空矩阵nn); return error; printf(itjtdatan); for( i=1; itu=0;/初始化q q-mu=m.mu; q-nu=m.nu; if(m.tu*n.tu!=0) /非零矩阵 for(arow=1; arow=m.mu; arow+) for(i=1; irposarow=q-tu+1; /给q-rpos数组赋值 mlim = arowm.mu ? m.rposarow+1 : m.tu+1;/m中第arow行在结点数组中的范围 for( mcol=m.

33、rposarow; mcolmlim; mcol+ )/遍历m中第arow行的每一个j mj=m.matrixmcol.j; nlim = mjn.mu ? n.rposmj+1 : n.tu+1;/在n中找到行号i等于m中的列号j的位置 for( nrow=n.rposmj; nrownlim; nrow+ )/乘积元素在q中的列号 ctempn.matrixnrow.j += m.matrixmcol.data * n.matrixnrow.data; for(i=1; inu; i+)/列号对应元素不为零，赋值 if( ctempi ) if( +q-tu maxsize ) retur

34、n 0; q-matrixq-tu.i = arow; q-matrixq-tu.j = i; q-matrixq-tu.data = ctempi; return 1; 四、 注意事项：1. 在磁盘上创建一个目录，专门用于存储数据结构实验的程序；2. 用数组存放矩阵的三元组，矩阵的行数和列数及非0数据从键盘输入；3. 若两个矩阵不能相乘则输出“error”实验七二叉树1一、实验目的：1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求：1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保

35、存和打印出程序的运行结果，并结合程序进行分析。4 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容：编写一个程序实现下列目标。1，根据输入的数据建立一个二叉树2，输出二叉树（输出的结果应为树型结构）3，输出其前序、中序和后序遍历的结果#include#include#define maxsize 100typedef char elemtype;typedef struct nodeelemtype data;struct node *lchild;struct node *rchild;btnode;void createbtnode(btnode *&b,

36、char *str)btnode *stmaxsize,*p=null;int top=-1,k,j=0;char ch;b=null;ch=strj;while(ch!=0)switch(ch)case(:top+;sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(btnode *)malloc(sizeof(btnode);p-data=ch;p-lchild=p-rchild=null;if(b=null)b=p;elseswitch(k)case 1:sttop-lchild=p;break;case 2:sttop-rchild=p;break;j+;ch=strj;void dispbtnode(btnode *b)if(b!=null)printf(%c,b-data);if(b-lchild!=null|b-rchild!=null)printf();dispbtnode(b-lchild);if(b-rchild!=null)printf(,);dispbtnode(b-rchild);printf();void preorder(btnode *b)if(b!=null)printf(%c,b-data);pre