作为码农,一看到数据结构和算法就头疼,谁让自己的数学和逻辑分析能力那么差呢.....,不过知耻而后勇,虽然头疼,但是数据结构和算法还是要了解一些的,而《大话数据结构》这本书就让我了解了数据结构和算法的最基本概念。现将读书笔记总结如下:
1.数据结构的分类
按逻辑结构分为:
集合结构:数据元素之间没有任何关系;
线性结构:数据元素之间一对一的关系;
树形结构:数据元素之间是一对多的关系;
图形结构:数据元素之间是多对多的关系;
按物理结构分为,即数据的逻辑结构在计算机中的存储形式:
顺序存储结构:数据元素存放在连续的地址空间内;
链式存储结构:数据元素放在任意的存储空间内,通过链(通常是指针)进行连接;
2.推到大O阶的方法:
1)用常数1取代运行时间中的所有加法常数;
2)在修改后的运行次数函数中,只保留最高阶项;
3)如果最高阶项存在且不是1,则去除与这个相乘的常数。
常用时间复杂度的大小关系:
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
3.计算机是如何计算四则运算的(本书108页)
中缀表达式转后缀表达式: 9+(3-1)*3+10/2 --> 9 3 1 - 3 * + 10 2 / +
后缀表达式的计算规则:从左到右遍历表达式的每个数字和符号,遇到数字就进栈,遇到符号,就将栈顶两个数字出栈,进行运算,运输结果进栈,一直到最终获得结果;
中缀表达式转换成后缀表达式的转换规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出 后缀表达式为止;
4.二叉树
1)二叉树的二叉链表的结点结构定义
/* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode { TElemType data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ } BiTNode, *BiTree
2)前序遍历
遍历规则是:若二叉树为空,则空操作返回;否则先访问根结点,然后前序遍历左子树,再前序遍历右子树;代码如下:
/* 二叉树的前序遍历递归算法 */ void PreOrderTraverse (BiTree T) { if (T == NULL) return; printf("%c,", T->data); /* 显示节点数据,可替换成其他操作 */ PreOrderTraverse(T->lchild); /* 再前序遍历左子树 */ PreOrderTraverse(T->rchild); /* 最后前序遍历右子树 */ }
3)中序遍历
遍历规则是:若二叉树为空,则空操作返回,否则从跟结点开始(注意不是先访问根结点),中序遍历根节点的左子树,然后访问根节点,最后中序遍历右子树;代码如下:
/* 二叉树的中序遍历递归算法 */ void InOrderTraverse (BiTree T) { if (T == NULL) return; InOrderTraverse(T->lchild); /* 中序遍历左子树 */ printf("%c,", T->data); /* 显示节点数据,可替换成其他操作 */ InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */ }
4)后序遍历
遍历规则是:若二叉树为空,则空操作返回,否则从左至右先叶子后结点的方式遍历访问左右子树,最后访问根结点。代码如下:
/* 二叉树的后序遍历递归算法 */ void PostOrderTraverse (BiTree T) { if (T == NULL) return; PostOrderTraverse (T->lchild); /* 后序遍历左子树 */ PostOrderTraverse (T->rchild); /* 再后续遍历右子树 */ printf("%c,", T->data); /* 最后显示节点数据,可替换成其他操作 */ }
5.顺序表查找
简单的算法代码如下:
/* 顺序查找,a为数组,n为要查找的数组个数, key为要查找 */ int Sequential_Search (int *a, int n, int key) { int i; for (i=1; i<=n; i++) /* 注意i从1开始,不是从0开始 */ { if (a[i] == key) return i; } return 0; }
上述代码并不完美,因为每次循环时都要判断i是否越界,下面的代码通过设置一个哨兵,优化一下,代码如下:
/* 有哨兵的顺序查找 */ int Sequential_Search2 (int *a, int n, int key) { int i; a[0] = key; /* 设置a[0]为关键字值,即“哨兵” */ i = n; while (a[i] != key) i--; return i; }
上述代码将“哨兵”放到了数组的第一个位置,当然也可以放到数组的末尾,这个时候i就从0开始,在while循环内就用i++来移动数据了;这种技巧对于总数据较多时,效率提高会很大的。
6.有序表查找
1)折半查找(二分查找)代码如下:
/* 折半查找 */ int Binary_Search(int *a, int n, int key) { int low, high, mid; low=1; /* */ high=n; while(low<=high) { mid = (low+high)/2; /* 折半 */ if ( key < a[mid] ) /* 若查找值比中指小 */ high = mid - 1; else if ( key > a[mid] ) /* 若查找值比中指小 */ low = mid + 1; else return mid; /* 若相等则mid即为查找到的位置 */ } return 0; }
2)插值查找
只要将折半查找那个折半语句,用下面的语句替换即可:
mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); /* 插值 */
注意:插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法。对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好很多。
3)斐波那契查找
代码如下:
/* 斐波那契数组 */ /* F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ...} ; */ /* 斐波那契查找 */ int Fibonaci_Search(int *a, int n, int key) { int low, high, mid, i, k; low = 1; high = n; k = 0; while (n > F[k] - 1) /* 计算n在斐波那契数列的位置 */ k++; for (i=n; i<F[k]-1; i++) /* 将不满的数值补全 */ a[i] = a[n]; while(low <= high) { mid = low + F[k-1] - 1; /* 计算当前分割的下表 */ if (key < a[mid]) { high = mid -1; k = k - 1; /* 斐波那契数列下标减一位 */ } else if (key > a[mid]) { low = mid + 1; k = k - 2; /* 斐波那契数列下标减两位 */ } else { if (mid <= n) return mid; else return n; /* 若mid>n说明是补全数值,返回n */ } } return 0; }
斐波那契查找适合要查找的记录在查找表中的右侧,那么左侧的数据就不用判断了。
【总结】折半查找是进行加法与除法运算;插值查找是进行复杂的四则运算;斐波那契查找只进行简单加法运算,在海量数据的查找过程中,这种细微的差别可能会影响最终的查找效率。
7.二叉排序树
1)二叉排序树的属性:
- 若它的左子树不为空,则左子树上所有结点的值都小于它的根结点的值;
- 若它的右子树不为空,则右子树上所有结点的值都大于它的根结点的值;
- 它的左、右子树也分别为二叉排序树;
2)二叉排序树的查找操作
二叉树的结构如下:
typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;
查找算法代码如下:
/* 递归查找二叉排序树T中是否存在key */ /* 指针 f 指向 T 的双亲,其初始值调用值为NULL */ /* 若查找成功,则指针 p 指向该数据元素结点,并返回TRUE */ /* 若指针 p 指向查找路径上访问的最有一个结点并返回FALSE */ Status SearchBST(BiTree T, int key, BiTree f, BiTree *p) { if (!T) /* 查找不成功 */ { *p = f; return FALSE; } else if (key == T->data) /* 查找成功 */ { *p = T; return TRUE; } else if (key < T->data) return SearchBST(T->lchild, key, T, p); else return SearchBST(T->rchild, key, T, p); }
3)二叉排序树的插入操作
代码如下:
/* 当二叉排序树T中不存在关键字等于key的数据元素时, */ /* 插入key并返回FALSE,否则返回FALSE */ Status InsertBST (BiTree *T, int key) { BiTree p, s; if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */ { s = (BiTree)malloc(sizeof(BiTNode)); s->data = key; s->lchild = s->rchild = NULL; if (!p) *T = s; else if (key < p->data) p->lchild = s; else p->rchild = s; return TRUE; } else return FALSE; /* 树中已有关键字相同的结点,不再插入 */ }
4)二叉排序树的删除操作
删除结点需要分三种情况:
- 叶子节点:直接删除即可,其他结点的结构并未受到影响;
- 仅有左或右子树的结点:删除结点后,将它的左子树或右子树整个移动到删除结点的位置即可;
- 左右子树都有的结点:找到需要删除的结点p的直接前驱(或直接后继)s,用s来替换节点p,然后再删除此结点s;
代码如下:
/* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */ /* 并返回TRUE;否则返回FALSE */ Status DeleteBST (BiTree *T, int key) { if (!*T) return FALSE; else { if (key == (*T)->data) return Delete(T); else if (key < (*T)->data) return DeleteBST(&(*T)->lchild, key); else return DeleteBST(&(*T)->rchild, key); } }
上述代码中的Delete函数的代码如下:
/* 从二叉排序树中删除结点p,并重接它的左或右子树 */ Status Delete(BiTree *p) { BiTree q,s; if ( (*p)->rchild == NULL) /* 右子树空则只需重接它的左子树 */ { q = *p; *p = (*p)->lchild; free(q); } else if ((*p)->lchild == NULL) /* 左子树空则只需重接它的右子树 */ { q = *p; *p = (*p)->rchild; free(q); } else { q = *p; s = (*p)->lchild; /* 转左,然后向右到尽头(找到待删结点的前驱) */ while (s->rchild) { q = s; s = s->rchild; } (*p)->data = s->data; /* s指向被删结点的直接前驱 */ if (q != *p) q->rchild = s->lchild; /* 重接q的右子树 */ else q->lchild = s->rchild; /* 重接q的左子树 */ free(s); } return 0; }
8.快速排序
基本思想:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到真个序列有序的目的。代码如下:
1 /* 对顺序表L作快速排序 */ 2 void QuickSort (SqList *L) 3 { 4 QSort(L, 1, L->Length); 5 }
QSort函数的实现如下:
/* 对顺序表L中的自序列L->r[low...high]作快速排序 */ void Qsort (SqList *L, int low, int high) { int pivot; if (low < high) { pivot = Partition(L, low, high); /* 将L->r[low...high]一分为二,算出枢轴值 */ QSort(L, low, pivot-1); /* 对低子表递归排序 */ QSort(L, pivot+1, high); /* 对高子表递归排序 */ } }
Partition函数要做的就是选取一个关键字,将其放到一个位置,使得它左边的值都比它小,右边的值比它大;其实现如下:
1 /* 交换顺序表L中子表的记录,使枢轴记录到位,并返回其所在位置 */ 2 /* 此时在它之前(后)的记录均不大(小)于它 */ 3 int Partition (SqList *L, int low, int high) 4 { 5 int pivotkey; 6 pivotkey = L->r[low]; /* 用子表的第一个记录作枢轴记录 */ 7 while (low < high) 8 { 9 while (low < high && L->r[high] > = pivotkey) 10 high--; 11 swap(L, low, high); /* 将比枢轴记录小的记录交换到低端 */ 12 while (low < high && L-r[low] <= pivotkey) 13 low++; 14 swap(L, low, high); /* 将比枢轴记录大的记录交换到高端 */ 15 } 16 17 return low; /* 返回枢轴所在的位置 */ 18 }
【总结】:快速排序算法,关键在于枢轴值的选取,为了优化枢轴值的选取,可以采取三数取中法,即取三个关键字先进行排序,将中间数所谓枢轴,一般是取左端、右端和中间三个数。
--------------------------本文完--------------------------