城市鏈表實驗報告

1、2014-2015學(xué)年第一學(xué)期實驗報告課程名稱： 算法與數(shù)據(jù)結(jié)構(gòu) 實驗名稱： 城市鏈表 一、 實驗?zāi)康?本次實驗的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉 各種鏈表的操作為側(cè)重點。同時，通過本次實驗幫助學(xué)生復(fù)習(xí)高級語言的使用方法。二、 實驗內(nèi)容 （一）城市鏈表 ： 將若干城市的信息，存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括：城市名，城 市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進(jìn)行有關(guān)查找、插入、刪除、更新等操作。(二) 約瑟夫環(huán)m 的初值為 20；密碼：3，1，7，2，6，8，4（正確的結(jié)果應(yīng)為 6，1，4，7，2，3，5）。三、 實驗環(huán)境 VS2010 、w

2、in8.1四、 實驗結(jié)果（一）城市鏈表:（1） 創(chuàng)建城市鏈表； （2） 給定一個城市名，返回其位置坐標(biāo)； （3） 給定一個位置坐標(biāo) P 和一個距離 D，返回所有與 P 的距離小于等于 D 的城市。 （4） 在已有的城市鏈表中插入一個新的城市； （5） 更新城市信息； （6） 刪除某個城市信息。(二) 約瑟夫環(huán)m 的初值為 20；密碼：3，1，7，2，6，8，4輸出 6，1，4，7，2，3，5。五、 附錄城市鏈表：5.1 問題分析該實驗要求對鏈表實現(xiàn)創(chuàng)建，遍歷，插入，刪除，查詢等操作，故使用單鏈表。5.2 設(shè)計方案該程序大致分為以下幾個模塊：1.創(chuàng)建城市鏈表模塊，即在空鏈表中插入新元素。故創(chuàng)建城

3、市鏈表中包涵插入模塊。2.返回位置坐標(biāo)模塊。3.計算距離模塊4.插入模塊。5.更新城市信息模塊6.刪除信息模塊。5.3 算法5.3.1 根據(jù)中心城市坐標(biāo)，返回在距離內(nèi)的所有城市：void FindCityDistance(citylist *L)/根據(jù)距離輸出城市/輸入信息與距離L=L->next;while(L != NULL)if(L->x-x1)*(L->x-x1)+(L->y-y1)*(L->y-y1)<=dis*dis)&&(L->x-x1)+(L->y-y1)!=0 )printf("城市名稱%sn"

4、;,L->Name);printf("城市坐標(biāo)%.2lf,%.2lfn",L->x,L->y); L=L->next; 該算法主要用到了勾股定理，考慮到不需要實際數(shù)值，只需要大小比較，所以只用橫坐標(biāo)差的平方+縱坐標(biāo)差的平方 <= 距離的平方 判定。 因中心城市本身也在判定范圍之內(nèi)，所以添加了判定條件橫縱坐標(biāo)差的和不能為零。5.3.2主程序中循環(huán)條件判定：for( ; ; ) printf("請選擇您的操作n");printf("1.創(chuàng)建城市鏈表n");printf("2.根據(jù)名字查詢城市n&qu

5、ot;);printf("3.插入n");printf("4.刪除n");printf("5.更新城市信息n");printf("6.根據(jù)離中心坐標(biāo)距離查看城市n");printf("7.退出系統(tǒng)n");scanf("%d",&choice);switch(choice)/case語句case 7:break;if(choice = 7)break;若用戶選擇了退出系統(tǒng)選項，則首先跳出switch 在跳出for循環(huán)結(jié)束程序。否結(jié)束是是否退出退出插入刪除更新距離5.4流

