一．緒論

1.何謂程序設計？

???????? 程序 = 算法 + 數據結構

2.數據結構的定義

???????? 是相互之間存在一種或多種特定關系的數據元素的集合

3.數據、數據元素、數據對象的概念

???????? 數據（data）：對客觀事物的符號表示，含義很廣，指數、圖像、聲音、文本等一切計算機可以處理的事物。

數據元素（data element）：組成數據的基本單位。

數據對象（data object）：性質相同的數據元素的集合。

4.四種基本的數據結構類型

???????? 集合結構、線性結構、樹型結構、圖形結構

5.兩種存儲結構（計算機中的實現方式）

???????? 順序存儲結構、鏈式存儲結構

6.理解順序存儲與鏈式存儲的方式、特點、優缺點、適用情況

7.數據類型、抽象數據類型

數據類型（Data Type）：刻畫程序對象的一種方式，包括值的集合與在這組值上的操作（一個成功的數據結構，就要設計成一種數據類型）

抽象數據類型（Abstract Data Type，ADT）：是與數據類型相似的概念

?ADT name

{??????????????? 數據對象 Data

????????????????? 數據關系 Relation

????????????????? 數據操作 Operation??????? }

8.抽象數據類型的意義

ADT著重數據結構的操作接口，不關心具體的實現，主要是面向用戶。ADT是數據結構設計所追求的目標。

9.何謂算法

???????? 算法是解決特定問題求解步驟的描述

10.算法特征

（1）有窮性：一個算法必須在執行有限步之后結束，每一步都在有窮時間內完成

（2）確定性：算法中每一步都有確切的含義，不會產生二義性

（3）可行性：算法的每一步操作都可以通過已有的可行的操作來完成

（4）輸入：算法有零個或若干個數據輸入

（5）輸出：算法有一個或若干個數據輸出

11.算法設計的要求

???????? （1）正確性：能夠解決問題

a.程序不含語法錯誤

b.對于幾組正常的輸入數據，能輸出滿足要求的結果

c.對于正常和異常數據，能給出滿足要求的結果

d.對一切合法數據，都能夠產生滿足要求的結果

（2）可讀性

（3）健壯性（要有異常處理機制）

（4）效率和低儲存容量需求

12.算法好壞的衡量標準

（1）事后統計

（2）事前估計

a.時間復雜度估計

b.空間復雜度估計

13.時間復雜度與空間復雜度

時間復雜度：T(n) = O( f(n) )，n為問題的規模。撇開具體的程序運行的環境，可以得到一個大致的數量階數。一般順序：O(1) < O(log n) < O(n) < O(nk) < O(kn)

將算法中基本操作的執行次數作為算法時間復雜度的度量。多數情況下都是取最深層循環的語句所描述的操作作為基本操作。遞歸算法的時間復雜度只需要記憶那幾個常用遞歸算法的即可。

如何算：

（1）確定算法中的基本操作以及數據量的大小(由算法所涉及的局部來看)。

（2）基本操作執行情況計算出規模n的函數f(n)，并確定時間復雜度為T(n) = O(f(n))中增長最快的項/此項的系數。

空間復雜度：類似的算法所需儲存空間? S(n) = O( f(n) )，n為問題的規模

?

二．線性表

1.何謂線性結構

在數據元素的非空有限集中，存在唯一的一個稱為“第一個”的數據元素，存在唯一的一個稱為“最后一個”的數據元素，除第一個之外，其他每個數據元素只有一個前驅，除最后一個之外，其他每個數據元素都只有一個后繼。

2.線性結構主要有哪幾種

???????? 線性表、棧、隊列、串

3.線性表ADT，尤其是它的幾個主要操作（插入元素、刪除元素）

ADT List

{ 數據對象 Data={ ai , i=1,2,…n }

???????? 數據關系 （略）

???????? 數據操作：

???????? InitList?????????????????????? 初始化線性表

???????? DestroyList?????????????? 銷毀線性表

???????? ClearList?????????? 清空線性表內的元素

ListEmpty???????? 判斷是否為空表

???????? ListLength???????????????? 取得表長度

???????? GetElement????????????? 取得某個位置的元素

???????? LocateElement???????????????? 定位某個元素的位置

???????? PriorElement??????????? 返回某個元素的前驅

???????? NextElement?????????? 返回某個元素的后繼

???????? InsertElement????????? 在某位置插入一個元素

???????? DeleteElement???????????????? 在某位置刪除一個元素

???????? ListTraverse????????????? 遍歷整個線性表

}

4.線性表的兩種實現方式

???????? 順序表、鏈表

5.順序表的C語言實現

#ifndef ARRAY_LIST_H

#define ARRAY_LIST_H

#include "type.h"

array_list.c

#include <stdio.h>

#include <stdlib.h>

#include "array_list.h"

static int get_array_index_from_logic_index(int logic_index) // 從邏輯下標得到數組下標

{ return logic_index - 1;}

static int get_logic_index_from_array_index(int array_index) // 從數組下標得到邏輯下標

{return array_index + 1;}

static int is_full(const struct array_list * list) // 是否滿了

{return list->capacity == list->last;}

struct array_list * array_list_init(int capacity) // 初始化

