了得網計算機/網絡_數據結構與算法實驗指導書

產品特色

編輯推薦

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

內容簡介

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

目錄
第1部分實驗要求及規範1第2部分面向過程語言實現數據結構3
實驗0復數ADT及其實現3
實驗1線性表(順序表)4
實驗2線性表(鏈表)7
實驗3棧12
實驗4隊列15
實驗5串與數組20
實驗6樹與二叉樹24
實驗7圖27
實驗8查找31
實驗9排序35第3部分面向對像語言實現數據結構40
實驗0復數ADT——C 實現45

第1部分實驗要求及規範1第2部分面向過程語言實現數據結構3

實驗0復數ADT及其實現3

實驗1線性表(順序表)4

實驗2線性表(鏈表)7

實驗3棧12

實驗4隊列15

實驗5串與數組20

實驗6樹與二叉樹24

實驗7圖27

實驗8查找31

實驗9排序35第3部分面向對像語言實現數據結構40

實驗0復數ADT——C 實現45

實驗1線性表(順序表)——C 實現46

實驗2線性表(鏈表)——C 實現50

實驗3棧——C 實現52

實驗4隊列——C 實現57

實驗5串與數組——C 實現62

實驗6二叉樹的遍歷——C 實現68

實驗7圖——C 實現71

實驗8查找——C 實現73

實驗9內部排序——C 實現76第4部分習題與部分參考答案79

習題1緒論79

習題2線性表81

習題3棧和隊列85

習題4串88

習題5數組和廣義表89

習題6樹和二叉樹91

習題7圖99

習題8查找106

習題9排序109參考文獻113

前言

前言數據結構是計算機專業的核心課程,它從長期的程序設計實踐中提煉而成,運用於程序設計;更是操作繫統、編譯原理等計算機核心課程的基礎,在計算機專業課程中起著承上啟下的作用。數據結構與算法的原理比較抽像,概念性強,難度大,不易掌握,但同時也具有較強的可應用性和實踐性。實驗是一個重要的教學環節,通過實現原理與算法,並將實驗結果反饋到原理與算法中去,有助於理解。各種數據結構以及相應算法的描述總是要選用一種語言工具。本書兼顧面向對像及面向過程兩種編程思想,采用了C語言和C 兩種語言來實現數據結構以及相應算法。本書分為四個部分: 部分緒論,要求學習者養成良好的實驗習慣;第二部分和第三部分分別采用C語言和C 語言來描述線性結構、棧、隊列、串與數組、樹與二叉樹、圖、查找和排序等數據結構及算法;第四部分為數據結構每章的習題練習。本書中所有算法的實現均通過實驗驗證可行。希望讀者通過本書的學習,能更加深入地理解和掌握數據結構的相關知識。由於編者水平有限,書中難免存在差錯,敬請廣大讀者批評指正。作者的電子郵箱地址: qinwang@126.com。
作者2018年3月

在線試讀

