数据结构课程实验设计1 下载本文

cout<<\项目名称:\ cout<<\项目编号:\

cout<<\取前3名还是前5名:\ for(m=0;m<5;m++) {

fread(&s[i].a[j].range[m],sizeof(int),1,fp); if(s[i].a[j].range[m]!=0)

cout<<\名次:\ fread(&s[i].a[j].mark[m],sizeof(int),1,fp); if(s[i].a[j].mark[m]!=0)

cout<<\分数:\ }

cout<

fclose(fp); //关闭文件 }

void Menu() //主菜单函数 {

int number; do {

Head(); MainMenu();

cout<<\ 请选择:\ cin>>number; switch(number) {

case 1: //输入信息 system(\ Head();

cout<<\请输入运动会各学校信息:\

InfoInput(); //信息输入模块 fsave(); //保存信息 system(\ break;

case 2: //输出信息

system(\ InfoOutput(); //信息输出模块 break;

case 3: //查询信息 system(\ Inquiry(); //信息查询模块

break;

case 4: //调用信息

system(\ Head();

Read(); //调用信息模块 system(\ system(\ break;

case 5: //“关于”模块 system(\ Head();

About(); //“关于”界面 system(\ system(\ break;

case 6: //退出系统 system(\ Head();

cout<<\谢谢使用!\ exit(0);

default: //其他

cout<<\对不起,无此功能,请输入正确的功能序号!\ system(\ system(\ break; }

}while(1); }

void main() //主函数 {

Menu(); //主菜单函数 }

四、时间复杂度分析:

用户输入信息时,采用三重循环进行输入,因此信息输入函数的时间复杂度为O(N*(M+W)*k)。利用冒泡排序法进行排序,采用二重循环,时间复杂度为O(N*N)。采用顺序存储结构,信息存放在数组的相应内存单元里,因此查询函数的时间复杂度为O(1)。写信息时可以一次全部写进去,读信息时也可以一次全部读出来,因此写文件函数和读文件函数的时间复杂度都为O(1)。

B一元多项式计算

一 实验任务: 能够按照指数降序排列建立并输出多项式; 能够完成两个多项式的相加、相减,并将结果输入; 一元多项式相加实验

已知 A( x )= a0 + a1x + a2x + ?? + anx 和B(x) = b0 + b1x + b2x +?? + amx ,并在 A( x ) 和 B( x ) 中指数相差很多,求 A( x ) = A( x ) + B(x) 。

程序以以下式子为例: A(x)=2+3x+1x3 B(x)=1+3x+2x2+2x4+12x7+32x8+42x11+2x12 二 实验要求:

在上交资料中请写明:存储结构、多项式相加的基本过程的算法(可以使用程序流程图) 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法; 三 算法设计介绍 1.存储结构分析

根据一元多项式的特点,要表示一个多项式,只要存储第i项以及ai的值,并且如果ai为0的话,该项就不用存储了,从而减少一个存储空间。在线性表中可以通过顺序和链式存储,并用Ti表示一个数据项Ti=(ai,i)。在存储空间分配量上两种结构是一致的,但如果两多项式相加的话需要频繁的做插入操作,顺序表的结构特性决定了插入操作的时间复杂度为O(n/2),链式表的时间复杂度为O(1),并且如果存储的是一个排好序的多项式的话,不需要双向查找,因此选择单链表存储。 2.相加算法分析

首先,由于两个多项式A(x)和B(x)的指数相差非常多,因此一定要把输入的多项式按照指数i排好序,防止过高的查找时间复杂度;其次,两个AB多项式同时从head开始查找,AB指数i相同的计算相加ai值存入A表,并且回收不需要的B空间,指数不同的,B指数小的节点插到A指数大的前面。以此往后推移。其时间复杂度为o(n)。

四 附程序源代码 一元多项式验证: #include #include #include

typedef struct term //项的表示,多项式的项作为LinkList的数据元素 {

float coef; //系数 int expn; //指数 struct term *next; }term;

term* CreatPolyn(term *P,int m) // 输入m项的系数和指数,建立表示一元多项式的有序链表P {

2

n

2

m

if(m <= 0) return NULL;

term *h = P = (term*)malloc(sizeof(term)), *q; P->coef = 0.0; int i;

printf(\依次输入%d个非零项,请注意输入格式,系数和指数之间要有空格,ex:2 2 3 1\\n\

for (i = 1; i <= m; ++i) // 依次输入m个非零项 {

scanf(\ if(P->coef) q = P;

P = P->next = (term*)malloc(sizeof(term)); }

q->next = NULL; free(P); return h; } // CreatPolyn

term* selsort(term *h) {

term *g, *p, *q; if(!h) return NULL; float f;

int i, fini = 1;

for(g = h;g->next&&fini;g = g->next) {

fini = 0;

for(p = h,q = h->next;q;p = p->next,q = q->next) if (p->expn < q->expn) {

f = p->coef;i = p->expn;

p->coef = q->coef;p->expn = q->expn; q->coef = f;q->expn = i; fini = 1; } }

for(g = h,p = g->next;p;) if(g->expn==p->expn) {

g->coef += p->coef; g->next = p->next; q = p;

p = p->next; free(q);

}else if(g->next) {

g = g->next; p = p->next; }

return h; }

void PrintfPoly(term *P) {

term *q = P; if(!q) {

putchar('0'); return; }

if(q->coef!=1) {

printf(\

if(q->expn==1) putchar('X');

else if(q->expn) printf(\ }

else if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf(\ q = q->next; while (q) {

if(q->coef > 0) putchar('+'); if(q->coef!=1) {

printf(\

if(q->expn==1) putchar('X');

else if(q->expn) printf(\ }

else if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf(\ q = q->next; } }

Compare(term *a, term *b) {