6、程圖查詢創(chuàng)建開始選擇操作5.5程序源代碼typedef struct citylist char Name20;double x,y; citylist *next;citylist, *L;void InitList_SqCity(citylist *L)/初始化節(jié)點 L->next = NULL;void Insert_sqCity(citylist *L)/在鏈表中插入元素citylist* newNode;newNode=(citylist*)malloc(sizeof(citylist);if(!newNode)printf("存儲分配失敗");printf

7、("請輸入城市名n");scanf("%s",newNode->Name);printf("請輸城市坐標(biāo)x yn");scanf("%lf%lf",&(newNode->x),&(newNode->y);while(L->next != NULL) L = L->next; /如果非空，L指針的位置向后移 newNode->next =L->next; L->next = newNode;void Create_sqCity(citylist *L)/

8、創(chuàng)建鏈表char ch100;int i;printf("輸入END退出,輸入其余值繼續(xù)n"); /當(dāng)輸入END時，在任意輸入，則退出此操作scanf("%s",ch);for(;strcmp(ch,"END")!=0 ; )Insert_sqCity(L); printf("輸入END退出,輸入其余值繼續(xù)n"); scanf("%s",ch);void Get_sqCityCoord(citylist *L)/輸入城市信息返回坐標(biāo)char ch10;printf("輸入要查詢的城市&

9、quot;);scanf("%s",ch);while(L->next!= NULL &&strcmp(L->next->Name,ch)L=L->next;if(L->next = NULL)printf("城市不存在");elseprintf("%.2lf,%.2lfn",L->next->x,L->next->y);void Delete_sqCity(citylist *L)/刪除城市信息 ，按名稱/坐標(biāo)printf("請輸入城市名n")

10、;char ch10;scanf("%s",ch);while(L->next != NULL&&strcmp(L->next->Name,ch)L=L->next;if(L->next = NULL)printf("城市不存在");/刪除位置不合理L->next=L->next->next; printf("刪除城市成功");void FindCityDistance(citylist *L)/根據(jù)距離輸出城市printf("輸入中心城市坐標(biāo)");d

11、ouble x1,y1;scanf("%lf%lf",&x1,&y1);printf("輸入距離");double dis;scanf("%lf",&dis);L=L->next;while(L != NULL)if(L->x-x1)*(L->x-x1)+(L->y-y1)*(L->y-y1)<=dis*dis)&&(L->x-x1)+(L->y-y1)!=0 )printf("城市名稱%sn",L->Name);prin

12、tf("城市坐標(biāo)%.2lf,%.2lfn",L->x,L->y);L=L->next;void Update_sqCity(citylist* L)/更新城市信息char ch10;printf("請輸入您要更新的城市名n");scanf("%s",ch); while(strcmp(L->next->Name,ch)L=L->next;if(L->next = NULL)printf("城市不存在n");printf("請輸入城市新信息:n"); pr

13、intf("請輸入城市新名n"); scanf("%s",L->next->Name); printf("請輸入城市新坐標(biāo)n"); scanf("%lf%lf",&(L->next->x),&(L->next->y); int main()citylist *L;L=(citylist*)malloc(sizeof(citylist);InitList_SqCity(L);for( ; ; )printf("-n");printf("

14、請選擇您的操作n");printf("1.創(chuàng)建城市鏈表n");printf("2.根據(jù)名字查詢城市n");printf("3.插入n");printf("4.刪除n");printf("5.更新城市信息n");printf("6.根據(jù)離中心坐標(biāo)距離查看城市n");printf("7.退出系統(tǒng)n");printf("-n");int choice;scanf("%d",&choice);switch(

15、choice)case 1:Create_sqCity(L);getchar();break;case 2:Get_sqCityCoord(L);break;case 3:Insert_sqCity(L);break;case 4:Delete_sqCity(L);break;case 5:Update_sqCity(L);break;case 6: FindCityDistance(L); break;case 7:break;if(choice = 7)break; 5.6仿真結(jié)果2.查詢城市信息3 添加城市4 刪除城市5 更新城市6 根據(jù)距離輸出城市5.7 調(diào)試心得5.7.1錯誤分析：實

16、驗中出現(xiàn)的第一個問題是聲明變量，從鍵盤中讀入數(shù)據(jù)是顯示變量未初始化，調(diào)試后發(fā)現(xiàn)是scanf的問題，以后的實驗中應(yīng)注意scanf中讀入信息后是存到了地址里。5.7.2 算法復(fù)雜度的分析： 所有程序 除了InitList_SqCity 復(fù)雜度為O(1),其余均為O(n)。5.7.3 收獲對數(shù)據(jù)結(jié)構(gòu)這門課地應(yīng)用有了一定地了解，知道對線性表插入、刪除等操作的實現(xiàn)，加深對課本地理解。附錄約瑟夫環(huán)：5.1問題分析該實驗要求循環(huán)連續(xù)查找信息，并刪除節(jié)點，故使用單項循環(huán)鏈表。5.2設(shè)計方案1.建立單循環(huán)鏈表 2.產(chǎn)生Joseph環(huán) 3.輸出順序表5.3算法5.3.1 構(gòu)成單鏈表void Creat_Joeph

17、Link(int num)Node *head,*q,*L;L=(Node*)malloc(sizeof(Node);/申請第一個數(shù)的節(jié)點head=L;L->num=1;printf("輸入第一個人的值:"); /輸入第一個人的值 scanf("%d",&(L->value);int i;for(i=2;i<=num;i+)q=(Node*)malloc(sizeof(Node);L->next=q;L=q;printf("輸入第%d個人的值:",i); /輸入每個人的值scanf("%d&q

18、uot;,&(L->value);L->num=i;L->next=head; L=head;/構(gòu)成單向循環(huán)鏈表5.3.2查找并刪除節(jié)點Status Delete_Node(Node *L)for (j=1;j<=num;j+)for(i=1;i<m;i+)/i做循環(huán)變量L=L->next;m=L->value;/將當(dāng)前值設(shè)為m值printf("%d ",L->num);/輸出當(dāng)前節(jié)點信息/刪除當(dāng)前節(jié)點L->num=L->next->num; L->value=L->next->va

19、lue;q=L->next;L->next=L->next->next;free(q); 5.4源程序代碼typedef struct Nodeint value;Node *next;int num;Node;void Creat_JoephLink(int num)Node *head,*q,*L;L=(Node*)malloc(sizeof(Node);/申請第一個數(shù)的節(jié)點head=L;L->num=1;printf("輸入第一個人的值:"); /輸入第一個人的值 scanf("%d",&(L->value);int i;for(i=2;i<=num;i+)q=(Node*)malloc(sizeof(Node);L->next=q;L=q;printf("輸入第%d個人的值:",i); /輸入每個人的值scanf("%d",&(L->value);L->num=i;L->next=head; L=head;/構(gòu)成單向循環(huán)鏈表int m;int j;printf("輸入初始值m的