{struct array_list * tmp = (struct array_list *) malloc(sizeof (struct array_list));

if (tmp == NULL)

{perror("順序表創建失敗\n");? return NULL;}

type * data = (type *) malloc(sizeof (type) * capacity);

if (data == NULL)

{perror("順序表創建失敗\n");? return NULL; }

tmp->capacity = capacity;

??? tmp->data = data;

??? tmp->last = 0;

return tmp;}

void array_list_destroy(struct array_list * list) // 銷毀

{free(list->data); free(list);}

int array_list_is_empty(const struct array_list * list) // 判空

{return list->last == 0; }

void array_list_clear(struct array_list * list) // 清空

{list->last = 0; }

int array_list_length(const struct array_list * list) // 求長度

{return list->last;}

type array_list_get(const struct array_list * list, int index) // 取得index位置的元素

{return list->data[get_array_index_from_logic_index(index)];}

void array_list_insert(struct array_list * list, int index, type data) // 在index位置添加元素

{if (is_full(list))? {perror("表是滿的"); return;}

if (index < 1 || index > array_list_length(list) + 1) {perror("下表超出范圍"); return; }

??? int array_index = get_array_index_from_logic_index(index);

??? int i = list->last - 1;

??? for (; i >= array_index; i--) {list->data[i + 1] = list->data[i];}

??? list->data[i + 1] = data;? list->last++;}

void array_list_insert_last(struct array_list * list, type data) // 在最后位置添加元素

{array_list_insert(list, array_list_length(list) + 1, data);}

type array_list_remove(struct array_list * list, int index) // 刪除index位置的元素

{if (index < 1 || index > array_list_length(list)) {perror("index out of range"); return null_value();}

int array_index = get_array_index_from_logic_index(index);

??? type data = list->data[array_index];

??? for (int i = array_index + 1; i < list->last; i++) {list->data[i - 1] = list->data[i];}

??? list->last--;

??? return data;}

void array_list_traverse(const struct array_list * list, void (*access_function)(type data)) //遍歷

{for (int i = 0; i < list->last; i++) {access_function(list->data[i]);}}

6.鏈表的C語言實現

???????? 單鏈表、循環鏈表、雙向鏈表中結點的操作，比如插入、刪除、查找、定位等等

7.實現的代碼中，如何方便地更換數據元素的類型，以便代碼復用

???????? 定義泛型泛型的定義主要有以下兩種：

1.在程序編碼中一些包含類型參數的類型，也就是說泛型的參數只可以代表類，不能代表個別對象。（這是當今較常見的定義）

2.在程序編碼中一些包含參數的類。其參數可以代表類或對象等等。（人們大多把這稱作模板）不論使用哪個定義，泛型的參數在真正使用泛型時都必須作出指明。

8.順序表和鏈表的優缺點、適用場景

順序實現的優點：

1.利用計算機存儲的特點，實現簡單，無需額外存儲元素間的邏輯關系

2.隨機存儲

順序實現的缺點：

1.插入和刪除操作常伴隨大量的數據元素的移動

2.不利于數據規模的經常增大

????????????????????????? a.對于預先分配空間的，無法增加空間

????????????????????????? b.對于有自動擴充功能的，擴充之前需大 量復制已有數據元素

因此，順序存儲適合表示那些預先知道數據元素規模，經常的操作是取得某個位置的元素，但不經常進行插入刪除操作的那些問題

鏈式實現的優點：

1.無需事先分配大塊連續的內存，可根據插入刪除的需要進行內存的分配和回收

2.插入和刪除操作比較簡單，無需進行數據的移動

???????? 鏈式實現的缺點

1.需要額外存儲指針域

2.實現時相對比較復雜

適用場景：需要插入或刪除操作較多的地方?

三．棧與隊列

1.棧的概念，ADT

棧（stack）是限定僅能在表尾進行插入和刪除操作的線性表。

（因此，對棧來說，表尾端有 其特殊含義，稱為棧頂，相應地，表頭端稱為棧底。不含元素的空表稱為空棧）

ADT Stack{ 數據元素：

?????????????????????????????????? 略

基本操作：

???????? ????????????????????????? InitStack

???????? ????????????????????????? DestroyStack

???????? ????????????????????????? ClearStack

?????????????????????????????????? StackEmpty

???????? ???????????????????????? GetTop

???????? ???????????????????????? Push

???????? ???????????????????????? Pop? ????? }

2.棧的三個基本操作

???????? Push、Pop、GetTop

void push(struct stack * st, type data) // 進棧

?{if (st->top == st->capacity)

{perror("stack is full, cannot push");return; }

st->data[st->top++] = data; }

type pop(struct stack * st) // 出棧

{if (stack_is_empty(st)) {perror("stack is empty, cannot pop"); ?return null_value();}

return st->data[--st->top]; }

type get_top(const struct stack * st) // 查看棧頂元素

{if (stack_is_empty(st)) {perror("stack is empty, got null");? return null_value();}

return st->data[st->top - 1]; }

3.棧的特點

先進后出（FILO）

4.判斷能否根據某種操作順序，得到某一個元素序列

具體分析

5.棧的一些應用：括號匹配、函數調用跟蹤、遞歸跟蹤、四則運算

???????? 括號匹配思路：

1.依次讀入每一個符號。

2.如果該符號是左括號（大、中、小），則入棧；

