數(shù)據(jù)結(jié)構(gòu)算法背誦版

1、數(shù)據(jù)結(jié)構(gòu)算法背誦一、線性表1. 逆轉(zhuǎn)順序表中的所有元素，依算法思想： 第一個(gè)元素和最后一個(gè)元素對調(diào)， 第二個(gè)元素和倒數(shù)第二個(gè)元素對調(diào)， 此類推。void Reverse(int A, int n)int i, t;for (i=0; i < n/2; i+)t = Ai;Ai = An-i-1;An-i-1 = t;2. 刪除線性鏈表中數(shù)據(jù)域?yàn)閕tem 的所有結(jié)點(diǎn) 算法思想：先從鏈表的第2 個(gè)結(jié)點(diǎn)開始，從前往后依次判斷鏈表中的所有結(jié)點(diǎn)是否滿足條件，假設(shè)某個(gè) 結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閕tem，那么刪除該結(jié)點(diǎn)。最后再回過頭來判斷鏈表中的第1 個(gè)結(jié)點(diǎn)是否滿足條件，假設(shè) 滿足那么將其刪除。void Pur

2、geItem(LinkList &list)LinkList p, q = list;p = list->next;while (p != NULL)if (p->data = item) q->next = p->next;free(p);p = q->next; else q = p;p = p->next;if (list->data = item)q = list;list = list->next;free(q);3. 逆轉(zhuǎn)線性鏈表 void Reverse(LinkList &list)LinkList p, q, r

