數(shù)據(jù)結(jié)構(gòu)實驗.doc

數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書計算機學(xué)院數(shù)據(jù)結(jié)構(gòu)課程組2007-9前言計算機編程中加工處理的對象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)計算機編程僅僅了解計算機語言是不夠的，還必須掌握數(shù)據(jù)的組織、存儲和運算的一般方法，這便是數(shù)據(jù)結(jié)構(gòu)課程中所研究的內(nèi)容，也是我們編寫計算機程序的重要基礎(chǔ)，由于它對計算機學(xué)科起到承前啟后的作用，因此本課程被列為計算機等相關(guān)專業(yè)最重要的專業(yè)基礎(chǔ)課；同時數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)教學(xué)的一門核心課程。計算機各領(lǐng)域都要用到各種數(shù)據(jù)結(jié)構(gòu)，而且要從事計算機科學(xué)與技術(shù)工作，尤其是計算機領(lǐng)域的軟件開發(fā)工作，必須具備較強的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容豐富、學(xué)習(xí)量大，實踐性強；隱含在各部分內(nèi)容中的方法和技術(shù)多；算法設(shè)計具有動態(tài)性和抽象性等特點，看懂聽明白與掌握會應(yīng)用之間有相當(dāng)大的一段距離。所以學(xué)生必須多實踐才能進一步加深對課程的理解，理解和掌握算法設(shè)計所需的方法和技術(shù)，為整個專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。實驗一 線性表的基本操作及其應(yīng)用一、實驗?zāi)康?、幫助讀者復(fù)習(xí)C+語言程序設(shè)計中的知識。2、熟悉線性表的邏輯結(jié)構(gòu)。3、熟悉線性表的基本運算在兩種存儲結(jié)構(gòu)上的實現(xiàn)，其中以熟悉鏈表的操作為側(cè)重點。二、實驗內(nèi)容本次實驗提供3個題目，每個題目都標(biāo)有難度系數(shù)，*越多難度越大，學(xué)生可以根據(jù)自己的情況任選一個！題目一：單鏈表的基本操作（*）問題描述實現(xiàn)帶頭結(jié)點的單鏈表的建立、求長度，取元素、修改元素、插入、刪除等單鏈表的基本操作?；疽螅?）依次從鍵盤讀入數(shù)據(jù)，建立帶頭結(jié)點的單鏈表； （2）輸出單鏈表中的數(shù)據(jù)元素（3）求單鏈表的長度；（4）根據(jù)指定條件能夠取元素和修改元素；（5）實現(xiàn)在指定位置插入和刪除元素的功能。 測試數(shù)據(jù)由學(xué)生任意指定。題目二：約瑟夫環(huán)（*）問題描述約瑟夫（Joseph）問題的一種描述是：編號為1,2,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計一個程序求出出列順序?；疽罄脝蜗蜓h(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。測試數(shù)據(jù)由學(xué)生任意指定。如：m的初值為20；n的值為7；密碼：3，1，7，2，4，8，4；（正確的輸出結(jié)果應(yīng)為6，1，4，7，2，3，5）。 (報告上要求寫出多批數(shù)據(jù)測試結(jié)果)實現(xiàn)提示程序運行后首先要求用戶輸入初始報數(shù)上限值m，人數(shù)n,(設(shè)n30)。然后輸入各人的密碼。選作內(nèi)容向上述程序中添加在順序結(jié)構(gòu)上實現(xiàn)的部分。題目三：多項式的表示及相加（*）問題描述設(shè)計一個算法，以實現(xiàn)一元稀疏多項式的加法運算?；疽螅?）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2，cn，en，其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；（3）多項式a和b相加，建立多項式a+b。測試數(shù)據(jù)由學(xué)生任意指定。實現(xiàn)提示用帶表頭結(jié)點的單鏈表存儲多項式。選作內(nèi)容多項式a和b相減，建立多項式a-b。三、實驗前的準(zhǔn)備工作1、掌握線性表的邏輯結(jié)構(gòu)。2、掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。3、熟練掌握線性表的插入、刪除等操作。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。實驗二 棧和隊列的基本操作及其應(yīng)用一、實驗?zāi)康?、掌握棧和隊列的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，以便在實際中靈活應(yīng)用。2、掌握棧和隊列的特點，即后進先出和先進先出的原則。3、掌握棧和隊列的基本運算，如：入棧與出棧，入隊與出隊等運算在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)。二、實驗內(nèi)容本次實驗提供2個題目，每個題目都標(biāo)有難度系數(shù)，*越多難度越大，學(xué)生可以根據(jù)自己的情況任選一個！題目一：回文判斷（*）問題描述對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤?。如“abba”是回文，而“abab”不是回文?；疽螅?）數(shù)據(jù)從鍵盤讀入；（2）輸出要判斷的字符串； （3）利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。測試數(shù)據(jù)由學(xué)生任意指定。題目二：商品貨架管理（*）問題描述商店貨架以棧的方式擺放商品。生產(chǎn)日期越近的越靠近棧底，出貨時從棧頂取貨。一天營業(yè)結(jié)束，如果貨架不滿，則需上貨。入貨直接將商品擺放到貨架上，則會使生產(chǎn)日期越近的商品越靠近棧頂。這樣就需要倒貨架，使生產(chǎn)日期越近的越靠近棧底?；疽笤O(shè)計一個算法，保證每一次上貨后始終保持生產(chǎn)日期越近的商品越靠近棧底。實現(xiàn)提示可以用一個隊列和一個臨時棧作為周轉(zhuǎn)。測試數(shù)據(jù)由學(xué)生任意指定。三、實驗前的準(zhǔn)備工作1、掌握棧的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。2、熟練掌握棧的出棧、入棧等操作。3、掌握隊列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。4、熟練掌握隊列的出隊、入隊等操作四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。題目三：Rails（ACM訓(xùn)練題）DescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track. The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N = 1000 coaches numbered in increasing order 1, 2, ., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station. InputThe input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ., N. The last line of the block contains just 0. The last block consists of just one line containing 0. OutputThe output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last null block of the input. Sample Input51 2 3 4 55 4 1 2 3066 5 4 3 2 100Sample OutputYesNoYes題目四： Sliding Window（ACM訓(xùn)練題）DescriptionAn array of size n 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is 13-1-35367, and k is 3. Window positionMinimum valueMaximum value13-1-35367-1313-1-35367-3313-1-35367-3513-1-35367-3513-1-353673613-1-3536737Your task is to determine the maximum and minimum values in the sliding window at each position. InputThe input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line. OutputThere are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values. Sample Input8 31 3 -1 -3 5 3 6 7Sample Output-1 -3 -3 -3 3 33 3 5 5 6 7實驗三 二叉樹的基本運算一、實驗?zāi)康?、使學(xué)生熟練掌握二叉樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。2、熟練掌握二叉樹的各種遍歷算法。二、實驗內(nèi)容問題描述建立一棵二叉樹，試編程實現(xiàn)二叉樹的如下基本操作：1. 按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；2. 對這棵二叉樹進行遍歷：先序、中序、后序以及層次遍歷，分別輸出結(jié)點的遍歷序列；3. 求二叉樹的深度/結(jié)點數(shù)目/葉結(jié)點數(shù)目；(選做)4. 將二叉樹每個結(jié)點的左右子樹交換位置。（選做） 基本要求從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），測試數(shù)據(jù)如輸入：ABCDEGF（其中表示空格字符）則輸出結(jié)果為 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG選作內(nèi)容采用非遞歸算法實現(xiàn)二叉樹遍歷。三、實驗前的準(zhǔn)備工作1、掌握樹的邏輯結(jié)構(gòu)。2、掌握二叉樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。3、掌握二叉樹的各種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。實驗四 哈夫曼樹與哈夫曼編碼一、實驗?zāi)康?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內(nèi)容問題描述已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼?；疽?. 初始化：從鍵盤讀入n個字符，以及它們的權(quán)值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）2. 編碼：根據(jù)建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進行編碼。選作內(nèi)容. 譯碼：利用已經(jīng)建立好的Huffman樹，對上面的編碼結(jié)果譯碼。譯碼的過程是分解電文中的字符串，從根結(jié)點出發(fā)，按字符0和1確定找左孩子或右孩子，直至葉結(jié)點，便求得該子串相應(yīng)的字符。4. 打印Huffman樹。測試數(shù)據(jù)利用教材P.148 例62中的數(shù)據(jù)調(diào)試程序?？稍O(shè)8種符號分別為A,B,C,D,E,F,G,H。編/譯碼序列為 “CFBABBFHGH”(也可自己設(shè)定數(shù)據(jù)進行測試)。三、實驗前的準(zhǔn)備工作1、掌握樹的邏輯結(jié)構(gòu)。2、掌握哈夫曼樹的定義及生成算法。3、掌握哈夫曼編碼的方法。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。實驗五 圖的基本操作一、實驗?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識。2、熟練掌握圖的存儲結(jié)構(gòu)。3、熟練掌握圖的兩種遍歷算法。二、實驗內(nèi)容問題描述對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷?；疽笠脏徑颖頌榇鎯Y(jié)構(gòu)，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列?！緶y試數(shù)據(jù)】由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。三、實驗前的準(zhǔn)備工作1、掌握圖的相關(guān)概念。2、掌握圖的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據(jù)的運行結(jié)果。3、結(jié)合運行結(jié)果，對程序進行分析。實驗六 圖的應(yīng)用一、實驗?zāi)康?、使學(xué)生可以鞏固所學(xué)的有關(guān)圖的基本知識。2、熟練掌握圖的存儲結(jié)構(gòu)。3、掌握如何應(yīng)用圖解決各種實際問題。二、實驗內(nèi)容本次實驗提供2個題目，學(xué)生可以任選一個！題目一：最小生成樹問題問題描述若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)，是一個網(wǎng)的最小生成樹問題?；疽? 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。2 要求輸出各條邊及它們的權(quán)值。實現(xiàn)提示通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點數(shù)不超過30個，并為簡單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)。圖的存儲結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲邊（帶權(quán)）的數(shù)