數(shù)據結構實驗.doc

數(shù)據結構實驗指導書計算機學院數(shù)據結構課程組2007-9前言計算機編程中加工處理的對象是數(shù)據，而數(shù)據具有一定的組織結構，所以學習計算機編程僅僅了解計算機語言是不夠的，還必須掌握數(shù)據的組織、存儲和運算的一般方法，這便是數(shù)據結構課程中所研究的內容，也是我們編寫計算機程序的重要基礎，由于它對計算機學科起到承前啟后的作用，因此本課程被列為計算機等相關專業(yè)最重要的專業(yè)基礎課；同時數(shù)據結構是計算機專業(yè)教學的一門核心課程。計算機各領域都要用到各種數(shù)據結構，而且要從事計算機科學與技術工作，尤其是計算機領域的軟件開發(fā)工作，必須具備較強的數(shù)據結構基礎。數(shù)據結構課程內容豐富、學習量大，實踐性強；隱含在各部分內容中的方法和技術多；算法設計具有動態(tài)性和抽象性等特點，看懂聽明白與掌握會應用之間有相當大的一段距離。所以學生必須多實踐才能進一步加深對課程的理解，理解和掌握算法設計所需的方法和技術，為整個專業(yè)學習打下良好的基礎。實驗一 線性表的基本操作及其應用一、實驗目的1、幫助讀者復習C+語言程序設計中的知識。2、熟悉線性表的邏輯結構。3、熟悉線性表的基本運算在兩種存儲結構上的實現(xiàn)，其中以熟悉鏈表的操作為側重點。二、實驗內容本次實驗提供3個題目，每個題目都標有難度系數(shù)，*越多難度越大，學生可以根據自己的情況任選一個！題目一：單鏈表的基本操作（*）問題描述實現(xiàn)帶頭結點的單鏈表的建立、求長度，取元素、修改元素、插入、刪除等單鏈表的基本操作?；疽螅?）依次從鍵盤讀入數(shù)據，建立帶頭結點的單鏈表； （2）輸出單鏈表中的數(shù)據元素（3）求單鏈表的長度；（4）根據指定條件能夠取元素和修改元素；（5）實現(xiàn)在指定位置插入和刪除元素的功能。 測試數(shù)據由學生任意指定。題目二：約瑟夫環(huán)（*）問題描述約瑟夫（Joseph）問題的一種描述是：編號為1,2,n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有人全部出列為止。試設計一個程序求出出列順序。基本要求利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序印出各人的編號。測試數(shù)據由學生任意指定。如：m的初值為20；n的值為7；密碼：3，1，7，2，4，8，4；（正確的輸出結果應為6，1，4，7，2，3，5）。 (報告上要求寫出多批數(shù)據測試結果)實現(xiàn)提示程序運行后首先要求用戶輸入初始報數(shù)上限值m，人數(shù)n,(設n30)。然后輸入各人的密碼。選作內容向上述程序中添加在順序結構上實現(xiàn)的部分。題目三：多項式的表示及相加（*）問題描述設計一個算法，以實現(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ù)據由學生任意指定。實現(xiàn)提示用帶表頭結點的單鏈表存儲多項式。選作內容多項式a和b相減，建立多項式a-b。三、實驗前的準備工作1、掌握線性表的邏輯結構。2、掌握線性表的鏈式存儲結構。3、熟練掌握線性表的插入、刪除等操作。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據的運行結果。3、結合運行結果，對程序進行分析。實驗二 棧和隊列的基本操作及其應用一、實驗目的1、掌握棧和隊列的順序存儲結構和鏈式存儲結構，以便在實際中靈活應用。2、掌握棧和隊列的特點，即后進先出和先進先出的原則。3、掌握棧和隊列的基本運算，如：入棧與出棧，入隊與出隊等運算在順序存儲結構和鏈式存儲結構上的實現(xiàn)。二、實驗內容本次實驗提供2個題目，每個題目都標有難度系數(shù)，*越多難度越大，學生可以根據自己的情況任選一個！題目一：回文判斷（*）問題描述對于一個從鍵盤輸入的字符串，判斷其是否為回文?；匚募凑葱蛳嗤Ｈ纭癮bba”是回文，而“abab”不是回文?；疽螅?）數(shù)據從鍵盤讀入；（2）輸出要判斷的字符串； （3）利用棧的基本操作對給定的字符串判斷其是否是回文，若是則輸出“Yes”，否則輸出“No”。測試數(shù)據由學生任意指定。題目二：商品貨架管理（*）問題描述商店貨架以棧的方式擺放商品。生產日期越近的越靠近棧底，出貨時從棧頂取貨。一天營業(yè)結束，如果貨架不滿，則需上貨。入貨直接將商品擺放到貨架上，則會使生產日期越近的商品越靠近棧頂。這樣就需要倒貨架，使生產日期越近的越靠近棧底。基本要求設計一個算法，保證每一次上貨后始終保持生產日期越近的商品越靠近棧底。實現(xiàn)提示可以用一個隊列和一個臨時棧作為周轉。測試數(shù)據由學生任意指定。三、實驗前的準備工作1、掌握棧的邏輯結構和存儲結構。2、熟練掌握棧的出棧、入棧等操作。3、掌握隊列的邏輯結構和存儲結構。4、熟練掌握隊列的出隊、入隊等操作四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據的運行結果。3、結合運行結果，對程序進行分析。題目三：Rails（ACM訓練題）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訓練題）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實驗三 二叉樹的基本運算一、實驗目的1、使學生熟練掌握二叉樹的邏輯結構和存儲結構。2、熟練掌握二叉樹的各種遍歷算法。二、實驗內容問題描述建立一棵二叉樹，試編程實現(xiàn)二叉樹的如下基本操作：1. 按先序序列構造一棵二叉鏈表表示的二叉樹T；2. 對這棵二叉樹進行遍歷：先序、中序、后序以及層次遍歷，分別輸出結點的遍歷序列；3. 求二叉樹的深度/結點數(shù)目/葉結點數(shù)目；(選做)4. 將二叉樹每個結點的左右子樹交換位置。（選做） 基本要求從鍵盤接受輸入（先序），以二叉鏈表作為存儲結構，建立二叉樹（以先序來建立），測試數(shù)據如輸入：ABCDEGF（其中表示空格字符）則輸出結果為 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA層序：ABCDEFG選作內容采用非遞歸算法實現(xiàn)二叉樹遍歷。三、實驗前的準備工作1、掌握樹的邏輯結構。2、掌握二叉樹的邏輯結構和存儲結構。3、掌握二叉樹的各種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據的運行結果。3、結合運行結果，對程序進行分析。實驗四 哈夫曼樹與哈夫曼編碼一、實驗目的1、使學生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內容問題描述已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。基本要求1. 初始化：從鍵盤讀入n個字符，以及它們的權值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）2. 編碼：根據建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進行編碼。選作內容. 譯碼：利用已經建立好的Huffman樹，對上面的編碼結果譯碼。譯碼的過程是分解電文中的字符串，從根結點出發(fā)，按字符0和1確定找左孩子或右孩子，直至葉結點，便求得該子串相應的字符。4. 打印Huffman樹。測試數(shù)據利用教材P.148 例62中的數(shù)據調試程序。可設8種符號分別為A,B,C,D,E,F,G,H。編/譯碼序列為 “CFBABBFHGH”(也可自己設定數(shù)據進行測試)。三、實驗前的準備工作1、掌握樹的邏輯結構。2、掌握哈夫曼樹的定義及生成算法。3、掌握哈夫曼編碼的方法。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據的運行結果。3、結合運行結果，對程序進行分析。實驗五 圖的基本操作一、實驗目的1、使學生可以鞏固所學的有關圖的基本知識。2、熟練掌握圖的存儲結構。3、熟練掌握圖的兩種遍歷算法。二、實驗內容問題描述對給定圖，實現(xiàn)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。基本要求以鄰接表為存儲結構，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結點為起點，分別輸出每種遍歷下的結點訪問序列?！緶y試數(shù)據】由學生依據軟件工程的測試技術自己確定。三、實驗前的準備工作1、掌握圖的相關概念。2、掌握圖的邏輯結構和存儲結構。3、掌握圖的兩種遍歷算法的實現(xiàn)。四、實驗報告要求1、實驗報告要按照實驗報告格式規(guī)范書寫。2、實驗上要寫出多批測試數(shù)據的運行結果。3、結合運行結果，對程序進行分析。實驗六 圖的應用一、實驗目的1、使學生可以鞏固所學的有關圖的基本知識。2、熟練掌握圖的存儲結構。3、掌握如何應用圖解決各種實際問題。二、實驗內容本次實驗提供2個題目，學生可以任選一個！題目一：最小生成樹問題問題描述若要在n個城市之間建設通信網絡，只需要假設n-1條線路即可。如何以最低的經濟代價建設這個通信網，是一個網的最小生成樹問題。基本要求1 利用克魯斯卡爾算法求網的最小生成樹。2 要求輸出各條邊及它們的權值。實現(xiàn)提示通信線路一旦建成，必然是雙向的。因此，構造最小生成樹的網一定是無向網。設圖的頂點數(shù)不超過30個，并為簡單起見，網中邊的權值設成小于100的整數(shù)。圖的存儲結構的選取應和所作操作相適應。為了便于選擇權值最小的邊，此題的存儲結構既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲邊（帶權）的數(shù)