3.如果該符號是右括號，則出棧一個符號，如果與該左括號匹配，則繼續；如果棧空或者取出的左括號不匹配，則判定表達式括號不匹配。

4.讀完表達式，如果棧空，判定表達式括號匹配；如果棧非空，則判定表達式括號不匹配

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<string.h>

#define TURE 1

#define ERROR 0

#define OK TURE

using namespace std;

const int max = 10000;

?char ch[max];

typedef int Status;

struct Stack ?//創建棧

{?????? char data[max];

???????? int top; };

Status search(char ch[], int n)

{?????? Stack s;

???????? s.top = -1;

???????? for (int i = 0; i < n; i++)

???????? {if (ch[i] == '(' || ch[i] == '[')

????????????????????????? s.data[++s.top] = ch[i];

if (ch[i] == ')')//左括號

????????????????? ???????? {if (s.top == -1)? return ERROR;?????????????????????

else if (s.data[s.top] == '(')

????????????????????????? s.top--;

????????????????????????? else? return ERROR; }

????????????????? if (ch[i] == ']') //右括號

????????????????? ???????? {if (s.top == -1) ?return ERROR;

????????????????????????? else if (s.data[s.top] == '[')//匹配s.top--;

????????????????????????? else//匹配失敗return ERROR;

//處理完所有的括號查看棧是否為空

????????????????????????? while (i == n)

????????????????????????? {if (s.top == -1) {return OK; cout << "s.top is cleaned";}

else{return ERROR; cout << "s.top is uncleaned";}}

}}}

int main()

{?????? int n;//檢測個數

???????? cout << "要檢測的個數:";

???????? cin >> n;//輸入n個數

???????? int i = 1;//設置i=1

???????? while (n--)//當n自減的時候

???????? {cout << "第" << i << "個括號序列:";? cin >> ch;//輸入括號

????????????????? int len = strlen(ch);//把ch的字符長度賦值給Len

????????????????? if (search(ch, len)) ?cout << "匹配成功" << endl;

????????????????? else? cout << "匹配失敗" << endl; i++;}

???????? system("pause");

???????? return 0;? ?}

四則運算思路：

1.設計算法將中序表達式轉換成后序表達式

2.設計算法進行后序表達式的計算

???????? 跟蹤思路：調用一次則入棧一次，

6.棧的順序實現方式（top指針的變化方式）

#include <stdio.h>

#include <stdlib.h>

#include "stack.h"

struct stack * stack_init(int capacity)

??? ?{struct stack * st = (struct stack *) malloc(sizeof (struct stack));

??? if (!st) {perror("stack init failed"); ???return NULL; }

st->data = (type *) malloc(sizeof (type) * capacity);

??? if (!st->data) {perror("stack init failed");return NULL; }

st->capacity = capacity;

?st->top = 0;? return st;}

7.隊列的特點：FIFO

8.隊列的頭尾與兩個基本操作

???????? 隊首（front），隊尾（rear），入隊（en），出隊（de）

void enq(struct queue * q, type data) // 入隊列

??? {if (is_full(q)) {perror("queue is full, cannot enq"); ?return; ?}

if (queue_is_empty(q)) { q->data[q->front] = data; }

q->data[q->rear] = data; q->rear = move_to_next(q->rear, q->length); }

type get_front(const struct queue * q) // 取得隊列首元素

??????? {if (queue_is_empty(q)) { perror("queue is empty"); ?return null_value(); }

??????? return q->data[q->front];}

type deq(struct queue * q) // 出隊列

??? {type o = get_front(q);

??? q->front = move_to_next(q->front, q->length); ?return o; }

9．隊列的順序實現方式

???????? front和rear的變化方式，何時表示隊列滿，何時表示隊列空

int queue_is_empty(const struct queue * q) //判空

{return q->front == q->rear;}

static int is_full(const struct queue * q) // 判斷隊列滿

??? {return move_to_next(q->rear, q->length) == q->front; }

一般規定：

當front與rear重合時，表示隊列為空

當rear再移動一位就將與front重合時，表示隊列滿（即以犧牲一個存儲單元的代價，表示隊列滿這個狀態）

四．串

1.串的概念（串、子串）

串是由零個或多個字符組成的有限序列，如? str = ‘abcdefg’，str：串名，單引號中的部分，表示串值，串值中的字符個數，為串長度，長度為0的表示空串

串中的任意連續的字符子序列，稱為該串的子串

當兩個串的值完全相同時，稱這兩個串相等

2.串的順序實現方式，主要操作

ADT String{?? 數據對象：略

????????????????????????? 數據關系：略

????????????????????????? 基本操作：StrInit：串初始化

??????????????????????????????????????????? ? StrCopy：串拷貝

????????????????????????? ???????? ????? StrCompare：串比較

?????????????????????????????????? ????? StrLength：求串長度

??????????????????????????????????????????? ? StrConcat：串連接

??????????????????????????????????????????? ? SubString：求串的某個子串

??????????????????????????????????????????? ? StrIndex：返回子串在串中的位置? }

3.模式匹配問題

模式匹配：在一個串中，對某子串的位置定位

假設主串長度為n，要匹配的子串長度為m，則常規匹配算法最壞情況下需要O(n*m)時間完成

KMP算法：該算法由Knuth，Morris，Pratt同時發現，因此命名為KMP算法，它是一種巧妙的算法，能在O(n+m)時間內完成串的模式匹配

