Part 1.梳理數據結構重點
一.宏
? ? ? ? 1.簡單宏
? ? ? ? ? ? ? ? a. #define 宏名 宏體
? ? ? ? ? ? ? ? b. #if 宏(#ifndef)
? ? ? ? ? ? ? ? c.#endif
? ? ? ? 2.多語句宏
? ? ? ? ? ? ? ? a. define 宏函數名(參數1，參數2......)({C語句1，C語句2......})
? ? ? ? ? ? ? ? b. define 宏函數名(參數1，參數2......)do(C語句1，C語句2......)while(0)
二.頭文件的引用
? ? ? ? 1.#include<頭文件>
????????2.#include"頭文件"
? ? ? ? 3.二者區別
1:頭文件是直接訪問系統頭文件庫繼續尋找頭文件
2:頭文件的尋找是先在本目錄下尋找有沒有適配的頭文件，再去系統頭文件庫尋找。
三.typedef
? ? ? ? 1.意義：將類型重定義(起別名)
? ? ? ? 2.用法：typedef int myint（可以用myint來使用int）
? ? ? ? ? ? ? ? ? ? ? #define myint int//將int替換為myint
? ? ? ? 3.define和typedef的區別
1.define是在預處理階段處理的文件，typedef得編譯才能運行。
2.define只是替換，而typedef是起別名
3.define只能做基本類型的替換，而typedef可以做復雜類型的起別名
四.解構類型
? ? ? ? 1.邏輯結構
? ? ? ? ? ? ? ? a.線性結構（順序表，鏈表）
? ? ? ? ? ? ? ? b.樹形結構（二叉樹）
? ? ? ? ? ? ? ? c.圖形結構
? ? ? ? ? ? ? ? d.集合結構
? ? ? ? 2.存儲結構
? ? ? ? ? ? ? ? a.順序存儲（順序表）
? ? ? ? ? ? ? ? b.鏈式存儲（鏈表）
? ? ? ? ? ? ? ? c.索引存儲（哈希表）
? ? ? ? ? ? ? ? d.散列存儲
五.順序表
? ? ? ? 1.定義
? ? ? ? ? ? ? ? a.邏輯
需要定義一個連續的結構體空間，data數組用來存儲數據，len記錄長度，相當于在普通節點數據域插入一個數組用來存儲。
? ? ? ? ? ? ? ? ? b.代碼
typedef struct sqlist
{int data[你需要的數據個數];//普通節點數據int len；//長度節點
}*sqlist;sqlist list = (sqlist)malloc(sizeof(struct sqlist));//申請堆區空間? ? ? ? 2.插入
? ? ? ? ? ? ? ? a.邏輯
判斷結構滿了沒有，沒有則可以在list->len位置插入數據（尾插邏輯）
頭插需要先將每一位數據后移一位for循環從len到1進行反向后移一位，在0的位置進行插入（頭插邏輯）
? ? ? ? ? ? ? ? b.代碼（尾插）
void insert (sqlist list,int element)
{if(list == NULL, list->len == maxsize)//沒有鏈表或者鏈表滿了不能插入return；list->data[list->len] = element;//在最后一位插入list->len++;
}? ? ? ? 3.刪除
? ? ? ? ? ? ? ? a.邏輯
直接len--就行，因為數據不用清除，循環遍歷只從0到len-1（尾刪邏輯）
刪除第一位，并從1開始到len-1位，循環前移（頭刪邏輯）
? ? ? ? ? ? ? ? b.代碼（尾刪）
int delete_rear(sqlist list)
{if(NULL == list || list->len == 0){ printf("順序表為空\n");return Faluse;}list->len--;return Success;
}六.鏈表
? ? ? ? 1.單向鏈表
? ? ? ? ? ? ? ? a.初始化
需要一個節點包含數據域和指針域，指針用來指向下一個，數據域又分頭節點和普通節點，所以需要共用體。
typedef struct Node
{//結構體嵌套共用體union{//普通節點數據域datatype data;//頭結點數據域：鏈表長度int len;};//指針域struct Node *next;
}*linklist;linklist create_node(int flag)
{linklist s = (linklist)malloc(sizeof(struct Node));if(NULL == s){return NULL;}if(flag == 1)//頭節點s->len = 0;else if(flag == 0)//普通節點s->data = 0;s->next = NULL;return s;
}????????2.單向循環鏈表
? ? ? ? 3.雙向鏈表
? ? ? ? 4.雙向循環鏈表
七.順序表和鏈表的區別
1.順序表是連續存儲的空間，而鏈表是分開的空間
2.順序表是固定的空間，定義好了就不能改變，鏈表是可以增加空間的。
八.棧
1.棧是先進后出的順序，進入abc，出來就是cba；也可以進a出a，進b出b，進c出c；出棧的順序很多。
2.棧也是需要定義maxsize的，棧滿條件就是top == maxsize-1
3.棧的top開始指向的是-1，插入一個數據+1，
4.棧的數據從0開始到 maxsize-1
5.出棧順序的個數（卡特蘭數）：1/n+1（2n n）? ? ? ? ?（n m） = n!/m!(n-m)!
九.隊列
1.隊列是先進先出的一個線性結構，會定義兩個指針front和rear指向0，當插入一個數據時，rear++，當刪除一個數據時front++，所以隊列只能先進先出，當隊列已經插入最大值的數據了，并且將所有數據都刪除了，此時front == rear == maxsize，此時就會產生假溢出
2.將隊列定義成循環隊列，即最后走完不指向NULL，指向頭，再人工空出一個節點方便循環，就可以解決假溢出問題
3.循環鏈表的隊滿條件：front == (rear+1)%maxsize
4.隊列空條件:front == rear
5.插入邏輯：data[rear] = element; rear = (rear+1)%maxsize
6.刪除邏輯：front = (front+1)%maxsize
7.計算長度：len = (maxsize+rear-front)%maxsize
十.哈希表
1.哈希算法：得出m（m為原數組長度的4/3），再得出m的最大質數p，然后原數組位置除以p，得到哈希算法后的位置、
2.哈希列表：因為哈希算法后可能有些數會位置相同，所以創建鏈表就行存儲
十一.排序
? ? ? ? 1.插入排序
將數組第一個設為有序數列，后面為無序數列，每次循環都將無序數列的的第一個值給他按大小排到有序數列里。
void insert_sort(int *p,int len)
{int j;for(int i = 1; i < len; i++){int temp = p[i];//記錄無序數組第一個for(j = i-1;j > 0; j++)//從有序數組最后一個開始循環比較{if(p[j] > temp)//由于是升序，每找到一個比要插入大的數，就將這個數循環后移p[j+1] = p[j]//后移elsebreak;}p[j+1] = temp;//將要插入數插入到空的有序數列中}
}? ? ? ? 2.快速排序
將第一個元素設為基準值，每次循環把大于基準值的放基準值右邊，把小于基準值的放左邊（升序），即完成了一個數的排序，然后利用遞歸算法循環調用自己則完成排序。
int once_sort(int *p,int low,int high)
{int key = p[low];while(low < high){while(p[high] >= key && low < high)//右循環找右邊比key小的數，沒有左移{high--;}p[low] = p[high];while(p[low] >= key && low < high)//左循環找左邊比key大的數，沒有右移{low++;}p[high] = p[low];}
}void quick_sort(int *p,int low,int high)
{int mid = once_sort(p,low,high);//一輪比較quick_sort(p,low,mid-1);//遞歸完成左部分排序quick_sort(p,mid+1,high);//遞歸完成右部分排序
} 
)
)
