迷宫求解方法在数据结构课程设计中的应用

山东理工大学计算机学院

课程设计

（数据构造）

班级__________________

姓名__________________

学号

指导教师

二O—年一月二十日

课程设计任务书和成绩评估

课题名称数据构造_____________________________

I、题目的目的和规定：

1、设计目的

巩固和加深对数据构造口勺理解，通过上机试验、调试程序，加深对书本知识的理解,

最终使学生可以纯熟应用数据构造的知识写程序。

(1)通过本课程的学习，能纯熟掌握几种基本数据构造向基本操作。

(2)能针对给定题目，选择对应的数据构造，分析并设计算法，进而给出问题的对

的求解过程并编写代码实现。

2、设计题目规定：

通讯录日勺制作

设计目的：用〈〈数据构造〉〉中日勺双向链表作数据构造，结合C/C++语言基本知识。

编写一种通讯录管理系统。以把所学数据构造知识应用到实际软件开发中去。

设计内容：

本系统应完毕一下几方面的功能：

输入信息----enterO;

显示信息-----display();

查找以姓名作为关键字-----search();

删除信息-----delete();

存盘-----save();

装入-----load();

设计规定：

1)每条信息至包括：姓名(NAME)街道(STREET)都市(CITY)(ZIP)国家

(STATE)几项。

2)作为一种完整H勺系统，应具有友好H勺界面和较强的容错能力。

3)上机能正常运行，并写出课程设计汇报。

IK设计进度和完毕状况

IV、成绩评估:

设计成绩：（教师填写）

指导老师：（签字）

二o年一月二十一日

目录

第一章概述..............................................1

第二章系统分析..........................................2

第三章概要设计..........................................2

第四章详细设计..........................................5

第五章运行与测试........................................16

第六章总结与心得......................................22

参照文献24

第一章概述

课程设计是实践性教学中日勺一种重要环节，它以某一课程为基础，可以涉和和课程

有关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课

程更全面的学习和应用，理解和掌握课程的有关知识。

《数据构造》是一门重要H勺专业基础课，是计算机理论和应用H勺关键基础课程。

数据构造课程设计，规定学生在数据构造日勺逻辑特性和物理表达、数据构造日勺选择

和应用、算法的设计和其实现等方面，加深对课程基本内容日勺理解。

同步，在程序设计措施以和上机操作等基本技能和科学作风方面受到比较系统和严

格H勺训练。

通过设计通讯录的制作，深入熟悉数据构造的概念、基本知识和技能，掌握程序设

计H勺基本思绪和措施，并运用所学的基本知识和技能处理简朴的程序设计问题。逐渐熟

悉程序设计H勺措施，并养成良好H勺编程习惯。

在这次H勺课程设计中我选择H勺题目是通讯录H勺制作,我觉得这是我们平常生活中用

到最多日勺首先，也是对我们比较重要的一种东西。虽然它仿佛是一种被遗忘日勺问题，不过

它往往能起到巨大H勺作用。

通讯录的存在重要是重要是以便人们的生活，老式通讯录采用纸张印刷，然后装订

成册，显示每个人的联络措施，地址等，比较粗笨不以便。

伴随现代社会科技日勺发展你可以在个人电脑、掌上电脑、移动等任何联网

设备上录入你日勺联络人的\号码、Email、、MSN、通信地址等通讯录信

息，或对此前日勺信息进行分组、管理和更新，这就是我想所做的。

我想做出一种愈加的以便，迅捷，减少诸多劳动量口勺通讯录。使人们能轻松的管理

自己的信息。

第二章系统分析

1.设计内容：

本系统应完毕一下几方面的功能：

①输入信息（Enter。）：调用此函数用以输入数据到内存中，此过程包括建立对应的

链表或对应的数组，便于读取。

②显示信息（DisplayQ）:用以显示输入的数据，包括从内存中读出和从磁盘中读。

③查找（ScarchO）:以姓名作为关键字查找要找的信息。

④删除信息（Delete。）：用以删除选定的输入信息（姓名作为关键字）。

⑤存盘（SavcQ）:调用比函数将内存中的数据保留至磁盘中。

⑥装入（Load。）：调用此函数用以将之前保留在磁盘的内容读入到内存中或显示到屏

幕上。

