數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)09級.

1、實驗一線性表的順序表示與實現(xiàn)1. 實驗?zāi)康?1) 掌握線性表的順序存儲結(jié)構(gòu)；(2) 驗證順序表及其基本操作的實現(xiàn)；(3) 掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。2. 實驗內(nèi)容(1) 建立含有若干個元素的順序表；(2) 對已經(jīng)建立的順序表實現(xiàn)插入、刪除、查找、合并等基本操作。3. 實現(xiàn)算法首先，定義順序存儲結(jié)構(gòu)如下：Typedef struct Elemtype *elem;Int len gth;Int listsize;sqlist;其次，建立含有n個元素的順序表，算法如下：Status InitList_Sq( SqList & L ) / 構(gòu)造一個空的順序表L.elem = (

2、ElemType*) malloc (LIST_INIT_SIZEsizeof (ElemType); if (!L.elem) exit (OVERFLOW);L.le ngth = 0;L.listsize = LIST_INIT_SIZEreturn OK;最后，對建立的順序表設(shè)計插入、刪除、查找等基本操作的算法如下：Status ListInsert_Sq(SqList &L, int i, ElemType e) /在順序表L的第i個元素之前插入新的元素eif (i < 1 | i > L.length+1) return ERROR;if (L.length &

3、gt;= L.listsize) newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType);if (!n ewbase) exit (OVERFLOW);L.elem = n ewbase;L.listsize += LISTINCREMENT;q = & (L.elemi-1);for (p = &(L.elemL.length-1); p >= q; -p)* (p+1) = * p;*q = e;+L.length;return OK; Status List

4、Delete_Sq (SqList & L, int i, ElemType &e) / 刪除算法if (i < 1) | (i > L.length) return ERROR;p = & (L.elemi-1);e = *p;q = L.elem+L.le ngth-1;for (+p; p <= q; +p)*(p-1) = *p;-L.le ngth;return OK;int locate_sq(SqList L ,elemtype x) / 查找算法 for(i=0;i<L.length;i+)If(L.elemi=x) return

5、 i+1; return 0;4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗二 線性表的鏈?zhǔn)奖硎九c實現(xiàn)1 實驗?zāi)康?1) 掌握線性表的鏈接存儲結(jié)構(gòu)；(2) 驗證單鏈表及其基本操作的實現(xiàn)；(3) 進(jìn)一步掌握數(shù)據(jù)結(jié)構(gòu)及算法的程序?qū)崿F(xiàn)的基本方法。 2 實驗內(nèi)容(1) 用頭插法和尾插法建立含有若干個元素的帶頭結(jié)點(diǎn)的單鏈表；(2) 對已經(jīng)建立的單鏈表實現(xiàn)插入、刪除、查找等基本操作。3.實現(xiàn)算法4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗三、四 棧與隊列及其應(yīng)用1 實驗?zāi)康?1) 掌握棧的順序存儲結(jié)構(gòu)和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)；(2) 掌握棧和隊列的操作

6、特性；(3) 掌握基于順序棧和鏈隊列的基本操作的實現(xiàn)方法。2 實驗內(nèi)容(1) 建立一個空棧；(2) 對已經(jīng)建立的棧實現(xiàn)入棧、出棧、取棧頂元素等基本操作。(3) 建立一個空隊列；(4) 對已經(jīng)建立的隊列實現(xiàn)插入、刪除等基本操作3 實現(xiàn)算法4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗五 二叉樹的應(yīng)用1 實驗?zāi)康?1) 掌握二叉樹的邏輯結(jié)構(gòu)；(2) 掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)；(3) 掌握基于二叉鏈表存儲的二叉樹的遍歷操作的實現(xiàn)。 2 實驗內(nèi)容(1) 建立一棵含有 n 個結(jié)點(diǎn)的二叉樹；(2) 前序(或中序、后序)遍歷該二叉樹；(3) 求該樹葉子結(jié)點(diǎn)個數(shù)。3 實現(xiàn)算法4

