邏輯上相鄰的元素存盤在物理位置上也相鄰的存盤單元中

優點：實作隨機存取，每個元素占用最少的存盤空間

缺點：只能使用相鄰的一整塊存盤單元，可能產生較多的外部碎片

借助指示元素存盤地址的指標來表示元素之間的邏輯關系

優點：不會出現碎片現象，充分利用所有存盤單元

缺點：占用額外的存盤空間，且只能實作順序存盤

存盤資訊的同時，建立附加的索引表，索引表中的每項稱為索引項

優點：檢索速度快

缺點：索引表占用了額外的存盤空間，增加洗掉資料要修改索引表，花費較多的時間

根據元素的關鍵字直接計算元素存盤地址

優點：檢索、增加洗掉節點操作快

缺點：散列函式要求較高，容易出現存盤單元沖突

概念

對特定問題求解步驟的一種描述

有窮性：一個演算法必須總在執行有窮步之后結束，且每一 步 都可在有窮時間內完成

確定性：演算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出，

可行性：演算法中描述的操作都可以通過已經實作的基本運算執行有限次來實作，

輸入：一個演算法有零個或多個輸入，這些輸入取自于某個特定的物件的集合，

輸出：一個演算法有一個或多個輸出，這些輸出是與輸入有著某種特定關系的量，

正確性，演算法應能夠正確地解決求解問題，

可讀性，演算法應具有良好的可讀性，以幫助人們理解，

健壯性，輸入非法資料時，演算法能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果，

效率與低存盤量需求，效率是指演算法執行的時間，存盤量需求是指演算法執行程序中所需要的最大存盤空間，這兩者都與問題的規模有關，

時間復雜度

一個陳述句的頻度是指該陳述句在演算法中被重復執行的次數

所有陳述句的頻度只和記為T（n）

演算法中基本運算【最深層循壞內的陳述句】的頻度與T（n）同數量級

