数据结构经典算法!!.doc

1、数据结构算法背诵 一、线性表 1. 逆转顺序表中的所有元素 算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，依此类推。 void Reverse(int A, int n) int i, t; for (i=0; i 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); 2 3. 逆转线性链表 voi

2、d Reverse(LinkList p = list; q = NULL; while (p != NULL) r = q; q = p; p = p-next; q-next = r; list = q; 4. 复制线性链表（递归） 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); ret

3、urn listb; 5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表 LinkList MergeList(LinkList lista, LinkList listb) LinkList listc, p = lista, q = listb, r; / listc 指向 lista 和 listb 所指结点中较小者 if (lista-data data) listc = lista; r = lista; p = lista-next; else listc = listb; r = listb; q = listb-next; while (p != NULL r

4、= p; p = p-next; else r-next = q; r = q; q = q-next; / 将剩余结点（即未参加比较的且已按升序排列的结点）链接到整个链表后面 r-next = (p != NULL) ? p : q; return listc; 3 二、树 1. 二叉树的先序遍历（非递归算法） 算法思想：若 p 所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将 p 指向其左孩 子结 点；若 p 所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将 p 指向其右孩子 结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。 #define M

5、AX_STACK 50 void 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. 二叉树的中序遍历（非递归算法） 算法思想：若 p 所指结点不为空，则将该结点的地址 p 入栈，然后再将 p 指向其左孩子结点；若 p 所 指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地

6、址）送 p，并访问该结点，然后再将 p 指 向该结点的右孩子结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。 #define MAX_STACK 50 void InOrderTraverse(BTree T) BTree STACKMAX_STACK, p = T; int top = -1; while (p != NULL | top != -1); while (p != NULL) STACK+top = p; p = p-lchild; p = STACKtop-; VISIT(p); p = p-rchild; 4 3. 二叉树的后序遍历（非递归算法） 算法思想

7、：当 p 指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点 的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对 它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子 树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量 flag，当 flag = 0 时表示该结点暂不访问， flag = 1 时表示该结点可以访问。 flag 的值随同该结点的地 址一起入栈和出栈。因此，算法中设置了两个堆栈，其中 STACK1 存放结点的地址， STACK2 存放 标志变量 fla

8、g，两个堆 栈使用同一栈顶指针 top，且 top 的初始值为 1。 #define MAX_STACK 50 void 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; STACK2top = 0; p = p-lchild; p = STACK1top; flag = STACK2top-; if (flag = 0) STAC

9、K1+top = p; STACK2top = 1; p = p-rchild; else VISIT(p); p = NULL; 4. 二叉树的按层次遍历 算法思想：设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每 退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点（若存在的话）和右孩 子结点（若存在的话 ）入队列。如此重复下去，直到队列为空。 #define MAX_QUEUE 50 void LayeredOrderTraverse(BTree T) BTree QUEUEMAX_QUEUE, p; int front, rear; if (T

10、 != NULL) QUEUE0 = T; front = -1; rear = 0; while (front lchild != NULL) QUEUE+rear = p-lchild; if (p-rchild != NULL) QUEUE+rear = p-rchild; 5 5. 建立二叉树（从键盘输入数据，先序遍历递归算法） BTree CreateBT() char ch; BTree T; sacnf(“%c“, if (ch = ) return NULL; else T = (BTree)malloc(sizeof(BTNode); T-data = ch; T-lchil

11、d = CreateBT(); T-rchild = CreateBT(); return T; 6. 建立二叉树（从数组获取数据） BTree CreateBT(int A, int i, int n) BTree p; if (i n) return NULL; else p = (BTree)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 CreateB

12、T(int A, int n) int i; BTree *pT; / 对应 n 个结点申请可容纳 n 个指针变量的内存空间 pT = (BTree *)malloc(sizeof(BTree)*n); / 若数组中的某个元素不等于零，则申请相应的结点空间并进行赋 值 for (i=1; i data = Ai; else pTi = NULL; / 修改结点的指针域的内容，使父结点指向左、右孩子结点 for (i=1; i lchild = pT2*i; pTi-rchild = pT2*i+1; 6 7. 求二叉树的深度（递归算法） int Depth(BTree T) int ldept

13、h, rdepth; if (T = NULL) return 0; else ldepth = Depth(T-lchild); rdepth = Depth(T-rchild); if (ldepth rdepth) return ldepth+1; else return rdepth+1; 8. 求二叉树的深度（非递归算法） 算法思想：对二叉树进行遍历，遍历过程中依次 记录各个结点所处的层次数以及当前已经访问过的 结点所处的最大层次数。每当访问到某个叶子结点时，将该叶子结点所处的层次数与最大层次数进 行比较，若前者大于后者，则修改最大层次数为该叶子结点的层次数，否则不作修改。遍历结束时

14、， 所记录的最大层次数即为该二叉树的深度。本算法使用的是非递归的中序遍历算法（其它遍历顺序 也可以）。 #define MAX_STACK 50 int 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

15、-lchild; curdepth+; p = STACK1top; curdepth = STACK2top-; if (p-lchild = NULL p = p-rchild; curdepth+; return maxdepth; 7 9. 求结点所在层次 算法思想：采用后序遍历的非递归算法对二叉树进行遍历，遍历过程中对每一个结点判断其是否为 满足条件的结点，若是满足条件的结点，则此时堆栈中保存的元素个数再加 1 即为该结点所在的层次。 #define MAX_STACK 50 int LayerNode(BTree T, int item) BTree STACK1MAX_STACK

16、, 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) return top+2; p = NULL; 10.交换二叉树中所有结点 的左右子树的

17、位置 算法思想：按层次遍历二叉树，遍历过程中每当访问一个结点时，就将该结点的左右子树的位置对 调。 #define MAX_QUEUE 50 void ExchangeBT(BTree T) BTree QUEUEMAX_QUEUE, temp, p = T; int front, rear; if (T != NULL) QUEUE0 = T; front = -1; rear = 0; while (front lchild; p-lchild = p-rchild; p-rchild = temp; if (p-lchild != NULL) QUEUE+rear = p-lchild;

18、 if (p-rchild != NULL) QUEUE+rear = p-rchild; 8 11.删除二叉树中以某个结点为根结点的子树 算法思想：先序遍历找到符合条件的结点（其它遍历方法亦可），然后删除以该结点为根结点的子树。 最后把该结点的父结点的相应的指针域置为 NULL。为此，需在算法中设置一个指针变量用以指示当 前结点的父结点。 #define MAX_STACK 50 BTree DeleteSubtree(BTree int top = -1; if (T-data = item) DestroyBT(T); T = NULL; return NULL; else while

19、(p != NULL | top != -1) while (p != NULL) if (p-data = item) if (q-lchild = p) q-lchild = NULL; else q-rchild = NULL; DestroyBT(p); return T; STACK+top= p; q = p; p = p-lchild; q = STACKtop-; p = q-rchild; 9 三、查找 1. 顺序查找的递归算法 int RecurSeqSearch(int A, int n, int key, int i) if (i = n) return -1; if (Ai = key)