五．數組與廣義表

1.數組（Array） 是用來描述一組具有連續的線性關系的相同事物的概念

2.ADT Array{? ???數據對象：（略）

數據關系：（略）

基本操作：

InitArray?????????? 數組初始化

DestroyArray?? 數組銷毀

GetValue????????? 取得某個元素

SetValue?????????? 給某個元素賦值 ??}

數組可以是多維的，不同的維數用來表示不同的實際事物

比如：可以用一維數組表示向量，二維數組表示矩陣，等等

3.多維數組的定義方法

通過其前一維數組來定義

比如，int a[3][4]，可以認為首先是一個具有3個元素（長度為3）的數組，然后每個元素是一個長度為4的數組

即：n維數組可以這樣認為：它是一個1維數組，其每個元素是一個n-1維數組

4.數組的順序實現

數組的基本元素在開始初始化后，一般其位置不會發生變化，數組的基本操作是取值和賦值，很少進行插入和刪除操作，內存的使用特性符合數組的這種特點。故數組一般都采用順序實現

5.兩種保存數組的方法

1.按行存儲2.按列存儲

6.多維數組中基本元素的定位：

每一個多維數組中的基本元素，都會有一個坐標，只要知道數組第一個元素的位置（基地址），某一個元素的坐標，就能夠計算出該元素的位置

7. 二維數組元素坐標

（以行存儲為例）：LOC(i, j) = LOC(0, 0) + (d2 * i + j)*L

???????? 其中d2為第二維的數組長度，L為每個基本元素所占的空間。由于有這樣的計算公式，因此順序實現的數組具有隨機存取的特點。

8.矩陣的壓縮存儲

（1）存一半：對稱矩陣（ai,j = aj,i)，上、下三角矩陣（ai,j = 0, i>j 或反過來）

（2）存坐標：稀疏矩陣（矩陣中大部分元素為0）

9.廣義表

廣義表是一種特殊的線性表，他的每一個元素可以是一個基本元素，也可以是另外一個不定長的線性表，這種性質決定了廣義表不太可能用順序存儲來實現，因此一般用鏈表來實現。

?

六．樹

1.樹的定義（遞歸方式）及表示方法

定義：樹是n（≥0）個結點的有限集，樹為：

空樹 或者 非空樹：有且僅有一個稱為“根”（root）的結點，它有若干個子樹

樹的幾種表示方法：

雙親表示法：盡管樹的每個結點都有若干個孩子，但是每個孩子只有一個雙親。（該方法在求某結點的孩子時，需要花費較多的時間）

孩子表示法：

孩子兄弟表示法：對每個結點，設定兩個指針，分別記錄該結點的第一個孩子和下一個兄弟

2.樹的主要術語（結點、葉子結點、孩子、兄弟、雙親、結點的度、樹的度、層次、深度、有序樹、森林）

結點（node）：包含一個數據元素及指向其子樹的分支

結點的度（Degree）：一個結點擁有的子樹的個數

葉子結點（Leaf）：度為0的結點

樹的度：樹內各個結點的度的最大值

孩子（Child）：結點的子樹

雙親（Parent）：結點的上層結點

兄弟（Sibling）：具有同一個雙親的結點

祖先：從根到該結點所經過的分支上的所有結點

子孫：某結點的子樹的所有結點

層次（Level）：根為第一次，某個結點若為l層，則其孩子為l+1層

深度（Depth）：樹中結點的最大層次

有序樹：各子樹從左往右有順序，反之稱為無序樹

森林（Forest）：若干棵互不相交的樹的集合

3.二叉樹（Binary Tree）的概念（遞歸方式）

定義1：每個結點至多只有兩棵子樹的樹（即二叉樹中不存在度大于2的結點），并且兩棵子樹有左右之分，分別稱為左子樹和右子樹

定義2：二叉樹或為一棵空樹，或是由一個根結點加上一棵左子樹和一棵右子樹，左子樹和右子樹也為二叉樹。

4.二叉樹的幾個性質

1.在二叉樹的第i層上至多有2i-1（i≥1）個結點

2.深度為k的二叉樹至多有2k-1（k≥1）個結點

3.任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1

4.具有n個結點的完全二叉樹的深度為（log2n）+1

5. 如果對一棵有n個結點的完全二叉樹（其深度為（log2n）+1）的結點按層序編號（從第1層到第（log2n）+1）層，每層從左到右），則對任一結點i(1<i<n)，有:

(1).如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則雙親是結點(i/2)

(2).如果2i>n，則結點i無做孩子（結點i為葉子結點）；否則其左孩子??是結點2i+1

(3).如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1

5.二叉樹的鏈式實現，幾個重要操作的實現（插入結點、刪除結點）

#include "bintree.h"

#include "queue.h"

#define max(a,b) ((a)>(b)?(a):(b))

struct bintree * bintree_init()// 初始化

?{struct bintree * p = (struct bintree *) malloc(sizeof (struct bintree));

??? if (!p) {perror("bintree init failed");? return NULL; }

p->root = NULL;? return p; }

static int is_leaf(const struct tree_node * node)//創建葉子節點

???? {return node->left == NULL && node->right == NULL;}

struct tree_node * insert_root(struct bintree * tree, type data) // 在空樹上插入第一個結點

