一、數(shù)據(jù)結構緒論

• 邏輯結構與物理結構
  • 邏輯結構：集合、線性（一對一）、樹（一對多）、圖（多對多）
  • 物理結構：順序存儲結構、鏈式儲存結構
• 抽象數(shù)據(jù)類型 （Abstract Data Type,ADT）：是指一個數(shù)學模型及定義在該模型上的一組操作

  標準格式
  　　　ADT　抽象數(shù)據(jù)類型名
  　　　Date 數(shù)據(jù)元素之間的邏輯定義
  Operation
  操作1
  初始條件
  操作結果描述
  操作2
  ......
  操作3
  ......
  endADT

二、算法

• 算法特性：輸入輸出、確定性、又窮性、可行性
• 算法要求：正確性、健壯性、可讀性、時間效率高和存儲量低
• 算法時間復雜度
  • 推導大O階方法
    1.用常數(shù)1取代運行時間中所有加法常數(shù)
    2.在修改后的運行函數(shù)中，只保留最高位
    3.如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)
    得到的結果是大O階

三、線性表

• 定義：零個或多個數(shù)據(jù)元素的有限序列
• 抽象數(shù)據(jù)結構

  ADT 線性表
  Data ：
  線性表的數(shù)據(jù)對象集合為{a1，a2，......，an}，每個元素的類型均為DataType。其中，除第一個元素a1外，每一個元素有且只有一個直接前驅元素，除了最后一個元素an外每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關系是一對一的關系。
  Operation：

InitList(&l)

操作結果：構造一個空的線性表L

DestroyList(&l)

初始條件：線性表已存在
操作結果：銷毀線性表L

ClearList(&l)

初始條件：線性表已存在
操作結果：置線性表L為空表

ListEmpty(L)

初始條件：線性表已存在
操作結果：若線性表L為空表，則返回TRUE，否則返回FALSE

ListLenght(L)

初始條件：線性表已存在
操作結果：返回線性表L數(shù)據(jù)元素個數(shù)

GetElem(L,i,&e)

初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：用e返回線性表L中第i個數(shù)據(jù)元素的值

locatElem(L,e,comare())

初始條件：線性表已存在,comare()是數(shù)據(jù)元素判定函數(shù)
操作結果：返回線性表L中第1個與e滿足關系comare()的數(shù)據(jù)元素的位序

PriorElem(L,cur_e,&pre_e)

初始條件：線性表已存在
操作結果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義

NextElem(L,cur_e,&)

初始條件：線性表已存在
操作結果：若cur_e是線性表L的數(shù)據(jù)元素，且不是第最后一個，則用next_e返回它的后繼，否則操作失敗，next_e無定義

ListInsert(&L,i,e)

初始條件：線性表已存在（1≤i≤ListLenght(L)+1）
操作結果：在線性表L中第i個數(shù)據(jù)元素之前插入新元素e，L長度加1

ListDelete(&L,i,&e)

初始條件：線性表已存在（1≤i≤ListLenght(L)）
操作結果：刪除線性表L中第i個數(shù)據(jù)元素，用e返回其值，L長度減1

ListTraverse(L,visit())

初始條件：線性表已存在
操作結果：依次對線性表L的每個數(shù)據(jù)元素調用visit()函數(shù)，一旦visit()失敗，則操作失敗}ADT List

• 順序儲存結構代碼
  #define MAXSIZE 20
  typedef int ElemType；
  typedef struct{
  ElemType data[MAXSIZE];
  int length;
  }SqList;

單鏈表、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表

• 單鏈表
• 單鏈表儲存結構代碼
  typedef struct node{
  ElemType data；
  struct Node *next；
  } Node；
  typedef struct Node *LinkList；

• 靜態(tài)鏈表（早期沒有指針，用數(shù)組代替指針）
• 靜態(tài)鏈表的儲存結構代碼
  #define MAXSIZE 1000
  typedef struct{
  Elemtype data；
  int cur；/游標/
  }Component,StaticLinkList[MAXSIZE];
  
  

  靜態(tài)鏈表

頭指針存放備用鏈表（后面空閑空間）第一個節(jié)點下標
數(shù)組最后一個元素的cur用來存放頭結點（第一個插入元素的下標）

