一、實驗目的
1．了解特殊矩陣壓縮儲存的實現原理；
2．掌握稀疏矩陣壓縮儲存的兩種常用方式：三元組表和十字鍊錶。
3．掌握矩陣壓縮相關的基本運算：壓縮、解壓、轉置、加法、乘法等。
二、實驗內容
本次實驗，請從下面三種稀疏矩陣的壓縮儲存方式中任選一種實現矩陣的壓縮儲存及相關操作的實現。
1．壓縮矩陣的三元組表儲存方式
（1）定義三元組表儲存結構；
（2）矩陣的壓縮：將稀疏矩陣轉換為三元組表儲存；
（3）矩陣的轉置：將三元組表儲存的壓縮矩陣進行轉置，轉置後矩陣仍然用三元組表儲存，請編寫一般轉置演算法和快速轉置演算法；
（4）遍歷三元組表：輸出矩陣的行數、列數和非0元個數，以及三元組表中儲存的三元組（行號、列號、非0元素的值）；
（5）矩陣解壓：將三元組表表示的壓縮矩陣還原為未壓縮的矩陣，並在螢幕上輸出。
2．壓縮矩陣的十字鍊錶儲存方式
（1）定義十字鍊錶儲存結構；
（2）矩陣的壓縮：將稀疏矩陣轉換為十字鍊錶儲存；
（3）矩陣的轉置：將十字鍊錶儲存的壓縮矩陣進行轉置，轉置後矩陣仍然用十字鍊錶儲存；
（4）遍歷十字鍊錶：輸出矩陣的行數、列數和非0元個數，並輸出十字鍊錶中儲存的資料（行號、列號、非0元素的值），可按行優先方式依次輸出；
（5）矩陣解壓：將十字鍊錶表示的壓縮矩陣還原為未壓縮的矩陣，並在螢幕上輸出。
3．壓縮矩陣的一維線性儲存方式
假設稀疏矩陣只存放其非0元素的行號、列號和數值，以一維陣列順次存放，行號為-1表示結束。例如：如下所示的稀疏矩陣m
可壓縮儲存在一維陣列d中：
（1）一維線性儲存方式儲存結構的定義；
（2）矩陣的壓縮：將稀疏矩陣轉換為一維陣列儲存，另外，還要儲存矩陣的行數、列數和非0元個數；
（3）矩陣的加法：假設有兩個稀疏矩陣a和b，它們均為m行n列，分別壓縮儲存在一維陣列a和b中，編寫求矩陣加法c=a+b的演算法，矩陣c也用一維陣列壓縮儲存；
（4）遍歷線性表：輸出矩陣的行數、列數和非0元個數，並輸出一維陣列中儲存的資料（行號、列號、非0元素的值），可按行優先方式依次輸出；
（5）矩陣解壓：將一維陣列表示的壓縮矩陣還原為未壓縮的矩陣，並在螢幕上輸出；
（6）矩陣的轉置：對用一維陣列儲存的二維稀疏矩陣進行轉置操作，轉置結果也用一維陣列儲存。（選做）
三、實驗要求
1．壓縮前的稀疏矩陣儲存在乙個文字檔案中，包括矩陣的行號、列號和矩陣中所有的元素。壓縮後的矩陣存入另乙個檔案，也要包括完整資訊。
2．編寫完整程式實現稀疏矩陣的相關操作。要求操作介面友好，採用選單式操作。
3．分析所程式設計序中每乙個演算法（函式）的時間複雜度。
4．撰寫實驗報告，並簡要給出演算法設計小結和心得。
資料結構實驗指導書
第一部分課程概述 資料結構是計算機程式設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已成為其它立功專業的熱門選修課。資料結構實驗可以使學生對資料結構課程所教授的內容通過實驗環節加以實踐，提高學生的程式設計 編寫及除錯能力，是一門基礎的實驗課程。第二部分實驗要求 通過實驗，學生對常用資料結...
資料結構實驗指導書
實驗名稱資料結構試驗 課程名稱資料結構 專業班級學生姓名 學號成績 指導老師實驗日期 2010年3月 5月 實驗報告如列印，紙張用a4，左裝訂 頁邊距 上下2.5cm，左2.5cm，右2.0cm 字型 字型小四號，1.25倍行距。驗證性 綜合性實驗報告應包含的主要內容 一 實驗目的及要求 1 實驗目...
資料結構實驗指導書
山東大學軟體學院 資料結構 演算法與應用 實驗指導書 一 實驗要求 1 採用良好的程式設計風格 關鍵操作要有注釋。2 程式能夠執行，顯示執行結果。二 開發工具 microsoft visual c eclipse ide for c 三 實驗時間 地點 一 實驗目的 1 熟悉開發工具的使用。2 掌握...