算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告

算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告word教育資料第一學(xué)期實驗報告課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)實驗名稱：城市鏈表一、實驗?zāi)康乃惴ㄅc及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第1頁。本次實驗的主要目的在于熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點。同時，通過本次實驗幫助學(xué)生復(fù)習(xí)高級語言的使用方法。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第1頁。二、實驗內(nèi)容（一）城市鏈表：將若干城市的信息，存入一個帶頭結(jié)點的單鏈表。結(jié)點中的城市信息包括：城市名，城市的位置坐標(biāo)。要求能夠利用城市名和位置坐標(biāo)進行有關(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、win8.1四、實驗結(jié)果（一）城市鏈表:（1）創(chuàng)建城市鏈表；（2）給定一個城市名，返回其位置坐標(biāo)；（3）給定一個位置坐標(biāo)P和一個距離D，返回所有與P的距離小于等于D的城市。（4）在已有的城市鏈表中插入一個新的城市；（5）更新城市信息；（6）刪除某個城市信息。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第2頁。(二)約瑟夫環(huán)算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第2頁。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)建城市鏈表中包涵插入模塊。2.返回位置坐標(biāo)模塊。3.計算距離模塊4.插入模塊。5.更新城市信息模塊6.刪除信息模塊。5.3算法算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第3頁。5.3.1根據(jù)中心城市坐標(biāo)，返回在距離內(nèi)的所有城市：算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第3頁。voidFindCityDistance(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("城市名稱%s\n",L->Name); printf("城市坐標(biāo)%.2lf,%.2lf\n",L->x,L->y); } L=L->next; }}該算法主要用到了勾股定理，考慮到不需要實際數(shù)值，只需要大小比較，所以只用橫坐標(biāo)差的平方+縱坐標(biāo)差的平方<=距離的平方判定。因中心城市本身也在判定范圍之內(nèi)，所以添加了判定條件橫縱坐標(biāo)差的和不能為零。5.3.2主程序中循環(huán)條件判定：for(;;){算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第4頁。 printf("請選擇您的操作\n");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第4頁。 printf("1.創(chuàng)建城市鏈表\n"); printf("2.根據(jù)名字查詢城市\(zhòng)n"); printf("3.插入\n"); printf("4.刪除\n"); printf("5.更新城市信息\n"); printf("6.根據(jù)離中心坐標(biāo)距離查看城市\(zhòng)n"); printf("7.退出系統(tǒng)\n"); scanf("%d",&choice); switch(choice){ ……//case語句 case7:break; } if(choice==7) break; } 若用戶選擇了退出系統(tǒng)選項，則首先跳出switch在跳出for循環(huán)結(jié)束程序。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第5頁。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第5頁。否結(jié)束是是否退出退出插入刪除更新距離5.4流程圖否結(jié)束是是否退出退出插入刪除更新距離查詢創(chuàng)建開始查詢創(chuàng)建開始選擇操作算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第6頁。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第6頁。 5.5程序源代碼typedefstructcitylist{ charName[20]; doublex,y;citylist*next;}citylist,*L;voidInitList_SqCity(citylist*L){//初始化節(jié)點L->next=NULL;}voidInsert_sqCity(citylist*L){ //在鏈表中插入元素 citylist*newNode; newNode=(citylist*)malloc(sizeof(citylist)); if(!newNode)算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第7頁。 printf("存儲分配失敗");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第7頁。 printf("請輸入城市名\n"); scanf("%s",newNode->Name); printf("請輸城市坐標(biāo)xy\n"); scanf("%lf%lf",&(newNode->x),&(newNode->y)); while(L->next!=NULL){ L=L->next; }//如果非空，L指針的位置向后移 newNode->next=L->next; L->next=newNode;}voidCreate_sqCity(citylist*L){ //創(chuàng)建鏈表 charch[100]; inti; printf("輸入END退出,輸入其余值繼續(xù)\n");//當(dāng)輸入END時，在任意輸入，則退出此操作 scanf("%s",ch); for(;strcmp(ch,"END")!=0;){ Insert_sqCity(L);算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第8頁。printf("輸入END退出,輸入其余值繼續(xù)\n");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第8頁。 scanf("%s",ch); } }voidGet_sqCityCoord(citylist*L){ //輸入城市信息返回坐標(biāo) charch[10]; printf("輸入要查詢的城市"); scanf("%s",ch); while(L->next!=NULL&&strcmp(L->next->Name,ch)){ L=L->next; } if(L->next==NULL) printf("城市不存在"); else{算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第9頁。 printf("%.2lf,%.2lf\n",L->next->x,L->next->y);算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第9頁。 }}voidDelete_sqCity(citylist*L){ //刪除城市信息，按名稱/坐標(biāo) printf("請輸入城市名\n"); charch[10]; 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("刪除城市成功");}voidFindCityDistance(citylist*L){ //根據(jù)距離輸出城市算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第10頁。 printf("輸入中心城市坐標(biāo)");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第10頁。 doublex1,y1; scanf("%lf%lf",&x1,&y1); printf("輸入距離"); doubledis; 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("城市名稱%s\n",L->Name); printf("城市坐標(biāo)%.2lf,%.2lf\n",L->x,L->y); } L=L->next; }}voidUpdate_sqCity(citylist*L){ //更新城市信息 charch[10]; printf("請輸入您要更新的城市名\n"); scanf("%s",ch);算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第11頁。 while(strcmp(L->next->Name,ch)){算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第11頁。 L=L->next; } if(L->next==NULL) printf("城市不存在\n"); printf("請輸入城市新信息:\n"); printf("請輸入城市新名\n"); scanf("%s",L->next->Name); printf("請輸入城市新坐標(biāo)\n"); scanf("%lf%lf",&(L->next->x),&(L->next->y));}intmain(){ citylist*L; L=(citylist*)malloc(sizeof(citylist)); InitList_SqCity(L); for(;;){ printf("-----------------------------------\n"); printf("請選擇您的操作\n"); printf("1.創(chuàng)建城市鏈表\n"); printf("2.根據(jù)名字查詢城市\(zhòng)n");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第12頁。 printf("3.插入\n");算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第12頁。 printf("4.刪除\n"); printf("5.更新城市信息\n"); printf("6.根據(jù)離中心坐標(biāo)距離查看城市\(zhòng)n"); printf("7.退出系統(tǒng)\n"); printf("-----------------------------------\n"); intchoice; scanf("%d",&choice); switch(choice){ case1: Create_sqCity(L); getchar(); break; case2: Get_sqCityCoord(L); break; case3: Insert_sqCity(L); break; case4: Delete_sqCity(L); break;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第13頁。 case5:算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第13頁。 Update_sqCity(L); break; case6: FindCityDistance(L); break; case7:break; } if(choice==7) break; } }算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第14頁。5.6仿真結(jié)果算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第14頁。2.查詢城市信息3添加城市4刪除城市算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第15頁。5更新城市算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第15頁。6根據(jù)距離輸出城市5.7調(diào)試心得5.7.1錯誤分析：實驗中出現(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)，加深對課本地理解。算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第16頁。附錄算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第16頁。約瑟夫環(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)成單鏈表voidCreat_JoephLink(intnum){Node*head,*q,*L;L=(Node*)malloc(sizeof(Node));//申請第一個數(shù)的節(jié)點head=L;L->num=1;printf("輸入第一個人的值:");//輸入第一個人的值scanf("%d",&(L->value));inti;for(i=2;i<=num;i++){q=(Node*)malloc(sizeof(Node));L->next=q;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第17頁。L=q;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第17頁。printf("輸入第%d個人的值:",i);//輸入每個人的值scanf("%d",&(L->value));L->num=i;}L->next=head;L=head;//構(gòu)成單向循環(huán)鏈表}5.3.2查找并刪除節(jié)點StatusDelete_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->value;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第18頁。q=L->next;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第18頁。L->next=L->next->next;free(q);}}5.4源程序代碼typedefstructNode{intvalue;Node*next;intnum;}Node;voidCreat_JoephLink(intnum){Node*head,*q,*L;L=(Node*)malloc(sizeof(Node));//申請第一個數(shù)的節(jié)點head=L;L->num=1;printf("輸入第一個人的值:");//輸入第一個人的值scanf("%d",&(L->value));inti;for(i=2;i<=num;i++){q=(Node*)malloc(sizeof(Node));算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第19頁。L->next=q;算法與及數(shù)據(jù)結(jié)構(gòu)實驗報告全文共22頁，當(dāng)前為第19頁。L=q;printf("輸入第%d個人的值:",i);//輸入每個人的值scanf("%d",&(L->value));L->num=i;}L->next=head;L=head;//構(gòu)成單向循環(huán)鏈表intm;intj;printf("輸入初始值m的大小");scanf("%d