第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

二○一三 ～二○一四 學(xué)年第 二 學(xué)期

信息科學(xué)與工程學(xué)院

綜合設(shè)計報告書

課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 班 級： 學(xué) 號： 姓 名： 指導(dǎo)教師：

二○一四 年 六 月

一、實驗內(nèi)容

(一)、單鏈表：將若干城市的信息存入一個帶頭的單鏈表中，結(jié)點中城市信息包括城市的位置坐標(biāo)，要求：給定一個城市名，返回其位置坐標(biāo)；給定一個位置坐標(biāo)P和一個距離D，返回所有與P的距離小于等于D的城市。

（二）、回文判斷：試寫出一個算法，判斷依次讀入的一個以@為結(jié)束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含有字符“&”，且序列2是序列1的逆序列。例如，“a+b&b+a”是屬于該模式的字符序列。

（三）、樹和二叉樹：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序，中序，后序）。打印輸出遍歷結(jié)果。

二、實驗過程

（一）、城市信息

1、根據(jù)題目，我們認(rèn)為我們所編的程序需要實現(xiàn)以下功能：（1）、創(chuàng)建一個城市鏈表，能夠輸入城市信息，即城市名和城市位置坐標(biāo)；（2）、能夠根據(jù)城市名查詢其位置坐標(biāo)；（3）、根據(jù)離中心坐標(biāo)距離查詢城市名；（4）、能夠插入城市信息；（5）、能夠刪除城市信息；（6）、能夠更新城市信息；（7）、執(zhí)行完畢，退出程序。

