《数据结构试验(cdut)练习题.doc》由会员分享，可在线阅读，更多相关《数据结构试验(cdut)练习题.doc（18页珍藏版）》请在三一办公上搜索。
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; /打印稀疏矩阵 int Print( Matrix M) int i; if(M.tu=0)
