數(shù)據(jù)結(jié)構(gòu)核心名詞解釋
以下名稱解釋摘自《算法與數(shù)據(jù)結(jié)構(gòu)》嚴蔚敏版。
數(shù)據(jù)（Data）
是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。
數(shù)據(jù)元素（Data Element）
數(shù)據(jù)元素是數(shù)據(jù)的基本單位便监，在程序中通常作為一個整體來進行考慮和處理。
一個數(shù)據(jù)元素可有若干個數(shù)據(jù)項（Data Item）組成。
數(shù)據(jù)項（Data Item）
數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位坛吁。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。
數(shù)據(jù)對象（Data Object）
是性質(zhì)相同的數(shù)據(jù)元素的集合铐尚，是數(shù)據(jù)的一個子集拨脉。
數(shù)據(jù)結(jié)構(gòu)（Data Structure）
是指相互之間具有（存在）一定聯(lián)系（關(guān)系）的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系（關(guān)系）稱為邏輯結(jié)構(gòu)宣增。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型玫膀。
邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
邏輯結(jié)構(gòu)
數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問題方便而人為定義的關(guān)系统舀，這種自然或人為定義的“關(guān)系”稱為數(shù)據(jù)元素之間的邏輯關(guān)系匆骗，相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)。
邏輯結(jié)構(gòu)有四種基本類型：
-
集合誉简，結(jié)構(gòu)中的數(shù)據(jù)元素除了”同屬于同一個集合“外碉就，沒有其他關(guān)系。 -
線性結(jié)構(gòu)闷串，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系瓮钥。 -
樹形結(jié)構(gòu)焕檬，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 -
圖狀結(jié)構(gòu)或網(wǎng)狀關(guān)系打颤，結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系财骨。
物理結(jié)構(gòu)
物理結(jié)構(gòu)是指數(shù)據(jù)邏輯結(jié)構(gòu)在計算機中的存儲形式，一般有三種锈津。
- 順序存儲結(jié)構(gòu)呀酸，例如線性表。
- 鏈式存儲結(jié)構(gòu)琼梆，如樹性誉。
- 復合存儲結(jié)構(gòu)，如圖茎杂。
算法
算法是對特定問題求解方法（步驟）的一種描述错览，是指令的有限序列，其中每一條指令表示一個或多個操作煌往。
算法的特性
- 有窮性：一個算法必須總是在執(zhí)行有窮步驟之后結(jié)束倾哺，且每一步驟都在有窮時間內(nèi)完成。
- 確定性：算法中的每一條指令必須有確切的含義刽脖。不存在二義性羞海。且算法只有一個入口和出口。
- 可行性：一個算法是能行的曲管。即算法描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)扣猫。
- 輸入：一個算法有零個或者多個輸入，這些輸入取自于某個特定的對象集合翘地。
- 輸出：一個算法有一個或多個輸出申尤，這些輸出是同輸出有著某些特定關(guān)系的量。
算法設(shè)計要求
評價一個好的算法有以下幾個標準：
-
正確性：算法應(yīng)該滿足具體問題的需求衙耕。 -
可讀性：算法應(yīng)該容易供人閱讀和交流昧穿。可讀性好的算法有助于對算法的理解和修改橙喘。 -
健壯性：算法應(yīng)該有容錯處理时鸵。當輸入非法或者錯誤數(shù)據(jù)時，算法能適當?shù)淖龀龇磻?yīng)或者處理厅瞎，而不是產(chǎn)生莫名其妙的輸出結(jié)果饰潜。 -
通用性：算法應(yīng)具有一般性，即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立和簸。 -
效率與存儲量需求：效率指的是算法執(zhí)行的時間彭雾；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般與問題的規(guī)模有關(guān)锁保。
算法效率衡量方法
算法執(zhí)行時間虛通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量薯酝，也就是時間復雜度半沽。
時間復雜度
算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間度量記作T(n)=O(f(n))吴菠，稱作算法的漸近時間復雜度者填，簡稱時間復雜度。一般地做葵，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度（重復執(zhí)行的次數(shù)）來表示占哟。
常用的時間復雜度的大小關(guān)系為：
空間復雜度
空間復雜度：是指算法編寫成程序后，在計算機中運行時所需存儲空間的大小的度量酿矢。記作：S(n)=O(f(n))重挑。其中n為問題的規(guī)模。例如：
線性表
線性表(Linear List)：是由n（n>=0）個元素（結(jié)點）a1棠涮，a2……an組成的有限序列。該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型刺覆。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度严肪。
- 當n=0時，稱為空表谦屑。
- 當n>0時驳糯，將非空線性表記作：（a1，a2……an）氢橙，a1稱為線性表的第一個（首）結(jié)點酝枢，an稱為線性表的最后一個（尾）結(jié)點。
順序存儲
把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里悍手。用這種方法存儲的線性表簡稱順序表帘睦。
順序存儲的特點
- 線性表的邏輯順序與物理順序一致；
- 數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)坦康。
順序表的基本操作
順序存儲結(jié)構(gòu)中竣付，很容易實現(xiàn)線性表的一些操作：初始化、賦值滞欠、查找古胆、修改、插入筛璧、刪除逸绎、求長度等。
- 順序表的初始化
Status Init_SqList(SqList *L){
L->elem_array = (ElemType*)malloc(MAX_SIZE*sizeof(ElemType));
if(!L->elem_array){
return ERROR;
}else{
L->Length = 0;
return OK;
}
}
直接進行malloc關(guān)鍵字的內(nèi)存空間開辟夭谤。
- 順序表的插入
Status Insert_SqList(Sqlist *L, int i, ElemType e){
int j;
if(i<0||i>L->Length-1) return ERROR;
if(L->Length >= MAX_SIZE){
printf("線性表溢出棺牧！")；
return ERROR朗儒；
}
for(j= L->Length;j>=i-1;j--){
L->Elem_array[j+1] = L->Elem_array[j];
}
L->Elem_array[i-1] = e;
L->Length++;
return OK;
}
步驟實現(xiàn)拆分：
- 將線性表L中的第i個至第n個結(jié)點后移一個位置陨帆。
- 將結(jié)點e插入到結(jié)點a[i-1]之后曲秉。
- 線性表長度加1。
- 線性表的刪除
ElemType Delete_SqList(Sqlist *L,int i){
int l;
ElemType x;
if(L->length == 0){
printf("線性表L為空")疲牵；
return ERROR承二；
}else if(i<1||i>L->length){
printf("要刪除的數(shù)據(jù)元素不存在")；
return ERROR纲爸；
}else{
//要刪除的結(jié)點的值 保存
x = L->Elem_array[i-1];
for(k = i; k<L->Lenght;k++){
L->Elem_array[k-1] = L->Elem_array[k];
L->length--;
return(x);
}
}
}
步驟解析：
- 將線性表L中的第i+1個至第n個結(jié)點依次向前移動一個位置亥鸠。
- 線性表長度減1。
鏈式存儲
用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素识啦。用這種方法存儲的線性表簡稱線性鏈表负蚊。
鏈式存儲的特點
存儲鏈表中結(jié)點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的颓哮，甚至是分布在內(nèi)存中的任意位置上的家妆。鏈表中的邏輯順序和物理順序不一定相同。
本篇主要介紹了一些基本概念冕茅，下一篇會對鏈表進行詳細的介紹和一些基本的操作進行算法實現(xiàn)伤极。