通讯录的基本活动包括：对一种人口勺采编、删除、查找和显示等等。由于上述四项基

本活动都是通过人名（即关键字）进行的。

作为通讯录，就需要一种模块来完毕对他人日勺登记和记录状况，本程序使用文献来完

毕上述操作。

2.演示程序是以顾客于计算机的对话方式执行，这需要一种模块来完毕使用者与计算机

语言是转化。

3.程序执行时的I命令：

本程序为了使用时的以便，采用菜单式日勺方式来完毕程序的演示，几乎不用输入

什么特殊日勺命令，只需按提醒输入选者即可.当然也要注意输入时格式，否者也许会

引起某些错误。

5.测试数据。要根据我们自己的需要进行测试，不能凭空的进行数据测试。

第三章概要设计

3.1重要数据构造

重要运用线性表的链式存储构造，来存储数据和信息。

3.2设计措施和原理

线性表的链式存储构造的特点是用一组任意的存储单元存储线性表的数据元素。

因此，为了表达每个数据元素与其后继元素之间的逻辑关系，对于数据元素来说，除

了存储数据自身信息之外，还需要存储一种指示其后继的信息。

这两部分构成数据的存储映像，称为结点。

3.3流程图

3.4设计构造体和基本数据组员类型:

(1)构造体:

(构造一种构造体来存储和使用数据)

structaddress)/*定义构造刃

charname[30J;〃姓名

charstreet[100J;〃街道

charcity[3OJ;〃都市

charstate[30];〃国家

charzip[l1];〃邮政编码

structaddress*next;/*后继指针*/

structaddress*prior;/*前导指针*/

｝；

structaddress*start;/*首结点*/

structaddress*last;/*尾结点*/

structaddress*find(char*);/*申明杳找函数*/

(2)包括被调用函数：

功能

voidenter();〃输入信息/*函数申明*/

voidsearch();〃查找信息

voidsave();〃存盘

voidload();//装入

voidlist();//显示信息

voidmldelete(structaddress**,structaddress**);〃删除信息

voiddls_store(structaddress*i,structaddress**start,

structaddress**lasl);

voidinputs(char*,char*,int);

voiddisplay(structaddress*);

intmenu_select(void);

(3)实现主程序与各模块的调用关系：

主函数通过调用各个函数来连接各个函数，从而实现程序功能的实现。

intmain(void)

