在日常學習、工作或生活中，大家總少不了接觸作文或者范文吧，通過文章可以把我們那些零零散散的思想，聚集在一塊。范文怎么寫才能發揮它最大的作用呢？接下來小編就給大家介紹一下優秀的范文該怎么寫，我們一起來看一看吧。

數據結構c語言版篇一

#include #include typedef int keytype;

typedef struct node{

keytype key;

struct node *lchild,*rchild;

}bstnode;

typedef bstnode *bstree;

bstree createbst(void);

void searchbst(bstree t,keytype key);

void insertbst(bstree *tptr,keytype key);

void delbstnode(bstree *tptr,keytype key);

void inorderbst(bstree t);

main()

{bstree t;

char ch1,ch2;

keytype key;

printf(“建立一棵二叉排序樹的二叉鏈表存儲n”);

t=createbst();

ch1='y';

while(ch1=='y' || ch1=='y')

{printf(“請選擇下列操作：n”);

printf(“1------------------更新二叉排序樹存儲n”);

printf(“2------------------二叉排序樹上的查找n”);

printf(“3------------------二叉排序樹上的插入n”);

printf(“4------------------二叉排序樹上的刪除n”);

printf(“5------------------二叉排序樹中序輸出n”);

printf(“6------------------退出n”);

scanf(“n%c”,&ch2);

switch(ch2)

{case '1':t=createbst();break;

case '2':printf(“n請輸入要查找的數據：”);

scanf(“n%d”,&key);

searchbst(t,key);

printf(“查找操作完畢。n”);break;

case '3': printf(“n請輸入要插入的數據：”);

scanf(“n%d”,&key);

insertbst(&t,key);

printf(“插入操作完畢。n”);break;

case '4': printf(“n請輸入要刪除的數據：”);

scanf(“n%d”,&key);

delbstnode(&t,key);

printf(“刪除操作完畢。n”);break;

case '5': inorderbst(t);

printf(“n二叉排序樹輸出完畢。n”);break;

case '6':ch1='n';break;

default:ch1='n';

}

}

}

bstree createbst(void)

{bstree t;

keytype key;

t=null;

printf(“請輸入一個關鍵字(輸入0時結束輸入)：n”);scanf(“%d”,&key);

while(key)

{insertbst(&t,key);

printf(“請輸入下一個關鍵字(輸入0時結束輸入)：n”);scanf(“n%d”,&key);

}

return t;

}

void searchbst(bstree t, keytype key)

{ bstnode *p=t;

while(p)

{if(p->key==key)

{printf(“已找到n”);

return;

}

p=(key

key)? p->lchild:p->rchild;

}

printf(“沒有找到n”);

}

void insertbst(bstree *t,keytype key)

{bstnode *f,*p;

p=(*t);

while(p)

{if(p->key==key)

{printf(“樹中已有key不需插入n”);

return;

}

f=p;

p=(key

key)?p->lchild:p->rchild;

}

p=(bstnode*)malloc(sizeof(bstnode));

p->key=key;

p->lchild=p->rchild=null;

if((*t)==null)(*t)=p;

else if(key

key)f->lchild=p;

else f->rchild=p;

}/*insertbst*/

void delbstnode(bstree *t,keytype key)

{bstnode *parent=null, *p, *q,*child;

p=*t;

while(p)

{if(p->key==key)break;

parent=p;

p=(key

key)?p->lchild:p->rchild;

}

if(!p){printf(“沒有找到要刪除的結點n”);return;}

q=p;

if(q->lchild && q->rchild)

for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;

if(!parent)*t=child;

else {if(p==parent->lchild)

parent->lchild=child;

else parent->rchild=child;

if(p!=q)

q->key=p->key;

}

free(p);

}

void inorderbst(bstree t){ if(t!=null)

{inorderbst(t->lchild);printf(“%5d”,t->key);inorderbst(t->rchild);}

}

數據結構c語言版篇二

實驗：線性表的基本操作

【實驗目的】

學習掌握線性表的順序存儲結構、鏈式存儲結構的設計與操作。對順序表建立、插入、刪除的基本操作，對單鏈表建立、插入、刪除的基本操作算法。

【實驗內容】

1.順序表的實踐