3、; p = list; q = NULL; while (p != NULL) r = q; q = p; p = p->next; q->next = r; list = q;4. 復(fù)制線性鏈表(遞歸)LinkList Copy(LinkList lista) LinkList listb;if (lista = NULL) return NULL; else listb = (LinkList)malloc(sizeof(LNode); listb->data = lista->data;listb->next = Copy(lista->next);

4、return listb;5. 將兩個(gè)按值有序排列的非空線性鏈表合并為一個(gè)按值有序的線性鏈表 LinkList MergeList(LinkList lista, LinkList listb)LinkList listc, p = lista, q = listb, r;/ listc 指向 lista 和 listb 所指結(jié)點(diǎn)中較小者if (lista->data <= listb->data) listc = lista;r = lista; p = lista->next; else listc = listb;r = listb; q = listb->

5、next; while (p != NULL && q != NULL)if (p->data <= q->data) r->next = p;r = p;p = p->next; else r->next = q;r = q;q = q->next;/ 將剩余結(jié)點(diǎn)(即未參加比擬的且已按升序排列的結(jié)點(diǎn))鏈接到整個(gè)鏈表后面 r->next = (p != NULL) ? p : q;return listc;二、樹1. 二叉樹的先序遍歷(非遞歸算法) 算法思想：假設(shè)p 所指結(jié)點(diǎn)不為空，那么訪問該結(jié)點(diǎn)，然后將該結(jié)點(diǎn)的地址入棧，然后再將

6、 p 指向其左孩 子結(jié)點(diǎn)；假設(shè),將p 所指向的結(jié)點(diǎn)為空，那么從堆棧中退出棧頂元素(某個(gè)結(jié)點(diǎn)的地址)p 指向其右孩子結(jié)點(diǎn)。重復(fù)上述過程，直到p = NULL 且堆棧為空，遍歷結(jié)束。#define MAX_STACK 50void PreOrderTraverse(BTree T)BTree STACKMAX_STACK, p = T;int top = -1;while (p != NULL | top != -1)while (p != NULL)VISIT(p);STACK+top = p;p = p->lchild;p = STACKtop-;p = p->rchild;2.

7、二叉樹的中序遍歷(非遞歸算法) 算法思想：假設(shè)p 所指結(jié)點(diǎn)不為空，那么將該結(jié)點(diǎn)的地址p 入棧，然后再將p 指向其左孩子結(jié)點(diǎn)；假設(shè)p所指向的結(jié)點(diǎn)為空，那么從堆棧中退出棧頂元素(某個(gè)結(jié)點(diǎn)的地址)送p,并訪問該結(jié)點(diǎn)，然后再將p指向該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。重復(fù)上述過程,直到p = NULL 且堆棧為空,遍歷結(jié)束。#define MAX_STACK 50void InOrderTraverse(BTree T)BTree STACKMAX_STACK, p = T;int top = -1;while (p != NULL | top != -1); while (p != NULL)STACK+top =

8、 p;p = p->lchild;p = STACKtop-;VISIT(p);p = p->rchild;3. 二叉樹的后序遍歷(非遞歸算法)算法思想：當(dāng)p 指向某一結(jié)點(diǎn)時(shí)，不能馬上對它進(jìn)行訪問，而要先訪問它的左子樹，因而要將此結(jié)點(diǎn) 的地址入棧；當(dāng)其左子樹訪問完畢后，再次搜索到該結(jié)點(diǎn)時(shí)(該結(jié)點(diǎn)地址通過退棧得到) ， 還不能對它進(jìn)行訪問，還需要先訪問它的右子樹， 所以，再一次將該結(jié)點(diǎn)的地址入棧。只有當(dāng)該結(jié)點(diǎn) 的右子樹訪問完畢后回到該結(jié)點(diǎn)時(shí)， 才能訪問該結(jié)點(diǎn)。 為了標(biāo)明某結(jié)點(diǎn)是否可以訪問， 引入一個(gè)標(biāo) 志變量flag，當(dāng)flag = 0 時(shí)表示該結(jié)點(diǎn)暫不訪問，flag = 1 時(shí)表示

9、該結(jié)點(diǎn)可以訪問。 flag 的值隨同該結(jié)點(diǎn)的地 址一起入棧和出棧。因此，算法中設(shè)置了兩個(gè)堆棧，其中 STACK1 存放結(jié)點(diǎn)的地址， STACK2 存放 標(biāo)志變量flag ，兩個(gè)堆棧使用同一棧頂指針top ，且top 的初始值為.1。#define MAX_STACK 50void PostOrderTraverse(BTree T)BTree STACK1MAX_STACK, p = T;int STACK2MAX_STACK, flag, top = -1;while (p != NULL | top != -1)while (p != NULL) STACK1+top = p;STACK2

10、top = 0;p = p->lchild;p = STACK1top;flag = STACK2top-;if (flag = 0) STACK1+top = p;STACK2top = 1;p = p->rchild; else VISIT(p);p = NULL;4. 二叉樹的按層次遍歷 算法思想：設(shè)置一個(gè)隊(duì)列，首先將根結(jié)點(diǎn)的地址入隊(duì)列，然后依次從隊(duì)列中退出一個(gè)元 素，每退出一個(gè)元素，先訪問該元素所指的結(jié)點(diǎn)，然后依次將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)假設(shè)存在的話 和右孩子結(jié)點(diǎn)假設(shè)存在的話入隊(duì)列。如此重復(fù)下去，直到隊(duì)列為空。#define MAX_QUEUE 50void LayeredOr

11、derTraverse(BTree T) BTree QUEUEMAX_QUEUE, p;int front, rear;if (T != NULL)QUEUE0 = T;front = -1;rear = 0;while (front < rear)p = QUEUE+front;VISIT(P);if (p->lchild != NULL) QUEUE+rear = p->lchild;if (p->rchild != NULL)QUEUE+rear = p->rchild;5. 建立二叉樹(從鍵盤輸入數(shù)據(jù)，先序遍歷遞歸算法)BTree CreateBT()c