{if (!bintree_is_empty(tree)) { perror("tree is not empty"); return NULL; }

struct tree_node * p = create_node(data);??? tree->root = p; ???return p; }

static int has_left_child(const struct tree_node * node)

??? {return node->left != NULL; }

static int has_right_child(const struct tree_node * node)

??????? {return node->right != NULL; }

struct tree_node * insert_left(struct tree_node * node, type data) // 插入左孩子

?? {if (has_left_child(node)) // 判斷是否有左孩子

??????? {?????? perror("node already has left child");? return NULL; ? }

??? struct tree_node * p = create_node(data);

??? node->left = p;

??? p->parent = node;

return p; }

struct tree_node * insert_right(struct tree_node * node, type data) // 插入右孩子

?? ?{if (has_right_child(node)) // 判斷是否有右孩子

??????????????? ?{??? perror("node already has right child");???? return NULL;?? }

struct tree_node * p = create_node(data);

??? node->right = p;

??? p->parent = node;

return p; }

struct tree_node * remove_root(struct bintree * tree) // 刪除根結點

{? ?if (!is_leaf(tree->root)) { perror("root is not leaf"); ?return NULL; ?}

??????? struct tree_node * p = tree->root;

??? tree->root = NULL;

??? return p; }

static int is_left_child(const struct tree_node * child, const struct tree_node * parent)

??? ?{return child->parent == parent && parent->left == child; }

static int is_right_child(const struct tree_node * child, const struct tree_node * parent)

??? ?{return child->parent == parent && parent->right == child; }

struct tree_node * bintree_remove(struct tree_node * node) // 刪除結點

??? {?????? if (!is_leaf(node)) {perror("node is not leaf");??? return NULL; }

??????? ?? struct tree_node * parent = node->parent;

if (parent)

????? {?? if (is_left_child(node, parent)) ??{parent->left = NULL; }

???? ?????????????? else if (is_right_child(node, parent)) ?{parent->right = NULL;}

? ???????????? ????node->parent = NULL;?? }

?? ??????????????? return node;??????????? ?}

6.四種二叉樹遍歷方法（前序、中序、后序、層次）

static void exec_pre_recurse(const struct tree_node * node, void (*access_function)(type data))

? {?? if (node == NULL) { ?return;? }

??? access_function(node->data);

??? exec_pre_recurse(node->left, access_function);

??? exec_pre_recurse(node->right, access_function); ??}

void pre_order_traverse(const struct bintree * tree, void (*access_function)(type data)) // 前序遍歷

{ exec_pre_recurse(tree->root, access_function); }

static void exec_in_recurse(const struct tree_node * node, void (*access_function)(type data))

?? ?{ ?if (node == NULL) {? return; ?}

exec_in_recurse(node->left, access_function);

?? ?????????? ?access_function(node->data);

?? ?????????? ?exec_in_recurse(node->right, access_function); ??}

void ?in_order_traverse(const struct bintree * tree, void (*access_function)(type data)) // 中序遍歷

{exec_in_recurse(tree->root, access_function); }

static void exec_post_recurse(const struct tree_node * node, void (*access_function)(type data)) { ?if (node == NULL) { return; ?}

exec_post_recurse(node->left, access_function);

??? exec_post_recurse(node->right, access_function);

??? access_function(node->data);? }

// 后序遍歷

void post_order_traverse(const struct bintree * tree, void (*access_function)(type data)) {

?? ?exec_post_recurse(tree->root, access_function);

}

struct bintree_queue_node // 層次遍歷用到的隊列，簡單一點利用鏈表實現

??? {struct tree_node * data;

??? struct bintree_queue_node * next; ?};

struct bintree_queue

{struct bintree_queue_node * front;

??? struct bintree_queue_node * rear; ?};

static struct bintree_queue * bintree_queue_init()

??? { struct bintree_queue * q = (struct bintree_queue *) malloc(sizeof (struct bintree_queue));

??? if (!q) { perror("bintree queue init failed"); return NULL; }

?? ? ??????? q->front = NULL;

??? ???????? q->rear = NULL;

?? ?????????? return q; ??}

static int bintree_queue_is_empty(const struct bintree_queue * q) // 判空

{ return q->front == NULL && q->rear == NULL; }

static void bintree_enq(struct bintree_queue * q, struct tree_node * data) // 入隊列

? ??? {struct bintree_queue_node * p = (struct bintree_queue_node *) malloc(sizeof (struct bintree_queue_node));

??? if (!p) { perror("bintree queue init failed"); return; }

??? p->data = data;

p->next = NULL;

if (bintree_queue_is_empty(q))

????? { ?q->front = p;

??????? ?q->rear = p;? }

?? else { p->next = q->rear->next;

??????? q->rear->next = p;

??????? q->rear = p; ?}?? }

static struct tree_node * bintree_deq(struct bintree_queue * q) // 出隊列

?{???? if (bintree_queue_is_empty(q))

???? {?? perror("bintree queue is empty");??? return NULL;??? }

??? struct bintree_queue_node * o = q->front;

??? q->front = o->next;

??? if (q->front == NULL) {? q->rear = NULL;??? }

return o->data;?? ?}

void level_order_traverse(const struct bintree * tree, void (*access_function)(type data)) // 層次遍歷

