数据结构课程设计报告学生通讯录管理系统城市链表.doc

l井冈山大学电子与信息工程学院数据结构课程设计报告 ( 20122013年度第一学期)课程名称： 数据结构课程设计 题 目 一： 2.2 学生通讯录管理系统 题 目 二： 2.4.3 城市链表 院 系： 计算机科学系 班 级： 10级软件本（一） 姓 名： 学 号： 指导教师： 孙凌宇老师 成 绩： 2012 年 月 日成 绩 评 定一、 指导教师评语二、 成绩成绩备注 指导教师： 日 期： 年 月 日设计题目<一>： 2.2 学生通讯录管理系统 一、设计要求1问题描述 纸质的通讯录系统已经不能满足大家的要求，容易丢失、查找困难等问题是纸质通讯录所不能克服的缺点。“学生通讯管理系统”是为了帮助老师、同学，或者其他一些需要使用通讯录的人员进行管理和分析的一种应用程序。2 需求分析(1) 输入数据建立通讯录(2) 查询通讯录系统中满足要求的信息(3) 插入新的通讯录信息(4) 删除不需要的通讯录信息(5) 查看所有通讯录信息二、概要设计 为了实现需求分析的功能，可以从三个方面着手设计。1 主界面设计 为了实现学生通讯录管理系统各功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。本系统主控菜单运行界面如图2-3所示。 图2-3 “学生通讯录管理系统”主菜单2 存储结构设计 本系统主要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。其中，链表结点由四个分量构成:通讯录成员学号、通讯录成员姓名、通讯录成员电话号码、指向该结构体的指针。此外，本系统还设置了一个全局变量seat，表示通讯录中成员的序号。3 系统功能设计 本系统设置了5个子功能菜单，5个子功能的设计描述如下。（1） 建立通讯录系统 。可以一次输入多个成员通讯录的信息，建立通讯录。该功能由creatIncreLink( )函数实现。（2） 插入通讯记录。每次可以插入一个成员通讯录的信息。如果要连续插入多个成员通讯录信息必须多次选择该功能。该功能有insertYouXu( )函数实现。（3） 查询通讯记录。可以按两种方式查询所需要的通讯录成员记录，一是按学号查询，二是按姓名查询。分别由seartNum( )和seartName( )函数实现。（4） 删除通讯记录。可以对通讯录中不再需要的信息进行删除。有三种删除方式：按序号进行删除，按学号进行删除和按姓名进行删除。分别由deleteElem( )函数，delNum( )函数和delName( )函数实现。（5） 显示通讯录系统。可以查看通讯录中所有的通讯录成员记录。该功能由printList( )函数实现。三、模块设计1 模块设计 本程序包含两个模块：主程序模块和链表操作模块。其调用关系如图2-4所示。 主程序模块链表操作模块 图2-4 模块调用示意图 2 系统子程序及功能设计 本系统共设置10个子程序，各程序的函数名及功能说明如下，其中大部分函数都是链表的基本操作函数。（1） LinkList creatIncreLink( ) /链表的创建（2） deleteElem( LinkList L,int i) /从通讯录中按序号删除第i个元素（3） delName(LinkList L,char n ) /按姓名删除通讯录记录（4） delNum( LinkList L,int n) /按学号删除通讯录记录（5） void insertYouXu(LinkList L，LinkList Elem ) /插入一条通讯录（6） printList( LinkList L) /打印指针地址为 L的通讯录（7） prior ( LinkList L，LinkList p) / 查找位于当前地址元素的前一元素的地址（8） searchName( LinkList L,int n) /按姓名查找通讯录记录 （9） int searchNum( LinkList L,int n) / 按学号查找查找通讯录记录（10） void main( ) /主函数。设定界面的颜色和大小，调用链表操作模块 3 函数主要调用关系图 本系统10个子程序之间的主要调用关系如图2-5所示。图中数字是各函数的编号。 图2-5 系统函数调用关系图如下所示： 四、详细设计1数据类型定义本系统采用链式结构存储通讯录结点。结点定义如下：typedef struct LNodeint number;double telenum;char name20;struct LNode *next;LNode,*Linklist;2 系统主要子程序详细设计（1） 建立链表的函数，主要用来建立通讯录。Linklist createIncreLink()/创建一个存放通讯录成员的非递减有序表，返回头结点地址Linklist L=(Linklist)malloc(LEN);L->next=NULL;Linklist p;int num=1,number;double telenum;char name20;printf("请输入学生学号、姓名和电话号码，建立通讯录，以'-1'为输入结束标志n"); printf("请输入学号 %d: ",num);scanf("%d",&number);printf("请输入姓名 %d: ",num); char temp=getchar();gets(name);printf("请输入电话号码 %d: ",num);scanf("%1f",&telenum);while(number>=0)p=(Linklist)malloc(LEN);p->number=number; p->telenum=telenum;strcpy(p->name,name);insertYouXu(L,P);num+;printf("请输入学号 %d: ",num); scanf("%d",&number); printf("请输入姓名 %d: ",num);temp=getchar();gets(name); printf("请输入电话号码 %d: ",num); scanf("%1f",&telenum);return(L);（2） 显示链表中所有结点的信息，用查看通讯录所有的记录。void printList(LinkList L) /打印头结点地址为L的通讯录printf("n-n");printf(" 学号姓名电话号码n");printf(" -n");LinkList p=L;int n=1;if(L=NULL | L->next=NULL) printf ("该通讯录中没有元素n"); /判断通讯录是否为空elsewhile(p->next !=NULL)printf("%2d %-9d",n,p->next->number);printf("%-5s %.0fn",p->next->name,p->next->telenum);p=p->next;n+;printf(" -n");return ;五、 测试分析 系统运行主界面如图2-3所示。各子功能测试运行结果如下。1. 通讯录的建立 在主菜单下，用户输入1并回车，然后按照提示建立通讯录，分别输入通讯录成员的学号，姓名，电话号码，运行结果如图2-6所示。 图2-6通讯录的建立 2. 插入通讯录记录 在主菜单下，用户输入2并回车，可以插入一个新的通讯录成员的信息，依次输入学号，姓名和电话号码，运行结果如图2-7所示。 图2-7 插入通讯录3 .查询通讯录记录 在主菜单下，用户输入3并回车，可以按照两种方式查询通讯录。一种是按学号查询，另一种方式是按姓名查询。可按照提示操作，运行结果如图2-8所示。 图2-8查询通讯记录4. 删除通讯录记录 在主菜单下，用户输入4并回车，进行通讯录记录的删除。可以按三种方式进行删除操作：按序号、按学号和按姓名。图2-9是按学号删除的运行结果。 图2-9删除通讯记录 5. 显示通讯录信息 在主菜单下，用户输入5并回车，可以查看通讯录中的所有成员信息。运行结果如图2-10所示。 图2-10 显示通讯录信息六、 用户手册 （1） 本程序执行文件为“学生通讯录管理系统.exe”。（2） 进入本系统之后，随即显示系统主菜单界面，用户可在该界面下输入各子菜单前对应的数字并按回车键，执行相应子菜单命令。（3） 本系统没有提供直接修改通讯录信息的功能，可通过删除和插入操作完成修改功能。七、调试报告 调试过程中insertYouXu createIncreLink 未声明变量。后来把对函数定义提到程序初始定义。发现直接将数值在调用的函数里定义、输入、输出，避免在主函数里传输数据，其这样就不易出现错误。查找算法，运行结果由于字母出错出现死循环。 通过这次课程设计使自己深刻认识到自身的不足。对线性表的插入、删除、查找等算法的实现有了更深一步的理解，受益多多。八、程序清单#include<stdio.h>#include<stdlib.h>#include<string.h>#define NULL 0#define LEN sizeof(LNode)int seat; /通讯录成员的序号typedef struct LNode/用于通讯录结点int number;double telenum;char name20;struct LNode *next;LNode,*LinkList;/1.创建链表void insertYouXu(LNode*pn,LinkList p);LinkList createIncreLink()/创建一个存放通讯录成员的非递减有序表，返回头结点地址LinkList L=(LinkList)malloc(LEN); /头结点L->next=NULL;LinkList p;int num=1,number;double telenum;char name20;printf("请输入学生学号、姓名和电话号码，建立通讯录，以'-1'为输入结束标志n"); printf("请输入学号 %d: ",num);scanf("%d",&number);printf("请输入姓名 %d: ",num); char temp=getchar();gets(name);printf("请输入电话号码 %d: ",num);scanf("%1f",&telenum);while(number>=0)p=(LinkList)malloc(LEN); /新结点p->number=number; p->telenum=telenum;strcpy(p->name,name);insertYouXu(L,p); /有序地插入新结点num+;printf("请输入学号 %d: ",num); scanf("%d",&number); printf("请输入姓名 %d: ",num);temp=getchar();gets(name); printf("请输入电话号码 %d: ",num); scanf("%1f",&telenum);return(L);/2.从通讯录中删除第i个元素void deleteElem(LinkList L,int i) LinkList p=L;int j=0;while (p->next && j<i-1)p=p->next;j+;if(!(p->next) /判断i是否合法，i不能大于元素的个数，也不能小于等于0printf("第%d个元素删除失败n",i); return; LinkList q=p->next;p->next=q->next;free(q); /释放删除的结点/3. 按姓名删除通讯者int delName(LinkList L,char n)int flag=0; /判断要删除的通讯者和通讯录中的姓名是否匹配 LinkList p=L->next;seat=1;if(L->next=NULL) printf("该链表中没有元素，查找失败n");elsewhile(p !=NULL)if(!strcmp(p->name,n) /比较输入的姓名和通讯录中的姓名flag=1; /输入姓名匹配printf("%s",p->name);p=p->next;deleteElem(L,seat);else p=p->next;seat+; /输入姓名不匹配，指针移到下一个通讯者if (flag) printf("被删除n");return flag;/4.按学号删除通讯录int delNum(LinkList L,int n)int flag=0; /判断要删除的通讯者 LinkList p=L->next;seat=1;if(L->next=NULL)printf("该链表中没有元素，删除失败n");elsewhile(p !=NULL)if(p->number<=n)if(p->number=n)flag=1; /输入学号匹配printf("%d",p->number);p=p->next;deleteElem(L,seat);elsep=p->next;seat+;printf("被删除n");return flag;/6.打印头结点地址为L的通讯录void printList(LinkList L) /打印头结点地址为L的通讯录printf("n-n");printf(" 学号姓名电话号码n");printf(" -n");LinkList p=L;int n=1;if(L=NULL | L->next=NULL) printf ("该通讯录中没有元素n"); /判断通讯录是否为空elsewhile(p->next !=NULL)printf("%2d %-9d",n,p->next->number);printf("%-5s %.0fn",p->next->name,p->next->telenum);p=p->next;n+;printf(" -n");return ;/7.找到位于当前地址元素的前一个元素的地址LinkList prior(LinkList L,LinkList p)if(L->next=NULL) return(L);LinkList p_prior=L;while(p_prior->next !=p)p_prior=p_prior->next;return (p_prior);/8.按姓名查找通讯者int searchName(LinkList L,char n)int flag=0; /标志要查找的通讯者和通讯录中的姓名是否匹配LinkList p=L->next;seat=1;if(L->next=NULL | L=NULL) printf("该通讯录中没有元素，查找失败n");elsewhile(p !=NULL)if(!strcmp(p->name,n) /比较要查找的姓名是否和当前通讯录所指姓名匹配flag=1; /输入姓名匹配printf("要查找的是第%d位通讯者：n",seat);printf("Number: %d Name: %s TeleNo.:%.ofn",p->number,p->name,p->telenum);p=p->next;seat+; /!return flag;/9.按学号查找通讯者int searchNum(LinkList L,int n)int flag=0; /标志要查找的通讯者和通讯录中的学号是否匹配LinkList p=L->next;seat=1;if(L->next=NULL) printf("该链表中没有元素，查找失败n");elsewhile(p !=NULL)if(p->number<=n)if(p->number=n)flag=1; /输入学号匹配printf("要查找的是第%d位通讯者：n",seat);printf("学号：%d 姓名：%s 电话号码.:%.ofn",p->number,p->name,p->telenum);p=p->next;seat+;return flag;/10.主函数。设定界面的颜色大小，调用工作区模块函数void main()system("color 1f"); /设置界面颜色LinkList L=NULL;printf("n * 欢迎使用通讯录系统*n");printf(" * 1 通讯录的建立 *n");printf(" * 2 插入通讯记录 *n");printf(" * 3 查询通讯记录 *n");printf(" * 4 删除通讯记录 *n");printf(" * 5 显示通讯记录信息 *n");printf(" * 0 退出管理系统 *n");printf("n * 欢迎使用通讯录系统*n");int flag=0; /通讯录是否建立int menu; /菜单选项printf("请选择0-5：");printf("%d",&menu);while(menu!=0)switch(menu) /用于调用菜单的语句 case 1:L=creatIncreLink(); /调用函数实现通讯录的建立printf("建立通讯录：");printList(L); flag=1;break;case 2:if (flag=1)int number,telenum;char name20;printf("请输入通讯者的学号和姓名：n");printf("请输入学号：");scanf("%d,&number");printf("请输入姓名：");char temp=getchar();gets(name);printf("请输入电话号码：");scanf("%d",&telenum);LinkList p=(LinkList)malloc(LEN); /新结点p->number=number; strcpy(p->name,name);p->telenum=telenum;insertYouXu(L,p); /有序的插入新结点printf("插入后：");printfList(L);else printf("nERROR:通讯录还没有建立，请先建立通讯录n");break;case 3:int way,n,s; /查找方式char na20;if(L!=NULL)if(flag) /通讯录已建立printf("选择查找方式：n");printf(" 1.按学号 2.按姓名");scanf("%d",&way);if(way=1) printf("n请输入学号："); scanf("%d",&n); s=searchNum(L,n); /查找通讯录成员 if(s=0)printf("无此通讯者，查找失败！n");else if(way=2)printf("n请输入姓名：");char temp=getchar(); gets(na);s=searchName(L,na);if(s=0)printf("无此通讯者，查找失败！n");else printf("通讯录中无记录！n");break;else printf("通讯录中无记录！n");break;case 4:int way; /删除方式printf("请选择删除方式：1.按序号 2.按学号 3.按姓名 n");scanf("%d",&way);if(way=1)int n;printf("请输入通讯录序号："); scanf("%d",&n);printf("删除后：n"); deleteElem(L,n); /按序号删除printfList(L);else if(way=2)int n,f;printf("请输入学号："); scanf("%d",&n);f=delNum(L,n); if(f!=0)printf("删除后：n"); printfList(L);else printf("无该学号，删除失败！n");else if(way=3);char na20;int f;printf("请输入姓名：");char temp=getchar();f=delName(L,na);if(f!=0)printf("删除后：n"); printfList(L);else printf("无该学号，删除失败！n");else printf("ERROR！n");break;case 5:printf("当前通讯录记录内容如下:n");printfList(L);break; case 0: exit(0); default: printf("n没有此功能，重新输入n");printf("选择功能:");scanf("%d",&menu);设计题目<二>： 2.2.3 城市链表一、 设计要求1问题描述将各个城市的信息存入一个带头结点的单链表。结点中的城市信息包括城市名、位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除更新等操作。2 需求分析（1） 输入城市信息，建立城市链表（2） 根据城市名或者位置对城市进行查找（3） 向城市链表中加入新的城市（4） 根据城市名或位置删除城市链表中的城市（5） 更新城市链表中城市的信息（6） 搜索离某点距离为d的城市，并输出它的信息（7） 查看城市链表中所以城市的信息二、概要设计1主界面设计 为了实现城市链表的各种功能，为了方便用户使用本系统。本系统主控菜单运行界面如图2-1所示。 图2-1 “城市链表”主菜单2. 存储结构设计 本系统采用带头节点的链表结构来储存“城市链表”中的信息。链表节点有4个成员：城市名、城市的横坐标、城市的纵坐标，指向该结构体的指针。3 系统功能设计本系统设置了9个子功能菜单，9个子功能的设计描述如下。 （1） 建立城市链表。由函数creatLink( ) 实现，该功能实现城市结点的输 入以及连接。可以初始化链表，输入城市名“end”时表示建立结束 。 （3） 插入链表记录。由函数insert()实现。该功能实现按坐标由小到大的 顺序将结点插入到链表中。 （4） 查询链表记录。由searchName（）函数和searchPos（）函数实现。 其中searchName（）实现按照城市名查询的操作，searchPos（）实 现按照城市坐标查询的操作。 （5） 删除链表记录。由delName（）函数和delPos（）函数实现。其中 delName 的操作。 （6） 显示链表记录。由printList（）函数实现。该功能实现格式化的链表 输出操作，可以显示修改后的链表状态。 （7） 更新链表信息。由update（）函数实现。该功能实现按照城市名更新 城市的坐标信息。 （8） 输出链表。由函数 PrintLn( )来实现。输出链表里所有城市的信息。 （9） 城市搜索。 由函数Search( )来实现。给定一个位置，搜索距离它d 的城市，并输出他们的信息。 三、模块设计1模块设计 本程序包含两个模块：主程序模块和链表操作模块。调用关系如图（2）所示。主程序模块链表操作模块 图2-2 模块调用示意图2 系统子程序及功能设计本系统共设置3个子程序，各程序的函数名及功能说明如下：（1） Linklist creatLink( ) /创建一个城市链表，返回头结点地址（2） printList(Linklist L)/ 打印头结点地址为L的城市链表（3） int searchName(Linklist L,char name)/以城市名查找（4） int searchPos(Linklist L,int px,int py)/以城市坐标查找（5） int insert(Linklist L,Linklist city)/插入（6） int delName(Linklist L,char name)/利用城市名称删除（7） int delPos(Linklist L,int px,int py)/利用坐标删除（8） int update(Linklist L,char name)/更新（9） int getPos(Linklist L,char name)/给定一个城市名,返回城市坐标（10）int getCity(Linklist L,int px,int py,int d)/给定一个城市坐标P,返回距离 小于等于d的城市（11） void main( )/主函数，实现链表各项操作的选择3 函数主要调用关系图 本系统3个子程序之间的主要调用关系如图2-3所示。图中数字是各函数的编号。128967543102222211main（）四、详细设计1数据类型定义（1）数据类型定义 typedef struct LNode/城市结点char name20;int posx;/横坐标int posy;/纵坐标struct LNode *next; LNode,*Linklist;2 系统主要子程序详细设计（1）建立城市链表Linklist creatLink() /创建一个城市链表，返回头结点地址Linklist L=(Linklist)malloc(LEN); /头结点L->next=NULL;Linklist p;char name20;int px;int py;char end4="end"printf("请输入城市名称、横坐标和纵坐标，建立城市链表，以'end'为输入结束标志n");printf("请输入城市名称：");scanf("%s",name);while (strcmp(name,end)printf("请输入横坐标x: ");scanf("%d",&px);printf("请输入纵坐标y：");scanf("%d",&py);p=(Linklist)malloc(LEN); /新结点strcpy(p->name,name)