12、har ch;BTree T; sacnf("%c", &ch); if (ch = ' ') return NULL; else T = (BTree)malloc(sizeof(BTNode);T->data = ch;T->lchild = CreateBT();T->rchild = CreateBT(); return T;6. 建立二叉樹(從數(shù)組獲取數(shù)據(jù))BTree CreateBT(int A, int i, int n)BTree p; if (i > n) return NULL;else p = (BTre

13、e)malloc(sizeof(BTNode); p->data = Ai;p->lchild = CreateBT(A, 2*i, n);p->rchild = CreateBT(A, 2*i+1, n); return p;T = CreateBT(A, 1, n);BTree CreateBT(int A, int n)int i;BTree *pT;/ 對應(yīng)n 個(gè)結(jié)點(diǎn)申請可容納n 個(gè)指針變量的內(nèi)存空間pT = (BTree *)malloc(sizeof(BTree)*n);/ 假設(shè)數(shù)組中的某個(gè)元素不等于零，那么申請相應(yīng)的結(jié)點(diǎn)空間并進(jìn)行賦值 for (i=1; i &

14、lt;= n; i+) if (Ai != 0) pTi = (BTree)malloc(sizeof(BTNode); pTi->data = Ai; else pTi = NULL;/ 修改結(jié)點(diǎn)的指針域的內(nèi)容，使父結(jié)點(diǎn)指向左、右孩子結(jié)點(diǎn) for (i=1; i <= n; i+)if (pTi != NULL)pTi->lchild = pT2*i; pTi->rchild = pT2*i+1;7. 求二叉樹的深度(遞歸算法)int Depth(BTree T)int ldepth, rdepth;if (T = NULL)return 0;else ldepth

15、= Depth(T->lchild);rdepth = Depth(T->rchild);if (ldepth > rdepth)return ldepth+1;elsereturn rdepth+1;8. 求二叉樹的深度(非遞歸算法)算法思想： 對二叉樹進(jìn)行遍歷， 遍歷過程中依次記錄各個(gè)結(jié)點(diǎn)所處的層次數(shù)以及當(dāng)前已經(jīng)訪 問過的結(jié)點(diǎn)所處的最大層次數(shù)。 每當(dāng)訪問到某個(gè)葉子結(jié)點(diǎn)時(shí)， 將該葉子結(jié)點(diǎn)所處的層次數(shù)與最大層 次數(shù)進(jìn)行比擬，假設(shè)前者大于后者，那么修改最大層次數(shù)為該葉子結(jié)點(diǎn)的層次數(shù)， 否那么不作修改。 遍歷 結(jié)束時(shí)，所記錄的最大層次數(shù)即為該二叉樹的深度。 本算法使用的是非遞歸的

16、中序遍歷算法 (其它遍 歷順序 也可以)。#define MAX_STACK 50int Depth(BTree T)BTree STACK1MAX_STACK, p = T;int STACK2MAX_STACK;int curdepth, maxdepth = 0, top = -1;if (T != NULL)curdepth = 1;while (p != NULL | top != -)while (p != NULL)STACK1+top = p;STACK2top = curdepth;p = p->lchild;curdepth+;p = STACK1top;curdep

17、th = STACK2top-;if (p->lchild = NULL && p->rchild = NULL) if (curdepth > maxdepth) maxdepth = curdepth;p = p->rchild;curdepth+;return maxdepth;9. 求結(jié)點(diǎn)所在層次算法思想： 采用后序遍歷的非遞歸算法對二叉樹進(jìn)行遍歷， 遍歷過程中對每一個(gè)結(jié)點(diǎn)判斷其 是否為滿足條件的結(jié)點(diǎn)，假設(shè)是滿足條件的結(jié)點(diǎn)，那么此時(shí)堆棧中保存的元素個(gè)數(shù)再加1 即為該結(jié)點(diǎn)所在的層次。#define MAX_STACK 50int LayerNode

18、(BTree T, int item)BTree STACK1MAX_STACK, p = T;int STACK2MAX_STACK, flag, top = -1;while (p != NULL | top != -1)while (p != NULL)STACK1+top = p;STACK2top = 0;p = p->lchild;p = STACK1top;flag = STACK2top-;if (flag = 0) STACK1+top = p;STACK2top = 1;p = p->rchild; else if (p->data = item)retu

19、rn top+2;p = NULL;10. 交換二叉樹中所有結(jié)點(diǎn)的左右子樹的位置算法思想： 按層次遍歷二叉樹， 遍歷過程中每當(dāng)訪問一個(gè)結(jié)點(diǎn)時(shí)， 就將該結(jié)點(diǎn)的左右子樹的 位置對調(diào)。#define MAX_QUEUE 50void ExchangeBT(BTree T)BTree QUEUEMAX_QUEUE, temp, p = T;int front, rear;if (T != NULL)QUEUE0 = T;front = -1;rear = 0;while (front < rear)p = QUEUE+front;temp = p->lchild;p->lchild

20、= p->rchild; p->rchild = temp;if (p->lchild != NULL) QUEUE+rear = p->lchild; if (p->rchild != NULL) QUEUE+rear = p->rchild; ，然后刪除以該結(jié)點(diǎn)為根結(jié)11. 刪除二叉樹中以某個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹 算法思想：先序遍歷找到符合條件的結(jié)點(diǎn)(其它遍歷方法亦可) 點(diǎn)的子樹。最后把該結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)的指針域置為NULL 。為此，需在算法中設(shè)置一個(gè)指針變量用以指示當(dāng) 前結(jié)點(diǎn)的父結(jié)點(diǎn)。#define MAX_STACK 50BTree DeleteSu

21、btree(BTree &T, int item)BTree STACKMAX_STACK, q, p = T; int top = -1;if (T->data = item)DestroyBT(T);T = NULL;return NULL;elsewhile (p != NULL | top != -1)while (p != NULL)if (p->data = item)if (q->lchild = p)q->lchild = NULL;elseq->rchild = NULL;DestroyBT(p);return T;STACK+top=

22、p;q = p;p = p->lchild;q = STACKtop-;p = q->rchild;三、查找1. 順序查找的遞歸算法int RecurSeqSearch(int A, int n, int key, int i) if (i >= n)return -1;if (Ai = key)return i;elsereturn RecurSeqSearch(A, n, key, i+1); pos = RecurSeqSearch(A, n, key, 0);2. 折半查找int BinSearch(int A, int n, int key) int low=0,

23、high=n-1, mid;while (low <= high)mid = (low+high)/2;if (key = Amid) return mid;if (key > Amid)low = mid + 1;elsehigh = mid T;return -1;3. 折半查找的遞歸算法int RecurBinSearch(int A, int low, int high, int key) int mid;if (low > high)return -1;else mid = (low+high)/2;if (key = Amid) return mid;if (ke

24、y > Amid)return RecurBinSearch(A, mid+1, high, key); elsereturn RecurBinSearch(A, low, mid-1, key); pos = RecurBinSearch(A, 0, n-1, key);4. 在按值遞增排列且長度為n 的線性表中折半查找并插入一元素 void BinInsert(int A, int &n, int key) int j, low=0, high=n-1, mid;while (low <= high)mid = (low+high)/2;if (key > Ami

25、d)low = mid + 1;elsehigh = mid T;for (j=n; j > low; j-)Aj = Aj-1;Alow = key;n+;5. 在按值遞增排列且長度為n 的線性表中折半查找值不小于 key 的最小元素 void BinSearch(int A, int n, int key) int low=0, high=n-1, mid;while (low <= high)mid = (low+high)/2;if (key = Amid) return mid;if (key > Amid)low = mid + 1;elsehigh = mid

26、T;if (low <= n-1)return low;elsereturn -1;四、排序1. 插入排序 算法思想：第i 趟插入排序?yàn)椋涸诤衖 . 1 個(gè)元素的有序子序列中插入一個(gè)元素，使之成為含有i個(gè)元素的有序子序列。在查找插入位置的過程中，可以同時(shí)后移元素。整個(gè)過程為進(jìn)行 n .1 趟插入，即先將整個(gè)序列的第1 個(gè)元素看成是有序的，然后從第2 個(gè)元素起逐個(gè)進(jìn)行插入，直到整個(gè)序列有序?yàn)橹?。void InsertSort(int A, int n)int i, j, temp;for (i=1; i <= n-1; i+)if (Ai < Ai-1)j = i-1;tem

