数据结构-学生管理系统.doc

太 原 工 业 学 院 数据结构实 验 报告院（系） 计算机工程系 实验课程 数据结构 实验教师 数据结构课程组 2015年4月4日目录实验一、线性表1一、实验类型1二、实验目的与任务1三、预习要求1四、实验基本原理1五、实验内容2六、实验步骤2实验二、 栈和队列5一、实验类型5二、实验目的与任务5三、预习要求5四、实验基本原理5五、实验内容6六、实验步骤6实验三、树的应用9一、实验类型9二、实验目的与任务9三、预习要求9四、实验基本原理9五、实验内容10六、实验步骤10实验四、图12一、实验类型12二、实验目的与任务12三、预习要求12四、实验基本原理12五、实验内容13六、实验步骤13实验五、查找排序17一、实验类型17二、实验目的与任务17三、预习要求17四、实验基本原理17五、实验内容17六、实验步骤18数据结构实验报告实验题目： 设计学生信息管理系统 姓名 学号： 班级： 系名： 计算机工程 专业 计算机科学有技术 指导老师： 刘海静 实验时间： 2016年4月4日 实验地点： 【实验概述】一 .实验目的及要求目的：1熟练掌握线性表的基本运算。2掌握顺序表和单链表结构上的插入和删除算法。3了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操 作。要求：预习并掌握线性表的逻辑结构特点、顺序存储结构、链式存储结构、顺序表的结构体类型定义、单链表的结构体类型定义、在两种存储结构上的各种基本操作的实现算法。二实验原理1、线性表的逻辑结构特点：线性表是n个数据元素的有限序列，记为： L=（a1,a2, ,an）。数据元素之间的关系是：ai-1领先于ai，ai领先于ai+1。称ai-1是ai的直接前驱元素；ai+1是ai的直接后继元素。除a1外，每个元素有且仅有一个直接前驱元素，除an外，每个元素有且仅有一个直接后继元素。注意：数据元素的类型可以是基本数据类型，也可以是结构体等自定义类型。2、线性表的基本操作有4类：结构初始化、结构销毁、引用型操作、加工型操作。3、线性表的顺序存储结构：用一组地址连续的存储单元依次存放线性表中的数据元素。顺序存储结构线性表的静态分配和动态分配空间区别。4类基本操作在顺序存储结构下的算法实现。4、线性表的链式存储结构：用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 。5、线性表的链式存储结构有4种：单链表；单循环链表；双链表、双循环链表。重点学习单链表，其他几种是单链表的变形。6、带头结点的单链表结构体描述。4类基本操作在单链表上的算法实现。三 .实验环境（使用的软件）VC+6.0【实验内容】1. 实验算法设计设计一个学生信息管理系统，实现对学生信息的以下操作：1、以线性表的顺序存储结构创建学生信息顺序表。2、以线性表的链式存储结构（单链表）创建学生信息单链表。3、在这两种存储结构上实现学生数据的插入、删除和按学号查找的算法。2.实验过程（源代码及描述、调试过程及分析）第一，启动VC+6.0，创建一个名为“test1”的空白工程。注意存放路径。第二，在“test1”工程下，创建一个名为“xsglxt1”的C+源程序文件。第三，在“xsglxt1.cpp”中进行源程序编辑。参考代码：1、 预处理命令行； #include#include#includeusing namespace std;#define TRUE 1#define OK 1#define ERROR -1#define FALSE -1 #define OVERFLOW -22、 顺序表结构体类型定义；typedef int Status;typedef structchar NO10;char name10;ElemType;const int LIST_INIT_SIZE=100;typedef structElemType *elem;int length;int listsize;Sqlist;3、 顺序表结构初始化；Status initlist_sq(Sqlist &L)L.elem=new ElemTypeLIST_INIT_SIZE;if(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;4、 在顺序表中输入学生信息；void listcreate_sq(Sqlist &L,int n)printf(请依次输入线性表中的%d个数据元素,n);for(int i=1;iL.elemi-1.NO;cinL.;L.length=n;5、 在顺序表中按照学号进行查找；int locate_sq(Sqlist L, char * e)int i=1;while(i=L.length & strcmp(L.elemi-1.NO,e)!=0) i+;if (i=L.length ) return i;else return 0;6、 在顺序表中插入一个新的学生信息；Status insertlist_sq(Sqlist &L, int i,ElemType e)if(iL.length +1) return ERROR;if(L.length =L.listsize ) exit(OVERFLOW);ElemType *p,*q;p=&(L.elem i-1);q=&(L.elem L.length -1);while(q=p)*(q+1)=*q;q-;*p=e;L.length +;return OK;7、 在顺序表中删除一个已有学生的信息；Status deletelist_sq(Sqlist &L, int i,ElemType &e)if(iL.length) return ERROR;if(L.length =0 ) return ERROR;ElemType *p,*q;p=&(L.elem i-1);q=&(L.elem L.length -1);e=*p;while(pq)*p=*(p+1);p+;L.length- ;return OK;8、 输出顺序表的学生信息；void printlist_sq(Sqlist L)for(int i=1;i=L.length ;i+)coutL.elem i-1.NO ; coutL.elem n;9、主程序。在主程序中调用以上几个模块。void main()Sqlist L; char e110;int loc,pos,i;ElemType stu,e2;initlist_sq(L);listcreate_sq(L,2);printlist_sq(L);cout请输入要查找的学生的学号：;scanf(%s,e1);loc=locate_sq(L,e1);coutlocn;coutpos;scanf(%s%s,stu.NO,);insertlist_sq(L,pos,stu);printlist_sq(L);couti;deletelist_sq(L,i,e2);printlist_sq(L);coute2.NO;Xsglxt2#include StdAfx.h#include#include#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0using namespace std;typedef int Status;typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;Status listEmpty_L(LinkList L)if(L-next =NULL)return TRUE;elsereturn FALSE;int ListLength_L(LinkList L)int i=0;LNode *p=L;while(p-next)p=p-next;i+;return i;void GetElem_L_1(LinkList L,int i,ElemType &e)if(listEmpty_L(L) cout空表”;exit( ERROR);if(iListLength_L(L) couti的值不在正确范围;exit( ERROR);int j=0;LinkList p=L ;while(jnext ;j+;e=p-data;Status GetElem_L_2(LinkList L,int i,ElemType &e)int j=1;LinkList p=L-next ;while(p&jnext ;j+;if(!p|ji)return ERROR;e=p-data ;return OK;Status ListInsert_L(LinkList &L,int i,ElemType e) int j=0; LinkList p=L; while(p&jnext ; j+; if(!p|ji-1) coutdata=e; s-next=p-next ; p-next =s; return OK;Status ListDelete_L(LinkList &L,int i,ElemType &e)int j=0;LinkList q,p=L;while(p-next&jnext ;j+;if(!(p-next )|ji-1) coutnext ;e=q-data ;p-next =q-next ;delete q;return OK;Status ListClear_L(LinkList &L)LinkList p;while(L-next )p=L-next ;L-next =p-next ;delete p;return OK;Status ListCreate_L_head(LinkList &L,int n)L=new LNode;L-next =NULL;for(int i=1;i=n;i+)LinkList p=new LNode;cout逆位序输入线性表的第n-i+1p-data ;p-next =L-next ;L-next =p;return OK;Status ListCreate_L_tail(LinkList &L,int n)ElemType e;L=new LNode;L-next =NULL;LinkList p,s=L;for(int i=1;i=n;i+)p=new LNode;cout正位序输入线性表的第ip-data ;p-next =s-next ;s-next =p;s=p;return OK;void ListPrint_L(LinkList L)LinkList p=L-next ;cout线性表括中的学生名字为：;while(p)coutdata next ;coutendl;void main()LinkList L;ElemType e,e1,e2;int n,i,j,k;coutn;/ListCreate_L_head(L,n); /正y位?序创洹?建带?头?结点?的?单蹋?链?表括?ListCreate_L_tail(L,n);ListPrint_L(L);cout线性表中的学生个数为：ListLength_L(L)endl;cou