{?? struct bintree_queue * q = bintree_queue_init();

?? ? ?bintree_enq(q, tree->root);

while (!bintree_queue_is_empty(q))

???? ?{?? struct tree_node * node = bintree_deq(q);

??????? access_function(node->data);

??????? if (has_left_child(node)) {?? bintree_enq(q, node->left); ??}

??????? if (has_right_child(node)) {??? bintree_enq(q, node->right);??? }??? ??}????????? }

7.給定前序和中序、中序和后序的遍歷序列，畫出樹的形狀

前序：訪問根結點→先序遍歷左子樹→先序遍歷右子樹

中序：中序遍歷左子樹→訪問根結點→中序遍歷右子樹

后序：后序遍歷左子樹→后序遍歷右子樹→訪問根結點

（前中后：根的位置）

層次：依次訪問深度為1、2、…的結點，從上至下，從左至右

8.滿二叉樹與完全二叉樹

滿二叉樹：深度為k，且有2k-1個結點

完全二叉樹：深度為k，有n個結點的二叉樹，與深度為k的滿二叉樹中編號從1至n的結點一一對應（葉子結點只存在于最大的兩個層次上面）

9.如何把任意一棵樹、森林轉化為一棵等價的二叉樹

森林是含有若干棵獨立的樹的一個集合，把森林中某棵樹的根結點看成是前一棵樹的根結點的兄弟，則可將該森林轉換成一棵二叉樹

10.Huffman樹、如何構造

? 路徑：樹中一個結點到另一個結點間的分支

? 路徑長度：路徑中的分支數目

? 樹的路徑長度：從樹根到每一個葉子結點的路徑長度之和

? 樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和

? ??? WPL = ∑wk·lk? ， k = 1, …, n

Huffman樹（最優二叉樹）：設有n個權值{w1,w2,…wn}，某二叉樹共有n個葉子結點，每個結點的權值分別為wi，則帶權路徑長度最小的二叉樹稱為Huffman樹（最優二叉樹）。

Huffman樹的應用：二叉樹由于只有兩個分支，可以用來代表判定語句中的true和false

樹的應用之一就是條件分支的判定，對于有些問題需要經常進行條件判斷，則若采用合適的樹（如Huffman樹，則可以減少在樹中走的路徑長度）

構造Huffman樹的算法：

1.已知n個結點與各自的權值

2.以這n個結點分別作為一個只有一個根結點的樹，組成集合F

3.在集合F中，尋找根結點權值最小的兩棵樹，構造一個新的根結點，把這兩棵樹分別作為該新結點的左右孩子，新的根結點的權值為兩子樹根結點的權值之和

4.在集合F中加入新的樹，并刪除原來的兩棵樹

5.重復第二步和第三部，直到最后只剩下一棵樹，該樹即為Huffman樹

11.Huffman編碼構造方法

???????? 前綴編碼：任一字符的編碼都不是另一個字符編碼的前綴，如給A、B、C、D分別編碼為0，00，1，01，則字符串ABCAD的編碼字符串為0001001，但反過來譯碼時，就會產生歧義，因為該編碼方式非前綴編碼

???????? 設計一棵樹，把各個字符看做樹的葉子結點，各個字符出現的頻率看做結點的權值，每個結點到其左孩子的路徑為0，到右孩子的路徑為1，則前綴編碼的構造就是一個構造Huffman樹的過程，而譯碼就是遍歷整個Huffman樹的葉子結點的過程

12.樹的非遞歸算法

push(root)

while(棧非空)

????????????????? node←pop

PreOrder:??? if(not_visited(node.right))?? push(node.right)

????????????????????????? if(not_visited(node.left))

?????????????????????????????????? push(node.left)

????????????????????????? if(should_visit(node)) ????????? visit(node)

????????????????????????? else ?push(node)

InOrder:?????????? if(not_visited(node.right)) ??? push(node.right)

????????????????????????? if(should_visit(node)) ??????????? visit(node)

????????????????????????? else????????? ?????????????????????????????????? push(node)

????????????????????????? if(not_visited(node.left)) ?????? push(node.left)

PostOrder:?? if(should_visit(node)) ???????????? visit(node)

????????????????????????? else??????????????????????????? ????????????????? push(node)

????????????????????????? if(not_visited(node.right)) ??? push(node.right)

????????????????????????? if(not_visited(node.left)) ?????? push(node.left)?????????????????????????????????

should_visit(node)

????????????????? PreOrder:? return TRUE

????????????????? InOrder:? 左孩子為空或左孩子已被訪問過????? return TRUE，否則 return FALSE

????????????????? PostOrder:? 左孩子為空或左孩子已被訪問過 &&右孩子為空或右孩子已被訪問過

　return TRUE，否則? return FALSE

七．查找

1.查找表、關鍵字、主關鍵字、次關鍵字、查找、平均查找長度（ASL）

???????? 查找表（Search Table）：需要被查找的數據所在的集合，通常是同一類型的數據元素（記錄）構成的集合

關鍵字（Key）：數據元素中的某個數據項的值

主關鍵字（Primary Key）：該關鍵字可以唯一地標識一個記錄

次關鍵字（Secondary Key）：不是可以唯一標識一個數據元素的關鍵字

查找（Searching）：根據給定的值，在查找表中確定一個其關鍵字等于給定值的數據元素（記錄）。若存在這樣的記錄，則稱為查找成功，反之稱為不成功