27、p = Ai;while (j >= 0 && temp < Aj)Aj+1 = Aj;j-;Aj+1 = temp;2. 折半插入排序 算法思想：算法同直接插入排序，只不過使用折半查找的方法來尋找插入位置。void BinInsertSort(int A, int n)int i, j, low, high, mid, temp;for (i=1; i <= n-1; i+)temp = Ai;low = 0;high = i T;while (low <= high)mid = (low+high)/2;if (temp > Amid) low

28、 = mid + 1; elsehigh = mid T;for (j=i; j > low; j-)Aj = Aj-1;Alow = temp;3. 冒泡排序 算法思想：首先將第1 個(gè)元素和第2 個(gè)元素進(jìn)行比擬，假設(shè)前者大于后者，那么兩者交換位置，然后比擬第2 個(gè)元素和第3 個(gè)元素。依此類推，直到第n . 1 個(gè)元素和第n 個(gè)元素進(jìn)行過比擬或交換為止。上 述過程稱為一趟冒泡排序，其結(jié)果是使得 n 個(gè)元素中值最大的那個(gè)元素被安排在最后一個(gè)元素的位置 上。然后進(jìn)行第二趟排序，即對前n . 1 個(gè)元素進(jìn)行同樣的操作，使得前 n . 1 個(gè)元素中值最大的那 個(gè)元素被安排在第n . 1 個(gè)位置上

