前段時間完整的看完了一部上了年紀的數據結構視頻,完整的做了筆記。 其次,推薦一個便宜的雲主機,感覺比阿裡便宜,新用戶一年68元,開發測試很舒服滴滴雲附上活動鏈接:https://i.didiyun.com/2d7Jy4Nzle8 語言環境是C語言 (1)數據結構基礎 一、線性結構 連續存儲[數組] ...
前段時間完整的看完了一部上了年紀的數據結構視頻,完整的做了筆記。
語言環境是C語言
(1)數據結構基礎
一、線性結構 連續存儲[數組] 離散存儲[鏈表] 線性結構的兩種常見應用之一 棧 線性結構的兩種常見應用之二 隊列 專題:遞歸 1、1+2+3+。。。100的和 2、求階乘 3、漢諾塔 4、走迷宮 二、非線性結構 樹 圖 三、查找和排序 折半查找 排序: 冒泡 插入 選擇 快速排序 歸併排序 數據結構概念:我們如何把顯示中大量而複雜的問題以特定的數據類型和特定的存儲結構保存到主存儲器(記憶體)中,以及在此基礎上為實現某個功能(比如查找某個元素,刪除某個元素,對所有元素進行排序)而執行的相應操作,這個相應操作也叫演算法 數據結構 = 個體 + 個體的關係 演算法 = 對存儲數據的操作 演算法:解題的方法和步驟 1、時間複雜度 大概程式要執行的次數,而非執行的時間 2、空間複雜度 演算法執行過程中大概所占用的最大記憶體 3、難易程度 4、健壯性 俠義的演算法是與數據的存儲方式密切相關 廣義的演算法是與數據的存儲方式無關 泛型: 利用某種技術達到的效果就是:不同的存儲方式,執行的操作是一樣的 數據結構的地位:數據結構是軟體中最核心的課程(2)數組
1、什麼叫數組 數據類型相同,大小相等 優點:存儲速度快 缺點:插入刪除很慢 自定義輸出化數組函數#include <stdio.h> #include <stdlib.h> struct Arr{ int* pBase; int len; int cnt; }; void int_arr(struct Arr* newarr,int length); void show_arr(struct Arr* newarr); void sort_arr(struct Arr* newarr); _Bool is_empty(struct Arr* newarr); _Bool is_full(struct Arr* newarr); _Bool append_arr(struct Arr* newarr,int val); _Bool insert_arr(struct Arr* newarr,int pos,int val); int main(void){ struct Arr newarr; int_arr(&newarr,6); show_arr(&newarr); append_arr(&newarr,1); insert_arr(&newarr,2,9); insert_arr(&newarr,2,-2); insert_arr(&newarr,2,2); insert_arr(&newarr,2,6); insert_arr(&newarr,2,20); insert_arr(&newarr,2,8); show_arr(&newarr); sort_arr(&newarr); show_arr(&newarr); return 0; } void int_arr(struct Arr* newarr,int length){ newarr->pBase = (int*)malloc(sizeof(int)*length); if(newarr->pBase == NULL){ printf("malloc fail"); exit(-1); }else{ newarr->len = length; newarr->cnt = 0; } return; } _Bool is_empty(struct Arr* newarr){ if(newarr->cnt == 0){ return 1; }else{ return 0; } } _Bool is_full(struct Arr* newarr){ if(newarr->len == newarr->cnt){ return 1; }else{ return 0; } } void show_arr(struct Arr* newarr){ if(is_empty(newarr)){ printf("array is empty"); }else{ for(int i = 0;i<newarr->cnt;i++){ printf("%d ",newarr->pBase[i]); } printf("\n"); } } _Bool append_arr(struct Arr* newarr,int val){ if(is_full(newarr)){ return 0; }else{ newarr->pBase[newarr->cnt] = val; (newarr->cnt)++; return 1; } } _Bool insert_arr(struct Arr* newarr,int pos,int val){ if(is_full(newarr)){ return 0; }else{ for(int i = newarr->cnt;i>=pos;i--){ newarr->pBase[i] = newarr->pBase[i-1]; } newarr->pBase[pos-1] = val; (newarr->len)++; (newarr->cnt)++; return 1; } } void sort_arr(struct Arr* newarr){ for(int i=0;i<=newarr->cnt;i++){ for(int j=i+1;j<newarr->cnt;j++){ if(newarr->pBase[i]>newarr->pBase[j]){ int x; x = newarr->pBase[j]; newarr->pBase[j] = newarr->pBase[i]; newarr->pBase[i] = x; } } } }View Code
(3)離散存儲
1、定義: N個節點離散分配 彼此通過指針相連 每個節點只有一個前驅節點,每個節點只有一個後續節點 首節點沒有前驅節點,尾節點沒有後續節點 優點:空間沒有限制、插入刪除速度快 缺點:存儲速度很慢 專業術語: 首節點 尾節點 頭節點:沒有有效數據,在首節點前面,方便操作鏈表 頭指針:頭節點指針 尾指針:尾節點指針 確定一個鏈表需要幾個參數,比如數組需要指針+總長度+當前長度: (頭指針)typedef struct Node{ int data; //數據域分類: 單鏈表 雙鏈表:每個節點有2個指針域 迴圈鏈表:能通過任何一個節點找到其他所有的節點,能繞回去 非迴圈鏈表 演算法: 遍歷 查找 清空 銷毀 求長度 排序 (4)鏈表
struct Node* pNext; //指針域
}* LbZZ,Lb;
#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <stdbool.h> typedef struct NODE{ int data; struct NODE* pNext; }* pNode,Node; pNode init_list(void); void show_list(pNode pHead); int len_list(pNode pHead); void sort_list(pNode pHead); void insert_list(pNode pHead,int pos,int val); bool delete_list(pNode pHead,int del_pos,int *del_val); int main(void){ pNode pHead = init_list(); show_list(pHead); int length = len_list(pHead); sort_list(pHead); show_list(pHead); printf("where start inert\n"); int pos,val; scanf("%d",&pos); printf("inert value is ?\n"); scanf("%d",&val); insert_list(pHead,pos,val); show_list(pHead); int del_pos,del_val; printf("whitch is delete\n"); scanf("%d",&del_pos); delete_list(pHead,del_pos,&del_val); show_list(pHead); return 0; } pNode init_list(void){ int len; int value; pNode pHead = (pNode)malloc(sizeof(Node)); printf("input your length\n"); scanf("%d",&len); pHead->pNext = NULL; pNode pTail = pHead; for(int i=0;i<len;i++){ printf("please input num %d\n",i+1); scanf("%d",&value); pNode pNew = (pNode)malloc(sizeof(Node)); pNew->data = value; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; } return pHead; } void show_list(pNode pHead){ pNode p = pHead; while(p->pNext != NULL){ p = p->pNext; printf("%d ",p->data); } printf("\n"); return; } int len_list(pNode pHead){ pNode p = pHead; int i = 0; while(p->pNext != NULL){ i++; p = p->pNext; } return i; } void sort_list(pNode pHead){ pNode p,q; int value,i,j; int len = len_list(pHead); for(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){ value = p->data; p->data = q->data; q->data = value; } } } return; } void insert_list(pNode pHead,int pos,int val){ int i=0; pNode p = pHead; while(i<pos && p!= NULL){ p = p->pNext; i++; } if(i>pos || p==NULL){ printf("insert fail"); } pNode pNew = (pNode)malloc(sizeof(Node)); pNew->data = val; pNode q = p->pNext; p->pNext = pNew; pNew->pNext = q; } bool delete_list(pNode pHead,int del_pos,int *del_val){ int i = 0; pNode p = pHead; while(i<del_pos && p!= NULL){ p = p->pNext; i++; } if(i>del_pos || p==NULL){ printf("del fail"); } pNode q = p->pNext; *del_val = q->data; if(p->pNext == NULL){ p->pNext == NULL; }else{ p->pNext = p->pNext->pNext; } free(q); q=NULL; return true; };View Code
(5)棧
#include <stdio.h> #include <malloc.h> typedef struct NODE{ int data; struct NODE* pNext; }Node,*pNode; typedef struct STACK{ pNode pTop; pNode pBottom; }Stack,*pStack; void initStack(pStack pS); void pushStack(pStack pS,int val); void showStack(pStack pS); void popStack(pStack pS); int main(void){ Stack S; initStack(&S); pushStack(&S,23); pushStack(&S,45); pushStack(&S,56); showStack(&S); popStack(&S); showStack(&S); return 0; } void initStack(pStack pS){ pS->pTop = (pNode)malloc(sizeof(Node)); pS->pBottom = pS->pTop; pS->pTop->pNext = NULL; } void pushStack(pStack pS,int val){ pNode pNew = (pNode)malloc(sizeof(Node)); pNew->pNext = pS->pTop; pNew->data = val; pS->pTop = pNew; } void showStack(pStack pS){ pNode p = pS->pTop; while(p != pS->pBottom){ printf("%d ",p->data); p = p->pNext; } printf("\n"); return; } void popStack(pStack pS){ pNode p = pS->pTop; pS->pTop = p->pNext; free(p); p = NULL; }View Code
(6)隊列
定義:一種可以實現“先進先出”的存儲結構 分類: 鏈式隊列:用鏈表實現的 靜態隊列:用數組實現的 靜態隊列通常都必須是迴圈隊列 迴圈隊列的講解: 1.靜態隊列為什麼必須是迴圈隊列 因為數組加數據的時候會溢出,指針在尾部需要迴圈調到首部開始覆蓋數據 2.迴圈隊列需要幾個參數來確定 2個參數(front,rear) 3.迴圈隊列各個參數的含義(寫入的時候val寫到r的位置,然後r+1) 1、隊列初始化:front和rear的值都是零 2、隊列非空:front代表的是隊列的第一個元素。rear代表的是隊列的最後一個有效元素的下一個元素 3、隊列空:front和rear的值相等 4.迴圈隊列入隊偽演算法講解 1、將值存入r所代表的位置 2、錯誤的寫法:r=r+1 正確的寫法:r=(r+1)%數組的長度 5.迴圈隊列出隊偽演算法講解 r=(r+1)%數組的長度 6.如何判斷迴圈隊列是否為空 front != rear 7.如何判斷迴圈隊列是否已滿,因為空和滿,r都=f 兩種方式: 1、多增加一個標識參數 2、少用一個元素(一般用這種)。如果rf緊挨著就是已滿,【if(r+1)%數組長度==f】已滿 使用場景: 所有和時間有關的操作都與隊列有關#include <stdio.h> #include <stdbool.h> #include <malloc.h> typedef struct Queue { int* pBase; int front; int rear; }QUEUE; void init(QUEUE* pQ); bool inert(QUEUE* pQ,int val); void show(QUEUE* pQ); bool is_full(QUEUE* pQ); bool out(QUEUE* pQ); int main(void){ QUEUE Q; init(&Q); inert(&Q,12); inert(&Q,23); inert(&Q,34); inert(&Q,45); inert(&Q,56); inert(&Q,67); inert(&Q,78); inert(&Q,89); show(&Q); out(&Q); show(&Q); return 0; } void init(QUEUE* pQ){ pQ->pBase = (int*)malloc(sizeof(int)*6); pQ->front = 0; pQ->rear = 0; } bool is_full(QUEUE* pQ){ if((pQ->rear+1)%6 == pQ->front){ return true; }else return false; } bool inert(QUEUE* pQ,int val){ if(is_full(pQ)){ return false; }else{ pQ->pBase[pQ->rear] = val; pQ->rear = (pQ->rear+1) % 6; return true; } } void show(QUEUE* pQ){ int i = pQ->front; while( i != pQ->rear){ printf("%d ",pQ->pBase[i]); i = (i+1)%6; } printf("\n"); return; } bool out(QUEUE* pQ){ pQ->front = (pQ->front+1) % 6; }View Code
(7)遞歸
定義:一個函數直接或間接自己掉用自己 遞歸滿足三個條件: 1、遞歸必須得有一個明確的中止條件 2、該函數所處理的數據規模必須在遞減 3、這個轉化必須是可解的 迴圈和遞歸的關係,所有的迴圈都可以用遞歸還實現,但是遞歸不一定能用迴圈實現 遞歸的應用: 樹和森林就是以遞歸的方式定義的 數和圖的很多演算法都是以遞歸來實現的 很多數據公式就是以遞歸的方式定義的 階乘:#include <stdio.h> int f(int n); int main(void){ printf("%d",f(3)); return 0; } int f(int n){ if(n == 1){ return 1; }else{ return f(n-1)*n; } }View Code
漢諾塔偽演算法:
if(n>1){ 先把A柱子上的前n-1個盤子從A藉助C移到B 將A柱子上的第n個盤子直接移到C 再將B柱子上的n-1個盤子藉助A移到C } #include <stdio.h> void hannuota(int n,char A,char B,char C); int main(void){ char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n=5; hannuota(n,ch1,ch2,ch3); return 0; } void hannuota(int n,char A,char B,char C){ if(n == 1){ printf("將編號為%d的盤子直接從%c移到%c\n",n,A,C); }else{ hannuota(n-1,A,C,B); printf("將編號為%d的盤子直接從%c移到%c\n",n,A,C); hannuota(n-1,B,A,C); } }View Code
(8)樹
樹的定義: 專業定義: 1、有且只有一個稱為根的節點 2、有若幹個互不相交的子樹,這些子樹本身也是一棵樹 通俗定義: 1、樹是由節點和邊組成 2、每個節點z只有一個父節點但可以有多個子節點 3、但有一個節點例外,該節點沒有父節點,那就是根節點 深度: 從根節點到最底層節點的層數稱為深度 根節點是第一層 葉子節點: 沒有子節點的節點 非終端節點: 實際就是非葉子節點 度: 子節點的個數稱為度 樹的分類: 一般樹:任意一個節點的子節點的個數b不受限制 二叉樹:任意一個節點的子節點個數最多兩個,且子節點的位置不可更改 分類: 一般二叉樹 滿二叉樹:每一層節點數都是最大的,不能再加了 完全二叉樹:只是刪除了滿二叉樹最底層最右邊的連續若幹個節點(上層的都必須要滿) 如果二叉樹中除去最後一層節點為滿二叉樹,且最後一層的結點依次從左到右分佈,則此二叉樹被稱為完全二叉樹。滿二叉樹一定是完全二叉樹 森林:n個互不相交的樹,整體上稱為森林 樹的存儲: 二叉樹的存儲:非線性,所以必須存儲完全二叉樹,不能只存有效節點 連續存儲【完全二叉樹】: 優點:查找某個節點的父節點和子節點(也包括查找有沒有子節點)速度很快 缺點:耗用的記憶體空間過大 一般樹的存儲: 雙親表示法:父的下標是誰,沒有就寫-1,求父節點方便 孩子表示法:求子節點方便 雙親孩子表示法:求父節點和子節點都方便 二叉樹表示法:把一個普通樹轉成二叉樹來存儲 具體轉換方法: 設法保證任意一個節點的左指針域指向它的第一個孩子,右指針域指向它的兄弟 一個普通樹轉化的二叉樹,在開頭一定沒有右子樹 森林的存儲 把森林轉換成二叉樹,不同的樹可以當作兄弟 操作: 遍歷 先序遍歷 1、先訪問根節點 2、再先序訪問左子樹 3、再先序訪問右子樹 中序遍歷 1、中序遍歷左子樹 2、再訪問根節點 3、再中序遍歷右子樹 後續遍歷 1、後序遍歷左子樹 2、後序遍歷右子樹 3、再訪問根節點 已知兩種遍歷序列求原始二叉樹:已知先中可以求得完整,已知中後可以求得完整,已知先後不可以求得完整 應用: 1、樹是資料庫中數據組織一種重要形式 2、操作系統進程樹 3、面向對象語言中類的繼承關係 4、赫夫曼樹 遍歷:#include <stdio.h> #include <malloc.h> typedef struct BTNPODE{ char data; struct BTNPODE* pRNode; struct BTNPODE* pLNode; }*pBTNode,BTNode; pBTNode inittree(void); void pretree(pBTNode); void intree(pBTNode); void posttree(pBTNode); int main(void){ pBTNode pT = inittree(); pretree(pT); printf("\n"); intree(pT); printf("\n"); posttree(pT); return 0; } void pretree(pBTNode pT){ if (pT != NULL){ printf("%c",pT->data); pretree(pT->pLNode); pretree(pT->pRNode); } } void intree(pBTNode pT){ if (pT != NULL){ intree(pT->pLNode); printf("%c",pT->data); intree(pT->pRNode); } } void posttree(pBTNode pT){ if (pT != NULL){ posttree(pT->pLNode); posttree(pT->pRNode); printf("%c",pT->data); } } pBTNode inittree(void){ pBTNode pA = (pBTNode)malloc(sizeof(BTNode)); pBTNode pB = (pBTNode)malloc(sizeof(BTNode)); pBTNode pC = (pBTNode)malloc(sizeof(BTNode)); pBTNode pD = (pBTNode)malloc(sizeof(BTNode)); pBTNode pE = (pBTNode)malloc(sizeof(BTNode)); pA->data = 'A'; pB->data = 'B'; pC->data = 'C'; pD->data = 'D'; pE->data = 'E'; pA->pLNode = pB; pA->pRNode = pC; pB->pLNode = pB->pRNode = NULL; pC->pLNode = pD; pC->pRNode = NULL; pD->pLNode = NULL; pD->pRNode = pE; pE->pLNode = pE->pRNode = NULL; return pA; }View Code
(8)排序
排序和查找的關係: 排序是查找的前提 排序是重點 分類: 冒泡 插入 選擇 快速排序 先把第一個值賦給val,然後比較兩邊,先從h開始移動 歸併排序 快速排序#include <stdio.h> int L[6] = {3,4,5,1,0,6}; void sortlist(int*,int,int); int FindPos(int*,int,int); int main(void){ sortlist(L,0,5); for(int i=0;i<6;i++) printf("%d ",L[i]); return 0; } void sortlist(int* L,int low,int high){ int pos; if (low < high){ //相等的時候不用排了 pos = FindPos(L,low,high); sortlist(L,low,pos-1); sortlist(L,pos+1,high); } } int FindPos(int* L,int low,int high){ int val = L[low]; while(low < high){ while(low<high && val<=L[high]){ high--; } L[low] = L[high]; while(low<high && L[low]<=val){ low++; } L[high] = L[low]; } L[low] = val; return low; }View Code