平均查找長度（Average Search Length）：為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的期望值。

2.靜態查找表與動態查找表的區別

靜態查找表：只做查找操作，查詢某個特定的數據元素是否在表中，檢索某個特定的數據元素和各種屬性

動態查找表：在查找過程中同時還插入或刪除元素

3.折半查找算法

???????? 折半查找（Binary Search），也叫“二分法查找”。給定一個有序的數據集，依次比較區間中間位置元素的關鍵字與給定值，若相等則查找成功，若不等，則把范圍縮小一半，繼續以上步驟，直到找到，或者區間長度小于0（未找到）。

算法描述（從a[N]中查找是否有元素b）

1.設立三個指標low、high、mid，初值分別為low=0，high=N-1

2.如果low>high，則表示未找到b

3.如果low>=high，則令mid=(low+high)/2，比較b與a[mid]是否相等，如相等則表示找到該數據，如果b>a[mid]，令low=mid+1，如果b<a[mid]，令high=mid-1

4.重復2、3步驟

性能：假設有序表有n個元素，則折半查找在查找成功時進行比較的次數最多為log2n+1

int binary_search(type data[], int length, type key)

{??? int start = 0;

??? int end = length - 1;

??? while (start <= end)

?? {?? ???int mid = (start + end) / 2;

??????? ??int result = compare(data[mid], key);

????? ????if (!result) ?{??? return mid;????? }

else if (result > 0) {???? end = mid - 1; ??}

??????? ??else {?? start = mid + 1;?? }??? ?????????????????}

??? return -1; ????}

4.二叉排序樹（Binary Sort Tree）

???????? 定義：二叉排序樹或者是一棵空樹，或者具有以下性質：

1、若其左子樹非空，則左子樹的所有結點的值均小于根結點的值；

2、若右子樹非空，則右子樹的所有結點的值均大于根結點的值；

3、左右子樹同時也是二叉排序樹

struct binary_sorted_tree * bst_init()// 初始化

{? struct binary_sorted_tree * p = (struct binary_sorted_tree *) malloc(sizeof (struct binary_sorted_tree));

??? if (!p) {? perror("bst init failed"); ?return NULL;? }

p->root = NULL;?? return p; ?????????????}

static int is_leaf(const struct tree_node * node)

{??? return node->left == NULL && node->right == NULL; ?}

static struct tree_node * exec_clear_recurse(struct tree_node * node) {

??? if (node == NULL) {? return NULL;? }

??? node->left = exec_clear_recurse(node->left);

??? node->right = exec_clear_recurse(node->right);

??? free(node);

return NULL;??? ?}

5.根據一串輸入數據，如何構造二叉排序樹

插入的過程與查找類似，只是當查找不成功時，根據關鍵字與根結點的大小，將新結點（關鍵字的值）插入根結點的相應孩子的位置（左或者右）

例題：設有一個輸入數據的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫出從空樹起，逐個輸入各個數據而生成的二叉排序樹。

6.如何在二叉排序樹中進行查找

1.若根結點為空，則表示查找失敗

2.若根結點非空，比較關鍵字與根結點的大小，若相等，則表示查找成功

3.若根結點的值小于關鍵字的值，則遞歸查找右子樹，若根節點的值大于關鍵值，則遞歸查找左子樹

7.二叉排序樹的性能取決于什么

二叉排序樹查找關鍵字的比較次數，等于該結點所在的層次數（查找成功）,若查找不成功，其比較次數最多為樹的深度。對于一棵具有n個結點的樹來說，其深度介于㏒2n+1與n之間。所以排序二叉樹的形態對于查找效率至關重要，或者說，一棵排序二叉樹不一定就能提高查找的速度，而是要看這棵樹的形態。

8.二叉平衡樹的概念、平衡因子

二叉平衡樹（平衡二叉樹，或AVL樹）：它或是一棵空樹，或者是具有以下性質的二叉樹：它的左右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過一。

深度為O(㏒2n)

平衡因子（Balance Factor，BF）：某結點的左子樹深度減去右子樹深度。對于一棵平衡二叉樹，每個結點的平衡因子的取值只可能是-1、0或者1

9.二叉平衡樹有什么好處

平衡二叉樹（Balanced Binary Tree）

??? 如果能構造出一棵左右子樹相對“均衡”的樹，則樹的深度就會比較小，就能體現出樹的良好性質，查找效率高。

10.四種旋轉方式、各用在什么情況下
平衡二叉樹的結點旋轉（以p指向由于插入結點導致不平衡的最小子樹的根）

單向右旋（順時針）：當在p的左子樹根結點的左子樹上插入結點導致不平衡時

單向左旋（逆時針）：當在p的右子樹根結點的右子樹上插入結點導致不平衡時

先左后右：當在p的左子樹根結點的右子樹上插入結點導致不平衡時

先右后左：當在p的右子樹根結點的左子樹插入結點導致不平衡時

11.描述下如何在二叉平衡樹中插入一個新節點

平衡二叉排序樹T上插入一個新元素e的算法：

1.若T為空樹，則插入新元素e作為根結點

2.若T的根結點關鍵字等于e的關鍵字，則不做任何操作

