\"本書是數據結構課程的輔助教材，采用C和C++兩種語言來描述數據結構，讓學生在實驗與習題中體會與掌握數據結構，同時培養編程能力和分析能力。主要內容包括實驗與習題兩大部分，用於鞏固數據結構的理論知識，提高實踐應用能力。 本書內容立足於高校教學的要求，適用於本科院校的課程和學生群體，可作為數據結構與算法課程的輔助教材，也可作為初學數據結構讀者的自學讀物。 \"

\"本書是數據結構課程的輔助教材，采用C和C++兩種語言來描述數據結構，讓學生在實驗與習題中體會與掌握數據結構，同時培養編程能力和分析能力。主要內容包括實驗與習題兩大部分，用於鞏固數據結構的理論知識，提高實踐應用能力。 本書內容立足於高校教學的要求，適用於本科院校的課程和學生群體，可作為數據結構與算法課程的輔助教材，也可作為初學數據結構讀者的自學讀物。\"

**部分 實驗要求及規範
第2部分 面向過程語言實現數據結構
實驗0 復數ADT及其實現
實驗1 線性表(順序表
實驗2 線性表(鏈表
實驗3 棧
實驗4 隊列
實驗5 串與數組
實驗6 樹與二叉樹
實驗7 圖
實驗8 查找
實驗9 排序
第3部分 面向對像語言實現數據結構
實驗0 復數ADT——C++實現
實驗1 線性表(順序表)——C++實現
實驗2 線性表(鏈表)——C++實現
實驗3 棧——C++實現
實驗4 隊列——C++實現
實驗5 串與數組——C++實現
實驗6 二叉樹的遍歷——C++實現
實驗7 圖——C++實現
實驗8 查找——C++實現
實驗9 內部排序——C++實現
第4部分 習題與部分參考答案
習題1 緒論
習題2 線性表
習題3 棧和隊列
習題4 串
習題5 數組和廣義表
習題6 樹和二叉樹
習題7 圖
習題8 查找
習題9 排序
參考文獻

第3部分面向對像語言實現數據結構 本部分實驗指導是為已經學習過C++語言的學生而編寫。編寫實驗指導的目的是為了配合理論教學。程序要求在Visual C++或者C++ Builder開發環境之下調試運行,采用面向對像方法進行設計。典型的數據結構被設計成為類(class),典型算法設計成為類的函數成員,然後在主函數中聲明創建類對像,根據實際需要調用重要的算法。
由於C++的使用具有一定的難度,為了*好地學習數據結構自身的知識內容,克服描述工具所帶來的困難,這裡針對數據結構上機實驗所必需的C++基本知識(結構體、類等等)做補充介紹。
1. 源程序組成 這部分內容參見本指導書的程序實例。
2. 結構體及運用 數據結構課程所研究的問題均運用到“結構體”和“類”。在C++語言中,結構體和函數又是理解和掌握“類”的語法基礎。定義結構體的一般格式: struct 結構體類型名 {類型名1 變量名1;//數據子域 類型名2 變量名2;  類型名n 變量名n; }其中,struct是保留字。結構體類型名由用戶自己命名。在使用時必須聲明一個具體的結構體類型的變量,聲明創建一個結構體變量的方法是: 結構體類型名結構體變量名;一個結構體中可以包含多個數據子域。數據子域的類型名一般指基本數據類型(int char 等),也可以是已經定義的另一結構體名。數據子域變量名可以是簡單變量,也可以是數組。它們也可以稱為結構體的數據成員,其訪問控制具有“公有”屬性。
(1) 通過“結構體變量名.數據子域” 可以訪問數據子域。// 設計Student結構體,在主程序中運用。
#include #include #include struct Student//定義結構體Student {longnum; //學號 int x;//成績 charname\\[10\\]; //姓名 } int main( ) { Student s1;//聲明創建一個結構體變量s1 //為s1的數據子域提供數據 s1.num=1001 ; s1. x=83; strcpy( s1.name, \" 李明\"); //輸出結構體變量s1 的內容 cout<< \"姓名: \"<< s1.name <>a\\[i\\].num;//輸入數組元素a\\[i\\]的學號域 cout<<\"姓名:\"; cin>> a\\[i\\].name;//輸入數組元素a\\[i\\]的姓名域 cout<<\"成績:\"; cin>>a\\[i\\].x;//輸入數組元素a\\[i\\]的成績域 }以上是關於結構體的基本概念和簡單運用。
數組a有5個數組元素,每個數組元素都是Student結構體類型。數組a的存儲結構如下: 3. 類的基本概念及運用 類是面向對像程序的基本單位。類由數據成員和相關的函數成員組成。從面向對像的角度考慮“學生”這個類,它不僅包括“學生”的一般屬性(學號、姓名、成績等),還應包括對於這些屬性的操作(輸入輸出、聽課、實驗等)。 類定義的一般格式: class類名 {若干數據成員; 若干函數成員; };類的數據成員和函數成員均存在訪問控制權限問題。訪問控制分為3種: 公有(public)、私有(private)和受保護(protected)。
數據成員的定義和結構體中的數據域定義是相似的。不同的是,它們必須明確訪問控制。而公有數據成員,可以認為與結構體的數據域的訪問權限相同。
成員函數的定義與一般函數的定義基本相同。不同的是,類中成員函數也必須明確訪問控制權限。如果在類之中定義成員函數帶函數體,並沒有什麼特殊之處。如果在類之中僅有成員函數的原型聲明,那麼當在類定義之外定義函數體時,需要加上類限定標識“類名: : ”。下面是“學生”類的定義: class Students//定義類結構體Students {private: //私有數據成員 longnum;//學號 int x; //成績 charname\\[10\\];//姓名 public: //公有成員函數 Students( ); Students ( long n, int x0, char na0 ) { num=n;x=x0;strcpy( name,na0);} ~Students( ) { }; void SetDat( long n, int x0, char na0 ) { num=n;x=x0;strcpy( name,na0); } void PrintOut( );//輸出函數的原型聲明 //其他函數…; }; voidStudents::PrintOut( )//輸出函數前加Students:: {cout<< \" 姓名: \"<< name <>m>>y>>xname; s. SetDat( m, y, xname ) ;//修改對像s的數據 s. PrintOut( );//輸出改變後s的內容 Studentsw(1002, 85, \"LiHua\") s; //聲明創建一個類對像w,調用有參構造函數 w. PrintOut( ); //輸出對像w的內容 _getch( ); return 0; }運行結果: 姓名:O 學號:0 成績:0 輸入學號,成績,姓名: 1001 90 WangMing 姓名:WangMing 學號:1001 成績:90 姓名:LiHua 學號:1002 成績:85通過上面兩個類對像的圖示,可以了解它們的內部數據情況。
對像s的數據是通過鍵盤輸入,再經由s. SetDat( m, y, xname ) 這個公有函數的運行,提供給對像s的私有數據成員。
而對像w的數據是通過Studentsw(1002, 85, \"LiHua\") s;聲明創建對像w時自動調用構造(有形參的)函數,將實參數據提供給對像w的私有數據成員。
這個例題中的數據成員全部定義為私有(private),以便保證數據安全性。
而函數成員全部定義為公有(public)成員函數,可以作為類對外部的接口。通過s. SetDat( m, y, xname ) 直接訪問公有函數成員SetDat( ), 將實參(主函數的局部變量m、y、xname)的數據賦值給類的私有數據成員num、x、name。通過 s.PrintOut( )直接訪問公有函數成員PrintOut( ),由它間接訪問和輸出私有數據成員num、x、name。
在面向對像的程序設計中,正確理解構造函數的作用是**重要的。
在主函數中,語句“Students s;”的作用是自動調用無參構造函數,聲明創建一個類對像s。主函數中倒數第3行語句“Students w (1002, 85, \"LiHua\")s;”的作用是自動調用帶有形參的構造函數,聲明創建一個類對像w。而語句“w. PrintOut();”的作用是輸出對像w的數據內容。