在日常學(xué)習(xí),、工作或生活中,，大家總少不了接觸作文或者范文吧,，通過(guò)文章可以把我們那些零零散散的思想,，聚集在一塊,。范文書寫有哪些要求呢？我們?cè)鯓硬拍軐懞靡黄段哪?？下面我給大家整理了一些優(yōu)秀范文,，希望能夠幫助到大家，我們一起來(lái)看一看吧,。
數(shù)據(jù)結(jié)構(gòu)演講篇一
【實(shí)驗(yàn)?zāi)康摹?/p>
學(xué)習(xí)掌握線性表的順序存儲(chǔ)結(jié)構(gòu),、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的設(shè)計(jì)與操作。對(duì)順序表建立,、插入,、刪除的基本操作，對(duì)單鏈表建立,、插入,、刪除的基本操作算法。
【實(shí)驗(yàn)內(nèi)容】
1.順序表的實(shí)踐
1)建立4個(gè)元素的順序表s=sqlist[]={1,，2,，3，4,，5},，實(shí)現(xiàn)順序表建立的基本操作。
2)在sqlist []={1,，2,，3，4,，5}的元素4和5之間插入一個(gè)元素9,，實(shí)現(xiàn)順序表插入的基本操作。
3)在sqlist []={1,，2,，3，4,，9，5}中刪除指定位置（i=5）上的元素9,，實(shí)現(xiàn)順序表的刪除的基本操作,。2.單鏈表的實(shí)踐
3.1)建立一個(gè)包括頭結(jié)點(diǎn)和4個(gè)結(jié)點(diǎn)的（5，4,，2,，1）的單鏈表,，實(shí)現(xiàn)單鏈表建立的基本操作。
2)將該單鏈表的所有元素顯示出來(lái),。
3)在已建好的單鏈表中的指定位置（i=3）插入一個(gè)結(jié)點(diǎn)3,，實(shí)現(xiàn)單鏈表插入的基本操作。
4)在一個(gè)包括頭結(jié)點(diǎn)和5個(gè)結(jié)點(diǎn)的（5,，4,，3，2,，1）的單鏈表的指定位置（如i=2）刪除一個(gè)結(jié)點(diǎn),，實(shí)現(xiàn)單鏈表刪除的基本操作。5)實(shí)現(xiàn)單鏈表的求表長(zhǎng)操作,。
【實(shí)驗(yàn)步驟】
1.打開vc++,。
2.建立工程：點(diǎn)file->new，選project標(biāo)簽,，在列表中選win32 console application,，再在右邊的框里為工程起好名字，選好路徑,，點(diǎn)ok->finish,。至此工程建立完畢。
3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽,，在列表里選c++ source file。給文件起好名字,，選好路徑,，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中,。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實(shí)驗(yàn)心得】
線性是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中,，碰到的第一個(gè)數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)線性表的重點(diǎn)掌握順序表和單鏈表的各種算法和時(shí)間性能分析,。線性表右兩種存儲(chǔ)方式即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),。通過(guò)學(xué)習(xí)我知道了對(duì)線性表進(jìn)行建立、插入,、刪除,，同時(shí)單鏈表也是進(jìn)行建立、插入,、刪除,。而對(duì)于順序表的插入刪除運(yùn)算，其平均時(shí)間復(fù)雜度均為0（n）.通過(guò)這次的學(xué)習(xí),，掌握的太熟練,，主要是課本上的知識(shí)點(diǎn)沒(méi)有徹底的理解,，回去我會(huì)多看書，理解重要的概念,?？傊@次實(shí)驗(yàn)我找到了自己的不足之處,，以后會(huì)努力的,。
實(shí)驗(yàn)二：棧的表示與實(shí)現(xiàn)及棧的應(yīng)用
【實(shí)驗(yàn)?zāi)康摹?/p>
（1）掌握棧的順序存儲(chǔ)結(jié)構(gòu)及其基本操作的實(shí)現(xiàn)。（2）掌握棧后進(jìn)先出的特點(diǎn),，并利用其特性在解決實(shí)際問(wèn)題中的應(yīng)用,。（3）掌握用遞歸算法來(lái)解決一些問(wèn)題?！緦?shí)驗(yàn)內(nèi)容】
1.編寫程序,，對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，輸出與其等值的八進(jìn)制數(shù),。
2.編寫遞歸程序,，實(shí)現(xiàn)n！的求解,。3.編寫遞歸程序,，實(shí)現(xiàn)以下函數(shù)的求解。
n,n?0,1?fib(n)?? ?fib(n?1)?fib(n?2),n?1
4.編寫程序,，實(shí)現(xiàn)hanoi塔問(wèn)題,。【實(shí)驗(yàn)步驟】 1.打開vc++,。
2.建立工程：點(diǎn)file->new,，選project標(biāo)簽，在列表中選win32 console application,，再在右邊的框里為工程起好名字,，選好路徑，點(diǎn)ok->finish,。至此工程建立完畢,。
3.創(chuàng)建源文件或頭文件：點(diǎn)file->new，選file標(biāo)簽,，在列表里選c++ source file,。給文件起好名字，選好路徑,，點(diǎn)ok,。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實(shí)驗(yàn)心得】
通過(guò)這次的學(xué)習(xí)我掌握了棧這種抽象數(shù)據(jù)類型的特點(diǎn),，并能在相應(yīng)的應(yīng)用任務(wù)中正確選用它,；總的來(lái)說(shuō)，棧是操作受限的線性表,，是限定僅在表尾進(jìn)行插入或刪除操作的線性表,。因此，對(duì)棧來(lái)說(shuō),，表尾端有其特殊含義,，稱為棧頂（top），相應(yīng)地,，表頭端稱為棧底（botton）,；棧又稱為后進(jìn)先出（last in first out）的線性表,簡(jiǎn)稱lifo結(jié)構(gòu)，因?yàn)樗男薷氖前春筮M(jìn)先出的原則進(jìn)行的,。
加上這個(gè)實(shí)驗(yàn),，我已經(jīng)學(xué)了線性表（順序表，單鏈表）和棧,，知道它們都是線性表,，而且對(duì)以后的學(xué)習(xí)有很大的作用，可以說(shuō)這是學(xué)習(xí)以后知識(shí)的總要基礎(chǔ),。
實(shí)驗(yàn)三：二叉樹的建立及遍歷
【實(shí)驗(yàn)?zāi)康摹?/p>
（1）掌握利用先序序列建立二叉樹的二叉鏈表的過(guò)程,。（2）掌握二叉樹的先序、中序和后序遍歷算法,?！緦?shí)驗(yàn)內(nèi)容】
1.編寫程序，實(shí)現(xiàn)二叉樹的建立,，并實(shí)現(xiàn)先序,、中序和后序遍歷。如：輸入先序序列abc###de###,，則建立如下圖所示的二叉樹,。
并顯示其先序序列為：abcde 中序序列為：cbaed 后序序列為：cbeda 【實(shí)驗(yàn)步驟】 1.打開vc++。
2.建立工程：點(diǎn)file->new,，選project標(biāo)簽,，在列表中選win32 console application，再在右邊的框里為工程起好名字,，選好路徑,，點(diǎn)ok->finish。至此工程建立完畢,。
3.創(chuàng)建源文件或頭文件：點(diǎn)file->new,，選file標(biāo)簽，在列表里選c++ source file,。給文件起好名字,，選好路徑,，點(diǎn)ok。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中,。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
【實(shí)驗(yàn)心得】
這次試驗(yàn)是關(guān)于二叉樹的常見操作,，主要是二叉樹的建立和遍歷，在這次實(shí)驗(yàn)中我按先序方式建立二叉樹的,，而遍歷方式則相對(duì)要多一些,，有遞歸的先序、中序,、后序遍歷,，和非遞歸的先序、中序,、后序遍歷,，此外還有層次遍歷.二叉樹高度和葉子個(gè)數(shù)的計(jì)算和遍歷相差不大，只是加些判斷條件,，總體來(lái)說(shuō),，本次試驗(yàn)不太好做，期間出現(xiàn)了很多邏輯錯(cuò)誤,，變量初始化的問(wèn)題等,，不過(guò)經(jīng)過(guò)仔細(xì)排查最后都一一解決了。
實(shí)驗(yàn)四：查找與排序
【實(shí)驗(yàn)?zāi)康摹?/p>
（1）掌握折半查找算法的實(shí)現(xiàn),。（2）掌握冒泡排序算法的實(shí)現(xiàn),。【實(shí)驗(yàn)內(nèi)容】
1.編寫折半查找程序,，對(duì)以下數(shù)據(jù)查找37所在的位置,。5，13,，19,，21，37,，56,，64，75,，80,，88，92 2.編寫冒泡排序程序,，對(duì)以下數(shù)據(jù)進(jìn)行排序,。49，38，65,，97,，76，13,，27,，49 【實(shí)驗(yàn)步驟】 1.打開vc++。
2.建立工程：點(diǎn)file->new,，選project標(biāo)簽，在列表中選win32 console application,，再在右邊的框里為工程起好名字,，選好路徑，點(diǎn)ok->finish,。至此工程建立完畢,。
3.創(chuàng)建源文件或頭文件：點(diǎn)file->new，選file標(biāo)簽,，在列表里選c++ source file,。給文件起好名字，選好路徑,，點(diǎn)ok,。至此一個(gè)源文件就被添加到了你剛創(chuàng)建的工程之中。
4．寫好代碼
5．編譯－＞鏈接－＞調(diào)試
（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(“輸入元素個(gè)數(shù)和各元素的值:”);
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
} 實(shí)驗(yàn)結(jié)果如下所示：
（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(“輸入元素個(gè)數(shù)和各元素的值:”);
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);} 實(shí)驗(yàn)結(jié)果如下所示：
【實(shí)驗(yàn)心得】
通過(guò)這次實(shí)驗(yàn),我明白了程序里的折半查找和冒泡查找.其實(shí)排序可以有很多種,，但是其目的應(yīng)該都是為了能夠在海量的數(shù)據(jù)里迅速查找到你要的數(shù)據(jù)信息,，折半查找是種比較快的方式，但前提是要是有 序的排序才可以,。對(duì)于有序表,，查找時(shí)先取表中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較，若相等,，則查找成功,；如果給定值比該記錄關(guān)鍵字大，則在后半部分繼續(xù)進(jìn)行折半查找,；否則在前半部分進(jìn)行折半查找,，直到查找范圍為空而查不到為止。折半查找的過(guò)程實(shí)際上死先確定待查找元素所在的區(qū)域,，然后逐步縮小區(qū)域,，直到查找成功或失敗為止。算法中需要用到三個(gè)變量,，low表示區(qū)域下界,，high表示上界，中間位置mid=(low+high)/2.而冒泡查找則是從小到大的排序.
數(shù)據(jù)結(jié)構(gòu)演講篇二
云淡風(fēng)清 http:///
第1章 數(shù)據(jù)結(jié)構(gòu)概述
1.1概述
以下為某市部分院校的交通地圖情況，要求找出從出發(fā)點(diǎn)到目的地之間的最短路徑及其長(zhǎng)度,。
對(duì)于此問(wèn)題,，如果手工去做，速度慢(特別地,，現(xiàn)實(shí)中實(shí)際地圖信息要比此例復(fù)雜許多),，還容易出錯(cuò)，此時(shí)可借助于計(jì)算機(jī)完成,。
計(jì)算機(jī)進(jìn)行此類信息的處理時(shí),，涉及到兩個(gè)問(wèn)題：一是現(xiàn)實(shí)當(dāng)中的信息在計(jì)算機(jī)中如何表示，二是如何對(duì)信息進(jìn)行處理,。
信息的表示和組織又直接關(guān)系到處理信息的程序的效率,。隨著應(yīng)用問(wèn)題不斷復(fù)雜化，導(dǎo)致信息量劇增與信息范圍的拓寬,，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大,，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此,，必須分析待處理問(wèn)題中的對(duì)象的特征及各對(duì)象之間存在的關(guān)系,，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問(wèn)題。
1.1.1編寫解決實(shí)際問(wèn)題的程序的一般流程
如何通過(guò)編寫程序,，以比手工更為高效精確的方式解決實(shí)際問(wèn)題呢,？一般流程如下：
1、由具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型,；
2,、分析問(wèn)題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系；
3,、確定如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系,？
4、確定處理問(wèn)題時(shí)需要對(duì)數(shù)據(jù)作何種運(yùn)算,？
5,、確定算法并編寫程序；
5,、分析所編寫的程序的性能是否良好,？若性能不夠好則重復(fù)以上步驟。
云淡風(fēng)清 http:/// 上面所列舉的問(wèn)題基本上由數(shù)據(jù)結(jié)構(gòu)這門課程來(lái)回答,。
《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中的一門綜合性專業(yè)基礎(chǔ)課,，是介于數(shù)學(xué)、計(jì)算機(jī)硬件,、計(jì)算機(jī)軟件三者之間的一門核心課程,，不僅是一般程序設(shè)計(jì)的基礎(chǔ),，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng),、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ),。
1.1.2數(shù)據(jù)結(jié)構(gòu)的例子
1、電話號(hào)碼查詢系統(tǒng)
設(shè)有一個(gè)電話號(hào)碼薄,，它記錄了n個(gè)人的名字和其相應(yīng)的電話號(hào)碼,。要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí),，該算法能夠打印出此人的電話號(hào)碼,，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠報(bào)告沒(méi)有這個(gè)人的標(biāo)志,。
姓名
電話號(hào)碼
陳偉海 *** 李四鋒 ***,。。
這是一種典型的線性結(jié)構(gòu),。
2、磁盤目錄文件系統(tǒng)
磁盤根目錄下有很多子目錄及文件,，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件,，但每個(gè)子目錄只有一個(gè)父目錄，依此類推,。
,。。
本問(wèn)題中各目錄從上到小形成了一種一對(duì)多的關(guān)系,，是一種典型的樹形結(jié)構(gòu),。
云淡風(fēng)清 http:///
3、交通網(wǎng)絡(luò)圖
下圖表明了若干個(gè)城市之間的聯(lián)系：
從圖中可看出,，一個(gè)地方到另外一個(gè)地方可以有多條路徑,，是一種典型的網(wǎng)狀結(jié)構(gòu)，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多的關(guān)系,。
4,、排序問(wèn)題
對(duì)100000個(gè)整數(shù)進(jìn)行降序排序。冒泡法程序： #include
#include
#include
#define n 100000 void main(){ int i,j;int a[n+1];srand(time(null));for(i=1;i<=n;i++)
a[i]=rand();printf(“n按原序輸出：n”);for(i=1;i<=n;i++)printf(“%8d”,a[i]);system(“pause”);for(j=1;j
for(i=n;i>j;i--)
if(a[i]>a[i-1])
{
a[0]=a[i];
a[i]=a[i-1];
a[i-1]=a[0];
} printf(“n按新次序輸出：n”);
云淡風(fēng)清 http:/// for(i=1;i<=n;i++)
printf(“%8d”,a[i]);printf(“n”);} 快速排序程序： #include
#include
#include
#define n 100000
void quick_sort(int a[n+1],int left,int right){ int j,last,temp;if(left{
//將劃分子集的元素(此處選中間元素)移動(dòng)到最左邊
temp=a[left];
a[left]=a[(left+right)/2];
a[(left+right)/2]=a[left];
last=left;//用last記錄比關(guān)鍵字小的元素的最右位置
for(j=left+1;j<=right;j++)//劃分子集
if(a[j]>a[left])
{
temp=a[last];
a[last]=a[j];
a[j]=temp;
last++;
}
//對(duì)形成的新子集遞歸進(jìn)行快速排序
quick_sort(a,left,last-1);
quick_sort(a,last+1,right);} } void main(){ int i;int a[n+1];srand(time(null));for(i=1;i<=n;i++)
a[i]=rand();printf(“n按原序輸出：n”);for(i=1;i<=n;i++)
printf(“%8d”,a[i]);system(“pause”);
云淡風(fēng)清 http:/// quick_sort(a,1,n);printf(“n按新次序輸出：n”);for(i=1;i<=n;i++)
printf(“%8d”,a[i]);printf(“n”);} 運(yùn)行可知,，兩者速度差異非常明顯,，主要是排序所花的時(shí)間差別很大?？煽闯?，同樣的問(wèn)題，采用不同方法進(jìn)行處理,，有可能呈現(xiàn)出非常大的性能方面的差異,。
還可以找到許多其它例子，如圖書館的書目檢索系統(tǒng)自動(dòng)化問(wèn)題，教師資料檔案管理系統(tǒng),，多叉路口交通燈的管理問(wèn)題等,。
1.2基本概念和術(shù)語(yǔ) 1.2.1數(shù)據(jù)(data)：
是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱,。
1.2.2數(shù)據(jù)元素(data element)：
是數(shù)據(jù)的基本單位,，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(data item)組成,。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位,。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。
1.2.3數(shù)據(jù)對(duì)象(data object)：
是性質(zhì)相同的數(shù)據(jù)元素的集合,，是數(shù)據(jù)的一個(gè)子集,，其中的數(shù)據(jù)元素可以是有限的，也可以是無(wú)限的,。如整數(shù)集合：n={0,，±1，±2,，…},，是無(wú)限集，而字符集合：c={ˊaˊ,，bˊ,，…，ˊzˊ}則為有限集,。
1.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)：
指對(duì)數(shù)據(jù)元素之間邏輯關(guān)系的描述,。
數(shù)據(jù)元素之間的關(guān)系可以是一種或多種。
數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系,，也可以是為處理問(wèn)題方便而人為定義的關(guān)系,，這種自然或人為定義的“關(guān)系”稱為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu),。其要點(diǎn)有兩個(gè)方面：一是元素本身,，二是元素之間的關(guān)系。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型,，如下：
云淡風(fēng)清 http:///
①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外,，沒(méi)有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系,。③樹型結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系,。
④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中相鄰的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)形式的定義是一個(gè)二元組： datastructure=(d,，s)其中：d是數(shù)據(jù)元素的有限集,，s是d上關(guān)系的有限集,。例：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)b=(k，r),，其中： k={k1, k2, …, k9}
r={
,，
，
,，
,，
，
,，
,，
，
,，
,，
} 畫出這邏輯結(jié)構(gòu)的圖示，并確定哪些是起點(diǎn),，哪些是終點(diǎn),。
1.2.5數(shù)據(jù)的物理結(jié)構(gòu)：又稱存儲(chǔ)結(jié)構(gòu)，指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式,。
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的存儲(chǔ),。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),。
順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer),，用該指針來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系),。
例：設(shè)有數(shù)據(jù)集合a={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲(chǔ)結(jié)構(gòu),。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的,；
鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。
數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面,，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu),，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。
在c語(yǔ)言中,，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu),；通過(guò)結(jié)構(gòu)體類型實(shí)現(xiàn)的鏈表來(lái)表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
1.2.6數(shù)據(jù)結(jié)構(gòu)(data structure)：
按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù),，按一定的映象方式把它存放在計(jì)算機(jī)存貯器中,，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu),。
1.2.7數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：
邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述：d_s=(d,，s),。
存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算,。
本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲(chǔ)結(jié)構(gòu)如下圖所示,。
云淡風(fēng)清 http:///
邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖
1.2.8數(shù)據(jù)類型(data type)：
指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱。
數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念,。在c語(yǔ)言中數(shù)據(jù)類型有：基本類型(如int,，float，double,，char等)和構(gòu)造類型(如數(shù)組,，結(jié)構(gòu)體，共用體等),。
數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型,，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象,，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系,。
1.3數(shù)據(jù)結(jié)構(gòu)的運(yùn)算
數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括： ⑴建立(create)一個(gè)數(shù)據(jù)結(jié)構(gòu)； ⑵消除(destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu),；
⑶從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(delete)一個(gè)數(shù)據(jù)元素,； ⑷把一個(gè)數(shù)據(jù)元素插入(insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中； ⑸對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)(access),；
⑹對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(modify),； ⑺對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(sort)； ⑻對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(search),。
以上只列舉了一些常見運(yùn)算,，實(shí)際應(yīng)用當(dāng)中可能會(huì)遇到許多其它運(yùn)算。
云淡風(fēng)清 http:/// 1.4抽象數(shù)據(jù)類型(abstract data type)1.4.1抽象數(shù)據(jù)類型簡(jiǎn)介：
簡(jiǎn)稱adt,，是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作,。adt的定義僅是一組邏輯特性描述，與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān),。因此,，不論adt的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變,，都不影響其外部使用,。
adt的形式化定義是三元組：adt=(d，s,，p)其中：d是數(shù)據(jù)對(duì)象,，s是d上的關(guān)系集，p是對(duì)d的基本操作集,。說(shuō)明：
⑴adt和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念,，其區(qū)別是：adt的范疇更廣,它不再局限于系統(tǒng)已定義并實(shí)現(xiàn)的數(shù)據(jù)類型,，還包括用戶自己定義的數(shù)據(jù)類型。
⑵adt的定義是由一個(gè)值域和定義在該值域上的一組操作組成,。包括定義,，表示和實(shí)現(xiàn)三個(gè)部分。⑶adt的最重要的特點(diǎn)是抽象和信息隱蔽,。抽象的本質(zhì)就是抽取反映問(wèn)題本質(zhì)的東西,，忽略非本質(zhì)的細(xì)節(jié)，使所設(shè)計(jì)的結(jié)構(gòu)更具有一般性,，可以解決一類問(wèn)題,。信息隱蔽就是對(duì)用戶隱藏?cái)?shù)據(jù)存儲(chǔ)和操作實(shí)現(xiàn)的細(xì)節(jié)，使用者了解抽象操作或界面服務(wù),，通過(guò)界面中的服務(wù)來(lái)訪問(wèn)這些數(shù)據(jù),。
adt不考慮物理結(jié)構(gòu)以及算法的具體實(shí)現(xiàn)。
例：整數(shù)的數(shù)學(xué)概念和對(duì)整數(shù)所能進(jìn)行的運(yùn)算構(gòu)成一個(gè)adt,，c語(yǔ)言中的變量類型int就是對(duì)這個(gè)抽象數(shù)據(jù)類型的一種物理實(shí)現(xiàn),。
1.4.2adt的一般定義形式：
adt的一般定義形式是： adt<抽象數(shù)據(jù)類型名> { 數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義> 數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義> 基本操作：<基本操作的定義> }adt<抽象數(shù)據(jù)類型名> 其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述?；静僮鞯亩x是： <基本操作名>(<參數(shù)表>)初始條件：<初始條件描述> 操作結(jié)果：<操作結(jié)果描述> 說(shuō)明：
初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件,；若不滿足，則操作失敗,，返回相應(yīng)的出錯(cuò)信息,。
操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果,。
1.5算法(algorithm)1.5.1算法基本概念：
算法是對(duì)特定問(wèn)題求解方法(步驟)的一種描述,，是指令的有限序列，其中每一條指令表示一個(gè)或
云淡風(fēng)清 http:/// 多個(gè)操作,。
1.5.2算法的基本特征：
算法具有以下五個(gè)特性
①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束,，且每一步都在有窮時(shí)間內(nèi)完成,。
②確定性：算法中每一條指令必須有確切的含義,。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口,。
③可行性：一個(gè)算法是能行的,。即算法描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。
④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入,，這些輸入取自于某個(gè)特定的對(duì)象集合,。
⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量,。
1.5.3算法的基本描述方法：
一個(gè)算法可以用多種方法描述,，主要有：使用自然語(yǔ)言描述,；使用形式語(yǔ)言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述等,。
1.5.4算法與程序的異同比較：
算法和程序是兩個(gè)不同的概念,。一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。算法必須可終止意味著不是所有的計(jì)算機(jī)程序都是算法,。
1.5.5評(píng)價(jià)算法好壞的幾個(gè)標(biāo)準(zhǔn)：
評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)
①正確性(correctness)：算法應(yīng)滿足具體問(wèn)題的需求,。
②可讀性(readability)：算法應(yīng)易于供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改,。
③健壯性(robustness)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí),，算法應(yīng)能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理,，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。
④通用性(generality)：算法應(yīng)具有一般性,，即算法的處理結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立,。⑤效率與存儲(chǔ)容量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)容量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間,。一般地,，這兩者與問(wèn)題的規(guī)模有關(guān)。
1.6算法效率的度量
解決同一個(gè)問(wèn)題的算法可能有多種,，如何選擇一個(gè)效率高的算法呢,？應(yīng)該來(lái)講，與算法效率相關(guān)的因素有很多,，如下：
云淡風(fēng)清 http:///
1,、算法選用何種策略；
2,、問(wèn)題的規(guī)模,；
3、程序設(shè)計(jì)的語(yǔ)言,；
4,、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；
5,、內(nèi)存的大?。?/p>
6,、外存的大?。?/p>
7、機(jī)器執(zhí)行指令的速度,；
8,、其它。
而確定算法效率的方法通常有兩種：
1.6.1事后統(tǒng)計(jì)：
先實(shí)現(xiàn)算法,，然后運(yùn)行程序,，測(cè)算其時(shí)間和空間的消耗。缺點(diǎn)：
1,、必須先依據(jù)算法編制程序并運(yùn)行程序,，耗費(fèi)人力物力；
2,、依賴軟硬件環(huán)境,，容易掩蓋算法本身的優(yōu)劣。由于算法的運(yùn)行與計(jì)算機(jī)的軟硬件等環(huán)境因素有關(guān),，不容易發(fā)現(xiàn)算法本身的優(yōu)劣,。同樣的算法用不同的編譯器編譯出的目標(biāo)代碼數(shù)量不同，完成算法所需的時(shí)間也不同,；若計(jì)算機(jī)的存儲(chǔ)空間較小,，算法運(yùn)行時(shí)間也就會(huì)延長(zhǎng)；
3,、沒(méi)有實(shí)際價(jià)值,。測(cè)試花費(fèi)不少時(shí)間但并沒(méi)有解決現(xiàn)實(shí)中的實(shí)際問(wèn)題。
1.6.2事前分析：
僅僅通過(guò)比較算法本身的復(fù)雜性來(lái)評(píng)價(jià)算法的優(yōu)劣,，不考慮其它的軟硬件因素,，通常考查算法所用的時(shí)間和所需的存儲(chǔ)空間,。
算法復(fù)雜性的度量可以分為時(shí)間復(fù)雜度和空間復(fù)雜度,。
1.6.3算法的時(shí)間復(fù)雜度(time complexity)
1、算法的時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度用于度量一個(gè)算法所用的時(shí)間,。
算法所用的時(shí)間主要包括程序編譯時(shí)間和運(yùn)行時(shí)間,。由于一個(gè)算法一旦編譯成功可以多次運(yùn)行，因此可以忽略編譯時(shí)間,，只討論算法的運(yùn)行時(shí)間,。
算法的運(yùn)行時(shí)間依賴于加、減,、乘,、除,、等基本的運(yùn)算以及參加運(yùn)算的數(shù)據(jù)量的大小,，另外，與計(jì)算機(jī)硬件和操作環(huán)境等也有關(guān)系,。要想準(zhǔn)確地估算時(shí)間是不可行的,，而影響算法時(shí)間最為主要的因素是問(wèn)題的規(guī)模,，即輸入量的多少。同等條件下,，問(wèn)題的規(guī)模越大,，算法所花費(fèi)的時(shí)間也就越長(zhǎng)。例如,，求1+2+3+?+n的算法,，即n個(gè)整數(shù)的累加求和，這個(gè)問(wèn)題的規(guī)模為n,。因此,，運(yùn)行算法所需的時(shí)間t是問(wèn)題規(guī)模n的函數(shù)，記作t(n),。
同等條件下,，相同或類似的基本操作在真正程序運(yùn)行過(guò)程中所花費(fèi)的時(shí)間也差不多，這樣,，如果兩個(gè)不同算法中一個(gè)所含基本操作多而另一個(gè)所含基本操作少,，則包含基本操作少的算法其花費(fèi)時(shí)間也就較少。因此,，通常用算法中基本語(yǔ)句的執(zhí)行次數(shù)來(lái)作為度量算法速度快慢的依據(jù),，而這種度量時(shí)間復(fù)雜度的方法得出的不是時(shí)間量，而是一種增長(zhǎng)趨勢(shì)的度量,，即當(dāng)問(wèn)題規(guī)模n增大時(shí),，t(n)也隨之變大。換言之,，當(dāng)問(wèn)題規(guī)模充分大時(shí),，算法中基本語(yǔ)句的執(zhí)行次數(shù)為在漸進(jìn)意義下的階，稱為算法的漸進(jìn)時(shí)間復(fù)雜度,，簡(jiǎn)稱時(shí)間復(fù)雜度,，通常用大o記號(hào)表示。用數(shù)學(xué)語(yǔ)言通常描述為：若當(dāng)且僅當(dāng)存在正整數(shù)n和n0,，對(duì)于任意n≥n0,，都有t(n)≤c×f(n)，則稱該算法的漸進(jìn)時(shí)間復(fù)雜度為t(n)=o(f(n)),。
一般地,，常用最內(nèi)層循環(huán)內(nèi)的語(yǔ)句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來(lái)表示時(shí)間復(fù)雜度。
2,、時(shí)間復(fù)雜度分析舉例： 例：兩個(gè)n階方陣的乘法,。
云淡風(fēng)清 http:/// for(i=1;i<=n;++i)for(j=1;j<=n;++j){
c[i][j]=0;
for(k=1;k<=n;++k)
c[i][j]+=a[i][k]*b[k][j];} 分析：由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為： n×n×n=n3,，時(shí)間復(fù)雜度為t(n)=o(n3),。
例： { ++x;s=0;} 分析：將x自增看成是基本操作，則語(yǔ)句頻度為1,，即時(shí)間復(fù)雜度為o(1),。
如果將s=0也看成是基本操作，則語(yǔ)句頻度為2,，其時(shí)間復(fù)雜度仍為o(1),，即常量階。只要t(n)不是問(wèn)題規(guī)模n的函數(shù),，而是一個(gè)常數(shù),，它的時(shí)間復(fù)雜度則均為o(1)。例：以下程序段： for(i=1;i<=n;++i){ ++x;s+=x;} 分析：基本語(yǔ)句的語(yǔ)句頻度為：n,，其時(shí)間復(fù)雜度為：o(n),，即為線性階。例：以下程序段： for(i=1;i<=n;++i)for(j=1;j<=n;++j){
++x;
s+=x;} 分析：基本語(yǔ)句的語(yǔ)句頻度為：n2,，其時(shí)間復(fù)雜度為：o(n2),，即為平方階。
定理：若t(n)=amnm+am-1nm-1+?+a1n+a0是一個(gè)m次多項(xiàng)式,，則t(n)=o(nm),，即復(fù)雜度表達(dá)式只取一個(gè)n趨向于無(wú)窮大時(shí)的同階無(wú)窮小表達(dá)式即可。
通過(guò)對(duì)算法復(fù)雜度的分析,，總結(jié)出這樣一條結(jié)論,，在計(jì)算任何算法的復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù),，這樣可以簡(jiǎn)化算法分析,，并使注意力集中在增長(zhǎng)率上。
從本質(zhì)上來(lái)講,，此種策略也就是只考慮對(duì)算法復(fù)雜度影響最大的因素而忽略次要因素,。例：以下程序段：
for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{
++x;
a[i,j]=x;
}
云淡風(fēng)清 http:/// 分析：基本語(yǔ)句的語(yǔ)句頻度為： 1+2+3+?+n-2 =(1+n-2)×(n-2)/2
=(n-1)×(n-2)/2 =(n2-3n+2)/2 按上述定理，時(shí)間復(fù)雜度為o(n2),，即此算法的時(shí)間復(fù)雜度為平方階,。
一個(gè)算法時(shí)間復(fù)雜度為o(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的,。因此,，總的時(shí)間由一個(gè)常數(shù)(即零次多項(xiàng)式)來(lái)界定。而一個(gè)時(shí)間為o(n2)的算法則由一個(gè)二次多項(xiàng)式來(lái)界定,。
3,、常見表示時(shí)間復(fù)雜度的階： o(1)：常量時(shí)間階 o(n)：線性時(shí)間階 o(㏒n)：對(duì)數(shù)時(shí)間階
o(n㏒n)：線性對(duì)數(shù)時(shí)間階 o(nk)：k≥2,，k次方時(shí)間階
4、常見時(shí)間復(fù)雜度大小關(guān)系分析：
以下六種計(jì)算算法時(shí)間復(fù)雜度的多項(xiàng)式是最常用的,，其大小關(guān)系通常為： o(1)
當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊,。因此,，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就,。
有的情況下,，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨輸入數(shù)據(jù)集的不同而不同。例：素?cái)?shù)的判斷算法,。
void prime(int n)//n是一個(gè)正整數(shù) { int i=2;while((n%i)!=0 && i*1.0
i++;if(i*1.0>sqrt(n))
printf(“&d 是一個(gè)素?cái)?shù)n”,n);else
printf(“&d 不是一個(gè)素?cái)?shù)n”,n);} 此例中執(zhí)行頻率最高的語(yǔ)句為i++;,，此語(yǔ)句最少執(zhí)行0次，最多執(zhí)行sqrt(n)次,，對(duì)于不同的n,，執(zhí)行次數(shù)不確定。
對(duì)于此類算法,，如果輸入數(shù)據(jù)不同,，則算法運(yùn)行時(shí)間也不同，因此要全面分析一個(gè)算法,，需要考慮算法在最好,、最壞、平均情況下的時(shí)間消耗,。由于最好情況出現(xiàn)的概率太小,，因此不具代表性，但是,，當(dāng)最好情況出現(xiàn)的概率大時(shí),，應(yīng)該分析最好情況；雖然最壞情況出現(xiàn)的概率也太小,，不具代表性,，但是分析最壞情況能夠讓人們知道算法的運(yùn)行時(shí)間最壞能到什么程度，這一點(diǎn)在實(shí)時(shí)系統(tǒng)中很重要,；分析平均情況是比較普遍的,，特別是同一個(gè)算法要處理不同的輸入時(shí)，通常假定輸入的數(shù)據(jù)是等概率分布的,。
例：冒泡排序法,。
void bubble_sort(int a[],int n)
云淡風(fēng)清 http:/// { int temp;change=false;for(i=n-1;change=ture;i>1 && change;--i)
for(j=0;j
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
change=ture;
} } 最好情況：0次
最壞情況：1+2+3+?+n-1=n(n-1)/2平均時(shí)間復(fù)雜度為：o(n2)1.6.4算法的空間復(fù)雜度(space complexity)
1、算法的空間復(fù)雜度
算法的空間復(fù)雜度是指在算法的執(zhí)行過(guò)程中需要的輔助空間數(shù)量,。輔助空間數(shù)量指的不是程序指令,、常數(shù),、指針等所需要的存儲(chǔ)空間，也不是輸入數(shù)據(jù)所占用的存儲(chǔ)空間,，輔助空間是除算法本身和輸入輸出數(shù)據(jù)所占據(jù)的空間外,，算法臨時(shí)開辟的存儲(chǔ)空間。算法的空間復(fù)雜度分析方法同算法的時(shí)間復(fù)雜度相似,，設(shè)s(n)是算法的空間復(fù)雜度,，通常可以表示為：
s(n)=o(f(n))其中：n為問(wèn)題的規(guī)模(或大小),。該存儲(chǔ)空間一般包括三個(gè)方面： 指令常數(shù)變量所占用的存儲(chǔ)空間,； 輸入數(shù)據(jù)所占用的存儲(chǔ)空間； 輔助(存儲(chǔ))空間,。
一般地,，算法的空間復(fù)雜度指的是輔助空間。如：
一維數(shù)組a[n]：空間復(fù)雜度o(n)二維數(shù)組a[n][m]：空間復(fù)雜度o(n*m)例：數(shù)組a中有10000個(gè)數(shù),，要求將所有數(shù)據(jù)逆置(即順序倒過(guò)來(lái)存放),。為達(dá)到逆置目的，有以下兩種方案： 方案一：
int a[10000],b[10000],i;for(i=0;i<10000;i++)b[10000-i-1]=a[i];for(i=0;i<10000;i++)a[i]=a[b];方案二：
int a[10000],t,i;for(i=0;i<10000/2;i++)
云淡風(fēng)清 http:/// { t=a[i];a[i]=a[10000-i-1];a[10000-i-1]=t;} 很明顯,，方案二中的輔助空間數(shù)量為1,，而方案一中的輔助空間數(shù)量為10000，方案二的空間復(fù)雜度優(yōu)于方案一,。
在算法的時(shí)間復(fù)雜度和空間復(fù)雜度中,，我們更注重算法的時(shí)間性能。因此,，在對(duì)算法性能的分析當(dāng)中,，通常均主要針對(duì)算法時(shí)間性能進(jìn)行分析。
1.6.5學(xué)習(xí)算法的原因
講述了這么多關(guān)于算法的基礎(chǔ)知識(shí),，究竟為什么要學(xué)習(xí)算法呢,？
首先，算法無(wú)處不在,。算法不僅出現(xiàn)在數(shù)學(xué)和計(jì)算機(jī)程序中,，更普遍地出現(xiàn)在我們的生活中，在生活中做什么事情都要有一定的順序,，然而不同的順序帶來(lái)的效率和成果可能都會(huì)不同,，只有學(xué)好了算法，才能讓生活更有趣,、更有效率,。
其次，算法是程序的靈魂,。學(xué)習(xí)計(jì)算機(jī)編程,，必須要掌握好其靈魂,，否則，寫出來(lái)的程序就像是沒(méi)有靈魂的軀體,。
再次,，算法是一種思想。掌握了這種思想,，能夠拓展思維,，使思維變得清晰、更具邏輯性,，在生活以及編程上的很多問(wèn)題,，也就更易解決,。
最后,，算法的樂(lè)趣。學(xué)習(xí)算法不僅僅是為了讓它幫助人們更有效地解決各種問(wèn)題,，算法本身的趣味性很強(qiáng),，當(dāng)通過(guò)煩瑣的方法解決了一個(gè)問(wèn)題后會(huì)感覺(jué)到有些疲憊，但是面對(duì)同一個(gè)問(wèn)題,，如若學(xué)會(huì)使用算法,，更簡(jiǎn)單有效地解決了這個(gè)問(wèn)題，會(huì)發(fā)現(xiàn)很有成就感,，算法的速度,、思想會(huì)讓人覺(jué)得很奇妙。每一個(gè)奇妙的算法都是智慧的結(jié)晶,。
學(xué)習(xí)算法的理由成千上萬(wàn),，不同的人可能出于不同的目的去學(xué)習(xí)算法，希望大家能夠通過(guò)對(duì)課程的學(xué)習(xí)對(duì)算法有進(jìn)一步的理解,。
習(xí)題一
1,、簡(jiǎn)要回答術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素,，數(shù)據(jù)結(jié)構(gòu),，數(shù)據(jù)類型。
2,、數(shù)據(jù)的邏輯結(jié)構(gòu),？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么,？
3,、數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括哪些？
4,、算法分析的目的是什么,？算法分析的主要方面是什么,？
云淡風(fēng)清 http:///
第2章 線性表
下表為某電臺(tái)提供給聽眾的若干首英文歌曲名及相關(guān)點(diǎn)播情況統(tǒng)計(jì)信息：
由于實(shí)際的歌曲庫(kù)可能很大，手工管理效率低,，不方便,，現(xiàn)請(qǐng)?jiān)O(shè)計(jì)一個(gè)軟件系統(tǒng)實(shí)現(xiàn)對(duì)此類歌曲庫(kù)的管理。
分析：
此例中相鄰的兩首歌之間是一種一對(duì)一的關(guān)系,，屬于典型的線性結(jié)構(gòu),，可按線性結(jié)構(gòu)進(jìn)行組織及管理。
2.1線性結(jié)構(gòu)與線性表 2.1.1線性結(jié)構(gòu)
如果一個(gè)數(shù)據(jù)元素序列滿足：
⑴除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外,，每個(gè)數(shù)據(jù)元素只有一個(gè)直接前驅(qū)數(shù)據(jù)元素和一個(gè)直接后繼數(shù)據(jù)元素,；
⑵第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)數(shù)據(jù)元素； ⑶最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼數(shù)據(jù)元素,。則稱這樣的數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu),。
線性表、棧,、隊(duì)列,、串和數(shù)組都屬于線性結(jié)構(gòu)。如下圖：
云淡風(fēng)清 http:/// 2.1.2線性表
線性表(linear list)是一種最簡(jiǎn)單,、最常用的線性結(jié)構(gòu),，是一種可以在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作的、由n(n≥0)個(gè)相同類型數(shù)據(jù)元素a1,，a2,，?，an組成的線性結(jié)構(gòu),。在這種結(jié)構(gòu)中：
⑴存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素,； ⑵存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素； ⑶除第一個(gè)元素外,，每個(gè)元素均有唯一一個(gè)直接前驅(qū),； ⑷除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼,。線性表中的數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度,。當(dāng)n=0時(shí)，稱為空表,?？站€性表用符號(hào)()表示。
當(dāng)n>0時(shí),，將非空的線性表記作：(a1,，a2，?an),，其中符號(hào)ai(1≤i≤n)表示第i個(gè)抽象數(shù)據(jù)元素,。
a1稱為線性表的第一個(gè)(頭)結(jié)點(diǎn),，an稱為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。a1,，a2,，?ai-1都是ai(2≤i≤n)的前驅(qū)，其中ai-1是ai的直接前驅(qū),；
ai+1,，ai+2，?an都是ai(1≤i ≤n-1)的后繼,，其中ai+1是ai的直接后繼,。
線性結(jié)構(gòu)是最常用、最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu),，而線性表是一種典型的線性結(jié)構(gòu),，其基本特點(diǎn)是可以在任意位置進(jìn)行插入和刪除等操作，且數(shù)據(jù)元素是有限的,。
線性表可以用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn),。用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表稱為順序表,，用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表稱為鏈表,。鏈表主要有單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表三種,。順序表和鏈表各有優(yōu)缺點(diǎn),，并且優(yōu)缺點(diǎn)剛好相反，在實(shí)際應(yīng)用中要根據(jù)情況選擇對(duì)操作及性能有利的存儲(chǔ)結(jié)構(gòu),。
線性表中的數(shù)據(jù)元素ai所代表的具體含義隨實(shí)際應(yīng)用領(lǐng)域的不同而不同,，在線性表的定義中，只不過(guò)是一個(gè)抽象的表示符號(hào),。
◆線性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng)),。例1：26個(gè)英文字母組成的字母表：(a，b,，c,、?、z)例2：某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況：(6,，17,，28，50,，92,，188)例3：一副撲克的點(diǎn)數(shù)：(2，3,，4,，?,，j，q,，k,，a)◆線性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng),，每個(gè)項(xiàng)稱為結(jié)點(diǎn)的一個(gè)域,。每個(gè)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱為關(guān)鍵字,。
例4：某校2001級(jí)同學(xué)的基本情況：{(‘2001414101’,，‘張里戶’，‘男’,，06/24/1983),，(‘2001414102’，‘張化司’,，‘男’,，08/12/1984)?，(‘2001414102’,，‘李利辣’,，‘女’，08/12/1984)} ◆若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的,，稱線性表是有序的,。◆線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu),，其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短,。
◆對(duì)線性表的基本操作如下(實(shí)際應(yīng)用中要根據(jù)需要選擇相應(yīng)操作或者添加未列出的操作)： ⑴建立空表l ⑵返回表l的長(zhǎng)度，即表中元素個(gè)數(shù) ⑶取線性表l中位置i處的元素(1≤i≤n)⑷取i的直接前驅(qū)元素 ⑸取i的直接后繼元素
⑹查詢?cè)豿在l中的邏輯位置
⑺在線性表l的位置i處插入元素x,，原位置元素后移一個(gè)位置 ⑻從線性表l中刪除位置i處的元素 ⑼判斷線性表是否為空 ⑽清空已存在的線性表 ⑾遍歷所有元素
云淡風(fēng)清 http:/// ⑿根據(jù)所給關(guān)鍵字查詢?cè)夭⒎祷仄湓敿?xì)信息 ⒀修改表中元素
⒁對(duì)所有元素按條件排序
2.1.3線性表的抽象數(shù)據(jù)類型定義
adt list { 數(shù)據(jù)對(duì)象：d = { ai | ai∈elemset, i=1,2,?,n, n≥0 } 數(shù)據(jù)關(guān)系：r = { | ai-1, ai∈d, i=2,3,?,n } 基本操作： initlist(&l)初始條件：無(wú)
操作結(jié)果：構(gòu)造一個(gè)空的線性表l,； listlength(l)初始條件：線性表l已存在；
操作結(jié)果：返回線性表中的元素個(gè)數(shù),； getelem(l,i,e)初始條件：線性表l已存在,，1≤i≤listlength(l)； 操作結(jié)果：用e返回l中第i個(gè)數(shù)據(jù)元素的值,； listinsert(l,i,e)初始條件：線性表l已存在,，1≤i≤listlength(l)+1，線性表未滿,；
操作結(jié)果：在線性表l中的第i個(gè)位置插入元素e,，原來(lái)位置及以后的元素都后移； listlocate(l,e)初始條件：線性表l已存在；
操作結(jié)果：返回元素e在l中的邏輯位置,，不存在則返回0,； listdelete(l,i)初始條件：線性表l已存在，1≤i≤listlength(l),； 操作結(jié)果：從表l中刪除位置i處的元素,； listclear(l)初始條件：線性表l已存在； 操作結(jié)果：清空已存在的表,； listtraverse(l)初始條件：線性表l已存在,； 操作結(jié)果：遍歷輸出所有元素； listupdate(l,i,e)初始條件：線性表l已存在,1≤i≤listlength(l),； 操作結(jié)果：將線性表l中第i個(gè)位置的值置為e,； listsort(l)初始條件：線性表l已存在；
操作結(jié)果：按一定條件對(duì)所有元素重新排序,； listdestroy(l)初始條件：線性表l已存在,； 操作結(jié)果：釋放線性表空間； …
云淡風(fēng)清 http:/// } adt list 2.2線性表的順序存儲(chǔ) 2.2.1線性表的順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)：把線性表的結(jié)點(diǎn)按邏輯順序依次存入地址連續(xù)的一組存儲(chǔ)單元里,。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表,。
順序存儲(chǔ)的線性表的特點(diǎn)：
◆線性表的邏輯順序與物理順序一致；
◆數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)體現(xiàn)的,。設(shè)有非空的線性表：(a1,，a2，?an),。順序存儲(chǔ)如下圖所示,。
在具體的機(jī)器環(huán)境下,，設(shè)線性表的每個(gè)元素需占用len個(gè)存儲(chǔ)單元,，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置，則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai)之間滿足下列關(guān)系：
loc(ai+1)=loc(ai)+l 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： loc(ai)=loc(a1)+(i-1)*len 高級(jí)語(yǔ)言中同一個(gè)數(shù)組的各個(gè)元素占用連續(xù)存儲(chǔ)單元,，具有隨機(jī)存取(指存取同一數(shù)組各元素的時(shí)間開銷相同,，不受所處位置的限制)的特性，故而在高級(jí)語(yǔ)言中通常用數(shù)組來(lái)存儲(chǔ)順序表,。除了用數(shù)組來(lái)存儲(chǔ)線性表的元素之外,，順序表還應(yīng)該表示線性表的長(zhǎng)度屬性以方便某些操作，所以用結(jié)構(gòu)體類型來(lái)定義順序表類型,。
#include
#include
#define ok #define error
-1 #define max_size 100 //最大長(zhǎng)度 typedef int status;//狀態(tài)typedef int elemtype;//元素類型,，可根據(jù)實(shí)際需要更改 typedef struct sqlist { elemtype *elem_array;//線性表存儲(chǔ)空間地址
int length;//線性表長(zhǎng)度 } sqlist;注意：c語(yǔ)言中數(shù)組的下標(biāo)值是從0開始，第i個(gè)元素的下標(biāo)值是i-1,。
2.2.2順序表的基本操作
順序存儲(chǔ)結(jié)構(gòu)中,，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找,、修改,、插入、刪除,、求長(zhǎng)度等,。
以下將對(duì)幾種主要的操作進(jìn)行討論。#include
云淡風(fēng)清 http:/// #include#define ok #define error
-1 #define max_size 100 //最大長(zhǎng)度 typedef int status;//狀態(tài)typedef int elemtype;//元素類型,，可根據(jù)實(shí)際需要更改 typedef struct sqlist { elemtype elem_array[max_size];//線性表存儲(chǔ)空間地址
int length;//線性表長(zhǎng)度 } sqlist;/*
1,、初始化
構(gòu)造一個(gè)空的線性表 */ status init_sqlist(sqlist *l){ l->length=0;return ok;} /*
2、測(cè)長(zhǎng)度
返回線性表中的元素個(gè)數(shù) */ int length_sqlist(sqlist *l){ return l->length;} /*
3,、取元素
用e返回l中第i個(gè)數(shù)據(jù)元素的值,，1≤i≤listlength(l)*/ status get_sqlist(sqlist *l,int i,elemtype *e){ if((i>=1)&&(i<=l->length)){
*e=l->elem_array[i-1];//i位置對(duì)應(yīng)的元素下標(biāo)為i-1
return ok;} else
return error;}
云淡風(fēng)清 http:/// /*
4、順序線性表的插入
在線性表l中的第i個(gè)位置插入元素e,，原來(lái)位置及以后的元素都后移,。要求1≤i≤listlength(l)+1，線性表未滿,。實(shí)現(xiàn)步驟：
(1)將線性表l中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置,。(2)將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。
(3)線性表長(zhǎng)度加1,。*/ status insert_sqlist(sqlist *l,int i,elemtype e){ int j;if((i<1)||(i>l->length+1))//位置錯(cuò)誤
return error;else
if(l->length>=max_size)//線性表上溢
//實(shí)際開發(fā)中達(dá)到空間上限時(shí)可用remalloc()函數(shù)重新分配空間,，擴(kuò)大空間容量
return error;
else
{
//i-1位置以后的所有結(jié)點(diǎn)后移
for(j=l->length-1;j>=i-1;--j)
l->elem_array[j+1]=l->elem_array[j];
l->elem_array[i-1]=e;//在i-1位置插入結(jié)點(diǎn)
l->length++;//線性表長(zhǎng)度增1
return ok;
} } /* 時(shí)間復(fù)雜度分析：
在線性表l中的第i個(gè)位置插入新結(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上,，因此,，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。
設(shè)在線性表l中的第i個(gè)位置插入結(jié)點(diǎn)的概率為pi,，不失一般性,，設(shè)各個(gè)位置插入是等概率，則pi=1/(n+1),，而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+1,。
總的平均移動(dòng)次數(shù)：einsert=∑pi*(n-i+1)(1≤i≤n)計(jì)算得：einsert=n/2。
即在順序表上做插入運(yùn)算,，平均要移動(dòng)表上一半結(jié)點(diǎn),，當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為o(n),。
*/ /*
5、線性表元素位置查詢
返回元素e在l中的邏輯位置,，不存在則返回0
云淡風(fēng)清 http:/// */ int locate_sqlist(sqlist *l,elemtype e){ int i,found=0;//found用于表示是否找到,，0：未找到 1：找到
i=0;//從第一個(gè)開始查詢
while((i
length)&&(found==0))
if(l->elem_array[i]==e)found=1;
else
i++;if(found==1)
return i+1;//返回邏輯位置編號(hào)
else
return 0;//未找到，返回0 } /*
6、刪除指定位置元素 在線性表：
l=(a1,，?ai-1,，ai，ai+1,，?,，an)中刪除結(jié)點(diǎn)ai(1≦i≦n)，使其成為線性表： l=(a1,，?ai-1,，ai+1，?,，an)要求1≤i≤listlength(l),，線性表未空。實(shí)現(xiàn)步驟：
(1)將線性表l中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移動(dòng)一個(gè)位置,。(2)線性表長(zhǎng)度減1,。*/ status delete_sqlist(sqlist *l,int i){ int k;if(l->length==0)//線性表空
{
printf(“線性表l為空!n”);
return error;} else
if(i<1||i>l->length)//指定位置不合適
{
printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!n”);
return error;
}
else
{
//i位置以后的所有結(jié)點(diǎn)前移
for(k=i;k
length;k++)
l->elem_array[k-1]=l->elem_array[k];云淡風(fēng)清 http:///
l->length--;//線性表長(zhǎng)度減1
return(ok);
} } /* 時(shí)間復(fù)雜度分析：
刪除線性表l中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上,，因此,，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。
設(shè)在線性表l中刪除第i個(gè)元素的概率為pi,，不失一般性,，設(shè)刪除各個(gè)位置是等概率，則pi=1/n,，而刪除時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i,。
則總的平均移動(dòng)次數(shù)：edelete=∑pi*(n-i)
(1≤i≤n)計(jì)算得：edelete=(n-1)/2 即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn),，當(dāng)表長(zhǎng)n較大時(shí),，算法的效率相當(dāng)?shù)?，因此算法的平均時(shí)間復(fù)雜度為o(n),。
*/ /*
7、清空 */ status clear_sqlist(sqlist *l){ l->length=0;return ok;} /*
8、遍歷 以輸出為例 */ status traverse_sqlist(sqlist *l){ int i;printf(“共有%d個(gè)元素,，以下為具體內(nèi)容：n”,l->length);for(i=0;i
length;i++)
printf(“%8d”,l->elem_array[i]);printf(“n------------------end------------------n”);return ok;} /*9、修改
將線性表l中第i個(gè)位置的值置為e,。要求線性表l已存在且1≤i≤listlength(l),。*/ status update_sqlist(sqlist *l,int i,elemtype e){ if((i<1)||(i>l->length))//位置錯(cuò)誤
云淡風(fēng)清 http:///
return error;else {
l->elem_array[i-1]=e;//放置新數(shù)據(jù)
return ok;} } /*
10、排序
按要求對(duì)線性表中元素排序,。*/ status sort_sqlist(sqlist *l){ int i,j;elemtype temp;for(i=1;i<=l->length-1;i++)
for(j=0;j<=l->length-i-1;j++)
{
if(l->elem_array[j]
elem_array[j+1])
{temp=l->elem_array[j];
l->elem_array[j]=l->elem_array[j+1];
l->elem_array[j+1]=temp;
}
} return ok;} /* 主函數(shù) */ void main(){ int xz=1,i;sqlist l;elemtype e;while(xz!=0){
printf(“
1,、初始化n
2、測(cè)長(zhǎng)度n
3、取元素n
4,、插入n
5,、查詢n
6、刪除n
7,、清空n
8,、遍歷n
9、修改n10,、排序n 0,、結(jié)束n請(qǐng)選擇：”);
scanf(“%d”,&xz);
switch(xz)
{
case 1:
if(init_sqlist(&l)==ok)
云淡風(fēng)清 http:///
printf(“初始化成功！n”);else
printf(“初始化未成功,！n”);break;case 2: printf(“線性表長(zhǎng)度為：%dn”,length_sqlist(&l));break;case 3: printf(“請(qǐng)輸入要取元素的位置：”);scanf(“%d”,&i);if(get_sqlist(&l,i,&e)==ok)
printf(“指定位置上的元素為：%dn”,e);else
printf(“error,！n”);break;case 4: printf(“請(qǐng)輸入要插入的位置：”);scanf(“%d”,&i);printf(“請(qǐng)輸入要插入的元素內(nèi)容：n”);scanf(“%d”,&e);if(insert_sqlist(&l,i,e)==ok)
printf(“插入成功n”);else
printf(“error！n”);break;case 5: printf(“請(qǐng)輸入要查詢的元素內(nèi)容：”);scanf(“%d”,&e);printf(“此元素邏輯位置為：%d(0表示未找到),。n”,locate_sqlist(&l,e));break;case 6: printf(“請(qǐng)輸入要?jiǎng)h除元素的位置：”);scanf(“%d”,&i);if(delete_sqlist(&l,i)==ok)
printf(“刪除成功n”);else
printf(“error,！n”);break;case 7: clear_sqlist(&l);break;case 8: traverse_sqlist(&l);break;
云淡風(fēng)清 http:///
case 9:
printf(“請(qǐng)輸入要修改的元素位置：”);
scanf(“%d”,&i);
printf(“請(qǐng)輸入元素的新內(nèi)容：n”);
scanf(“%d”,&e);
if(update_sqlist(&l,i,e)==ok)
printf(“修改成功n”);
else
printf(“error！n”);
break;
case 10:
sort_sqlist(&l);
printf(“排序完成,！n”);
break;
case 0:
printf(“謝謝使用,，再見！n”);
break;
default:
printf(“輸入錯(cuò)誤,！n”);
break;
} } } 需要說(shuō)明的是,，本例沒(méi)有實(shí)現(xiàn)空間的動(dòng)態(tài)分配，若要實(shí)現(xiàn)動(dòng)態(tài)分配,，可參照第三章“棧的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)”的做法,。
2.2.3順序存儲(chǔ)線性表的特點(diǎn)
優(yōu)點(diǎn)：表中任意一個(gè)結(jié)點(diǎn)的存取很方便，可以進(jìn)行隨機(jī)存取,，處于不同位置上的結(jié)點(diǎn)的存取時(shí)間從理論上來(lái)說(shuō)相同,，也能進(jìn)行插入和刪除操作。
缺點(diǎn)：
(1)插入和刪除不方便,。為保持連續(xù)存放,，操作中需要移動(dòng)大量元素。
(2)會(huì)造成空間的浪費(fèi)以及不易擴(kuò)充,。所占空間通常情況下大小固定,，處理長(zhǎng)度變化較大的線性表時(shí)，分配空間大小不夠,，會(huì)造成溢出,；分配空間太大，會(huì)造成浪費(fèi),。
2.3線性表的鏈?zhǔn)酱鎯?chǔ) 2.3.1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)：用一組任意(即不必要連續(xù))的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素,。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱線性鏈表,。
鏈表中結(jié)點(diǎn)所占用的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的,，甚至是零散分布在內(nèi)存中的任意位置上的,，鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。
為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系,，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí),，還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的
云淡風(fēng)清 http:/// 地址(或位置)，稱為指針(pointer)或鏈(link),，這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu),，如下圖所示。
data：數(shù)據(jù)域,，存放結(jié)點(diǎn)的值,。
next：指針域，存放結(jié)點(diǎn)的直接后繼的地址,。
鏈表通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起,。每一個(gè)結(jié)點(diǎn)只包含一個(gè)指針域的鏈表，稱為單鏈表,。
為操作方便,，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭指針變量head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或存放鏈表長(zhǎng)度等輔助信息),，此時(shí)通常稱為帶頭結(jié)點(diǎn)的單鏈表,。當(dāng)然，也可以讓頭結(jié)點(diǎn)的數(shù)據(jù)域存放有效數(shù)據(jù),，此時(shí)稱為不帶頭結(jié)點(diǎn)的單鏈表,。相對(duì)而言，帶頭結(jié)點(diǎn)的單鏈表浪費(fèi)了一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域,，但會(huì)給編程帶來(lái)一定方便,。
帶頭結(jié)點(diǎn)的單鏈表其基本結(jié)構(gòu)如下：
說(shuō)明：
(1)整個(gè)鏈表由若干個(gè)結(jié)點(diǎn)組成，一個(gè)結(jié)點(diǎn)占用一個(gè)內(nèi)存塊,，而每個(gè)結(jié)點(diǎn)又分為兩大部分：數(shù)據(jù)域和指針域,，其中數(shù)據(jù)域存放用戶數(shù)據(jù)，指針域用于存放后一個(gè)結(jié)點(diǎn)的地址,，通過(guò)指針域?qū)⑦壿嬌锨昂笙噜彽慕Y(jié)點(diǎn)連接起來(lái),，這樣，通過(guò)前一個(gè)結(jié)點(diǎn)指針域中存放的地址就可以找到后一個(gè)結(jié)點(diǎn),?？煽闯觯總€(gè)結(jié)點(diǎn)的指針域?qū)嶋H上充當(dāng)了指針變量的角色,，只要結(jié)點(diǎn)數(shù)可變,，則意味著指針變量數(shù)也可變，而事實(shí)上結(jié)點(diǎn)所對(duì)應(yīng)的這些內(nèi)存塊完全可以多次動(dòng)態(tài)分配,，這也就意味著指針域(相當(dāng)于指針變量)的個(gè)數(shù)可以根據(jù)需要?jiǎng)討B(tài)調(diào)整,，這就解決了前述的“程序中變量個(gè)數(shù)固定，但問(wèn)題本身所需變量個(gè)數(shù)不定”的矛盾,。
(2)設(shè)置一個(gè)頭指針變量指向首結(jié)點(diǎn),，在帶頭結(jié)點(diǎn)的單鏈表中，此結(jié)點(diǎn)不存放有效數(shù)據(jù),。(3)末尾結(jié)點(diǎn)的指針域設(shè)置為空“null”表示鏈表的結(jié)束,，相當(dāng)于字符串中的''。
(4)在沒(méi)有用戶數(shù)據(jù)的情況下,，此鏈表只有一個(gè)結(jié)點(diǎn),，此結(jié)點(diǎn)既是首結(jié)點(diǎn)，又是末結(jié)點(diǎn),，結(jié)點(diǎn)的指針域?yàn)椤皀ull”,，此時(shí)表示鏈表為邏輯“空”，也就是說(shuō),，鏈表的初始狀態(tài)應(yīng)該如下圖所示,。
單鏈表是由表頭唯一確定的，因此單鏈表可以用頭指針的名字來(lái)命名,。例
1,、線性表l=(bat，cat,，eat,，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如下圖所示,。
云淡風(fēng)清 http:///
1,、結(jié)點(diǎn)的描述與實(shí)現(xiàn)
c語(yǔ)言中用帶指針的結(jié)構(gòu)體類型來(lái)描述 typedef int elemtype;typedef struct lnode { elemtype
data;//數(shù)據(jù)域，保存結(jié)點(diǎn)的值
struct
lnode *next;//指針域,，保存后繼結(jié)點(diǎn)地址 }lnode;
//結(jié)點(diǎn)的類型
2,、結(jié)點(diǎn)空間分配及回收的實(shí)現(xiàn)
結(jié)點(diǎn)存儲(chǔ)空間是通過(guò)動(dòng)態(tài)內(nèi)存分配和釋放來(lái)實(shí)現(xiàn)的，即需要時(shí)分配,，不需要時(shí)釋放,。在c語(yǔ)言中可通過(guò)標(biāo)準(zhǔn)函數(shù)：malloc()，realloc(),，sizeof(),，free()等來(lái)實(shí)現(xiàn)分配。
動(dòng)態(tài)分配：p=(lnode*)malloc(sizeof(lnode));函數(shù)malloc分配了一個(gè)類型為lnode的結(jié)點(diǎn)變量的空間,，并將其首地址放入指針變量p中,。動(dòng)態(tài)釋放：free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū),。p必須是最近一次調(diào)用malloc()函數(shù)時(shí)的返回值。動(dòng)態(tài)重新分配：p=(lnode*)realloc(p,newsize);先判斷當(dāng)前的指針是否有足夠的連續(xù)空間,，如果有,，擴(kuò)大p指向的地址，并且將p返回,，如果空間不夠,，先按照newsize指定的大小分配空間，將原有數(shù)據(jù)從頭到尾拷貝到新分配的內(nèi)存區(qū)域,，而后釋放原來(lái)p所指內(nèi)存區(qū)域,，同時(shí)返回新分配的內(nèi)存區(qū)域的首地址，即重新分配存儲(chǔ)器塊的地址,。返回值：如果重新分配成功則返回指向被分配內(nèi)存的指針,，否則返回空指針null。
3,、最常用的基本操作 ⑴ 結(jié)點(diǎn)的賦值 lnode *p;p=(lnode*)malloc(sizeof(lnode));p->data=20;p->next=null;講課時(shí)板書教案上的幾種常見的指針操作,。效果如下圖。
⑵常見的指針操作 ①q=p;
云淡風(fēng)清 http:/// ②q=p->next;
③p=p->next;
④q->next=p;
⑤q->next=p->next;
云淡風(fēng)清 http:///
2.3.2單鏈?zhǔn)降幕静僮?/p>
以帶頭結(jié)點(diǎn)的單鏈表為例,。#define ok #define error
-1 typedef int status;//狀態(tài) #include “stdlib.h” #include “stdio.h” typedef int elemtype;typedef struct lnode { elemtype
data;//數(shù)據(jù)域,，保存結(jié)點(diǎn)的值
struct
lnode *next;//指針域，保存后繼結(jié)點(diǎn)地址 }lnode;
//結(jié)點(diǎn)的類型
/*
1,、鏈表初始化(建立空鏈表)*/ lnode * init_linklist(void){ lnode *l;l=(lnode *)malloc(sizeof(lnode));//給頭結(jié)點(diǎn)分配空間
if(l!=null)
l->next=null;//指針域置為空以作為結(jié)束標(biāo)記
return l;} /*
2,、頭插入法建表
從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù),，生成新結(jié)點(diǎn),，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,，直到讀入結(jié)束標(biāo)志為止,，每次插入的結(jié)點(diǎn)都作為鏈表的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。
*/
云淡風(fēng)清 http:/// status create1_linklist(lnode *l){ elemtype data;char sfjx=1;//0：結(jié)束 1：繼續(xù)
lnode *p;while(sfjx!=0){
p=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間
if(p==null)
return error;//空間分配不成功
else
{
printf(“請(qǐng)輸入元素內(nèi)容：”);
scanf(“%d”,&data);//讀入值
p->data=data;//數(shù)據(jù)域賦值
//鉤鏈,，新創(chuàng)建的結(jié)點(diǎn)總是作為第一個(gè)數(shù)據(jù)結(jié)點(diǎn)
p->next=l->next;
l->next=p;
}
printf(“是否繼續(xù)(0：結(jié)束 1：繼續(xù))：”);
scanf(“%d”,&sfjx);} return ok;} /*
3,、尾插入法建表
頭插入法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反,。若希望二者次序一致,，可采用尾插法建表。
該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾,，使其成為當(dāng)前鏈表的尾結(jié)點(diǎn),。*/ status create2_linklist(lnode *l){ elemtype data;char sfjx=1;//0：結(jié)束 1：繼續(xù)
lnode *p,*q;//找到已有鏈表的末結(jié)點(diǎn)
q=l;while(q->next!=null)
q=q->next;while(sfjx!=0){
p=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間
if(p==null)
云淡風(fēng)清 http:///
return error;//空間分配不成功
else
{
printf(“請(qǐng)輸入元素內(nèi)容：”);
scanf(“%d”,&data);//讀入值
p->data=data;//數(shù)據(jù)域賦值
//鉤鏈，新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)
q->next=p;
q=p;//q重新指向末結(jié)點(diǎn)
}
printf(“是否繼續(xù)(0：結(jié)束 1：繼續(xù))：”);
scanf(“%d”,&sfjx);} q->next=null;//重設(shè)鏈表結(jié)束標(biāo)記
return(ok);} /*
4,、按序號(hào)查找,，取單鏈表中的第i個(gè)元素,。
對(duì)于單鏈表，不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn),，而只能從鏈表的頭結(jié)點(diǎn)出發(fā),，沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索,，直到搜索到第i個(gè)結(jié)點(diǎn)為止,。因此，鏈表不是隨機(jī)存取結(jié)構(gòu),。
設(shè)單鏈表的長(zhǎng)度為n,，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí),，i的值是合法的,。*/ status get_linklist(lnode *l,int i,elemtype *e){
int j=1;lnode *p;p=l->next;//使p指向第一個(gè)結(jié)點(diǎn)
while((p!=null)&&(j
p=p->next;//移動(dòng)指針p
j++;
//j計(jì)數(shù)
} if(p==null)//找不到
return(error);else {
*e=p->data;
return(ok);} } /*
云淡風(fēng)清 http:///
5、按值查找
按值查找是在鏈表中,，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)? 若有,，則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回null,。
*/ lnode *locate_linklist(lnode *l,elemtype key){ lnode *p;p=l->next;while((p!=null)&&(p->data!=key))
p=p->next;if(p!=null)//找到了
return p;else//找不到
return(null);} /*
6,、單鏈表的插入，插入到指定位置
在以l為頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn),。
插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上,，即插入到ai-1與ai之間。因此,，必須首先找到ai-1所在的結(jié)點(diǎn)p,，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q，q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn),。
*/ status insert_linklist(lnode *l,int i,elemtype e){ int j=0;lnode *p,*q;p=l;//找待插入位置的前一個(gè)結(jié)點(diǎn)位置
while((p!=null)&&(j
p=p->next;
j++;} if((j!=i-1)||(p==null))//位置不合適
{
printf(“位置不合適,，無(wú)法插入！n”);
return error;} else {
q=(lnode *)malloc(sizeof(lnode));//給新結(jié)點(diǎn)分配空間
if(q==null)
return error;
else
云淡風(fēng)清 http:///
{
//實(shí)現(xiàn)插入
q->data=e;
q->next=p->next;
p->next=q;
return ok;
} } } /*
7,、按序號(hào)刪除
刪除單鏈表中的第i個(gè)結(jié)點(diǎn),。
為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲(chǔ)地址,。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中,，因此，必須首先找到ai-1的存儲(chǔ)位置p,，然后令p->next指向ai的直接后繼結(jié)點(diǎn),，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間,，將其歸還給“存儲(chǔ)池”,。設(shè)單鏈表長(zhǎng)度為n,，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≤i≤n時(shí)是合法的。則當(dāng)i=n+1時(shí),，雖然被刪結(jié)點(diǎn)不存在,，但其前趨結(jié)點(diǎn)卻存在，是終端結(jié)點(diǎn),。故判斷條件之一是p->next!=null,。顯然此算法的時(shí)間復(fù)雜度也是o(n)。
*/ status delete1_linklist(lnode *l,int i){ int j=1;lnode *p,*q;p=l;q=l->next;//找待刪除位置的前一個(gè)結(jié)點(diǎn)位置
while(q!=null && j
p=q;
q=q->next;
j++;} if((q==null)||(i<=0)){
printf(“位置不合適,，無(wú)法刪除,！n ”);
return error;} else {
//實(shí)現(xiàn)刪除
p->next=q->next;
free(q);
return ok;} }
云淡風(fēng)清 http:/// /*
8、按值刪除
刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn),。
與按值查找相類似,，首先要查找值為key的結(jié)點(diǎn)是否存在? 若存在，則刪除,；否則返回null,。*/ status delete2_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//找待刪除結(jié)點(diǎn)位置，q指向其位置,，p指向其前驅(qū)結(jié)點(diǎn)
while(q!=null && q->data!=key){
p=q;
q=q->next;} if(q!=null)//找到了
{
//實(shí)現(xiàn)刪除
p->next=q->next;
free(q);
return ok;} else {
printf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在,！n”);
return error;} } /*
9、刪除單鏈表中值為key的所有結(jié)點(diǎn)
與按值查找相類似,，但比前面的算法更簡(jiǎn)單,。
基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查,，若結(jié)點(diǎn)的值為key,，則刪除之，然后檢查下一個(gè)結(jié)點(diǎn),，直到所有的結(jié)點(diǎn)都檢查,。
*/ void delete3_linklist(lnode *l,int key){ lnode *p=l,*q=l->next;//p始終指向q的前驅(qū)，以方便刪除操作的實(shí)現(xiàn)
while(q!=null){
if(q->data==key)
{
p->next=q->next;
云淡風(fēng)清 http:///
free(q);
q=p->next;
}
else
{
p=q;
q=q->next;
} } } /*
10,、刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn),，使得所有結(jié)點(diǎn)的值都不相同 與按值查找相類似，但比前面的算法更復(fù)雜,。
基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開始,，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查：檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，只要有值和該結(jié)點(diǎn)的值相同,，則刪除之,；然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。
*/ void delete4_linklist(lnode *l){ lnode *p=l->next,*q,*ptr;while(p!=null)//檢查鏈表中所有結(jié)點(diǎn)
{
q=p;
ptr=p->next;
while(ptr!=null)//檢查結(jié)點(diǎn)p的所有后繼結(jié)點(diǎn)ptr
{
if(ptr->data==p->data)
{
q->next=ptr->next;
free(ptr);
ptr=q->next;
}
else
{
q=ptr;
ptr=ptr->next;
}
}
p=p->next;} } /*
云淡風(fēng)清 http:///
11,、修改指定位置的數(shù)據(jù) */ status modify_linklist(lnode *l,int i,elemtype e){ int j=1;lnode *p;p=l->next;//找待修改結(jié)點(diǎn)位置
while(p!=null && j
p=p->next;
j++;} if((p==null)||(i<=0))//找不到
{
printf(“位置不合適,，無(wú)法修改！n ”);
return error;} else {
p->data=e;
return ok;} } /*
12,、單鏈表遍歷 以輸出為例 */ void traverse_linklist(lnode *l){ lnode *p;p=l->next;while(p!=null){
printf(“%8d”,p->data);
p=p->next;} printf(“n”);} /*
13,、單鏈表的合并
設(shè)有兩個(gè)有序的單鏈表，它們的頭指針?lè)謩e是la,、lb,，將它們合并為以lc為頭指針的有序鏈表。算法說(shuō)明：算法中pa,，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn),，pc是合并過(guò)程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。
云淡風(fēng)清 http:///
合并了值為-7,，-2的結(jié)點(diǎn)后示意圖如下圖所示。
*/ lnode *merge_linklist(lnode *la,lnode *lb){ lnode *lc,*pa,*pb,*pc,*ptr;lc=la;pc=la;//指向新鏈表的末結(jié)點(diǎn)
pa=la->next;pb=lb->next;while(pa!=null && pb!=null){
if(pa->data
data)//將pa所指的結(jié)點(diǎn)合并,，pa指向下一個(gè)結(jié)點(diǎn)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
if(pa->data>pb->data)//將pb所指的結(jié)點(diǎn)合并,，pb指向下一個(gè)結(jié)點(diǎn)
{
pc->next=pb;
pc=pb;
pb=pb->next;
云淡風(fēng)清 http:///
}
else//將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除
{
pc->next=pa;
pc=pa;
pa=pa->next;
ptr=pb;
pb=pb->next;
free(ptr);
} } //將剩余的結(jié)點(diǎn)鏈上
if(pa!=null)
pc->next=pa;else
pc->next=pb;
free(lb);return(lc);} /*
14,、單鏈表的排序
采用插入排序方法,，以升序?yàn)槔?*/ void sort_linklist(lnode *l){ lnode *p,*q,*r,*s;p=l->next;l->next=null;while(p!=null){
q=l->next;
r=l;
while((q!=null)&&(p->data>q->data))
{
q=q->next;
r=r->next;
}
s=p->next;
r->next=p;
p->next=q;
p=s;} }
云淡風(fēng)清 http:/// /*
15、單鏈表的釋放 */ void release_linklist(lnode *l){ lnode *p,*q;p=l;//指向頭結(jié)點(diǎn),，從此結(jié)點(diǎn)開始釋放
while(p!=null){
q=p->next;
free(p);
p=q;} } void main(){ int xz=1,i;lnode *l,*l1,*l2;elemtype e;while(xz!=0){
printf(“
1,、鏈表初始化n
2、頭插入法建表n
3,、尾插入法建表n
4,、按序號(hào)查找n
5、按值查找n
6,、單鏈表的插入n”);
printf(“
7,、按序號(hào)刪除n
8、按值刪除n
9,、刪除單鏈表中指定值的所有結(jié)點(diǎn)n10,、刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)n”);
printf(“
11、修改指定位置的數(shù)據(jù)n12,、單鏈表遍歷n13,、單鏈表的合并n14、單鏈表的排序n15,、單鏈表的釋放n 0,、結(jié)束n請(qǐng)選擇：”);
scanf(“%d”,&xz);
switch(xz)
{
case 1:
l=init_linklist();
if(l!=null)
printf(“初始化成功！n”);
break;
case 2:
if(create1_linklist(l)==ok)
printf(“建立成功！n”);
else
printf(“建立不成功,！n”);
break;
case 3:
if(create2_linklist(l)==ok)
printf(“建立成功,！n”);
云淡風(fēng)清 http:///
else
printf(“建立不成功！n”);break;case 4: printf(“請(qǐng)輸入要查找元素的序號(hào)：”);scanf(“%d”,&i);if(get_linklist(l,i,&e)==ok)
printf(“%dn”,e);else
printf(“找不到,！n”);break;case 5: printf(“請(qǐng)輸入要查找元素的關(guān)鍵字：”);scanf(“%d”,&e);l1=locate_linklist(l,e);if(l1!=null)
printf(“%dn”,l1->data);else
printf(“找不到,！n”);break;case 6: printf(“請(qǐng)輸入要插入元素的內(nèi)容：”);scanf(“%d”,&e);printf(“請(qǐng)輸入插入位置：”);scanf(“%d”,&i);if(insert_linklist(l,i,e)==ok)
printf(“插入成功！n”);else
printf(“插入不成功,！n”);break;case 7: printf(“請(qǐng)輸入要?jiǎng)h除元素的位置：”);scanf(“%d”,&i);if(delete1_linklist(l,i)==ok)
printf(“成功刪除,！n”);else
printf(“未成功刪除！n”);break;case 8: printf(“請(qǐng)輸入要元素的內(nèi)容：”);scanf(“%d”,&e);if(delete2_linklist(l,e)==ok)
printf(“成功刪除,！n”);else
云淡風(fēng)清 http:///
printf(“未成功刪除,！n”);break;case 9: printf(“請(qǐng)輸入要元素的內(nèi)容：”);scanf(“%d”,&e);delete3_linklist(l,e);printf(“成功刪除！n”);break;case 10: delete4_linklist(l);printf(“成功刪除,！n”);
break;case 11: printf(“請(qǐng)輸入修改位置：”);scanf(“%d”,&i);printf(“請(qǐng)輸入元素的新內(nèi)容：”);scanf(“%d”,&e);if(modify_linklist(l,i,e)==ok)
printf(“修改成功,！n”);else
printf(“修改不成功！n”);break;case 12: traverse_linklist(l);
break;case 13: l1=init_linklist();l2=init_linklist();if((l1==null)||(l2==null))
printf(“初始化不成功,！n”);else {
printf(“請(qǐng)建立第一個(gè)鏈表：n”);
create2_linklist(l1);
printf(“請(qǐng)建立第二個(gè)鏈表：n”);
create2_linklist(l2);
sort_linklist(l1);
sort_linklist(l2);
l=merge_linklist(l1,l2);
printf(“合并后的結(jié)果如下：n”);
traverse_linklist(l);} break;case 14:
云淡風(fēng)清 http:///
}
} sort_linklist(l);break;case 15: release_linklist(l);
break;case 0: printf(“謝謝使用,，再見！n”);break;default: printf(“輸入錯(cuò)誤,！n”);break;} 2.4循環(huán)鏈表
循環(huán)鏈表(circular linked list)：是一種頭尾相接的鏈表,，其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán),，這樣,，從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活,。
下圖是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖,。
循環(huán)鏈表的操作：
對(duì)于帶頭結(jié)點(diǎn)的單循環(huán)鏈表，除鏈表的合并外,，其它操作和單線性鏈表基本上一致,，僅僅需要在單線性鏈表操作算法基礎(chǔ)上做以下簡(jiǎn)單修改：
1、判斷是否是空鏈表 head->next==head;
2,、判斷是否是表尾結(jié)點(diǎn) p->next==head;例：有m個(gè)人圍成一圈,，順序排號(hào)。從第一個(gè)人開始報(bào)數(shù),，凡報(bào)到3的人退出圈子,，問(wèn)最后留下的那位是原來(lái)的第幾號(hào)？
根據(jù)問(wèn)題描述可知,，該問(wèn)題中m個(gè)人圍坐在一起形成首尾相接的環(huán),，比較自然的一種思路是用循環(huán)鏈表模擬這個(gè)環(huán),。從第3個(gè)人開始出圈，相當(dāng)于從鏈表中刪除一個(gè)結(jié)點(diǎn),。該程序主要由三個(gè)模塊組成：
1,、建立循環(huán)單鏈表存放初始各人編號(hào)；
2,、報(bào)數(shù)并按順序輸出出圈人的編號(hào),；
3、輸出剩下的人的編號(hào),。具體步驟如下：
云淡風(fēng)清 http:/// 第一步：輸入人員總數(shù),；
第二步：創(chuàng)建循環(huán)鏈表并向單鏈表中填入人員編號(hào)； 第三步：找第一個(gè)開始報(bào)數(shù)的人,；
第四步：數(shù)到3讓此人出圈(刪除對(duì)應(yīng)結(jié)點(diǎn)),；
第五步：接著開始報(bào)數(shù)，重復(fù)第四步,，直到圈中剩余一個(gè)為止,； 第六步：輸出剩下結(jié)點(diǎn)中的編號(hào)，即為最終所要求的編號(hào),。程序源代碼： #include “stdio.h” #include “stdlib.h” #define maxn 100 //最大個(gè)數(shù) struct node { int data;struct node *next;};void main(){ struct node *head, *s, *q, *t;int n, m, count=0, i;do//輸入總個(gè)數(shù)
{ printf(“請(qǐng)輸入總個(gè)數(shù)(1－%d)：”,maxn);scanf(“%d”,&m);}while((m<1)||(m>maxn));do//輸入出圈時(shí)要數(shù)到的個(gè)數(shù)
{ printf(“要數(shù)到的個(gè)數(shù)(1--%d)：”,m);scanf(“%d”,&n);}while((n<1)||(n>m));for(i=0;i
{ s=(struct node *)malloc(sizeof(struct node));s->data=i+1;s->next=null;if(i==0){ head=s;q=head;} else
{ q->next=s;q=q->next;}
云淡風(fēng)清 http:/// } q->next=head;//形成圈
//以下代碼輸出原始狀態(tài)
printf(“原始狀態(tài)：n”);q=head;while(q->next!=head){ printf(“%4d”,q->data);q=q->next;} printf(“%4dn”,q->data);q=head;//以下代碼實(shí)現(xiàn)出圈
printf(“出圈順序：n”);do { count++;if(count==n-1){ t=q->next;q->next=t->next;count=0;printf(“%4d”,t->data);free(t);} q=q->next;}while(q->next!=q);printf(“n剩下的是%4dn”,q->data);} 注意：此程序采用的是不帶頭結(jié)點(diǎn)的單鏈表,，以免在循環(huán)鏈表中由于不存放有效數(shù)據(jù)的頭結(jié)點(diǎn)的存在而影響計(jì)數(shù)。
2.5雙向鏈表
雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的,。單鏈表只
數(shù)據(jù)結(jié)構(gòu)演講篇三
《數(shù)據(jù)結(jié)構(gòu)》教案
課程性質(zhì)和任務(wù)
本課程是計(jì)算機(jī)專業(yè)的主要專業(yè)基礎(chǔ)課程之一。本課程的參考教學(xué)時(shí)數(shù)為54學(xué)時(shí),，實(shí)際講課學(xué)時(shí)為35,，實(shí)驗(yàn)學(xué)時(shí)為16。其主要內(nèi)容包括順序表,、鏈表,、棧、隊(duì),、串,、樹和圖的結(jié)構(gòu)，以及查找和排序技術(shù),。通過(guò)本課程的教學(xué),，使學(xué)生理解計(jì)算機(jī)軟件系統(tǒng)所必須的數(shù)據(jù)結(jié)構(gòu)及算法的內(nèi)部邏輯，掌握在軟件工程中大量存在的查找和排序技術(shù),，并通過(guò)大量的上機(jī)實(shí)習(xí),，實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的算法，以便為后續(xù)課程的學(xué)習(xí)提供專業(yè)基礎(chǔ)知識(shí),，同時(shí)增強(qiáng)學(xué)生編制程序的能力,。
課程教學(xué)目標(biāo)
通過(guò)本課程的學(xué)習(xí)，應(yīng)達(dá)到以下目標(biāo)：
? 深刻理解數(shù)據(jù)結(jié)構(gòu)中線性表、棧,、隊(duì)和鏈的概念,、算法及其基本應(yīng)用。
? 理解樹的基本概念,，學(xué)會(huì)建立二叉樹,，并在二叉樹上進(jìn)行查找、插入和刪除等各種運(yùn)算,。
? 理解圖的基本結(jié)構(gòu)和算法,，了解圖的路徑問(wèn)題。
? 熟練掌握幾種重要的內(nèi)部排序和查找技術(shù),，了解外部排序的一般過(guò)程,。
? 能熟練地運(yùn)用c語(yǔ)言，準(zhǔn)確,、清晰地編制與本課程有關(guān)的算法,，并能上機(jī)調(diào)試通過(guò)。
新疆農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)課程教案
第一講 緒論(對(duì)應(yīng)教材p1—p17)
一,、教學(xué)目的和要求
要求掌握數(shù)據(jù)結(jié)構(gòu)中基本概念的定義,，理解數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容，了解抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn),，理解算法評(píng)價(jià)的兩個(gè)指標(biāo),。
二、授課主要內(nèi)容
1.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容 2.數(shù)據(jù)結(jié)構(gòu)中涉及的基本概念
3.算法的概念,、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)
三,、教學(xué)重點(diǎn)難點(diǎn)
數(shù)據(jù)結(jié)構(gòu)中的基本概念、算法的概念,、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)
四,、授課內(nèi)容和方法
【口述】當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)：所處理的數(shù)據(jù)量大且具有一定的關(guān)系；對(duì)其操作不再是單純的數(shù)值計(jì)算,，而更多地是需要對(duì)其進(jìn)行組織,、管理和檢索。
一,、什么是數(shù)據(jù)結(jié)構(gòu)
我們大家知道許多非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型常常是數(shù)學(xué)方程,，如線性方程組、微分方程,。所以這類非數(shù)值計(jì)算問(wèn)題的解決就歸結(jié)于對(duì)數(shù)學(xué)模型設(shè)計(jì)算法,、編寫程序。然而在現(xiàn)實(shí)社會(huì)中存在著許多非數(shù)值計(jì)算問(wèn)題,，其數(shù)學(xué)模型難以用數(shù)學(xué)方程描述,。
1,、舉例說(shuō)明
? 圖書館的書目檢索自動(dòng)化問(wèn)題----計(jì)算機(jī)處理的對(duì)象之間存在著線性關(guān)系，稱為線性的數(shù)據(jù)結(jié)構(gòu),。
? 人機(jī)對(duì)奕問(wèn)題----計(jì)算機(jī)處理的對(duì)象是一個(gè)個(gè)格局,。所有可能出現(xiàn)的格局是一棵倒置的樹。
? 多岔路口交通燈的管理問(wèn)題----數(shù)學(xué)模型是圖的數(shù)學(xué)結(jié)構(gòu),。
【由以上舉例引出下列結(jié)論：】
非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型是表,、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)?！究偨Y(jié)出定義】 數(shù)據(jù)結(jié)構(gòu)：是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)操作對(duì)象以及它們之間關(guān)系和操作的一門學(xué)科,。（三個(gè)要素：對(duì)象、關(guān)系及操作（運(yùn)算））
2,、《數(shù)據(jù)結(jié)構(gòu)》課程的介紹
1968年美國(guó)克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系： 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作,。
數(shù)據(jù)結(jié)構(gòu)是一門綜合性的專業(yè)課程，是一門介于數(shù)學(xué),、計(jì)算機(jī)硬件,、計(jì)算機(jī)軟件之間的一門核心課程。是設(shè)計(jì)和實(shí)現(xiàn)編譯系統(tǒng),、操作系統(tǒng),、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)。
二,、基本概念和術(shù)語(yǔ)
1,、數(shù)據(jù) 數(shù)據(jù)：是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。是計(jì)算機(jī)
加工的“原料”,。
數(shù)據(jù)元素:是數(shù)據(jù)的基本單位,，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。
數(shù)據(jù)項(xiàng):有時(shí),，一個(gè)數(shù)據(jù)元素可由多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位,。
2,、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合,，是數(shù)據(jù)的一個(gè)子集,。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。四類基本結(jié)構(gòu)：集合,、線性結(jié)構(gòu),、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu),。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組
data_structure=(d,s)其中,，d 是數(shù)據(jù)元素的有限集,，s 是d上關(guān)系的有限集。
例：復(fù)數(shù) complex=(c,r)例：課題小組 group=(p,r)p={t,g1,?,gn,s11,?,snm}1≤n≤3,，1≤m≤2,，r={r1,r2} r1={
|1≤i≤n, 1≤n≤3,} r2={
|1≤i≤n, 1≤j≤m,1≤m≤2,} 數(shù)據(jù)結(jié)構(gòu)一般包括三方面的內(nèi)容：
① 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。② 存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器的表示,。用于表示數(shù)據(jù)元素的位串稱之為元素或結(jié)點(diǎn),。用于表示數(shù)據(jù)項(xiàng)的位串稱之為數(shù)據(jù)域。
③ 數(shù)據(jù)的運(yùn)算：對(duì)數(shù)據(jù)施加的操作,。
算法的設(shè)計(jì)取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu),，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。
3,、數(shù)據(jù)的兩種存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu)：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里,，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。通常順序存儲(chǔ)結(jié)構(gòu)是借助于語(yǔ)言的數(shù)組來(lái)描述的,。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：不要求邏輯上相鄰的結(jié)點(diǎn)物理上也相鄰,，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的，通常要借助于語(yǔ)言的指針類型來(lái)描述,。
*
4,、數(shù)據(jù)類型、抽象數(shù)據(jù)類型
數(shù)據(jù)類型:是一個(gè)值的集合和定義在這個(gè)值集上的所有的操作,。例如,，整數(shù)類型。數(shù)據(jù)類型可分為：非結(jié)構(gòu)的原子類型和結(jié)構(gòu)類型,。
原子類型的值是不可分解的,，結(jié)構(gòu)類型的值是由若干成分按某種結(jié)構(gòu)組成的。
抽象數(shù)據(jù)類型:是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作,。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念,，它僅取決于數(shù)據(jù)類型的邏輯性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)是無(wú)關(guān)的,。
抽象數(shù)據(jù)類型的定義由一個(gè)值域和定義在該值域上的一組操作組成,。抽象數(shù)據(jù)類型按其值的不同特性，分為三種類型： ① 原子類型:變量的值是不可分解的,。
② 固定聚合類型:變量的值由確定數(shù)目的成分按某種結(jié)構(gòu)組成,。③ 可變聚合類型:其值的成分?jǐn)?shù)目不確定。
抽象數(shù)據(jù)類型的形式定義：我們用一個(gè)三元組來(lái)表示一個(gè)抽象數(shù)據(jù)類型,。
（d,，s，p）
d是數(shù)據(jù)對(duì)象,，s是d上的關(guān)系集,，p是對(duì)d的基本操作,。
格式：
adt 抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作的定義〉 }adt 抽象數(shù)據(jù)類型名。
數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述,。數(shù)據(jù)基本操作的定義格式：
基本操作名（參數(shù)表）
初始條件：〈初始條件描述〉
操作結(jié)果：〈操作結(jié)果描述〉 例：
adt triplet{ 數(shù)據(jù)對(duì)象：d={e1,，e2,e3 |e1,e2,e3∈elemset(定義了關(guān)系運(yùn)算的某個(gè)集合)} 數(shù)據(jù)關(guān)系：r1={〈e1,e2>,
〉 基本操作：
inittriplet(&t,v1,v2,v3)destroytriplet（&t）get（t,i,&e）put(&t,i,e)isascending(t)isdescending(t)max(t,&e)min(t,&e)
}adt triplet 多形數(shù)據(jù)類型:是其值的成分不確定的數(shù)據(jù)類型。
三,、抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)
抽象數(shù)據(jù)類型可通過(guò)固有數(shù)據(jù)類型來(lái)表示和實(shí)現(xiàn),，即利用處理器中已存在的數(shù)據(jù)類型來(lái)說(shuō)明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來(lái)組合新的操作,。
1,、類c語(yǔ)言
精選了c 的一個(gè)子集，擴(kuò)充修改,，增強(qiáng)了語(yǔ)言的描述功能,。? 預(yù)定義常量和類型
? 數(shù)據(jù)結(jié)構(gòu)的表示：存儲(chǔ)結(jié)構(gòu)用類型（typedef）定義來(lái)描述。
數(shù)據(jù)元素類型約定為elemtype.? 基本操作的算法用函數(shù)描述：
函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）{ //算法說(shuō)明
語(yǔ)句序列
}//函數(shù)名
增加了引用調(diào)用的參數(shù)傳遞方式,。
? 賦值語(yǔ)句,、選擇語(yǔ)句、循環(huán)語(yǔ)句,、結(jié)束語(yǔ)句,、輸入輸出語(yǔ)句、注釋語(yǔ)句 ? 基本函數(shù) ? 邏輯運(yùn)算約定
例：triplet的表示和實(shí)現(xiàn)
//采用動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)
typedef elemtype * triplet://由inittriplet分配三個(gè)元素存儲(chǔ)空間 //基本操作的函數(shù)原型說(shuō)明
status inittriplet(triplet &t,elemtype v1, elemtype v2, elemtype v3)status destroytriplet（&t）status get（t,i,&e）status put(&t,i,e)status isascending(t)status isdescending(t)status max(t,&e)status min(t,&e)//基本操作的實(shí)現(xiàn)
status inittriplet(triplet &t, elemtype v1, elemtype v2, elemtype v3){ //構(gòu)造三元組t,，依次置t 的三個(gè)元素的處值為v1,v2和v3,。
t=(elemtype)malloc(3*sizeof(elemtype));//分配三個(gè)元素的存儲(chǔ)空間
if(!t)exit(overflow);//分配存儲(chǔ)空間失敗 t[0]=v1;t[1]=v2;t[2]=v3;return ok;}//inittriplet status destroytriplet（triplet &t）{ //銷毀三元組t?！ぁぁぁぁぁ?/p>
}//min
四,、算法和算法分析
1、算法（algorithm）
是對(duì)特定問(wèn)題求解步驟的一種描述,，它是指令的有限序列,。算法具有五個(gè)重要特性：有窮性、確定性,、可行性,、輸入、輸出
2,、算法設(shè)計(jì)的要求
正確性、可讀性,、健壯性和效率與低存儲(chǔ)量要求
3,、算法效率的度量
算法時(shí)間是由控制結(jié)構(gòu)和原操作的決定的。做法：選取一種是基本操作的原操作,，以該基本操作重復(fù)的次數(shù)作為算法的時(shí)間量度,。
時(shí)間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f（n）,，t（n）=o（f（n））
它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)綠相同,。
語(yǔ)句的頻度：是該語(yǔ)句重復(fù)執(zhí)行的次數(shù),。
例：求兩個(gè)n階方陣的乘積c=a×b，其算法如下： #define n 100 void matrixmultiply(int a[n][n],int b[n][n],int c[n][n]){ int i,j,k for(i=1;i<=n;++i)n+1
for(j=1;j<=n;++j)n*(n+1)
c[i][j]=0;n2
for(k=1;k<=n,k++)n2(n+1)
3c[i][j]=c[i][j]+a[i][k]*b[k][j];n
} } t(n)=2n3+3n2+2n+1 3limt(n)/ n=2 t(n)=o(n3)例：
（a）{++x;s=0;}（b）for(i=1;i<=n;++i){++x;s+=x;}（c）for(j=1;j<=n;++j)for(k=1;k<=n;k++){++x;s+=x;} 含基本操作“x增1”的語(yǔ)句的頻度分別為1,n和n2 時(shí)間復(fù)雜度是o(1),o(n)和o(n2),。時(shí)間復(fù)雜度有時(shí)與輸入有關(guān),。
4、算法的存儲(chǔ)空間需求
空間復(fù)雜度：s（n）=o（f（n））
五,、作業(yè)布置
復(fù)習(xí)回顧c語(yǔ)言中關(guān)于結(jié)構(gòu)體和指針部分的內(nèi)容,，以便于后期學(xué)習(xí)。
六,、教學(xué)后記
按2 學(xué)時(shí)講完,。
以前教學(xué)中反映出學(xué)生對(duì)抽象數(shù)據(jù)類型掌握不好，結(jié)構(gòu)體知識(shí)基本不懂,，所以要求學(xué)生課下自學(xué),，下次課抽1學(xué)時(shí)學(xué)習(xí)結(jié)構(gòu)體和指針。
學(xué)生讀程序能力差,，循環(huán)嵌套分析不出執(zhí)行次數(shù),。考慮布置了一道題目練習(xí),。
數(shù)據(jù)結(jié)構(gòu)演講篇四
數(shù)據(jù)結(jié)構(gòu)參考題目
一,、選擇
1.如果在數(shù)據(jù)結(jié)構(gòu)中每個(gè)數(shù)據(jù)元素只可能有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼,，則該結(jié)構(gòu)是（）
a.棧 b.隊(duì)列 c.樹 d.圖 2.下面程序段的時(shí)間復(fù)雜度為（）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.兩個(gè)字符串相等的條件是（）
a.串的長(zhǎng)度相等 b.含有相同的字符集c.都是非空串 d.串的長(zhǎng)度相等且對(duì)應(yīng)的字符相同 5．若以s和x分別表示進(jìn)棧和退棧操作,，則對(duì)初始狀態(tài)為空的棧可以進(jìn)行的棧操作系列是（）
xx sx sx xx 6.已知一棵含50個(gè)結(jié)點(diǎn)的二叉樹中只有一個(gè)葉子結(jié)點(diǎn),，則該樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）a.0 b.1 c.48 d.49 7.已知用某種排序方法對(duì)關(guān)鍵字序列（51,，35，93,，24,，13，68,，56,，42，77）進(jìn)行排序時(shí),，前兩趟排序的結(jié)果為
（35,，51，24,，13,，68,，56，42,，77,，93）
（35，24,，13,，51，56,，42,，68，77,，93）所采用的排序方法是（）
a.插入排序 b.冒泡排序 c.快速排序 d.歸并排序
8.已知散列表的存儲(chǔ)空間為t[0..16],，散列函數(shù)h（key）=key%17,并用二次探測(cè)法處理沖突。散列表中已插入下列關(guān)鍵字：t[5]=39,，t[6]=57和t[7]=7,，則下一個(gè)關(guān)鍵字23插入的位置是（）
a.t[2] b.t[4] c.t[8] d.t[10] 9.如果將矩陣an×n的每一列看成一個(gè)子表，整個(gè)矩陣看成是一個(gè)廣義表l,，即l=((a11,a21,…,an1),(a12,a22,…,an2),…,，（a1n,a2n,…,ann）),并且可以通過(guò)求表頭head和求表尾tail的運(yùn)算求取矩陣中的每一個(gè)元素，則求得a21的運(yùn)算是（）(tail(head(l)))(head(head(l)))(head(tail(l)))(head(tail(l)))10.在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中,，所有頂點(diǎn)的出度之和為dout,，則所有頂點(diǎn)的入度之和為（）
-1 +1 d.n 11．從邏輯關(guān)系來(lái)看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（）a線性結(jié)構(gòu) b.樹形結(jié)構(gòu) c.線性結(jié)構(gòu)和樹型結(jié)構(gòu) d.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)
12．棧的插入和刪除操作在()進(jìn)行,。
a．棧頂 b.棧底 c.任意位置 d指定位置 13．由權(quán)值分別為11,，8，6,，2,，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）a.24 b.71 c.48 d.53 14．一個(gè)棧的輸入序列為1 2 3,，則下列序列中不可能是棧的輸出序列的是()a.2 3 1 b.3 2 1 c.3 1 2 d.1 2 3 15．關(guān)于棧和隊(duì)列的說(shuō)法中正確的是（）
a．棧和隊(duì)列都是線性結(jié)構(gòu) b.棧是線性結(jié)構(gòu),，隊(duì)列不是線性結(jié)構(gòu) c.棧不是線性結(jié)構(gòu)，隊(duì)列是線性結(jié)構(gòu) d.棧和隊(duì)列都不是線性結(jié)構(gòu) 16．關(guān)于存儲(chǔ)相同數(shù)據(jù)元素的說(shuō)法中正確的是（）a．順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)少占空間 b.順序存儲(chǔ)比鏈?zhǔn)酱鎯?chǔ)多占空間
c.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)都要求占用整塊存儲(chǔ)空間 d.鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)難于擴(kuò)充空間
17．已知一個(gè)單鏈表中,，指針q指向指針p的前趨結(jié)點(diǎn),，若在指針q所指結(jié)點(diǎn)和指針p所指結(jié)點(diǎn)之間插入指針s所指結(jié)點(diǎn)，則需執(zhí)行（）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．設(shè)一組記錄的關(guān)鍵字key值為{62，50,，14,，27，19,，35,，47，56,，83},，散列函數(shù)為h(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）a.1 b.2 c.3 d.4 19．執(zhí)行下面程序段時(shí),，s語(yǔ)句被執(zhí)行的次數(shù)為：（）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．在長(zhǎng)度為n的線性表中刪除一個(gè)指針p所指結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）a．o(n)b.o(1)c.o(log2n)d.o(n2)21．設(shè)一個(gè)棧的輸入序列是a,，b，c,，d,，則所得到的輸出序列（輸入過(guò)程中允許出棧）不可能出現(xiàn)的是（）
a.a，b,，c,，d b.a，b,，d,，c c.d，c,，b,，a d.c，d,，a,，b 22．關(guān)于串的敘述中，正確的是（）a．空串是只含有零個(gè)字符的串 b.空串是只含有空格字符的串
c.空串是含有零個(gè)字符或含有空格字符的串
d.串是含有一個(gè)或多個(gè)字符的有窮序列
23．在具有m個(gè)單元的循環(huán)隊(duì)列中,，隊(duì)頭指針為front,，隊(duì)尾指針為rear，則隊(duì)滿的條件是（）
a．front==rear
b.(front+1)%m==rear
+1==front
d.(rear+1)%m==front 24．設(shè)有二維數(shù)組
?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的完全二叉樹中,，結(jié)點(diǎn)數(shù)最多為（）
ha．2h-1 b.2h+1 c.2-1 d.2h 26．由m棵結(jié)點(diǎn)數(shù)為n的樹組成的森林，將其轉(zhuǎn)化為一棵二叉樹，則該二叉樹中根結(jié)點(diǎn)的右子樹上具有的結(jié)點(diǎn)個(gè)數(shù)是（）
-1 c.n(m-1)d.m(n-1)27．在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中,，每個(gè)頂點(diǎn)度的最大值為（）a.n b.n-1 c.n+1 d.2(n-1)28．關(guān)于無(wú)向圖的鄰接矩陣的說(shuō)法中正確的是（）a.矩陣中非全零元素的行數(shù)等于圖中的頂點(diǎn)數(shù)
b.第i行上與第i列上非零元素總和等于頂點(diǎn)vi的度數(shù) c.矩陣中的非零元素個(gè)數(shù)等于圖的邊數(shù)
d.第i行上非零元素個(gè)數(shù)和第i列上非零元素個(gè)數(shù)一定相等
29．設(shè)一組記錄的關(guān)鍵字key值為{62,，50，14,，28,，19，35,，47,，56，83},，散列函數(shù)為h(key)=key mod 13,，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（）a.1 b.2 c.3 d.4 30．設(shè)有一組初始關(guān)鍵字值序列為（49，81,，55,，36，44,，88）,，則利用快速排序的方法，以第一個(gè)關(guān)鍵字值為基準(zhǔn)得到的一次劃分為（）
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.數(shù)據(jù)是計(jì)算機(jī)加工處理的對(duì)象（）。2.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu),、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面(),。
3.線性表是由n≥0個(gè)相同類型組成的有限序列（）。4.棧是一種后進(jìn)先出的線性表（）,。
5.從循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā),，只能找到它的后繼結(jié)點(diǎn)，不能找到它的前驅(qū)結(jié)點(diǎn)（）,。6.單鏈表設(shè)置頭結(jié)點(diǎn)的目的是為了簡(jiǎn)化運(yùn)算（）。7.樹的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）,。8.組成數(shù)據(jù)的基本單位稱為數(shù)據(jù)元素（）,。
9.從非循環(huán)鏈表的某一結(jié)點(diǎn)出發(fā)，既能找到它的后繼結(jié)點(diǎn),，又能找到它的前驅(qū)結(jié)點(diǎn)（）,。
10.單鏈表結(jié)點(diǎn)的指針域是用來(lái)存放其直接后繼結(jié)點(diǎn)的首地址的（）
11.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象（）。
12.用順序表來(lái)存儲(chǔ)線性表時(shí),，不需要另外開辟空間來(lái)保存數(shù)據(jù)元素之間的相互關(guān)系（）,。
13.在非線性結(jié)構(gòu)中，至少存在一個(gè)元素不止一個(gè)直接前驅(qū)或不止一個(gè)直接后驅(qū)（）,。14.樹的最大特點(diǎn)是一對(duì)多的層次結(jié)構(gòu)（）,。15.隊(duì)列的特點(diǎn)是先進(jìn)先出（）。
16.由后序遍歷序列和中序遍歷序列能唯一確定一顆二叉樹（）,。17.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)（）,。18.線性表簡(jiǎn)稱為”順序表”。（）
19.對(duì)數(shù)據(jù)的任何運(yùn)算都不能改變數(shù)據(jù)原有的結(jié)構(gòu)特性（）,。20.從循環(huán)單鏈表的任一結(jié)點(diǎn)出發(fā),，可以找到表中的所有結(jié)點(diǎn)（）。21.棧是一種先進(jìn)先出的線性表（）,。22.鏈表的主要缺點(diǎn)是不能隨機(jī)訪問(wèn)（）,。23.二叉樹是樹的特殊形式（）。24.冒泡排序法是穩(wěn)定的排序（）,。25.算法是對(duì)解題方法和步驟的描述（）,。26.算法可以用任意的符號(hào)來(lái)描述（）。
27.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型（）,。
28.線性表的順序存儲(chǔ)方式是按邏輯次序?qū)⒃卮娣旁谝黄刂愤B續(xù)的空間中（）,。29.棧是一種先進(jìn)后出的線性表（）。
30.將插入和刪除限定在表的同一端進(jìn)行的線性表是隊(duì)列（）,。
三,、畫圖題
1.請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={15,11,20,8,14,13 } r={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={a,b,c,d,e,f,g,h,i,j} r={,,
,
,
,
,
,
,
} 3．請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) 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.請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)
k={1,2,3,4,5} r={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu) 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．請(qǐng)根據(jù)下列二元組畫出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)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）}
四,、運(yùn)算題
1．已知一個(gè)圖的頂點(diǎn)集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.一個(gè)線性表為b=（12,，23，45,，57,，20,，03，78，31，15,，36），設(shè)散列表為ht[0..12],，散列函數(shù)為h（key）= key % 13并用線性探查法解決沖突,，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度,。
平均查找長(zhǎng)度：（寫出計(jì)算過(guò)程）
3．已知一個(gè)圖的頂點(diǎn)集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},；
按照普里姆算法得到最小生成樹,，試寫出在最小生成樹中依次得到的各條邊。（從頂點(diǎn)2出發(fā)）
____
__,，___
_,，___
___，__
____,，___ ___,，__ ____，___ ___,。4.寫出下圖所示的二叉樹的前中后序遍歷結(jié)果：
前序： 中序： 后序：
5.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起,，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉排序樹。
五,、編程題
1.請(qǐng)編寫一個(gè)算法,，實(shí)現(xiàn)十進(jìn)制整數(shù)與二進(jìn)制數(shù)的轉(zhuǎn)換。void shi_to_er(unsigned x){ 2.寫出二分法查找的算法：
int search_bin(keytype k,sstable st){ 3.請(qǐng)編寫一個(gè)算法,，實(shí)現(xiàn)單鏈表的就地逆置（單鏈表不帶頭結(jié)點(diǎn)）,。linklist *invertlink(linklist *h){
數(shù)據(jù)結(jié)構(gòu)演講篇五
數(shù)據(jù)結(jié)構(gòu)】二叉排序樹的建立，查找,，插入和刪除實(shí)踐題 /*sy53.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(“建立一棵二叉排序樹的二叉鏈表存儲(chǔ)n”);
t=createbst();
ch1='y';
while(ch1=='y' || ch1=='y')
{printf(“請(qǐng)選擇下列操作：n”);
printf(“1------------------更新二叉排序樹存儲(chǔ)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請(qǐng)輸入要查找的數(shù)據(jù)：”);
scanf(“n%d”,&key);
searchbst(t,key);
printf(“查找操作完畢,。n”);break;
case '3': printf(“n請(qǐng)輸入要插入的數(shù)據(jù)：”);
scanf(“n%d”,&key);
insertbst(&t,key);
printf(“插入操作完畢。n”);break;
case '4': printf(“n請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)：”);
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(“請(qǐng)輸入一個(gè)關(guān)鍵字(輸入0時(shí)結(jié)束輸入)：n”);scanf(“%d”,&key);
while(key)
{insertbst(&t,key);
printf(“請(qǐng)輸入下一個(gè)關(guān)鍵字(輸入0時(shí)結(jié)束輸入)：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(“沒(méi)有找到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(“沒(méi)有找到要?jiǎng)h除的結(jié)點(diǎn)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);}
}