29、。一般地，第i 趟冒泡排序是從前n .i + 1 個(gè)元素中的第1 個(gè)元素 開始，兩兩比擬，假設(shè)前者大于后者，那么交換，結(jié)果使得前 n .i + 1 個(gè)元素中最大的元素被安排在第 ni + 1 個(gè)位置上。顯然，判斷冒泡排序結(jié)束的條件是“在一趟排序中沒有進(jìn)行過交換元素的操作，為此，設(shè)立一個(gè)標(biāo)志變量flag， flag = 1 表示有過交換元素的操作， flag = 0 表示沒有過交換元素的操 作，在每一趟排序開始前，將flag 置為 0，在排序過程中，只要有交換元素的操作，就及時(shí)將 flag 置 為1。因?yàn)橹辽僖獔?zhí)行一趟排序操作，故第一趟排序時(shí)，flag = 1 。void BubbleSort(

30、int A, int n)int i, j, temp, flag = 1;for (i=n-1; i >= 1 && flag = 1; i-)flag = 0; for (j=0; j < i; j+)if (Aj > Aj+1)temp = Aj;Aj = Aj+1;Aj+1 = temp;flag = 1;4. 選擇排序 算法思想：第i 趟排序從序列的后n .i + 1 (i = 1,2,)n個(gè)元素中選擇一個(gè)值最小的元素與該個(gè)元素的第1 個(gè)元素交換位置，即與整個(gè)序列的第i 個(gè)元素交換。依此類推，直到i = n . 1 為止。也然后將其與這些未就是說，

31、每一趟排序從從未排好序的那些元素中選擇一個(gè)值最小的元素， 排好序的元素中的第1 個(gè)元素交換位置。void SelectSort(int A, int n)int i, j, min, temp;for (i=0; i < n; i+)min = i;for (j=i+1; j < n; j+)if (Amin > Aj)min = j;if (min != i)temp = Amin;Amin = Ai;Ai = temp;5. 快速排序 算法思想：在參加排序的序列中任意選擇一個(gè)元素(通常稱為分界元素或基準(zhǔn)元素) ，把小 于或等于分界元素的所有元素都移到分界元素的前面， 把大

32、于分界元素的所有元素都移到分界元素的 后面，這樣，當(dāng)前參加排序的序列就被劃分成前后兩個(gè)子序列， 其中前一個(gè)子序列中的所有元素都 小于后一個(gè)子序列的所有元素， 并且分界元素正好處于排序的最終位置上。 然后分別對這兩個(gè)子序 列遞歸地進(jìn)行上述排序過程，直到所有元素都處于排序的最終位置上，排序結(jié)束。void QuickSort(int A, int n)QSort(A, 0, n-1);void QSort(int A, int low, int high)int pivotloc;if (low < high)pivot = Partition(A, low, high);QSort(A, low, pivotloc-1);QSort(A, pivotloc+1, high);int Partition(int A, int low, int high)int pivot;pivot = Alow;/ 從