3.若e的關鍵字小于T的根結點的關鍵字，則在T的左子樹上遞歸插入e，然后檢查下T的根結點的平衡因子，若平衡因子大于1或者小于-1，則根據上面四種情況之一進行調整

4.若e的關鍵字大于T的根結點的關鍵字，則在T的右子樹上做類似3中的操作

12.二叉平衡樹中的查找的時間復雜度

??? 對于二叉排序樹，其最大查找次數取決于樹的最大深度，含有n個結點的平衡二叉樹的最大深度是O(㏒2n)，因此平衡二叉排序樹的性能為O(㏒2n)。

13.哈希函數

???????? f : 關鍵字 → 存儲位置，即，hash函數是指關鍵字與存儲位置（哈希地址）的對應關系，只要給出關鍵字，就可以通過這個函數得到存儲位置

14.哈希表的定義

如：給定一個保存了10個元素的數組，[ 10, 31, 22, 133, 254, 65, 16, 47, 98, 2009 ]，你會用什么方法去查找表里的某一個元素

如果給定Hash函數f(K)=K mod 10，就可以立刻得到該鍵值對應元素的數組下標

如果給定Hash函數f(K)=K mod 2，則雖然也縮小了查找范圍，但達不到上面函數的效果

哈希表：根據設定的哈希函數H(key)和處理沖突的方法，將一組關鍵字映射到一個有限的連續的地址區間上，并以關鍵字的映像作為記錄在表中的存儲位置

映射過程稱為哈希造表，或者散列（哈希表有時也叫散列表）

所得的存儲位置值稱為哈希地址或者散列地址

15.幾種哈希函數的構造算法

?1.直接定址法：取關鍵字或者關鍵字的某個線性函數作為Hash地址，即：H(key) = key，

???????? H(key) = a×key + b，a、b為常數

?2. 數字分析法

3.平方取中法

4.折疊法

?5.除留余數法（取模）：

??? 把關鍵字對某個數p（不大于哈希表的表長m）取模，所得到的數作為哈希地址

???? H(key) = key MOD p, p≤m?? （p值的選取，影響到散列之后的效果）

6. 隨機數法：H(key) = random(key)，把產生的隨機數做為哈希地址

16.沖突、處理沖突的基本思想

沖突：如果不同的鍵值，被Hash函數映射到同樣的一個哈希地址，則稱為沖突。Hash函數不可能完全避免沖突，只可能盡量減少沖突，或者說，好的Hash函數能將關鍵字映射后得到的哈希地址，盡量均勻地分布

處理沖突的基本思想：在處理的過程中，可能會得到一個地址序列Hi，i = 1，2，…，k，即每次得到一個哈希地址Hi，若仍然發生了沖突，則再由相應方法得到下一個哈希地址Hi+1，直到得到一個不發生沖突的哈希地址為止

17.幾個處理沖突的方法（開放地址法、再哈希法、鏈地址法）

???????? 1.開放定址法：處理沖突函數為Hi = (H(key) + di) MOD m, i = 1,2, …,k, k ≤ m-1，H為哈希函數，m為哈希表的表長，di為增量序列。di的選取方法：

di=1,2,3, …,m-1，稱為“線性探測再散列”

di=12,-12,22,-22, …,k2,-k2, k≤m/2，稱為“二次探測再散列”

di為偽隨機數序列，稱為“偽隨機探測再散列”

2.再哈希法：Hi = RHi(key), i = 1,2, …, k， RHi為不同的一些哈希函數

3.鏈地址法：將所有沖突的記錄存儲在一個線性鏈表中，哈希函數得到的地址中保存這個鏈表

18.哈希表中查找一個元素的過程

哈希表的查找過程與構造過程基本一致，在查找過程中，利用哈希函數和沖突函數，直到查找失敗或者查找成功

影響哈希函數比較次數的因素：

1.哈希函數

???????? 哈希函數的好壞，影響出現沖突的頻繁程度。一個均勻的哈希函數，對一組關鍵字，產生的沖突可能性都相同，它不是影響ASL的決定性因素

2.沖突處理方法

???????? 針對所介紹的幾個沖突處理方法（線性探測、二次探測、隨機探測、再探測、鏈地址），各自的ASL不同

3.裝填因子（衡量哈希表的裝滿程度）影響該哈希表的ASL

α（裝填因子）= 表中記錄數/哈希表長度

裝填因子越小，發生沖突的可能性就越小，反之就越大（需比較的次數就越多）

八．排序

1.排序的基本概念、穩定、內部排序與外部排序

2.簡單排序方法有：插入排序、冒泡排序、選擇排序

3.先進排序方法有：shell排序、快速排序、堆排序、歸并排序

4.基數排序

5.Shell排序中的步長序列（或增量因子）、shell排序的大致過程，shell排序快慢的關鍵

6.快速排序中：支點（pivot），算法的基本過程，快慢取決于什么

7.會使用C庫中自帶的快速排序函數qsort

8.什么叫做堆（注意與排序樹的差別）、最大堆、最小堆

9.描述堆排序的過程（兩個主要過程），每一次建堆之后會形成什么狀態

10.何為歸并，歸并排序的主要過程

11.多關鍵字排序

12.MSD方法與LSD方法

13.基數排序的過程（詳細描述）（分配與收集）

14.各種排序方法的比較（最壞、平均時間復雜度、所需輔助空間、穩定與否）

待續