第一篇：數據結構課程設計
二○一三 ～二○一四 學年第 二 學期
信息科學與工程學院
綜合設計報告書
課程名稱： 數據結構課程設計 班 級： 學 號： 姓 名： 指導教師：
二○一四 年 六 月
一、實驗內容
(一)、單鏈表：將若干城市的信息存入一個帶頭的單鏈表中，結點中城市信息包括城市的位置坐標，要求：給定一個城市名，返回其位置坐標；給定一個位置坐標P和一個距離D，返回所有與P的距離小于等于D的城市。
（二）、回文判斷：試寫出一個算法，判斷依次讀入的一個以@為結束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含有字符“&”，且序列2是序列1的逆序列。例如，“a+b&b+a”是屬于該模式的字符序列。
（三）、樹和二叉樹：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序，中序，后序）。打印輸出遍歷結果。
二、實驗過程
（一）、城市信息
1、根據題目，我們認為我們所編的程序需要實現以下功能：（1）、創(chuàng)建一個城市鏈表，能夠輸入城市信息，即城市名和城市位置坐標；（2）、能夠根據城市名查詢其位置坐標；（3）、根據離中心坐標距離查詢城市名；（4）、能夠插入城市信息；（5）、能夠刪除城市信息；（6）、能夠更新城市信息；（7）、執(zhí)行完畢，退出程序。
2、演示程序以用戶和計算機的對話方式執(zhí)行，即在在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；輸入相應的數據（濾去輸入中非法字符），運算結果顯示在其后。`測試數據
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;//若分配內存不成功，則返回繼續(xù)分配。
} printf(“請輸入城市名n”);scanf(“%s”,newNode->CityName);//指針的數據域
printf(“請輸入城市坐標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指向得頭結點的下一個結點開判斷結點中的城市名與輸入城市名是否相等。
{
LHead = LHead->Next;//不相等則指針LHead下移，繼續(xù)查找
} LHead->Next = LHead->Next->Next;//相等則刪除此節(jié)點 }
void Create(CityList *LHead){ char sign[20];//定義輸入信息類型及長度
printf(“輸入END退出,輸入其余值繼續(xù)n”);//當輸入END時，在任意輸入，則退出此操作
scanf(“%s”,sign);while(strcmp(sign,“END”))////當輸入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(“城市坐標為%.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下移，繼續(xù)查找
} 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)<= distance*distance)
{
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(“ 歡迎使用本系統(tǒng) n”);printf(“***************************n”);printf(“***************************n”);printf(“1.創(chuàng)建城市鏈表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);//構造并創(chuàng)建城市信息鏈表
break;
case '2':
FindCity(Store);//根據城市名查找城市位置
break;
case '3': FindCityDistance(Store);//根據所給中心坐標和距離值，返回小于等于所給距離值得節(jié)點信息。
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
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]='