一、數(shù)據(jù)結(jié)構(gòu)緒論

• 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)
  • 邏輯結(jié)構(gòu)：集合、線性（一對(duì)一）、樹（一對(duì)多）、圖（多對(duì)多）
  • 物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)
• 抽象數(shù)據(jù)類型 （Abstract Data Type,ADT）：是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作

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

二、算法

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

三、線性表

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

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

InitList(&l)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L

DestroyList(&l)

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

ClearList(&l)

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

ListEmpty(L)

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

ListLenght(L)

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

GetElem(L,i,&e)

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

locatElem(L,e,comare())

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

PriorElem(L,cur_e,&pre_e)

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

NextElem(L,cur_e,&)

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

ListInsert(&L,i,e)

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

ListDelete(&L,i,&e)

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

ListTraverse(L,visit())

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

• 順序儲(chǔ)存結(jié)構(gòu)代碼
  #define MAXSIZE 20
  typedef int ElemType；
  typedef struct{
  ElemType data[MAXSIZE];
  int length;
  }SqList;

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

• 單鏈表
• 單鏈表儲(chǔ)存結(jié)構(gòu)代碼
  typedef struct node{
  ElemType data；
  struct Node *next；
  } Node；
  typedef struct Node *LinkList；

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

  靜態(tài)鏈表

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

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

• 雙向鏈表

  • 雙向鏈表的儲(chǔ)存結(jié)構(gòu)代碼
    typedef Struct DulNode{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode next;
    }DulNode,DuLinkList;

四、棧與隊(duì)列

棧

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

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

InitStack（*S）

初始化操作，建立一個(gè)空棧*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的元素個(gè)數(shù)
endADT

• 棧的順序存儲(chǔ)結(jié)構(gòu)
  typedef int SElemType；
  typedef struct{
  SElemtype data[MAXSIZE];
  int top;
  }SqStack；
• 兩棧共享空間
  typedef struct{
  SElemType data[MAXSIZE];
  int top1;
  int top2;
  }sqDoubleStack；

判斷是否滿棧

top1+1==top2

• 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
  typedef struct StackNode{
  SElemType data;
  struct StackNode next;
  }StackNode,LinkStackPtr;

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

• 棧的應(yīng)用：
  四則運(yùn)算表達(dá)式求值：后綴表示法(逆波蘭表示法)。

隊(duì)列

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

ADT 隊(duì)列（Queue）
Data ：
同線性表
Operation：

InitQueue（*Q）

初始化操作，建立一個(gè)空隊(duì)列*Q

DestroyQueue（*Q）

若隊(duì)列存在，則銷毀它

ClearQueue（*S）

將隊(duì)列清空

QueueEmpty（*Q）

若隊(duì)列為空，則返回true，反之返回false

GetHead（Q，*e）

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

EnQueue（*Q，e）

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

DeQueue（Q，e）

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

QueueLengh（Q）

返回隊(duì)列Q的元素個(gè)數(shù)
endADT

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

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

• 隊(duì)列的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)
  typedef int QElemType；
  typedef struct QNode{
  QElemType data；
  struct QNde next；
  }QNode,QueuePtr;
  typedef struct{
  QueuePtr font,rear;
  }LinkQueue；

五、串

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

ADT 串（string）
Data
串中元素僅由一個(gè)字符組成，相鄰元素具有前驅(qū)和后繼關(guān)系
Operation

StrAssign( &T, chars )

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

StrCopy( &T, S )

初始條件：串S存在。
操作結(jié)果：由串S復(fù)制得串T。

StrEmpty( S )

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

StrLength( S )

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

ClearString( &S )

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

Concat( &T, S1, S2 )

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

SubString( &Sub, S, pos, len )

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

Index( S, T, pos )

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

Replace( &S, T, V )

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

StrDelete( &S, pos, len )

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

DestroyString( &S )

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

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

六、樹

• 樹的定義

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

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

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

• 結(jié)點(diǎn)的層次從根開始定義，根為第一層，樹中結(jié)點(diǎn)的最大層次稱為樹的深度（高度）

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

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

• 樹的存儲(chǔ)結(jié)構(gòu)

  • 雙親表示法
    #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;/根的位置和結(jié)點(diǎ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;
    

線性表儲(chǔ)存結(jié)點(diǎn)元素，孩子鏈表的孩子結(jié)點(diǎn) child是數(shù)據(jù)域，儲(chǔ)存某結(jié)點(diǎn)在表頭數(shù)組中的下標(biāo)。next是指針域，用來存儲(chǔ)指向某結(jié)點(diǎn)的下一個(gè)孩子的指針

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

• 二叉樹

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

  • 存儲(chǔ)結(jié)構(gòu)

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

  • 遍歷二叉樹

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

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

  • 線索二叉樹

    • 定義：二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱為線索化
    • 二叉樹的線索存儲(chǔ)結(jié)構(gò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;}//前驅(qū)線索
      if(!pre->rchild){
      pre->RTag=Thread;
      pre->rchild=p;}//后續(xù)線索
      pre=p; //保持pre指向p的前驅(qū)
      InThreading(p->rchild);//右子樹線索化
      }
      }//InThreading

因?yàn)榇藭r(shí)p結(jié)點(diǎn)的后繼還沒有訪問到，因此只能對(duì)它的前驅(qū)界限pre的右指針rchild做判斷，if（！pre->rchild）表示如果為空，則p就是pre的后繼，于是pre->rchild=p，并且設(shè)置pre->RTag=Thread,完成后繼結(jié)點(diǎn)的線索化

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

七、圖

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

ADT 圖（Graph）
Data
頂點(diǎn)的有窮非空集合和邊的集合
Operation
endADT

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

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

       typedef char VertexType;
       typedef int EdgeType;

       typedef struct EdgeNode{ 
        int adjvex； /*鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)的對(duì)應(yīng)下標(biāo)*/
        EdgeType weight；/*存儲(chǔ)權(quán)值*/
        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】

十字鏈表

容易求得頂點(diǎn)的出度和入度

• 鄰接多重表

  
  
  邊表結(jié)點(diǎn)結(jié)構(gòu)

鄰接多重表

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

八、查找

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

九、排序

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