数据结构课程设计实验报告.doc

软件111班 18号 赵庆珍数据结构课程设计任务书 学期：12-13-1 班级：软件111一、设计目的数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读数据结构课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在三周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题说明：课程设计题目主要分为两大类：，主要是验证性题，少数是简单的综合性题，侧重考查学生对数据结构课程中重要数据结构和算法的理解与掌握程度，相对较简单；本类题目选题要求：要求个人所选题目必须独立完成；原则上不得参考别人的程序，若个人能力有限必须参考，参考成分不得超过30%，其中参考部分自己必须能消化吸收，否则视为无效；为培养学生分析问题、解决问题的实际动手能力和团队协作能力，鼓励有能力的学生尽可能选作难度较高的题目，故仅选作一星题目的学生，无论完成多少题目，原则上最高分不超出70分；仅选作一星和二星题目的学生，无论完成多少题目，原则上最高分不超出85分注意：上述题目，可以相互讨论，但严禁搭便车，杜绝拷贝或分享别人的劳动果实，坚决杜绝让别人代做。一经发现、核实，无论是拷贝者或是被拷贝者的成绩均视为不及格，情节严重者将交由学工办通报批评并受到相应的纪律处分。54选题说明：一个*的题代表满分10分，出色完成者方可得满分，下同；两个*的代表满分15分，三个*的题代表满分30分，四个*的题代表60分。验收时将根据实际选做题目的分值和数量以及实现程序的完善性可以适当加减分；同学们在选题时，要结合个人实际情况，力争多做，必须保证所选题目总分应该在100分以上，保障及格。第一题（一）设计内容简介散列表的设计与实现（*）任务：设计散列表实现电话号码查找系统。要求： （1) 设每个记录有下列数据项：用户名、电话号码、地址； （2) 从键盘输入各记录，以用户名（汉语拼音形式）为关键字建立散列表； （3) 采用一定的方法解决冲突； （4) 查找并显示给定电话号码的记录； 选作内容： （1) 系统功能的完善； （2) 设计不同的散列函数，比较冲突率； （3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。（二）算法设计说明此算法要用散列表实现，里面必须涉及到哈希表的建立，整个程序要实现的功能有：添加用户信息；读取所有用户信息； 以姓名建立哈希表；以电话号码建立哈希表； 查找并显示给定用户名的记录；查找并显示给定电话号码的记录；清屏以及保存功能。定义电话本记录数量（maxsize）、表长（hashsize）、姓名长度(max_size)以及结构体typedef struct的内容，构造两个哈希函数hash1和hash2。解决冲突的办法，姓名用折叠法处理，电话号码取其整型长度，hash1是用姓名建立的哈希函数，hash2是用电话号码建立的哈希函数，两个哈希函数都是用除留余数法实现。处理冲突的函数，采用二次探测法。（三）测试结果1.程序的主界面，包含程序的各个功能：2.添加用户信息的测试结果：3.用哈希数查找第一个用户的信息：（四）分析与探讨这道题主要解决在查找用户时解决冲突。利用哈希表。程序的功能像添加用户信息，读取所有用户信息，清屏以及保存功能 ，都很容易实现，而像以姓名建立哈希表；以电话号码建立哈希表； 查找并显示给定用户名的记录；查找并显示给定电话号码的记录这些就比较难点。要想实现这些，必须了解关于散列表的一些基本定义和原理。以姓名建立哈希表的主要函数：void createhash1(hashtable* h,record* a) for(i=0;ielempp!=null)pp=collision(p,c);if(pp0)cout第i+1elempp=&(ai);h-count+;cout第i+1个记录冲突次数为c.n;coutn建表完成!n此哈希表容量为hashsize,当前表内存储的记录个数为count.n; bengettime();其中的难点就是管理冲突的解决办法，方法就是用二次探测法，主要实现：void searchhash1(hashtable* h,int &c)bengettime();na str;coutstr;int p,pp;p=hash1(str);pp=p;while(h-elempp!=null) & (eq(str,h-elempp-name)=-1)pp=collision(p,c);if(h-elempp!=null&eq(str,h-elempp-name)=1)coutn查找成功！n查找过程冲突次数为c;cout姓名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人存在，查找不成功!n;(五) 流程图开始进入录入系统获得关键字key用hash1(key)计算地址nam_2(d) =关键字？输出记录用探查序列d+i*hash2(key)计算（寻找）散列地址结束nam_ht(d) =关键字？未找到记录 (六) 附录：源代码#include#include#include#include #define maxsize 20 /电话薄记录数量 #define max_size 20 /人名的最大长度#define hashsize 53 /定义表长 #define success 1#define unsuccess -1#define len sizeof(hashtable)typedef int status; /自定义类型语句typedef char namax_size;typedef struct/记录na name;na tel;na add;record;typedef struct/哈希表record *elemhashsize; /数据元素存储基址int count; /当前数据元素个数int size; /当前容量hashtable;/关键字比较功能的实现status eq(na x,na y)/关键字比较，相等返回success；否则返回unsuccessif(strcmp(x,y)=0)return success;else return unsuccess;/记录个数功能的实现status num_ber; /记录定义的个数/输入信息功能void getin(record* a)/键盘输入各人的信息coutnum_ber;for(int i=0;inum_ber;i+)cout请输入第i+1;cout请输入第i+1ai.tel;cout请输入第i+1ai.add;/显示输入信息的实现void showinformation(record* a)/显示输入的用户信息 for(int i=0;inum_ber;i+) coutn第i+1个用户信息:n 姓名：n 电话号码：ai.teln 联系地址：ai.addn; /清屏功能的实现void cls(record* a)system(cls);long fold(na s)/人名的折叠处理char *p;long sum=0;na ss;strcpy(ss,s);/复制字符串，不改变原字符串的大小写strupr(ss);/将字符串ss转换为大写形式p=ss;while(*p!=0)sum+=*p+;coutnsum=sum; return sum;/构造哈希函数int hash1(na str)/哈希函数long n;int m;n=fold(str);/先将用户名进行折叠处理m=n%hashsize; /折叠处理后的数，用除留余数法构造哈希函数return m; /并返回模值int hash2(na str)/哈希函数long n;int m;n = atoi(str);/把字符串转换成整型数.m=n%hashsize; /用除留余数法构造哈希函数return m; /并返回模值/冲突处理函数，用于解决冲突status collision(int p,int &c)/冲突处理函数，采用二次探测法int i,q;i=c/2+1;while(i=0) return q;else i=c/2+1;elseq=(p-i*i)%hashsize;c+;if(q=0) return q;else i=c/2+1;return unsuccess;void bengettime();void createhash1(hashtable* h,record* a)/建表，以人的姓名为关键字，建立相应的散列表bengettime();int i,p=-1,c,pp; for(i=0;ielempp!=null)pp=collision(p,c);if(pp0)cout第i+1elempp=&(ai); /求得哈希地址，将信息存入h-count+;cout第i+1个记录冲突次数为c.n;/需要显示冲突次数时输出coutn建表完成!n此哈希表容量为hashsize,当前表内存储的记录个数为count.n; bengettime();/查找功能的实现void searchhash1(hashtable* h,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息bengettime();na str;coutstr;int p,pp;p=hash1(str);pp=p;while(h-elempp!=null) & (eq(str,h-elempp-name)=-1)pp=collision(p,c);if(h-elempp!=null&eq(str,h-elempp-name)=1)coutn查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn;cout姓名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;bengettime();void bengettime()systemtime sys; getlocaltime( &sys ); coutsys.wyearsys.wmonthsys.wdaysys.whoursys.wminutesys.wsecondsys.wmilliseconds; void createhash2(hashtable* h,record* a)/建表，以电话号码为关键字，建立相应的散列表bengettime();int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c);if(pp0)cout第i+1elempp=&(ai); /求得哈希地址，将信息存入h-count+;cout第i+1个记录冲突次数为c。n;/需要显示冲突次数时输出coutn建表完成!n此哈希表容量为hashsize,当前表内存储的记录个数为count.n;bengettime();void searchhash2(hashtable* h,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息bengettime();na tele;couttele;int p,pp;p=hash2(tele);pp=p;while(h-elempp!=null)&(eq(tele,h-elempp-tel)=-1)pp=collision(p,c);if(h-elempp!=null&eq(tele,h-elempp-tel)=1)coutn查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn;cout姓名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;bengettime();/主界面功能的实现：int main(int argc, char* argv)int c,flag=1;hashtable *h;h=(hashtable*)malloc(len);for(int i=0;ielemi=null;h-size=hashsize;h-count=0;record amaxsize;while (1)coutn 欢迎使用电话号码查找系统 ; coutn coutn ; coutn * 哈希表的设计与实现* ;coutn # ; coutn 1. 添加用户信息 ;coutn 2. 读取所有用户信息 ;coutn 3. 以姓名建立哈希表(解决冲突) ;coutn 4. 以电话号码建立哈希表(解决冲突) ;coutn 5. 查找并显示给定用户名的所有信息 ;coutn 6. 查找并显示给定电话号码的所有信息 ;coutn 7. 清屏处理 ;coutn 8. 退出程序 ; coutn _ 温馨提示： ; coutn 进行5操作前 请先运行3 ; coutn 进行6操作前 请先运行4 （否则查找失败！） ; coutn ;coutn;cout;coutnum;switch(num) case 1:getin(a); break;case 2:showinformation(a);break;case 3: createhash1(h,a); /以姓名建立哈希表 break;case 4: createhash2(h,a); /以电话号码建立哈希表break; case 5:c=0;searchhash1(h,c); break; case 6:c=0;searchhash2(h,c); break; case 7:cls(a);break;case 8:return 0;break;default:cout你输错了，请重新输入!;coutn; system(pause);return 0;第二题文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共n行；要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；一概要设计1.定义结构体struct line，文本行采用顺序存储，行与行之间采用链式存储。二流程图具体操作输出删除后的文章删除这一子串统计字母、数字、空格、某一字符串的个数以及文章总字数输出文字查找某一字串输入文字统计个数主函数开始三测试结果四源代码#include #include typedef struct line char *data; struct line *next; line; /创建列表，向里面输入文本数据/向屏幕输出文字void output(line * &head) line *p=head; /头指针 printf(输入的文章为:n); do /执行 printf(%sn,p-data); while(p=p-next)!=null); /遍历列表printf(n); void menu() /主菜单函数 printf(*文章编辑*n); printf(*n); printf(1.统计文章中全部英文字母数 n); printf(2.统计文章中空格数 n); printf(3 .统计文章中数字个数 n); printf(4.统计文章总字数 n); printf(5.统计指定字符串在文章中出现的次数 n); printf(6.删除指定字符串 n); printf(*n); void create(line * &head) printf (请输入一篇文章，以ctrl+e(e)结尾（每行最多输入80个字符）:n); line *p=new line; /为链表建立一个附加表头指针 head=p; /附给表头指针 char tmp100; while(1) gets(tmp); /输入字符串if(strlen(tmp)80) printf(每行最多输入80个字符); break; if(tmp0=5)break; /如果发现输入e则输入退出 p=p-next=new line; /为结点申请新的存储空间p-data=new charstrlen(tmp)+1; /为结点分配空间 strcpy(p-data,tmp); if(tmpstrlen(tmp)-1=5) /除去最后一个控制符e p-datastrlen(tmp)-1=0; break; p-next=null; /最后一个指针为空 head=head-next; output(head); printf(n); menu(); /统计英文字母void countletter(line * &head) line *p=head; int count=0; do int len=strlen(p-data); /计算当前data中的数据元素个数for(int i=0;idatai=a&p-dataidatai=a&p-datainext)!=null); /遍历链表 printf(全部英文字母数%d n, count);/返回文章里 printf(n); menu(); void countnumber(line * &head) line *p=head; int count=0; do int len=strlen(p-data); for(int i=0;idatai=48 & p-datainext)!=null); printf(文章中字母数为：%d n,count); printf(n); menu(); void countspace(line * &head) line *p=head; int count=0; do int len=strlen(p-data); for(int i=0;idatai=32)count+; while(p=p-next)!=null); printf(文章中空格数为: %d n, count); printf(n); menu(); void countall(line * &head) line *p=head; int count=0; do count+=strlen(p-data); while(p=p-next)!=null); printf(文章总字数%d n,count); printf(n); menu(); void findstring(line * &head) line *p=head; int count=0; int len1=0; int len2; int i,j,k; char str120; printf(n); printf(请输入要统计的字符串:); scanf(%s,str1); len2=strlen(str1); do len1=strlen(p-data); for(i=0;idatai=str10) k=0; for(j=0;jdatai+j=str1j) k+; if(k=len2) count+;i=i+k-1; while(p=p-next)!=null);/遍历列表 printf(该字符串在文中出现的次数: %d n,count); printf(n); menu(); /删除指定的字符串void delstringword(char *s,char *str)/*s为输入的字符串，*str为将要删除的字符串 char *p=strstr(s,str); /从字符串中寻找str第一次出现的位置char tmp80; int len=strlen(s); int i=len-strlen(p); int j=i+strlen(str); int count=0; for(int m=0;mi;m+)tmpcount+=sm; for(int n=j;ndata,str)!=null)delstringword(p-data,str); while(p=p-next)!=null); printf(删除指定字符串后的文章为: n); /output(head); printf(n); menu(); void main() line *head; int i; create(head); for(;) /for 循环 printf(请输入任意一个数字n); scanf(%d,&i); switch(i) case 1:countletter(head);break; case 2:countspace(head);break; case 3:countall(head);break; case 4:countnumber(head);break; case 5:findstring(head);break; case 6:delstring(head);break; default:printf(你输入的数字有误n); （五）心得体会输入文章时，计算机怎样识别文章是否结束？输出文章时，怎样处理表示结束的字符？解决方案：输入文章时，以ctrl+e(e)为结尾，当tmp0=5时，发现输入 e，则退出输入。输出时文章时，如果tmpstrlen(tmp)-1=5即发现表示结束的字符e，用p-datastrlen(tmp)-1=0除去最后一个控制符 e。第三题迷宫求解（*）任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；（一）存储结构定义一个空栈，把从键盘上输入的数据都存储到栈中，定义m n,分别代表迷宫的行数和列数，建立迷宫函数的时候，最外围会加一圈墙作为迷宫的边界。定义四个迷宫方向int add42=0,1,1,0,0,-1,-1,0。先调用函数initmaze(sto)，建立迷宫，然后调用函数mazepath(start,end,sto,add)来寻找出口。（二）算法设计定义一个空栈，把从键盘上输入的数据都存储到栈中，定义m n,分别代表迷宫的行数和列数，建立迷宫函数的时候，最外围会加一圈墙作为迷宫的边界。定义四个迷宫方向int add42=0,1,1,0,0,-1,-1,0。先调用函数initmaze(sto)，建立迷宫，然后调用函数mazepath(start,end,sto,add)来寻找出口。（三） 测试结果(四)分析与探讨迷宫路径寻找的具体方法：先定义一个二维数组：mazestart.xstart.y=2作为入口上的标记，走过的值记做2。往栈里压入元素。push(s1,elem); while(!stackempty(s1) /栈不为空 有路径可走 pop(s1,elem); i=elem.x; j=elem.y; d=elem.d+1; /继续向下一个方向查找寻找路径重要代码：if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; elem.x=i; elem.y=j; elem.d=d; push(s1,elem);i=a;j=b; d=-1; d+;（五）源代码#include #include #define overflow -1 #define max 100 typedef struct int x,y,d; data; typedef struct int pos; data datamax; snode,*stack; stack initstack() stack pstack; pstack=(stack)malloc(sizeof(snode); if(!pstack) exit(overflow); pstack-pos=-1; return pstack; int isempty(stack pstack) return pstack-pos=-1; void push(stack pstack,data x) if(pstack-pos=max-1) exit(overflow); else pstack-pos+; pstack-datapstack-pos=x; void pop(stack pstack) if(pstack-pos=-1) exit(overflow); else pstack-pos-; data gettop(stack pstack) return pstack-datapstack-pos; data setstackelem(int x,int y,int d) data element; element.x=x; element.y=y; element.d=0; return element; void displaypath(stack pstack) data element; printf(the path is:n); while(!isempty(pstack) element=gettop(pstack); pop(pstack); printf(the node is:(%d,%d)n,element.x,element.y); void mazepath(int maze811,int direction42,int x1,int y1,int x2,int y2) int i,j,k,g,h; stack pstack; data element;