1)建立4個元素的順序表s=sqlist[]={1，2，3，4，5}，實現順序表建立的基本操作。

2)在sqlist []={1，2，3，4，5}的元素4和5之間插入一個元素9，實現順序表插入的基本操作。

3)在sqlist []={1，2，3，4，9，5}中刪除指定位置（i=5）上的元素9，實現順序表的刪除的基本操作。2.單鏈表的實踐

3.1)建立一個包括頭結點和4個結點的（5，4，2，1）的單鏈表，實現單鏈表建立的基本操作。

2)將該單鏈表的所有元素顯示出來。

3)在已建好的單鏈表中的指定位置（i=3）插入一個結點3，實現單鏈表插入的基本操作。

4)在一個包括頭結點和5個結點的（5，4，3，2，1）的單鏈表的指定位置（如i=2）刪除一個結點，實現單鏈表刪除的基本操作。5)實現單鏈表的求表長操作。

【實驗步驟】

1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

線性是我們學習數據結構中，碰到的第一個數據結構。學習線性表的重點掌握順序表和單鏈表的各種算法和時間性能分析。線性表右兩種存儲方式即順序存儲結構和鏈式存儲結構。通過學習我知道了對線性表進行建立、插入、刪除，同時單鏈表也是進行建立、插入、刪除。而對于順序表的插入刪除運算，其平均時間復雜度均為0（n）.通過這次的學習，掌握的太熟練，主要是課本上的知識點沒有徹底的理解，回去我會多看書，理解重要的概念?？傊?，這次實驗我找到了自己的不足之處，以后會努力的。

實驗二：棧的表示與實現及棧的應用

【實驗目的】

（1）掌握棧的順序存儲結構及其基本操作的實現。（2）掌握棧后進先出的特點，并利用其特性在解決實際問題中的應用。（3）掌握用遞歸算法來解決一些問題。【實驗內容】

1.編寫程序，對于輸入的任意一個非負十進制整數，輸出與其等值的八進制數。

2.編寫遞歸程序，實現n！的求解。3.編寫遞歸程序，實現以下函數的求解。

n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1

4.編寫程序，實現hanoi塔問題?！緦嶒灢襟E】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

通過這次的學習我掌握了棧這種抽象數據類型的特點，并能在相應的應用任務中正確選用它；總的來說，棧是操作受限的線性表，是限定僅在表尾進行插入或刪除操作的線性表。因此，對棧來說，表尾端有其特殊含義，稱為棧頂（top），相應地，表頭端稱為棧底（botton）；棧又稱為后進先出（last in first out）的線性表,簡稱lifo結構，因為它的修改是按后進先出的原則進行的。

加上這個實驗，我已經學了線性表（順序表，單鏈表）和棧，知道它們都是線性表，而且對以后的學習有很大的作用，可以說這是學習以后知識的總要基礎。

實驗三：二叉樹的建立及遍歷

【實驗目的】

（1）掌握利用先序序列建立二叉樹的二叉鏈表的過程。（2）掌握二叉樹的先序、中序和后序遍歷算法。【實驗內容】

1.編寫程序，實現二叉樹的建立，并實現先序、中序和后序遍歷。如：輸入先序序列abc###de###，則建立如下圖所示的二叉樹。

并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實驗步驟】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

【實驗心得】

這次試驗是關于二叉樹的常見操作，主要是二叉樹的建立和遍歷，在這次實驗中我按先序方式建立二叉樹的，而遍歷方式則相對要多一些，有遞歸的先序、中序、后序遍歷，和非遞歸的先序、中序、后序遍歷，此外還有層次遍歷.二叉樹高度和葉子個數的計算和遍歷相差不大，只是加些判斷條件，總體來說，本次試驗不太好做，期間出現了很多邏輯錯誤，變量初始化的問題等，不過經過仔細排查最后都一一解決了。

實驗四：查找與排序

【實驗目的】

（1）掌握折半查找算法的實現。（2）掌握冒泡排序算法的實現?！緦嶒瀮热荨?/p>

1.編寫折半查找程序，對以下數據查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.編寫冒泡排序程序，對以下數據進行排序。49，38，65，97，76，13，27，49 【實驗步驟】 1.打開vc++。

2.建立工程：點file->new，選project標簽，在列表中選win32 console application，再在右邊的框里為工程起好名字，選好路徑，點ok->finish。至此工程建立完畢。