第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 iostream.h #include conio.h #include string.h 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 endl;cout "學號: " s1.num endl;cout "成績:" s1.x ednl;_getch( ); return 0;}(2) 設計一維數組,每素都是Student結構體類型,通過以下語句段可以說明結構體數組的一般用法: 通過“結構體數組名［下標］.數據子域”訪問數據域。Studenta\\[5\\]; //聲明創建一個結構體數組afor(inti=0, i 5, i ){ cout "學號:"; cin 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 endl;cout "學號: " num endl;cout "成績:" x endl; } 在主程序中運用類 Students。int main( ) {Students s;//聲明創建一個類對像s,調用無參構造函數s.PrintOut( ); //輸出s的內容longm;int y;charxname\\[10\\];cout " 輸入學號,成績,姓名:" ;cin 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的數據內容。4. 結構體在類中的使用1) 結構體數組做類的數據成員const int MAXSIZE=100; //數組的容量structElemType /素的類型{int numb; char name\\[20\\]; long tel;};class Sqlist { private:ElemTypeelem\\[MAXSIZE\\];//結構體類型的數組elem\\[ \\]做數據成員int length;public:Sqlist( void);~Sqlist( ){ };//其他函數};在上面這個類Sqlist之中,數組素elem［i］都不是簡單的數據類型,而是結構體ElemType的類型。那麼在輸入輸出時不能直接寫: cin elem［i］或cout elem［i］,而需要寫成: cin elem\\[i\\].numb; cin lelm\\[i\\].name;cin elem\\[I\\].tel;cout elem\\[i\\].numb;cout lelm\\[i\\].name; cout elem\\[I\\].tel;2) 結構體指針變量做類的數據成員struct NodeType//結點的結構定義{intdata;//數據域 NodeType next;//指針域};class Link //類聲明{ private:NodeTypeHead;//指向結構體NodeType的指針變量Head做數據成員 public:Link ( ){ Head=new NodeType;//為頭結點申請空間Head- next=Head; //頭結點Head 形成空環};~ Link ( ){ };voidcreat( );voidouts( );};在上面這個類Link之中,數據成員僅是一個指針,當為它申請和分配到一個結點的存儲空間之後,簡單的情況如上圖所示。在一般情況下可以構成連接多個數據結點的鏈表。實驗0復數ADT——C 實現〖*2〗1. 實驗目的(1) 本實驗是預備性實驗,可以機動掌握。(2) 了解抽像數據類型(ADT)的基本概念及描述方法。(3) 通過對復數抽像數據類型ADT的實現,熟悉C/C 語法及程序設計。為以後章節的學習打下基礎。2. 實例復數的抽像數據類型ADT面向對像程序設計的實現。［復數ADT的描述］ADT complex{ 數據對像:D={ c1,c2 c1,c2∈FloatSet }數據關繫:R={ c1,c2 c1為實部,c2為虛部的實繫數 }基本操作:創建一個復數creat(a);輸出一個復數outputc(a);求兩個復數相加之和add(a,b);求兩個復數相減之差sub(a,b);求兩個復數相乘之積chengji(a,b);等等;} ADT complex; ［復數ADT實現的面向對像源程序］#include iostream.h #include conio.h class Complex//定義結構體復數類型Complex { private:floatx; //實部floaty;//虛部public:Complex( ){}Complex(float x0,float y0){ x=x0; y=y0; }~Complex( ){}void outputc( ){ cout "復數: " x " i" y endl;} Complex operator (Complex k){ return Complex(k.x x,k.y y); }};int main( ){ Complex a1(1,2), a2(4,6),a3,a4,a5;a3=a1 a2;a3.outputc( );_getch( ); return 0;}3. 實習題首先將上面的源程序輸入計算機,進行調試。運行程序,輸入下列兩個復數的實部和虛部,記錄兩個復數相加的輸出結果。原始數據: 2.0 3.5i,3.0-6.3i 然後在上面程序的基礎上,增加自行設計的復數相減的子函數,適當補充必需的語句。再次調試運行程序。輸入數據,記錄結果,後完成實驗報告。實驗1線性表(順序表)——C 實現〖*2〗1. 實驗目的(1) 了解線性表的邏輯結構特性,以及這種特性在計算機內的順序存儲結構,通常稱為順序表。(2) 重點是線性表的基本操作在順序存儲結構上的實現,其中以插入和刪除的操作為側重點,並進一步學習結構化的程序設計方法。(3) 掌握使用 C 面向對像的程序設計技術,設計數據結構源程序的方法。2. 實例線性表的順序存儲表示(結構)及實現。閱讀下列程序請注意幾個問題。 源稱序結構: 見本書的第1部分。 數據結構類定義(包括成員函數的定義)的程序代碼。對於小型程序,這部分代碼可以直接放入源程序中。對於較復雜的程序,這部分代碼可以生成一個頭文件(如Sqlistc.h)與源程序文件存儲在同一個文件夾中。再在源程序之中寫入一個語句,如下: #include"Sqlistc.h"; 主函數。在學生沒有學習可視化圖形界面之前,建議在主函數中簡單設計一個“菜單”(dowhile循環內嵌套一個 switch結構)。隨著學習的深入,應該學會熟練使用“菜單”技術,這樣會明顯提高編程和運行效率。主函數的一般樣式如下: int main( ){ //聲明程序所需要的一般變量int i,k; ElemType e,x;//聲明和創建類對像,這個類往往是典型數據結構類 Sqlistas; cout "\\\
線性表順序存儲結構演示"; do{ //顯示菜單內容cout "\\\
\\\
;cout "\\\
\\\
1. 初步建立一個線性表 ";cout "\\\
\\\
2. 插入一素 ";cout "\\\
\\\
3. 刪素,返回其值";cout "\\\
\\\
4. 結束程序";cout "\\\
 ";cout "\\\
請輸入你的選擇(1,2,3,4)";cin k;//接收用戶的選擇//根據k值,轉向對應的case 分支程序段執行switch(k){ case 1:{as.SetData( ); as.PrintOut( ); }break;case 2:{ cout "\\\
插入的位置,數據 i,e=?"; cin i e; as.Insert(i,e);as.PrintOut( );}break;case 3:{cout "\\\
刪除素i=?";cin i;x=as.Delet(i); cout "\\\<素數值= " x;as.PrintOut( ); }break;default:break; } //switch }while(k =1 k 4);cout "\\\
再見!";cout "\\\
按任意鍵,返回。";_getch( ); return 0;}//-----------------------------------------------(1) 線性表順序存儲結構的本質是: 在邏輯上相鄰的兩素ai-1和ai,在存儲地址中也是相鄰的,即地址連續。順序存儲結構也稱“向量(vector)”。在下列類設計中,采用靜態一維數組elem［］表示向量,同時用length表示線性表長度。ElemTypeelem\\[MAXSIZE\\];int length;有時可以采用動態一維數組來表示向量。ElemTypeelem;int length;int MAXSIZE這就要求在類的構造函數中為其elem動態分配存儲空間,而在析構函數中釋放內存空間。在上機實驗時,需要將數據結構的類定義(包括成員函數的定義)的程序代碼,寫入源程序。同時用戶必須自己編寫一段主函數main( ),在主函數中創建聲明類的具體對像,通過這些對像調用類的公有函數,以便將一個典型數據結構類運用到實際問題中去。(2) 下面是一個完整的源程序,目的是提供一個示範,供參考。［使用線性表實現一個通訊錄］本程序的特點是:素的類型不再是簡單類型(int、char、float),而是更加接近實用的比較復雜的結構體類型。素輸入輸出時,情況復雜一些。#include iostream.h #include conio.h #include iomanip.h #include string.h //------------------------------------------------------------struct ElemType/素的類型 { int numb; char name\\[20\\]; long tel; };const int MAXSIZE=100; //數組的容量class Sqlist{ private:ElemTypeelem\\[MAXSIZE\\];int length;public:Sqlist( void);~Sqlist( ){ };voidSetData( );voidInsert( int i, ElemType e);ElemType Delet(int i);void PrintOut( );第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的數據內容。4. 結構體在類中的使用1) 結構體數組做類的數據成員const int MAXSIZE=100; //數組的容量structElemType /素的類型{int numb; char name\\[20\\]; long tel;};class Sqlist { private:ElemTypeelem\\[MAXSIZE\\];//結構體類型的數組elem\\[ \\]做數據成員int length;public:Sqlist( void);~Sqlist( ){ };//其他函數};在上面這個類Sqlist之中,數組素elem［i］都不是簡單的數據類型,而是結構體ElemType的類型。那麼在輸入輸出時不能直接寫: cin>> elem［i］或cout<< elem［i］,而需要寫成: cin>>elem\\[i\\].numb; cin>>lelm\\[i\\].name;cin>>elem\\[I\\].tel;cout<< elem\\[i\\].numb;cout<next=Head; //頭結點Head 形成空環};~ Link ( ){ };voidcreat( );voidouts( );};在上面這個類Link之中,數據成員僅是一個指針,當為它申請和分配到一個結點的存儲空間之後,簡單的情況如上圖所示。在一般情況下可以構成連接多個數據結點的鏈表。實驗0復數ADT——C 實現〖*2〗1. 實驗目的(1) 本實驗是預備性實驗,可以機動掌握。(2) 了解抽像數據類型(ADT)的基本概念及描述方法。(3) 通過對復數抽像數據類型ADT的實現,熟悉C/C 語法及程序設計。為以後章節的學習打下基礎。2. 實例復數的抽像數據類型ADT面向對像程序設計的實現。［復數ADT的描述］ADT complex{ 數據對像:D={ c1,c2 c1,c2∈FloatSet }數據關繫:R={ c1為實部,c2為虛部的實繫數 }基本操作:創建一個復數creat(a);輸出一個復數outputc(a);求兩個復數相加之和add(a,b);求兩個復數相減之差sub(a,b);求兩個復數相乘之積chengji(a,b);等等;} ADT complex; ［復數ADT實現的面向對像源程序］#include #include class Complex//定義結構體復數類型Complex { private:floatx; //實部floaty;//虛部public:Complex( ){}Complex(float x0,float y0){ x=x0; y=y0; }~Complex( ){}void outputc( ){ cout<< "復數: "<線性表順序存儲結構演示"; do{ //顯示菜單內容cout<<"\\\
\\\
;cout<<"\\\
\\\
1. 初步建立一個線性表 ";cout<<"\\\
\\\
2. 插入一素 ";cout<<"\\\
\\\
3. 刪素,返回其值";cout<<"\\\
\\\
4. 結束程序";cout<<"\\\
 ";cout<<"\\\
請輸入你的選擇(1,2,3,4)";cin>>k;//接收用戶的選擇//根據k值,轉向對應的case 分支程序段執行switch(k){ case 1:{as.SetData( ); as.PrintOut( ); }break;case 2:{ cout<<"\\\
插入的位置,數據 i,e=?"; cin>>i>>e; as.Insert(i,e);as.PrintOut( );}break;case 3:{cout<<"\\\
刪除素i=?";cin>>i;x=as.Delet(i); cout<<"\\\<素數值= "<=1&&k<4);cout<<"\\\
再見!";cout<<"\\\
按任意鍵,返回。";_getch( ); return 0;}//-----------------------------------------------(1) 線性表順序存儲結構的本質是: 在邏輯上相鄰的兩素ai-1和ai,在存儲地址中也是相鄰的,即地址連續。順序存儲結構也稱“向量(vector)”。在下列類設計中,采用靜態一維數組elem［］表示向量,同時用length表示線性表長度。ElemTypeelem\\[MAXSIZE\\];int length;有時可以采用動態一維數組來表示向量。ElemTypeelem;int length;int MAXSIZE這就要求在類的構造函數中為其elem動態分配存儲空間,而在析構函數中釋放內存空間。在上機實驗時,需要將數據結構的類定義(包括成員函數的定義)的程序代碼,寫入源程序。同時用戶必須自己編寫一段主函數main( ),在主函數中創建聲明類的具體對像,通過這些對像調用類的公有函數,以便將一個典型數據結構類運用到實際問題中去。(2) 下面是一個完整的源程序,目的是提供一個示範,供參考。［使用線性表實現一個通訊錄］本程序的特點是:素的類型不再是簡單類型(int、char、float),而是更加接近實用的比較復雜的結構體類型。素輸入輸出時,情況復雜一些。#include #include #include #include //------------------------------------------------------------struct ElemType/素的類型 { int numb; char name\\[20\\]; long tel; };const int MAXSIZE=100; //數組的容量class Sqlist{ private:ElemTypeelem\\[MAXSIZE\\];int length;public:Sqlist( void);~Sqlist( ){ };voidSetData( );voidInsert( int i, ElemType e);ElemType Delet(int i);void PrintOut( );
};//------------------------------------------------------------Sqlist::Sqlist( ) { length=0;}voidSqlist::SetData( ) //初步建立一個通訊錄 { cout<<\\\
輸入人數length="; cin>>length;for(int i=0;i 輸入學號:";cin>>elem\\[i\\].numb;cout<<"\\\
輸入姓名:";cin>> elem\\[i\\].name;cout<<"\\\
輸入電話號碼:="; cin>>elem\\[i\\].tel;}}voidSqlist::Insert( int i, ElemType e){ int j; i--; if(i<0||i>length)cout<< " i Error!"<i; j--) elem\\[j\\]=elem\\[j-1\\];elem\\[i\\]=e; length ; }}ElemType Sqlist::Delet(int i) {ElemType x; int j; i--;if(i<0||i>length-1){ cout<< " i Error!"< 通訊錄總人數:"< PrintOut Data:\\\
; cout< 通訊錄演示";do{cout<<"\\\
\\\
;cout<<"\\\
\\\
1. 初步建立一個通訊錄(線性表) ";cout<<"\\\
\\\
2. 插入一素 ";cout<<"\\\
\\\
3. 刪素,返回其值";cout<<"\\\
\\\
4. 結束程序";cout<<"\\\
 ";cout<<"\\\
請輸入你的選擇(1,2,3,4)";cin>>k;switch(k) { case 1:{as.SetData( ); as.PrintOut( );}break;case 2:{ cout<<"\\\
插入的位置, i=?"; cin>>i; cout<<"\\\
插入的數據編號=?"; cin>>e.numb; cout<<"\\\
插入的數據姓名=?"; cin>>e.name; cout<<"\\\
插入的數據電話號碼=?"; cin>>e.tel; as.Insert(i,e);as.PrintOut( ); }break;case 3:{ cout<<"\\\
刪除素i=?";cin>>i;x=as.Delet(i);cout<<"\\\
被素數值= "<=1&&k<4); cout<<"\\\
再見!";cout<<"\\\
按任意鍵,返回。"; _getch( ); return 0;}//-----------------------------------------------實驗2線性表(鏈表)——C 實現〖*2〗1. 實驗目的(1) 了解線性表的邏輯結構特性,以及這種特性在計算機內的鏈表存儲結構。(2) 重點是線性表的基本操作在鏈表結構上的實現,其中以鏈表的操作為側重點,並進一步學習結構化的程序設計方法。(3) 掌握使用 C 面向對像的程序設計技術,設計數據結構源程序的方法。2. 實例(1) 線性表的鏈表存儲表示(結構)及實現。閱讀下列程序請注意幾個問題。一個鏈表由一個頭結點和若干個數據結點組成。① 每個結點的結構定義如下: struct NodeType//結點的結構定義{intnum;//編號子域char name\\[20\\]; //姓名子域NodeType next;//指針域};② 鏈表類的定義。在鏈表類之中,僅列出該鏈表的表頭指針作為類的數據成員。例如,Head是指向上面已經定義過的結點類型NodeType的指針。具體如下: class linkList//類聲明{ private: NodeType Head;};(2) 約瑟夫問題的一種描述: 編號為1,2,…,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數)。一開始任選一個正整數作為報數的上限值m,從個人開始按順時針方向自1開始順序報數。方法1,報數為m的人出列(將其刪除),從他在順時針方向上的下一個人開始重新從1報數……如此下去,直到所有人全部出列為止。試設計一個程序求出出列順序。要求利用單向循環鏈表存儲結構模擬此過程,按照出列的順序打印出各人的編號和此人密碼。方法2,報m的人出列(將其刪除),將他的密碼作為新的m值,從他在順時針方向上的下一個人開始重新從1報數……如此下去,直到所有人全部出列為止。試設計一個程序求出出列順序。要求利用單向循環鏈表存儲結構模擬此過程,按照出列的順序打印出各人的編號。［方法1的程序清單］#include #include struct NodeType//結點的結構定義 {intnum;//編號子域char name\\[20\\]; //姓名子域NodeType next;//指針域 };class Jose//類聲明{ private: NodeType Head; public: Jose( ){ Head=new NodeType; //為頭結點申請空間Head->next=Head;//頭結點Head 形成空環};~Jose( ){ };voidcreat( );voidouts( );};void Jose::creat( ){inti=0, n; NodeTypenewp, pre, h; pre= Head; cout<<"\\\
輸入總人數 n=";cin>>n; for(i=0;inum=i 1;//結點送值(號碼)cout<<"\\\
姓名=";cin>>newp->name;//讀入姓名newp->next=Head;pre->next=newp;pre=newp;//形成循環鏈表} pre->next= Head->next; delete Head;//刪除附加頭結點Head Head=pre->next;//頭指針指向素結點 }//建成約瑟夫環void Jose::outs( )//約瑟夫問題的方法1{int m,i; NodeType q=Head, p; cout<<"\\\
輸入m值(m>=2)";cin>>m; cout<<"\\\
根據m值,開始報數輸出:"<next!=q) { for(i=1;inext;}//報數到第m個人 cout<num<<<name<next=q->next; delete q;//第m個人出列 q=p->next; }cout<num<<<name<#include #include //------------------------棧的順序存儲結構------------------------typedef intElemType; /素的類型const int MAXSIZE=100; //數組的容量class SqStack{ private:ElemTypeelem\\[MAXSIZE\\];int top;public:SqStack( void);~SqStack( ){};intSqStack::SetEmpty( );voidSqStack::push(ElemType e);ElemType SqStack::pop( );void SqStack::PrintOut( ); int SqStack::IsEmpty(void)const ;};//------------------------------------------------------------SqStack::SqStack( void):top(0){ }intSqStack::SetEmpty( ) { return top==0; }
voidSqStack::push(ElemType e){ if(top==MAXSIZE-1) {cout<<"棧滿溢出"< PrintOut Data:\\\
; for(k=top; k>=1;k--) cout< 順序表存儲結構演示";do{cout<<"\\\
\\\
;cout<<"\\\
\\\
1.插入一素e(入棧)";cout<<"\\\
\\\
2.刪素,返回其值(出棧)";cout<<"\\\
\\\
3.結束程序";cout<<"\\\
 ";cout<<"\\\
請輸入你的選擇(1,2,3,4,5,6)";cin>>k;switch(k){ case 1:{cout<<"\\\
入棧,數據 e=?"; cin>>e; as.push(e); as.PrintOut( );}break; case 2:{cout<<"\\\
出棧"; x=as.pop( ); cout<<"\\\--------------------------------- ";}while(k>=1&&k<4);cout<<"\\\
再見!";cout<<"\\\
按任意鍵,返回。";_getch( ); return 0;}2) 棧的鏈式存儲結構及實現（C 語言源程序）//------------------------------------------------------------
#include #include typedef int ElemType;struct Lsnode{ ElemType data; Lsnode next;};class LsStack{private:Lsnode top;public:LsStack( );void Display( );void Push(ElemType x);ElemType Pop( );};LsStack::LsStack( ){ LsStack p; top=NULL;}void LsStack::Display( ){Lsnode p;p=top;while(p!=NULL){cout<data;p=p->next;}cout<<"結束!outend";}void LsStack::Push(ElemTypex){Lsnode p;p=new Lsnode;p->data=x;p->next=top;top=p;}ElemType LsStack::Pop( ){Lsnode p;ElemType x;if(top!=NULL){p=top;top=top->next;x=p->data;delete p;; return x; }else{cout<<"Stack null!\\\
;exit(1);}}int main(){ElemType e;int j;LsStack h;int k;cout<<"\\\
棧的鏈式存儲結構演示";do{cout<<"\\\
\\\
;cout<<"\\\
\\\
1.初步建立一個空棧";cout<<"\\\
\\\
2.輸出整個鏈表棧";cout<<"\\\
\\\
3.入棧:插素e";cout<<"\\\
\\\
4.出棧:刪素";cout<<"\\\
\\\
5.結束程序";cout<<"\\\
\\\\";cout<<"\\\
請輸入你的選擇(1,2,3,4,5,6)";cin>>k;switch(k){case 1:{LsStack::LsStack( );}break;case 2:{h.Display( );}break;case 3:{cout<<"進棧data=??";cin>>e;h.Push(e);h.Display( );}break;case 4:{e=h.Pop( );cout<<"出棧的結點值是:"<-------------------------------";}while(k>=1&&k<6);cout<<"\\\
再見";cout<<"\\\
按任意鍵,返回。";_getch( );return 0; }實驗4隊列——C 實現〖*2〗1. 實驗目的(1) 掌握隊列這種數據結構的邏輯特性及其主要存儲結構。(2) 在簡單情況下會使用順序結構的隊列,熟練掌握循環隊列的使用。 (3) 在復雜情況下會使用鏈表結構的隊列,並能在現實生活中靈活運用。2. 實例在各種教科書中關於隊列的敘述十分清晰。但是,關於它們在計算機內的實現介紹不夠詳細。為了降低學生上機實驗的難度,在此給出幾個例題供參考。本實驗給出了隊列的順序存儲結構及實現(C 語言源程序)和隊列的鏈式存儲結構及實現(C 語言源程序）。1) 隊列的順序存儲結構及實現（C 語言源程序）//------------------------------------------------------------#include #include #define MAXSIZE 20typedef int ElemType; class SeQueue//循環隊列類{private: ElemType elem\\[MAXSIZE\\];int front,rear; public:SeQueue( );~SeQueue( );void Display( );void AddQ(ElemType x);ElemType DelQ( );};SeQueue::SeQueue( ){front=0; rear=0; cout<<"init!"<; else{rear=(rear 1) % MAXSIZE;elem\\[rear\\]=x;cout<<" OK!"; }} ElemType SeQueue::DelQ( ) { if(front==rear) {cout<<"QUEUE IS EMPTY\\\
; return -1;} else{ front=(front 1) % MAXSIZE; return(elem\\[front\\]);} }int main( ){ElemType e;int j; SeQueue h; int k; cout<<"\\\
隊列存儲結構演示";do{cout<<"\\\
\\\
;cout<<"\\\
\\\
1.初步建立一個隊列";cout<<"\\\
\\\
2.輸出整個隊列";cout<<"\\\
\\\
3.入隊";cout<<"\\\
\\\
4.出隊";cout<<"\\\
\\\
5.結束程序";cout<<"\\\
 ";cout<<"\\\
請輸入你的選擇(1,2,3,4,5)";cin>>k;switch(k){ case 1:{SeQueue::SeQueue( );}break; case 2:{h.Display( );}break; case 3:{cout<< "進隊data=?";cin>>e;h.AddQ(e);h.Display( ); }break; case 4:{ e=h.DelQ( ); if(e!=-1) cout<< "出隊的結點值是:"<--------------------------------- ";}while(k>=1&&k<5);cout<<"\\\
再見!";cout<<"\\\
按任意鍵,返回。"; _getch( ); return 0;}2) 隊列的鏈式存儲結構及實現（C 語言源程序）//------------------------------------------------------------#include #include typedef int ElemType;struct quenode{ ElemType data; quenode next;};

書摘插畫

商品搜索

商品分类

【醫學】

【各大出版社】