第1章 數(shù)據(jù)結(jié)構(gòu)緒論

第2章 算法

第3章 線性表

第1章 數(shù)據(jù)結(jié)構(gòu)緒論

• 程序設(shè)計 = 數(shù)據(jù)結(jié)構(gòu) + 算法

邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

邏輯結(jié)構(gòu)

1. 集合結(jié)構(gòu)
2. 線性結(jié)構(gòu)
3. 樹形結(jié)構(gòu)
4. 圖形結(jié)構(gòu)

物理結(jié)構(gòu)

• 物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的存儲形式。

1. 順序存儲結(jié)構(gòu)：把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里得湘，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的失都。
2. 鏈?zhǔn)酱鎯Y(jié)構(gòu)：把數(shù)據(jù)元素存放在任意的存儲單元里跌前，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的布疼。

第2章 算法

算法是解決特定問題求解步驟的描述，在計算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作淌友。

算法的特性

1. 輸入輸出：有零個或多個輸入，至少有一個或多個輸出骇陈。
2. 有窮性
3. 確定性
4. 可行性

算法設(shè)計的要求

1. 正確性
2. 可讀性
3. 健壯性
4. 時間效率高和存儲量低

算法時間復(fù)雜度

定義：在進(jìn)行算法分析時震庭，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級你雌。算法的時間復(fù)雜度器联，也就是算法的時間度量，記作：T(n) = O(f(n))婿崭。它表示隨問題規(guī)模n的增大拨拓，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度氓栈，簡稱為時間復(fù)雜度渣磷。其中f(n)是問題規(guī)模n的某個函數(shù)。
這樣用大寫O()來體現(xiàn)算法時間復(fù)雜度的記法颤绕，稱之為大O記法幸海。

推導(dǎo)大O階

1. 用常數(shù)1取代運行時間中的所有加法常數(shù)
2. 在修改后的運行次數(shù)函數(shù)中，只保留最高階項奥务。
3. 如果最高階項存在且不是1物独，則去除與這個項相乘的常數(shù)。
   得到的結(jié)果就是大O階氯葬。

常用的時間復(fù)雜度所消耗的時間從小到大依次是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n(2)) < O(n(3)) < O(2(2)) < O(n!) < O(n(n))

算法的空間復(fù)雜度

算法的空間復(fù)雜度通過計算算法所需的存儲空間實現(xiàn)挡篓，算法空間復(fù)雜度的計算公式記作：S(n) = O(f(n))，其中帚称，n為問題的規(guī)模官研，f(n)為語句關(guān)于n所占存儲空間的函數(shù)。

第3章 線性表

線性表(List)：零個或多個數(shù)據(jù)元素的有限序列闯睹。

a(i-1)是a(i)的直接前驅(qū)元素戏羽，a(i+1)是a(i)的直接后繼元素。

線性表的抽象數(shù)據(jù)類型定義

ADT 線性表（List）
Data
    線性表的數(shù)據(jù)對象集合為{a1,a2,...,an},每個元素的類型均為DataType楼吃。其中始花，除第一個元素a1外妄讯，每一個元素有且只有一個直接前驅(qū)元素，除了最后一個元素an外酷宵，每一個元素有且只有一個直接后繼元素亥贸。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。
Operation
    InitList(*L):初始化操作浇垦，建立一個空的線性表L炕置。

    ListEmpty(L):若線性表為空，返回true男韧，否則返回false朴摊。

    ClearList(*L):將線性表清空。

    GetElem(L,i,*e):將線性表L中的第i個位置元素返回給e煌抒。

    LocaEleme(L,i,*e):將線性表L中查找與定位值e相等的元素仍劈，如果查找成功，返回該元素在表中序號表示成功寡壮；否則，返回0表示失敗讹弯。

    ListInsert(*L,i,e):在線性表L中的第i個位置插入新元素e况既。

    ListDelete(*L,i,e):在線性表L中的第i個位置元素，并用e返回其值组民。
    ListLength(L):返回線性表L的元素個數(shù)棒仍。
endADT

