第一篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)
數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書(shū)
南京工程學(xué)院
信息管理與信息系統(tǒng)教研室
2014年3月
實(shí)驗(yàn)一 線性表操作
一、實(shí)驗(yàn)?zāi)康?/p>
1.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。
3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。
二、實(shí)驗(yàn)內(nèi)容
1.順序線性表的建立、插入及刪除。
2.鏈?zhǔn)骄€性表的建立、插入及刪除。
三、實(shí)驗(yàn)步驟
1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。
3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。
四、實(shí)現(xiàn)提示
1.由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。
在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/* 線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/* 順序表的長(zhǎng)度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。
2.注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。
3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：
typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域
struct node *next;//指針域
}linklist;注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：
p=(linklist *)malloc(sizeof(linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。
五、思考與提高
1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？
實(shí)驗(yàn)二
棧和隊(duì)列的應(yīng)用
一、實(shí)驗(yàn)?zāi)康?/p>
1.掌握棧的順序表示和實(shí)現(xiàn) 2.掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
二、實(shí)驗(yàn)內(nèi)容
1.編寫(xiě)一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算。2.實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。
三、實(shí)驗(yàn)步驟
1.順序棧(1)初始化順序棧;(2)插入元素(3)刪除棧頂元素(4)取棧頂元素(5)遍歷順序棧(6)置空順序棧 2.鏈隊(duì)列
(1)初始化并建立鏈隊(duì)列(2.)入鏈隊(duì)列(3)出鏈隊(duì)列(4)遍歷鏈隊(duì)列
四、實(shí)現(xiàn)提示
1./*定義順序棧的存儲(chǔ)結(jié)構(gòu)*/ typedef struct { ElemType stack[MAXNUM];int top;}SqStack;
/*初始化順序棧函數(shù)*/ void InitStack(SqStack *p)
{q=(SqStack*)malloc(sizeof(SqStack));/*申請(qǐng)空間*/} /*入棧函數(shù)*/ void Push(SqStack *p,ElemType x){if(p->top
SqStack S;
ElemType e;
int N;
/*初始化順序棧*/ /*入棧*/ /*出棧*/ /*遍歷順序棧*/ getch();}
2./*定義鏈隊(duì)列*/ typedef struct Qnode { ElemType data;struct Qnode *next;}Qnodetype;typedef struct { Qnodetype *front;Qnodetype *rear;}Lqueue;
/*初始化并建立鏈隊(duì)列函數(shù)*/ void creat(Lqueue *q)
{ h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申請(qǐng)空間*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循環(huán)快速輸入數(shù)據(jù)*/ { scanf(“%d”,&x);Lappend(q,x);} /*利用入鏈隊(duì)列函數(shù)快速輸入數(shù)據(jù)*/ } /*入鏈隊(duì)列函數(shù)*/ void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;} /*出鏈隊(duì)列函數(shù)*/ ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*釋放空間*/ /*遍歷鏈隊(duì)列函數(shù)*/ void display(Lqueue *q){ while(p!=NULL)/*利用條件判斷是否到隊(duì)尾*/ { printf(“%d-->”,p->data);p=p->next;} } 可參考如下代碼： #include “stdio.h” #define MaxSize 100 typedef int ElemType;main(){
LinkQueue Q;
ElemType e;
/*初始化并建立鏈隊(duì)列*/
/*入鏈隊(duì)列*/ /*出鏈隊(duì)列*/
*遍歷鏈隊(duì)列*/
}
DestoryQueue(&Q);
getch();}
五、思考與提高
1.讀棧頂元素的算法與退棧頂元素的算法有何區(qū)別？ 試寫(xiě)一個(gè)算法，判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是?回文?。實(shí)驗(yàn)三 樹(shù)操作
一、實(shí)驗(yàn)?zāi)康?/p>
1.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的建立與存儲(chǔ) 2.通過(guò)實(shí)驗(yàn)，掌握二叉樹(shù)的遍歷方法
二、實(shí)驗(yàn)內(nèi)容
1.練習(xí)二叉樹(shù)的建立與存儲(chǔ) 2.練習(xí)二叉樹(shù)的遍歷
三、實(shí)驗(yàn)步驟
1.建立二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。
2.建立二叉樹(shù),并通過(guò)調(diào)用函數(shù), 輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。
四、實(shí)現(xiàn)提示
1.采用遞歸方法建立二叉樹(shù)：
首先建立二叉樹(shù)的根 結(jié)點(diǎn)，然后建立其左右子樹(shù)，直到空子樹(shù)為止。
2.先序遍歷、中序遍歷與后序遍歷二叉樹(shù)。#include
BiTree CreateBiTree(BiTree &T){ } /*先序遍歷*/ Status PreOrderTraverse(BiTree T){ } /*中序遍歷*/ Status InOrderTraverse(BiTree T){ } /*后序遍歷*/ Status PostOrderTraverse(BiTree T){ }
int main(){ BiTree T;CreateBiTree(T);PreOrderTraverse(T);printf(“n”);/*先序遍歷*/ InOrderTraverse(T);printf(“n”);/*中序遍歷*/ PostOrderTraverse(T);printf(“n”);/*后序遍歷*/
return 0;}
五、思考與提高
編寫(xiě)遞歸算法，計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。
第二篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書(shū)
數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 指 導(dǎo) 書(shū)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)
目錄
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū).......................................................................................................................1
目錄...........................................................................................................................................1 實(shí)驗(yàn)指導(dǎo)書(shū)概述...............................................................................................................................2 上機(jī)實(shí)驗(yàn)題目...................................................................................................................................3
實(shí)驗(yàn)一 C語(yǔ)言相關(guān)知識(shí)復(fù)習(xí)................................................................................................3
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................3
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................3 實(shí)驗(yàn)二 單鏈表的插入、刪除...............................................................................................3
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................3
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................3
三、實(shí)現(xiàn)提示...................................................................................................................4 實(shí)驗(yàn)三 棧及其應(yīng)用.................................................................................................................5
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................5
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................5 實(shí)驗(yàn)四 二叉樹(shù)的遞歸算法.....................................................................................................6
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................6
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................6 實(shí)驗(yàn)五 圖的遍歷.....................................................................................................................7
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)六 有序表的查找.............................................................................................................7
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)七 哈希表.........................................................................................................................7
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................7
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................7 實(shí)驗(yàn)八 內(nèi)部排序算法的應(yīng)用.................................................................................................8
一、實(shí)驗(yàn)?zāi)康?..................................................................................................................8
二、實(shí)驗(yàn)內(nèi)容...................................................................................................................8
實(shí)驗(yàn)指導(dǎo)書(shū)概述
“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)一門(mén)重要的專業(yè)技術(shù)基礎(chǔ)課程，是一門(mén)關(guān)鍵性核心課程。本課程系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)算法，介紹了多種常用的查找和排序技術(shù)，并對(duì)其進(jìn)行了性能分析和比較，內(nèi)容非常豐富。本課程的學(xué)習(xí)將為后續(xù)課程的學(xué)習(xí)以及軟件設(shè)計(jì)水平的提高打下良好的基礎(chǔ)。
由于以下原因，使得掌握這門(mén)課程具有較大難度： ? 內(nèi)容多，時(shí)間短，給學(xué)習(xí)帶來(lái)困難；
? 貫穿全書(shū)的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)和遞歸技術(shù)是學(xué)習(xí)中的重點(diǎn)和難點(diǎn)； ? 隱含在各部分的技術(shù)和方法豐富，也是學(xué)習(xí)的重點(diǎn)和難點(diǎn)； ? 先修課程中所介紹的專業(yè)性知識(shí)不多，加大了學(xué)習(xí)難度。
由于數(shù)據(jù)結(jié)構(gòu)課程的技術(shù)性與實(shí)踐性，《數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)》的設(shè)置十分必要。為了幫助學(xué)生更好地學(xué)習(xí)本課程，理解和掌握算法設(shè)計(jì)所需的技術(shù)，為整個(gè)專業(yè)學(xué)習(xí)打好基礎(chǔ)，要求運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些典型問(wèn)題，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的一些技術(shù)。
上機(jī)實(shí)踐是對(duì)學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽(tīng)講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通過(guò)上機(jī)實(shí)踐，使學(xué)生在可能短的時(shí)間內(nèi)對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)的實(shí)踐和應(yīng)用有一個(gè)比較全面和系統(tǒng)的認(rèn)識(shí)，達(dá)到理論與實(shí)踐相結(jié)合的目的。
為了達(dá)到上述目的，本指導(dǎo)書(shū)安排了8個(gè)實(shí)驗(yàn)題目，它們與教科書(shū)的各章有緊密的關(guān)系，使學(xué)生在實(shí)驗(yàn)后能加深對(duì)課程內(nèi)容的理解，增強(qiáng)動(dòng)手能力。
每個(gè)實(shí)驗(yàn)題目采取了統(tǒng)一的格式，由問(wèn)題描述、基本要求、測(cè)試數(shù)據(jù)、實(shí)現(xiàn)提示等部分組成。
問(wèn)題描述旨在為讀者建立問(wèn)題提出的背景環(huán)境，指明問(wèn)題“是什么”；
要求則對(duì)問(wèn)題進(jìn)一步求精，劃出問(wèn)題的邊界，指出具體的參量或前提條件，并規(guī)定該題的最低限度要求；
測(cè)試部分旨在為檢查學(xué)生上機(jī)作業(yè)提供方便，在完成實(shí)習(xí)題時(shí)應(yīng)自己設(shè)計(jì)完整和 嚴(yán)格的測(cè)試方案，當(dāng)數(shù)據(jù)輸入量較大時(shí)，提倡以文件形式向程序提供輸入數(shù)據(jù)；
實(shí)現(xiàn)提示對(duì)實(shí)現(xiàn)中的難點(diǎn)及其解法思路等問(wèn)題作了簡(jiǎn)要提示，個(gè)別問(wèn)題給出了參考實(shí)現(xiàn)。
下面帶*的題目為選做題目。
上機(jī)實(shí)驗(yàn)題目
實(shí)驗(yàn)一 C語(yǔ)言相關(guān)知識(shí)復(fù)習(xí)
一、實(shí)驗(yàn)?zāi)康?/p>
復(fù)習(xí)C語(yǔ)言中函數(shù)、數(shù)組、結(jié)構(gòu)體、文件等概念，掌握它們的描述與操作方法；熟悉掌握C++中typedef、引用參數(shù)調(diào)用（&）的概念及使用方法，為理解數(shù)據(jù)結(jié)構(gòu)課程的后續(xù)內(nèi)容以及算法書(shū)寫(xiě)奠定基礎(chǔ)。
二、實(shí)驗(yàn)內(nèi)容 問(wèn)題描述：編寫(xiě)一個(gè)函數(shù)，求一個(gè)整數(shù)數(shù)組中的最大、最小值。
要求：在函數(shù)聲明中采用引用參數(shù)傳遞方式實(shí)現(xiàn)最大、最小值的返回。測(cè)試：在主函數(shù)中輸入10個(gè)數(shù)，調(diào)用此函數(shù)，打印輸出最大和最小值。2 關(guān)于指針的使用：
用malloc方式分別申請(qǐng)兩個(gè)指針，并實(shí)現(xiàn)兩個(gè)指針內(nèi)容的比較大小操作。要求：此功能在一個(gè)函數(shù)內(nèi)實(shí)現(xiàn)，該函數(shù)接受兩個(gè)整數(shù)值，存儲(chǔ)到兩個(gè)指針內(nèi)容中，輸出兩者中的最大值。
測(cè)試：從主函數(shù)中輸入兩個(gè)數(shù)，調(diào)用該函數(shù)，打印輸出交換后的值。
實(shí)驗(yàn)二 單鏈表的插入、刪除
一、實(shí)驗(yàn)?zāi)康?/p>
1、熟悉某種數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)上實(shí)現(xiàn)的方法。
2、掌握單鏈表的定義、創(chuàng)建、插入、刪除、遍歷等基本操作的實(shí)現(xiàn)。
3、體會(huì)單鏈表操作、有序表插入、刪除的一般方法。
二、實(shí)驗(yàn)內(nèi)容
問(wèn)題描述：已知遞增有序的單鏈表A，編寫(xiě)算法實(shí)現(xiàn)向A中插入或刪除一個(gè)元素，并保持A的有序性。
實(shí)驗(yàn)要求：
1、結(jié)點(diǎn)的數(shù)據(jù)均為整型。
2、若表中已經(jīng)存在此元素，則不插入
三、實(shí)現(xiàn)提示
1.在已知的線性表中插入或刪除，需要下面的輔助函數(shù)：線性表的創(chuàng)建、線性表的遍歷
2.在單鏈表表中插入或刪除，需依次實(shí)現(xiàn)：
a)單鏈表結(jié)構(gòu)的定義
b)單鏈表的創(chuàng)建（頭插法或尾插法建表）c)單鏈表的遍歷
d)單鏈表的插入、刪除（采用順序查找方法，順頭指針往后，查找插入或刪除位置，再修改指針）
//頭文件
#include “stdlib.h” //預(yù)定義常量 #define NULL 0
//單鏈表的定義
typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//單鏈表的創(chuàng)建
void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
q=L;
scanf(“%d”,&data);while(data!=0){
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf(“%d”,&data);} }
//單鏈表的遍歷
void TranverseList(LinkList L){
LinkList p;
p=L->next;
if(p==NULL)
{
printf(“niln”);
return;
}
while(p!=NULL)
{
printf(“%d ”,p->data);
p=p->next;
}
printf(“n”);}
實(shí)驗(yàn)三 棧及其應(yīng)用
一、實(shí)驗(yàn)?zāi)康?/p>
1、熟悉棧的順序表示與實(shí)現(xiàn)。
2、熟悉棧的應(yīng)用。
3、理解并掌握遞歸函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)。
二、實(shí)驗(yàn)內(nèi)容 問(wèn)題描述：利用棧實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為d進(jìn)制數(shù) 要求：
1)輸入一個(gè)n和d，打印輸出d進(jìn)制數(shù)序列。
2)利用順序棧來(lái)實(shí)現(xiàn)十進(jìn)制數(shù)n轉(zhuǎn)化為其他d進(jìn)制數(shù)。此時(shí)，需要同時(shí)實(shí)現(xiàn)初始化空棧、入棧、出棧、判?？盏容o助功能。測(cè)試數(shù)據(jù)：
（1）輸入n:1348
d:8 輸出：2504（2）輸入n:9
d:8 輸出：11（3）輸入n:0
d:8 輸出：0 2 問(wèn)題描述：利用棧實(shí)現(xiàn)算術(shù)表達(dá)式求值。要求：
1)參與運(yùn)算的操作數(shù)為10以內(nèi)的數(shù)值。測(cè)試數(shù)據(jù)：
自擬。
實(shí)驗(yàn)四 二叉樹(shù)的遞歸算法
一、實(shí)驗(yàn)?zāi)康?/p>
1、掌握二叉樹(shù)的表示與實(shí)現(xiàn)。
2、掌握二叉樹(shù)的定義、創(chuàng)建、遍歷等基本操作的實(shí)現(xiàn)。
3、熟悉求二叉樹(shù)深度等遞歸算法的設(shè)計(jì)與實(shí)現(xiàn)。
二、實(shí)驗(yàn)內(nèi)容
問(wèn)題描述：已知二叉樹(shù)t，分別采用順序存儲(chǔ)結(jié)構(gòu)、二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)求二叉樹(shù)的深度，并對(duì)二叉樹(shù)分別進(jìn)行中序遍歷。要求：
1、二叉樹(shù)分別采用順序或二叉鏈表存儲(chǔ)。
2、樹(shù)中的數(shù)據(jù)類型約定為整型。測(cè)試數(shù)據(jù)：
1、輸入序列：-+a??*b??-c??d??/e??f??創(chuàng)建二叉樹(shù)； 輸出：深度：5
前序序列：-+a*b-cd/ef
中序序列：a+b*c-d-e/f
后序序列：abcd-*+ef/-T:d / e f
2、t=nil
輸入：?
輸出：深度：0 實(shí)驗(yàn)五 圖的遍歷
一、實(shí)驗(yàn)?zāi)康?/p>
熟悉圖的基本操作，掌握?qǐng)D遍歷的設(shè)計(jì)與實(shí)現(xiàn)。
二、實(shí)驗(yàn)內(nèi)容
問(wèn)題描述：已知的描述校園景點(diǎn)的圖，實(shí)現(xiàn)對(duì)該圖的深度優(yōu)先和廣度優(yōu)先遍歷。要求：
圖采用鄰接矩陣存儲(chǔ)，頂點(diǎn)信息包括景點(diǎn)的名稱和簡(jiǎn)單描述。
實(shí)驗(yàn)六 有序表的查找
一、實(shí)驗(yàn)?zāi)康?/p>
1、理解各種查找方法的基本思想
2、熟悉有序表查找方法的算法實(shí)現(xiàn)
二、實(shí)驗(yàn)內(nèi)容 已知一有序的序列{1,3,5,7,9}，采用折半法分別查找3和6。
2已知輸入一無(wú)序的序列{5,1,3,9,7}，創(chuàng)建一棵二叉排序樹(shù)，然后對(duì)其遍歷，輸出遞增有序的序列。
實(shí)驗(yàn)七 哈希表
一、實(shí)驗(yàn)?zāi)康?/p>
理解哈希表的概念和基本操作；熟悉哈希表的創(chuàng)建、查找、插入的算法實(shí)現(xiàn)。
二、實(shí)驗(yàn)內(nèi)容
問(wèn)題描述：已知11位好友的名字各不相同，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)哈希表，根據(jù)好友的名字，可以取得其生日。要求：
1、好友的信息包含名字和生日兩個(gè)數(shù)據(jù)項(xiàng)，其中好友的名字為主鍵，用漢語(yǔ)拼音形式存放；
2、哈希函數(shù)采取：好友名字中所有拼音字母ASCII碼值的和 MOD 11(除以1取余)；
3、采取線性探測(cè)再散列的方式處理沖突。
實(shí)驗(yàn)八 內(nèi)部排序算法的應(yīng)用
一、實(shí)驗(yàn)?zāi)康?/p>
理解各種內(nèi)部排序方法的基本思想；熟悉各種內(nèi)部排序方法的算法實(shí)現(xiàn)
二、實(shí)驗(yàn)內(nèi)容
問(wèn)題描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分別采取下列排序方法對(duì)其進(jìn)行排序：
（1）直接插入排序；
（2）簡(jiǎn)單選擇排序；
（3）起泡排序；（4）快速排序；（5）堆排序。
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)
目 錄
實(shí)驗(yàn)規(guī)則················································2 實(shí)驗(yàn)環(huán)境················································2 實(shí)驗(yàn)報(bào)告要求············································3 實(shí)驗(yàn)一 單鏈表
（一）······································4 實(shí)驗(yàn)二 單鏈表
（二）······································5 實(shí)驗(yàn)三 ?！ぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ? 實(shí)驗(yàn)四 二叉樹(shù)···········································7 實(shí)驗(yàn)五 最短路徑·········································8 實(shí)驗(yàn)六 內(nèi)部排序·········································9
實(shí) 驗(yàn) 規(guī) 則
為了順利完成實(shí)驗(yàn)教學(xué)任務(wù)，確保人身、設(shè)備的安全，培養(yǎng)嚴(yán)謹(jǐn)、踏實(shí)、實(shí)事求是的科學(xué)作風(fēng)和愛(ài)護(hù)國(guó)家財(cái)產(chǎn)的優(yōu)良品質(zhì)，特制定以下實(shí)驗(yàn)規(guī)則：
1、實(shí)驗(yàn)前必須充分預(yù)習(xí)，完成指定的預(yù)習(xí)任務(wù)。預(yù)習(xí)要求如下：
（1）認(rèn)真閱讀指導(dǎo)書(shū)，進(jìn)行必要的設(shè)計(jì)與計(jì)算。（2）熟悉實(shí)驗(yàn)內(nèi)容。
（3）預(yù)先復(fù)習(xí)，并按要求編寫(xiě)程序。（4）未完成預(yù)習(xí)任務(wù)者不得進(jìn)入實(shí)驗(yàn)室。
2、遵守以下紀(jì)律：
（1）在實(shí)驗(yàn)室不得做和實(shí)驗(yàn)無(wú)關(guān)的事情。
（2）進(jìn)行任課老師指定內(nèi)容以外的實(shí)驗(yàn)，必須經(jīng)指導(dǎo)教師同意。（3）遵守紀(jì)律，不遲到。
（4）保持實(shí)驗(yàn)室內(nèi)安靜、整潔，愛(ài)護(hù)公物，不許亂寫(xiě)亂畫(huà)。
實(shí) 驗(yàn) 環(huán) 境
本實(shí)驗(yàn)在386以上的微機(jī)上進(jìn)行，運(yùn)行環(huán)境為VC6.0。
實(shí)驗(yàn)報(bào)告要求
1、實(shí)驗(yàn)題目 2．實(shí)驗(yàn)?zāi)康?3．實(shí)驗(yàn)環(huán)境
4．實(shí)驗(yàn)內(nèi)容與完成情況（可以附上自主設(shè)計(jì)的源程序）5．出現(xiàn)的問(wèn)題及對(duì)問(wèn)題的解決方案 6．實(shí)驗(yàn)思考：（學(xué)生對(duì)本次實(shí)驗(yàn)的收獲的總結(jié)）
實(shí)驗(yàn)一 單鏈表
（一）一、實(shí)驗(yàn)?zāi)康?/p>
掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作。
二、預(yù)習(xí)要求
1、看懂書(shū)上的算法，深入理解鏈表的物理存儲(chǔ)模式和邏輯模式。
2、根據(jù)要求，編寫(xiě)程序準(zhǔn)備上機(jī)調(diào)試。
三、實(shí)驗(yàn)內(nèi)容
實(shí)現(xiàn)一個(gè)簡(jiǎn)單的學(xué)生信息管理系統(tǒng)，該系統(tǒng)的功能有：
1、利用單鏈表建立學(xué)生基本信息表
2、瀏覽每個(gè)學(xué)生的信息
3、根據(jù)學(xué)號(hào)查詢某個(gè)學(xué)生的基本信息
4、添加學(xué)生信息到單鏈表中
5、刪除一個(gè)學(xué)生的信息
四、實(shí)現(xiàn)提示
設(shè)計(jì)結(jié)點(diǎn)的結(jié)構(gòu)體類型，包括學(xué)生的學(xué)號(hào)、姓名、年齡、性別；要求設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單界面，根據(jù)需要選擇所要進(jìn)行的操作；構(gòu)造函數(shù)，每一個(gè)函數(shù)實(shí)現(xiàn)上述的一個(gè)功能。
實(shí)驗(yàn)二 單鏈表
（二）一、實(shí)驗(yàn)?zāi)康?/p>
掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本操作。
二、預(yù)習(xí)要求
1、看懂書(shū)上的算法，深入理解鏈表的物理存儲(chǔ)模式和邏輯模式。
2、根據(jù)要求，編寫(xiě)程序準(zhǔn)備上機(jī)調(diào)試。
三、實(shí)驗(yàn)內(nèi)容
1、實(shí)現(xiàn)單鏈表的就地逆置。
2、建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞減鏈表。
3、建立兩個(gè)非遞減有序單鏈表，然后合并成一個(gè)非遞增鏈表。
4、編寫(xiě)一個(gè)主函數(shù),調(diào)試上述算法。
四、選做題、思考題
1、如何用帶表頭結(jié)點(diǎn)的單鏈表作為多項(xiàng)式的存儲(chǔ)表示，實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加。
2、約毖夫環(huán)的實(shí)現(xiàn)。
3、如何利用文件實(shí)現(xiàn)學(xué)生信息的存取。
實(shí)驗(yàn)三 棧
一、實(shí)驗(yàn)?zāi)康?/p>
深入了解并掌握棧的特性及其在實(shí)際中的應(yīng)用；熟練掌握棧的算法實(shí)現(xiàn)；運(yùn)用棧操作求解實(shí)際問(wèn)題。
二、預(yù)習(xí)要求
1、看懂書(shū)上的算法，深入理解棧的特性和存儲(chǔ)結(jié)構(gòu)，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用。
2、根據(jù)要求，編寫(xiě)程序準(zhǔn)備上機(jī)調(diào)試。
三、實(shí)驗(yàn)內(nèi)容
利用棧實(shí)現(xiàn)數(shù)據(jù)的分類，要求當(dāng)輸入為偶數(shù)時(shí)進(jìn)棧1，當(dāng)輸入為奇數(shù)時(shí)進(jìn)棧2，最后分別從棧1和棧2輸出偶數(shù)和奇數(shù)序列。
四、實(shí)現(xiàn)提示
1、開(kāi)辟一個(gè)連續(xù)的存儲(chǔ)空間，實(shí)現(xiàn)兩個(gè)棧順序存儲(chǔ)空間的共享；分別在兩端設(shè)置棧頂指針，并按要求實(shí)現(xiàn)棧操作。
2、采用順序存儲(chǔ)實(shí)現(xiàn)棧的初始化、入棧、出棧操作。
五、選做題、思考題
1、兩?？臻g共享時(shí)，棧滿的條件是什么？
2、為停車場(chǎng)編制進(jìn)行管理的模擬程序（習(xí)題集P96，2.1）。
3、編寫(xiě)程序，利用棧實(shí)現(xiàn)表達(dá)式求值。
實(shí)驗(yàn)四 二叉樹(shù)
一、實(shí)驗(yàn)?zāi)康?/p>
通過(guò)實(shí)踐掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和遍歷思想；掌握二叉樹(shù)的常見(jiàn)算法的程序?qū)崿F(xiàn)。
二、預(yù)習(xí)要求
二叉樹(shù)的三種遍歷方法。
三、實(shí)驗(yàn)內(nèi)容
1、輸入字符序列，建立二叉鏈表。
2、利用棧，編寫(xiě)非遞歸算法，編程實(shí)現(xiàn)二叉樹(shù)的中序遍歷。
3、求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)。
4、在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別調(diào)試上述算法。
四、選做題、思考題
1、如何實(shí)現(xiàn)二叉樹(shù)的后序遍歷（非遞歸）。
2、如何求二叉樹(shù)的高度。
實(shí)驗(yàn)五 最短路徑（旅游景點(diǎn)導(dǎo)游咨詢模擬）
一、實(shí)驗(yàn)?zāi)康?/p>
利用圖的最短路徑原理為用戶提供路徑咨詢，掌握求最短路徑的算法并編程實(shí)現(xiàn)。
二、預(yù)習(xí)要求
學(xué)習(xí)了解圖的存儲(chǔ)結(jié)構(gòu)，掌握求最短路徑的兩種算法。
三、實(shí)驗(yàn)內(nèi)容
設(shè)計(jì)一個(gè)旅游景點(diǎn)導(dǎo)游模擬程序，為來(lái)訪的客人提供景點(diǎn)最短路徑的信息查詢服務(wù)，任意選取n城市，構(gòu)成一個(gè)有向帶權(quán)圖，圖中頂點(diǎn)表示城市，邊上的權(quán)值表示兩點(diǎn)間的距離，根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)的最短路徑。
四、實(shí)現(xiàn)提示
咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行，由用戶輸入起始點(diǎn)和終點(diǎn)，輸出信息：最短路徑是多少？并指出所經(jīng)過(guò)的城市。存儲(chǔ)結(jié)構(gòu)可選用鄰接矩陣。
五、選做題、思考題
1．如何實(shí)現(xiàn)對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能。
2．用鄰接表作存儲(chǔ)結(jié)構(gòu)，求一指定景點(diǎn)出發(fā)，到其余各景點(diǎn)的最短路徑。
實(shí)驗(yàn)六 內(nèi)部排序
一、實(shí)驗(yàn)?zāi)康?/p>
直觀感受算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)。
二、預(yù)習(xí)要求
1、常見(jiàn)的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點(diǎn)及其適用條件。
2、根據(jù)要求，編寫(xiě)程序準(zhǔn)備上機(jī)調(diào)試。
三、實(shí)驗(yàn)內(nèi)容
1、對(duì)直接插入排序和簡(jiǎn)單選擇排序算法進(jìn)行關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)的比較。
2、利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編寫(xiě)程序，實(shí)現(xiàn)直接插入排序和冒泡排序。
四、實(shí)現(xiàn)提示
測(cè)試數(shù)據(jù)可以為幾組典型的數(shù)據(jù)：正序、逆序、亂序。
五、選做題、思考題
1、快速排序算法的非遞歸實(shí)現(xiàn)。
2、結(jié)合實(shí)驗(yàn)，理解針對(duì)不同待排元素的特點(diǎn)而選擇不同排序方法的重要性。
3、如何對(duì)本實(shí)驗(yàn)進(jìn)行時(shí)間、空間的復(fù)雜度分析。
第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)
目 錄
實(shí)驗(yàn)一
線性表、棧和隊(duì)列的基本操作............................................................1 實(shí)驗(yàn)二
二叉樹(shù)的基本操作................................................................................3 實(shí)驗(yàn)三
內(nèi)部排序的基本操作............................................................................5 附錄：《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)報(bào)告格式..........................................................6
實(shí)驗(yàn)一
線性表、棧和隊(duì)列的基本操作
【實(shí)驗(yàn)?zāi)康摹?/p>
1.掌握線性表（順序表和鏈表）的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義及C語(yǔ)言的實(shí)現(xiàn)。
2.掌握線性表（順序表和鏈表）的建立、插入、刪除、查找等基本操作。3.深入了解棧和隊(duì)列的基本特性。
4.熟練掌握棧和隊(duì)列的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。5.熟練掌握循環(huán)隊(duì)列的基本操作。
【實(shí)驗(yàn)內(nèi)容】
1.報(bào)數(shù)問(wèn)題：編號(hào)為1，2，···，n的n個(gè)人圍坐在一圓桌旁，每人持有一個(gè)正整數(shù)的編號(hào)。從第一個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到一個(gè)預(yù)先約定的正整數(shù)m時(shí)，停止報(bào)數(shù)，報(bào)m的人退席，下一個(gè)人又重新從1開(kāi)始報(bào)數(shù)，依此重復(fù)，直至所有的人都退席。編一程序輸出他們退席的編號(hào)序列。例如，設(shè)m=20，n=7，則退席的人的編號(hào)依次為6，1，7，5，3，2，4。
2.設(shè)計(jì)一個(gè)順序棧的基本操作的程序，包括初始化順序棧、判斷棧空、求順序棧中的元素個(gè)數(shù)、取順序棧棧頂元素、入棧、出棧，并測(cè)試十進(jìn)制轉(zhuǎn)換成16進(jìn)制的運(yùn)算。
3.設(shè)計(jì)一個(gè)循環(huán)隊(duì)列的基本操作的程序，包括實(shí)現(xiàn)下列6種基本運(yùn)算：初始化、入隊(duì)、出隊(duì)、遍歷、求隊(duì)列的長(zhǎng)度，并測(cè)試用隊(duì)列實(shí)現(xiàn)楊輝三角的輸出顯示。
【實(shí)驗(yàn)安排】
由于該實(shí)驗(yàn)是數(shù)據(jù)結(jié)構(gòu)的第一個(gè)實(shí)驗(yàn)，建議適當(dāng)多安排一些時(shí)間進(jìn)行熟悉。建議課時(shí)安排如下：
課外 2學(xué)時(shí)，課內(nèi)2學(xué)時(shí)
【實(shí)驗(yàn)提示】
1.報(bào)數(shù)問(wèn)題的存儲(chǔ)結(jié)構(gòu)可以采用以下兩種方式：
(1)以順序表為存儲(chǔ)結(jié)構(gòu)：可以用簡(jiǎn)單的數(shù)組
int p[n];
(2)以循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)：用不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表表示圍成圓圈的n個(gè)人；建立此循環(huán)單鏈表；某人離席相當(dāng)于刪除一個(gè)結(jié)點(diǎn)要正確設(shè)置程序中循環(huán)終止的條件和刪除結(jié)點(diǎn)時(shí)指針的修改變化。
typedef struct LNode{ int data;
實(shí)驗(yàn)二
二叉樹(shù)的基本操作
【實(shí)驗(yàn)?zāi)康摹?/p>
1.掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)方法。2.掌握二叉樹(shù)的遍歷方法。
3.掌握二叉樹(shù)中插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)的方法。
4.掌握二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)和樹(shù)的深度的計(jì)算方法。5.掌握建立哈夫曼樹(shù)的方法，實(shí)現(xiàn)哈夫曼編碼。
【實(shí)驗(yàn)內(nèi)容】
1.要求采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，完成二叉樹(shù)的建立，前序、中序和后序遍歷的操作，求所有葉子及結(jié)點(diǎn)總數(shù)的操作等。具體實(shí)現(xiàn)要求：(1)基于先序遍歷的構(gòu)造算法：輸入是二叉樹(shù)的先序序列，但必須在其中加入虛結(jié)點(diǎn)以示空指針的位置。假設(shè)虛結(jié)點(diǎn)輸入時(shí)用空格字符表示。(2)分別利用前序遍歷、中序遍歷、后序遍歷所建二叉樹(shù)。(3)統(tǒng)計(jì)以上二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)和結(jié)點(diǎn)總數(shù)。2.熟練掌握哈夫曼樹(shù)的構(gòu)建，并實(shí)現(xiàn)哈夫曼編碼。
【實(shí)驗(yàn)安排】
建議課時(shí)安排如下：
課外 4學(xué)時(shí)，課內(nèi)2學(xué)時(shí)
【實(shí)驗(yàn)提示】
1.采用C語(yǔ)言的定義樹(shù)的存儲(chǔ)結(jié)構(gòu)： //二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示 typedef char DataType;//應(yīng)由用戶定義DataType的實(shí)際類型 typedef struct node { DataType data;struct node *lchild, *rchild;//左右孩子指針 } BinTNode;
//結(jié)點(diǎn)類型
typedef BinTNode *BinTree;
2.可以考慮采用遞歸的方法先創(chuàng)建根結(jié)點(diǎn)，然后分別創(chuàng)建左右子樹(shù)。在創(chuàng)建二叉樹(shù)的過(guò)程中，要注意結(jié)點(diǎn)數(shù)是根據(jù)輸入的字符確定的。如：
void CreateBinTree(BinTree &T){
實(shí)驗(yàn)三
內(nèi)部排序的基本操作
【實(shí)驗(yàn)?zāi)康摹?/p>
1.掌握排序的有關(guān)概念和特點(diǎn)。
2.熟練掌握直接插入排序、希爾排序、冒泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、歸并排序、基數(shù)排序等算法的基本思想。
3.關(guān)鍵字序列有序與無(wú)序，對(duì)于不同的排序方法有不同的影響，通過(guò)該實(shí)驗(yàn)進(jìn)一步加深理解。
4.了解各種排序方法的優(yōu)缺點(diǎn)和適用范圍。
【實(shí)驗(yàn)內(nèi)容】
1.從鍵盤(pán)輸入上述8個(gè)整數(shù)，存放在數(shù)組quick[8]中，并輸出值。2.輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。
3.如果上述8個(gè)整數(shù)按照升序輸入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。4.如果上述8個(gè)整數(shù)按照降序輸入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，輸出各種排序算法每一趟排序的結(jié)果，觀察關(guān)鍵字次序的變化。5.測(cè)試各排序算法的執(zhí)行時(shí)間，比較執(zhí)行效率。
6.隨機(jī)產(chǎn)生3萬(wàn)個(gè)數(shù)，對(duì)其進(jìn)行排序，觀察其結(jié)果。
【實(shí)驗(yàn)安排】
建議課時(shí)安排如下：
課外 2學(xué)時(shí)，課內(nèi)2學(xué)時(shí) 【實(shí)驗(yàn)提示】
1.采用C語(yǔ)言的定義記錄類型的存儲(chǔ)結(jié)構(gòu)： typedef int InfoType;#define n 10
typedef int KeyType;typedef struct {
//假設(shè)的文件長(zhǎng)度，即待排序的記錄數(shù)目 //假設(shè)的關(guān)鍵字類型 //記錄類型
//關(guān)鍵字項(xiàng)
//其它數(shù)據(jù)項(xiàng)，類型InfoType依賴于具體應(yīng)用而 KeyType key;
InfoType otherinfo;定義
} RecType;typedef RecType SeqList[n+1];作哨兵
2.注意哨兵的作用。
//SeqList為順序表類型，表中第0個(gè)單元一般用
第五篇：《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)書(shū)
《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)(訓(xùn))指導(dǎo)書(shū)
電氣與信息工程學(xué)院實(shí)驗(yàn)中心
前 言
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)相關(guān)專業(yè)的一門(mén)核心基礎(chǔ)課程，也是很多高校研究生入學(xué)考試專業(yè)課必考課程之一。它主要介紹線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖形結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲(chǔ)實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時(shí)、空效率分析。這門(mén)課程的主要任務(wù)是培養(yǎng)學(xué)生的算法分析、設(shè)計(jì)能力及良好的程序設(shè)計(jì)習(xí)慣。通過(guò)學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計(jì)思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問(wèn)題選取合適的存儲(chǔ)方案，設(shè)計(jì)出簡(jiǎn)潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開(kāi)發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門(mén)課程，習(xí)題和實(shí)驗(yàn)是兩個(gè)關(guān)鍵環(huán)節(jié)。學(xué)生理解算法的最佳途徑是上機(jī)實(shí)驗(yàn)。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好《數(shù)據(jù)結(jié)構(gòu)》的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫(xiě)該實(shí)驗(yàn)指導(dǎo)書(shū)。
一、實(shí)驗(yàn)?zāi)康摹⒁蠛腿蝿?wù)
計(jì)算機(jī)編程中加工處理的對(duì)象是數(shù)據(jù)，而數(shù)據(jù)具有一定的組織結(jié)構(gòu)，所以學(xué)習(xí)編寫(xiě)計(jì)算機(jī)程序僅僅了解計(jì)算機(jī)語(yǔ)言是不夠的，還必須掌握數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法，這是數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)和研究的內(nèi)容。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法較抽象，而該課程一般在本科低年級(jí)開(kāi)設(shè)，對(duì)于計(jì)算機(jī)程序設(shè)計(jì)知識(shí)的初學(xué)者，理解和掌握其中的原理就顯得較為困難。
1.熟練掌握C語(yǔ)言的編輯、編譯、調(diào)試程序。2.會(huì)書(shū)寫(xiě)類C語(yǔ)言的算法，并將算法轉(zhuǎn)變?yōu)槌绦驅(qū)崿F(xiàn)。
3.正確理解各種數(shù)據(jù)結(jié)構(gòu)的邏輯特性和存儲(chǔ)表示和基本操作的算法實(shí)現(xiàn)。4.有較強(qiáng)的邏輯分析能力。
5.針對(duì)問(wèn)題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計(jì)的能力和動(dòng)手實(shí)驗(yàn)的技能。
6.學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用設(shè)計(jì)的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。
7.本課程的學(xué)習(xí)過(guò)程也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過(guò)程，要求學(xué)生編寫(xiě)的程序結(jié)構(gòu)清楚、正確易讀，符合軟件過(guò)程的規(guī)范，從而培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力。
8.通過(guò)若干數(shù)據(jù)結(jié)構(gòu)應(yīng)用實(shí)例，引導(dǎo)學(xué)生學(xué)習(xí)數(shù)據(jù)類型的使用，為今后學(xué)習(xí)面向?qū)ο蟮某绦蜃鲆恍╀亯|。
二、實(shí)驗(yàn)基本內(nèi)容及學(xué)時(shí)分配
為了達(dá)到實(shí)驗(yàn)?zāi)康?，本課程安排了4個(gè)實(shí)驗(yàn)單元，訓(xùn)練的重點(diǎn)在于基本的數(shù)據(jù)結(jié)構(gòu)，而不是強(qiáng)調(diào)面面俱到。各實(shí)驗(yàn)單元與教科書(shū)的各章只具有粗略的對(duì)應(yīng)關(guān)系，一個(gè)實(shí)驗(yàn)題常常涉及到幾部分教學(xué)內(nèi)容?？倢W(xué)時(shí)：8學(xué)時(shí)。
1、線性表（2學(xué)時(shí)）
（1）熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)（順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)）上的實(shí)現(xiàn)；（2）以線性表的各種操作（建立、插入、刪除等）的實(shí)現(xiàn)為重點(diǎn)；
（3）通過(guò)本次實(shí)驗(yàn)幫助學(xué)生提高C語(yǔ)言的編程能力（特別是函數(shù)參數(shù)、指針類型、鏈表的使用）。
2、數(shù)組和廣義表（2學(xué)時(shí)）（1）掌握稀疏矩陣的壓縮存儲(chǔ)
（2）掌握稀疏矩陣的轉(zhuǎn)置算法
3、樹(shù)與二叉樹(shù)（2學(xué)時(shí)）
常見(jiàn)的二叉樹(shù)遍歷算法有先序遍歷，中序遍歷和后序遍歷算法。實(shí)現(xiàn)簡(jiǎn)單的先序遍歷，中序遍歷和后序遍歷算法。
4、排序（2學(xué)時(shí)）
常見(jiàn)的內(nèi)部排序算法，插入類排序算法，如直接插入排序和希爾排序；交換類排序算法，如冒泡排序和快速排序；選擇類排序算法，如簡(jiǎn)單選擇排序、樹(shù)形選擇類排序和堆排序。實(shí)冒泡排序或者直接插入排序算法。
三、說(shuō)明
該課程采用理論與實(shí)踐相結(jié)合的教學(xué)方法，集知識(shí)性與趣味性于一體，達(dá)到良好的教學(xué)效果。硬件要求：在多媒體教室講解及演示。為保證教學(xué)順利進(jìn)行，要求實(shí)驗(yàn)室提供電腦等設(shè)備。學(xué)生每次上機(jī)實(shí)驗(yàn)都必須遵守實(shí)驗(yàn)室的有關(guān)規(guī)定。
四、實(shí)驗(yàn)報(bào)告規(guī)范 實(shí)驗(yàn)報(bào)告的內(nèi)容包括：
1、實(shí)驗(yàn)?zāi)康模赫f(shuō)明實(shí)驗(yàn)所驗(yàn)證的知識(shí)點(diǎn)。
2、需求分析：以無(wú)歧義的陳述說(shuō)明程序設(shè)計(jì)的任務(wù)、約束條件、輸入輸出要求、對(duì)功能的規(guī)定及模型。
3、邏輯設(shè)計(jì)：說(shuō)明本程序中用到的所有抽象的數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次調(diào)用關(guān)系。
4、詳細(xì)設(shè)計(jì)：邏輯設(shè)計(jì)中定義的所有數(shù)據(jù)類型的實(shí)現(xiàn)，核心算法的設(shè)計(jì)描述、人機(jī)界面設(shè)計(jì)、函數(shù)之間調(diào)用關(guān)系的描述，主要功能的算法框架，測(cè)試數(shù)據(jù)設(shè)計(jì)。
5、測(cè)試分析：測(cè)試結(jié)果的分析與討論，測(cè)試過(guò)程中遇到的主要問(wèn)題及采取的解決措施。
6、心得：軟件設(shè)計(jì)與實(shí)現(xiàn)過(guò)程中的經(jīng)驗(yàn)與體會(huì)，進(jìn)一步改進(jìn)的設(shè)想。
7、程序清單：源程序中應(yīng)有足夠的注釋。如果提交源程序軟盤(pán)，列出程序文件名。
五、如何提高上機(jī)效率
為了提高上機(jī)的效率，真正達(dá)到實(shí)驗(yàn)?zāi)康模笸瑢W(xué)做好實(shí)驗(yàn)前的準(zhǔn)備工作，寫(xiě)好實(shí)驗(yàn)預(yù)習(xí)報(bào)告，即實(shí)驗(yàn)報(bào)告規(guī)范中的1）、2）、3）、4）部分，編寫(xiě)好程序，并用一組測(cè)試數(shù)據(jù)手工執(zhí)行程序靜態(tài)檢查程序是否有錯(cuò)，通過(guò)閱讀、執(zhí)行程序或給別人講解自己的程序而深入全面地理解程序邏輯，提高程序的正確性。對(duì)C語(yǔ)言程序不熟悉的同學(xué)，上機(jī)時(shí)最好帶上C語(yǔ)言程序設(shè)計(jì)的教材，以備查閱。調(diào)試中遇到問(wèn)題，應(yīng)認(rèn)真分析，確定可疑點(diǎn)，設(shè)置調(diào)試斷點(diǎn)或輸出斷點(diǎn)處變量的值，以便發(fā)現(xiàn)問(wèn)題，迅速排除問(wèn)題，加快調(diào)試速度。
實(shí)驗(yàn)室要求：
不能曠課，不遲到，不穿拖鞋進(jìn)實(shí)驗(yàn)室
實(shí)驗(yàn)需預(yù)習(xí)報(bào)告（不能單純抄寫(xiě)，預(yù)習(xí)程序代碼）實(shí)驗(yàn)報(bào)告（總結(jié)，注釋，實(shí)驗(yàn)結(jié)果）
目 錄
實(shí)驗(yàn)一 線性表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）..........................................4 實(shí)驗(yàn)二 數(shù)組和廣義表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）....................................6 實(shí)驗(yàn)三 樹(shù)與二叉樹(shù)（設(shè)計(jì)性實(shí)驗(yàn)）..........................................8 實(shí)驗(yàn)四 排序（設(shè)計(jì)性實(shí)驗(yàn)）................................................9
實(shí)驗(yàn)一
線性表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）
一、實(shí)驗(yàn)?zāi)康?/p>
1.熟悉C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步掌握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。
3.掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表的定義及C語(yǔ)言實(shí)現(xiàn)。4.掌握線性表在順序存儲(chǔ)結(jié)構(gòu)即順序表中的各種基本操作。5.掌握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——單鏈表中的各種基本操作。
二、實(shí)驗(yàn)內(nèi)容
1.順序線性表的建立、插入及刪除。2.鏈?zhǔn)骄€性表的建立、插入及刪除。
三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦
四、實(shí)驗(yàn)步驟
1.建立含n個(gè)數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長(zhǎng)度。
2.利用前面的實(shí)驗(yàn)先建立一個(gè)順序表L={21，23，14，5，56，17，31}，然后在第i個(gè)位置插入元素68。
3.建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)的值域?yàn)檎蛿?shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來(lái)建立相應(yīng)單鏈表。
五、實(shí)驗(yàn)提示
1.由于C語(yǔ)言的數(shù)組類型也有隨機(jī)存取的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語(yǔ)言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。
在此，我們利用C語(yǔ)言的結(jié)構(gòu)體類型定義順序表： #define MAXSIZE 1024 typedef int elemtype;/*
線性表中存放整型元素 */ typedef struct { elemtype vec[MAXSIZE];int len;/*
順序表的長(zhǎng)度 */ }sequenlist;將此結(jié)構(gòu)定義放在一個(gè)頭文件sqlist.h里，可避免在后面的參考程序中代碼重復(fù)書(shū)寫(xiě)，另外在該頭文件里給出順序表的建立及常量的定義。
2.注意如何取到第i個(gè)元素，在插入過(guò)程中注意溢出情況以及數(shù)組的下標(biāo)與位序（順序表中元素的次序）的區(qū)別。
3.單鏈表的結(jié)點(diǎn)結(jié)構(gòu)除數(shù)據(jù)域外，還含有一個(gè)指針域。用C語(yǔ)言描述結(jié)點(diǎn)結(jié)構(gòu)如下：
typedef int elemtype;typedef struct node { elemtype data;//數(shù)據(jù)域
struct node *next;//指針域
}linklist;
注意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc()，如給指針變量p分配一個(gè)結(jié)點(diǎn)的地址：
p=(linklist *)malloc(sizeof(linklist));該語(yǔ)句的功能是申請(qǐng)分配一個(gè)類型為linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p 中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值（NULL）。
六、實(shí)驗(yàn)總結(jié)與思考
1.如果按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立順序表。2.在main函數(shù)里如果去掉L=&a語(yǔ)句，會(huì)出現(xiàn)什么結(jié)果？
實(shí)驗(yàn)二
數(shù)組和廣義表實(shí)驗(yàn)（設(shè)計(jì)性實(shí)驗(yàn)）
一、實(shí)驗(yàn)?zāi)康?/p>
1.掌握稀疏矩陣的壓縮存儲(chǔ) 2.掌握稀疏矩陣的轉(zhuǎn)置算法
二、實(shí)驗(yàn)內(nèi)容
1.實(shí)現(xiàn)上三角陣的壓縮存儲(chǔ)。
2.用三元組順序表存儲(chǔ)稀疏矩陣，并實(shí)現(xiàn)矩陣的轉(zhuǎn)置。
三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦
四、實(shí)驗(yàn)步驟
1.創(chuàng)建一個(gè)數(shù)組。2.輸入數(shù)據(jù)
3.給定矩陣任一元素的下標(biāo)，4.打印給定下標(biāo)所對(duì)應(yīng)的數(shù)據(jù)。5.創(chuàng)建三元組順序表。?a22 7.A輸出對(duì)應(yīng)的矩陣。??
21五、實(shí)驗(yàn)提示 ?aaa6.輸入矩陣中的數(shù)據(jù)。?11?a11??a?313233a2122?1.對(duì)于如下對(duì)稱矩陣： ??A?aaa?4243?41?a31a32a33??1個(gè)位置，a21存入到第二個(gè)位置，?將它們存入到一個(gè)線性數(shù)組中B，不存非零元素，a11存入到第a41a42aija44????aij的位則aij能存到第幾個(gè)位置，我們要以用梯形公式算面積。置是它上面的元素之和再加上左邊的元素之和。
它上面的元素之和為((1+(i-1))×(i-1)/2，左邊的元素為(j-1)所以這個(gè)元素存儲(chǔ)的位置為k=i(i-1)/2+j-1。
因?yàn)榫仃嘇為對(duì)稱矩陣，(另一部分沒(méi)有寫(xiě)出)，所以另一部分的元素為 k=j(j-1)/2+i-1.所以存在關(guān)系k=i(i-1)/2+j-1(i>j)和k=j(j-1)/2+i-1(i 2.結(jié)點(diǎn)結(jié)構(gòu) struct triple{ int i,j;//非零元的行下標(biāo)和列下標(biāo) elemtype e;//非零元數(shù)據(jù)} 三元組順序表存儲(chǔ)類型 struct tsmatrix{ triple data[12500];aa?????a44?? int mu,nu,tu;} 三元順序表的轉(zhuǎn)置 方法：(1)將矩陣行列互換，(2)重排矩陣 六、實(shí)驗(yàn)總結(jié)與思考 1.如何存儲(chǔ)三對(duì)角陣？ 2.如何用行邏輯鏈接順序表及十字鏈表存儲(chǔ)稀疏矩陣？ 實(shí)驗(yàn)三 樹(shù)與二叉樹(shù)（設(shè)計(jì)性實(shí)驗(yàn)） 一、實(shí)驗(yàn)?zāi)康?/p> 1.掌握稀疏矩陣的壓縮存儲(chǔ) 2.掌握稀疏矩陣的轉(zhuǎn)置算法 二、實(shí)驗(yàn)內(nèi)容 1.練習(xí)二叉樹(shù)的建立與存儲(chǔ) 2.練習(xí)二叉樹(shù)的遍歷 三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦 四、實(shí)驗(yàn)步驟 1.建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。 2.建立二叉樹(shù),并通過(guò)調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。 五、實(shí)驗(yàn)提示 建立二叉樹(shù)的代碼如下： BTCHINALR * createbt(){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf(“建立二叉樹(shù)，輸入結(jié)點(diǎn)對(duì)應(yīng)的編號(hào)和值,編號(hào)和值之間用逗號(hào)隔開(kāi)nn”);printf(“i,x = ”);scanf(“%d,%c”,&i,&x);while(i!= 0 && x!= '$') {q =(BTCHINALR*)malloc(sizeof(BTCHINALR));/*建立一個(gè)新結(jié)點(diǎn)q*/ q->data = x;q->lchild = NULL;q->rchild = NULL; s[i] = q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/ if(i!= 1)/*i = 1，對(duì)應(yīng)的結(jié)點(diǎn)是根結(jié)點(diǎn)*/ {j = i / 2;/*求雙親結(jié)點(diǎn)的編號(hào)j*/ if(i % 2 == 0)s[j]->lchild = q;/*q結(jié)點(diǎn)編號(hào)為偶數(shù)則掛在雙親結(jié)點(diǎn)j的左邊*/ else s[j]->rchild = q;} /*q結(jié)點(diǎn)編號(hào)為奇數(shù)則掛在雙親結(jié)點(diǎn)j的右邊*/ printf(“i,x = ”); scanf(“%d,%c”,&i,&x);} return s[1];/*返回根結(jié)點(diǎn)地址*/ } 六、實(shí)驗(yàn)總結(jié)與思考 1.如何用孩子兄弟表示法存儲(chǔ)樹(shù)？ 2.熟悉及難赫夫曼樹(shù)。 實(shí)驗(yàn)四 排序（設(shè)計(jì)性實(shí)驗(yàn)） 一、實(shí)驗(yàn)?zāi)康?/p> 1.掌握常用的排序方法，并掌握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法； 2.深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用； 3.了解各種方法的排序過(guò)程及其時(shí)間復(fù)雜度的分析方法。 二、實(shí)驗(yàn)內(nèi)容 統(tǒng)計(jì)成績(jī) 給出n個(gè)學(xué)生的考試成績(jī)表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個(gè)算法： （1）按分?jǐn)?shù)高低次序，打印出每個(gè)學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；（2）按名次列出每個(gè)學(xué)生的姓名與分?jǐn)?shù)。 三、實(shí)驗(yàn)儀器設(shè)備與器材 上機(jī)電腦 四、實(shí)驗(yàn)步驟 1.定義結(jié)構(gòu)體。2.定義結(jié)構(gòu)體數(shù)組。 3.定出主程序，對(duì)數(shù)據(jù)進(jìn)行排序。 五、實(shí)驗(yàn)提示 #define n 30 typedef struct student { char name[8];int score;} student R[n];main(){ int num, i, j, max, temp;printf(“n請(qǐng)輸入學(xué)生成績(jī): n”);for(i=0;i if(max!=i){ temp = R[max];R[max]=R[i];R[i]= temp;} if((i>0)&&(R[i].score 六、實(shí)驗(yàn)總結(jié)與思考 1.快速排序算法解決本問(wèn)題。2.較各種排序算法的優(yōu)缺點(diǎn)及。 3.使用其它排序算法實(shí)現(xiàn)該問(wèn)題（直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序等）。
點(diǎn)擊咨詢 