数据结构课程实 验 报 告.doc

实 验 报 告专业班级： 08级管理科学一班小组成员： 吴蓓蕾 裴倩茹 白雪 贾真真完成日期： 2010年7月7日小组分工情况题目一：基础题 完成人员：白雪题目二：应用题 完成人员：吴蓓蕾题目三：综合题 完成人员：裴倩茹题目四：拓展题 完成人员：贾真真 吴蓓蕾短学期小结 完成人员：白雪题目一基本题：数制的转换（十进制到m进制转换）1、解题思路（较详细说明）十进制转化即为栈的应用。首先定义栈的结构体，入栈函数，出栈函数。再添加转换函数。转换函数思路：用栈暂存低位值（n/m循环取余，依次压入栈中，直到余数为0时，循环终止。最后，将余数逆序输出，即出栈。）2、函数调用图及各函数的功能（简要说明）函数中用到三个函数：conversion函数，pop函数，push函数Conversion函数为将十进制数n转化为m进制Pop函数为出栈函数Push函数为入栈函数;Main函数函数调用图Conversion函数Pop函数 Push 函数3、三组测试数据（原始数据，预期结果，实际结果）第一组数据原始数据：取10，2预期结果：1010实际结果：第二组数据原始数据；取15，2预期结果：1111实际结果：第三组数据原始数据：64，8预期结果：100实际结果：4、含注释的源程序（说明主要变量的作用，函数段的功能）#include #include#includestruct Lstack /定义链栈的结构体 int data; struct Lstack *next;struct Lstack *push(struct Lstack *top,int k) /定义入栈函数 struct Lstack *p; p=(struct Lstack *)malloc(sizeof(struct Lstack); /新分配一个空间 p-data=k; /栈顶top指针上移 p-next=top; top=p; return top;struct Lstack *pop(struct Lstack *top) /定义出栈函数 int x; while(top!=NULL) /top不为空时 x=top-data; printf(%d ,x); /数据输出 top=top-next; /栈顶top指针下移 return top;void conversion(int n, int m) /十进制数n与m进制数的转换 struct Lstack *s=NULL; while(n) s=push(s,n%m); n=n/m; while(s!=NULL) s=pop(s);void main()int n,m;printf(Input 十进制数,转换进制数:);scanf(%d,&n); scanf(%d,&m);conversion(n,m);printf(n);5、编译与运行情况（存在的问题）#include #include 添加语句#includestruct Lstack int data; struct Lstack *next;struct Lstack *push(struct Lstack *top,int k) struct Lstack *p; p=(struct Lstack *)malloc(sizeof(struct Lstack); 未对malloc进行定义，不能应用。 p-data=k; p-next=top; top=p; return top;struct Lstack *pop(struct Lstack *top) int x; while(top!=NULL) x=top-data; printf(%d ,x); top=top-next; return top;void conversion(int n, int m) struct Lstack *s=NULL; while(n) s=push(s,n%m); n=n/m; while(s!=NULL) s=pop(s);void main()int n,m;printf(Input 十进制数,转换进制数:);scanf(%d,&n); scanf(%d,&m);conversion(n,m);printf(n); 题目二应用题：将两个有序线性表合并成一个有序线性表，并去掉重复元素。1、解题思路（较详细说明）算法分析算法主要包括：搜索、比较、插入三个操作。搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小（实际上是ASCII值的比较）；插入：将两个结点中数据小的结点插入新链表2、函数调用图及各函数的功能（简要说明）该程序用到了三个函数:CreateListR函数: 功能：建立链表MergeList函数: 功能：合并链表PrintList函数: 功能： 输出链表函数调用图：Main函数CreateList函数MergeList函数PrintLis函数3、三组测试数据（原始数据，预期结果，实际结果）第一组数据测试：原始数据：15648 28379 预期结果：123456789实际结果：第二组数据测试：原始数据：1458 2349 预期结果：1234589实际结果：第三组数据测试：原始数据：1568 2349 预期结果：12345689实际结果：第四组数据测试：原始数据： abfi AFY 预期结果：AFYabfi实际结果：4、含注释的源程序（说明主要变量的作用，函数段的功能）#include #include #include typedef struct Lnode /结构体定义 char data; /数据域 struct Lnode *next; /指针域ListNode; ListNode *CreateListR() /尾插法建立链表char ch;ListNode *head,*s,*r;head=r=NULL;while(ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch; s-next=NULL;if(head=NULL) head=s;elser-next=s;r=s;return head;struct Lnode *MergeList(struct Lnode *ha, struct Lnode *hb) /合并链表 struct Lnode *pa=ha, *pb=hb, *hc=NULL, *r=hc; /两个指针pb,pc从两个链表ha,hb的表头开始搜索,指针r指向新链表hc的头 while(pa&pb) / 两个链表都不为空时 if(pa-datadata) if(hc=NULL) hc=pa; else r-next=pa; r=pa; pa=pa-next; /将较小的结点插入新链表 else if(hc=NULL) hc=pb; else r-next=pb; r=pb; pb=pb-next; if(hc!=NULL) r-next=pa?pa:pb; else hc=pa?pa:pb; return hc; PrintList(struct Lnode *c) /打印合并后链表struct Lnode *p;p=c;while(p!=NULL) /当p指向的非空时 printf(%c,p-data); /取出数据域中的值，并输出 p=p-next;printf(n); main() /主程序 struct Lnode *a,*b,*c; a=CreateListR(); / 建立链表 b=CreateListR(); c=MergeList(a,b); /合并链表 PrintList(c); /输出链表 5、编译与运行情况（存在的问题）第一组数据中：运行时输出的是没有意义的字符原程序部分代码：PrintList(struct Lnode *c) /打印合并后链表struct Lnode *p;p=c-next; 修改：p=c; /原因：merge函数建立的是没有空头结点的链表while(p!=NULL) printf(%d,p-data); 修改：%c /原因：结构体定义数据类型 为字符型 p=p-next;printf(n);第二组数据中：运行输出的字符串并没有按从小到达的顺序排列。 原因：建立链表的时候采用的是头插法，与合并函数取较小结点插入新链表的思想有冲突，故修改时改为尾插法建立链表。题目四扩展题：学生成绩管理系统1、解题思路（较详细说明）利用结构体定义及C语言知识将学生成绩这一实体转化为数组类型的记录，其中包括学生学号、姓名、分数三类数据项，利用记录中的关键字，通过输入、显示、排序、插入、删除、查询、统计等函数对学生数据结构课程的成绩进行管理分析。2、函数调用图及各函数的功能（简要说明）函数调用图：Main()menu_select()Insert_a_record()Delete_a_record()Query_a_record()Statistic()Sort_by_num()Display()Input()menu_select() 功能：提供交互界面，供用户选择该系统的各个功能和选项。Input() 功能：交互输入若干条记录、信息。Display() 功能：显示所有输入的符合定义的记录。Sort_by_num() 功能：按学号利用冒泡排序法对记录进行排序。Insert_a_record() 功能：交互式插入一条记录，再利用冒泡排序法对记录进行排序Delete_a_record() 功能：按姓名进行交互式查找，删除一条查找到的记录Query_a_record() 功能：按姓名进行交互式输入，查找并显示一个记录Statistic() 功能：新增功能，输出统计信息3、程序运行演示及检验（1）在“菜单”中选择Input records ，输入四条记录。（2）选择Display All Rrcords ,显示输入的记录（3）选择Sort ，显示排序成功选择Display All Rrcords ，查看排序后的结果（4）选择Insert a Records ,输入需要插入的记录选择Display All Rrcords ，查看输入的记录（5）选择Delete a Record ,输入删除记录中的学生姓名删除后的结果（6）选择Query ,输入所要查询记录中学生的姓名，显示出查询结果（7）选择Statistic ,显示所有的记录数量、最高分者的记录、最低分者的记录和平均分（8）选择Quit，结束程序4、含注释的源程序（说明主要变量的作用，函数段的功能）#include /*引用库函数*/ #include #include #include typedef struct /*定义结构体数组*/ char num10; /*学号*/ char name20; /*姓名*/ int score; /*成绩*/ Student; Student stu80; /*结构体数组变量*/ int menu_select() /*菜单函数*/ char c; do printf(t*Students Grade of Data Struture Course Management System*n); /*菜单选择*/ printf(t | 1. Input Records |n); printf(t | 2. Display All Records |n); printf(t | 3. Sort |n); printf(t | 4. Insert a Record |n); printf(t | 5. Delete a Record |n); printf(t | 6. Query |n); printf(t | 7. Statistic |n); printf(t | 0. Quit |n); printf(t*n); printf(ttGive your Choice(0-7):); c=getchar(); /*读入选择*/ while(c7); return(c-0); /*返回选择*/ int Input(Student stud,int n) /*输入若干条记录*/ int i=0; char sign,x10; /*x10为清除多余的数据所用*/ while(sign!=n&sign!=N) /*判断*/ printf(tttstudents num:); /*交互输入*/ scanf(ttt%s,studn+i.num); printf(tttstudents name:); scanf(ttt%s,studn+); printf(tttstudents score:); scanf(ttt%d,&studn+i.score); gets(x); /*清除多余的输入*/ printf(tttany more records?(Y/N); scanf(ttt%c,&sign); /*输入判断*/ i+; return(n+i); void Display(Student stud,int n) /*显示所有记录*/ int i; printf(ttt-n); /*格式头*/ printf(tttnumber name scoren); printf(ttt-n); for(i=1;i1&i%10=0) /*每十个暂停*/ printf(ttt-n); /*格式*/ printf(ttt); system(pause); printf(ttt-n); printf(ttt); system(pause); void Sort_by_num(Student stud,int n) /*按学号排序*/ int i,j,*p,*q,s; char t10; for(i=0;in-1;i+) /*冒泡法排序*/ for(j=0;j0) strcpy(t,studj+1.num); strcpy(studj+1.num,studj.num); strcpy(studj.num,t); strcpy(t,studj+1.name); strcpy(studj+1.name,); strcpy(,t); p=&studj+1.score; q=&studj.score; s=*p; *p=*q; *q=s; int Insert_a_record(Student stud,int n) /*插入一条记录*/ char x10; /*清除多余输入所用*/ printf(tttstudents num:); /*交互式输入*/ scanf(ttt%s,studn.num); printf(tttstudents name:); scanf(ttt%s,); printf(tttstudents score:); scanf(ttt%d,&studn.score); gets(x); n+; Sort_by_num(stud,n); /*调用排序函数*/ printf(tttInsert Successed!n); /*返回成功信息*/ return(n); int Delete_a_record(Student stud,int n) /*按姓名查找，删除一条记录*/ char s20; int i=0,j; printf(ttttell me his(her) name:); /*交互式问寻*/ scanf(%s,s); while(strcmp(,s)!=0&in) i+; /*查找判断*/ if(i=n) printf(tttnot find!n); /*返回失败信息*/ return(n); for(j=i;jn-1;j+) /*删除操作*/ strcpy(studj.num,studj+1.num); strcpy(,studj+1.name); studj.score=studj+1.score; printf(tttDelete Successed!n); /*返回成功信息*/ return(n-1); void Query_a_record(Student stud,int n) /*查找并显示一个记录*/ char s20; int i=0; printf(tttinput his(her) name:); /*交互式输入*/ scanf(ttt%s,s); while(strcmp(,s)!=0&in) i+; /*查找判断*/ if(i=n) printf(tttnot find!n); /*输入失败信息*/ return; printf(ttthis(her) number:%sn,studi.num); /*输出该学生信息*/ printf(ttthis(her) score:%dn,studi.score); void Statistic(Student stud,int n) /*新增功能，输出统计信息*/ int i,j=0,k=0,sum=0; float aver; /*成绩平均值*/ for(i=0;istudi.score) j=i; if(studk.scorestudi.score) k=i; aver=1.0*sum/n; printf(tttthere are %d records.n,n); /*总共记录数*/ printf(tttthe hignest score:n); /*最高分*/ printf(tttnumber:%s name:%s score:%dn,studj.num,,studj.score); printf(tttthe lowest score:n); /*最低分*/ printf(tttnumber:%s name:%s score:%dn,studk.num,,studk.score); printf(tttthe average score is %5.2fn,aver); /*平均分*/ void main() /*主函数*/ int n=0; for(;) switch(menu_select() /*选择判断*/ case 1: printf(tttInput Recordsn); /*输入若干条记录*/ n=Input(stu,n); break; case 2: printf(tttDisplay All Recordsn); /*显示所有记录*/ Display(stu,n); break; case 3: printf(tttSortn); Sort_by_num(stu,n); /*按学号排序*/ printf(tttSort Suceessed!n); printf(ttt); system(pause); break; case 4: printf(tttInsert a Recordn); n=Insert_a_record(stu,n); /*插入一条记录*/ printf(ttt); system(pause); break; case 5: printf(tttDelete a Recordn); n=Delete_a_record(stu,n); /*按姓名查找，删除一条记录*/ printf(ttt); system(pause); break; case 6: printf(tttQueryn); Query_a_record(stu,n); /*查找并显示一个记录*/ printf(ttt); system(pause); break; case 7: printf(tttStatisticn); Statistic(stu,n); /*新增功能，输出统计信息*/ printf(ttt); system(pause); break; case 0: printf(tttHave a Good Luck,Bye-bye!n); /*结束程序*/ printf(ttt); system(pause); exit(0); 5、编译与运行情况（存在的问题）（1）原程序代码：int menu_select() /*菜单函数*/ char c; do printf(t*Students Grade of Data Struture Course Management System*n); /*菜单选择*/ printf(t | 1. Input Records |n); printf(t | 2. Display All Records |n); printf(t | 3. Sort |n); printf(t | 4. Insert a Record |n); printf(t | 5. Delete a Record |n); printf(t | 6. Query |n); printf(t | 7. Statistic |n); printf(t | 0. Quit |n); printf(t*n); printf(ttGive your Choice(0-7):); c=getchar(); /*读入选择*/ while(c7); return(c); /*返回选择*/ 修改为 return(c-0); 原因：程序最后返回的是您输入的字符的ASCII码减去0的ASCII码的值 也就是说，如果选择0就返回0 如果不减返回的是0的ASCII值。 （2）原程序代码：void Display(Student stud,int n) /*显示所有记录*/ int i; printf(ttt-n); /*格式头*/ printf(tttnumber name scoren); printf(ttt-n); for(i=1;i1&i%10=0) /*每十个暂停*/ printf(ttt-n); /*格式*/ printf(ttt); system(pause); printf(ttt-n); printf(ttt); system(pause); （3）本来想加入保存