目錄

• 一、預備知識
• • 1、預備知識
  • • （1）數據結構概述
  • 2、衡量算法的標準
  • 3、數據結構的地位
  • 4、指針
  • • （1）基本類型的指針
    • （2）數組和指針
  • 5、結構體的使用
  • 6、動態內存的分配
  • • （1）舉例：動態構造一個int型數組
    • （2）跨函數使用內存
  • 7、typedef 的用法
• 模塊一：線性結構
• • 1、連續存儲數組
  • • （1）init_arr
    • （2）show_arr
    • （3）append_arr
    • （4）insert_arr
    • （5）delete_arr
    • （6）inversion_arr
    • （7）sort_arr
  • 2、離散存儲鏈表
  • • （1）專業術語
    • （2）節點的數據類型，該如何表示
    • （3）鏈表的分類
    • （4）鏈表的偽算法
    • （5）基本算法實現
    • • （1）create_list
      • （2）traverse_list
      • （3）is_empty
      • （4）length_list
      • （5）insert_list
      • （6）delete_list
      • （7）sort_list
      • 補充泛型的初步定義：
  • 3、線性結構的應用 —— 棧
  • • （1）序言
    • （2）棧的算法實現
    • • （1）init
      • （2）push
      • （3）traverse
      • （4）pop
      • （5）clear
    • （3）棧的應用
  • 4、線性結構的應用—— 隊列
  • • （1）序言
    • （2）靜態隊列的分析：
    • （3）循環隊列程序演示
    • • （1）init
      • （2）en_queue
      • （3）full_queue
      • （4）traverse_queue
      • （5）out_queue
      • （6）empty_queue
    • （4）隊列的具體的應用
• 遞歸專題
• • 1、前景知識
  • 2、應用舉例
  • • （1）求階乘
    • （2）求 1+2+3+4+....+100
  • 3、對遞歸的理解
  • • （1）函數調用：
    • （2）函數調用，棧的使用
    • （3）遞歸調用，必須滿足的3個條件
    • （4）循環的遞歸的關系
    • （5）漢諾塔
  • 4、遞歸的應用

學玩數據結構要達到的目的：
（1）對數據結構要有一個基本的了解。
（2）要熟練 掌握鏈表的操作
（3）偽算法要能看懂（偽算法：只是邏輯，沒有代碼實現）

一、預備知識

使用教材：嚴蔚敏，吳偉民編寫的《數據結構》
但是書中的算法都是偽算法（不是程序），都是解題的思路
具體的程序由高一凡主編的書里面有。
黃國瑜寫的數據結構也可以。

模塊一： 線性結構

• 連續存儲（數組）
  優點：存取速度很快，可以直接找到某一個元素
  缺點：
  （1）插入刪除元素比較慢（后面的元素都得移動）
  （2）需要大片的內存
  （3）事先知道數組的長度（防止內存污染）

• 離散存儲（鏈表）
  優點：
  （1）插入刪除元素比較方便（只需要切換指針域即可）
  （2）并不需要大片的內存
  缺點：存取速度比較慢

• 線性結構的兩種常用應用之一 （棧）

• 線性結構的兩種常用應用之一 （隊列）

• 專題：遞歸
  （1）1+2+3+4+5+… 100 的和
  （2）求階乘
  （3）漢諾塔
  （4）走迷宮

模塊二：非線性結構

• 樹
• 圖

模塊三：查找和排序

• 折半查找
• 排序：冒泡、插入、選擇、快速、歸并

1、預備知識

（1）數據結構概述

定義：
1、我們如何把現實當中，大量而復雜的問題以，特定的數據類型 和 特定的存儲結構，保存到內存當中。

2、在此基礎上，為實現某個功能（比如查找某個元素、刪除某個元素、對所有元素進行排序），而執行的相應操作，這個相應的操作叫做算法。

舉例：如何保存一個班級學生的信息？

（1）少數較少的時候，使用數組就可以。（需要內存是連續的）
（2）但是保存1000 個學生信息，就沒有這么大的連續空間，可以使用鏈表實現。（使用鏈表，可以將其他零散的內存利用起來）

（3）如保存人事單，如果使用鏈表則不知道他們之間的關系誰是領導，這種結構需要使用樹結構。（樹的結構：就可以知道誰是領導，誰是下屬）

（4）再如交通圖，幾個站點之間修路，則需要使用圖結構實現。

總結：
數據結構：解決數據如何存儲的問題。（個體和個體的關系）
算法：如何對已經存儲的數據，進行操作。

2、衡量算法的標準

1、時間復雜度：大概程序要執行的次數、而非執行的時間。（因為硬件不同）

2、空間復雜度：算法執行過程中，大概所占用的最大內存。

3、難易程度：不能只有自己一個看懂

4、健壯性：不能給一個非法立即數就掛掉了。

3、數據結構的地位

數據結構是軟件中最核心的課程。

程序 = 數據的存儲 + 數據的操作 + 可以被計算執行的語言。

4、指針

（1）內存是 cpu 能夠直接訪問的，唯一的存儲器。

（2）通過地址線，來確定，對哪塊內存來進行存儲。（32位——0 – 4G-1）

（3）通過控制線，來確定，對內存是 讀取還是 寫入。

（4）通過數據線，來確定，傳輸什么數據。

總結：
（1）地址：內存單元的編號， 0000 0000 – FFFF FFFF， 從0 開始的非負整數。

（2）指針：指針就是地址，地址就是指針。是一個操作受限的非負整數。

（3）指針變量：是存放，內存單元地址（編號），的單元。

（1）基本類型的指針

int *p;

p ： 是一個變量的名字
int * ：表示 p 只能存放，整形變量的地址。

必須理解，只能存放，這個概念。

int * p; char a = 'A'; p = &a; //error：&a 不是整形變量的地址 p = 10； //error：10 是一個整數，不是一個地址

（2）數組和指針