7、 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗六 圖的遍歷與應(yīng)用1 實驗?zāi)康?1) 掌握圖的邏輯結(jié)構(gòu)；(2) 掌握圖的鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)；(3) 掌握圖的鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)下遍歷算法的實現(xiàn)。2 實驗內(nèi)容(1) 建立無向圖的鄰接矩陣存儲；(2) 對已經(jīng)建立的無向圖進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷操作。( 3) 建立有向圖的鄰接表存儲；(4) 對已經(jīng)建立的有向圖進(jìn)行深度優(yōu)先和廣度優(yōu)先遍歷操作。3 實現(xiàn)算法4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗七 查找技術(shù)1 實驗?zāi)康?1) 掌握順序查找和折半查找算法的基本思想；(2

8、) 掌握順序查找和折半查找算法的實現(xiàn)方法；(3) 掌握順序查找和折半查找算法的時間性能。2 實驗內(nèi)容k 相等的元對給定的長度為 n 的數(shù)組，分別使用順序查找、折半查找查找數(shù)組中與給定值素。3.實現(xiàn)算法4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，調(diào)試通過并輸出正確的結(jié)果。實驗八 內(nèi)部排序1 實驗?zāi)康?1) 掌握直接插入排序、冒泡排序和簡單選擇排序的基本思想；(2) 掌握直接插入排序、冒泡排序和簡單選擇排序的實現(xiàn)方法；(3) 掌握快速排序的基本思想和實現(xiàn)方法。2 實驗內(nèi)容 對一組數(shù)據(jù)進(jìn)行直接插入排序、冒泡排序、簡單選擇排序和快速排序。(升序)3 實現(xiàn)算法4 根據(jù)上面設(shè)計的算法，用C/C+語言實現(xiàn)，

9、調(diào)試通過并輸出正確的結(jié)果。附錄一：山東理工大學(xué)實驗教學(xué)授課計劃表附錄二：實驗一的源代碼山東理工大學(xué)實驗教學(xué)授課計劃表1011學(xué)年第1 學(xué)期開課實驗室名稱計算機(jī)中心實驗室課程名稱數(shù)據(jù)結(jié)構(gòu)課程代碼052054開課時間2010.9總實驗學(xué)時16課程類別主講教師肖愛梅院（部）計算機(jī)科學(xué)與技術(shù)課程性質(zhì)專業(yè)基礎(chǔ)課開課班級計科09實驗人數(shù)本科及實驗者類別序 號實驗項 目名稱學(xué)時實驗類別實驗 要求實驗類型實驗計劃時間（到周節(jié)）備注1線性表的順序表示和實現(xiàn)2專業(yè)必選設(shè)計第三周周二7-8節(jié)2線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2專業(yè)必選設(shè)計第四周周二7-8節(jié)3棧的實現(xiàn)及其應(yīng)用2專業(yè)必選設(shè)計第六周周六3-4節(jié)4隊列的實現(xiàn)及其應(yīng)用

10、2專業(yè)必選設(shè)計第八周周六3-4節(jié)5二叉樹及其應(yīng)用2專業(yè)必選設(shè)計第十周周二7-8節(jié)6圖及其應(yīng)用2專業(yè)必選設(shè)計第十二周周二7-8節(jié)7查找技術(shù)2專業(yè)必選設(shè)計第十四周周二7-8節(jié)8內(nèi)部排序2專業(yè)必選設(shè)計第十五周周二7-8節(jié)9101112131415教學(xué)部主任：院（部）分管領(lǐng)導(dǎo)：注：1本表由任課教師填寫，課程所在院（部）統(tǒng)一于每學(xué)期第一周報送實驗室，跨院部的另報實驗室管理科一份。本表留存實驗室； 2實驗類別：基礎(chǔ) /技術(shù)（或?qū)I(yè)）基礎(chǔ)/專業(yè)/ 其他（含畢業(yè)論文和畢業(yè)設(shè)計的實驗） ；3實驗類型：驗證 /創(chuàng)新/綜合/設(shè)計/研究/演 示；4實驗要求：必修 /選修；4備注：改進(jìn)/新開。4 實驗要求：必修 /選修