• 循環(huán)鏈表
  將單鏈表中的終端結點的指針端由空指針改為指向頭結點，鏈表就形成了一個環(huán)

• 雙向鏈表

  • 雙向鏈表的儲存結構代碼
    typedef Struct DulNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode next;
    }DulNode,DuLinkList;

四、棧與隊列

棧

• 棧的定義：限定僅在表尾進行插入和刪除操作的線性表
• 棧的抽象數(shù)據(jù)類型

  ADT 棧（stack）
  Data ：
  同線性表
  Operation：

InitStack（*S）

初始化操作，建立一個空棧*S

DestroyStack（*S）

若棧存在，則銷毀它

ClearStack（*S）

將棧清空

StackEmpty（*S）

若棧為空，則返回true，反之返回false

GetTop（S，*e）

若棧存在且非空，用e返回棧頂元素

Push（*S，e）

若棧存在，插入新元素e到棧S中并成為棧頂元素

Pop（S，e）

刪除棧S中棧頂元素，并用e返回其值

StackLengh（S）

返回棧S的元素個數(shù)
endADT

• 棧的順序存儲結構
  typedef int SElemType；
  typedef struct{
  SElemtype data[MAXSIZE];
  int top;
  }SqStack；
• 兩棧共享空間
  typedef struct{
  SElemType data[MAXSIZE];
  int top1;
  int top2;
  }sqDoubleStack；

判斷是否滿棧

top1+1==top2

• 棧的鏈式存儲結構
  typedef struct StackNode{
  SElemType data;
  struct StackNode next;
  }StackNode,LinkStackPtr;

  typedef struct LinkStack{
     LinkStack top;
     int count; 
  }LinkStack；
  

• 棧的應用：
  四則運算表達式求值：后綴表示法(逆波蘭表示法)。

隊列

• 隊列的定義：只允許在一端進行插入操作，而在另一端進行刪除操作的線性表
• 隊列的抽象數(shù)據(jù)類型

ADT 隊列（Queue）
Data ：
同線性表
Operation：

InitQueue（*Q）

初始化操作，建立一個空隊列*Q

DestroyQueue（*Q）

若隊列存在，則銷毀它

ClearQueue（*S）

將隊列清空

QueueEmpty（*Q）

若隊列為空，則返回true，反之返回false

GetHead（Q，*e）

若隊列存在且非空，用e返回隊頭元素

EnQueue（*Q，e）

若隊列Q存在，插入新元素e到隊列Q中并成為隊尾元素

DeQueue（Q，e）

刪除隊列Q中隊頭元素，并用e返回其值

QueueLengh（Q）

返回隊列Q的元素個數(shù)
endADT

• 循環(huán)隊列
  • 定義：隊列頭尾相接
  • 循環(huán)隊列順序存儲結構
    typedef int QElemType；
    typedef struct{
    QElemType data[MAXSIZE];
    int front;
    int rear;
    }SqQueue;

隊列滿的條件是
######（rear+1）%QueueSize == front

• 隊列的鏈式儲存結構
  typedef int QElemType；
  typedef struct QNode{
  QElemType data；
  struct QNde next；
  }QNode,QueuePtr;
  typedef struct{
  QueuePtr font,rear;
  }LinkQueue；

五、串

• 串的定義：串是由零個或多個字符組成的有限序列，又名叫字符串
• 串的抽象數(shù)據(jù)結構

ADT 串（string）
Data
串中元素僅由一個字符組成，相鄰元素具有前驅和后繼關系
Operation

StrAssign( &T, chars )

初始條件：chars是字符串常量。
操作結果：生成一個其值等于chars的串T。

StrCopy( &T, S )

初始條件：串S存在。
操作結果：由串S復制得串T。

StrEmpty( S )

初始條件：串S存在。
操作結果：若S為空串，則返回TRUE，否則返回FALSE。 StrCompare( S, T )
初始條件：串S和T存在。
操作結果：若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0。

StrLength( S )

初始條件：串S存在。
操作結果：返回S的元素個數(shù)，稱為串的長度。

ClearString( &S )

初始條件：串S存在。
操作結果：將S清為空串。

Concat( &T, S1, S2 )

