《高等数据结构与算法分析》结课项目设计说明书

高等数据结构与算法分析结课项目说明书专 业： 计算机技术 姓 名： 彭 洋 学 号： 课 程 教 师： 周 娅 所 属 学 院： 计算机与信息安全学院 成绩评定教师签名桂林电子科技大学研究生院2018年02月20日一、 系统概述该项目是设计一个模拟学生学籍信息管理程序，要求使用链表来实现。它具有浏览、插入、删除、修改等功能，并且能够对数据进行文件存储和读出操作。主要功能模块如下：1. 浏览学生信息：显示学生的信息。2. 插入学生信息：添加学生的信息。3. 删除学生信息：通过输入学号删除学生的信息。4. 修改学生信息：通过输入学号修改学生的信息。5. 保存学生信息：将学生信息保存到文件。0. 退出系统：结束程序的运行，结束前询问是否保存信息。二、 需求分析在本系统中所实现的功能有浏览学生信息、插入学生信息、删除学生信息、修改学生信息和保存学生信息。进入系统后首先有一个访问界面，可列出功能列表及操作指引，用户可通过提示进行选择。首先，在浏览学生信息模块，可通过界面指令浏览系统中保存的所有学生信息。在插入学生信息模块，用户通过一系列连续的交互指令输入学生信息，然后通过链表进行存储。我们可以采用多种链表存储结构对学生信息进行存储，比如：单链表，双链表，循环链表等；其中每一个节点代表了一个学生信息，根据采用的存储结构的不同，对信息的增删改查等操作的具体实现也会有所不同。在插入、删除和修改学生信息的操作中，首先都需要对链表进行遍历操作，获取我们所期望的节点位置，然后进行相应操作。比如在插入时我们可以分别使用头插法，尾插法，或者是按照一定规则进行有序地插入。修改和删除操作则相对简单，只需要先遍历得到目标节点位置，然后按照规则进行修改和删除即可。而保存则是借助文件操作进行的，即将学生信息以流的形式读入指定文件中进行保存，需要浏览的时候再读出来进行显示。三、 概要设计本系统为学生学籍信息管理系统，系统执行流程如下图3-1所示。图3-1 学生学籍信息管理系统执行流程首先，进入系统后可以看到一个功能界面，上面有指令操作码（0-5），通过选择不同的指令操作码可以执行不同的操作，包括浏览学生信息、插入学生信息、删除学生信息、修改学生信息、保存学生信息以及退出系统。四、 详细设计通过分析可以知道在学生学籍信息管理系统中最常用的操作是数据的插入，一般录入之后对信息的修改和删除操作是相对较少的，所以为了能够提高插入的效率本系统采用了单链表结构进行数据存储。4.1 单链表单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：（1）用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）（2）链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）。4.2 单链表的节点结构单链表的结点结构如下图4-1所示。图4-1 单链表的结点结构其中，data域指存放结点值的数据域，next域指存放结点的直接后继的地址的指针域（链域）。链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，就此构成了一个单链表的存储结构。单链表中每个结点的存储地址是存放在其前趋结点next域中，因为开始结点无前趋，故应设头指针head指向开始结点。我们将每个结点只有一个链域的链表称为单链表（Single Linked List）。4.3 算法设计通过需求分析和概要分析我们可以知道单链表很适合作为这类需求的存储结构，我们通过单链表进行数据存储，并且在需要时通过头插法直接将要插入的数据插入到单链表头部，这样其插入复杂度仅为O(1)。由于此类系统中插入操作是最普遍的操作，一旦输入之后很少涉及到修改操作，因此通过头插法进行单链表的存储方案能极大地提高系统的工作效率。而删除和修改操作都得遍历整个列表以得到目标节点，再进行相应的操作。4.4 数据存储结构系统所采用的存储结构体定义如下：struct node char number12; char name10; char sex4; char classes10; char tel12; struct node *next;typedef struct node NODE;该结构体描述了一个结构体变量的5个结构体成员，分别是包含了12位的学号、10位的姓名、4位的性别、10位的班级以及12位的联系方式，然后将其声明为NODE，即以后可用NODE表示该结构体。如：头结点声明：NODE *head。结构体就像一个“模板”，由它定义出来的变量都具有相同的性质，定义成功之后，每一个结构变量将会具有以上结构体的5个属性，可通过指针进行访问。比如：我们可以通过head - number的方式访问结构体变量的属性number的值，该值可作为后面查找操作的依据。五、 编程实现本系统是通过C语言在CodeBlocks环境下进行开发的，开发环境及算法清单如下表5-1所示。开发环境及算法清单开发环境CodeBlocks开发语言C语言函数名称函数功能Browse（）浏览学生信息Insert（）插入学生信息Delete（）删除学生信息Modify（）修改学生信息ReadInfo（）将学生信息从文件读出WriteInfo（）将学生信息写入文件FreeList（）释放链表Exit（）退出函数表5-1 开发环境及算法清单其中，Browse()函数为浏览学生信息的函数，该函数首先会检查本地是否存在信息存储文件（E:Database.txt），若文件不存在则显示学生数据文件不存在，或文件打不开!，反之调用ReadInfo()函数将其中的学生信息打印出来。void Browse(NODE *head) /浏览学生信息记录NODE *p=head;if(p-next=NULL)printf(无文件记录！请输入学生信息！n);return;p=head-next;printf(学号 姓名 班级 性别联系方式n);printf(-n);while(p!=NULL)printf(%s %s %s %s %sn,p-number,p-name,p-classes,p-sex,p-tel);p=p-next;void ReadInfo(NODE *head) /将学生信息从文件读出FILE *fp;NODE *p=head,*t;if (fp=fopen(E:Database.txt,rb)=NULL)printf(学生数据文件不存在，或文件打不开!n);return;p-next=!NULL;while(p-next!=NULL)t=(NODE *)malloc(sizeof(NODE);fread(t,sizeof(NODE),1,fp);p-next=t;p=p-next;fclose(fp);Insert()函数的作用是向链表中插入一条学生信息记录，此处采用的是头插法，即将每一条记录插入到链表头指针后面，第一条记录的前面。头插法是在插入时先将待插入节点的next指针指向头指针的下一条记录，再修改头指针的next域指向待插入节点（t-next=p-next; p-next=t;其中，t为待插入节点，p为头指针）。void Insert(NODE *head) / 定义插入函数NODE *t,*p;t=(NODE *)malloc(sizeof(NODE);p=head;printf(请输入学生学号：n);scanf(%s,t-number);printf(请输入学生姓名：n);scanf(%s,t-name);printf(请输入学生性别：n);scanf(%s,t-sex);printf(请输入学生班级：n);scanf(%s,t-classes);printf(请输入学生电话：n);scanf(%s,t-tel);if(p-next=NULL) / 原本无学生记录p-next=t;t-next=NULL;else / 原本有学生记录t-next=p-next;p-next=t;Delete()的作用是删除指定学号的学生信息，Modify()的作用是修改指定学生的信息,这两个函数都要先通过学号对链表进行遍历，找到目标节点，然后执行删除或者修改操作。void Delete(NODE *head) / 定义删除函数NODE *p=head,*t=p-next;char num12;printf(请输入要删除学生的学号:n);scanf(%s,num);while(t!=NULL)if(strcmp(t-number,num)!=0)t=t-next;p=p-next;elsep-next=t-next;free(t);printf(学生信息删除成功n);return;printf(该学生学号不存在，请输入正确的学生学号n);在修改学生信息时，会要求从界面输入用户想要修改的信息编号，然后根据所输入的编号修改指定数据内容。void Modify(NODE *head) / 修改学生信息NODE *p=head;p=p-next;char num12;printf(请输入要修改信息的学生学号:n);scanf(%s,num);int choice;while(p!=NULL)if(strcmp(p-number,num)!=0)p=p-next;elseprintf(1.学号2.姓名3.性别4.班级5.电话n请选择：);scanf(%d,&choice);switch(choice)case 1:printf(请输入要修改学生的学号:n);scanf(%s,p-number);break;case 2:printf(请输入要修改学生的姓名:n);scanf(%s,p-name);break;case 3:printf(请输入要修改学生的性别:n);scanf(%s,p-sex);break;case 4:printf(请输入要修改学生的班级:n);scanf(%s,p-classes);break;case 5:printf(请输入要修改学生的电话:n);scanf(%s,p-tel);break;break;WriteInfo()的作用则是将已经插入到链表当中的学生信息保存到本地文件中，以方便Browse()函数读取其中的信息并显示出来。void WriteInfo(NODE *head) /将学生信息写入文件FILE *fp;NODE *p=head;if (fp=fopen(E:Database.txt,wb)=NULL)printf(不能打开学生文件!n);return;p=p-next;while(p!=NULL)if (fwrite(p,sizeof(NODE),1,fp)!=1)printf(写入学生文件错误!n);p=p-next;fclose(fp);FreeList()函数的作用是释放链表资源，Exit()函数则是退出系统的出口函数，在退出前还可以自主选择是否将链表中的信息保存到文件中。void FreeList(NODE *head) / 释放链表NODE *p=head, *t=head;while(p!=NULL)p=p-next;free(t);t=p;void Exit(NODE *head) /退出程序char ans;int flag=1;if (head-next!=NULL)printf(保存当前数据吗？请输入y/n:);while(flag)scanf(%c, &ans);getchar();if (ans=y|ans=Y)WriteInfo(head);flag=0;else if (ans=n|ans=N)flag=0;elseprintf(输入错误，请重新输入y/n:);FreeList(head);printf(再见，谢谢使用!n);主函数负责交互界面的打印和操作逻辑的控制，用户通过界面所提示的不同数字指令可以进行不同的操作。int main() int choice; / 功能选择的参数 NODE *head; head=(NODE *)malloc(sizeof(NODE); / 创建头结点 head-next=NULL; ReadInfo(head); / 从文件读取信息 while(1) /打印主菜单 printf(n%s, *学生信息管理系统*n * 1. 浏览学生信息 *n * 2. 插入学生信息 *n * 3. 删除学生信息 *n * 4. 修改学生信息 *n * 5. 保存学生信息 *n * 0. 退出系统 *n *n 请按功能代码选择(0 5):); scanf(%d,&choice); getchar(); switch(choice) case 1: Browse(head); break; case 2: Insert(head); break; case 3: Delete(head); break; case 4: Modify(head); break; case 5: WriteInfo(head); break; case 0: Exit(head); exit(0); default: printf(n 选择错误，请重新输入!n); return 0;六、 测试方法与运行结果、在测试中，所使用的测试方法是先通过单元测试（Unit Testing）检查各单元功能是否正常，再进行集成测试（Integration Testing）和系统测试（System Testing）以验证个单元集成之后工作逻辑是否正常。单元测试是最微小规模的测试;以测试某个功能或代码块。集成测试是单元测试的逻辑扩展。它的最简单的形式是：两个已经测试过的单元组合成一个组件，并且测试它们之间的接口。从这一层意义上讲，组件是指多个单元的集成聚合。在现实方案中，许多单元组合成组件，而这些组件又聚合成程序的更大部分。方法是测试片段的组合，并最终扩展进程，将您的模块与其他组的模块一起测试。最后，将构成进程的所有模块一起测试。系统测试是基于系统整体需求说明书的黑盒类测试，应覆盖系统所有联合的部件。系统测试是针对整个产品系统进行的测试，目的是验证系统是否满足了需求规格的定义，找出与需求规格不相符合或与之矛盾的地方。首先，进入界面之后，我们可以看到系统中有6条指令代码可供我们选择并执行。分别是：浏览学生信息、插入学生信息、删除学生信息、修改学生信息、保存学生信息和退出系统。图6-1是我们第一次进入系统并选择浏览学生信息后的结构页面，由于第一次进入系统时系统中应该是没有任何数据的，所以执行该指令之后应该打印无文件记录！请输入学生信息！。图6-1 第一次进入系统后执行浏览学生信息指令后的结果页面然后，我们执行插入学生信息指令（图6-2），并插入一条学生信息记录（ 小明 女 05 ），再执行指令1以查看我们是否插入成功，结果如图6-3所示，我们可以看到我们已经成功地插入了一条数据记录。图6-2执行插入学生信息指令后的操作页面图6-3插入记录后再执行浏览学生信息指令后的结果页面接下来，我们进行修改操作的测试。在指令界面选择指令4并执行，则会出现图6-4所示的界面。我们先输入想要修改的学生学号，然后算法Modify()函数会根据输入的学号查找目标节点，找到之后再执行操作。此时，我们可以通过输入序号选择我们想要修改的具体属性值，修改成功之后再执行指令1查看我们是否修改成功。根据图6-4所示可以看出，我们的修改操作是成功的。图6-4修改学生信息操作及结果页面在退出前，我们应该先进行保存操作。当然，如果操作者遗忘了这一步也是没有关系的，因为在退出指令执行后还会询问是否保存已有数据。我们再次选择保存后退出，操作界面如图6-5所示。图6-5保存学生信息并退出的操作界面按照我们之前的逻辑，由于我们创建了本地文件（E:Database.txt）进行信息存储，那么在保存之后文件中也一定会出现相关记录。保存后我们打开我们的本地文件以查看保存操作是否成功，结果如图6-6所示。图6-6保存操作后本地存储文件内容结果图最后，我们删除掉我们从系统界面所插入的内容，并检查本地文件是否也成功删除了。结果如图6-6和6-7所示。 图6-7删除操作及结果示图 图6-6删除操作后本地存储文件内容结果图根据以上测试结果我们可以得出此系统能完成需求中的所有功能并正常运行的结论。它能向我们的存储结构（单链表）中插入数据记录，并进行修改、查看和删除的操作。并且能够将链表中的所有数据备份到本地文件中，这大大增强了系统的容错和恢复能力。七、 总结（系统开发是否成功、能否正常运行、系统特色、创新点、体会、成效分析、收获）经过几天的研究和开发，最终实现了任务书中的所有要求，完整地开发出了整个系统。该系统是一个通过单链表进行数据存储的学生信息管理系统，用户能够对信息进行增删改查等基本操作，并能将已有信息备份到本地文档中进行存储。经过单元测试、集成测试和系统测试等一系列测试之后，也证明了系统运行的正确性和有效性，并且能够正常地工作。对于本系统而言，存储操作是最重要的操作，其效率将会影响整个系统的工作效率。而由于学生信息