演算法中基本運算的頻度f(n）來分析演算法的時間復雜度

演算法的時間復雜度不僅依賴于問題的規模，也取決于待輸入資料的性質

最壞時間復雜度是指在最壞情況下，演算法的時間復雜度，

平均時間復雜度是指所有可能輸入實體在等概率出現的情況下，演算法的期望運行時間，

最好時間復雜度是指在最好情況下，演算法的時間復雜度，

一般總是考慮在最壞情況下的時間復雜度，以保證演算法的運行時間不會比它更長，

空間復雜度

S（n）演算法所耗費的存盤空間

一個程式在執行時除需要存盤空間來存放本身所用的指令、常數、變數和輸入資料外

還需要一些對資料進行操作的作業單元和資料一些為實作計算所需資訊的輔助空間

定義

特點

表示元素的個數有限

表中元素具有邏輯上的順序性，表中元素有其先后次序，

表中元素都是資料元素，每個元素都是單個元素，

表中元素的資料型別都相同，這意味著每個元素占有相同大小的存盤空間，

表中元素具有抽象性，即僅討論元素間的邏輯關系，而不考慮元素究竟表示什么內容，

基本操作

InitList(&L):初始化表，構造-一個空的線性表，

Length(L):求表長，回傳線性表L的長度，即L中資料元素的個數，

LocateElem(L,e):按值查找操作，在表L中查找具有給定關鍵字值的元素，

GetElem(L,i):按位查找操作，獲取表L中第i個位置的元素的值，

ListInsert(&L,i,e):插入操作，在表L中的第i個位置上插入指定元素e.

ListDelete(&L,i,&e):洗掉操作，洗掉表L中第i個位置的元素，并用e回傳洗掉元素的值，

PrintList (L):輸出操作，按前后順序輸出線性表L的所有元素值，

Empty(L):判空操作，若L為空表，則回傳true，否則回傳false，

DestroyList(&L):銷毀操作，銷毀線性表，并釋放線性表L所占用的記憶體空間，

一組地址連續的存盤單元依次存盤線性表中的資料元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰

邏輯順序與其物理順序相同

線性表L存盤的起始位置為LOC（A），sizeof（ElemType）是每個資料元素所占用存盤空間的大小，則表L所對應的順序存盤

線性表的順序存盤結構是一種隨即存取的存盤結構

通常用高級程式設計語言中的陣列來描述線性表的順序存盤結構

#define MaxSize 50            //定義線性表的最大長度
typedef struct{
    ElemType data[MaxSize];   //順序表的元素
    int length;               //順序表的當前長度
}SqList;                      //順序表的型別定義

一維陣列可以靜態分配，也可以是動態分配

靜態分配時，由于陣列的大小和空間事先已經固定，一旦空間占滿，再加入新的資料就會產生溢位，進而導致程式崩潰

動態分配時，存盤陣列的空間是在程式執行程序中通過動態存盤分配陳述句分配的，一旦資料空間占滿，就另外開辟一塊更大的存盤空間，用以替換原來的存盤空間，從而達到擴充存盤陣列空間的目的，而不需要為線性表一次性地劃分所有空間，

動態分配并不是鏈式存盤，它同樣屬于順序存盤結構，物理結構沒有變化，依然是隨機存取方式，只是分配的空間大小可以在運行時動態決定，

#define InitSize 100          //表長度的初始定義
typedef struct{
    ElemType *data;           //指示動態分配陣列的指標
    int MaxSize,length;       //陣列的最大容量和當前個數
}SqList;                      //動態分配陣列順序表的型別定義

C的初試動態分配陳述句為

L.data=https://www.cnblogs.com/yyyyfly1/archive/2022/03/14/(ElemType*)malloc(sizeof(ElemType)*InitSize);

C++的初始動態分配陳述句為

L.data=https://www.cnblogs.com/yyyyfly1/archive/2022/03/14/new ElemType[InitSize];

順序表最主要的特點是隨機訪問，即通過首地址和元素序號可在時間0(1)內找到指定的元素，

順序表的存盤密度高，每個結點只存盤資料元素，

順序表邏輯上相鄰的元素物理上也相鄰，所以插入和洗掉操作需要移動大量元素，

插入操作

在順序表L的第i (1<=i<=L. 1ength+1)個位置插入新元素e，

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(int j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

最好情況:在表尾插入(即i=n+ 1)，元素后移陳述句將不執行，時間復雜度為0(1)，

最壞情況:在表頭插入(即i= 1),元素后移陳述句將執行n次，時間復雜度為0(n)，

平均情況:假設pi (pr= 1/(n+ 1)是在第i個位置上插入- -個結點的概率，則在長度為n的線性表中插入-個結點時，所需移動結點的平均次數為n/2

洗掉操作

洗掉順序表L中第i (1<=i<=L. length)個位置的元素，用參考變數e回傳，

bool ListDelete(SqList &L,int i,Elemtype &e){
    if(i<1||i>L.length)
        return false;
    e=L.data[i-1];
    for(int j=i,j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}

最好情況:洗掉表尾元素(即i=n)，無須移動元素，時間復雜度為0(1)，

最壞情況:洗掉表頭元素(即i= 1),需移動除表頭元素外的所有元素，時間復雜度為O(n)，

平均情況:假設pi (p= 1/n)是洗掉第i個位置上結點的概率，則在長度為n的線性表中洗掉一個結點時，所需移動結點的平均次數為n-1/2

按值查找【順序查找】

在順序表L中查找第一個元素值等于e的元素，并回傳其位序

int LocateElem(SqList L,ElemType e){
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;    //下標為i的元素值等于e，回傳其位序1+1
        return 0;          //退出回圈，說明查找失敗
}

最好情況:查找的元素就在表頭，僅需比較一-次， 時間復雜度為0(1)，

最壞情況:查找的元素在表尾(或不存在)時，需要比較n次，時間復雜度為O(n)，

平均情況:假設p; (p;= 1/n)是查找的元素在第i (1<=i<=L. length)個位置上的概率，則在長度為n的線性表中查找值為e的元素所需比較的平均次數為n+1/2

堆疊的定義

只允許在一端進行插入或洗掉操作的線性表

堆疊頂：線性表允許進行插入洗掉的那一端，

堆疊底：固定的，不允許進行插入和洗掉的另一端 ，

空堆疊：不含任何元素的空表，

堆疊的操作特性為后進先出

堆疊的基本操作

InitStack(&S):初始化一一個空堆疊S，

StackEmpty(S):判斷-一個堆疊是否為空，若堆疊s為空則回傳true,否則回傳false.

Push(&S,x):進堆疊，若堆疊s未滿，則將x加入使之成為新堆疊頂，

Pop(&S, &x):出堆疊，若堆疊s非空，則彈出堆疊頂元素，并用x回傳，

GetTop(S,&x):讀堆疊項元素，若堆疊s非空，則用x回傳堆疊頂元素，

DestroyStack(&S):銷毀堆疊，并釋放堆疊s占用的存盤空間(“ &”表示參考呼叫)，

在解答演算法題時，若題千未做出限制，則可直接使用這些基本的操作函式，

順序堆疊的實作

采用順序存盤的堆疊稱為順序堆疊

利用一組地址連續的存盤單元存放自堆疊底到堆疊頂的資料元素，同時附設一個指標只是當前堆疊頂元素的位置

#define MaxSize 50
typedef struct{
    Elemtype data[Maxsize];
    int top;
}SqStack;

堆疊項指標: s. top,初始時設定s. top=-1P;堆疊頂元素: s .data [S. top].

進堆疊操作:堆疊不滿時，堆疊頂指標先加1,再送值到堆疊頂元素，

出堆疊操作:堆疊非空時，先取堆疊頂元素值,再將堆疊頂指標減1.

堆疊空條件: s. top==-1;堆疊滿條件: s. top==Maxsize-1;堆疊長: s. top+1.

由于順序堆疊的入堆疊操作受陣列上界的約束，當對堆疊的最大使用空間估計不足時，有可能發生堆疊上溢，此時應及時向用戶報告訊息，以便及時處理，避免出錯，

順序堆疊的基本運算

【1】初始化

void InitStack(SqStack &S){
    S.top=-1;    //初始化堆疊頂指標
}

【2】判堆疊空

bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;
    else
        return false;
}

【3】進堆疊

bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1)
        return false;
    S.data[++S.top]=x;
    return true;
}

當堆疊不滿時，top先加1，再入堆疊

【4】出堆疊

bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1)
        return false;
    x=S.data[S.top--];
    return true;
}