2、演示程序以用戶和計算機的對話方式執(zhí)行，即在在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；輸入相應(yīng)的數(shù)據(jù)（濾去輸入中非法字符），運算結(jié)果顯示在其后。`測試數(shù)據(jù)

1）、輸入”1”調(diào)用函數(shù) 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”,調(diào)用函數(shù)FindCity()；

當(dāng)鍵入城市名時,返回其城市坐標(biāo): 如：鍵入城市名”fujian”，返回坐標(biāo)：1.10.2.20 3）、輸入“3”調(diào)用函數(shù) FindCityDistance();

如：當(dāng)給定坐標(biāo)P（3.3，4.4）時,距離5時,就輸出所有與P的距離小于等于5的城市信息。4）、輸入”4”,調(diào)用函數(shù)Insert().進行插入新城市信息操作；

如:插入城市信息:hainan(5,8)，當(dāng)進行查找時,能看到插入城市的信息.證明插入成功.5）、輸入”5”,調(diào)用函數(shù)Delete(),進行刪除操作： 6）、輸入”6”,調(diào)用函數(shù)UpdateCity(Store),進行更新操作； 7）、輸入”7”,退出.3、源程序代碼：

void Init(CityList *LHead){ LHead->Next = NULL;} //建立一個帶頭結(jié)點的單鏈線性表，LHead指向頭結(jié)點。void Insert(CityList *LHead){ CityList* newNode;//定義指針結(jié)構(gòu)為cityList型

char m;newNode =(CityList*)malloc(sizeof(CityList));//生成新結(jié)點

if(newNode == NULL)//驗證空間申請是否成功

{

printf(“內(nèi)存分配失敗n”);

return;//若分配內(nèi)存不成功，則返回繼續(xù)分配。

} printf(“請輸入城市名n”);scanf(“%s”,newNode->CityName);//指針的數(shù)據(jù)域

printf(“請輸入城市坐標(biāo)x,yn”);scanf(“%f%c%f”,&newNode->X,&m,&newNode->Y);//將城市信息填入新節(jié)點中

while(LHead->Next!= NULL){

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

newNode->Next = LHead->Next;LHead->Next = newNode;} //將新節(jié)點插入鏈表 void Delete(CityList *LHead){ char delCity[10];printf(“請輸入要刪除的城市名n”);scanf(“%s”,delCity);while(strcmp(LHead->Next->CityName,delCity))//從LHead指向得頭結(jié)點的下一個結(jié)點開判斷結(jié)點中的城市名與輸入城市名是否相等。

{

LHead = LHead->Next;//不相等則指針LHead下移，繼續(xù)查找

} LHead->Next = LHead->Next->Next;//相等則刪除此節(jié)點 }

void Create(CityList *LHead){ char sign[20];//定義輸入信息類型及長度

printf(“輸入END退出,輸入其余值繼續(xù)n”);//當(dāng)輸入END時，在任意輸入，則退出此操作

scanf(“%s”,sign);while(strcmp(sign,“END”))////當(dāng)輸入END時，再任意輸入，則退出此操作

{

Insert(LHead);

printf(“輸入END退出,輸入其余值繼續(xù)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(“城市坐標(biāo)為%.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指向得頭結(jié)點的下一個結(jié)點開判斷結(jié)點中的城市名與輸入城市名是否相等。

{

LHead = LHead->Next;// 當(dāng)不相等則指針LHead下移，繼續(xù)查找

} printf(“請輸入城市新信息:n”);printf(“請輸入城市新名n”);scanf(“%s”,LHead->Next->CityName);printf(“請輸入城市新坐標(biāo)n”);scanf(“%f”,&LHead->Next->X);scanf(“%f”,&LHead->Next->Y);} //輸入城市新信息

void FindCityDistance(CityList* LHead){ char m;float x;float y;float distance;printf(“請輸入中心坐標(biāo)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)<= distance*distance)

{

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

printf(“城市坐標(biāo)為%.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”)){ //當(dāng)所選擇等于7時，進行以下操作

printf(“***************************n”);printf(“***************************n”);printf(“ 歡迎使用本系統(tǒng) n”);printf(“***************************n”);printf(“***************************n”);printf(“1.創(chuàng)建城市鏈表n”);printf(“2.根據(jù)城市名查詢城市n”);

printf(“3.根據(jù)離中心坐標(biāo)距離查詢城市n”);printf(“4.插入新城市信息n”);printf(“5.刪除城市信息n”);printf(“6.更新城市信息n”);printf(“7.退出n”);//以上相當(dāng)于一個選擇菜單，皆為提示信息

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

printf(“請輸入:”);

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

case '1': //相當(dāng)于選擇1

Create(Store);//構(gòu)造并創(chuàng)建城市信息鏈表

break;

case '2':

FindCity(Store);//根據(jù)城市名查找城市位置

break;

case '3': FindCityDistance(Store);//根據(jù)所給中心坐標(biāo)和距離值，返回小于等于所給距離值得節(jié)點信息。

break;

case '4':

Insert(Store);//插入新結(jié)點

break;

case '5':

Delete(Store);//刪除結(jié)點

break;

case '6':

UpdateCity(Store);//更新結(jié)點信息

break;

case '7'://退出

break;

default:

printf(“輸入錯誤,請重新輸入n”);

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

（二）、回文判斷

1、需求分析：

（1）輸入測試數(shù)據(jù)組數(shù)，接著分組輸入字符串，以@結(jié)尾。

（2）輸入序列總長不超過(MAX_N = 10005)/2 個。將序列1先入棧，接著處理序列2，同時出棧判斷。

（3）將序列1全部入棧，接著輸入序列2，同時出棧判斷。

（4）如果序列滿足題目要求，則輸出“回文序列”；否則，輸出“非回文序列”。

（5）測試數(shù)據(jù)：pal.txt

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

2、（1）數(shù)據(jù)結(jié)構(gòu)：

typedef struct Stack{ int top,size;char str[MAX_N>>1];};使用結(jié)構(gòu)體，內(nèi)部定義數(shù)組模擬棧。top為棧頂指針，指向當(dāng)前元素的下一個位置，size表示棧內(nèi)的元素個數(shù)。

（2）函數(shù)介紹：

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(“請輸入測試組數(shù)：n”);scanf(“%d”,&cas);getchar();j=0;while(cas--){ ++j;

printf(“n第 %d 組數(shù)據(jù)??n”,j);printf(“n請輸入數(shù)據(jù)（字符串1&字符串2@）：n”);

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

str[i]='