3.創建源文件或頭文件：點file->new，選file標簽，在列表里選c++ source file。給文件起好名字，選好路徑，點ok。至此一個源文件就被添加到了你剛創建的工程之中。

4．寫好代碼

5．編譯－＞鏈接－＞調試

（1）查找算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st){ int i,n;

=

(elemtype*)

malloc(elemtype));

if(!)return(overflow);

printf(“輸入元素個數和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

(maxnum*sizeof

scanf(“%d”,&[i]);}

= n;

return ok;} int seq_search(sstable st,elemtype key){

int i;

[0]=key;

for(i=;[i]!=key;--i);

return i;} int binarysearch(sstable st,elemtype key){

int mid,low,high,i=1;

low=1;

high=;

while(low<=high)

{

mid=(low+high)/2;

if([mid]==key)

return mid;

else if(key

high=mid-1;

else

}

return 0;} void main(){ sstable st;initlist(st);

elemtype key;int n;printf(“ key= ”);

scanf(“%d”,&key);

printf(“nn”);

/*printf(“after seqsearch:: ”);

n=seq_search(st,key);

printf(“position is in %d nn”,n);*/

printf(“after binary search::”);

n=binarysearch(st,key);

low=mid+1;if(n)printf(“position is in %d nn”,n);else

} 實驗結果如下所示：

（2）排序算法的代碼如下所示： #include “stdio.h” #include “malloc.h” #define overflow-1 #define ok 1 #define maxnum 100 #define n 10 typedef int elemtype;typedef int status;typedef struct {

elemtype *elem;

int length;}sstable;status initlist(sstable &st)printf(“not in nn”);{ int i,n;

(elemtype));

if(!)return(overflow);

printf(“輸入元素個數和各元素的值:”);

scanf(“%dn”,&n);

for(i=1;i<=n;i++){

scanf(“%d”,&[i]);}

= n;

