数据结构课程设计.doc

实验一一实验题目：线性表的综合操作二实验目的: 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表是最基本的线性结构，任何线性结构都可以用线性表表示。线性表的结构在信息检索、程序设计语言的编译等许多方面有广泛的应用。本次设计主要是运用线性表的插入、删除、查找和排序，并运用C语言的一些知识编写出程序使算法得以实现。三设计分析3.1 线性表的结构特点 1）均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数所类 长度。 2）有序性：各数据元素在线性表中的位置只取决于它们的序与，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前趋和后面均只有一个数据元素（直接后继）。 在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈队列和串也是线性表的特殊情况，又称为受限的线性结构。3.2 线性表的常见操作包括： 确定表的长度n，即求表中数据元素的个数； 读表：从左到右（或从右到左）读表，即按a1，a2，an（或an，an-1 ，a1 ）读取数据元素的值； 检索：即在表中查找具有某个特征值的数据元素； 改写：修改、存入表中第i个数据元素（1in），即给第i个数据元素赋值； 插入：在第i-1个和第i个数据元素之间（1in）插入一个新的数据元素，使原来的第i，i+1，n个数据元素变成为第i+1，i+2，n，n+1个数据元素； 删除：删除第i个数据元素（1in），使原来的第i+1，i+2，n个数据元素变成为第i，i+1，n-1个数据元素； 排序：即按某个特征值递增（或递减）的顺序对表中的数据元素重新排列。 归并：将两个以上的有序线性表合并成一个新表。3.3 程序流程图程序流程图查找数据创建线性表删除数据排序插入数据遍历四设计方案系统提供的功能有：线性表的初始化操作，插入元素，删除元素，显示所有元素，排序和查找第i个元素。用户可根据显示菜单来进行相关操作。4.1.插入一个元素：例如在第i个元素之前插入一个元素，首先要将尾元素到第i个元素向后移动一位，再将新元素传送到第i个位置，即可。4.2.删除一个元素：例如删除第i个元素时，要将第i+1个元素到最后一个元素向前移到一位。尾数置零。五详细设计#include stdio.hmain() int a10,de=0,i=0,data=0,locate=0,t=0,j=0; printf(请依次输入10个输入数据：n); for(i=0;i10;i+) scanf(%d,&ai); printf(n); for(i=0;i=0&de10) break; else printf(超出范围请重新输入：); for(i=de;i=0&locate=locate;i-) ai+1=ai; alocate=data; if(j=3) printf(对数据进行升序排列); for(i=0;i10;i+) for(j=0;jaj+1) t=aj; aj=aj+1; aj+1=t; if(j=4) printf(请输入查找数据的位置：); for(;) scanf(%d,&locate); if(locate=0&locate10)break; else printf(超出范围请重新输入：); printf(%d, alocate); if(j=5) break; if(j=0) printf(按顺序显示输入的数据：); for(i=0;i5) printf(没有此操作命令); 六用户手册6.1依次输入十个数据6.2遍历输入0选项实现数字的遍历，按顺序显示输入的数据。6.3删除删除数据范围内的数字.删除后，后位数字依次向前移位，末位补0。删除数据范围外的数字，显示超出范围请重新输入。6.4插入插入数据位置在范围内插入数据位置超出范围，显示超出范围请重新输入。6.5排序对数据进行升序排列。6.6查找按位置查找.查找数据位置范围内，显示该位置数字。按位置查找.查找超出数据表范围，显示超出范围请重新输入。6.7退出输入指令代码5，退出程序。6.8输入代码超出指令范围，显示没有此操作命令。七测试与结果分析(1)对数据进行排序时，按升序排列。(2)删除指定位置元素时将该元素之后所有元素依次向前移动一位，尾元素置0。八学习心得做了这次课程设计，我觉得课程设计这种形式真的是我们需要的，可以让我们学到很多，包括书上的、书外的。理论永远不等于实际。在学排序算法的时候，读了书上的算法描述，觉得自己都会了，考试题目也都做出来了，但真的到编程去实现它的时候，却不是一次就成功的，总会出点差错，循环的边界条件啊，排序表的设计啊，等等，只得一次次改，等到程序终于正确运行的时候，才算真正会了这些算法，理论和实际永远差那么一点，不去做是体会不出来的。坐在电脑前才真正知道自己会不会，眼高手低是要不得的。在课程设计中我对数据结构有很大的认识和了解。近几十年来，计算机的应用领域日益扩大，早已不再局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。数据结构的学习就是为以后从事非数值处理的程序设计打下坚实的理论、方法和技术基础。数据结构是从事计算机软件开发、应用人员必备的专业知识。随着计算机的日益普及，掌握数据结构知识已成为计算机专业的基本要求。摸索着用C语言做完课程设计，增强了自己的自学能力，这应该是最有用的吧，语言会过时，学习的能力却不会过时。这次的课程设计也使我意识到了理论与实践相结合的重要作用。九参考文献1 严蔚敏,吴伟民.数据结构（C语言版）M.北京:清华大学出版社,2008. 2 熊岳山,刘越.数据结构与算法M.北京:电子工业出版社,2007. 3 苏仕华编著.数据结构与算法解析.合肥：中国科学技术大学出版社，20044 徐孝凯编著.数据结构实用教程. 北京：清华大学出版社，1999 十教师评审意见实验二一实验题目：学生学籍管理系统二实验目的: 随着学校规模的发展，学生会越来越多，学生从全国各地来上学每个人的信息需要大量的统计。例如一个学生从某地来上学，每个学生的学号姓名政治面貌住址等信息都不同。用笔和纸传统的手工管理档案，这中管理方式存在着不易更新、不易存放、不安全、容易丢失、难以备份等重大缺陷，管理起来效率低下而且很可能造成管理上的混乱。而自己建立简单的电子文档对个人信息进行管理虽然克服了以上的缺点，但查询效率较低，特别是当数据量十分庞大时，劣势尤其明显。因此开发一个既可以存储信息，又可以进行插入、删除、查询、管理等功能，同时价格又能为广大消费者接受的多功能电子学籍信息管理系统就显得十分必要。三设计分析 程序设计一般由两部分组成：算法和数据结构，合理地选择和实现一个数据结构和处理这些数据结构具有同样的重要性。在学生学籍管理过程中，由于预计记录对于一个单位的学生数或人事数来说太大，操作除了能够增加、删除、保存等外，更多的情况是查询，且能够实现快速查询。特别是当需要动态变化时利用链表，例如插入和删除数据等操作时，为方便插入和删除人事记录，通过数据的自动的移动数据，实现动态管理。学籍管理系统应实现以下功能：1、能录入学生的基本信息，包括学号、姓名、性别、专业、系别、职务、政治面貌和入学时间，保存到结构体数组中。2、能根据输入的学号、姓名查找学生，进行信息的修改。3、能根据输入的学号、姓名从结构体数组中删除学生的记录。4、实现查询功能，能根据输入的学号或姓名在屏幕上显示相应的学生信息。3.1 部分源程序代码 二叉树如下： 3.1.1求二叉树深度的算法int depth(btree *b) int dep1,dep2; /*左右子数的深度*/ if(b=NULL) return(0); else dep1=depth(b-left); dep2=depth(b-right); if(dep1dep2) return(dep1+1); else return(dep2+1); 3.1.2源程序#include #include #define MaxSize 100 typedef char ElemType; typedef struct node ElemType data; struct node *left,*right; BTree; void creatree(BTree *BT,char *str) BTree *stackMaxSize,*p; int top=-1,k,j=0; /*top为栈指针，k指定是左还是右孩子，j为str指针*/ char ch; *BT=NULL; ch=strj; while (ch!=0) switch(ch) case (:top+;stacktop=p;k=1; /*为左结点*/ break; case ):top-; break; case ,:k=2; /*为右结点*/ break; default: p=(BTree *)malloc(sizeof(BTree); p-data=ch;p-left=p-right=NULL; if (*BT=NULL) /*根结点*/ *BT=p; else switch(k) case 1:stacktop-left=p; break; case 2:stacktop-right=p; j+; ch=strj; int BTreeDepth(BTree *B) int leftdep,rightdep; if (B=NULL) return(0); else leftdep=BTreeDepth(B-left); rightdep=BTreeDepth(B-right); if (leftdeprightdep) return(leftdep+1); else return(rightdep+1); main() BTree *B; char *s=A(B(D,E(H,I),C(G); creatree(&B,s); printf(n二叉树的深度为%dn,BTreeDepth(B); getch();3.1.3运行结果四设计方案在这次课程设计中使用了TC2.0开发工具，最后调试、生成可执行文件等是在VC下进行的。在这个简单的人事管理程序中，使用了链表这个动态数据结构。链表是动态数据结构中最简单的一种。它是一种用前后链指针连接的若干个有限结点的集合，其连接是前一个结点的尾指针指向下一个结点的起始地址，从而连接成的一个链，所以它是一种线性的动态数据结构。在该程序中，采用了动态存储分配技术，这样可以有效地利用有限的内存空间。要实现它，就必须使用malloc（）和free（）函数。该程序主要使用了链表的插入、删除、查询。除了使用链表，还使用了文件的操作。 该学籍管理系统，可以实现各种学生学籍信息的输入，可分别进行基本信息的整体浏览和对某一学生信息的浏览，可实现对学生学籍信息的修改，亦可以进行插入、删除操作，可以按照姓名或学号进行查询，现该程序只能对学生数进行统计。4.1、系统功能结构图 根据项目的开发要求，本系统划分成六个主功能模块：录入学生信息模块、修改学生信息模块、删除学生信息模块、查询信息模块、输出模块和系统退出模块。系统功能结构图如下：4.2 采用类c语言定义相关的数据类型struct student /*定义结构体*/char num10; /*学号*/char name20; /*学生姓名*/char sex4; /*性别*/char part20; /*系别*/char title20; /*职务*/char ID20; /*身份证号*/char edu10; /*政治面貌*/char pro10; /*专业*/char time10; /*入学时间*/char school20; /*家庭住址*/;typedef struct node /*线性单链表的存储结构*/struct student data;struct node *next;Node,*Link;4.3 各模块的伪码算法4.2.1 链表的插入是根据某一关键字的顺序来进行插入操作的。要实现它，需要用三个指针，一个头指针、一个指向开辟新结点的指针，以及一个用来保存刚刚建立的结点的指针。该算法如下：Status ListInsert_L(LinkList &L,int i,ElemType e) /在带头结点的单链表L中第i个位置之前插入元素e p=L; j=i; while(p&jnext;+j; /*寻找第i-1个结点*/ if(!p|ji-1) return ERROR /*i小于1或者大于表长+1*/ s=(LinkList)malloc(sizeof(LNode); /*生成新结点*/ s-data=e;s-next=p-next; /*插入L中*/ p-next=s; return OK; /ListInsert_L4.3.2 链表的删除是指从某个已经存在的链表中根据给定的条件删去若干结点的操作。删除操作的实现，实际上就是把某个结点从原链表中分离出来。也就是使被删除结点与原链表失去联系，从而改变原链表的连接关系。其算法如下：Status ListDelete_L(LinkList &L,int i,ElemType e)/*在带头结点的单链表L中删除第i个元素，并由e返回其值*/p=L; j=i;while(p-next&jnext;+j; /*寻找第i-个结点,并令p指向其前驱*/if(!(p-next)|ji-1) return ERROR; /*删除位置不合理*/q=p-next; p-next=q-next; /*删除并释放结点*/e=q-data; free(q); return OK; /ListDelete_L4.3.3链表的查找操作是指从某个已经存在的链表中根据给定的条件寻找符合条件的结点。其算法如下：Node* Locate(Link l,char findmess,char nameornum) /*查找子函数*/Node *r;if(strcmp(nameornum,num)=0) /*与比较员工号相同*/ r=l-next; while(r!=NULL) /*不是尾结点*/ if(strcmp(r-data.num,findmess)=0) /*比较相同*/ return r; /*返回结点信息*/ r=r-next; /*查找下一个*/ else if(strcmp(nameornum,name)=0) /*与比较学生姓名相同*/ r=l-next; while(r!=NULL) if(strcmp(,findmess)=0) return r; r=r-next;return 0;五详细设计 #include stdio.h#include stdlib.h#include string.hint shoudsave=0;struct student /*定义结构体*/ char num10; /*学号*/ char name20; /*学生姓名*/ char sex4; /*性别*/ char part20; /*所在系别*/ char title20; /*职务*/ char ID20; /*身份证号*/ char edu10; /*政治面貌*/ char pro10; /*专业*/ char time10; /*入学时间*/ char school20; /*家庭住址*/;typedef struct node /*定义链表*/ struct student data; struct node *next;Node,*Link;void menu() /*菜单子函数*/ printf(*); printf(t1输入学生资料 ttttt2删除学生资料n); printf(t3查询学生资料 ttttt4修改学生资料n); printf(t5显示学生基本资料tttt6保存学生资料n); printf(t7显示学生学历资料tttt8统计学生资料n); printf(t0退出系统n);printf(*n);void printstart() /*分隔线子函数*/printf(-n); void Wrong() /*错误信息子函数*/printf(n=提示:输入错误!n);void Nofind() /*查找失败信息子函数*/printf(n=提示:没有找到该学生!n);void printc() /*基本信息标题子函数*/printf(学号t 姓名t 性别t 所在系别t 职务t 身份证号码 tn);void printe(Node *p) /*基本信息输出子函数*/printf(%st %st %st %st %st %stn,p-data.num,,p-data.sex,p-data.part,p-data.title,p-data.ID);void printb() /*信息子函数*/printf(学生基本信息:n);void printx() /*信息标题子函数*/printf(学号t 姓名t 政治面貌t 专业t 入学时间t家庭住址tn);void printd(Node *p) /*信息输出子函数*/printf(%st %st %st %st %st %stn,p-data.num,,,,p-data.time,p-data.school);Node* Locate(Link l,char findmess,char nameornum) /*查找子函数*/Node *r;if(strcmp(nameornum,num)=0) /*与比较学号相同*/ r=l-next; while(r!=NULL) /*不是尾结点*/ if(strcmp(r-data.num,findmess)=0) /*比较相同*/ return r; /*返回结点信息*/ r=r-next; /*查找下一个*/ else if(strcmp(nameornum,name)=0) /*与比较学生姓名相同*/ r=l-next; while(r!=NULL) if(strcmp(,findmess)=0) return r; r=r-next; return 0;void Add(Link l) /*学生信息输入子函数*/ Node *p,*r,*s; char num10; r=l; s=l-next; while(r-next!=NULL) r=r-next; while(1) printf(请你输入学号(以0返回上一级菜单:); scanf(%s,num); if(strcmp(num,0)=0) /*检验输入值是否为*/ break; while(s) if(strcmp(s-data.num,num)=0) /*检验输入值是否已存在*/ printf(=提示:学号为%s的学生已经存在,若要修改请你选择4修改!n,num); printstart(); /*调用分隔线子函数*/ printc(); /*调用基本信息标题子函数*/ printe(s); /*调用基本信息输出子函数*/ printstart(); /*调用分隔线子函数*/ printf(n); return; s=s-next; /*循环*/ p=(Node *)malloc(sizeof(Node); strcpy(p-data.num,num); printf(请您输入姓名:); scanf(%s,&); getchar(); printf(请您输入性别:); scanf(%s,&p-data.sex); getchar(); printf(请您输入所在系别:); scanf(%s,&p-data.part); getchar(); printf(请您输入班级职务:); scanf(%s,&p-data.title); getchar(); printf(请您输入身份证号码:); scanf(%s,&p-data.ID); getchar(); printf(请您输入政治面貌:); scanf(%s,&); getchar(); printf(请您输入专业:); scanf(%s,&); getchar(); printf(请您输入入学时间:); scanf(%s,&p-data.time); getchar(); printf(请您输入家庭住址:); scanf(%s,&p-data.school); getchar(); p-next=NULL; r-next=p; r=p; shoudsave=1; /*信息未保存标志*/ void Qur(Link l) /*查询子函数*/ int sel; char findmess20; Node *p; if(!l-next) printf(n=提示:没有资料可以查询!n); return; printf(n=1按员学号查找n=2按姓名查找n); scanf(%d,&sel); if(sel=1) printf(请您输入要查找的学号:); scanf(%s,findmess); p=Locate(l,findmess,num); if(p) printf(tttt查找结果n); printstart(); /*调用分隔线子函数*/ printc(); /*调用基本信息标题子函数*/ printe(p); /*调用基本信息输出子函数*/ printb(); /*调用学历信息子函数*/ printx(); /*调用学历信息标题子函数*/ printd(p); /*调用学历信息输出子函数*/ printstart(); /*调用分隔线子函数*/ else Nofind(); /*调用查找失败信息子函数*/ else if(sel=2) printf(请您输入要查找的姓名:); scanf(%s,findmess); p=Locate(l,findmess,name); /*调用查找子函数*/ if(p) printf(tttt查找结果n); printstart(); printc(); printe(p); printb() ; printx(); printd(p); printstart(); else Nofind(); else Wrong();void Del(Link l) /*删除子函数*/ int sel; Node *p,*r; char findmess20; if(!l-next) printf(n=提示:没有资料可以删除!n); return; printf(n=1按学号删除n=2按姓名删除n); scanf(%d,&sel); if(sel=1) printf(请您输入要删除的学号:); scanf(%s,findmess); p=Locate(l,findmess,num); /*调用查找子函数*/ if(p) r=l; while(r-next!=p) r=r-next; r-next=p-next; free(p); printf(n=提示:该学生信息已经成功删除!n); shoudsave=1; else Nofind(); else if(sel=2) printf(请您输入要删除的姓名:); scanf(%s,findmess); p=Locate(l,findmess,name); /*调用查找子函数*/ if(p) r=l; while(r-next!=p) r=r-next; r-next=p-next; free(p); printf(n=提示:该学生信息已经成功删除!n); shoudsave=1; else Nofind(); else Wrong();void Modify(Link l) /*修改信息子函数*/ Node *p; char findmess20; if(!l-next) printf(n=提示:没有资料可以修改!n); return; printf(请您输入要修改的学号:); scanf(%s,findmess); p=Locate(l,findmess,num); /*调用查找子函数*/ if(p) printf(请您输入新学号(原来是%s):,&p-data.num); scanf(%s,&p-data.num); getchar(); printf(请您输入新姓名(原来是%s):,&); scanf(%s,&); getchar(); printf(请您输入新性别(原来是%s):,&p-data.sex); scanf(%s,&p-data.sex); getchar(); printf(请您输入新的所在系别(原来是%s):,&p-data.part); scanf(%s,&p-data.part); getchar(); printf(请您输入新的班级职务(原来是%s):,p-data.title); scanf(%s,&p-data.title); getchar(); printf(请您输入新的身份证号码(原来是%d):,&p-data.ID); scanf(%s,&p-data.ID); getchar(); printf(请您输入新的政治面貌(原来是%s):,&); scanf(%s,&); getchar(); printf(请您输入新的专业(原来是%s):,&); scanf(%s,&); getchar(); printf(请您输入新的入学时间(原来是%d):,&p-data.time); scanf(%s,&p-data.time); getchar(); printf(请您输入新的家庭住址(原来是%s):,&p-data.school); scanf(%s,&p-data.school); getchar(); printf(n=提示:资料修改成功!n); shoudsave=1; else Nofind(); void Disp(Link l) /*基本信息浏览子函数*/ int count=0; Node *p; p=l-next; if(!p) printf(n=提示:没有资料可以显示!n); return; printf(tttt显示结果n); printstart(); printc(); printf(n); while(p) printe(p); p=p-next; printstart(); printf(n);void xueli(Link l) /*政治信息浏览子函数*/ Node *p; p=l-next; if(!p) printf(n=提示:没有资料可以显示!n); return; printf(t