目 录
1单链表的基本操作 ............................................ 1
1.1 设计的目的 .................................................................... 1 1.2 设计的内容与要求 .............................................................. 1 1.3 课题分析 ...................................................................... 1 1.4 算法思想 ...................................................................... 1 1.5 概要设计 ...................................................................... 1 1.6 详细设计 ...................................................................... 2 1.7 源码 .......................................................................... 2 1.8 运行、测试及使用说明（包括运行界面及运行过程） ................................. 4 1.9算法分析 ....................................................................... 4 1.10 总结与体会 ................................................................... 5
2 顺序表的基本操作 ........................................... 6
2.1设计的目的 ..................................................................... 6 2.2 设计内容与要求 ................................................................ 6 2．3 课题分析 ..................................................................... 6 2．4 算法思想 ..................................................................... 6 2．5 概要设计 ..................................................................... 6 2．7 源码 ......................................................................... 8 2．8 运行、测试及使用说明。 ...................................................... 10 2.9 总结与体会 ................................................................... 10
3.线性表在图书管理中的应用 .................................. 11
3.1设计的目的 .................................................................... 11 3.2设计内容与要求 ................................................................ 11 3.3 课题分析 ..................................................................... 11 3.4算法思路 ...................................................................... 11 3.5概要设计 ...................................................................... 12 3.6详细设计 ...................................................................... 12 3.7源码 .......................................................................... 13 3.8运行结果及调试 ................................................................ 14 3.9总结体会 ...................................................................... 14
4线性表在图书管理中的应用 ................................... 16
4.1设计的目的 .................................................................... 16 4.2计内容和要求 .................................................................. 16 4.3课题分析 ...................................................................... 16 4.4算法思路 ...................................................................... 16 4.5概要思想 ...................................................................... 16
4.6概要设计 ...................................................................... 17 4.7源码 .......................................................................... 17 4.8运行、测试及使用说明 .......................................................... 20 4.9总结和体会 .................................................................... 21
5线性表在学生成绩管理中的应用 ............................... 22
5.1设计的目的 .................................................................... 22 5.2设计的内容与要求 .............................................................. 22 5.3课题分析 ...................................................................... 22 5.4算法思路 ...................................................................... 22 5.5概要设计 ...................................................................... 22 5.6详细设计 ...................................................................... 23 5.7源代码 ........................................................................ 23 5.8总结体会 ...................................................................... 29
6线性表在工资管理中的应用 ................................... 30
6.1设计的目的 .................................................................... 30 6.2设计的内容与要求 .............................................................. 30 6.3 课题分析 ..................................................................... 30 6.4 算法原理 ..................................................................... 30 6.5 概要设计 ..................................................................... 30 6.6 详细设计 ..................................................................... 31 6.7 程序代码 ..................................................................... 32 6.8 运行结果 ..................................................................... 35 6.9 实验总结 ..................................................................... 35
7 线性表在汽车管理中的应用 .................................. 36
7.1 设计的目的 ................................................................... 36 7.2 设计内容与要求 ............................................................... 36 7.3 课题分析 ..................................................................... 36 7.4 算法思路 ..................................................................... 36 7.5 源码 ......................................................................... 36 7.6 运行结果 ..................................................................... 40 7.7 总结体会 ..................................................................... 40
8 线性表实现一元稀疏多项式的简单计算器 ....................... 41
8.1 设计的目的 ................................................................... 41 8.2 设计内容与要求 ............................................................... 41 8.3 课题分析 ..................................................................... 41 8.4 算法思想 ..................................................................... 41 8.5 概要设计 ..................................................................... 42
8.6 详细设计 ..................................................................... 42 8.7 源码 ......................................................................... 43 8.8 运行 ......................................................................... 47 8.9 总结与体会设计 ............................................................... 47
9 利用线性表解决约瑟夫环问题 .............................. 48
9.1 设计的目的 ................................................................... 48 9.2 设计内容与要求 ............................................................... 48 9.3 概要设计 .................................................................... 48 9.4 详细设计 .................................................................... 48 9.5 源码 ........................................................................ 48 9.6 测试结果 .................................................................... 50 9.7 总结与体会 .................................................................. 50
10 线性表解决约瑟夫环问题-链式存储结构实现 ................ 51
10.1 问题描述 ................................................................... 51 10.2 目的 ....................................................................... 51 10.3 要求 ....................................................................... 51 10.4 算法思想 ................................................................... 51 10.5 概要设计 ................................................................... 51 10.6 数据结构 ................................................................... 52 10.7 源程序 ..................................................................... 52 10.8 测试情况 ................................................................... 57
线性表的分析与应用
1单链表的基本操作
1.1 设计的目的
1、理解并掌握单链表结构结构的特点。
2、学会单链表的接本操作：建立、输出、连接。
1.2 设计的内容与要求
1、内容：
利用头插建立一个带头结点的单链表，并用算法实现单链表的建立、连接、输出。 2、要求：
用VC++6.0软件平台，操作系统：windows XP 硬件：内存要求：内存大小在256MB，其他配置一般就行。
1.3 课题分析
单链表是用一组地址任意的存储单元存放线性表中的数据元素，在单链表的程序设计中运用了指针、结点等等一些编写C语言的技巧。
在本次的课程设计的题目是单链表的建立、连接、输出，可以说是比较基础的，当然也有一定的难度在里面。首先要考虑到单链表的存储和输出，如何正确的在计算机中存储所需要计算的单链表和输出所计算的结果。其次考虑是算法问题，应该如何计算算法让计算机能够正确的完成计算连接的过程。
连接既是两个单链表中的元素连接到一个单链表中，进行输出。
1.4 算法思想
1,、定义一个创建单链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做好准备。
2、定义输出链表的算法，通过第一步已经定义好的创建链表函数的调用，在这一步通过调用输出链表的函数算法来实现对链表的输出操作。
3、定义连接链表的算法，通过第一步已经定义好的创建链表函数的调用，在这一步通过调用连接链表的函数算法来实现对链表的连接操作。
1.5 概要设计
（1）数据结构的定义：
Typedef struct {
int data; //数据域 Struct LNode *next； //指针域
}Lnode， *linklist; //定义变量
1
（2）程序结构： Mergelidt() 1、系统流程图： 程序如下： #include struct LNode *next; }LNode, *linklist; void create (linklist La,int n) { Main( ) shuchu() create() 1.6 详细设计 开始 调用建立函数create() 调用建立函数shuchu（） 调用建立函数Mergelidt（） 结束 1.7 源码 2 La->next=NULL;int i;linklist p; printf(\"请输入要插入节点的元素:\"); for(i=n;i>0;--i) {p=(linklist)malloc(sizeof(LNode)); scanf(\"%d\p->next=La->next; La->next=p;} for(i=0;i void MergeLidt(linklist La,linklist Lb) { linklist Lc; int i;int n; printf(\"请输入n值与主函数输入的值相等:\"); scanf(\"%d\ linklist pa,pb,pc; pa=La->next;pb=Lb->next; pc=La; Lc=pc; while(pa&&pb) if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} pc->next=pa?pa:pb; Lc=Lc->next; for(i=1;i<=2*n;i++) { printf(\"%4d\ Lc=Lc->next;} printf(\"\\n\"); } void shuchu(linklist L,int n) {int i; printf(\"输出的链表元素为：\"); for(i=0;i { LNode La,Lb; 3 int n; printf(\"请输入要插入节点的总数:\"); scanf(\"%d\ create(&La,n); create(&Lb,n); shuchu(&La,n); shuchu(&Lb,n); MergeLidt( &La,&Lb); } 1.8 运行、测试及使用说明（包括运行界面及运行过程） 运行结果如下： 1.9算法分析 分析如下： 主函数main（）首先调用构造单链表函数create（）和函数shuchu（），然后调用函数MergeLidt（）。 有上述结构可知采用分功能模块调试的方法比较合理，即主要功能按以下顺序实现：构造—输出—连接。 4 1.10 总结与体会 通过这次的课程设计，我们对数据结构中单链表的应用有了更深的了解，并且使我们深刻的认识到实践的重要性，只有理论与实践相结合才能达到很好的学习效果，学到很多东西，同时也发现仅仅书本的知识是远远不够的，需要把知识运用到实践中去，能力才能得到提高。由于刚开始对单链表的应用总体结构不熟悉，对书本知识的学习不够扎实，刚拿到题目的时候，还不好下手，就请教了一些学习好的同学，并认真查找了一些资料，才对这次课程设计有了初步了解。 根据对数据结构的了解，我们觉得我们对单链表的认识要更深一点。因此我们选择了单链表实验，作为线性表的一种存储数据，并且可以方便的实现对数据进行插入，输出等操作。 在我们进行课程设计时，虽然在大体上算法是正确的，但时常会出现一些小问题，使我们不得不花一些时间来查找、修改错误。 通过这次课程设计，让我们充分认识到数据结构在编写程序方面的重要地位。由于我们课程设计中编写的是对单链表的基本操作，因此我们在这次课程设计中收获聊了很多关于单链表的应用方面的知识。由于课程设计的目的还有很多，因此没有对其他的题目进行深入的了解而感到遗憾。因此我们希望在以后的学习过程中，能够多多的学习这方面的知识来弥补不足。 5 2 顺序表的基本操作 2.1设计的目的 （1）、学会定义线性表的顺序存储类型，实现C语言程序的基本结构，对线性表的一些基本操作和具体的函数定义。 （2）、掌握顺序表的基本操作，实现顺序表的插入、删除、查找等操作。 2.2 设计内容与要求 要求：（1）对顺序表的每个基本操作用单独的函数实现。 （2）编写完后上机实验。 内容：在表中实现插入、删除、查找等操作。 2．3 课题分析 本程序主要实现顺序表的基本操作，实现顺序表的插入删除等运算。并且要输入一个元素后可以快速查找到并进行相关的操作。 2．4 算法思想 本程序是关于顺序表的基本操作运算的，算法思想如下： 建立一个顺序表，在顺序表中若L是SqList类型的顺序表，则表中第i个数据元素是L.elem[i-1]。一般情况下，在第i个元素之前插入一个元素时，需要将第n至第i（共n-i+1）个元素向后移动一个位置。而删除时，即删除第i个元素时需将从第i+1至第n（共n-i）个元素一次向前移动一个位置。 2．5 概要设计 （1）、函数结构定义： Typedef struct{ elemType *elem; int length; int listsize }Sqlist; (2)、程序结构 Main() Create() Locate() Insert() Delete() Printf() 6 2．6 详细设计 动态分配顺序存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int *elem; int length; int listsize }SqList; 建立顺序表 create(SqList *L) { int n,i;L1->elem=(int*)malloc((LIST_INIT_SIZE)*sizeof(int)); if(!L1->elem) {printf(“overflow\\n\\n”);return; } L1->length=0;L1->listsize=LIST_INIT_SIZE; printf(“please input Listlength n;\\n”); scanf(“%d”,&n); L1->length=n; printf(“input list elem:”); for(i=0;i locate(SqList *L2,int e) { int i=1 int *p; p=L2->elem; while(*p!=e) {p++;i++;} if(i<=L2->length) printf(“Be find;the position is:%d\\n,i”); else printf(“not be find\\n”);} 插入元素 insert(SqList *L3,int i,int e) { int *newbase;int *p,*q;int j; if(i<1||i>L3->length+1) 7 {printf(“the position is error!\\n”); return;} if(L3->length<=L3->listsize) {newbase=(int*)realloc(L2->elem,L2->listsize+LISTNCREMENT)*sizeof(int); if(!newbase){printf(“overflow\\n”);return;} l3->elem=newbase;L3->listsize+=LISTNCREMENT;} q=&(L3->elem[i-1]); for(p=&(L3->elem[L3->length-1]);p>=q;--p) *(p+1)=*p;*q=e;++L3->length; printf(“the list elem are:”); for(j=0;j delete(SqList *L4,int i) { int *p;int *q;int j; if((i<1)||i>(L4->length)) {printf(“the position of deleting is error!\\n”); return;} p=&(L4->elem[i-1]); e=*p;q=&(L4->elem[L4->length-1]); for(++p;p 2．7 源码 #define LIST_INIT_SIZE 100 #define LISTNCREMENT 10 typedef struct{ int *elem; int length; int listsize;}SqList; main() { SqList L;int m;int n;int i;int k,b; create(&L); printf(\"input locate elem is:\"); scanf(\"%d\locate(&L,m); printf(\"input a insert position:\"); 8 scanf(\"%d\printf(\"\\n\"); printf(\"input a insert elem:\"); scanf(\"%d\printf(\"\\n\"); insert(&L,i,n); printf(\"input delete the position k:\"); scanf(\"%d\printf(\"\\n\"); delete(&L,k,&b); printf(\"The program END!\\n\");} create (SqList *L1) { int n;int i;L1->elem=(int*)malloc((LIST_INIT_SIZE)*sizeof(int)); if (!L1->elem) {printf(\"overflow!\\n\");return;} L1->length=0;L1->listsize=LIST_INIT_SIZE; printf(\"please input listlength n:\\n\"); scanf(\"%d\L1->length=n; printf(\"input list elem:\"); for (i=0;i locate (SqList *L2,int e) { int i=1;int *p; p=L2->elem; while (*p!=e) {p++,i++;} if (i<=L2->length) printf(\"be find;the position is:%d\\n,i\"); else printf(\"not be find\\n\");} insert (SqList *L3,int i,int e) { int *newbase;int *p,*q;int j; if (i<1||i>L3->length+1) {printf(\"the position is error!\\n\"); return;} if (L3->length<=L3->listsize) 9 newbase=(int*)realloc(L3->elem,(L3->listsize+LISTNCREMENT)*sizeof(int)); if (!newbase) {printf(\"overflow\\n\");return;} L3->elem=newbase;L3->listsize+=LISTNCREMENT;} q=&(L3->elem[i-1]); for (p=&(L3->elem[L3->length-1]);p>=q;--p) *(p+1)=*p;*q=e;++L3->length; printf(\"the list elem are:\"); for (j=0;j printf(\"%-3d\printf(\"\\n\");} delete (SqList *L4,int i) { int *p;int *q;int j; if ((i<1)||i>(L4->length)) {printf(\"the position of deleting is error!\\n\"); return;} p=&(L4->elem[i-1]); q=&(L4->elem[L4->length-1]); for (++p;p printf(\"the list elem are:\"); for (j=0;j 2．8 运行、测试及使用说明。 2.9 总结与体会 在做这个课程设计之前，我把以前的数据结构基本上都忘了，现在做了课程设计，等于有重新回顾了一下！收获很大！知道了顺序表的基本操作流程，并且自己编写了程序！是的自己关于顺序表方面的真的长进了很多！ 10 3.线性表在图书管理中的应用 3.1设计的目的 熟悉并掌握线性表的定义和使用，能够进行数据的输入、修改和删除。进一步理解所学的各种基础知识，如数据对象的逻辑结构，物理结构和操作实现算法，以及它们的在编程时的使用方法。进一步掌握用C++来编写和调试程序。 3.2设计内容与要求 内容： 完成《图书馆管理系統》系统的分析设计工作，并选用适当的开发工具完成系统的开发。 要求： 1、完成课题分析； 2、算法思路； 3、概要设计； 4、详细设计； 5、源码； 6、运行测试； 3.3 课题分析 目前市面上流行的管理系统不少。但是，对于学校的图书馆管理系统来说，不需要大型的系统。只需要一个操作方便，功能实用，能满足学校图书馆数据的管理及需求的系统。我的目标就是开发一个功能实用、操作方便，简单明了的图书馆管理系统。 此图书馆管理系统，包括：图书管理子系统。对每种书的登记内容包括书号、书号、著作作者、现存量和库存量。 系统主要功能如下： 采编入库：新购一种书，确定书号后，登记到图书账目表中，如果表中已有，则只将库存量增加。 通过本管理系统，可以大大的节约工作时间，减少工作量，提高了工作效率，能帮助工作人员更加方便、高效的管理图书馆。 3.4算法思路 1) 图书初始化 输入图书的一些信息，编号、作者、书名、数量，使有一定的库存。 2) 新书入库 11 新书采编入库，输入编号后如果有次数只需输入数量，没有则继续输入书名、作者、数量。 3.5概要设计 图书馆管理总是以书类为单位管理的，将创建的书类用数组存储起来。每一本书用一个节点表示，考虑到以后进行各项操作的方便，这些结点用链表方式组成一个个书类。每个结点有五个域： （1）书名； （2）书号； （3）著作作者； （4）现存量； （5）库存量。 3.6详细设计 (1)涉及单链表 template void BuildList(Node T e;char c; Node while((c=getchar())==’\\n’); } (2)功能设计 12 图书管理系统 图书录入 书 名 书 号 著作作者 现存量 库存量 3.7源码 int creat(shu ku)//创建 { int n,i,m=0,j=1; book *p; cout<<\"请输入一共有多少个图书种类：\"< 13 p->num=m; j++; } cout<<\"请输入第 \"< if (m= =-1) break; cout<<\"请输入第 \"< 3.8运行结果及调试 建立书库，书库为空。然后按照提示，输入书类、书名、书号、著作者等相关信息，即可创建。 3.9总结体会 虽然这次的程序是通过上网查出来的，但是通过这次的实验使我知道了图书管理系统中图书录入的流程，知道了一些以前不知道的知识，在运行程序时也遇到了一些问题，由于对数据结构知识的了解不多所以出现了好多语法错误，通过不断调试运行，向同学请教，最终自己完成了程序的设 14 计与运行成功。通过此程序的编制，我不仅了解到图书馆中图书录入的步骤，而且最重要的是对数据结构知识有了进一步加强和巩固。 这次的实验增加了我们自己动手动脑的能力，希望多做一些这样的实验，很有意义，和现实生活结合的程序增加了我的兴趣。 15 4线性表在图书管理中的应用 4.1设计的目的 随着人们知识能力的提高，图书馆成了人们生活中不可或缺的一部分，而图书馆中存书量和业务量庞大，仅仅靠传统的记账式管理是不够的，图书管理系统应运而生，目的为了提高图书馆的工作效率，实现图书馆、读者图书借阅、返还、读者信息的管理，并且实现图书管理的核心功能，即图书的信息检索，增加、删除、查询、更改等管理。 4.2计内容和要求 运行程序后，首先进入主菜单界面，读者可根据需求，进行借阅图书、归还图书、注册新书、注销旧书、和查询图书信息的操作。进入相应界面，可实现相应功能，并实现对数据的修改。 4.3课题分析 我们要用散列表实现电话号码查找系统。设计出的程序要包含以下功能： 1、设计一个中文界面来帮助用户，提示用户要实现什么操作，需要输入什么才能实现这种操作，使用户一目了然。 2、设计一个散列表来存储电话号码、用户名、地址。最常用的是除留余数法，这就需要合理的选择k值来减少冲突发生的机会。另外冲突时不可避免的。 3、从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表。 4.4算法思路 根据开发者和客户的需求分析后，可以把系统功能分为五个功能模块： 图书管理系统 主菜单界面 查询图书信息息注册新书注销旧书借阅图书归还图书 1、设计界面：首先设计一个界面，使读者能根据输出的界面正确操作，来完成用户的所需要的操作。定义一个菜单，输出用户界面。 2、建立节点：用结构体定义一个名为node的结构体。先建立节点具体如下： 16 4.5概要思想 定义三个字符数组分别存放名字地址和号码，在定义一个next指针，是用来指向下一个位置的下面在定义几个指针用来以后调用用。定义两个哈希函数，分别用号码和姓名作为关键码来进行散列存储的。在按号码散列是取第三位及三位后的关键码相加，然后用除留余数法，取K=20进行散列key=key%20按姓名存储时是从第一个就开始累加的。因为名字一般第一个不会重复，而电话号码的前三位大多都一样，所以电话号码的从三开始累加的。 3、显示列表：分别按名字和号码输出信息，建立一个工作指针，用来指向数组的第一个位置如果第一个位置不为空，则输出所指向的节点的信息，将该指针后移。按姓名显示和按号码显示均可用此方法。 4、查找用户信息（按号码）：形参为数组。调用散列表函数1，既以号码为关键码存的函数/按号码查找用户信息。定义一个工作指针q当q不为空时吧输入的号码和当前q所指向的号码比较若不同，则q指向数组的下一个位置。若指向的内容和输入的内容相同则指针调用name,address,num函数输出内容。 5、查找用户信息（按姓名）：同按号码一样，主函数：用if 语句来实现不同函数的调用输入1就调用添加记录的函数apend();输入2就调用list2();输入3就调用list() ; 输入6,7分别调用find(),find2();输入5返回 4.6概要设计 1、单通过直接输出显示号码本及其选项1.添加记录；2.姓名散列； 3.号码散列；4.查找记录；5.退出系统。 主函数，先定义字符串char num[11];char name[21];创建两个 create();create2() ;调用前面已经建立的闭散列函数从而实现电话本的创建接着运用 while循环来实现输出。每次输出前都调用menu()一次，然后输入你想进行的操作sel的值。例如输入4，会显示6号码查询，7姓名查询，然后根据上述提示 输入按姓名还是号码查询。当输入2时，会显示姓名散列结果，输入3时会显示号码散列结果当输入5时会退出电话本查找系统。 4.7源码 #include struct BOOK { int id,usr[10],total,store,days[10];//定义id 为地址，usr[10]为读者借书证序号store为现存量,days[10]借阅天数， char name[31],author[21]; //name[31]为存放名字的数组,author[21]为存放作者的数组 }books[100]; void return_confirm(void) //定义一个返回函数 { cout<<\"按任意键返回……\"< { cout<<\"书名:\"< int n,i; cout<<\"请输入图书序号:\"; cin>>i; for(n=0;n<100;n++) { if(books[n].id==i) { cout<<\"书名:\"< void book_out(void) //1：借阅图书 { int n,s,l,d; cout<<\"借阅图书\"; if((n=search_book())!=-1&&books[n].store>0) { cout<<(\"请输入借书证序号:\"); cin>>s; cout<<(\"请输入可借天数:\"); cin>>d; for(l=0;l<10;l++) { books[n].usr[l]=s; books[n].days[l]=d; break; } books[n].store--; } 18 if(n!=-1&&books[n].store==0) cout<<\"此书已经全部借出\"; return_confirm(); } int look(int id) // 查找函数 { int i=0; for(i=0;i<100;i++) { if(books[i].id==id) return i; }; return -1; } void book_add(void) 量 { int n,id; cout<<\"注册新书\"< books[n].id=id; cout<<\"书名:\"; cin>>books[n].name; cout<<(\"作者:\"); cin>>books[n].author; cout<<(\"数量:\"); cin>>books[n].total; books[n].store=books[n].total; z++; return_confirm(); }} //3：注册新书若库里有的只需增加总 //若库里没有则把书的各种输入 19 void main(void) // 主菜单 { while(1) { menu: cout<<\" ***操作选单***\"< switch(n) //用switch(n) case调用各个函数 {case 1: book_out();break; case 3: book_add();break； }}} 4.8运行、测试及使用说明 1借阅图书 3注册新书 20 4.9总结和体会 在这项工作中，使我了解到了在设某个程序的过程中，需求分析是十分重要的，只有通过需求分析，才能使我们正确认识到在程序设计是将要面临的问题，并进行合理的解决。想要进行程序的设计，首先我们必须先认清这个实验将要完成什么，需要实现那些功能，并且在分析其功能的过程中，需要我们运用哪些知识来解决问题，在分析程序的过程中，更要明确一条主线，即主要的解决方式，然后将程序分成几个功能模块，再分析每个模块都具体运用哪些知识来实现，画出程序实现的流程图并编写伪代码。 还有在程序的设计过程中，重要一点就是要有耐心，往往在调试的过程中会出现特别多的错误，而纠正错误则是一项十分艰巨的任务。更重要的是，让我们明确了在面对一个课题或设计题目的时候，应该如何下手，如何对其的各项功能进行分析，在具体应用的时候，又让我们对程序设计语言的运用有了进一步的巩固，在改正错误的时候，则是大家知道了在设计程序的时候，哪些问题是经常出现的，应如何避免。相信本次设计会让自己在以后的学习过程中提升一个层次。 21 5线性表在学生成绩管理中的应用 5.1设计的目的 本课程设计为学生提供了一个既动手又动脑，自学，查资料，独立实践的机会。将本学期课本上的理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对C++系统编程有一个大致的了解。 5.2设计的内容与要求 内容 :(1)系统功能的进一步完善；(2)索引表采用树表。(3)设计内容(4)程序流程图(5)源程序（6）软件测试报告（包括所用到的数据及结果） 要求 (1)成绩信息录入功能(2)成绩信息浏览功能(3)查询功能：按学号查询或按成绩段查询(4)成绩信息的删除(5)成绩信息的修改 5.3课题分析 目前市面上流行的管理系统不少。但是，对于学校的学生成绩管理系统来说，不需要大型的系统。只需要一个操作方便，功能实用，能满足学校学生成绩信息数据的管理及需求的系统。我的目标就是开发一个功能实用、操作方便，简单明了的学生成绩管理系统。通过本管理系统，可以大大的节约工作时间，减少工作量，提高了工作效率，能帮助老师更加方便、高效的管理成绩的信息。 5.4算法思路 1录入模块 录入一些学生的基本信息，包括学生姓名，学号，成绩等。 2显示模块 显示学生的主要信息，包括学生的姓名，学号，成绩等。 3查询模块 根据你输入的学生姓名，输出详细的学生信息。 4删除模块 根据你输入的学生姓名，删除学生信息。 5修改模块 对学生的信息进行修改。 5.5概要设计 相关知识点： 1.建立单链表 template void BuildList(Node T e;char c; Node cout<<”Another element?y/n”< cin>>e;p=new Node while((c=getchar())==’\\n’); } } 5.6详细设计 1录入模块 主函数 Student 输入函数 录入功能 其他程序代码 其他功能 保存基本信息 其他成员函数 2查询模块 录入学生基本信息 其他功能 主函数 Student 保存姓名函数 查询功能 其他程序代码 输出函数 其他成员函数 输出被查找的学生基本信息 5.7源代码 #include \"stdio.h\" struct Student { 23 char ID[20]; char Name[20]; float Mark1; float Mark2; float Mark3; float Average; }; struct Student students[1000]; int num=0; float Avg(struct Student stu) { return (stu.Mark1+stu.Mark2+stu.Mark3)/3; } int Student_SearchByIndex(char id[]) { int i; for (i=0;i return i; } return -1; } int Student_SearchByName(char name[]) { int i; for (i=0;i return i; } } return -1; } void Student_DisplaySingle(int index) { printf(\"%10s%10s%8s%8s%8s%10s\\n\学号\姓名\成绩\成绩\成绩\平均成绩\"); printf(\"-------------------------------------------------------------\\n\"); printf(\"%10s%10s%8.2f%8.2f%8.2f%10.2f\\n\ students[index].Mark1,students[index].Mark2,students[index].Mark3,students[index].Average); 24 } void Student_Insert() { while(1) { printf(\"请输入学号:\"); scanf(\"%s\ getchar(); printf(\"请输入姓名:\"); scanf(\"%s\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); students[num].Average=Avg(students[num]); num++; printf(\"是否继续?(y/n)\"); if (getchar()=='n') { break; } } } /*修改学生信息*/ void Student_Modify() { float mark1,mark2,mark3; while(1) { char id[20]; int index; printf(\"请输入要修改的学生的学号:\"); scanf(\"%s\ getchar(); index=Student_SearchByIndex(id); if (index==-1) { printf(\"学生不存在!\\n\"); 25 } else { printf(\"你要修改的学生信息为:\\n\"); Student_DisplaySingle(index); printf(\"-- 请输入新值--\\n\"); printf(\"请输入学号:\"); scanf(\"%s\ getchar(); printf(\"请输入姓名:\"); scanf(\"%s\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); printf(\"请输入成绩:\"); scanf(\"%f\ getchar(); students[index].Average=Avg(students[index]); } printf(\"是否继续?(y/n)\"); if (getchar()=='n') { break; } } } void Student_Delete() { int i; while(1) { char id[20]; int index; printf(\"请输入要删除的学生的学号:\"); scanf(\"%s\ getchar(); index=Student_SearchByIndex(id); if (index==-1) { printf(\"学生不存在!\\n\"); 26 } else { printf(\"你要删除的学生信息为:\\n\"); Student_DisplaySingle(index); printf(\"是否真的要删除?(y/n)\"); if (getchar()=='y') { for (i=index;i num--; } getchar(); } printf(\"是否继续?(y/n)\"); if (getchar()=='n') { break; } } } void Student_Select() { while(1) { char name[20]; int index; printf(\"请输入要查询的学生的姓名:\"); scanf(\"%s\ getchar(); index=Student_SearchByName(name); if (index==-1) { printf(\"学生不存在!\\n\"); } else { printf(\"你要查询的学生信息为:\\n\"); Student_DisplaySingle(index); } printf(\"是否继续?(y/n)\"); if (getchar()=='n') 27 { break; } } } main() { int choice; IO_ReadInfo(); while(1) { printf(\"\\n------ 学生成绩管理系统------\\n\"); printf(\"1. 增加学生记录\\n\"); printf(\"2. 修改学生记录\\n\"); printf(\"3. 删除学生记录\\n\"); printf(\"4. 按姓名查询学生记录\\n\"); printf(\"5. 按平均成绩排序\\n\"); printf(\"6. 退出\\n\"); printf(\"请选择(1-6):\"); scanf(\"%d\ getchar(); switch(choice) { case 1: Student_Insert(); break; case 2: Student_Modify(); break; case 3: Student_Delete(); break; case 4: Student_Select(); break; case 5: Student_SortByAverage(); Student_Display(); break; case 6: exit(); break; } IO_WriteInfo(); 28 } } 5.8总结体会 通过此次学生成绩管理系统的设计，使我对C++程序设计有了深一步的了解，对系统设计及开发有了比较全面的思路。此次系统设计给我们提供了一个既动手又动脑、自学、独立实践的机会，使我们养成了勤翻阅各种相关资料的习惯，将书本上的理论知识和实际有机地结合起来，锻炼了实际分析问题和解决问题的能力，提高了适应实际、实践编程的能力，为今后的学习和实践打下了良好的基础。 29 6线性表在工资管理中的应用 6.1设计的目的 (1) 掌握线性表的定义 (2）熟悉线性表的实现方法 (3) 掌握线性表的各种基本操作 6.2设计的内容与要求 问题描述：利用所学知识，完成线性表的插入、删除、查找等基本操作设计与实现；通过实验加强对线性表的理解和应用。 基本要求： (1) 定义线性表结构 (2) 分别完成数据的插入，删除，查找等基本操作。 (3) 设计一个测试主函数进行测试 6.3 课题分析 (1) 这是一个命令解释函数，循环往复的处理用户的每一条命令，每一条命令以回车符结束。 (2) 所输入的数据应按一定的格式规范，程序本身应能很好的对命令的格式进行检查，并有一定的简单的容错能力。 (3) 程序演示线性表的基本操作应包含数据的插入，删除，查找等基本操作等 (4) 程序的输出要规范，并有一定的解释性文字 6.4 算法原理 一个线性表是n个数据元素的有限序列。在非空表中的每一个数据元素都有一个确定 的 位置。线性表是一个非常灵活的数据结构，它的长度可根需要增长或缩短，即对线性表可以进行插 入或删除等。因此通常用数组来描述数据结构中的顺序存储结构。 6.5 概要设计 （1）线性表的抽象数据类型的定义 AST String{ 数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0} 数据关系：R1={ 30 基本操作： InitList(&L) 操作结果：构建一个空的线性表L。 GetElem(L,I,&e) 初始条件：线性表L已存在，1<=i<=ListLength(L)。 操作结果：用e返回L中第i个数据元素的值。 ListInsert(&L,i,e) 初始条件：线性表L已存在，1<=i<=ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelste(&L,I,&e) 初始条件：线性表L已存在且非空，1<=i<=ListLength(L)。 操作结果：删除L中第i个数据元素，并且e返回其值，L的长度减1. 数组指针elem指示线性表的基地址，length指示线性表的当前长度并将线性表的当前长度设为“0”。Listsize指示顺序表当前的分配的存储空间大小，一旦因插入元素空间不足时，可进行再分配.即对顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。 线性表的插入的操作时指在线性表的第i-1个数据和第i个数据之间插入一个新的数据。就是要使线性表的长度+1.一般情况下，在第i（1 6.6 详细设计 （1）线性表的插入： Status ListInsert_Sq(SqList &L,int i,ElemType e){ //在顺序线性表L中第i个位置之前插入新的元素e， 31 //i的合法值为1<=i<=ListLength_Sq(L)+1 if(L.length>=L.length+1)return ERROR; //i值不合法 if(L.length>=L.listsize){ //当前储存空间已满，增加分配 newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW); L.listsize+=LISTINCREMENT;} q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p; //插入位置及之后的元素右移 *q=e; //插入e ++L.length; //表长增1 return OK; }//ListInsert_Sq （2）线性表的删除： Status ListDelet_Sq(SqList &L,int i,ElemType &e){ //在顺序线性表L中删除第i元素，并用e返回其值， //i的合法值为1<=i<=ListLength_Sq(L) if((i<1)||(i>L.length))return ERROR; //i值不合法 p=&(L.elem[i-1]); //p为被删除元素的位置 e=*p; //被删除元素的值赋给e q=L.elem+L.length-1; //表尾元素的位置 for(++p;p<=q;++p)*(p-1)=*p; //被删除元素之后的元素左移 --L.length; //表长减1 return OK; }//ListInsert_Sq 6.7 程序代码 #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int *elem; int length; int listsize; }SQLIST; void Create(SQLIST &L) { L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int)); if(!L.elem) printf(\"为线性表分配空间失败!\"); 32 L.length=0; L.listsize=LIST_INIT_SIZE; } int Insert(SQLIST &L,int i,int e) {int *newbase,*p,*q; if(i<1||i>L.length+1) printf(\"error\"); if(L.length>=L.listsize) { newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); if (!newbase) printf(\"fail\"); L.elem=newbase; L.listsize+=LISTINCREMENT; }q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK;} int ListDelete(SQLIST &L,int i,int e) {int *p,*q; if ((i<1)||(i>L.length)) return ERROR; p=&(L.elem[i-1]); e= *p; q=(L.elem+L.length-1); for (++p;p<=q;++p) *(p-1)=*p; --L.length; return OK; } void Locate(SQLIST &L,int e) {int i,*p; i=1; p=L.elem; } void main() { SQLIST s; Create(s); s.elem[0]=1000; s.elem[1]=2000; s.elem[2]=3000; s.elem[3]=4000; s.elem[4]=5000; s.length=5; printf(\"\\n\\n----------------------------------------工资表为---------------------------------------\\n\"); printf(\"\\n\\n已建立的工资表为:\\n\"); for(int i=0; i printf(\"%d \",s.elem[i]); printf(\"\\n\\n请输入要插入工资的位置及插入的工资的数目:\\n\"); int tmp,n; scanf(\"%d%d\",&n,&tmp); Insert(s,n,tmp); printf(\"\\n\\n插入数据后的顺序表为:\\n\"); for(i=0; i printf(\"\\n\\n删除数据后的顺序表为:\\n\"); for(i=0; i 6.8 运行结果 6.9 实验总结 通过这次实验，我对线性表有了更好的认识。在实验过程中，我掌握了线性表的插入和删除方法，。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。通过克服困难让我不断的进步。 35 7 线性表在汽车管理中的应用 7.1 设计的目的 熟悉并掌握线性表的定义和使用，能够进行数据的输入、修改和删除。进一步掌握用C++来编写和调试程序。 7.2 设计内容与要求 内容：完成《汽车管理系統》系统的分析设计工作，并选用适当的开发工具完成系统的开发。 要求：1、完成课题分析；2、算法思路；3、概要设计；4、详细设计；5、源码；6、运行测试； 7.3 课题分析 目前市面上流行的管理系统不少。但是，对于汽车管理系统来说，不需要大型的系统。只需要一个操作方便，功能实用，能满足汽车数据的管理及需求的系统。我的目标就是开发一个功能实用、操作方便，简单明了的汽车管理系统。 此管理系统，包括：汽车管理子系统。通过本管理系统，可以大大的节约工作时间，减少工作量，提高了工作效率，能帮助工作人员更加方便、高效的管理。 7.4 算法思路 3) 汽车初始化 输入汽车的一些信息，编号、颜色，使有一定的库存。 4) 新车入库 新车采编入库，输入编号后有次数只需输入数量。 7.5 源码 #include int num; char name[10]; int age; char colour[10]; char outdady[20]; int tel; char nativeplace[50]; }car[50]; 36 int i=0; void shuru() { char a; do{ printf(\"\\n请输入品牌:\"); scanf(\"%s\ fflush(stdin); printf(\"\\n请输入具体名称:\"); gets(car[i].name); printf(\"\\n\") ; printf(\"请输入出场日期:\"); scanf(\"%d\ fflush(stdin); printf(\"\\n请输入颜色:\"); gets(car[i].colour); fflush(stdin); printf(\"\\n请输入车牌号:\"); scanf(\"%d\ fflush(stdin); printf(\"\\n请输入汽车归属地:\"); gets(car[i].nativeplace); fflush(stdin); printf(\"\\n是否继续输入另外一辆车的信息?(y/n)\"); fflush(stdin); a=getchar(); i++; }while(a=='y' && i<=50); } void xianshi() { int j; printf(\"品牌\名称\出场日期\颜色\车牌号\汽车归属地\\n\"); for(j=0;j car[j].name,car[j].name,car[j].age,car[j].colour,car[j].outdady,car[j].num,car[j].nativeplace); } void chazhao() { int m; char name[20],b; do { printf(\"\\n请输入想查找的车的类型:\"); fflush(stdin); 37 gets(name); for(m=0;m if(strcmp(name,car[m].name)==0) { printf(\"\\n\您查找的车型在第%d个位置找到了!!!\\n\ break; } } if(m>=20) printf(\"\\n\没有找到这种车型!!!\\n\"); else { printf(\"%s\%s\%d\%s\%d\%d\%s\\n\ car[m].name,car[m].name,car[m].age,car[m].colour,car[m].outdady,car[m].num,car[m].nativeplace); } printf(\"\\n是否查找另一辆车的信息?(y/n)\"); fflush(stdin); b=getchar(); }while(b=='y'); } void shanchu() { char name[20],c; int a,b; do { printf(\"\\n请输入要删除的汽车型号:\\n\"); fflush(stdin); gets(name); for(a=0;a if(strcmp(name,car[a].name)==0) break; } for(b=a;b if(a>i) printf(\"\没有找到这种车!!!\\n\"); else { i--; 38 xianshi(); } printf(\"\\n是否继续删除另一辆车的信息?(y/n) \"); fflush(stdin); c=getchar(); }while(c=='y'); } void main() { int change; do{ printf(\"\\n\"); printf(\"\\n\"); printf(\" * * * * * *欢迎使用公司汽车信息管理* * * * * \\n\"); printf(\" （此汽车管理程序是利用线性表结构完成的）\\n\\n\"); printf(\" 以下为功能选项：\\n\"); printf(\" = =\\n\"); printf(\" = 1.输入汽车信息 2.显示汽车信息 =\\n\"); printf(\" = =\\n\"); printf(\" = 3.查找汽车信息 4.删除汽车信息 =\\n\"); printf(\" = =\\n\"); printf(\" = 0.退出汽车信息管理系统 =\\n\"); printf(\" = =\\n\"); printf(\" 这是杨州同学的汽车信息管理程序！\\n\"); printf(\"\\n\"); printf(\"\\n\"); fflush(stdin); printf(\" 请输入功能选项：\"); scanf(\"%d\ switch(change) { case 1: shuru(); break; case 2: xianshi(); break; case 3: chazhao(); break; case 4: shanchu(); break; case 0: break; } getch(); } 39 while(change!=0); } 7.6 运行结果 7.7 总结体会 虽然这次的程序是通过上网查出来的，但是通过这次的实验使我知道了汽车管理系统中的流程，知道了一些以前不知道的知识，在运行程序时也遇到了一些问题，由于对数据结构知识的了解不多所以出现了好多语法错误，通过不断调试运行，向同学请教，最终自己完成了程序的设计与运行成功。对于数据结构知识有了进一步加强和巩固。 40 8 线性表实现一元稀疏多项式的简单计算器 8.1 设计的目的 进一步熟悉抽象数据类型的定义和实现、如何利用数组实现顺序结构、继承的实现方式。 学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。 8.2 设计内容与要求 基本功能要求： 1 输入并建立多项式 2输出多项式，输出形式为整数序列：n，c1，e1，c2，e2„„cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。 3多项式a和b相加，建立多项式a+b，输出相加的多项式。 用带表头结点的单链表存储多项式。 测试数 23 据：(x+x+x)+0 8.3 课题分析 本程序要求输入并建立多项式，能够降幂显示出多项式，实现多项式相加相减的计算问题，输出结果。 8.4 算法思想 采用链表的方式存储链表，定义结点结构体。运用尾差法建立两条单链表，以单链表polyn p和polyn h分别表示两个一元多项式a和b。 为实现处理，使p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项。 ① 若p->expn 41 8.5 概要设计 1数据结构的选用 typedef struct Polynomial{float coef; //系数 int expn; //指数 struct Polynomial *next;}*Polyn,Polynomial; 2函数调用关系 程序流程图 主函数pa,pb,pc 项数m return返回*bc *n 返回*head back 建立多项式 create polyn 多项式相PolynADDpol(polyn pa, 输出多项式polyn pb ) while{printf(“”) 8.6 详细设计 开始 建立多项式 根据flag 选择功能 flag=1 flag=3 flag=2 输出多项式 多项式相加 退出 结束 42 8.7 源码 #include typedef struct Polynomial{//项的表示 float coef; //系数 int expn; //指数 struct Polynomial *next; //指针域 }*Polyn,Polynomial; //Polyn为结点指针类型 void Insert(Polyn p,Polyn h){ //插入或者合并 if(p->coef==0) free(p); //系数为0的话释放结点 else{ Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn q1=q2; q2=q2->next; } if(q2&&p->expn==q2->expn){ //将指数相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef){ //系数为0的话释放结点 q1->next=q2->next; free(q2); } } else{ //指数为新时将结点插入即p->expn>q2expn情况 p->next=q2; q1->next=p; } } }//Insert Polyn CreatePolyn(Polyn head,int m){//建立一个头指针为head、项数为m的一元多项式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i printf(\"请输入第%d项的系数与指数:\ 43 scanf(\"%f %d\ Insert(p,head); //调用Insert函数插入结点 } return head; }//CreatePolyn void DestroyPolyn(Polyn p){ //销毁多项式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next){ free(q1); //释放q1 q1=q2;//指针后移，循环继续释放，直至销毁 q2=q2->next; } } void PrintPolyn(Polyn P){ //输出多项式 Polyn q=P->next; int flag=1; //项数计数器 if(!q) { //若多项式为空，输出0 putchar('0'); printf(\"\\n\"); return; } while (q){ if(q->coef>0&&flag!=1) putchar('+'); //系数大于0且不是第一项 if(q->coef!=1&&q->coef!=-1){//系数非1或-1的普通情况 printf(\"%g\ if(q->expn==1) putchar('X');//系数为1的情况 else if(q->expn) printf(\"X^%d\ } else{ if(q->coef==1){ if(!q->expn) putchar('1'); else if(q->expn==1) putchar('X'); else printf(\"X^%d\ } if(q->coef==-1){ if(!q->expn) printf(\"-1\"); else if(q->expn==1) printf(\"-X\"); else printf(\"-X^%d\ } } 44 q=q->next; flag++; }//while printf(\"\\n\"); }//PrintPolyn Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多项式a+b，返回其头指针 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)){//调用compare返回值 case 1: { qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; } case 0: { qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; } case -1: { qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; } }//switch if(qc->coef!=0){ qc->next=hc->next; hc->next=qc; hc=qc; } 45 else free(qc);//当相加系数为0时，释放该结点 }//while return headc; }//AddPolyn Polyn pa=0,pb=0,pc,pd,pe,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(\"请输入a的项数:\"); scanf(\"%d\ pa=CreatePolyn(pa,m);//建立多项式a printf(\"请输入b的项数:\"); scanf(\"%d\ pb=CreatePolyn(pb,n);//建立多项式a //输出菜单 printf(\"**********************************************\\n\"); printf(\"操作提示：\\n\1.输出多项式a和b\\n\2.建立多项式a+b\\n\3.建立多项式 a-b\\n\4.退出\\n\"); for(;;flag=0){ printf(\"执行操作\"); scanf(\"%d\ if(flag==1){//输出多项式 printf(\"多项式a：\");PrintPolyn(pa); printf(\"多项式b：\");PrintPolyn(pb);continue; } if(flag==2){//多项式相加 pc=AddPolyn(pa,pb); //调用函数，实现相加 printf(\"多项式a+b：\");PrintPolyn(pc); DestroyPolyn(pc);continue; } if(flag==3){//多项式相减 pd=SubtractPolyn(pa,pb); printf(\"多项式a-b：\");PrintPolyn(pd); DestroyPolyn(pd);continue; } if(flag==4) break; //结束循环，退出 DestroyPolyn(pa); DestroyPolyn(pb); return 0; } } 46 8.8 运行 程序运行测试数据：(x+x2+x3)+0 8.9 总结与体会设计 通过这次课程，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获的，特别是当自己遇到问题，问老师，问同学，上网查资料，想尽办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容，编写程序中遇到问题在所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查，直到搞清楚为止。不断的借鉴别人的算法开你不自己的不足，最终深入理解掌握了这个算法我感觉就是我最大的收获。 47 9 利用线性表解决约瑟夫环问题 9.1 设计的目的 1.了解线性表的概念 2.了解线性表的存储结构 3.了解线性表的基本操作 9.2 设计内容与要求 时针方向的下一个人开始重新从1报数，直至所有人全部出列为止。用线性表的相关知识解决约瑟夫环问题，约瑟夫环问题如下编号为1，2，„，n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺 9.3 概要设计 ① 读取人数n和各人的password，生成单循环链表； ② 读取m的初值，用两个for循环依次输出出列人的编号。 9.4 详细设计 删除结点算法设计的思考： p->number=p->next->number; p->password=p->next->password; q=p->next; p->next=p->next->next; free(q); 目前指针p指向代表报到m值的人的结点，需要将此结点删除。要想直接删除p结点，则需增加一个前驱结点，所以采用先将p->next结点中的内容复制到p结点中，然后删除p->next结点的办法。 9.5 源码 #include \"stdafx.h\" #include JosephCircle Init(void)//返回指向表尾的指针（考虑方便删除及报数可能为1的情况） { PJoseph rear = NULL , p = NULL; int pass = 0; int number = 0; do 48 { printf(\"请输入编号为%d成员的密码：(输入 0 终止)\scanf(\"%d\ if (pass)//输入为0则不处理，do while循环将结束 { p = new JosephNode;//分配内存 p->number = number; p->password = pass; if (rear)//如果不是空表，将新节点插入到rear之后并修改rear为新节点。 { p->next = rear->next; rear->next = p; rear = p; } else//如果是空表，修改rear为新节点，将其next域指向自身，构成循环链表。 { rear = p; rear->next = rear; } } } while (pass); return rear; } JosephCircle CountOff(JosephCircle joseph , int& number , int& password) {//返回出列成员的前一个报数成员，理由同前，number存储出列成员编号， //password带入报数数以及存储出列成员密码。 PJoseph p = joseph , q = NULL; int count = 0; if (p->next != p)//如果表中多于一个节点 { while (count++ < password - 1)//为方便删除，计数到报数值-1。 p = p->next; q = p->next; p->next = q->next; number = q->number; password = q->password; delete q; } else//如果表中只有一个节点，出列的肯定为改节点表示的成员，同时表空。 { number = p->number; password = p->password; delete p; p = NULL; 49 } return p; } int main(int argc, char* argv[]) { JosephCircle joseph; int number, pass = 20; printf(\"请输入初始密码：\"); scanf(\"%d\joseph = Init(); while (joseph) { joseph = CountOff(joseph,number,pass); printf(\"%d\\n\} return 0 9.6 测试结果 9.7 总结与体会 编写程序要认真，作图要细心，注意符号问题，做完之后检查是否准确。 50 10 线性表解决约瑟夫环问题-链式存储结构实现 10.1 问题描述 约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，„，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序，以及密码顺序。 10.2 目的 1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 10.3 要求 1. 分析题目，查阅相关资料； 2. 算法设计、数据结构设计； 3. 编写代码并调试； 4. 完成课程设计报告。 5. 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 10.4 算法思想 为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。 用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。 10.5 概要设计 51 GetPersonNumberGetFirstCountValGetPassword InitLinkList() Void main() GetOutputOrder() printResult() printkey() 10.6 数据结构 基本抽象数据类型：建立线性表的链式存储结构；利用链式存储结构建立一单向循环链表！ typedef struct Node { int data; //整型（注：基本数据类型） int password; //整型（注：基本数据类型） struct Node *next; //结点类型，指针类型 }Node, *LinkList; //基本抽象数据类型 int array[] ;//整型数组（注：存放出对序列） int keyp[] ; //整型数组（注：按出队的正确序列，存放密码） int personNumber；//整型（注：输入参与的人的个数） int reportValue; //整型 （注：每次执行的上限值） char I; //字符型（注：用于控制是否重新进入运行程序） 10.7 源程序 #include\"stdio.h\" #include\"stdlib.h\" #include #define MAXPASSWORDVALUE 20 #define MAXPERSONNUMBER 30 //输入人数的最大值 #define MAXFIRSTCOUNTVALUE 10 //最大初始上限值 #define MAXPASSWORD 20 //输入密码最大值 void jiemian ( ) { cout<<\"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\"< cout<<\"@ 欢迎您进入'约瑟夫环'运行界面 @\"< int data; int password; struct Node *next; }Node, *LinkList; //////////////////////////////////////////////// /////函数的声明 //////////////////////////////////////////////// void CreatLinkList(LinkList *); void InitLinkList(LinkList *,int ); int GetPassword(); int GetPersonNumber(); int GetPersonNumber(); int GetFirstCountValue(); void GetOutputOrder(LinkList* , int, int, int* ); void printResult(int * ,int ); void CreatLinkList(LinkList *L)//构建单链表 { (*L) = (LinkList)malloc(sizeof(Node)); if ((*L) == NULL) { printf(\"memory allocation failed, goodbye\"); exit(1); } //系统出现错误 } void InitLinkList(LinkList *L, int personNumber)//初始化单链表 { Node *p, *q;//定义结构体类型指针变量 int i ; p = (*L);//初始化第一个结点,并赋值给p p->data = 1; p->password = GetPassword();//调用GetPassword()输入密码 for (i = 2; i <= personNumber; i++) { q = (LinkList)malloc(sizeof(Node)); if (q == NULL) { 53 printf(\"memory allocation failed, goodbye\"); exit(1); } q->password = GetPassword(); q->data = i; p->next = q; p = q; } p->next = (*L); } int GetPassword()//给每个人赋密码 { int password; static int count = 1;//定义静态局部整性变量 printf(\"\\n请输入第%d的密码:\scanf(\"%d\ while (password > MAXPASSWORDVALUE || password < 0) { printf(\"您输入的数字无效，请输入在1到%d的整数:\scanf(\"%d\} printf(\"第%d个人的密码为:%d\count++; return password; //返回参数 } int GetPersonNumber()//确定需要输入的人数 { int personNumber; printf(\"请输入需要输入人的数目:\"); scanf(\"%d\ while (personNumber > MAXPERSONNUMBER || personNumber <=0) { printf(\"\\n你输入的数字无效,请输入在1到%d的整数!\scanf(\"%d\} printf(\"最终确定的人数为%d\\n\return personNumber; //返回参数 } int GetFirstCountValue()//确定开始的上限值 { int firstCountValue; printf(\"请输入初始的上限值:\"); scanf(\"%d\ while (firstCountValue >MAXFIRSTCOUNTVALUE || firstCountValue <=0) 54 { printf(\"\\n你输入的数字无效,请输入在1到%d的整数!\ALUE); scanf(\"%d\} printf(\"最终的上限值为:%d\return firstCountValue; //返回参数 } /////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////// void GetOutputOrder(LinkList *L, int personNumber, int array[MAXPERSONNUMBER],int key[MAXPERSONNUMBER]) { Node *p, *q; int count = 1, i = 0,j=0; p = (*L); if(reportValue==1) { q=p; while(q->next!=p) q=q->next; //寻找p的头一个节点 array[i++] = p ->data; reportValue=key[j++] = p->password; q->next = p->next; //删除结点p free(p); //释放p中所有数值 p = q->next; count = 1; //重新记当前位置为1 personNumber--; //人数减1 } while (personNumber!=0) { while (count != reportValue) { q = p; p = p->next; count++; } array[i++] = p ->data; reportValue=key[j++]= p->password; q->next = p->next; free(p); p = q->next; count = 1; //重新记当前位置为1 personNumber--; } 55 reportValue, int } void printResult(int array[],int personNumber) //输出出列结果 { int i; printf(\"\\n出队的顺序为:\"); for(i = 0; i < personNumber; i++) { printf(\"%-3d\} } void printkey(int key[],int personNumber) //输出密码顺序 { int i; printf(\"\\n出队的密码为:\"); for(i = 0; i < personNumber; i++) { printf(\"%-3d\} printf(\"\\n\"); printf(\"\\n\"); } int main(void) //主函数 { char i; //定义变量 do //执行do－while语句 { //建立并初始化链表,以及调用各个函数 LinkList L; jiemian ( ); int personNumber, reportValue; int array[MAXPERSONNUMBER]; int key[MAXPERSONNUMBER]; personNumber = GetPersonNumber(); reportValue = GetFirstCountValue(); CreatLinkList(&L); InitLinkList(&L, personNumber); GetOutputOrder(&L,personNumber, reportValue, array,key); printResult(array, personNumber); printkey(key, personNumber); printf(\"请问您是否需要重新开始(Y/N):\"); scanf(\"%d\}while(i=='Y'); return 0; } 56 10.8 测试情况 1、第一次测试。输入所规定范围内的数值。 运行结果如下： 2、 57 因篇幅问题不能全部显示，请点此查看更多更全内容