int a[5] = {1,2,3,4,5};

數組名的理解：
（1）一維數組名：它是一個，指針常量。
（2）一維數組名：它里面存放的是，第一個元素的地址。
（3）一維數組名：指向，數組當中的第一個元素。

下標的理解：

a[3] <=====> *(a+3)3[a] <=====> *(a+3)

5、結構體的使用

（1）為什么會出現結構體？
為了表示一些復雜的數據類型，而單個基本類型無法滿足需要。

（2） 什么是結構體？
用戶根據實際需要，自己定義的復合數據類型。

分號不能省略，分號表示結構體定義結束。

struct Student{ int aga; char address; char sex; }; //分號不能省略，分號表示結構體定義結束

• 定義了一個，新的數據類型。（類似于 int ）
• 只是單純的定義了一個類型，而不定義一個變量，也就是說并不分配內存。
• 這個數據類型的名字： struct Student

（3）如何使用結構體

兩種方式:struct Student st = {1000, "zhangsan", 20};struct Student * pst = &st;1.st.sid 2.pst->sidpst所指向的結構體變量中的sid這個成員

注意事項：

• 結構體變量不能加減乘除，但是可以相互賦值
• 普通結構體變量 和 結構體指針變量，作為函數參數傳參的問題

#include <stdio.h> #include <string.h>struct Mystruct {int id;char name[200];int age; }; void fcun(struct Mysturct s1) // 輸入型參數，不會修改本身的值 { printf("%d,%s,%d \n", s1.id,s1.name,s1.age); } void func1(struct Mysturct *ps1) // 輸出型參數，會修改實參的值 {*ps1.s1 = 10086;strcpy(ps1->name,"zhangsan");ps1->age = 20; }int main(void) {struct Mysturct s1;func1(&s1);func(s1); }

（1）當結構體變量，變為函數參數時候：

void fcun(struct Mysturct s1) // 輸入型參數，不會修改本身的值 { printf("%d,%s,%d \n", s1.id,s1.name,s1.age); }

這樣傳參：會發生結構體的賦值，整個結構體單元都會被拷貝。
這種方法：耗用內存、耗費時間，不推薦。(發送了 200多個字節)

解決辦法：結構體指針傳參

void fcun(struct Mysturct *s1) // 輸入型參數，不會修改本身的值 { printf("%d,%s,%d \n", s1->id,s1->name,s1->age); }

這樣傳參：只傳送了 4 個字節。

6、動態內存的分配

怎么區分動態內存和靜態內存？

只要使用了 malloc 函數就是動態的。
沒使用，就是靜態的。

（1）舉例：動態構造一個int型數組

char a[5] = {1,2,3,4,5};

這個數組的空間大小，在運行當中是不可以改變的，只能重新編寫。

int len; printf("請輸入你需要的數組的長度 len = "); scanf("%d",len); int *pArr = (int *) malloc(sizeof(int) * len);*pArr = 4; // 類似于 a[0] = 4 pArr[1] = 5; // pArr[1] <=====> *(pArr + 1)free(pArr); // 釋放這個內存空間

這個數組的空間大小，在運行當中，取絕于用戶的輸入，所以是動態的。

（1）malloc 函數的形參：是一個 int 類型的整數，表示申請多少個字節大小的內存空間。
（sizeof 返回值是一個整數，int 占用4個字節）

（2）malloc函數的功能是請求系統len個字節的內存空間，如果請求分配成功，則返回第一個字節的地址，如果分配不成功，則返回NULL.

第一個字節地址：它并沒有實際的含義，因為我們根據這個地址，可以把 8 個字節當一個變量，也可以把4個字節當一個變量。

（3）(int *) 強制轉換：就是根據這個地址，把4個字節當作一個變量。

（4）malloc 申請的空間使用

*pArr = 4; // 類似于 a[0] = 4 pArr[1] = 5; // pArr[1] <=====> *(pArr + 1)

可以當作一個普通的數組來使用。

（2）跨函數使用內存

通過調用 fun ，使main 函數當中的指針變量 p 指向一個合法的變量單元。

void fun(int *q) {int s;q = &s; }int main(void) {int *p;fun(p); }

不可以：因為這是一個 值傳遞，調用完函數，實參p 的值根本沒有改變

void fun(int **q) {int s;*q = &s; }int main(void) {int *p;fun(&p); }

不可以：
（1）雖然變成了地址傳遞，最終 p 的值也發生了改變。
（2）但是 s 變量的內存，在fun 執行完畢之后，就銷毀了。

void fun(int *q) {q = (int *) malloc(4); }int main(void) {int *p;fun(p); }

不可以：因為這是一個 值傳遞，調用完函數，實參p 的值根本沒有改變

void fun(int **q) {*q = (int *) malloc(4); }int main(void) {int *p;fun(&p); }

可以訪問：因為malloc 函數申請的內存，只有 free 函數才能釋放。

使用案例：

#include <stdio.h> #include <malloc.h>struct Student {int id;int age; };struct Student * CreatStudent(); // 返回值使 struct Student * 類型 {return (struct Student *) malloc(sizeof(struct Student)); } void ShowStudent(struct Student *ps1) {printf("%d, %d\n", ps1->id, ps1->age); }int main() { struct Student *ps1; //申請了 4 個字節的內存空間 ps1 = CreatStudent(); // 又申請了 8 個字節（1個結構體變量）的空間 ShowStudent(ps1); // 輸入型參數 return 0; }

7、typedef 的用法

我們自己構建的數據類型，struct Mystruct 的名字太長用起來不方便

