数据结构课程设计实验报告

数据结构和算法课程设计报告姓 名： 林小琼 学 号： 0907022118 班 级： 09网络工程 设计时间： 2011.1.102011.1.14 审阅教师： 林仙丽 目 录一课程设计的目的和要求（含设计指标）.2二方案实现和调试.22.1仓库管理系统.22.2通讯录管理系统.52.3猴子选大王.72.4.二叉树运算（最近祖先）.72.5各种排序.8三课程设计分析和总结.9四源程序清单.9一. 课程设计的目的和要求（含设计指标）设计目的：1、培养学生运用算法和数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题；2、培养学生独立设计程序和解决问题的能力，培养学生团队协作集成程序模块及调试能力；3、培养学生初步的软件设计及软件测试的能力。设计任务及要求基本要求：1、学生必须仔细阅读数据结构课程设计指导书，认真主动完成课设的要求。有问题及时主动通过各种方式和教师联系沟通； 2、学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报； 3、课程设计按照教学要求需要一周时间完成，一周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序15小时； 4、根据设计报告要求编写设计报告，主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论；5、每个人必须有可运行的程序，学生能对自己的程序面对教师提问并能熟练地解释清楚，学生回答的问题和程序运行的结果作为评分的主要衡量标准。 二. 方案实现和调试2.1仓库管理系统题目内容描述：设计一个仓库管理系统，可以按照顺序和货物名称查询仓库的存储情况，也可以增加或删除货物。 struct nodeint NO; /商品编号 char namemax; /商品名称 int count; /商品数量;2.1.1算法描述及实验步骤主要模块的算法描述（1）直接生成一个链表，增加则在后面直接插入一个结点（2）定义该链表的头指针，一个个指下去，直到它等于要查询的结点，打印并推出。（3）删除流程图 主界面选项要求输入数字，错误输入有提示且要求重新输入。货物信息输入时，编号为整型，名称为10个字符，数量为整型。同时输入货物信息时，编号输入n作为结束符。2.1.2调试过程及实验结果（1）存入仓库货物信息（2）打印出仓库货物信息并插入、增加货物信息，分别存入要增加商品编号、商品名称、数量。（3）增加后并一起打印出来，列表如下。接下来实现查询功能，你可以根据商品编号查询，也可以跟据商品名称查询，若仓库里没有该商品信息，则输出查找失败。若存在，则输出其他对应的商品信息。（4）删除功能。输入要删除的商品编号，则该商品在仓库里的记录取消；删除后打印出剩余商品的信息。最后按相应提示结束系统操作。 2.2通讯录管理系统题目描述：通讯录一般包括通讯者的编号、姓名、性别、电话及地址等信息，设计一个通讯录要求实现通讯者的插入、查询、删除、更新、排序操作 struct node char num5; /编号 char name8; /姓名 char sex; /性别 char tel8; /电话 char address100; /地址;2.2.1算法描述及实验步骤主要模块的算法描述（1）插入、查询、删除功能和上题仓库管理系统一样（2）排序功能。我采用冒泡排序法，分为降序、升序两方式。其中最主要是交换两结点，这步较繁琐。下面为交换流程图。p1为p的前指针，q1为q的前指针，比较p、q大小，当符合条件，交换p、q结点，并重新交换p、q指针。 2.2.2调试过程及实验结果该通讯录管理系统和仓库管理系统类似，新添加了一个排序功能。 (1)存入通讯录信息，生成一个链表。(2)打印并输出通讯录信息，列表如下。之后实现插入功能，在其链表后面插入一个新结点，生成一个新链表。分别输入通讯者的编号、姓名、性别、电话、地（3）插入后并一起打印出来，列表如下。接下来实现查询功能，你可以根据通讯者的编号查询，也可以跟据姓名查询，若通讯录里没有该通讯者信息，则输出查找失败若存在，则输出其他对应的通讯者的信息（4）实现删除功能，输入通讯者的编号，则删除该编号对应的其他信息。删除该编号对应的其他信息。删除后打印剩余通讯者的信息，最后退出系统。（5）排序功能。排序分为降序、升序两种方式。由于根据编号排序，通过比较编号的大小依次排序。2.3猴子选大王题目内容描述任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm;输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 2.3.1算法描述及实验步骤主要模块的算法描述主要函数void Select(LinkList head,int m,int n)运用单循环链表来实现，尾结点指向头结点，定义一个中间变量i来实现，当i=n时，删除该结点，i重新申请为0，指针继续指下去，直到删除到只剩一个结点，也就是说，该指针的下一个指针还是指向本身。2.3.2调试过程及实验结果删除报数为n的结点，直到只剩一个结点，则该结点为最终结果，猴子大王。2.4.二叉树运算（最近祖先）题目内容描述：任务：求二叉树中指定两个结点共同的最近祖先2.4.1算法描述及实验步骤主要模块的算法描述：先生成一个二叉排序树，用链表指针来存储。之后运用递归算法求叶子结点，另外申请一个指向二叉树的结构指针来存储叶子结点，生成一个单链表，最后打印出链表。链接是用叶子结点的右孩子域存放指针。 void CreateBiTree创建二叉树 Search Ancestors 查找最近祖先。算法的改进方法：上树存储为整型，可以改进定义为其他类型，建立二叉树2.4.2调试过程及实验结果创建树查找2.5各种排序题目内容描述：任务：用程序实现插入法排序、起泡法改进算法排序；利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。2.5.1算法描述及实验步骤主要模块的算法描述：直接插入排序的基本思想是：当插入第i (i 1) 个对象时，前面的V0, V1, , vi-1已经排好序。这时，用vi的关键码和vi-1, vi-2, 的关键码顺序进行比较，找到插入位置即将vi 插入，原来位置上的对象向后顺移。起泡排序的基本思想是：需反复比较相邻两个数的比较和交换这两种基本操作。对相邻的两个数进行比较时，如果反面的数大于（或小于）前面的数，将这两个数进行交换，大的数（小的数）往前冒。2.5.2调试过程及实验结果直接插入法： 冒泡排序法： 三课程设计分析和总结本次课程设计的运行结果在不断的修改中得到完善！使我对数据结构有了更深的理解，既培养了我运用算法和数据结构的能力，又培养了我对于团队协作集成程序模块及调试能力。平时学的东西终于在这课程设计充分体现出来！这次又学到了很多！四. 源程序清单一：仓库管理#include#include#includetypedef struct nodeint NO;char name20;int count;struct node *next;Storage,*Goods;void showlist1()printf(=storage information= n); printf(numbers name quantityn); printf(001 naicha 100n); printf(002 huoguo 200n); printf(003 qiaokeli 300n);void showlist()printf( 1.add goodsn);printf( 2.look up goodsn);printf( 3.delete goodsn);printf( 4.exit systemn);printf(=n);Goods Inputgoods(Goods head)Storage *p,*q;char a;int ch1,ch3;char *ch2;ch2=(char*)malloc(sizeof(char)*20);head=(Goods)malloc(sizeof(Storage); p=head;p-next=NULL;printf(=input goods information=n);doq=(Storage *)malloc(sizeof(Storage);printf(goods number);scanf(%d,&ch1); q-NO=ch1;printf(goods name);scanf(%s,ch2);strcpy(q-name,ch2);printf(goods quantity);scanf(%d,&ch3);q-count=ch3;p-next=q; p=q;p-next=NULL;getchar();printf(if continue?(y/n);scanf(%c,&a);printf(n);while(a=y|a=Y);return head;Goods Insertgoods(Goods head)Storage *p,*p2;char *ch2;int ch1,ch3;ch2=(char*)malloc(sizeof(char)*20);printf(please input goods numbers name quantityn);p=head;while(p-next!=NULL)p=p-next;p2=(Storage *)malloc(sizeof(Storage);printf(goods numbers);scanf(%d,&ch1);p2-NO=ch1; printf(goods name);scanf(%s,ch2);strcpy(p2-name,ch2);printf(goods quantity);scanf(%d,&ch3);p2-count=ch3;p-next=p2;p2-next=NULL;return head;void Lookupgoods(Goods head)char r,*c2;Storage *p,*p2;int c1;p=p2=head-next;c2=(char*)malloc(sizeof(char)*20);getchar();printf(a.look up by goods numbers:n);printf(b.kook up by goods name:n);printf(please input a or b to look up:n);scanf(%c,&r);if(r=a)printf(please input goods numbers:n); scanf(%d,&c1); getchar(); while(p & p-NO !=c1 )p=p-next;if(p=NULL) printf(no find no this numbern);else printf(name%sn,p-name); printf(quantity%dn,p-count);else if(r=b)printf(please input goods name:n);scanf(%s,c2);getchar();while(p & strcmp(p2-name,c2)!=0 ) p2=p2-next;if(p2=NULL) printf(no find, no this namen);else printf(numbers %dn,p2-NO);printf(quantity %dn,p2-count);else getchar(); printf(input wrong!n); getchar(); void Deletegoods(Goods head)Storage *s,*p=head; int er;printf(please the numbers want to delete);scanf(%d,&er);if(p-next=NULL) printf(no recordn); return ;else while(p-next!=NULL) s=p-next;if(s!=NULL&s-NO=er)p-next=s-next;break;p=p-next;void Printgoods(Goods head)Storage *h=head-next;printf(*n);printf(numbers name quantityn);while(h!=NULL)printf(%d %st %dn,h-NO,h-name,h-count);h=h-next;printf(*n);main() Goods head=NULL; int n,i,j; showlist1();head=Inputgoods(head);system(cls);showlist();Printgoods(head); for(i=0;i+)printf(please input the key want to operate!n);for(j=0;j+)scanf(%d,&n);if(n5)printf(wrong !please input again!n);continue;else break;if(n=1) head=Insertgoods(head); system(cls);showlist(); Printgoods(head);if(n=2)Lookupgoods(head);system(cls); showlist(); Printgoods(head);if(n=3) Deletegoods(head);system(cls);showlist();Printgoods(head);if(n=4) break; printf( cang ku information );return 0;二通讯录管理系统 #include#include#includetypedef struct node char num5; /编号 char name8; /姓名 char sex10; /性别 char tel8; /电话 char address100; /地址 struct node *next;ListNode,*Tel;void showlist()printf(=n); printf( 1.please insert the peoplen); printf( 2.please look up the peoplen); printf( 3.please delete the peoplen); printf( 4.sort numbersn); printf( 5.exit systemn); printf(=n);Tel InputTel(Tel head) ListNode *p,*q;char a;char *ch1,*ch2,*ch3,*ch4,*ch5;ch1=(char*)malloc(sizeof(char)*20); ch2=(char*)malloc(sizeof(char)*20); ch3=(char*)malloc(sizeof(char)*20); ch4=(char*)malloc(sizeof(char)*20); ch5=(char*)malloc(sizeof(char)*20);head=(Tel)malloc(sizeof(ListNode); p=head; p-next=NULL;printf(input communication informationn);do q=(ListNode *)malloc(sizeof(ListNode);printf(numbers:);scanf(%s,ch1);strcpy(q-num,ch1);printf(name:);scanf(%s,ch2);strcpy(q-name,ch2);printf(sex:);scanf(%s,ch3);strcpy(q-sex,ch3);printf(telephone:);scanf(%s,ch4);strcpy(q-tel,ch4);printf(address:);scanf(%s,ch5);strcpy(q-address,ch5); p-next=q; p=q;p-next=NULL;getchar();printf(if continue?(y/n);scanf(%c,&a);printf(n);while(a=y|a=Y);return head;Tel InsertTel(Tel head) /插入 ListNode *p,*p2;char *ch1,*ch2,*ch3,*ch4,*ch5;ch1=(char*)malloc(sizeof(char)*20); ch2=(char*)malloc(sizeof(char)*20); ch3=(char*)malloc(sizeof(char)*20); ch4=(char*)malloc(sizeof(char)*20); ch5=(char*)malloc(sizeof(char)*20);printf(n);p=head;while(p-next!=NULL) p=p-next;p2=(ListNode *)malloc(sizeof(ListNode);printf(numbers:);scanf(%s,ch1);strcpy(p2-num,ch1); printf(name:);scanf(%s,ch2);strcpy(p2-name,ch2);printf(sex:);scanf(%s,ch3);strcpy(p2-sex,ch3);printf(telephone:);scanf(%s,ch4);strcpy(p2-tel,ch4);printf(address:);scanf(%s,ch5);strcpy(p2-address,ch5);p-next=p2; p2-next=NULL;return head;void LookupTel(Tel head) /查询 char r,*c1,*c2;ListNode *p,*p2;p=p2=head-next;c1=(char*)malloc(sizeof(char)*20);c2=(char*)malloc(sizeof(char)*20);getchar();printf(a.by numberlook upn);printf(b.by name loop upn);printf(please input a or b to look upn);scanf(%c,&r);if(r=a) printf(please input numbersn); scanf(%d,c1);getchar();while(p & strcmp(p-num,c1)!=0 ) p=p-next;if(p=NULL) printf(no find ,no this number !n);else printf(name%sn,p-name);printf(sex%sn,p-sex);printf(telphone%dn,p-tel);printf(adderss%sn,p-address);else if(r=b) printf(please input name:);scanf(%s,c2);getchar();while(p & strcmp(p2-name,c2)!=0 ) p2=p2-next;if(p2=NULL) printf(no find, no this name !n);else printf(number%dn,p2-num);printf(sex%sn,p2-sex);printf(telphone%sn,p2-tel); printf(address%sn,p2-address);else getchar(); printf(input wrong!n);getchar();void DeleteTel(Tel head) /删除 ListNode *s,*p=head;char *er;er=(char*)malloc(sizeof(char)*20);printf(please input the numbers want to delete :);scanf(%s,er);if(p-next=NULL) printf(no findn);return ; else while(p-next!=NULL) s=p-next; if(s!=NULL&strcmp(s-num,er)=0) p-next=s-next; break;p=p-next;void SortTel(Tel head) ListNode *p,*p1,*q1,*q,*t;char e;p1=head; p=head-next; q=p;getchar();printf(please chance the way want to sort？(a.jiangxu b.shengxu)n);scanf(%c,&e); while(p!=NULL) while(q!=NULL) q1=q; q=q-next; if(e=b) if(q!=NULL&strcmp(p-num,q-num)0) if(q1=p) p-next=q-next; p1-next=q;q-next=p; else q1-next=q-next;q-next=p-next;p-next=q1-next; q1-next=p;p1-next=q； t=q;q=p;p=t; else if(e=a) if(q!=NULL&strcmp(p-num,q-num)next=q-next;p1-next=q;q-next=p; elseq1-next=q-next;q-next=p-next; p-next=q1-next;q1-next=p; p1-next=q; t=q;q=p; p=t; else printf(wrong！n); q=p-next;p1=p;p=p-next;void PrintTel(Tel head) ListNode *h=head-next;printf(*n);printf(numbers name sex telphone addressn);while(h!=NULL) printf(%s %st %st %s %stn,h-num,h-name,h-sex,h-tel,h-address);h=h-next;printf(*n);int main()Tel head=NULL;int i,j,n;head=InputTel(head);system(cls);PrintTel(head);showlist();for(i=0;i+)printf(please input the key want to operate!n);for(j=0;j+)scanf(%d,&n);if(n5)printf(wrong!please input again!n);continue;else break;if(n=1) head=InsertTel(head);system(cls);PrintTel(head);showlist();if(n=2)LookupTel(head);system(cls);PrintTel(head);showlist();if(n=3) DeleteTel(head);system(cls);PrintTel(head);showlist();if(n=4) SortTel(head); system(cls);PrintTel(head);showlist();if(n=5) break;return 0;三猴子选大王#include#includetypedef struct node /定义结点 int data; /结点的数据域struct node *next; /结点的指针域 ListNode;typedef ListNode * LinkList; / 自定义LinkList单链表类型/=用尾插入法建立带头结点的单链表=LinkList CreatListR1(int m) LinkList head=(LinkList)malloc(sizeof(ListNode); /生成头结点 ListNode *r,*s; int i; r=head; r-next=NULL; for( i=1;idata=i;r-next=s; r=s; r-next=head-next; /单循环链表，尾指针指向头指针return head; /返回头指针/=猴子选大王=void Select(LinkList head,int m,int n)ListNode *p, *q;int i;q=head;p=head-next; for(i=1;p-next!=p;i+)if(i=n) /i等于报数 q-next=p-next; /删除结点p p=q-next; /p指向它的下一个结点 i=0; else if(i=n-1) q=p; p=p-next; printf(an zhao %d monkey ,shu %d numbers ,input the monkey are %d hao.n,m,n,p-data);/=主函数= main()int i,m,n;char c； LinkList head; for(i=0;) printf(please input m,n: n); scanf(%d,%d,&m,&n); head=CreatListR1(m); /用尾插入法建立单链表，返回头指针 Select(head,m,n); getchar(); printf(if continue?input y/nn);scanf(%c,&c); if(c=n) break;printf(n); return 0;四、二叉树运算（最近祖先）#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;int i=1;num100=0;int SearchAncestors(BiTree T,int node,int a) if(T) if(T-data=node)return 1; if(SearchAncestors(T-lchild,node,a)=1)ai=T-data;i+;return 1; if(SearchAncestors(T-rchild,node,a)=1)ai=T-data;i+;return 1; return 0;int Search(int node)int s; if(node=0)return 0; for(s=0;nums!=0;s+) if(node=nums)return 1; nums=node; return 0;void CreateBiTree(BiTree *T,int e,int n) int node; while(1) if(n=0)printf(please input the root number(0 is NULL):); if(n=1)printf(please input the %d left child number(0 is NULL):,e); if(n=2)printf(please input the %d right child number(0 is NULL):,e); scanf(%d,&node); if(Search(node)=1)printf(%d