2015數據結構實踐題目計科13級

一、課題內容：任意選作一j1、【山西農業(yè)大學校園導游程序】問題描述：用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題?；疽螅翰樵兏骶包c的相關信息；查詢圖中任意兩個景點間的最短路徑：查詢圖中任意兩個景點間的所有路徑；增加、刪除、更新有關景點和道路的信息。選作內容：①求多個景點的最佳(最短)游覽路徑。②區(qū)分機動車道和人行道。③實現導游圖的仿真界面。數據結構：typedefstnictmessage(intnum;//景點代碼charname[l00]為景點名稱charpro[500];//簡介}Ciceroni;例如：Ciceromschool[10]={{l,”行政樓\n”},{2,”食堂\ii"},(3,"賽博樓，信息分院辦公室所在地心”},{4,”求是樓，實驗樓計算機中心\n”},{5,”格致樓，法學管理學院”},{6,”工程實習中心，金工實習\n”},{7,”仰儀樓,機電計測分院"},{&”體育館滂邊有籃球場'足球場'還有網球場"},{9,”一號教學樓，主要以階梯教室為主{10,”二號教學樓，小教室為多\n”}}；/*景點名稱和簡介*/要求以本校的景點為例進行編號與介紹。操作：/*給景點之間的路徑賦最大值*//*最短路徑的C語言函數*//*輸出最短路徑和最短距離函數*//*輸入景點代碼查景點名稱和簡介*//*輸入景點代碼查到其它景點的最短距離*/2、【員工管理系統(tǒng)】問題描述：每個員工的信息包括：編號、姓名、性別、出生年月、學歷、職務、電話、住址等。系統(tǒng)能夠完成員工信息的查詢、更新、插入、刪除、排序等功能?；疽螅号判颍喊床煌P鍵字，對所有員工的信息進行排序；查詢：按特定條件查找員工；更新，按編號對某個員工的某項信息進行修改；插入，加入新員工的信息；刪除，按編號刪除己離職的員工的信息。選作內容：實現圖形用戶界面。通過鏈表實現數據結構：stnictworkers{chai-name[15姓名chardepartment]18];//單位chargender;//性別unsignedmtage;〃年齡unsignedlongtelephone;〃電話unsignedlongwage;//工資unsignedlongnum;//職工號stiuctworkers*next;};操作實現：/*插入職工信息，通過鏈表實現*//*具體實現職工信息的插入*//*對職工信息的刪除操作*〃*修改操作*//*實現對員工信息的查找*//*排序勺/*輸出員工信息*//*顯示職工工資情況計算平均工資*/3、【本班學生成績管理】實現功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。能實現對學生信息的簡單管理。具體要求：建立一個4個學生的信息登記表，每個學生的信息包括：學號，姓名，和3門課程的成績(FOX,C,ENGLISH)°程序運行時顯示一個簡單的菜單，例如：：信息輸入(INPUT)：總分統(tǒng)計(COUNT)：總分排序(SORT)：查詢(QUERY)其中：：對4個學生的信息進行輸入；：對每個學生的3門課程統(tǒng)計總分；：對4個學生的總分按降序排序并顯示出來：：查詢輸入一個學號后，顯示出該學生的有關信息：數據結構：structstudent(mtnum;//學號charname[20];〃姓名mtfbxscorey/fbx成績mtcscore;//C語言mtenglishscore;//英語成績stnictstudent*next;};操作：成績信息輸入；統(tǒng)計總分;排序；查詢4、【訂票系統(tǒng)】任務：通過此系統(tǒng)可以實現如下功能：錄入：可以錄入航班情況(數據可以存儲在一個數據文件中，數據結構、具體數據自定)查詢：可以查詢某個航線的情況(如，輸入航班號，查詢起降時間，起飛抵達城市,航班票價，票價折扣，確定航班是否滿倉)可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班己經無票，可以提供相關可選擇航班；退票：可退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。修改航班信息:當航班信息改變可以修改航班數據文件要求：根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；航班信息數據結構typedefchaikeytype;//航班信息結構typedefstnict（clwstart[6]y/;起點站chai-end[6];//終點站chai-sche[10];〃航班期chaitune1[5];//起飛時間chaitune2[5];//到達時間clwmodel[4];//機型mtprice;//^價}nifbtype;〃定義航班節(jié)點typedefstnict（keytypekeys[keylen];//航班號uifotypeothers;〃航班信息mtnext;〃下一航班}slnode;〃航班表typedefstnict（slnodesl[maxspace];intkeynum;mtlength;}sllist;操作實現：（1）錄入航班信息：（2）查詢航班信息：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵這城市，航班票價，票價折扣，確定航班是否滿倉）；可■以輸入起飛抵達城市，查詢飛機航班情況：航班信息查詢系統(tǒng)：可以按：1.航班號；2.起點站；3.終點站；4.起飛時間：5.到達時間；以下選作：（3）航班訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班巳經無票，可以提供相關可選擇航班；（4）航班退票：可■退票，退票后修改相關數據文件；客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。（5）修改航班信息：當航班信息改變可以修改航班數據文件。注：因為航班號為兩位字母后跟數字，所以在排序時應該使用多關鍵字的基數排序對航班號進行排序。5、【商店存貨管理系統(tǒng)】功能：建立一商店存貨管理系統(tǒng)，要求每次出貨時取進貨時間最早旦最接近保質期中止時間的貨物。分步實施：初步完成總體設計，搭好框架，確定人機對話的界面，確定函數個數：完成最低要求：建立一個文件，包括5個種類的貨物情況，能對商品信息進行擴充（追加）,修改和刪除以及簡單的排序；進一步要求：擴充商品數量，以及完成系統(tǒng)查詢功能。有興趣的同學可以自己擴充系統(tǒng)功能。6、【中國道路交通網絡信息查詢系統(tǒng)（****）】【問題描述】出于不同的目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可■能省，而老年旅客則要求中轉次數最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。【基本要求】（1）提供對城市信息進行編輯（如：添加或刪除）的功能。（2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到這或最省錢到達。全程只考慮一種交通工具：（4）旅途中耗費的總時間應該包括中轉站的等候時間；（5）咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地?！緶y試數據】參考《數據結構》清華版7.6節(jié)圖7.33的全國交通圖，自行設計列車時刻表和飛機航班?！緦崿F提示】（1）對時刻表和飛機航班進行編輯，應提供文件輸入和鍵盤輸入兩種形式。飛機航班信息包括:起始站的出發(fā)時間，終點站的到達時間和票價;列車時刻表則需根據交通圖給出各個路段的詳細信息，如:對從北京到上海的火車,給出北京至天津，天津至徐州及徐州至上海各段的出發(fā)時間，到達時間及票價等信息。（2）以鄰接表作交通圖的存儲結構，表示邊的結構內除含有鄰接點的信息外，還包括交通工具,路途中耗費的時間和花費以及出發(fā)和到達時間等多種屬性?！具x做內容】增加旅途中中轉次數最少的最優(yōu)決策二、作業(yè)提交上交相關內容要求:以班為單位刻盤,并在盤面標明班級名稱，如：計科1301?每個同學上交成果的內容必須由以下兩大部分組成，缺一不可（一）電子版：每個同學建立一個文件夾。?文件夾名禾爾為：學號（兩位）-姓名-課題名稱：?文件夾I法a容：包含下面3個內容。1、上交源程序：學生按照課程實踐的具體要求所開發(fā)的所有源程序（應該放到一個文件夾中，文件夾名稱：姓名-課題名稱，如：張三-學生成績管理）；2、上交程序的說明文件：（保存在.txt中）在說明文檔中應該寫明上交程序所在的目錄,上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；3、課程實踐報告：（保存在word文檔中，文件名要求按照”姓名-**課程實踐報告”）報告按所給樣例完成，樣例見文件后邊。（二）紙質版：課程設計報告A4打印一份，封面由學委統(tǒng)一監(jiān)督打印，全班保持封面格式一致。提交日期：2015年9月16日下午4點，學委交到教師備課室教師辦公桌。每推遲提交報告一天，扣5分。三、考核評分上機情況30%+實踐報告70%1、上機情況（30%）包括出勤情況、調試表現、是否上網、玩游戲。一次扣10分。2、實踐報告（70%）見詳細評分標準。附件一:《數據結構》

綜合實踐報告評分標準TOC\o"1-5"\h\z1、內容完整10分2、概要設計合理、明了20分3、詳細設計思路清晰、內容完善40分4、調試分析過程認真、合理10分5、測試結果正確合理10分6、實踐總結深刻10分共計100分以上內容可以在評分標準內按所做系統(tǒng)實際情況酌情給分。附件二:《數據結構》

綜合實踐報告學院：班級：學號：姓名：課題名稱：指導教師：完成日期：1.實踐題目編制一個演示單鏈表插入、刪除、查找等操作的程序需求分析本演示程序用vc編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元素在單鏈表中的位置。輸入的形式和輸入值的范圍：插入元素時需要輸入插入的位置和元素的值；刪除元素時輸入刪除元素的位置；查找操作時需要輸入元素的值。在所有輸入中，元素的值都是整數輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內容。其中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。程序所能達到的功能：完成單鏈表的生成(通過插入操作)、插入、刪除、查找操作測試數據：插入操作中依次輸入11,12,13,14,15,16,生成一個單鏈表查找操作中依次輸入12,15,22返回這3個元素在單鏈表中的位置刪除操作中依次輸入2,5,刪除位于2和5的元素概要設計為了實現上述程序功能，需要定義單鏈表的抽象數據類型：ADTLinkList{數據對象：D={ai|aieintegerSetzi=0,l/2,...znzn>0}數據關系：R={<ai,ai+l>|ai,ai+leD}基本操作：InitLinkList(&L)操作結果：構造一個空的單鏈表L.InsLinkList(&Lzpos,e)初始條件：單鏈表L己存在操作結果：將元素e插入到單鏈表L的pos位置DelLinkList(&L,pos,&e)初始條件：單鏈表L己存在操作結果：將單鏈表L中pos位置的元素刪除，元素值置入e中返回LocLinkList(Lze)初始條件：單鏈表L依存在操作結果：單鏈表L中查找是否元素e,若存在，返回元素在表中的位置；若不存在，返回-1.Menu()操作結果：在屏幕上顯示操作菜單

本程序包含7個函數：主函數main()初始化單鏈表函數InitLinkListO顯示操作菜單函數menu()顯示單鏈表內容函數dispLinkList()插入元素函數InsLinkList()刪除元素函數DelLinkList()查找元素函數LocLinkList()各函數間關系如下：mainInitLinkListMenumainInitLinkListMenuDispLinkListInsLinkListDelLinkListLocLinkList4.詳細設計對主程序和其他模實現概要設計中定義的所有的數據類型，對每個操作給出偽碼算法。塊也都需要寫出偽碼算法。對主程序和其他模結點類型和指針類型typedefstructnode〈intdata;structnode*next;}Node,*LinkListl;單鏈表的基本操作為了方便，在單鏈表中設頭結點，其data域沒有意義。boolInitLinkList(LinkList&L)(偽碼算法)voidDispLinkList(LinkListL)(偽碼算法)voidmenu()(偽碼算法)boolInsLinkList(LinkList&L,intposjnte)(偽碼算法)boolDelLinkList(LinkList&L,intposjnt&e)(偽碼算法)intLocLinkList(LinkListLzinte)(偽碼算法)其他模塊偽碼算法調試分析調試過程中所做的工作，時間復雜度等分析。使用說明程序名為LinkList.exe,運行環(huán)境為DOS。程序執(zhí)行后顯示0—-EXIT-INSERT—DELETE-LOCATESELECT:在select后輸入數字選擇執(zhí)行不同的功能。要求首先輸入足夠多的插入元素，才可?以進行其他的操作。每執(zhí)行一次功能，就會顯示執(zhí)行的結果(正確或錯誤