第一篇：數(shù)據(jù)結(jié)構(gòu)與算法-教學(xué)編制
目 錄
1.需求分析.........................................錯誤！未定義書簽。2.概要設(shè)計.........................................錯誤！未定義書簽。3.詳細(xì)設(shè)計.........................................錯誤！未定義書簽。4.測試分析.........................................錯誤！未定義書簽。課程設(shè)計總結(jié).......................................錯誤！未定義書簽。參考文獻...........................................錯誤！未定義書簽。
1.需求分析
根據(jù)課程之間的依賴關(guān)系制定課程安排計劃，輸入課程數(shù)及課程之間的關(guān)系。需要利用代碼實現(xiàn)排序，以及對各個學(xué)期課程安排進行排序并輸出。
1.1問題描述
大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等，每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。
1.2設(shè)計思路
首先利用拓?fù)渑判驅(qū)φn程先后順序進行分析，鄰接表位主要存儲結(jié)構(gòu)，棧為主要輔助結(jié)構(gòu)，給出課程之間的先后關(guān)系比如AOV網(wǎng)，然后進行拓?fù)渑判?，但?dāng)又向圖中存在環(huán)時，無法查找該圖的一個拓?fù)渑判?，?dāng)圖中的所有頂點全部輸出，表示對該圖排序成功，實現(xiàn)拓?fù)渑判蛩惴〞r，相應(yīng)的建立鄰接表存儲AOV網(wǎng)，為了避免重復(fù)檢測入度為零的頂點，建立一個棧來對入度為零的頂點進行存放。根據(jù)課程的先后關(guān)系，對個學(xué)期的課程進行排序，輸出。
1.3設(shè)計環(huán)境、原理
設(shè)計環(huán)境和器材： 硬件：計算機；軟件：Microsoft Visula C++。
設(shè)計原理說明：運用圖的拓?fù)渑判驅(qū)φn程先修排列的實現(xiàn)，并調(diào)用遞歸完成拓?fù)渑判颉?/p>
1.4實驗?zāi)康?/p>
培養(yǎng)學(xué)生用學(xué)到的書本知識解決實際問題的能力；培養(yǎng)實際工作所需要的動手能力；培養(yǎng)學(xué)生以科學(xué)理論和工程上能力的技術(shù)，規(guī)范地開發(fā)大型、復(fù)雜、高質(zhì)量的應(yīng)用軟件和系統(tǒng)軟件具有關(guān)鍵性作用。通過課程設(shè)計的實踐，學(xué)生可以在程序設(shè)計方法、上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。
1.5實驗內(nèi)容
針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。
2.概要設(shè)計：
2.1流程圖
void FindInDegree(ALGraph G, int indegree[])//求圖中各節(jié)點的入度（如下左圖）void CreatGraph(ALGraph *G)//構(gòu)件圖（如下右圖）。
void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)//有向圖G采用鄰接表存儲結(jié)構(gòu)(如下左圖)；
void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)//有向圖G采用鄰接表存儲結(jié)構(gòu)（如下右圖）。
主函數(shù)： void main()
2.2抽象數(shù)據(jù)類型圖的定義 ADT Graph{
數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點集.數(shù)據(jù)關(guān)系R: R={VR} VR={(v,w)|v,w∈V,(v,w)表示v和w之間存在直接先修關(guān)系} 基本操作P: void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int *);void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);}ADT Graph 棧的定義: ADT Stack{ 數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0} 數(shù)據(jù)關(guān)系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作: void InitStack(SqStack *S);int StackEmpty(SqStack S);void Push(SqStack *S, int);int Pop(SqStack *S, int *e);}ADT Stack 2.3主程序
int main()//主函數(shù) {
int numterm;//學(xué)期總數(shù)
int uplcredit;//一個學(xué)期的學(xué)分上限
int selectway;
ALGraph G;
printf(“請輸入學(xué)期總數(shù):n”);
scanf(“%d”,&numterm);
printf(“請輸入一個學(xué)期的學(xué)分上限:n”);
scanf(“%d”,&uplcredit);
CreatGraph(&G);
printf(“請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布n”);
scanf(“%d”,&selectway);
if(selectway==1)
TopologicalSort_1(G,numterm,uplcredit);
if(selectway==2)
TopologicalSort_2(G,numterm,uplcredit);
system(“pause”);
return 0;} 2.4本程序只有兩個模塊,調(diào)用關(guān)系簡單
主程序模塊→拓?fù)渑判蚰K
3.詳細(xì)設(shè)計
3.1頭結(jié)點、表結(jié)點、鄰接表的定義
#define MAX_VERTEX_NUM 100 //最大課程總數(shù) typedef struct ArcNode{ int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{ char name[24];
//課程名 int classid;
//課程號
int credit;
//課程的學(xué)分 int indegree;
//該結(jié)點的入度 int state;
//該節(jié)點的狀態(tài) ArcNode *firstarc;//指向第一條依附該頂點的弧的指針 }VNode,AdjList[MAX_VEXTEX_NUM];typedef struct{ AdjList vertices;int vexnum, arcnum;}ALGraph;鄰接表的基本操作：
void CreatGraph(ALGraph *);創(chuàng)建鄰接表
void FindInDegree(ALGraph , int *);求一個結(jié)點的入度
void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺砭幣耪n程
void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺砭幣耪n程
3.2棧的定義
#define STACk_INIT_SIZE 100 //存儲空間的初時分配量 #define STACKINCREMENT 10
//存儲空間的分配增量
typedef int ElemType;typedef struct { AdjList vertices;int vexnum, arcnum;}ALGraph;基本操作：
void InitStack(SqStack *S);棧的初始化
int StackEmpty(SqStack S);判斷棧是否為空
void Push(SqStack *S, int);入棧操作
int Pop(SqStack *S, int *e);出棧操作
3.3主程序和其他算法：
#include // exit()#include typedef int Boolean;// Boolean是布爾類型,其值是TRUE或FALSE #define MAX_NAME 10 /* 頂點字符串的最大長度 */ #define MAXCLASS 100 int Z=0;int X=0;int xqzs,q=1,xfsx;typedef int InfoType;typedef char VertexType[MAX_NAME];/* 字符串類型 */ /* 圖的鄰接表存儲表示 */ #define MAX_VERTEX_NUM 100 typedef enum{DG}GraphKind;/* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */ typedef struct ArcNode { int adjvex;/* 該弧所指向的頂點的位置 */ struct ArcNode *nextarc;/* 指向下一條弧的指針 */ InfoType *info;/* 網(wǎng)的權(quán)值指針）*/ } ArcNode;/* 表結(jié)點 */ typedef struct { VertexType data;/* 頂點信息 */ ArcNode *firstarc;/* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針 */ } VNode,AdjList[MAX_VERTEX_NUM];/* 頭結(jié)點 */ typedef struct { AdjList vertices,verticestwo;int vexnum,arcnum;/* 圖的當(dāng)前頂點數(shù)和弧數(shù) */ int kind;/* 圖的種類標(biāo)志 */ }ALGraph;/* 圖的鄰接表存儲的基本操作 */ int LocateVex(ALGraph G,VertexType u){ /* 初始條件: 圖G存在,u和G中頂點有相同特征 */ /* 操作結(jié)果: 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1 */ int i;for(i=0;i void FindInDegree(ALGraph G,int indegree[]){ /* 求頂點的入度，算法調(diào)用 */ int i;ArcNode *p;for(i=0;i (SElemType));if(!(*S).base)exit(OVERFLOW);/* 存儲分配失敗 */(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e;return OK;} typedef int pathone[MAXCLASS];typedef int pathtwo[MAXCLASS];Status TopologicalSort(ALGraph G){ /* 有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點的一個拓?fù)湫蛄胁⒎祷豋K, */ /* 否則返回ERROR。*/ int i,k,j=0,count,indegree[MAX_VERTEX_NUM];SqStack S;pathone a;pathtwo b;ArcNode *p;FindInDegree(G,indegree);/* 對各頂點求入度indegree[0..vernum-1] */ InitStack(&S);/* 初始化棧 */ for(i=0;i while(q<=xqzs){ int C=0;if(X<=G.arcnum){ while(C<=xfsx){C+=*G.verticestwo[Z].data;++Z;} printf(“第%d個學(xué)期應(yīng)學(xué)課程:”,q);while(X<=Z){cout<<*G.vertices[X].data<<“ ”;++X;} cout< 4.用戶使用和說明 使用VC++，打開sjjg.cpp文件，接著編譯，無錯誤，然后重建也沒有錯誤，最后執(zhí)行該文件。顯示如下圖： 要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排課程總數(shù)、課程名、課程號、該課程的學(xué)分，按照出現(xiàn)的每一步來輸入該課程設(shè)計所提供的相關(guān)數(shù)據(jù)。然后還要輸入課程先修課程總數(shù)，依據(jù)教科書圖7．26，可以算出有16種關(guān)系，分別輸出如下圖所示。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進行選擇，有兩種編排策略，最后結(jié)果體現(xiàn)在實驗的正確測試結(jié)果里（如上圖）。 5.調(diào)試分析 5.1實驗過程中出現(xiàn)的問題及解決方法 我們在實驗過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴?，對于課程設(shè)計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。 5.2測試數(shù)據(jù) 學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序為2，3，4，3，2，3，4，4，7，5，2，3。 5.3測試結(jié)果（包含正確和錯誤的） 正確測試結(jié)果： 錯誤測試結(jié)果： 5.4測試數(shù)據(jù)及程序運行情況 輸入的內(nèi)容如下: 課程編號 課程名稱 學(xué)分 先決條件 01 程序設(shè)計基礎(chǔ) 無 02 離散數(shù)學(xué) 01 03 數(shù)據(jù)結(jié)構(gòu) 01，02 04 匯編語言 01 05 語言的設(shè)計和分析 03，04 06 計算機原理 07 編譯原理 05，03 08 操作系統(tǒng) 03，06 09 高等數(shù)學(xué) 無 10 線性代數(shù) 09 11 普通物理 09 12 數(shù)值分析 09，10，01 兩種編排方法都輸出結(jié)果為: 第一學(xué)期學(xué)的課程有:高等數(shù)學(xué)程序設(shè)計基礎(chǔ)； 第二學(xué)期學(xué)的課程有:普通物理 線性代數(shù) 匯編語言； 第三學(xué)期學(xué)的課程有:數(shù)值分析 計算機原理 離散數(shù)學(xué)； 第四學(xué)期學(xué)的課程有:數(shù)據(jù)結(jié)構(gòu)； 第五學(xué)期學(xué)的課程有:操作系統(tǒng) 語言的設(shè)計和分析； 第六學(xué)期學(xué)的課程有:編譯原理。 6.總結(jié) 剛開始學(xué)的時候確實有很多地方我很不理解，每次上課時老師都會給我們出不同的設(shè)計題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。老師會給我們需要編程的內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計，我們可以開始運行自己的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤，但是程序還是得繼續(xù)下去，我多次請教了老師和同學(xué)，逐漸能自己找出錯誤，并加以改正。經(jīng)過了這次課程設(shè)計，現(xiàn)在已經(jīng)可以了解很多錯誤在英文里的提示，這對我來說是一個突破性的進步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心。此次的程序設(shè)計能夠成功，是我和我的同學(xué)三個人共同努力作用的結(jié)果。在這一段努力學(xué)習(xí)的過程中，我們的編程設(shè)計有了明顯的提高。 其實現(xiàn)在想起來，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費了好多心血，覺得它很難，是需用花費了大量的時間編寫出來的。現(xiàn)在真正的明白了一些代碼的應(yīng)用，每個程序都有一些共同點，通用的結(jié)構(gòu)，相似的格式。同時也對教學(xué)編制問題有了進一步的認(rèn)識。只要努力去學(xué)習(xí)，就會靈活的去應(yīng)用它。 7.參考文獻 ［1］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003。［2］《數(shù)據(jù)結(jié)構(gòu)題集》，嚴(yán)蔚敏，清華大學(xué)出版社，2005。［3］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），劉大有，高等教育出版社，2004。［4］《Data Structure with C++》，William Ford．William Topp，清華大學(xué)出版社，2003。 算法與數(shù)據(jù)結(jié)構(gòu)總結(jié) 算法與數(shù)據(jù)結(jié)構(gòu)這一門課程，就是描述了數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，以及數(shù)據(jù)的運算集合在計算機中的運用和體現(xiàn)。數(shù)據(jù)的邏輯結(jié)構(gòu)就是數(shù)據(jù)與數(shù)據(jù)之間的邏輯結(jié)構(gòu)；數(shù)據(jù)的存儲結(jié)構(gòu)就包含了順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存儲。在這學(xué)期當(dāng)中，老師給我們主要講了順序存儲和鏈?zhǔn)酱鎯ΑＷ詈髷?shù)據(jù)的運算集合就是對于一批數(shù)據(jù)，數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的，而運算的具體實現(xiàn)依賴于數(shù)據(jù)的存儲結(jié)構(gòu)。 通過這學(xué)期的學(xué)習(xí)，讓我在去年C語言的基礎(chǔ)上對數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系有了更深的理解和認(rèn)識。以前在學(xué)Matlab這一課程的時候，我們?nèi)绻獙崿F(xiàn)兩個數(shù)的加減乘除，或者一系列復(fù)雜的數(shù)據(jù)運算，就直接的調(diào)用函數(shù)就行，套用規(guī)則符號和運算格式，就能立馬知道結(jié)果。在學(xué)習(xí)C語言這一課程時，我們逐漸開始了解函數(shù)的調(diào)用的原理，利用子函數(shù)中包含的運算規(guī)則，從而實現(xiàn)函數(shù)的功能。現(xiàn)今學(xué)習(xí)了算法，讓我更深層次的知道了通過順序表、指針、遞歸，能讓數(shù)據(jù)算法的實現(xiàn)更加的簡潔，明了，更易于理解。摒棄了數(shù)據(jù)的冗雜性。 在本書第二章中，主要介紹了順序表的實現(xiàn)以及運用。順序表中我認(rèn)為最重要的是一個實型數(shù)組，和順序表的表長，不論是在一個數(shù)據(jù)的倒置、插入、刪除以及數(shù)據(jù)的排序過程中，都能將數(shù)據(jù)依次存入數(shù)組當(dāng)中，利用數(shù)組下標(biāo)之間的關(guān)系，就能實現(xiàn)數(shù)據(jù)的一系列操作了。在存儲棧中，給我留下最深刻的映像就是“先進后出”，由于它特殊的存儲特性，所以在括號的匹配，算術(shù)表達式中被大量應(yīng)用。在存儲隊列之中，數(shù)據(jù)的刪除和存儲分別在表的兩端進行操作，所以存儲數(shù)據(jù)很方便。為節(jié)省隊列浪費閑置空間的這一大缺點，所以引入了循環(huán)隊列這一概念，很好用。 在第三章中，主要講的是鏈?zhǔn)酱鎯μ匦?。它最突出的?yōu)點就是可以選擇連續(xù)或者不連續(xù)的存儲空間都行。所以，不管是數(shù)據(jù)在插入或者刪除一個數(shù)據(jù)時，會很方便，不會像順序表那樣，要移動數(shù)組中的諸多元素。所以鏈表利用指針能很方便的進行刪除或者插入操作。而鏈?zhǔn)皆跅：完犃械幕A(chǔ)上，也有了多方面的應(yīng)用，所以在這些方面有了更多的應(yīng)用。 第四章字符串中，基本的數(shù)組內(nèi)部元素的排序和字符串的匹配大部分代碼自己還是能夠理解，能夠看懂，如果真的要將所學(xué)的大量運用于實踐的話，那就要多花些功夫和時間了。在對稱矩陣的壓縮，三角矩陣的壓縮，稀疏矩陣在存儲中能夠合理的進行，能大大提高空間的開支。 在第五章遞歸當(dāng)中，就是在函數(shù)的定義之中出現(xiàn)了自己本身的調(diào)用，稱之為遞歸。而遞歸設(shè)計出來的程序，具有結(jié)構(gòu)清晰，可讀性強，便于理解等優(yōu)點。但是由于遞歸在執(zhí)行的過程中，伴隨著函數(shù)自身的多次調(diào)用，因而執(zhí)行效率較低。如果要在追求執(zhí)行效率的情況下，往往采用非遞歸方式實現(xiàn)問題的算法程序。 在第六章數(shù)型結(jié)構(gòu)當(dāng)中，這是區(qū)別于線性結(jié)構(gòu)的另一大類數(shù)據(jù)結(jié)構(gòu)，它具有分支性和層次性。它是數(shù)據(jù)表示，信息組織和程序設(shè)計的基礎(chǔ)和工具。在本章中，映像深刻的是樹的存儲結(jié)構(gòu)。有雙親表示法，孩子表示法，以及孩子兄弟表示法。在表示怎樣存儲數(shù)據(jù)之后，接著要從數(shù)型結(jié)構(gòu)中將數(shù)據(jù)讀取出來，于是，有了樹的遍歷，在遍歷當(dāng)中，又分為前序、中序和后序遍歷，這三種遍歷各有各的特點。 在第七章中，說到了樹的擴展---二叉樹。二叉樹不同一般的樹型結(jié)構(gòu)的另一種重要的非線性結(jié)構(gòu)，它是處理兩種不同的數(shù)據(jù)結(jié)構(gòu)，許多涉及樹的算法采用二叉樹表示和處理更加便捷和方便。其他的也是和一般的二叉樹差不多。還多了一個樹、森林和二叉樹之間的轉(zhuǎn)換。 第八章的圍繞著圖來展開，它是一種復(fù)雜的非線性結(jié)構(gòu)，在人工智能、網(wǎng)絡(luò)工程、數(shù)學(xué)、并行計算和工業(yè)設(shè)計有著廣泛的應(yīng)用。圖最重要的由一個非空的頂點集合和一個描述頂點之間的多對多關(guān)系的邊集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖的存儲室通過鄰接矩陣?yán)洗鎯D的信息。而圖的讀取是通過深度優(yōu)先遍歷和廣度優(yōu)先遍歷實現(xiàn)。生成最小生成樹有Prim算法和Kruskal算法，相對于這兩種算法，后一種算法要更加易于理解。 在考試的時候，我以為老師只會出題作業(yè)部分。然后書中有一小部分就沒看，但是題中出現(xiàn)了一個二叉樹轉(zhuǎn)換為森林的時候，我有印象，但就是沒思路想法了，就沒做。從中我真的理解了老師說的，考試不代表學(xué)習(xí)的結(jié)束?；蛘吣悻F(xiàn)在看的內(nèi)容在生活中學(xué)習(xí)中暫時沒有太大的作用，但是到了某一特定的環(huán)境條件下，總會有作用。所以，學(xué)習(xí)是一個積累的過程，不懈怠，踏實的走下去，你才會有所收獲。 金陵科技學(xué)院實驗報告 學(xué) 生 實 驗 報 告 冊 課程名稱： 學(xué)生學(xué)號： 所屬院部： （理工類） 算法與數(shù)據(jù)結(jié)構(gòu) 專業(yè)班級： 13網(wǎng)絡(luò)工程 1305106009 學(xué)生姓名： 陳韜 網(wǎng)絡(luò)與通信工程學(xué)院 指導(dǎo)教師： 沈奇 14 ——20 15 學(xué)年 第 1 學(xué)期 金陵科技學(xué)院教務(wù)處制 金陵科技學(xué)院實驗報告 實驗報告書寫要求 實驗報告原則上要求學(xué)生手寫，要求書寫工整。若因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙張一律采用A4的紙張。 實驗報告書寫說明 實驗報告中一至四項內(nèi)容為必填項，包括實驗?zāi)康暮鸵螅粚嶒瀮x器和設(shè)備；實驗內(nèi)容與過程；實驗結(jié)果與分析。各院部可根據(jù)學(xué)科特點和實驗具體要求增加項目。 填寫注意事項 （1）細(xì)致觀察，及時、準(zhǔn)確、如實記錄。（2）準(zhǔn)確說明，層次清晰。 （3）盡量采用專用術(shù)語來說明事物。 （4）外文、符號、公式要準(zhǔn)確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號。（5）應(yīng)獨立完成實驗報告的書寫，嚴(yán)禁抄襲、復(fù)印，一經(jīng)發(fā)現(xiàn)，以零分論處。 實驗報告批改說明 實驗報告的批改要及時、認(rèn)真、仔細(xì)，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標(biāo)準(zhǔn)由各院部自行制定。 實驗報告裝訂要求 實驗批改完畢后，任課老師將每門課程的每個實驗項目的實驗報告以自然班為單位、按學(xué)號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。 金陵科技學(xué)院實驗報告 實驗項目名稱： 順序表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗1 順序表 一、實驗?zāi)康暮鸵?/p> 掌握順序表的定位、插入、刪除等操作。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。 （2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回－1。編寫主函數(shù)測試結(jié)果。（3）在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。 解題思路：首先查找插入的位置，再移位，最后進行插入操作；從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。 （4）刪除順序表中所有等于X的數(shù)據(jù)元素。 2、選做題 （5）已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。 程序清單： #include 金陵科技學(xué)院實驗報告 } sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技學(xué)院實驗報告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技學(xué)院實驗報告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技學(xué)院實驗報告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技學(xué)院實驗報告 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 單鏈表 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗2 單鏈表 一、實驗?zāi)康暮鸵?/p> 1、實驗?zāi)康?/p> 掌握單鏈表的定位、插入、刪除等操作。 2、實驗要求 （1）注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進行物理刪除，以便釋放其內(nèi)存空間。 （2）鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止丟失。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。（2）在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。 解題思路：首先查找插入的位置然后進行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成插入操作。 （3）編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。 2、選做題 已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單： 金陵科技學(xué)院實驗報告 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 堆棧和隊列 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗3 堆棧和隊列 一、實驗?zāi)康暮鸵?/p> （1）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進行表達式求和的算法。 （3）掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）判斷一個算術(shù)表達式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。 （3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以’@’為結(jié)束符的字符序列是否是“回文”。 2、選做題 在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊列采取簡化的短作業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 串 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗4 串 一、實驗?zāi)康暮鸵?/p> 掌握串的存儲及應(yīng)用。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。 （2）編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。 解題思路：可以將第一題程序改進成一個子函數(shù)，在本題中循環(huán)調(diào)用。（3）設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。 2、選做題 假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。 提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計為從鍵盤輸入。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 二叉樹 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗5 二叉樹 一、實驗?zāi)康暮鸵?/p> （1）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）建立一棵二叉樹。對此樹進行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。 （2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點總數(shù)。（4）在第一題基礎(chǔ)上，求二叉樹的深度。 2、選做題 已知一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結(jié)點的值。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。 解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 圖 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗6 圖 一、實驗?zāi)康暮鸵?/p> （1）熟練掌握圖的基本概念、構(gòu)造及其存儲結(jié)構(gòu)。 （2）熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）構(gòu)造一個無向圖（用鄰接矩陣表示存儲結(jié)構(gòu)）。 （2）對上面所構(gòu)造的無向圖，進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。 2、選做題 采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復(fù)頂點的路徑。提示：兩個頂點及k值均作為參數(shù)給出。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 排序 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗7 排序 一、實驗?zāi)康暮鸵?/p> （1）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。 （2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 用隨機數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關(guān)鍵字值。測試下列各排序函數(shù)的機器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、堆排序。 2、選做題 假設(shè)含n個記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v…w]，令number[i]統(tǒng)計關(guān)鍵字為整數(shù)i的紀(jì)錄個數(shù)，然后按number重排序列以達到有序。試編寫算法實現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 金陵科技學(xué)院實驗報告 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 金陵科技學(xué)院實驗報告 實驗項目名稱： 查找 實驗學(xué)時： 2 同組學(xué)生姓名： 實驗地點： 實驗日期： 實驗成績： 批改教師： 批改時間： 金陵科技學(xué)院實驗報告 實驗8 查找 一、實驗?zāi)康暮鸵?/p> （1）掌握順序表查找、有序表查找、索引順序表查找的各種算法。（2）掌握哈希表設(shè)計。 二、實驗儀器和設(shè)備 Turbo C 2.0/ Visual C++ 三、實驗內(nèi)容與過程（含程序清單及流程圖） 1、必做題 （1）在一個遞增有序的線性表中利用二分查找法查找數(shù)據(jù)元素X。 2、選做題 （2）構(gòu)造一個哈希表，哈希函數(shù)采用除留余數(shù)法，哈希沖突解決方法采用鏈地址法。設(shè)計一個測試程序進行測試。 提示：構(gòu)造哈希表只是完成查找的第一步，大家應(yīng)該掌握在哈希表上進行查找的過程，可以試著編程序?qū)崿F(xiàn)。程序清單： 金陵科技學(xué)院實驗報告 四、實驗結(jié)果與分析（程序運行結(jié)果及其分析） 五、實驗體會（遇到問題及解決辦法，編程后的心得體會） 《數(shù)據(jù)結(jié)構(gòu)與算法》課程學(xué)習(xí)總結(jié)報告 100401200510計本（4）班章興春 本學(xué)期所學(xué)習(xí)的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落，就其知識點及其掌握情況、學(xué)習(xí)體會以及對該門課程的教學(xué)建議等方面進行學(xué)習(xí)總結(jié)。以便在所學(xué)習(xí)知識有更深刻的認(rèn)識。 一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識點： 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前、一直以為數(shù)據(jù)結(jié)構(gòu)是一門新的語言、后來才知道學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了更加高效的的組織數(shù)據(jù)、設(shè)計出良好的算法，而算法則是一個程序的靈魂。經(jīng)過了一學(xué)期的數(shù)據(jù)結(jié)構(gòu)了，在期末之際對其進行總結(jié)。首先，學(xué)完數(shù)據(jù)結(jié)構(gòu)我們應(yīng)該知道數(shù)據(jù)結(jié)構(gòu)講的是什么，數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的研究的程序設(shè)計問題中所出現(xiàn)的計算機處理對象以及它們之間關(guān)系和操作的學(xué)科。 第一章主要介紹了相關(guān)概念，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中，數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲結(jié)構(gòu)分為：順序存儲、鏈接存儲、索引存儲和散列存儲四類。最后著重介紹算法性能分析，包括算法的時間性能分析以及算法的空間性能分析。 第二章具體地介紹了順序表的定義、特點及其主要操作，如查找、插入和刪除的實現(xiàn)。需要掌握對它們的性能估計。包括查找算法的平均查找長度，插入與刪除算法中的對象平均移動次數(shù)。 鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動元素，給算法的效率帶來較大的提高。鏈表這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。 第三章介紹了堆棧與隊列這兩種運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進后出”的規(guī)則，對堆棧的操作只能在棧頂進行；而隊列要遵循“先進先出”的規(guī)則，教材中列出了兩種結(jié)構(gòu)的相應(yīng)算法，如入棧、出棧、入隊、出隊等。在介紹隊列時，提出了循環(huán)隊列的概念，以避免“假溢出”的現(xiàn)象。算法上要求掌握進棧、退棧、取棧頂元素、判?？蘸兄每諚５任宸N操作及掌握使用元素個數(shù)計數(shù)器及少用一個元素空間來區(qū)分隊列空、隊列滿的方法。 第四章串和數(shù)組中，我們知道串是一種特殊的線性表，是由零個或多個任意字符組成的字符序列。串的儲存結(jié)構(gòu)分為緊縮模式和非緊縮模式。 基本運算需掌握求串長、串賦值、連接操作、求子串、串比較、串定位、串插入、串刪除、串替換等。 第五章二叉樹的知識是重點內(nèi)容。在介紹有關(guān)概念時，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應(yīng)用：基本算法、哈弗曼樹、二叉排序樹和堆排序。 樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。 第六章介紹了圖的概念及其應(yīng)用，圖的存儲結(jié)構(gòu)的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點理解AOV網(wǎng)和拓?fù)渑判蚣捌渌惴ā?/p> 最后兩章集體說明了查找和排序算法，查找教材上介紹了靜態(tài)查找表和哈希查找表，靜態(tài)查找表中介紹了順序查找、折半查找以及分塊查找。哈希法中，學(xué)習(xí)要點包括哈希函數(shù)的比較；解決地址沖突的線性探查法的運用，平均探查次數(shù)；解決地址沖突的二次哈希法的運用。 排序是使用最頻繁的一類算法，可分為內(nèi)部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交換排序（包括冒泡排序算法、快速排序遞歸算法）,選擇排序（包括直接選擇排序算法、堆排序算法）等。 二、對各知識點的掌握情況 總體來看，對教材中的知識點理解較為完善，但各個章節(jié)均出現(xiàn)有個別知識點較為陌生的現(xiàn)象?，F(xiàn)將各個章節(jié)出現(xiàn)的知識點理解情況列舉如下。 第一章中我對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹，熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。而對算法的時間、空間性能分析較為模糊，尤其是空間性能分析需要加強。 第二章，順序表的概念、生成算法理解較為清晰，并且熟悉簡單順序查找和二分查找，對分塊查找較為含糊；排序問題中，由于冒泡排序在大一C語言課上已經(jīng)學(xué)習(xí)過，再來學(xué)習(xí)感覺很輕松。對插入排序和選擇排序理解良好，但是，在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習(xí)中感覺較吃力，現(xiàn)在對這種排序方法仍然非常模糊，所以需要花較多的時間來補習(xí)。此外串的模式匹配也是較難理解的一個地方。 鏈表這一章中，除對雙向循環(huán)鏈表這一知識點理解困難之外，其他的知識點像單鏈表的建立和基本算法等都較為熟悉。 接下來的有關(guān)堆棧以及隊列的知識點比較少，除有關(guān)算法較為特殊以外，其余算法都是先前學(xué)過的順序表和鏈表的知識，加上思想上較為重視，因此這部分內(nèi)容是我對全書掌握最好的一部分。不足之處仍然表現(xiàn)在算法的性能分析上。 在學(xué)習(xí)第六章時感覺較為吃力的部分在于矩陣的應(yīng)用上，尤其對矩陣轉(zhuǎn)置算法的C語言描述不太理解。稀疏矩陣相加算法中，用三元組表實現(xiàn)比較容易理解，對十字鏈表進行矩陣相加的方法較為陌生。 第七章是全書的重點，卻也有一些內(nèi)容沒有完全理解。在第一節(jié)基本概念中，二叉樹的性質(zhì)容易懂卻很難記憶。對二叉樹的存儲結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好，能夠熟練運用，而對于二叉樹應(yīng)用中的哈弗曼樹卻比較陌生。 第八章內(nèi)容較少，牽涉到所學(xué)的隊列的有關(guān)內(nèi)容，總體來說理解上沒有什么困難，問題依舊出現(xiàn)在算法的性能分析上。 散列結(jié)構(gòu)這一章理解比較完善的知識點有：基本概念和存儲結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學(xué)得比較扎實，對數(shù)字分析法等方法則感覺較為陌生。對兩種沖突處理的算法思想的理解良好，問題在于用C語言描述上。 最后一章，圖及其應(yīng)用中，圖的定義、基本運算如圖的生成等起初理解有困難，但隨著學(xué)習(xí)深入，對它的概念也逐步明朗起來。鄰接矩陣、鄰接表和逆鄰接表掌握較好，而對十字鏈表和鄰接多重表則較為陌生。感覺理解較為吃力的內(nèi)容還有圖的遍歷（包括深度和廣度優(yōu)先遍歷），最小生成樹問題也是比較陌生的知識點。最短路徑和AOV網(wǎng)學(xué)習(xí)起來感覺比較輕松，而對于C語言描述卻又不大明白。 由于平時上機練習(xí)的少，對于教材中很多算法都掌握的不是很熟悉、不過這些都是可以彌補的，我會在剩下的時間中不斷練習(xí)書上給出的算法和練習(xí)，正如教材上說的，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，僅從書本上學(xué)習(xí)是不夠的，必須經(jīng)過大量的程序設(shè)計實踐，在實踐中體會構(gòu)造性思維方法，掌握數(shù)據(jù)組織與程序設(shè)計技術(shù)。 三、學(xué)習(xí)體會： 多做實驗！這個就沒有太多理由了，我一直覺得編程是一門熟練科學(xué)，多編程，水平肯定會提高，最重要的是能夠養(yǎng)成一種感覺，就是對程序?qū)λ惴ǖ拿舾?，為什么那些牛人看一個算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了過了一陣子又忘記了？其實這個是因為牛人們以前看的程序很多，編得也很多，所以他們有了那種感覺，所以我覺得大家應(yīng)該多看程序，多寫程序，培養(yǎng)自己的感覺。 復(fù)習(xí)和考試的技巧，我想大家應(yīng)該都有這樣的感覺，就是覺得自己什么都掌握了，但是在考試的時候就是會犯暈，有時候一出考場就知道錯在哪個了，然后考完以后一對答案，發(fā)現(xiàn)其實考得很簡單，應(yīng)該都是自己會做的，這個就是與自己的復(fù)習(xí)和考試的技巧有關(guān)系了。 首先就是復(fù)習(xí)，前面已經(jīng)說過其實我們學(xué)的算法也就是幾十個，那么我們的任務(wù)也就是理解這幾十個算法，復(fù)習(xí)也就是要加深你的理解。如何理解算法，然后理解到什么程度呢？ 是能默出整個算法嗎？其實不是這樣的，數(shù)據(jù)結(jié)構(gòu)的考試有它的特點，考過程考試了，大家應(yīng)該都發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)其實不要求你把整個算法背出來，它注重考察你的理解，那么怎么考察呢？其實也就是兩種方式吧，一種就是用實例，就是給你一個例子，要你用某個算法運行出結(jié)果，我想這個期末考試的時候仍然會有很多這樣的題目，比如排序那塊就很好出這樣的題目，要復(fù)習(xí)這種題目我覺得很簡單，就是每個算法都自己用例子去實踐一下，以不變應(yīng)萬變，我期中復(fù)習(xí)的時候就是這樣去做的，而且考試之前我就覺得那個并查集的題目就很有可能會考，于是就自己出了幾個例子，做了一下。另外一種考察方式就是算法填空和算法改錯，可能有一些同學(xué)覺得這種題目很難，其實我們首先可以確定這兩種題目肯定是與書上算法有關(guān)系的，只要理解了書上的算法就可以了，有人覺得看完書以后什么都懂了，而且要默也默得出來，其實不是這樣的，算法改錯和填空主要是考察的細(xì)微處，雖然你覺得你默得出來，那是能夠默出算法的主體部分，很多細(xì)微的地方你就會很容易忽略。我想大家考過期中考以后應(yīng)該都有這種感覺吧？那要怎樣解決這種問題呢？ 我覺得有兩種方法，一種就是自己去編程實現(xiàn)，這種方法比較有意義，還能夠提高編程水平，另外一種就是用實例分析算法的每句話，我認(rèn)為這種方法是最有效的。 然后還有一種題目，就是最后的寫算法的題目，我覺得這種題目還是很好解決的，只要是能夠自己做出作業(yè)的，基本上都會很容易做出來，這也是為什么我前面覺得平時做作業(yè)應(yīng)該自己獨立思考的原因，同時做這種題目千萬要小心，尤其是題目簡單的時候，那肯定會有一些小地方要考慮清楚，一不小心就會被扣掉很多分，這樣很不值。 我覺得考試的時候沒有太多要講的，只要復(fù)習(xí)好了，考試的時候細(xì)心一點就可以了，然后就是做一個題目開始就要盡量保證正確，如果覺得留在那里等后面做完了再來檢查，這樣錯誤還是很有可能檢查不出來，我期中考試的時候就基本上沒有檢查，因為我做每個題目都是確保正確，用的時間也挺多的，然后也覺得沒有檢查的必要了。 三、對《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)的建議 1、建議在上課過程中加大隨堂練習(xí)的分量，以便學(xué)生能當(dāng)堂消化課堂上學(xué)習(xí)的知識，也便于及時了解學(xué)生對知識點的掌握情況，同時有助于學(xué)生保持良好的精神狀態(tài)。 2、建議在課時允許的情況下，增加習(xí)題課的分量，通過課堂的習(xí)題講解，加深對知識點的掌握，同時對各知識點的運用有一個更為直觀和具體的認(rèn)識。 3、要更加重視實驗的重要性。 以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學(xué)習(xí)總結(jié)，我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學(xué)習(xí)，克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進！ 《數(shù)據(jù)結(jié)構(gòu)與算法》課程學(xué)習(xí)總結(jié)報告 070401301507計本（3）班張浩 本學(xué)期開設(shè)的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落，現(xiàn)就其知識點及其掌握情況、學(xué)習(xí)體會以及對該門課程的教學(xué)建議等方面進行學(xué)習(xí)總結(jié)。 一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識點 在課本的第一章便交代了該學(xué)科的相關(guān)概念，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。其中，數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合。邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲結(jié)構(gòu)分為：順序存儲、鏈接存儲、索引存儲和散列存儲四類。緊接著介紹了一些常用的數(shù)據(jù)運算。最后著重介紹算法性能分析，包括算法的時間性能分析以及算法的空間性能分析。 第二章具體地介紹了順序表的概念、基本運算及其應(yīng)用。基本運算有：初始化表、求表長、排序、元素的查找、插入及刪除等。元素查找方法有：簡單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等。最后介紹了順序串的概念，重點在于串的模式匹配。 鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動元素，給算法的效率帶來較大的提高。鏈表這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。 堆棧與隊列是兩種運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進后出”的規(guī)則，對堆棧的操作只能在棧頂進行；而隊列要遵循“先進先出”的規(guī)則，教材中列出了兩種結(jié)構(gòu)的相應(yīng)算法，如入棧、出棧、入隊、出隊等。在介紹隊列時，提出了循環(huán)隊列的概念，以避免“假溢出”的現(xiàn)象。 第六章介紹了特殊矩陣和廣義表的概念與應(yīng)用。其中，特殊矩陣包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣，書中分別詳細(xì)介紹了它們的存儲結(jié)構(gòu)。稀疏矩陣的應(yīng)用包括轉(zhuǎn)置和加法運算等。最后介紹了廣義表的相關(guān)概念及存儲結(jié)構(gòu)，關(guān)于它的應(yīng)用，課本中舉了m元多項式的表示問題。 第七章二叉樹的知識是重點內(nèi)容。在介紹有關(guān)概念時，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應(yīng)用：基本算法、哈弗曼樹、二叉排序樹和堆排序。 樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識點有：散列結(jié)構(gòu)的概念及其存儲結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。 最后一章介紹了圖的概念及其應(yīng)用，是本書的難點。圖的存儲結(jié)構(gòu)的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應(yīng)用。有向無環(huán)圖重點理解AOV網(wǎng)和拓?fù)渑判蚣捌渌惴ā?/p> 二、對各知識點的掌握情況 總體來看，對教材中的知識點理解較為完善，但各個章節(jié)均出現(xiàn)有個別知識點較為陌生的現(xiàn)象?，F(xiàn)將各個章節(jié)出現(xiàn)的知識點理解情況列舉如下。 第一章中我對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹，熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。而對算法的時間、空間性能分析較為模糊，尤其是空間性能分析需要加強。 第二章，順序表的概念、生成算法理解較為清晰，并且熟悉簡單順序查找和二分查找，對分塊查找較為含糊；排序問題中，由于冒泡排序在大一C語言課上已經(jīng)學(xué)習(xí)過，再來學(xué)習(xí)感覺很輕松。對插入排序和選擇排序理解良好，但是，在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習(xí)中感覺較吃力，現(xiàn)在對這種排序方法仍然非常模糊，所以需要花較多的時間來補習(xí)。此外串的模式匹配也是較難理解的一個地方。 鏈表這一章中，除對雙向循環(huán)鏈表這一知識點理解困難之外，其他的知識點像單鏈表的建立和基本算法等都較為熟悉。 接下來的有關(guān)堆棧以及隊列的知識點比較少，除有關(guān)算法較為特殊以外，其余算法都是先前學(xué)過的順序表和鏈表的知識，加上思想上較為重視，因此這部分內(nèi)容是我對全書掌握最好的一部分。不足之處仍然表現(xiàn)在算法的性能分析上。 在學(xué)習(xí)第六章時感覺較為吃力的部分在于矩陣的應(yīng)用上，尤其對矩陣轉(zhuǎn)置算法的C語言描述不太理解。稀疏矩陣相加算法中，用三元組表實現(xiàn)比較容易理解，對十字鏈表進行矩陣相加的方法較為陌生。 第七章是全書的重點，卻也有一些內(nèi)容沒有完全理解。在第一節(jié)基本概念中，二叉樹的性質(zhì)容易懂卻很難記憶。對二叉樹的存儲結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好，能夠熟練運用，而對于二叉樹應(yīng)用中的哈弗曼樹卻比較陌生。 第八章內(nèi)容較少，牽涉到所學(xué)的隊列的有關(guān)內(nèi)容，總體來說理解上沒有什么困難，問題依舊出現(xiàn)在算法的性能分析上。 散列結(jié)構(gòu)這一章理解比較完善的知識點有：基本概念和存儲結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學(xué)得比較扎實，對數(shù)字分析法等方法則感覺較為陌生。對兩種沖突處理的算法思想的理解良好，問題在于用C語言描述上。 最后一章，圖及其應(yīng)用中，圖的定義、基本運算如圖的生成等起初理解有困難，但隨著學(xué)習(xí)深入，對它的概念也逐步明朗起來。鄰接矩陣、鄰接表和逆鄰接表掌握較好，而對十字鏈表和鄰接多重表則較為陌生。感覺理解較為吃力的內(nèi)容還有圖的遍歷（包括深度和廣度優(yōu)先遍歷），最小生成樹問題也是比較陌生的知識點。最短路徑和AOV網(wǎng)學(xué)習(xí)起來感覺比較輕松，而對于C語言描述卻又不大明白。 三、學(xué)習(xí)體會 接觸這門課程以前，我對該課程所學(xué)的內(nèi)容有許多疑點，例如：這門課是否是在介紹一種新的計算機語言？如果不是，那么學(xué)習(xí)這門課程的用途是什么？為什么市面上各種介紹數(shù)據(jù)結(jié)構(gòu)的資料采用了不同的計算機語言，如C、C++還有Java？我的C語言學(xué)得不好，對學(xué)習(xí)這門課是否有影響?? 在學(xué)習(xí)伊始，老師就明確提出它不是一種計算機語言，不會介紹新的關(guān)鍵詞，而是通過學(xué)習(xí)可以設(shè)計出良好的算法，高效地組織數(shù)據(jù)。一個程序無論采用何種語言，其基本算法思想不會改變。聯(lián)系到在大一和大二上學(xué)期學(xué)習(xí)的C和C++語言，我深刻認(rèn)識到了這一點?！败浖_發(fā)好比寫作文，計算機語言提供了許多華麗的辭藻，而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來?！痹趯W(xué)習(xí)這門課中，要熟悉對算法思想的一些描述手段，包括文字描述、圖形描述和計算機語言描述等。因此，計算機語言基礎(chǔ)是必須的，因為它提供了一種重要的算法思想描述手段——機器可識別的描述。 這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上的知識與老師的講解都比較容易理解，但是當(dāng)自己采用剛學(xué)的知識點編寫程序時卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后，只能將書本上原有的程序段謄寫到 自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況，我會嚴(yán)格要求自己，熟練掌握算法思想，盡量獨立完成程序的編寫與修改工作，只有這樣，才能夠提高運用知識，解決問題的能力。 四、對《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)的建議 1、建議在上課過程中加大隨堂練習(xí)的分量，以便學(xué)生能當(dāng)堂消化課堂上學(xué)習(xí)的知識，也便于及時了解學(xué)生對知識點的掌握情況，同時有助于學(xué)生保持良好的精神狀態(tài)。 2、建議在課時允許的情況下，增加習(xí)題課的分量，通過課堂的習(xí)題講解，加深對知識點的掌握，同時對各知識點的運用有一個更為直觀和具體的認(rèn)識。 以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學(xué)習(xí)總結(jié)，我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學(xué)習(xí)，克服學(xué)習(xí)中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進！第二篇：算法與數(shù)據(jù)結(jié)構(gòu)總結(jié)
第三篇：算法與數(shù)據(jù)結(jié)構(gòu)實驗
第四篇：數(shù)據(jù)結(jié)構(gòu)與算法總結(jié)
第五篇：數(shù)據(jù)結(jié)構(gòu)與算法總結(jié)
點擊咨詢 