初始條件：串S1和S2存在。
操作結果：用T返回由S1和S2聯(lián)接而成的新串。

SubString( &Sub, S, pos, len )

初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
操作結果：用Sub返回串S的第pos個字符起長度為len的子串。

Index( S, T, pos )

初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。
操作結果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。

Replace( &S, T, V )

初始條件：串S，T和V存在，T是非空串。
操作結果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。 ######StrInsert( &S, pos, T )
初始條件：串S和T存在，1≤pos≤StrLength(S)+1。
操作結果：在串S的第pos個字符之前插入串T。

StrDelete( &S, pos, len )

初始條件：串S存在，1≤pos≤StrLength(S)-len+1。
操作結果：從串S中刪除第pos個字符起長度為len的子串。

DestroyString( &S )

初始條件：串S存在。
操作結果：串S被銷毀。
}
endADT

• 串的匹配
• 樸素匹配算法
  一個一個匹配
• kmp模式匹配算法
  算法思想：利用已經(jīng)匹配過的數(shù)據(jù)，創(chuàng)建一個next數(shù)組。避免重復遍歷
  難點：理解next數(shù)組

六、樹

• 樹的定義

• 樹是n個結點的有限集。n=0時稱為空樹。在任何一棵非空樹：
  （1）有且僅有一個特定的稱為根的結點
  （2）當n>1時，其余結點可分為m（m>0）個互不相交的有限集t1、t2、......、tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹

• 結點的度：結點擁有的子樹數(shù)，度為零的稱為葉節(jié)點（終端結點）

  樹的度是節(jié)點的度的最大值

• 結點的層次從根開始定義，根為第一層，樹中結點的最大層次稱為樹的深度（高度）

• 樹的抽象數(shù)據(jù)類型

ADT 樹（tree）
Data
樹是由一個根節(jié)點和若干棵子樹構成。樹中結點具有相同數(shù)據(jù)類型及層次關系。
Operation
endADT

• 樹的存儲結構

  • 雙親表示法
    #define MAX_TREE_SIZE 100
    typedef int ElemType;
    typedef struct PTNode{
    TElemType data；
    int parent；
    }PTNode；
    typedef struct
    {
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;/根的位置和結點數(shù)/
    }PTree;

  • 孩子表示法

    #define MAX_TREE_SIZE 100
     typedef int ElemType;
     typedef struct CTNode{
           int child；
           struct CTNode *next；
     }*ChildPtr；
    typedef  struct
    {
       TElemType data；
       ChildPtr firstchild；
    }CTBox;
    typedef struct
    {
     CTbox nodes[MAX_TREE_SIZE];
     int r,n;
    }CTree;
    

線性表儲存結點元素，孩子鏈表的孩子結點 child是數(shù)據(jù)域，儲存某結點在表頭數(shù)組中的下標。next是指針域，用來存儲指向某結點的下一個孩子的指針

• 孩子兄弟表示法
  typedef int ElemType;
  typedef struct CSNode{
  TElemType data；
  struct CSNode firstchild，rightsib；
  }CSNode，*CSTree；