return ok;} void sort(sstable st){

int i,j,t;

for(i=1;i

for(j=i+1;j<=;j++)

if([i]>[j]){ t=[i];=

(elemtype*)

malloc

(maxnum*sizeof

}

} [i]=[j];[j]=t;void display(sstable st){ int i;

for(i=1;i<=;i++){

printf(“%d

”,[i]);}

} void main(){

sstable st;initlist(st);int n;printf(“before sort::n”);display(st);sort(st);printf(“nafter sort::n”);display(st);} 實驗結果如下所示：

【實驗心得】

通過這次實驗,我明白了程序里的折半查找和冒泡查找.其實排序可以有很多種，但是其目的應該都是為了能夠在海量的數據里迅速查找到你要的數據信息，折半查找是種比較快的方式，但前提是要是有 序的排序才可以。對于有序表，查找時先取表中間位置的記錄關鍵字和所給關鍵字進行比較，若相等，則查找成功；如果給定值比該記錄關鍵字大，則在后半部分繼續進行折半查找；否則在前半部分進行折半查找，直到查找范圍為空而查不到為止。折半查找的過程實際上死先確定待查找元素所在的區域，然后逐步縮小區域，直到查找成功或失敗為止。算法中需要用到三個變量，low表示區域下界，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.

數據結構c語言版篇三

數據結構參考題目

一、選擇

1.如果在數據結構中每個數據元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（）

a.棧 b.隊列 c.樹 d.圖 2.下面程序段的時間復雜度為（）for(i=0;i

next =hl;b.p->next=hl;hl=p;c.p->next=hl;p=hl;d.p->next=hl->next;hl->next=p;4.兩個字符串相等的條件是（）

a.串的長度相等 b.含有相同的字符集

c.都是非空串 d.串的長度相等且對應的字符相同 5．若以s和x分別表示進棧和退棧操作，則對初始狀態為空的?？梢赃M行的棧操作系列是（）

xx sx sx xx 6.已知一棵含50個結點的二叉樹中只有一個葉子結點，則該樹中度為1的結點個數為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對關鍵字序列（51，35，93，24，13，68，56，42，77）進行排序時，前兩趟排序的結果為

（35，51，24，13，68，56，42，77，93）

（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）

a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序

8.已知散列表的存儲空間為t[0..16]，散列函數h（key）=key%17,并用二次探測法處理沖突。散列表中已插入下列關鍵字：t[5]=39，t[6]=57和t[7]=7，則下一個關鍵字23插入的位置是（）

a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個子表，整個矩陣看成是一個廣義表l，即l=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通過求表頭head和求表尾tail的運算求取矩陣中的每一個元素，則求得a21的運算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個具有n個頂點的有向圖中，所有頂點的出度之和為dout，則所有頂點的入度之和為（）

-1 +1 d.n 11．從邏輯關系來看，數據元素的直接前驅為0個或1個的數據結構只能是（）a線性結構 b.樹形結構 c.線性結構和樹型結構 d.線性結構和圖狀結構

12．棧的插入和刪除操作在()進行。

a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）a.24 b.71 c.48 d.53 14．一個棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關于棧和隊列的說法中正確的是（）

a．棧和隊列都是線性結構 b.棧是線性結構，隊列不是線性結構 c.棧不是線性結構，隊列是線性結構 d.棧和隊列都不是線性結構 16．關于存儲相同數據元素的說法中正確的是（）a．順序存儲比鏈式存儲少占空間 b.順序存儲比鏈式存儲多占空間

c.順序存儲和鏈式存儲都要求占用整塊存儲空間 d.鏈式存儲比順序存儲難于擴充空間

17．已知一個單鏈表中，指針q指向指針p的前趨結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執行（）a.q→next=s；p→next=s； b.q→next=s；s→next=p； c.q→next=s；q→next=p； d.q→next=s；s→next=q；

18．設一組記錄的關鍵字key值為{62，50，14，27，19，35，47，56，83}，散列函數為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結點個數是（）a.1 b.2 c.3 d.4 19．執行下面程序段時，s語句被執行的次數為：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)s;a.n*n b.n*n/2 c.n(n+1)d.n(n+1)/2 20．在長度為n的線性表中刪除一個指針p所指結點的時間復雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設一個棧的輸入序列是a，b，c，d，則所得到的輸出序列（輸入過程中允許出棧）不可能出現的是（）

a.a，b，c，d b.a，b，d，c c.d，c，b，a d.c，d，a，b 22．關于串的敘述中，正確的是（）a．空串是只含有零個字符的串 b.空串是只含有空格字符的串

c.空串是含有零個字符或含有空格字符的串

d.串是含有一個或多個字符的有窮序列

23．在具有m個單元的循環隊列中，隊頭指針為front，隊尾指針為rear，則隊滿的條件是（）

a．front==rear

b.(front+1)%m==rear

+1==front

d.(rear+1)%m==front 24．設有二維數組

?1????a［n］［n］表示如下：?23456??????????，則a［i］［i］（0≤i≤n-1）的d.i2/2 值為（）

a．i*(i-1)/2 b.i*(i+1)/2 c.(i+2)*(i+1)/2 25．高度為h的完全二叉樹中，結點數最多為（）

ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結點數為n的樹組成的森林，將其轉化為一棵二叉樹，則該二叉樹中根結點的右子樹上具有的結點個數是（）

-1 c.n(m-1)d.m(n-1)27．在一個具有n個頂點的無向圖中，每個頂點度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關于無向圖的鄰接矩陣的說法中正確的是（）a.矩陣中非全零元素的行數等于圖中的頂點數

b.第i行上與第i列上非零元素總和等于頂點vi的度數 c.矩陣中的非零元素個數等于圖的邊數

d.第i行上非零元素個數和第i列上非零元素個數一定相等

29．設一組記錄的關鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結點個數是（）a.1 b.2 c.3 d.4 30．設有一組初始關鍵字值序列為（49，81，55，36，44，88），則利用快速排序的方法，以第一個關鍵字值為基準得到的一次劃分為（）

a.36，44，49，55，81，88 b.44，36，49，55，81，88 c.44，36，49，81，55，88 d.44，36，49，55，88，81

二、填空題

1.數據是計算機加工處理的對象（）。2.數據結構的概念包括數據的邏輯結構、數據在計算機中的存儲方式和數據的運算三個方面()。

3.線性表是由n≥0個相同類型組成的有限序列（）。4.棧是一種后進先出的線性表（）。

5.從循環鏈表的某一結點出發，只能找到它的后繼結點，不能找到它的前驅結點（）。6.單鏈表設置頭結點的目的是為了簡化運算（）。7.樹的最大特點是一對多的層次結構（）。8.組成數據的基本單位稱為數據元素（）。

9.從非循環鏈表的某一結點出發，既能找到它的后繼結點，又能找到它的前驅結點（）。

10.單鏈表結點的指針域是用來存放其直接后繼結點的首地址的（）

11.數據的存儲結構是數據的邏輯結構的存儲映象（）。

12.用順序表來存儲線性表時，不需要另外開辟空間來保存數據元素之間的相互關系（）。

13.在非線性結構中，至少存在一個元素不止一個直接前驅或不止一個直接后驅（）。14.樹的最大特點是一對多的層次結構（）。15.隊列的特點是先進先出（）。

16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）。17.數據的存儲結構獨立于計算機（）。18.線性表簡稱為”順序表”。（）

19.對數據的任何運算都不能改變數據原有的結構特性（）。20.從循環單鏈表的任一結點出發，可以找到表中的所有結點（）。21.棧是一種先進先出的線性表（）。22.鏈表的主要缺點是不能隨機訪問（）。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩定的排序（）。25.算法是對解題方法和步驟的描述（）。26.算法可以用任意的符號來描述（）。

27.數據的邏輯結構可以看作是從具體問題抽象出來的數學模型（）。

28.線性表的順序存儲方式是按邏輯次序將元素存放在一片地址連續的空間中（）。29.棧是一種先進后出的線性表（）。

30.將插入和刪除限定在表的同一端進行的線性表是隊列（）。

三、畫圖題

1.請根據下列二元組畫出相應的數據結構

k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請根據下列二元組畫出相應的數據結構

k={a,b,c,d,e,f,g,h,i,j} r={,,

,

,

,

,

,

,

} 3．請根據下列二元組畫出相應的數據結構 k={1,2,3,4,5,6,7} r={<1,2>,<1,3>,<1,4>,<2,1>,<2,4>,<3,5>,<3,6>,<3,7>,<4,1>,<4,5>,<5,1>,<5,3>,<5,4>,<6,5>,<6,7>,<7,3>} 4.請根據下列二元組畫出相應的數據結構

k={1,2,3,4,5} r={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請根據下列二元組畫出相應的數據結構 k={0,1,2,3,4,5,6,7} r={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．請根據下列二元組畫出相應的數據結構

k={1,2,3,4,5,6,7} r={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}

四、運算題

1．已知一個圖的頂點集v和邊集h分別為：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照克魯斯卡爾算法得到最小生成樹，拭寫出在最小生成樹中依次得到的各條邊。______，______，______，______，______，______，______。

2.一個線性表為b=（12，23，45，57，20，03，78，31，15，36），設散列表為ht[0..12]，散列函數為h（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。

平均查找長度：（寫出計算過程）

3．已知一個圖的頂點集v和邊集h分別為：

v＝{0，1，2，3，4，5，6，7}

e＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；

按照普里姆算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。（從頂點2出發）

____

__，___

_，___

___，__

____，___ ___，__ ____，___ ___。4.寫出下圖所示的二叉樹的前中后序遍歷結果：

前序： 中序： 后序：

5.設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。

五、編程題

1.請編寫一個算法，實現十進制整數與二進制數的轉換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：

int search_bin(keytype k,sstable st){ 3.請編寫一個算法，實現單鏈表的就地逆置（單鏈表不帶頭結點）。linklist *invertlink(linklist *h){

數據結構c語言版篇四

《數據結構與算法》教學大綱

課程編號：030816 適用專業：教育技術學 總學時數：64

學 分：4 編制單位：茂名學院理學院教育與信息技術系 編制時間：2008年6月20日

一、課程地位、性質和任務

《數據結構與算法》課程是計算機相關學科專業的基礎課程中的一門重要的核心課程。通過本課程的教學，使學生知道求解非數值類問題的基本模型（表、樹、圖），模型的特點和適用場合，能夠根據問題設計和選擇好的算法，為學習后續的操作系統、編譯原理和軟件工程等專業課程，設計應用程序打下基礎。

本課程以提高學生的計算機應用能力和綜合素質為目標，通過課程教學，為學生構建數據結構與算法方面的知識體系，使學生一方面能夠根據問題選擇合適的數據結構，設計高效的算法，提高程序設計能力，另一方面，在工程應用中，具有甄別好算法的能力，也就是要從建模、解模和綜合等三個方面，提高學生的程序設計能力。

二、與其他課程的關系

先修課：程序設計基礎、離散數學、計算機組成原理、計算機文化基礎

三、教學內容、課時安排和基本要求

（一）教學部分 第1章 緒論（2學時）1.1什么是數據結構 1.2 基本概念和術語

1.3 抽象數據類型的表示與實現

1.4 算法和算法分析（算法及其設計的要求，算法效率的度量，算法的存儲空間需求）1.5 問題求解

基本要求：

了解：抽象數據類型，算法設計方法與算法分析。

掌握：數據與數據結構、算法的基本概念；問題求解的方法與步驟 重點：數據結構和算法的概念，算法的描述形式和評價方法，問題求解的一般步驟 難點：評價算法的標準和評價方法，最壞情況和平均情況的區分。

第2章 線性表（8學時）2.1 線性表的類型定義 2.2 線性表的順序表示和實現

2.3 線性表的鏈式表示和實現（線性鏈表，循環鏈表，雙向鏈表）2.4 一元多項式的表示及相加

基本要求：

了解：兩種存儲結構（順序存儲結構和鏈式存儲結構）及一元多項式的表示及相加。

掌握：要求熟練掌握處理線性表的各種算法。為后繼章節的學習打基礎。重點：各種算法。難點：鏈表的理解。

第3章 棧與隊列（4學時）

3.1 棧（定義，棧的表示和實現）

3.2 棧的應用舉例（數制轉換，括號匹配的檢驗，行編輯程序，迷宮求解，表達式求值）

3.3 棧與遞歸的實現

3.4 隊列及其實現（定義，鏈隊列，循環隊列）3.5 *離散事件模擬

教學要求：熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。棧和隊列是表最基本和重要的數據結構，是數據結構課程的基礎。

基本要求：

了解： 棧和隊列的定義及其實現。

掌握： 熟練掌握棧和隊列的特性和在不同存儲結構前提下的算法實現。重點： 棧和隊列的算法實現。難點： 棧和隊列的算法實現。

第4章 串（2學時）4.1 串類型的定義

4.2 串的表示和實現（定長順序存儲，堆分配存儲，串的塊鏈存儲）4.3 串的模式匹配算法（求子串位置的定位函數，模式匹配的一種改進算法）4.4 串操作應用舉例（文本編輯，建立詞索引表）

基本要求：

了解：串的基本概念及主要操作和運算。掌握：掌握串的基本概念和運算。重點：主要操作和運算。難點：模式匹配及串的應用。

第5章 數組（2學時）5.1 數組的定義

5.2 數組的順序表示和實現

5.3 矩陣的壓縮存儲（特殊矩陣，稀疏矩陣）5.4 廣義表的定義 5.5 廣義表的存儲結構 5.6 m元多項式的表示

5.7 廣義表的遞歸算法（求廣義表的深度，復制廣義表，建立廣義表的存儲結構）

基本要求：

了解：了解作為抽象數據類型的數組和c語言的數組。認識到數組可以作為順序存儲結構用于順序表、字符串和稀疏矩陣的實現。也可以采用鏈式存儲結構。

掌握：掌握基本概念和算法。重點：算法。

難點：廣義表的遞歸算法。

第6章 樹與二叉樹（15學時）6.1 樹的定義和基本術語

6.2 二叉樹（二叉樹的定義，二叉樹的性質，二叉樹的存儲結構）6.3 遍歷二叉樹和線索二叉樹（遍歷二叉樹，線索二叉樹）

6.4 樹和森林（樹的存儲結構，森林與二叉樹的轉換，樹和森林的遍歷）6.5 樹與等價問題

6.6 赫夫曼樹及其應用（最優二叉樹（赫夫曼樹），赫夫曼編碼）6.7 回溯法與樹的遍歷 6.8 樹的計數

基本要求：

了解：理解樹與森林的定義與術語。

掌握：熟練掌握二叉樹性質和遍歷算法，掌握樹與森林的孩子兄弟存儲表示和遍歷。掌握哈夫曼樹構造的方法和算法。重點： 樹的存儲結構和遍歷算法。難點：哈夫曼樹構造的方法和算法

第7章 圖（11學時）7.1 圖的定義和術語

7.2 圖的存儲結構（數組表示法，鄰接表，十字鏈表，鄰接多重表）7.3 圖的遍歷（深度優先搜索，廣度優先搜索）

7.4 圖的連通性問題（無向圖的連通分量和生成樹，有向圖的強連通分量，最小生成樹，關節點和重連通分量）

7.5 有向無環圖及其應用（拓撲排序，關鍵路徑）

7.6 最短路徑（從某個源點到其余各項點的最短路徑，每一對頂點之間的最短路徑）基本要求：

了解：圖的基本概念和相關術語。

掌握：圖的兩種主要存儲結構及遍歷算法。掌握最小生成樹、最短路徑和活動網算法的思想。

重點：圖的兩種主要存儲結構及遍歷算法。難點：圖的遍歷算法，最短路徑算法。

第8章 查找（8學時）

9.1 靜態查找表（順序表，有序表，靜態樹表，索引順序表）9.2 動態查找表（二叉排序樹和平衡二叉樹，b_樹和b+樹，鍵樹）9.3 哈希表（定義，構造方法，處理沖突的方法，查找及其分析）

基本要求：

了解： 各種查找法的基本概念及實現的基本思想。

掌握：熟練掌握搜索結構的折半查找、二叉搜索樹、平衡二叉樹主要搜索算法。掌握哈希表查找算法。重點：各種算法的基本思想及實現。難點：哈希表查找算法。

第9章 內部排序（8學時）10.1 概述

10.2 插入排序（直接插入，其他插入，希爾）10.3 交換排序（冒泡排序、快速排序）10.4 選擇排序（簡單，樹形，堆）10.5 歸并排序

10.6 基數排序（多關鍵字，鏈式）10.7 排序算法分析

基本要求：

了解：基數排序，排序算法分析方法

掌握：排序的基本概念，插入排序，交換排序，選擇排序，歸并排序重點：內部排序算法

難點：基數排序（多關鍵字，鏈式）

第10章 *外部排序（2學時）11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實現 11.4 置換-選擇排序 11.5 最佳歸并樹

基本要求：

了解：外部排序的基本概念和相關術語。

掌握：基本掌握外排算法的基本思想，不同排序方法的比較。重點：外部排序算法 難點：多路平衡歸并的實現 第11章 算法設計的一般方法（2學時）

1．重點

（1）有效算法的概念，問題固有難度的概念；

（2）遞歸法；分治法；平衡原則；貪心法；動態規劃的基本原理；（3）搜索-回溯法的基本原理和本質.2．難點

（1）問題固有難度的概念；

（2）遞歸分治法的效率分析（寫出時間耗費的遞推式，并求解）；（3）動態規劃法中的狀態轉移方程的確定。

（二）實驗、實習部分

課程安排五個類別的實驗，實驗時數為12課時，其中： 實驗

一、線性鏈表及運算 2課時 實驗

二、棧和隊列 2課時 實驗

三、樹和二叉樹 4課時 實驗

四、圖及其應用 2課時 實驗

五、查找與排序 2課時

四、課程考核方式

閉卷考試70%、平時作業與實驗30%

五、建議教材和教學參考書 參考教材：

1、《數據結構》（c語言描述）高等教育出版社 耿國華主編

2、《數據結構》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

3、《數據結構題集》（c語言版）清華大學出版社 嚴蔚敏，吳偉民編者

4、《數據結構》算法實現及解析（第二版）西安電子科技大學出版社 高一凡

六、說明

1、因課時安排少，教學內容多。建議采用多媒體教學。

2、由于本課程內容較多，在實際教學中可根據大綱內容，進行適當調整。

數據結構c語言版篇五

河南省高等教育自學考試

實 驗 報 告 冊

計算機及應用專業（本科段）

《數據結構》

姓名周東偉準考證號010512201008所屬地市鄭州實驗地點河南職業技術學院實驗日期2023-3-18實驗總成績指導教師簽名實驗單位（實驗室）意見：主考院校審核意見：

河南科技大學自學考試辦公室