【5】讀堆疊頂元素

bool GetTop(SqStack S,ElemType &x){
    if(S.top==-1)
        return false;
    x=S.data[S.top];
    return true;
}

注意:

這里top指向的是堆疊頂元素，

所以進堆疊操作為s .data[++S. top]=x,

出堆疊操作為x=s.data[s.top--].

若堆疊頂指標初始化為s. top=0，即top指向堆疊頂元素的下一位置，

則入堆疊操作變為s.data[s. top++]=x;

出堆疊操作變為x=s.data[--s.top].

相應的堆疊空、堆疊滿條件也會發生變化，

共享堆疊

利用堆疊底位置相對不變的特性，可讓兩個順序堆疊共享一個一維陣列空間，將兩個堆疊的堆疊底分別設定在共享空間的兩端，兩個堆疊頂向共享空間的中間延伸

兩個堆疊的堆疊項指標都指向堆疊頂元素，top0=-1 時0號堆疊為空，top1=MaxSize 時1號堆疊為空:

僅當兩個堆疊頂指標相鄰(top1-top0=1) 時，判斷為堆疊滿，當0號堆疊進堆疊時top0先加1再賦值，1號堆疊進堆疊時top1先減1再賦值;出堆疊時則剛好相反，

共享堆疊是為了更有效地利用存盤空間，兩個堆疊的空間相互調節，只有在整個存盤空間被占滿時才發生上溢，其存取資料的時間復雜度均為0(1),所以對存取效率沒有什么影響，

堆疊的鏈式存盤結構

采用鏈式存盤的堆疊稱為鏈堆疊

鏈堆疊的優點是便于多個堆疊共享存盤空間和提高其效率，且不存在堆疊滿上溢的情況，

通常采用單鏈表實作，并規定所有操作都是在單鏈表的表頭進行的，

這里規定鏈堆疊沒有頭結點，Lhead 指向堆疊頂元素

typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
} *LiStack;

佇列的定義

【1】佇列【Queue】簡稱隊

【2】一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行洗掉

【3】向佇列中插入元素稱為入隊或進隊

【4】洗掉元素稱為出隊或離隊

【5】其操作特性是先進先出

【6】隊頭：允許洗掉的一端，又稱對手

【7】隊尾：允許插入的一端

【8】空佇列：不含任何元素的空表

佇列常見的基本操作

【1】InitQueue (&Q):初始化佇列，構造一個空佇列Q，

【2】QueueEmpty (Q):判佇列空，若佇列Q為慷訓傳true,否則回傳false.

【3】EnQueue (&Q,x):入隊，若佇列Q未滿，將x加入，使之成為新的隊尾，

【4】DeQueue (&Q, &x):出隊，若佇列e非空，洗掉隊頭元素，并用x回傳，

【5】GetHead(Q,&x):讀隊頭元素，若佇列Q非空，則將隊頭元素賦值給X，

【6】需要注意的是，堆疊和佇列是操作受限的線性表，因此不是任何對線性表的操作都可以作為堆疊和佇列的操作，比如，不可以隨便讀取堆疊或佇列中間的某個資料，

佇列的順序存盤