typedef int zhangsan int i = 0; <======> zhangsan i = 0; typedef struct Student {int sid;char name[20]'int age; }ST; // typedef 給 struct Student 新起了一個名字叫做 STstruct Student st; <=======> ST st; struct Student *pst; <=======> ST *pst; typedef struct Student {int sid;char name[20]'int age; }* PST; // typedef 給 struct Student * 新起了一個名字叫做 PST struct Student *pst; <=======> PST pst; typedef struct Student {int sid;char name[20]'int age; }* PSTU,STU; // typedef 給 struct Student * 新起了一個名字叫做 PSTU // 給 struct Student 新起了一個名字叫做 STU struct Student *pst; <=======> PSTU pst; struct Student st <=======> STU st;

模塊一：線性結構

數據結構 = 個體的存儲 + 個體的關系存儲
算法 = 對存儲數據的操作（增加、刪除、遍歷等等）

別人問：什么是線性結構？
把所有的結點，用一根直線穿起來。

1、連續存儲數組

int a[10]; int *pArr = (int *)malloc(len);

自己定義一個數據類型，并且為它添加方法。

#include <stdio.h> #include <malloc.h> //定義一個數據類型，里面又三個變量 struct Arr {int *pBase; // 存放數組第一個元素的地址int len; // 數組所能容納的最大個數int cnt;// 當前數組的元素個數 } // 定義一些算法 void init_arr(); // 初始化整個數組 bool append_arr(); //在數組最后，追加一個元素 bool insert_arr(); // 在數組當中插入一個元素 bool delete_arr(); // 刪除一個數組元素 bool get_arr(); bool is_empty(); // 判斷是否為空 boll is_full(); // 判斷是否為滿void sort_arr(); // 排序整個數組 void show_arr(); // 輸出數組 void inversion_arr(); //導致整個數組int main(void) {struct Arr arr;init_arr(&arr,6);shouw_arr(&arr);return 0; }void init_arr(struct Arry *pArr , int length) { pArr -> pBase = (int *) malloc(sizeof(struct Arry) * length); if(NULL == pArr->pBase){printf("malloc error");exit(-1); // 終止整個程序} else{pArr -> len = length;pArr -> cnt = 0;}return; }

（1）init_arr

我們希望，一調用 init_arr 函數， arr 當中的 pBase 指向一塊連續內存。len 表示這個內存的大小，cnt 有效元素的個數。

分析： 1、需不需要返回值 2、需不需要參數：肯定需要，沒有的話，不知道操作誰（1）輸入型參數？（2）輸出型參數？struct Arr arr; init_arr(arr); void init_arr(strcut Arr array) // 傳值方式，根本不會改變實參的內容 {array.len = 99; }struct Arr arr; init_arr(&arr); // 傳入地址 void init_arr(strcut Arr *parr) // 傳址方式，可以改變實參內容 {(*parr).len = 99; }void init_arr(struct Arry *pArr , int length) { pArr -> pBase = (int *) malloc(sizeof(struct Arry) * length); if(NULL == pArr->pBase){printf("malloc error");exit(-1); // 終止整個程序} else{pArr -> len = length;pArr -> cnt = 0;}return; }

（2）show_arr

輸出這個數組
傳入指針：只傳遞 4 個字節的內容

void show_arr(struct Arry *pArr) // 輸出數組， {if（數組為空）提示用戶數組為空else輸出數組有效內容 }bool is_empty(struct Arry *pArr) {if(0 == pArr -> cnt)return ture;elsereturn flase; }要注意：pArr 是一個結構體變量的地址 void show_arr(struct Arry *pArr) // 輸出數組， {if(is_empty(pArr))printf("數組為空！\n");elsefor(int i = 0; i < pArr->cnt , i++){printf("%d\n",pArr->pBase[i]);} }

（3）append_arr

bool append_arr(struct Arry *pArr, int val) {if(數組滿了)提示用戶數組滿了else追加 }bool is_full(struct Arry *pArr) {if(pArr->cnt == pArr->len)return ture;elsereturn flase; }bool append_arr(struct Arry *pArr, int val) {if(is_full(pArr)){printf("數組已滿\n");return flase;}elsepArr->pBase[pArr->cnt] = val;(pArr->cnt)++;return ture; }

（4）insert_arr

思考函數要實現的功能：
向指定位置插入一個數字。
所以需要傳入的參數：
1、結構體（數組、數組大小、當前元素個數）
2、準備插入的位置
3、要插入的值

// pos從1開始，假設pos = 3, val = 55; 則 a[2] = 55; bool insert_arr(struct Arry *pArr, int pos,int val) {int i = 0;if(is_full(pArr)) // 如果滿了return flase;if(pos<1 || pos > pArr->cnt-1) //如果元素不夠：一共有 3 個元素，就不可以在第 5 個位置插入return flase;// 先進行后移for(i = cnt-1; i>=pos-1; i--) // 這個循環，一步一步去試數字然后往出寫{pArr->pBase[i+1] = pArr->pBase[i]} // 再進行插入pArr->pBase[pos-1] = val;(pArr->cnt)++; }

（5）delete_arr

思考函數要實現的功能：
向指定位置刪除一個函數、并且返回成功、還是返回失敗？并且想返回被刪除的值？
所以需要傳入的參數：
1、結構體（數組、數組大小、當前元素個數）
2、準備刪除的位置
3、輸出型參數 int *pVal (從而實現多個返回值)

主函數調用： int val; // 定義一個變量來接收刪除的數字 struct Arr arr;delete(&arr,1,&val);bool delete(struct Arry *pArr, int pos, int *pVal) {int i = 0;if( is_empty(pArr) )return flase;if(pos<1 || pos > pArr->cnt) // 要刪除，必須有這個值return flase;// 先拿出*pVal = pArr->pBase[pos-1];// 再移動for(i = pos; i<cnt ; i++){pArr->pBase[i-1] = pArr->pBase[i];(pArr->cnt)--;}return ture; }

（6）inversion_arr

函數功能：倒置
最后一個換到第一個

