数据结构课程设计_数据结构课程设计全

数据结构课程设计由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计全”。

二○一三 ～二○一四 学年第 二 学期

信息科学与工程学院

综合设计报告书

课程名称： 数据结构课程设计 班 级： 学 号： 姓 名： 指导教师：

二○一四 年 六 月

一、实验内容

(一)、单链表：将若干城市的信息存入一个带头的单链表中，结点中城市信息包括城市的位置坐标，要求：给定一个城市名，返回其位置坐标；给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

（二）、回文判断：试写出一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含有字符“&”，且序列2是序列1的逆序列。例如，“a+b&b+a”是属于该模式的字符序列。

（三）、树和二叉树：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序，中序，后序）。打印输出遍历结果。

二、实验过程

（一）、城市信息

1、根据题目，我们认为我们所编的程序需要实现以下功能：（1）、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标；（2）、能够根据城市名查询其位置坐标；（3）、根据离中心坐标距离查询城市名；（4）、能够插入城市信息；（5）、能够删除城市信息；（6）、能够更新城市信息；（7）、执行完毕，退出程序。

2、演示程序以用户和计算机的对话方式执行，即在在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；输入相应的数据（滤去输入中非法字符），运算结果显示在其后。`测试数据

1）、输入”1”调用函数 Create()；

新建城市信息:

fujian(1.1,2.2)

beijing(3.3,4.4)

shanghai(5,6)tianjing(7,8)nanjing(910，910)hangzhou(11,12)输入END键,退出.2）、输入”2”,调用函数FindCity()；

当键入城市名时,返回其城市坐标: 如：键入城市名”fujian”，返回坐标：1.10.2.20 3）、输入“3”调用函数 FindCityDistance();

如：当给定坐标P（3.3，4.4）时,距离5时,就输出所有与P的距离小于等于5的城市信息。4）、输入”4”,调用函数Insert().进行插入新城市信息操作；

如:插入城市信息:hainan(5,8)，当进行查找时,能看到插入城市的信息.证明插入成功.5）、输入”5”,调用函数Delete(),进行删除操作： 6）、输入”6”,调用函数UpdateCity(Store),进行更新操作； 7）、输入”7”,退出.3、源程序代码：

void Init(CityList *LHead){ LHead->Next = NULL;} //建立一个带头结点的单链线性表，LHead指向头结点。void Insert(CityList *LHead){ CityList* newNode;//定义指针结构为cityList型

char m;newNode =(CityList*)malloc(sizeof(CityList));//生成新结点

if(newNode == NULL)//验证空间申请是否成功

{

printf(“内存分配失败n”);

return;//若分配内存不成功，则返回继续分配。

} printf(“请输入城市名n”);scanf(“%s”,newNode->CityName);//指针的数据域

printf(“请输入城市坐标x,yn”);scanf(“%f%c%f”,&newNode->X,&m,&newNode->Y);//将城市信息填入新节点中

while(LHead->Next!= NULL){

LHead = LHead->Next;}//如果非空，HLead指针的位置向后移

newNode->Next = LHead->Next;LHead->Next = newNode;} //将新节点插入链表 void Delete(CityList *LHead){ char delCity[10];printf(“请输入要删除的城市名n”);scanf(“%s”,delCity);while(strcmp(LHead->Next->CityName,delCity))//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。

{

LHead = LHead->Next;//不相等则指针LHead下移，继续查找

} LHead->Next = LHead->Next->Next;//相等则删除此节点 }

void Create(CityList *LHead){ char sign[20];//定义输入信息类型及长度

printf(“输入END退出,输入其余值继续n”);//当输入END时，在任意输入，则退出此操作

scanf(“%s”,sign);while(strcmp(sign,“END”))////当输入END时，再任意输入，则退出此操作

{

Insert(LHead);

printf(“输入END退出,输入其余值继续n”);

scanf(“%s”,sign);} }

void FindCity(CityList* LHead){ char CityName[30];int j=0;printf(“请输入您要搜索的城市名n”);scanf(“%s”,CityName);while(LHead->Next!= NULL && strcmp(LHead->Next->CityName,CityName)){

LHead = LHead->Next;} if(LHead->Next == NULL){

printf(“您要搜索的城市不存在n”);

return;} printf(“城市坐标为%.2f,%.2fn”,LHead->Next->X,LHead->Next->Y);}

void UpdateCity(CityList* LHead){ char CityName[10];printf(“请输入您要更新的城市名n”);scanf(“%s”,CityName);while(strcmp(LHead->Next->CityName,CityName))//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。

{

LHead = LHead->Next;// 当不相等则指针LHead下移，继续查找

} printf(“请输入城市新信息:n”);printf(“请输入城市新名n”);scanf(“%s”,LHead->Next->CityName);printf(“请输入城市新坐标n”);scanf(“%f”,&LHead->Next->X);scanf(“%f”,&LHead->Next->Y);} //输入城市新信息

void FindCityDistance(CityList* LHead){ char m;float x;float y;float distance;printf(“请输入中心坐标x,yn”);scanf(“%f%c%f”,&x,&m,&y);printf(“请输入距离:”);scanf(“%f”,&distance);LHead = LHead->Next;while(LHead!= NULL){

if((x-LHead->X)*(x-LHead->X)+(y-LHead->Y)*(y-LHead->Y)

{

printf(“城市名为%sn”,LHead->CityName);

printf(“城市坐标为%.2f,%.2fn”,LHead->X,LHead->Y);

}

LHead = LHead->Next;}}

void main(){ CityList* LHead;CityList* Store;char choice[3] = {1,2,3};LHead =(CityList*)malloc(sizeof(CityList));Init(LHead);//建立空表

Store = LHead;while(strcmp(choice,“7”)){ //当所选择等于7时，进行以下操作

printf(“***************************n”);printf(“***************************n”);printf(“ 欢迎使用本系统 n”);printf(“***************************n”);printf(“***************************n”);printf(“1.创建城市链表n”);printf(“2.根据城市名查询城市n”);

printf(“3.根据离中心坐标距离查询城市n”);printf(“4.插入新城市信息n”);printf(“5.删除城市信息n”);printf(“6.更新城市信息n”);printf(“7.退出n”);//以上相当于一个选择菜单，皆为提示信息

printf(“==========================n”);

printf(“请输入:”);

scanf(“%s”,&choice);switch(choice[0]){

case '1': //相当于选择1

Create(Store);//构造并创建城市信息链表

break;

case '2':

FindCity(Store);//根据城市名查找城市位置

break;

case '3': FindCityDistance(Store);//根据所给中心坐标和距离值，返回小于等于所给距离值得节点信息。

break;

case '4':

Insert(Store);//插入新结点

break;

case '5':

Delete(Store);//删除结点

break;

case '6':

UpdateCity(Store);//更新结点信息

break;

case '7'://退出

break;

default:

printf(“输入错误,请重新输入n”);

break;} } system(“PAUSE”);return;}

（二）、回文判断

1、需求分析：

（1）输入测试数据组数，接着分组输入字符串，以@结尾。

（2）输入序列总长不超过(MAX_N = 10005)/2 个。将序列1先入栈，接着处理序列2，同时出栈判断。

（3）将序列1全部入栈，接着输入序列2，同时出栈判断。

（4）如果序列满足题目要求，则输出“回文序列”；否则，输出“非回文序列”。

（5）测试数据：pal.txt

a+b&b+a@ a&b@ a&a@

2、（1）数据结构：

typedef struct Stack{ int top,size;char str[MAX_N>>1];};使用结构体，内部定义数组模拟栈。top为栈顶指针，指向当前元素的下一个位置，size表示栈内的元素个数。

（2）函数介绍：

void st_init(Stack *st);//栈的初始化

bool st_push(Stack *st,const char *temp);//入栈

bool st_top(Stack *st,char *temp);//出栈

3、源程序代码： #include #include #include

const int MAX_N = 10005;

typedef struct Stack{ int top,size;char str[MAX_N>>1];};

void st_init(Stack *st){ st->size=MAX_N>>1;st->top=0;} bool st_push(Stack *st,const char *temp){ if(st->top>st->size)

return false;st->str[st->top++] = *temp;return true;} bool st_pop(Stack *st){ if(st->top==0)

return false;st->top--;return true;} bool st_top(Stack *st,char *temp){ if(st->top==0)

return false;*temp = st->str[st->top-1];return true;} int main(){ char str[MAX_N],c;int i,j,cas,len;Stack st;bool flag;// freopen(“pal.txt”,“r”,stdin);printf(“请输入测试组数：n”);scanf(“%d”,&cas);getchar();j=0;while(cas--){ ++j;

printf(“n第 %d 组数据„„n”,j);printf(“n请输入数据（字符串1&字符串2@）：n”);

for(i=0;1;i++){ str[i]=getchar();if(str[i]=='@'){

str[i]='';

break;} } getchar();flag = true;len = strlen(str);st_init(&st);if(!len&1)flag = false;else { for(i=0;i

if(str[i]=='&')

break;

st_push(&st,&str[i]);} for(++i;i

st_top(&st,&c);

flag = st_pop(&st);

if(c!=str[i] ||!flag)

{

flag = false;

break;

} } if(st.top>0)

flag = false;} printf(“nCase : %dn”,j);if(flag)printf(“回文序列。n”);

else

printf(“非回文序列。n”);

printf(“n”);} printf(“输入结束。By changning.huang”);// while(true);return 0;}

（三）、二叉树

1、算法思想：

定义二叉树结构体类型时，也定义了一个顺序栈结构体类型，用以辅助完成二叉树的非递归遍历。

由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。

遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各遍历函数相应操作。

先序遍历，先访问根节点，然后按先序遍历左子树，再按先序遍历右子树。

中序遍历，先按中序遍历左子树，再访问根节点，然后按中序访问右子树。

后序遍历，先按后序遍历左子树，接着按中序遍历右子树，然后访问根节点。

2、测试数据：

ABCффDEфGффFффф（其中ф表示空格字符）

输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA3、源程序代码： #include #include typedef struct tnode { char data;struct tnode *lchild;struct tnode *rchild;}tnode;tnode *Tree_creat(tnode *t){ char ch;ch=getchar();if(ch==' ')t=NULL;else { if(!(t=(tnode *)malloc(sizeof(tnode))))printf(“Error!”);t->data=ch;//printf(“[%c]”,t->data);t->lchild=Tree_creat(t->lchild);t->rchild=Tree_creat(t->rchild);} return t;}

void preorder(tnode *t){ if(t!=NULL){ printf(“%c ”,t->data);

preorder(t->lchild);preorder(t->rchild);} }

void main(){ tnode *t=NULL;t=Tree_creat(t);preorder(t);}

三、心得体会：

数据结构实验是大一学过c语言实验的深化，难度增加了很多。但本次实验三个部分主要涉及单链表、栈、队列的知识。我觉得这些计算机中的线性存储结构原理比较好理解，但是当自己来编写程序的时候难度大大增加了，这其中涉及到一些指针、结构体等c语言基础的东西。开始做实验的时候，由于对上述知识不太熟悉，感觉很困难，后来通过复习c语言相关内容和上网查阅资料，逐步理解代码，一点点掌握了技巧。

总之，这次实验自己感觉对用c语言写程序的掌握又进一步强化了，实验中遇到的困难也都解决了，能力得到了锻炼。