【1】佇列的順序實作是指分配一塊連續的存盤單元存放佇列中的元素，并附設兩個指標

【2】隊頭指標front指向對頭元素

【3】隊尾指標rear指向對偽元素的下一個位置

【4】佇列的順序存盤型別可描述為

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}   SqQueue;

初始狀態【隊空條件】：Q.front==Q.rear==0

進隊操作：隊不滿時，先送值到隊尾元素，再將隊尾指標加1

出隊操作：隊不空時，先取隊頭元素值，再將隊頭指標加1

所示為佇列的初始狀態，有Q.front==Q.rear==0成立

該條件可以作為佇列判空的條件

但不能用Q.rear==MaxSize作為佇列滿的條件

如圖，佇列中只有一個元素，但仍滿足條件

佇列出現上溢位，但是是假溢位

回圈佇列

【1】定義：將順序佇列臆造為一個環狀的空間，即把存盤佇列元素的表從邏輯上視為一個環

【2】當隊首指標Q.front=MaxSize-1后，再前進一個位置就自動到0，這可以利用除法取余運算來實作

【3】初始時：Q.front=Q.rear=0

【4】隊首指標進1：Q.front=(Q.front+1)%MaxSize;

【5】隊尾指標進1：Q.rear=(Q.rear+1)%MaxSize;

【6】佇列長度：（Q.rear+MaxSize-Q.front）%MaxSize;

【未完成】

回圈佇列的操作

【1】初始化

void InitQueue(SqQUEUE &q){
    Q.rear=Q.front=0;
}

【2】判隊空

bool isEmpty(SqQueue Q){
    if(Q.rear==Q.front)
        return true;
    else 
        return false;
}

【3】入隊

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front)    //隊滿則報錯
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;//隊尾指標加1取模
    return true;
}

【4】出隊

bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear==Q.front)
        return false;
    x=data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

佇列的鏈式存盤

鏈式佇列的基本操作

雙端佇列

堆疊在括號匹配中的應用

堆疊在運算式求值中的應用

堆疊在遞回中的應用

佇列在層次遍歷中的應用

佇列在計算機系統中的應用

陣列的定義

陣列的存盤結構

對稱矩陣

三角矩陣

三對角矩陣

稀疏矩陣

串的定義

定長順序存盤表示

堆分配存盤表示

塊鏈存盤表示

串的基本操作

簡單的模式匹配演算法

KMP演算法

KMP演算法的進一步優化

樹的定義

基本術語

樹的性質

二叉樹的定義

幾個特殊的二叉樹

二叉樹的性質

二叉樹的存盤結構

二叉樹先序遍歷

二叉樹中序遍歷

二叉樹后序遍歷

遞回演算法和非遞回演算法的轉換

二叉樹層次遍歷

由遍歷序列構造二叉樹

線索二叉樹的基本概念

中序線索二叉樹的構造

中序線索二叉樹的遍歷

先序線索二叉樹和后續線索二叉樹

樹的存盤結構

樹、森林與二叉樹的轉換

樹和森林的遍歷

二叉排序樹的定義

二叉排序樹的查找

二叉排序樹的插入

二叉排序樹的構造

二叉排序樹的洗掉

二叉排序樹的查找效率分析

平衡二叉樹的定義

平衡二叉樹的插入

平衡二叉樹的查找

哈夫曼樹的定義

哈夫曼樹的構造

哈夫曼編碼

圖的定義

圖的基本概念和術語

鄰接矩陣法

鄰接表法

十字鏈表

鄰接多重表

圖的基本操作

BFS演算法的性能分析

BFS演算法求解單源最短路徑問題

廣度優先生成樹

DFS演算法的性能分析

深度優先的生成樹和生成森林

圖的遍歷與圖的連通性

Prim演算法

Kruskal演算法

Dijkstra演算法秋單源最短路徑問題

Floyd演算法求各頂點之間最短路徑問題

有向無環圖描述運算式

拓撲排序

關鍵路徑

一般線性表的順序查找

有序表的順序查找

二分查找

分塊查找【索引順序查找】

B樹及其基本操作

B樹的高度

B樹的查找

B樹的插入

B樹的洗掉

B+樹的基本概念

散串列的基本概念

散列函式的構造方法

處理沖突的方法

散列查找及性能分析

直接插入排序

折半插入插敘

希爾排序

快速排序

冒泡排序

簡單選擇排序

堆排序

歸并排序

基數排序

內部排序演算法的比較

內部排序演算法的應用

外部排序的方法

多路平衡歸并與敗者樹

置換-選擇排序

最佳歸并樹