• 二叉樹

  • 定義
    是n個結點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個跟結點和兩棵互不相交的、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。

  • 存儲結構

    • 順序儲存結構
      從根節(jié)點開始遍歷二叉樹，遇到?jīng)]有則置空
    • 二叉鏈表
      typedef struct BiTNode{
      TElemType data；
      struct BiTNode lchild，rchild；
      } BiTNode，*BiTree；

  • 遍歷二叉樹

    • 定義：從根節(jié)點出發(fā)，按照一定的次序依次訪問二叉樹中所有結點，使得每個結點被訪問依次且僅被訪問依次
    • 前序遍歷

      根左右
      * 中序遍歷
      >左根右
      * 后序遍歷
      >左右根

  • 線索二叉樹

    • 定義：二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化
    • 二叉樹的線索存儲結構
      typedef enum{Link,Thread} PointerTag;
      typedef struct BiThrNode
      {
      TElemType data;
      struct BiThrNode lchild,rchild;
      PointerTag LTag;
      PointerTag RTag;
      } BiThrNode,*BiThrTree;
    • 中序遍歷線索化
      void InThreading(BiThrTree p）
      {
      if(p) {
      InThreading(p->lchild);//左子樹線索化
      if(!p->lchild){
      p->LTag=Thread;
      p->lchild=pre;}//前驅線索
      if(!pre->rchild){
      pre->RTag=Thread;
      pre->rchild=p;}//后續(xù)線索
      pre=p; //保持pre指向p的前驅
      InThreading(p->rchild);//右子樹線索化
      }
      }//InThreading

因為此時p結點的后繼還沒有訪問到，因此只能對它的前驅界限pre的右指針rchild做判斷，if（！pre->rchild）表示如果為空，則p就是pre的后繼，于是pre->rchild=p，并且設置pre->RTag=Thread,完成后繼結點的線索化

• 赫夫曼樹
  • 定義 帶權路徑長度wpl最小的二叉樹稱為赫夫曼樹（最優(yōu)二叉樹）
  • 算法描述

七、圖

• 圖的定義
  • 圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E),其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合
  • 有向邊（?。喉旤cvi到vj有方向，則稱這條邊為有向邊
  • 簡單圖：不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)，則為簡單圖
  • 無向（有向）完全圖：任意兩個頂點之間都存在邊
  • 權：與圖的邊或弧相關的數(shù)
  • 網(wǎng)：帶權的圖
• 回路（環(huán)）：第一個頂點到最后一個頂點相同的路徑
• 簡單路徑：頂點不重復出現(xiàn)的路徑
• 連通圖：圖中任意兩個頂點都是連通的
• 連通分量：無向圖中的極大連通子圖
• 強連通圖：在有向圖中，對于每一對vi，vj從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。有向圖中的極大連通子圖稱做有向圖的強連通分量。
• 圖的抽象數(shù)據(jù)結構

ADT 圖（Graph）
Data
頂點的有窮非空集合和邊的集合
Operation
endADT

• 圖的儲存結構
  • 鄰接矩陣
    typedef char VertexType;
    typedef int EdgeType;
    #define MAXVEX 100
    #define INFINITY 65355
    typedef struct{
    VertexType vexs[MAXVEX];/頂點數(shù)組/
    EdegeType arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
    }MGraph;
  • 鄰接表

與上一章的孩子表示法思路相同

       typedef char VertexType;
       typedef int EdgeType;

       typedef struct EdgeNode{ 
        int adjvex； /*鄰接點域，存儲該頂點的對應下標*/
        EdgeType weight；/*存儲權值*/
        struct EdgeNode *next; 
       }EdgeNode；

       typedef struct VertexNode{ 
        VertexType data；
        EdgeNode  firstedge；
       }VertexNode,AdjList[MAXVEX];

       typedef struct{
        AdjList adjList;
        int numVertexes,numEdges; 
       }GraphAdjList;
 * 邊集數(shù)組

![邊集數(shù)組]XO.png](http://upload-images.jianshu.io/upload_images/1318539-703d9b755b44bc94.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

 * 十字鏈表

【data、firstin、firstout】【tailvex、headvex、headlink、taillink】

十字鏈表

容易求得頂點的出度和入度

• 鄰接多重表

  
  
  邊表結點結構

鄰接多重表

• 圖的遍歷
  • 深度優(yōu)先遍歷
    從圖中某個頂點v出發(fā)，訪問此頂點，然后從v的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到（鄰接表）
  • 廣度優(yōu)先遍歷
    類似于樹的前序遍歷（隊列）
• 最小生成樹
  • （普里姆）prim算法
  • （克魯斯卡爾）kruskal算法
• 最短路徑
  • （地杰斯特拉）dijkstr算法
  • （弗洛伊德）floyd算法
• 拓撲排序

八、查找

• 順序表查找
• 有序表查找
  • 有序查找
  • 斐波那契查找
  • 插值查找
• 線性索引查找
  • 稠密查找
  • 到排查找
  • 分塊索引
• 二叉排序樹
• 平衡二叉樹
• 多路查找樹（B樹）
• 散列表查找（哈希表）概述
• 散列函數(shù)構造方法
• 處理散列沖突方法
• 散列表的查找實現(xiàn)

九、排序

• 冒泡排序
• 簡單選擇排序
• 直接插入排序
• 希爾排序
• 堆排序
• 歸并排序
• 快速排序