線性表的順序存儲結(jié)構(gòu)

• 順序存儲定義：指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

• 順序存儲方式：一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu)臭胜。

線性表的順序存儲的結(jié)構(gòu)代碼:

#define MAXSIZE 20 /*存儲空間初始分配量*/
typedef int ElemType;/*ElemType類型根據(jù)實際情況而定莫其，這里假設(shè)為int*/
typedef struct
{
    ElemType data[MAXSIZE];/*數(shù)組存儲數(shù)據(jù)元素，最大值為MAXSIZE*/
    int length;/*線性表當(dāng)前長度*/
}SQList;

順序存儲結(jié)構(gòu)需要三個屬性：

• 存儲空間的起始位置：數(shù)組data,它的存儲位置就是存儲空間的存儲位置耸三。
• 線性表的最大存儲容量:數(shù)組長度MaxSize乱陡。
• 線性表的當(dāng)前長度：Length。

用數(shù)組存儲順序表意味著要分配固定長度的數(shù)組空間仪壮，由于線性表中可以進(jìn)行插入好人刪除操作憨颠，因此分配的數(shù)組空間要大于等于當(dāng)前線性表的長度。

存儲器中的每個存儲元素都有自己的編號积锅，這個編號成為地址爽彤。

順序存儲結(jié)構(gòu)的插入與刪除

• 獲得元素操作
  實現(xiàn)GetElem操作，將線性表L中的第i個位置元素值返回缚陷。就程序而言适篙，只要i的數(shù)值在數(shù)組下標(biāo)范圍內(nèi)，就是把數(shù)組第i-1下標(biāo)的值返回即可箫爷。

#define ok 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
Status是函數(shù)的類型嚷节，其值是函數(shù)結(jié)果狀態(tài)代碼铆铆，如OK等
初始條件：順序線性表L已存在，1<= i <= ListLength(L)
操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值
Status GetElem (SqList L, int i, ElemType *e)
{
if(L.length==0 || i>L.length)
    return ERROR;
    *e=L.data[i-1];
    return OK;
}

插入操作

插入算法的思路：

• 如果插入位置不合理丹喻，拋出異常薄货；
• 如果線性表長度大于等于數(shù)組長度，則拋出異嘲郏或動態(tài)增加容量谅猾；
• 從最后一個元素開始向前遍歷到第i個位置，分別將它們都向后移動一個位置鳍悠；
• 將要插入元素填入位置i處税娜；
• 表長加1；
  代碼實現(xiàn)：

初始條件：順序線性表Ｌ已存在藏研，１<= i <= ListLength(L)
操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加1

Status ListInsert(SqLsit *L, int i,ElemType e)
{
int k;
    if (L->length == MAXSIZE)/*順序線性表已經(jīng)滿*/
        return ERROR;
    if(i<1 || i>L->length+1)/*當(dāng)i不在范圍內(nèi)時*/
        return ERROR;
    if(i<=L->length)/*若插入數(shù)據(jù)位置不在表尾*/
    {
        for(k=L->length-1;k>=i-1;k--)/*將要插入位置后數(shù)據(jù)元素向后移動一位*/
            L->data[k+1] = L->data[k];
    }
    L->data[i-1] = e;/*將新元素插入*/
    L-length++;
    return OK;
}

刪除操作

算法思路：

• 如果刪除位置不合理敬矩，拋出異常;
• 取出刪除元素;
• 從刪除元素位置開始遍歷到最后一個元素位置，分別將它們都向前移動一個位置;
• 表長減1.

線性表順序存儲結(jié)構(gòu)的優(yōu)缺點

優(yōu)點

• 無須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間
• 可以快速的存取表中任一位置元素

缺點

• 插入和刪除操作需要移動大量元素
• 當(dāng)線性表長度變化較大時蠢挡，難以確定存儲空間的容量
• 造成存儲空間的"碎片"

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系弧岳，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外业踏，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）禽炬。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域勤家。指針域中存儲的信息稱為指針或鏈腹尖。
數(shù)據(jù)域 + 指針域 = 結(jié)點