void inversion_arr(struct Arry *pArr) {int i = 0; //第一個元素int j = (pArr->cnt）- 1； // 最后一個元素int tmp = 0; while(i<j){tmp = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = tmp;} return 0; }

（7）sort_arr

void sort_arr(struct Arry *pArr) {int i, j = 0;int tmp = 0;for(i=0; j < pArr->cnt-1; ++i) // cnt-1 說明最后一個不用比較{for(j = i+1 ; j <pArr->cnt; ++j){if(pArr->pBase[i] > pArr->pBase[j]) // 把小的換到前面來{tmp = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = tmp;} }}}

2、離散存儲鏈表

鏈表的重要性：是我們學習數據結構的基礎，
如下面的樹（一個結點指向下面多個結點）

圖（任何一個結點可以保存其他結點的地址）

（1）專業術語

定義：

（1）n個節點離散分配
（2）彼此通過指針相連接，上一結點保存了下一個結點的地址
（3）每個節點只有一個前驅節點，一個后續節點。首節點沒有前驅節點，尾結點沒有后續節點。
(樹下面可以有很多節點)

專業術語：

首節點：第一個有效結點
尾結點：最后一個有效結點

頭結點：
（1）第一個有效結點，之前的結點
（2）頭結點，不存放有效數據
（3）加頭結點的目的是可以方便我們對鏈表的操作
（4）頭結點與其他結點，數據類型完全一樣

頭指針：第一個節點的地址
指向頭結點的指針變量（可能不對，是指向第一個有效結點的指針）

尾指針：最后一個節點的地址
指向尾結點的指針變量。

如果我們希望，通過函數來對鏈表進行處理，我們至少需要接受鏈表的幾個參數

數組：（3個參數）首地址、長度、當前元素個數。

鏈表：（1個參數）首地址（頭指針）
注：
（1）頭節點的數據結構，和其他的節點一樣。
（2）所以我們知道 頭指針，可以一個一個推算出下面節點的信息。

（2）節點的數據類型，該如何表示

每一個節點,都是一個數據類型。
每一個節點當中，應該包含什么？應該有幾個成員？

• 有效數據
• 指針（地址）：指向下一個節點。

問題：
（1）通過指針，我們要找到后面一個節點，而不是僅僅是首地址。

int *p = (int *)0x10002000; *p = 2; // 這樣的解引用，是將整數 2 ，存放到了 0x10002000 地址開頭的四個字節當中。char *p = (char *)0x10002000; *p = 2; // 這樣的解引用，是將整數 2 ，存放到了 0x10002000 地址開頭的 1 個字節當中。

我們每個節點的數據類型一樣。
所以我們指針，相當于指向了和自己數據類型一樣的變量。

struct Node {int data; // 數據域（本身可以特別復雜）struct Node *pNext; // 指針域 }typedef struct Node {int data; // 數據域（本身可以特別復雜）struct Node *pNext; // 指針域 }NODE, *PNODE;

（3）鏈表的分類

• 單鏈表
  

• 雙鏈表（每一個節點有兩個指針域）

• 循環鏈表 能通過一個節點，找到任何一個節點
  

• 非循環鏈表

（4）鏈表的偽算法

遍歷（找到節點，之后就可以，增加、刪除、改變、等等）
查找
清空
銷毀
求長度
排序
刪除結點
插入節點

插入非循環節點的偽算法

把 q 指向的節點，插入 p 指向節點的后面

注意：指針和結構體的知識：
（1）指針 p ：本身并沒有指針域， p 指向的結構體才有指針域

p -> pNext ; // p 指向結構體，這樣調用該結構體當中的成員

（2）實現的效果：p中的指針域，指向q。 q當中指針域指向下一個節點

p -> pNext = q; // p指向的結構體當中的指針域，指向q q -> pNext = // 發現已經丟失了一下個節點的地址 r = p -> pNext; // 先將下一個地址，存起來 p -> pNext = q; q -> pNext = r; q -> pNext = p -> pNext; // 先將 q 的指針域，指向下一個節點 p -> pNext = q;

刪除肺循環節點的偽算法

問題：導致內存泄漏（找不到第2個節點的地址，所以無法釋放）

p -> pNext = p -> pNext -> pNext ; free(p -> pNext) ; //錯誤：p -> pNext 已經發生改變

解決：

r = p -> pNext; // 先將第二個節點地址保存 p -> pNext = p -> pNext -> pNext ; free(r); // 然后再釋放

（5）基本算法實現

#include <stdio.h> #include <malloc.h>typedef struct Node {int data; // 數據域struct Node *pNode; // 指針域 }NODE, *PNODE;int main(void) {//跨函數使用內存（動態內存）PNODE pHead = NULL;pHead = create_list(); // 創建一個非循環單鏈表，并將該鏈表的頭節點地址賦值給 pHead return 0; }

（1）create_list

1、返回值：（是一個地址，頭節點地址） PNODE
2、參數：不需要

流程：

1、首先生成一個頭節點
2、由用戶決定生成的節點個數
3、創建這些節點

不循環生成節點：非常麻煩，想要申請100個，就得寫100次。

//獲取用戶信息 printf("請輸入第 1 個節點的值: val= "); scanf("%d",&val); //生成第一個節點的地址為 pNew PNODE pNew1 = (PNODE)malloc(sizeof(NODE)); //將用戶信息存放 pNew1 -> data = val; //將這個節點的首地址，掛到上一個節點指針域 pHead -> pNext = pNew1; // 每次創建，將尾結點的指針域指向 NUll pNew1 -> pNext = NULL;// 第二個節點 //獲取用戶信息 printf("請輸入第 2 個節點的值: val= "); scanf("%d",&val); //生成第二個節點的地址為 pNew2 PNODE pNew2 = (PNODE)malloc(sizeof(NODE)); //將用戶信息存放 pNew2 -> data = val; //將這個節點的首地址，掛到上一個節點指針域 pNew1 -> pNext = pNew2 ; // 每次創建，將尾結點的指針域指向 NUll pNew2 -> pNext = NULL;

循環生成節點：

for (i = 0; i < len; i++) {//獲取用戶信息 printf("請輸入第 1 個節點的值: val= "); scanf("%d",&val); //生成第一個節點的地址為 pNew PNODE pNew = (PNODE)malloc(sizeof(NODE)); //將用戶信息存放 pNew -> data = val; //將這個節點的首地址，掛到上一個節點指針域 pHead -> pNext = pNew; // 每次創建，將尾結點的指針域指向 NUll pNew -> pNext = NULL; }

出現的問題：只有第一次可以創建成功，后面都失敗

解決辦法：自己構造一個，多余的指針，讓這個指針始終指向尾結點

for (i = 0; i < len; i++) {//獲取用戶信息 printf("請輸入第 1 個節點的值: val= "); scanf("%d",&val); //生成第一個節點的地址為 pNew PNODE pNew = (PNODE)malloc(sizeof(NODE)); //將用戶信息存放 pNew -> data = val; //將這個節點的首地址，掛到上一個節點指針域 pTail -> pNext = pNew; // 每次創建，將尾結點的指針域指向 NUll pNew -> pNext = NULL; // 將pTail 后移 pTail = pNew; }

整體的創建實現

PNODE create_list() {int len = 0;int i = 0;int val = 0;//生成一個頭節點PNODE pHead = (PNODE) malloc(sizeof(NODE));if(NULL = pHead){printf("分配失敗\n");exit(-1);}PNODE pTail = pHead ;pHead -> pNext = NULL; // 尾結點的指針域永遠為NULLprintf("請輸入您需要生成的鏈表節點個數：len = ");scanf("%d",len);//數組的內存是連續的，所以可以直接 malloc//鏈表的內存是離散的，所以需要一個循環for (i = 0; i < len; i++){//獲取用戶信息printf("請輸入第 1 個節點的值: val= ");scanf("%d",&val);//生成第一個節點的地址為 pNew PNODE pNew = (PNODE)malloc(sizeof(NODE));//將用戶信息存放pNew -> data = val;//將這個節點的首地址，掛到上一個節點指針域pTail -> pNext = pNew;// 每次創建，將尾結點的指針域指向 NUllpNew -> pNext = NULL;// 將pTail 后移pTail = pNew;}return pHead; // 返回頭指針 }

（2）traverse_list

1、返回值：不需要
2、參數：必須要，指定對哪一個鏈表進行遍歷

void traverse_list(PNODE pHead) {PNODE p = pHead -> pNext;while(NUll != p) //如果 p 不為空（下一個節點存在）{printf("%d\n", p-> data);// p++ ,移動到下一個節點p = p->pNext;}printf("\n"); }

（3）is_empty

參數： PNODE pHead 判斷是哪一個鏈表
返回值：bool，判斷是否成功

bool is_empty(PNODE pHead) {if(NULL == pHead->pNext) //頭節點的指針域為空return true;elsereturn false; }

（4）length_list

參數： PNODE pHead 判斷是哪一個鏈表
返回值：int 返回長度

思路：遍歷的時候計數即可

int length_list(PNODE pHead) {PNODE p = pHead -> pNext;int cnt = 0;while(NUll != p) //如果 p 不為空（下一個節點存在）{cnt++; // 計數p = p->pNext;}return cnt; }

（5）insert_list

參數：PNODE pHead 判斷是哪一個鏈表
int pos：插入的位置
int val：插入的值 （輸入型參數）
返回值：是否成功

bool insert_list(PNODE pHead,int pos,int val) { // pos 的值必須合法，一共有 5 個節點，那么插入第 10 個就錯誤 int i = 0; PNODE p = pHead;//移動節點位置 // 當前節點不是尾結點 NULL!=p ：說明如果移動到尾節點就停止移動// 并且移動到第 pos-1 個節點之前 // 代數：pos=1時，向第一個節點之前插入，當前p指向頭節點，不需要執行循環 // pos=2時，向第二個節點之前插入，所以需要執行一次。 while(NULL!=p && i<pos-1) {i++;p = p->pNext; }// 如果pos的值不合法的時候 // 或者移動到尾結點之后，我們在此處進行返回 if(i>pos-1 || NULL==p)return false; // 分配動態內存 PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf("insert 動態內存分配錯誤\n"); exit(-1); } // 保存用戶數據 pNew -> data = val; // 插入節點// 保存后面節點的地址 PNODE q = p->pNext;// 然后將前面的節點指向新申請的節點 p->pNext = pNew;// 將插入的節點指向后面的節點 pNew->pNext = q;return true; }

（6）delete_list

參數：PNODE pHead 判斷是哪一個鏈表
int pos：刪除的位置
int *val：插入的值 （輸出型參數）

bool delete_list(PNODE pHead,int pos,int val) { int i = 0; PNODE p = pHead; //移動節點位置 // 當前節點不是尾結點 NULL!=p ：說明如果移動到尾節點就停止移動// 并且移動到第 pos-1 個節點之前 // 代數：pos=1時，向第一個節點之前插入，當前p指向頭節點，不需要執行循環 // pos=2時，向第二個節點之前插入，所以需要執行一次。 while(NULL!=p->Next && i<pos-1) {i++;p = p->pNext; }// 如果pos的值不合法的時候 // 或者移動到尾結點之后，我們在此處進行返回 if(i>pos-1 || NULL==p->Next)return false;//刪除節點//保留當前節點地址 PNODE q = p->pNext;//輸出刪除節點的內容 *val = q->data;//更換指針域 p->pNext = p->pNext->pNext;//釋放內存 free(q); q = NULL;return true; }

（7）sort_list

參數：PNODE pHead 判斷是哪一個鏈表
返回值： 無

數組和鏈表的探討

不同點：一個是連續的，另一個是離散的。
相同點：都是線性結構，算法嚴格來說是一樣的（邏輯上）
比如：都可以使用冒泡來進行排序。（第一個依次和后面比較）

void sort_list(PNODE pHead) {int i, j = 0;int tmp = 0;int len = length_list(pHead);PNODE p,q; // p相當于i， q相當于jfor(i=0,p=pHead->pNext; i < len-1; ++i, p=p->pNext) {for(j=i+1, q = p->pNext ; j <len ; ++j , q= q->pNext){if(p->data > q->data ) // 把小的換到前面來{tmp = p->data;p->data = q->data;q->data = tmp;} } }

補充泛型的初步定義：

算法：（數組和鏈表的算法一樣嗎？）

狹義的算法：與數據的存儲方式，密切相關
廣義的算法：與數據的存儲方式，不相關

泛型：
利用某種技術：達到，不同的存儲方式，執行的操作是一樣的。

舉例：運算符的重載

p++：我們可以將 ++ 運算符進行重載。（為 ++ 重寫一個函數）
所以廣義上來說就實現了泛型

3、線性結構的應用 —— 棧

（1）序言

靜態內存：分配在棧上
局部變量
棧序：先進后出

動態內存：分配在堆上
malloc 函數
堆序：堆排序

棧的定義：事先 “先進后出” 的數據結構。（類似于一個杯子）

棧的分類：

靜態棧：是用數組來實現
注意：靜態棧必須提前確定棧的大小(有限的),并且都是連續的.

動態棧：是用鏈表來實現.
動態棧可以無限大小(內存夠的情況下),并且是不連續的.

分析棧和鏈表的區別：
棧只能在棧頂進入，或者是棧頂刪除。

棧的算法：

出棧：
入棧：

（2）棧的算法實現

pBottom：指向頭節點（里面并不存放有效數據）,棧底元素的下一個
pTop ：指向尾結點

刪除元素：pTop 向上移動
插入元素：pTop 向下移動

判斷空棧：pTop == pBottom

#include <stdio.h> #include <malloc.h> #include <stdlib.h>// 定義每個節點的數據類型 typedef struct Node {int data; // 數據域struct Node *pNext; // 指針域 }NODE, *PNODE;typedef struct Stack {PNODE pTop;PNODE pBottom; }STACK, *STACK;int main(void) {STACK S; // 等價于 struct Stack S // 初始化棧指針initStack(&S); // 一定要思考傳入什么參數 // 壓棧push(&S,1);push(&S,2); // 遍歷輸出traverse(&S); }

（1）init

// 數入之前：棧指針都是垃圾值 // 1、如果我們的 棧頂指針和棧底指針 都指向一個頭節點（無用），才能說明我們構造了一個空棧 // void init(PSTACK PS) {PS -> pTop = (PNODE)malloc(sizeof(NODE));if(NULL == PS -> pTop){printf("init 動態分配出錯\n");exit(-1);}else{PS -> pBottom = PS -> pTop;// 將頭節點的指針域清空PS -> pTop ->pNext = NULL;} }

（2）push

// 1、新申請一個節點 // 2、入棧的指針域，指向 上一個節點 // 3、棧頂指針，指向新malloc 的節點 // 4、 void push(PSTACK PS, int val) {PNODE pNew = (PNODE) malloc(sizeof(NODE));pNew -> pdata = val;// 新申請的節點的指針域指向上一個節點，也就是 pTop 指向的節點pNew -> pNext = PS->pTop; // 棧頂指針，指向新malloc 的節點PS->pTop = pNew; }

（3）traverse

// 1、先輸出 88 // 思考： // 1、我們不能改變棧頂指針，和棧底指針 // 2、所以我們定義一個臨時的指針p ，指向棧頂元素 // 3、p 指針一個一個向下移動 // 4、p == pBottom 的時候，遍歷完成 void traverse(PSTACK PS) {PSTACK p = PS->pTop;while(p != PS->pBottom){printf("%d ",p->data);p = p->pNext;} return ; }

（4）pop

// 1、保存棧頂節點的地址，然后釋放 // 2、pTop 向下移動 // 3、將下一個節點的指針域，指向NULLbool pop(PSTACK PS,int *val) { //棧為空if(PS -> pTop == PS -> pBottom){return false;} // 1、保存棧頂節點的地址，然后釋放PNODE p = PS ->pTop;*val = p -> data;free(p); // 2、pTop 向下移動PS ->pTop = PS ->pTop -> pNext; // 將下一個節點的指針域，指向NULLPS ->pTop -> pNext = NULL; }

（5）clear

// 將棧中元素清零，然后節點還在 // 遍歷一次，然后清除元素 void clear(PSTACK PS) {if (empty(PS)) // 如果為空棧 {return ; }PSTACK p = PS->pTop;while(p != PS->pBottom){p->data = 0；p = p->pNext;} return ; }// 將棧當中的節點釋放 // 遍歷一次元素，將其釋放 // 但是棧頂指針，和棧底指針都必須留下，留下框架 void clear(PSTACK PS) {if (empty(PS)) // 如果為空棧{return ;}else{PNODE p = PS->pTop;PNODE q = NULL;while(p != PS->pBottom) {q = p->pNext;free(p);p=q;}}return ; }

（3）棧的應用

1、函數的調用

int f () {int a,b = 0;g(&a;&b);printf("hello world\n"); }

分析：在 f() 函數當中調用g() 函數的時候，參與棧的使用。

將指令 printf("hello world\n"); 的地址壓入棧
將參數所用的局部變量 int a,b = 0; 也壓棧

2、中斷

3、表達式求值

4、內存分配
5、緩沖處理
6、迷宮

4、線性結構的應用—— 隊列

（1）序言

棧：我們講的是動態隊列，（本質還是鏈表）

什么是隊列？
一種可以實現 “先進先出” 的存儲結構。

鏈表的分類？

鏈式隊列：本質是鏈表
靜態隊列：本質是數組

（2）靜態隊列的分析：

1、靜態隊列為什么必須是循環隊列？
2、循環隊列，需要幾個參數來確定？
3、循環隊列，各個參數的含義？
4、循環隊列，入隊偽算法講解
5、循環隊列，出隊偽算法講解
6、如何判斷循環隊列為空？
7、如何判斷循環隊列為滿？

1、靜態隊列為什么必須是循環隊列？

分析：

rear：用來添加元素的指針（向上移動）
front：用來刪除元素的指針（向上移動）

發現一個問題：指針都是向上移動，內存總有一天會崩潰。（而且使用數組的時候，數組的大小是固定的）

解決辦法：循環隊列

2、循環隊列，需要幾個參數來確定？

• 需要兩個參數：front 指針和 rear 指針。

3、循環隊列，各個參數的含義？

• 2個參數不同的場合有著不同的含義
  

（1）隊列初始化：front 和 rear 的值都是零。

（2）隊列空時：front 和 rear 的值相等，但不一定是零。

（3）隊列為空：front代表第一個元素，rear代表最后一個元素的下一個元素。

4、循環隊列，入隊偽算法講解

入隊：在隊尾加入
出隊：在隊頭彈出

5、循環隊列，出隊偽算法講解

6、如何判斷循環隊列為空？

如果，front 和 rear 的值相等，則該隊列就一定為空。

7、如何判斷循環隊列已滿？

1、可以發現，f 和 r 的值可以是任意值。

2、可以看出當我們隊列已經滿了的時候，指針 p 和 指針 r 是相等的，所以和我們的，隊列已空發生了沖突。

解決辦法：

1、少使用一個元素
則：當 指針p 和 指針r 互相臨近，則隊列已經滿了。
因為：f 和 r 的值可以是任意值，所以當 r = 4 的時候，f 可以變為 f = 3，f = 5。（其中有一種情況是隊列只有一個元素）
但是，入隊的時候是，r + 1，所以說當 (r+1) % 數組的長度 == f 的時候，隊列就是滿的，另外一種情況排除。

2、添加一個元素
原理和少用一個元素是相同的

（3）循環隊列程序演示

#include <stdio.h>typedef struct queue {int *pBase; // 數組的基地址int front; // 作為數組元素的下標int rear; }QUEUE,*QUEUE;int main(void) {QUEUE Q;init(&Q);return 0; }

（1）init

//目的： //1、創建一個數組 //2、下標進行初始化void init(QUEUE *pQ) { // 6 個元素大小pQ -> pBase = (int*)malloc(sizeof(int)*6 );pQ -> front = 0;pQ -> rear = 0; }

（2）en_queue

注意：判斷是否已滿：就為少用一個元素，創造了條件。

// 入隊：如果隊列不滿 // 1、將值放在 r 當前的位置 // 2、將 r 移動到下一個位置bool en_queue(QUEUE *pQ , int val) {if( full_queue(pQ) ){return false;}else {// 1、將值放在 r 當前的位置pQ->pBase[pQ->rear] = val;// 2、將 r 移動到下一個位置pQ->rear = (pQ->rear+1) % 6;} }

（3）full_queue

bool full_queue(QUEUE *pQ) {// 回顧偽算法if( (pQ->rear + 1)%6 == pQ->front )return true;elsereturn false; }

（4）traverse_queue

void traverse_queue(QUEUE *pQ) {int i = pQ -> front;// i != pQ->rear 時候，有東西要輸出while(i != pQ->rear){printf("%d ",pQ->pBase[i]);i = (i+1) % 6; // 開始循環} }

（5）out_queue

// 出隊：刪除一個元素 // 1、先將值進行輸出 // 2、指針 f 向上移動 bool out_queue(QUEUE *pQ , int *val) {if( empty_queue() )return false;else{// 1、先將值進行輸出*pVal = pQ->pBase[pQ->front];// 2、指針 f 向上移動pQ->front = (pQ->front + 1) %6;} }

（6）empty_queue

bool empty_queue( QUEUE *pQ ) {if(pQ->rear == pQ->front )return true;elsereturn false; }

（4）隊列的具體的應用

1、所以和時間有關的操作，都與隊列相關。

比如：任務，先進先執行。

遞歸專題

1、前景知識

遞歸定義：不同函數之間的，相互調用。

#include <stdio.h>void f(); void g(); void k();void f() {printf("FFFF\n");g();printf("1111\n"); } void g() {printf("GGGG\n");k();printf("2222\n"); } void k() {printf("KKKK\n"); }int main(void) {f();return 0; }

自己調用自己

1、死遞歸：不知道什么停止調用自己
2、遞歸：一定要知道，自己什么時候停止調用自己。

#include <stdio.h> // 死遞歸 void f() {printf("1111\n"); }int main(void) {f();return 0; }// 不是死遞歸 void f(int n) {if(n==1)printf("1111\n");elsef(n-1); }int main(void) {f();return 0; }

2、應用舉例

（1）求階乘

n! = n x (n-1)!

（1）使用循環來實現

#include <stdio.h>int main(void) {int val;int i=0;int mul = 1;printf("請輸入一個數字：val = ");scanf("%d ",&val);for(i=1, i<=val; i++){mul = i * mul;}printf("%d 的階乘是 %d\n", val, mul);return 0; }

（2）使用遞歸來實現

#include <stdio.h>// 1、出入一個數 // 2、返回這個數的階乘 long f(long val) {// f(1) 肯定可以實現if(1==n) return 1;// f(n) 要借助 f(n-1) 來實現elsereturn f(n-1) * n; }int main(void) {printf("%d \n",f(5));return 0; }

遞歸的思想：
規模很大的問題的解決，是借助于規模很小問題解決，當最后規模最小的問題，不需要再借助其他解決辦法的時候，再倒推回來。

求：100！ -> 99! ->98! …-> … …-> 1!
所以，先求 1！，然后再反推。

1、n 規模問題的解決，可以借助 (n-1) 規模問題的解決而解決。
舉例：求 100！，我們知道 99！，就可以輕易的得到 100！

（2）求 1+2+3+4+…+100

//long f(long n) { // 規模最小的時候 n==1if(1==n)return 1; // 剩下的規模，需要借助 n-1 的規模來解決 elsereturn f(n-1) + n; }int main(void) {printf("%d \n",f(5));return 0; }

3、對遞歸的理解

定義：一個函數，直接或者間接，調用自己。

（1）函數調用：

當在一個函數的運行期間調用另一個函數時，在運行被調函數之前，系統需要完成三件事：

1、將所有的實際參數、返回地址等信息傳遞給被調函數保存。
返回地址：下一條語句的地址

2、為被調函數的局部變量（也包括行參）分配存儲空間。

3、將控制轉移到被調函數的入口。

從被調函數返回函數之前，系統也要完成三件事：

保存被調函數的返回結果。
保存 return 的值

釋放被調函數所占的存儲空間。

依照被調函數保存的返回地址將控制轉移到調用函數。

舉例1：

#include <stdio.h>int f(int n) {int i,j;n = n+2;return n; } // f 返回函數，需要做的事情 1、保存 n 的值 2、釋放所有形參、局部變量， 3、根據保存地址，返回主調函數int main(void) {int val;val = f(5);printf("val = %d\n",val);return 0; }// 在 main 函數當中調用 f() 函數 1、將實參 5 ，下一個語句地址 printf 的地址， 2、為形參 n 分配空間 3、控制權限轉移

A函數調用A函數，和A函數調用B函數，在計算機看來是沒有任何區別的，只不過用我們日常的思維方式理解比較怪異而已！

（2）函數調用，棧的使用

當有多個函數相互調用時，按照”后調用先返回“的原則，上述函數之間信息傳遞和控制轉移必須借助”棧“來實現。

即系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時，就在棧頂分配一個存儲區，進行壓棧操作，每當一個函數退出時，就釋放它的存儲區，就做出棧操作，當前運行的函數永遠都在棧頂位置。

（3）遞歸調用，必須滿足的3個條件

• 遞歸必須得有一個明確的中止條件

• 該函數所處理的數據規模必須在遞減（遞歸的值，可以遞增）

// 值在減小、規模也在減小 int f(int n) {if(n<3)printf("結束\n")； // 遞歸結束elsen = f(n-1); // 在此遞歸 return n; }// 值在增大、規模卻在減小 int f(int n) {if(n>7)printf("結束\n")； // 遞歸結束elsen = f(n+1); // 在此遞歸 return n; }

• 這個轉化必須是可解的

（4）循環的遞歸的關系

（1）理論上講，所有的循環都可以轉化為遞歸。但是用遞歸能解決的問題，不一定用循環可以解決。

（2）遞歸和循環的特點

遞歸：易于理解、速度比較慢、占用存儲空間大
優點：易于理解
缺點：調用函數，有很大的開銷。

循環：不易理解、速度比較快、占用存儲空間比較小

（5）漢諾塔

如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面。
求移動的步驟和移動的次數

解：

（1）n == 1
第1次 1號盤 A---->C sum = 1 次

(2) n == 2
第1次 1號盤 A---->B
第2次 2號盤 A---->C
第3次 1號盤 B---->C sum = 3 次

（3）n == 3
第1次 1號盤 A---->C
第2次 2號盤 A---->B
第3次 1號盤 C---->B
第4次 3號盤 A---->C
第5次 1號盤 B---->A
第6次 2號盤 B---->C
第7次 1號盤 A---->C sum = 7 次

n=1； 1次
n=2； 3次
n=3； 7次
總結：一共是 2 的 n次方，減一。

// 當用戶輸入盤子個數的時候，我們就假設 A 上有n個盤子，并且從小到大排列好了void hannuota(int n, char A, char B, char C) {如果是一個盤子，直接將 A 柱子上的盤子移動到 C柱子上面否則先將 A 柱子上的 n-1 個盤子借助 C 移動到B上面直接將 A 柱子上的第 n 個盤子移動到上C上面最后將 B 柱子上面的n-1個盤子借助 A 移動到 C 上 }// n：代表要移動盤子的總數 // A：代表準備要移動的柱子，（不一定是 A ，有可能是 B） // B：代表移動過程中借助的柱子（不一定是 B，有可能是 A） // C：代表要接收的盤子的柱子，（也不一定是C）void hannuota(int n, char A, char B, char C) {if(1==n){printf("將編號為 n 的柱子，直接從 %c 柱子，移動到 %c的柱子上面\n",n,A,C);}else{//將 A 上面的 n-1 個盤子，借助 C 移動到 B 上面.hannuota(n-1,A,C,B);//將編號為 n 的盤子，移動到 C 上面printf("將編號為 n 的柱子，直接從 %c 柱子，移動到 %c的柱子上面\n",n,A,C);//hannuota(n-1,B,A,C); } }

總結：其實從宏觀上來說，只需要 3 步（只是其中兩步比較復雜）

1、A上的 n-1 個移動到 B 上 （比較復雜）
這個原理和（將 n 個圓盤從 A 移動到 C 是一樣的）

2、A上的第 n 個移動到 C 上

3、B 上的 n-1 個移動到 C 上（比較復雜）
這個原理和（將 n 個圓盤從 A 移動到 C 是一樣的）

就像將大象放到冰箱里，也需要3步，第二步，將大象放到冰箱比較復雜，但是打開冰箱，和關閉冰箱比較容易。

4、遞歸的應用

1、樹和森林，就是以遞歸的方式來定義的。
2、樹和圖，很多算法就是以遞歸來實現的。
3、很多數學公式，就是以遞歸的方式來定義的。

斐波那契數列：1、2、3、5、8、13、21、34
每個數都是前兩項相加。

總結

以上是生活随笔為你收集整理的郝斌——数据结构笔记（数组、链表、栈、队列）（递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。