11、。5備注：改進(jìn)/新開。附錄二： C 語言實現(xiàn)：#include <stdio.h>#include <conio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef int Status;typedef struct int *elem;int length;int listsize;SqList;int InitList_Sq(SqList *L) (*L).e

12、lem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(!(*L).elem)exit(OVERFLOW);(*L).length=0;(*L).listsize=LIST_INIT_SIZE;return OK;/ 創(chuàng)建順序表int CreateList_Sq(SqList *L) int i;cout<<" 請輸入數(shù)據(jù) :"for(i=0;i<(*L).length;i+)scanf("%d",&(*L).elemi);return OK;/ 順序表賦值Status listinse

13、rt_sq(SqList *L,int i,int e) int *q,*p,*newbase; if(i<1|i>(*L).length+1) return ERROR; if(*L).length>=(*L).listsize) newbase=(int*)realloc(*L).elem,(*L).listsize+LISTINCREMENT)* sizeof(int);if(!newbase) exit(OVERFLOW);(*L).elem=newbase;(*L).listsize+=LISTINCREMENT;q=&(*L).elemi-1); for(

14、p=&(*L).elem(*L).length-1);p>=q;-p)*(p+1)=*p;q=e;+(*L).length;return OK;/ 順序表的插入Status listdelete_sq(SqList *L,int i,int &e) int *p,*q;if(i<1|i>(*L).length) return ERROR;p=&(*L).elemi-1);e=*p;q=(*L).elem+(*L).length-1;for(+p;p<=q;+p)*(p-1)=*p;-(*L).length;return OK;/ 順序表的刪除vo

15、id output(SqList *L) cout<<" 輸出序列為 :"int i;for(i=0;i<(*L).length;i+)cout<<" "<<(*L).elemi; cout<<endl;/ 輸出函數(shù)void main() int i,n,e;SqList L;InitList_Sq(&L);cout<<" 請輸入表長 n:" cin>>n;L.length=n;CreateList_Sq(&L); output(&L

16、);cout<<" 請輸入插入位置 i 和插入的元素 cin>>i>>e;listinsert_sq(&L,i,e); cout<<endl; output(&L);cout<<" 請輸入刪除位置 i ： " cin>>i;e=0; listdelete_sq(&L,i,e);cout<<" 被刪除的元素為第 "<<i<<" 位的e 的值： "<<e;cout<<endl

17、; output(&L);C+語言實現(xiàn):#include "iostream.h"#include "sqlist.h"void main() int r=1,2,3,4,5,6,7,8,9,10;sqlist <int> a(r,10);cout<<" 執(zhí)行插入操作前數(shù)據(jù)為: "<<endl;a.printlist();a.insert(2,99);cout<<" 執(zhí)行插入操作后數(shù)據(jù)為: "<<endl;a.printlist();cout<

18、;<" 值為 3 的元素位置為: "<<endl;cout<<a.locate(3)<<endl;a.remove(1);cout<<" 執(zhí)行刪除操作后數(shù)據(jù)為: "<<endl;a. printlist();sqlist.h 文件中進(jìn)行如下的順序表類定義const int MaxSize=100;template<class T>class sqlist public:sqlist()length=0;sqlist(T a,int n);void insert(int i,T

19、x);T remove(int i);int locate(T x);void printlist();private:T elemMaxSize;int length;template<class T> sqlist<T>:sqlist(T a,int n) if(n>MaxSize) cout<< "參數(shù)非法 "for(int i=0;i<n;i+) elemi=ai;length=n;template<class T>void sqlist<T>:insert(int i,T x) if(length<=MaxSize)