(

start=last=NULL;

for(;;)

(

switch(mcnu_sclcct())

(

casel:enter();

continue;

case2:mldelete(&start,&last);

continue;

case3:list();

continue;

case4:search();

continue;

case5:save();

continue;

case6:load();

continue;

case7:exit(0);

}

第四章详细设计

(X)头函数

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

⑵被调用函数

1.添加学生信息：

voidenterO/*输入函数，本函数循环输入资料，当输入姓

名为空时退出*/

(

structaddress*info;/*定义目前结点*/

for(;;)

(

info=(structaddress*)malloc(sizeof(structaddress));/*为目前结点分派空间*/

if(!info)

(

printf(n\nOulofmemory");

exit(O);/*假如分派空

间失败，退出程序*/

)

printf（"输入空姓名结束:\n"）;

inputs("Enternamc:'\info->name,30);

if(!info->name[OD

break;/*假如输入姓名为空，结束循环*/

inpuls("Enterstreet:u,info->street,100);

inputs("Entercity:",info->city,30);

inputs("Enterstate：0,info->state,30);

inputs("Enterzip:",info->zip,l1);

dls_storc(info,&start,&last);/*调用结点插入函数列

1

2删除联络人信息:

voidmldelete(structaddress**start,structaddress**last)/*删除函数列

structaddress*info;

chars[80];

inputs("Entername:",s,30);/*输入欲删除结点日勺name域内容*/

info=find(s);/*杳找该内容*/

if(info)/*假如找到*/

printf("Deleting.....\n");

if(*start==info)/*假如该结点为首结点，把该结点的I下驱

作为新日勺首结点(入口)沟

{*start=info->next;

if(*start)

(*start)->prior=NULL;/*假如新入口不为空，把入口Ff、J前驱置空*/else

*last=NULL;/*假如新入口为空，把尾结点置空，链表为空刃

)

else/*假如欲删除的结点不是首结点*/

{info->prior->next=info->next;/*令该结点日勺前驱的next指针指向该结点

时后驱，*乂令该结点日勺后驱的Iprior指点指向该结点日勺前驱*/

if(info!=*last)/*假如该结点是尾结点，则令该结点

的前驱为尾结点*/

info->next->prior=info->prior;

else

*last=info->prior;

}

free(info);/*释放该结点所占用的J内存*/

printfC^Ok,deletedsuccessfully!\n");

3显示所有联络人;

voidlist(void)

{structaddress*info;

infb=start;

if(inf0=NULL)

printf("NOinformation!*');

while(info)

1

display(info);

info=info->next;

)

printf(H\n\n");

I

voiddisplay(structaddress*info)/*输出传入结点函数*/

(

printf(n%s\nn,infb->name);

printf("%s\n",info->street);

printf(H%s\n",info->city);

printf(n%s\n",info->state);

printf("%s\nu,info->zip);

printf("\n\n");

)

4查找联络人信息；

voidsearch(void)/*查找函数*/

charname[40];

structaddress*info;

printf(uEnternametofind:");/*输入欲查找的姓名*/

gets(name);

info=find(name);

if(!info)

printf('*Notfound");/*假如没找到，显示Notfound*/

else

display(info);产假如找到，显示该结点资料共

)

5装入

voidload()/*调用预存文献函数刃

{

registerintt,size;

structaddress*infb,*temp=O;

char*p;

FILE*fp;/*打开文献*/

if((fp=fopen("mlist",,,r"))==NULL)

printf(HCannotopenfile!\n");

cxit(O);

)

printf("\n\nLoading...\n");*调用文献*/

size=sizeof(structaddress);/*为结点分派内存*/

start==malloc(size);

if(!start)/*假如读取失败，返回*/

(

printfC'Outofmemory

exit(O);

)

info=start;

p=(char*)info;

while((5j:p++=geic(fp))!=EOF)

(

for(t=();t<size-1;++t)

*p++=getc(fp);

info->next==malloc(size);

if(!info->next)

{

printf(nOutofmemory!\n");

return;

)

infb->prior=temp;

temp=info;

info=info->next;

p=(char*)info;

)

temp->next=();

last=temp;

start->prior=();

fclose(fp);/*关闭文献，释放内存*/

printf(u-OK!\nM);

)

6目录函数；

intmenu_select(void)/*主目录*/

{

chars[80];

intc;

printfC...............O(n_n)O~欢迎使用亮亮通讯录系统O(n_G)O~................\nn);

printf(”*****************************************\n”)，

prinlf("**************1.输入信息***************\n">

primf(”**************2.删除信息***************\n”>

prinlf(”**************3.显示信息***************\n“>

prinlf(“**************4杳找***************\n"「

prinlf(“**************5存盘***************\n”>

printf("**************6装入***************\n”>

prinlf(“**************7退出***************\n”)“

printf("*****************************************\n”);

do{

printf("\nPleaseenteryourchoice:\nM);

gets(s);

c=atoi(s);

)while(c<0||c>7);/*超过选项范围时，提醒重新输入*/

returnc;/*返回输入值刃

}

（3）最终程序代码

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

structaddress{/*定义构造*/

charname[30];

charstreetfl00];

charcity[30];

charstate[30];

charzip[l1J;

structaddress*next;/*后继指针*/

structaddress*prior;/*前导指针*/

)；

structaddress*start;/*首结点*/

structaddress*last;/*尾结点*/

structaddress*find(char*);/*巾明查找函数*/

voidenter();/*函数申明*/

voidsearch();

voidsave();

voidload();

voidlist();

voidmldelete(structaddressstructaddress**);

voiddls_store(structaddress*i,structaddress**start,

structaddress**last);

voidinputs(char*,char

voiddisplay(structaddress*);

intmenu_select(void);

intmain(void)

(

start=last=NULL;

for(;;)

(

switch(menu_select())

(

case1:enter();

continue;

case2:mldclctc(&start,&last);

continue;

case3:list();

continue;

case4:search();

continue;

case5:save();

continue;

case6:load();

continue;

case7:exit(0):

}

intmenu_select(void)/*主目录*/

charsl80J;

intc;

printfC...............O(n_n)O~欢迎使用迷你通讯录系统0(n_n)O~.................\nH);

printf(MjJCrjwrjwrjwrjwrjwrjwrjCrjwrjwrjwrjC•

prinlf("**************1.输入信息***************\n”)・

prinlf(”**************2.删除信息***************\n">

prinlf(”**************3.显示信息***************\n“>

prinlf('‘*****************************\n">

prinlf(“**************5存盘***************\n”).

printf("**************6装入***************、]]“)•

printf(H**************7退出***************、]]“)•

printf("*****************************************\n'');

do{

printf("\nPleaseenteryourchoice:\nM);

gets(s);

c=atoi(s);

)while(c<0||c>7);/*超过选项范围时，提醒重新输入*/

returnc;/*返回输入值*/

voidenter()/*输入函数,本函数循环输入资料，当输入姓名

为空时退出以

structaddress*info;/*定义目前结点*/

for(；；)

info=(structaddress*)malloc(sizeof(structaddress));/*为目前结点分派空间*/

if(!info)

printf(n\nOutofmemory");

exit(O);/*假如分派空

间失败，退出程序*/

)

printf("输入空姓名结束:\n");

inputs("Entername:'\info->name,30);

if(!info->name[0])

break;/*假如输入姓名为空，结束循环*/

inpuls("Enterstreel:u,info->street,100);

inputs("Entercity:",info->city,30);

inputs("Enterstate：n,info->state,30);

inputs("Enterzip:",info->zip,l1);

dls_store(info,&start,&last);/*调用结点插入函数*/

)

1

voidinputs(char*prompt,char*s,intcount)/*输入函数，有越界检测功能*/

(

charp[255];

do

{

printf(prompt);

fgets(p,254,stdin);

if(strlen(p)>count)

printf("\nTooLong\n");

)while(strlen(p)>count);

p[strlen(p)-l]=O;

strcpy(s,p);

)

voiddls_storc(/*数据插入函数，也是本例的关键函数*/

structaddress*i,/*接受传入的目前输入结点地址*/

structaddress**start,/*接受传入口勺首结点地址*/

structaddress**last/*接受传入口勺尾结点地址刃

)

(

structaddress*old,*p;/*定义临时指针*/

if(*last==NULL)/*假如尾结点为空,意味着目前链表为空切

(

i->next=NULL;/*目前结点的后驱赋空*/

i->prior=NULL;/*目前结点的前驱赋空*/

*last=i;/*尾结点定义为目前结点*/

*start=i;/*首结点定义为目前结点*/

return;/*返回调用函数*/

)

/*假如链表不为空*/

p=*start;/*p取入口地址（也就是首结点地址产/

old=NULL;/*old赋空*/

while(p)

/*假如p不为空时，执行特循环体，查找比目

前结点应当插入的位置切

if(strcmp(p->name,i->name)<O)/*假如目前结点日勺name域比p（首结点）大

时(实现以name域升序排序)*/

{

old=p;/*old暂存p地址*/

p=p->next;/*p取下一结点*/

)

else/*假如目前输入数据中『'Jname域比p

小时，把数据插入结点p之前*/

(

if(p->prior)/*假如p日勺前驱不为空时*/

(

p->prior->ncxt=i;/*令p的前驱的next域指向目前结点

*/

i->next=p;/*令目前结点日勺后继指向P*/

i->prior=p->prior;/*令目前结点日勺前驱指向p日勺前驱可

p->prior=i;/*令p日勺前驱为目前结点*/

return;/*插入完毕，返回调用函数*/

I

i->next=p;/*假如p的前驱为空时，把目前结点作

为首结点，并令目前结点向后驱为p*/

i->prior=NULL;/*定义目前结点日勺前驱为空*/

p->prior=i;/*P的前驱为目前结点*/

*start=i;/*首结点（入口）为目前结点*/

return;/*插入完毕，返回调用函数号

)

)/*循环体结束*/

old->next=i;/*假如在整个链表都找不到name域比目前数

据日勺name域大欧I结点，

*把R前数据放在作为尾结点放在最终刃

i->next=NULL;/*令链表尾结点后驱批向目前结点，目前结

点日勺后驱为空号

i->prior=old;/*令目前结点的前驱为之前的I最终结点*/

*last=i;/*尾结点取i地址*/

voidmldelete(structaddress**start,structaddress**last)/*删除函数*/

structaddress*info;

chars[80];

inputs("Entername:'\s,30);/*输入欲删除结点『、Jname域内容力

info=find(s);/次查找该内容*/

if(info)/*假如找到*/

printf("Deleting.....\n");

if(*start==info)/*假如该结点为首结点，把该结点的下驱

作为新日勺首结点(入口)*/

{

*starl=info->next;

if(*start)

(*start)->prior=NULL;/*假如新入口不为空，把入口的前驱置空*/

else*last=NLLL;/*假如新入口为空，把尾结点置

空，链表为空*/

}

else/*假如欲删除日勺结点不是首结点*/

{

info->prior->next=info->next;/*令该结点的前驱的next指针指向该结

点日勺后驱，

*又令该结点口勺后驱的prior指点指向该

结点的前驱*/

if(info!=*last)/*假如该结点是尾结点，则令该结点

的前驱为尾结点*/

info->next->prior=info->prior;

else

*last=infd->prior;

)

free(info);/*释放该结点所占用的内存*/

printf("-Ok,deletedsuccessfully!\n");

)

1

structaddress*find(char*name)/*查找函数，形参为欲查找结点的)name域*/

(

structaddress*info;

info=start;

while(info)

(

if(!strcmp(name,infb->name))returninfo;

info=info->next;

)

pnntf(nNamenotfoundAn*');

returnNULL;

}

/*输出整个链表*/

voidlist(void)

(

structaddress*info;

infb=start;

if(inf0=NULL)

printf(HNOinformation!");

while(info)

display(info);

info=info->nexl;

1

printf("\n\n");

voiddisplay(structaddress*info)/*输出传入结点函数*/

(

printf("%s\nu,info->name);

printf(n%s\n",info->street);

printf(u%s\n",info->city);

printf(n%s\n",info->state);

printf("%s\n",info->zip);

printf(n\n\n");

)

voidscarch(void)/*查找函数*/

{

charname[40];

structaddress*info;

printf(nEnternametofind:");/*输入欲查找的I姓名*/

gets(name);

infb-find(name);

if(!info)

printf("Notfound'd);/*假如没找到，显示Notfound*/

else

display(info);/*假如找到，显示该结点资料*/

1

voidsave(void)/*保留函数*/

(

structaddress*info;

FILE*fp;

fp=fbpen(,,mlist,,,,,wb");/*生成文献*/

if(!fp)

(

printf("CannotopenfileAn");

return;

)

printf(u\nSaveing......\nM);

info=start;

while(info)/*把链表写入文献*/

fwritc(info,sizcof(structaddress),1,fp);

infb=info->next;

)

printf("-ok!\n");

fclose(fp);/*链表所有写入文献后，关闭文献*/

voidload()/*调用预存文献函数刃

{

registerintt,size;

structaddress*info,*temp=0;

char*p;

FILE町p;/*打开文献*/

if((fp=fopen("mlist","r"))==NULL)

{

printf("Cannotopenfile!\n");

exit(O);

)

printf("\n\nLoading...\n,');/*调用文献*/

sizc=sizcof(structaddress);/*为结点分派内存*/

start==malloc(size);

if(!start)/*假如读取失败，返回*/

(

printf("Outofmemory!\n");

cxit(O);

)

info二start:

p=(char*)info;

while((*p++=getc(fp))!=EOF)

for(t=0;t<size-1;++t)

*p++=getc(fp);

info->next==malloc(size);

if(!info->ncxt)

(

printf(nOutofmemory!\n");

return;

)

info->prior=temp;

temp=info;

info=info->next;

p二(char小)info;

I

temp->next=();

last=temp;

start->prior=();

fclose(fp);/*关闭文献，释放内存*/

prinlf(n-OK!\n");

第五章运行与测试

(1)运行中的错误

在运行中出现了如下问题

c:\uindows\system32\78.cpp(S1):errorC2065:'exit':undeclaredidentifier

c:\sindoss\system32\78・cpp(54):warningC4508:•main':Functionshouldreturnaualue;,uoid,returntypeassuned

c:\uindons\system32\78.cpp(73):errorC206S:"atoi":undeclaredidentifier

c:\uindow5\5ysteni32\78.cpp(85):errorC2065:"nalloc':undeclaredidentifier

c:\uindous\spsteni32\78.cpp(111):warningC4018:>>,:signed/unsignedmisnatch

c:\uindous\system32\78.cpp(113):earningC«i018:•>>:signed/unsignedmisnatch

c:\windows\system32\78.cpp(196):errorC2G65:•free,:undeclaredidentifier

c:\idndows\system32\78.cpp(286):errorC2g6::noconversionFrom*infto'structaddress»*

Conuersionfronintegraltypetopointertyperequiresreinterpret_castfC-stylecastorfunction-stylecast

c:\ifindows\system32\78.cpp(286):errorC2040::'structaddress■'differsinleuelsofindirectionfron,int'

c:\sindos5\5ystein32\78.cpp(286):warningC4553::operatorhasnoeffect;didyouintend'■'?

c:\Endoss\systeni32\78.cpp(298):errorC2HH。：*=*:cannotconuertfrom*int'to'structaddress«*

ConuersionFronintegraltypetopointertyperequiresreinterpret_cast,C-stylecastorfunction-stylecast

执行cl.exe而出格.

THk期建I调试\在文件1中杳找\在文件2中沓找'结果\SQLDebusine/<II

第一行政IErrorc2065;'exit';undeclaredidentifier

我看过不明白什么意思因此百度了一下意思是未定义的标识符，就是说‘exit'没有定

义，通读程序之后我感觉没有错误，当我准备放弃时发现我没有写头文献

4#include<stdlib.h>?。

因此才会出现没有定义的标识符这个问题我迅速的将其改正来了。

在运行。还是有错误。

IC:\Windows\System32\t.cpp(299):errorC244G::cannotconuertFron'uoid*'to'structaddress»

Conuersionfrom'uoid*'topointertonon-'uoid'requiresanexplicitcast

执行cl.exe时出错.

t.obj-1error(s),0uarning(s)

while((*p++=getc(Fp))?=EOF)

<

for(t=0;t<size-1;++t)

*p++=getc(Fp);

■|inFo->next=malloc(size);

if(?info->next)

{

printF(',Outofnenory?\n");

return;

>

info->prior=tenp;

tenp=info;

inFo=info->next;

p=(char*)info;

错误出目前info->next=malloc(size)这一句中。出错汇报说是赋值时发生错误，

通过我仔细研究和观测发现本来书少写了一种‘='，重要是粗心所致的。

终于在好多次试验之后亮亮通讯录终于做成了。

"LT］:Xliru-ZlirAL

printF("Outofnemory?\n");

return;

info->prior=temp;

leinp=infu;

info=info->next;

p=(char*)info;

tenp->next=0;

last=tenp;

start->prior=0;

fclose(Fp);

printF("-OK?\n");

■:ClassV...］皇］FileView「j

■t.exe-0error(s),0warning(s)

I

-I~K/S国刀'ite•件irhNs转\右书•什crhzfc转\y甲'-CCT口…

主目录如图

如下依次是程序分别是

(1)主界面

(2)联络人信息的输入

(3)联络人的信息的删除

(4)联络人信息的显示

(5)联络人的查找

(6)联络人信息时装盘

0《门」1〉0~欢迎使用迷你通讯录系统0<f］」12

Pleaseenteryourchoice：

Pleaseenteryourchoice：

除入空姓名结更：

Entername：liu

Enterstreet：df

Entercity：dh

Enterstate：hf

Enterzip：hgf

输入至姓名结束：

Entername：

'C：\Wirdovvs\system32\Debug\t.exe"

3显示

4查

MMMMXXXX**■***・入

5

MXXXXXXXX*****

6

出

7

Pleaseenteryoui*choice：

2

Entername：liu

Deleting.............

-Ok,deletedsuccessfully?

............o<n_n）。~欢迎使用迷你通讯录系统。<n_n〉。~

1输入

删

2除

-•KK-X

显

3示

MMXMXXXXX*****

查

4找

5盘

6入

7出

Pleaseenteryourchoice：

Pleaseenteryourchoice：

Liang

fsd

hbtg

xg

re

liu

li

li

yj

。<n_n〉。~欢迎使用迷你通讯录系统。<n_n〉。~

1输

2删

3显