鏈表中第一個結(jié)點的存儲位置叫做頭指針，最后一個結(jié)點指針為“空”伐脖，用NULL或^表示热幔。

頭指針與頭結(jié)點的異同

頭指針

• 頭指針是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點讼庇，則是指向頭結(jié)點的指針
• 頭指針具有標(biāo)示作用绎巨，所以常用頭指針冠以鏈表的名字
• 無論鏈表是否為空，頭指針均不為空巫俺。頭指針是鏈表的必要元素认烁。

頭結(jié)點

• 頭結(jié)點是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點之前介汹，其數(shù)據(jù)域一般無意義（也可存放鏈表的長度）
• 有了頭結(jié)點却嗡，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與其他結(jié)點的操作系統(tǒng)就統(tǒng)一了
• 頭結(jié)點不一定是鏈表必須要素

單鏈表的讀取

獲取鏈表第i個數(shù)據(jù)的算法思路

1. 聲明一個結(jié)點p指向鏈表第一個結(jié)點嘹承，初始化j從1開始窗价；
2. 當(dāng)j<i時，就遍歷鏈表叹卷，讓p的指針向后移動撼港，不斷指向下一結(jié)點坪它，j累加1；
3. 若到鏈表末尾p為空帝牡，則說明第i個元素不存在往毡；
4. 否則查找成功，返回結(jié)點p的數(shù)據(jù)靶溜。

單鏈表的插入與刪除

單鏈表第i個數(shù)據(jù)插入結(jié)點的算法思路

1. 聲明一節(jié)點p指向鏈表第一個結(jié)點开瞭，初始化j從1開始；
2. 當(dāng)j<i時罩息，就遍歷鏈表嗤详，讓p的指針向后移動，不斷指向下一結(jié)點瓷炮，j累加1葱色；
3. 若到鏈表末尾p為空，則說明第i個元素不存在娘香；
4. 否則查找成功苍狰，在系統(tǒng)中生成一個空結(jié)點s；
5. 將數(shù)據(jù)元素e賦值給s->data茅主；
6. 單鏈接的插入標(biāo)準(zhǔn)語句s -> next = p -> next; p ->next = s;
7. 返回成功舞痰。

單鏈表第i個數(shù)據(jù)刪除結(jié)點的算法思路

1. 聲明一節(jié)點p指向鏈表第一個結(jié)點，初始化j從1開始诀姚；
2. 當(dāng)j<i時，就遍歷鏈表玷禽，讓p的指針向后移動赫段，不斷指向下一個結(jié)點，j累加1矢赁；
3. 若到鏈表末尾p為空糯笙，則說明第i個元素不存在；
4. 否則查找成功撩银，將欲刪除的結(jié)點p->next賦值給q;
5. 單鏈表的刪除標(biāo)準(zhǔn)語句p->next = q->next给涕；
6. 將q結(jié)點中的數(shù)據(jù)賦值給e，作為返回额获；
7. 釋放q結(jié)點够庙；
8. 返回成功。

對于插入或刪除數(shù)據(jù)越頻繁的操作抄邀，單鏈表的效率優(yōu)勢就越是明顯

單鏈表的整表創(chuàng)建

單鏈表整表創(chuàng)建的算法思路:

1. 聲明一結(jié)點p和計數(shù)器變量i耘眨；
2. 初始化一空鏈表L;
3. 讓L的頭結(jié)點的指針指向NULL，即建立一個帶頭結(jié)點的單鏈表境肾；
4. 循環(huán)
   • 生成一新結(jié)點賦值給p剔难；
   • 隨機(jī)生成一數(shù)字賦值給p的數(shù)據(jù)域p->datd;
   • 將p插入到頭結(jié)點與前一新結(jié)點之間胆屿。

單鏈表的整表刪除

單鏈表整表刪除的算法思路如下：

1. 聲明一結(jié)點p和q；
2. 將第一個結(jié)點賦值給p偶宫；
3. 循環(huán)
   • 將下一結(jié)點賦值給q非迹；
   • 釋放p;
   • 將q賦值給p。