2015數(shù)據(jù)結(jié)構(gòu)實踐題目計科13級

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

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

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

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