大话数据结构文摘
第1章 数据结构绪论
程序设计=数据结构+算法
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合
1.逻辑结构 ：是指数据对象中数据元素之间的相互关系
a：集合结构 b：线性结构 c：树形结构 d：图形结构
2.物理结构：在计算机中的存储形式
a: 循序存储 b: 链式存储
第2章 算法
算法: 是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作
特性：1.输入输出 2.有穷性 3.确定性 4.可行性
算法设计的要求:
1.正确性 2.可读性 3.健壮性 4.时间效率高和存储量低
算法的时间复杂度:
推导大O阶方法:
1. 用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶项
3.如果最高价项存在且不是1，则去除与这个项相乘的常数
常数阶：O(1) ; 线性阶: O(n) ; 对数阶:O(logn) ; 平方阶: O(n2)
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
第3章 线性表
线性表:零个或多个数据元素的有限序列
1.顺序存储结构:
| 优点 | 缺点 |
| 无须为表示表中元素之间的逻辑关系而增加额外的存储空间 | 插入和删除操作需要移动大量元素 |
| 可以快速地存取表中任一位置的元素 | 当线性表长度变化较大时难以确定存储空间的容量 |
| 造成存储空间的“碎片” |
2.链式存储结构：
单链表:
单链表与顺序存储结构作比较:
| 存储分配方式 | 时间性能 | 空间性能 |
| 顺序存储用一段连续的存储单元依次存储线性表的数据元素 | 查找：顺序：O(1),单链：O(n) | 差 |
| 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 | 插入删除:顺序:O(n),单链:O(1) | 好 |
静态链表:用数组描述的链表
| 优点 | 缺点 |
| 在插入和删除操作时，只需要修改游标，不需要移动元素 | 没有解决连续存储分配带来的表长难以确定的问题 |
| 失去了顺序存储结构随机存取的特性 |
循环链表:将单链表中终端结点的指针由空指针改为指向头结点,就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
双向链表:在单链表的每个结点中，再设置一个指向其前驱结点的指针域
第4章 栈与队列
栈:限定仅在表尾进行插入和删除操作的线性表
后进先出,(3种元素，就有5种可能的出栈顺序)
栈的顺序存储结构，进栈，出栈，O(1)
两栈共享空间
栈的链式存储结构,0(1)
斐波那契数列：
0 ,当n=0
1,当n=1
F(n) = F(n-1) + F(n-2),当n>1
四则运算表达式求值:后缀表达法，（逆波兰）
-----------------------------------------------------------------
队列:只允许在一端进行插入操作，而在另一端进行删除操作的线性表
先进先出
第5章 串
由零个或多个字符组成的有限序列,字符串
朴素的模糊匹配算法：最好：O(n+m),n为主串长度，m为子串长度,最差:O((n-m+1)*m)
KMP模式匹配算法:O(n+m)
第6章 树
完全二叉树
二叉树遍历方法：1.前序遍历 2.中序遍历 3.后序遍历 4.层序遍历
线索二叉树
赫夫曼树
第7章 图
第8章 查找
1.静态查找：
顺序查找:O(n)
/* 无哨兵顺序查找，a为数组，n为要查找的数组个数，key为要查找的关键字 */ int Sequential_Search(int *a,int n,int key) { int i; for(i=1;i<=n;i++) { if (a[i]==key) return i; } return 0; }
/* 有哨兵顺序查找 */ int Sequential_Search2(int *a,int n,int key) { int i; a[0]=key; i=n; while(a[i]!=key) { i--; } return i; }
有序表查找：
二分查找:O(logn)/* 折半查找 */
递归算法
static int BinarySearch2(int[] a, int value, int low, int high) { int mid = (low + high) / 2; if (a[mid] == value) return mid; else if (a[mid] > value) return BinarySearch2(a, value, low, mid); else if (a[mid] < value) return BinarySearch2(a, value, mid, high); else return 0; }
非递归算法
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; }
c#版本:
static int Test(int[] a,int x)
{
int low = 0, high = a.Length-1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (x < a[mid])
{
high = mid - 1;
}
else if (x > a[mid])
{
low = mid + 1;
}
else
{
return mid;
}
}
return 0;
}
插值查找:O(logn)
/* 插值查找 */ int Interpolation_Search(int *a,int n,int key) { int low,high,mid; low=1; /* 定义最低下标为记录首位 */ high=n; /* 定义最高下标为记录末位 */ while(low<=high) { mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */ if (key<a[mid]) /* 若查找值比插值小 */ high=mid-1; /* 最高下标调整到插值下标小一位 */ else if (key>a[mid])/* 若查找值比插值大 */ low=mid+1; /* 最低下标调整到插值下标大一位 */ else return mid; /* 若相等则说明mid即为查找到的位置 */ } return 0; }
斐波那契查找
线性索引查找：
稠密索引，在线性索引中，将数据项的每个记录对应一个索引项。
分块索引，分块有序的数据集，将每块对应一个索引项。
倒排索引，由属性值来确定记录的位置。
2.动态查找：查找时需要插入和删除
二叉排序树，O(logn)-O(n)
平衡二叉树(AVL树)，（O(logn)）
B树(多路查找树)，
2-3树，
2-3-4树，
B+树
散列表查找
直接定址法，数学分析法，平方取中法，折叠法，除留余数法，随机数法
处理散列冲突的方法：1.开放定址法，2再散列函数法，3.链地址法，4，公共溢出区法
第9章 排序
| 排序 | |||||||
| 插入排序类 | 选择排序类 | 交换排序类 | 归并排序类 | ||||
| 直接插入排序 | 希尔排序 | 简单选择排序 | 堆排序 | 冒泡排序 | 快速排序 | 归并排序 |
|
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 |
| 直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn)-O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(nlogn)-O(n2) | 不稳定 |
假设含有n个记录的序列为{r1,r2,.....rn},其对应的关键字分别为{k1,k2...kn},
需确定1,2，。。。N的一种排列p1,p2,...pn,使其相应的关键字满足kp1<=kp2...<=kpn
非递减（或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2...rpn},这样的操作叫做排序
排序的稳定性：
假设ki=kj,且在排序前的序列中ri领先于rj,如果排序后仍然领先，则是稳定的，反之是不稳定的。
内排序与外排序：
内排序所有记录放在内存中，外排序需要在内外存之间多次交换数据才能进行。
冒泡排序:
int[] array = { }; void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } ///////////////冒泡排序1/////////// void bubblesort1(int[] array) { for (int i = 0; i < array.Length;i++ ) { for (int j = i + 1; j < array.Length;j++ ) { if (array[i] > array [j]) { swap(array, i, j); } } } } ///////////////冒泡排序2/////////// void bubblesort2(int[] array) { for (int i = 0; i < array.Length; i++) { for (int j = array.Length-1; j >=i; j--) { if (array[i] > array[j]) { swap(array, i, j); } } } } ///////////////冒泡排序3/////////// void bubblesort3(int[] array) { bool flag = true; for (int i = 0; i < array.Length && flag; i++) { flag = false; for (int j = array.Length - 1; j >= i; j--) { if (array[i] > array[j]) { swap(array, i, j); flag = true; } } } }
冒泡排序时间复杂度O(n2)
简单选择排序:
////////////简单选择排序////////// void selectSort(int[] array) { int i,j,min; for (i = 0; i < array.Length-1; i++ ) { min = i; for (j = i + 1; j <= array.Length-1; j++) { if (array[min] > array[j]) { min = j; } } if (i != min) { swap(array,i,min); } } }
简单选择排序时间复杂度O(n2)
直接插入排序: 扑克牌
/// <summary> /// //////直接插入排序/////// /// </summary> void insertSort(int[] array) { int t,i, j; for (i = 1; i < array.Length; i++) { if (array[i] < array[i - 1]) { t = array[i]; for (j = i - 1; j >= 0; j--) { array[j + 1] = array[j]; } array[j + 1] = t; } } }
直接插入排序时间复杂度O(n2)
希尔排序:
static void shellSort(int[] array) { int i, j, temp; int increment = array.Length; do { increment = increment / 3 + 1; for (i = increment; i < array.Length; i++) { if (array[i] < array[i - increment]) { temp = array[i]; for (j = i - increment; j >= 0 && temp < array[j]; j -= increment) { array[j + increment] = array[j]; } array[j + increment] = temp; } } } while (increment > 1); }
希尔排序时间复杂度O(n3/2)
不稳定
堆排序:
堆是具有下列性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆；
static void HeapSort(int[] array) { int i; for (i = array.Length / 2 - 1; i >= 0; i--) HeapAdjust(array, i, array.Length - 1); for (i = array.Length - 1; i >= 1; i--) { swap(array, 0, i); HeapAdjust(array, 0, i - 1); } } static void HeapAdjust(int[] array, int i, int m) { int temp, j; temp = array[i]; for (j = 2 * i; j <= m; j *= 2) { if (j < m && array[j] < array[j + 1]) ++j; if (temp >= array[j]) break; array[i] = array[j]; i = j; } array[i] = temp; }
时间复杂度O(nlogn)
不稳定
归并排序:
时间复杂度O(nlogn)
稳定
快速排序:
原始版本
static void QuickSort(int[] array, int low, int high) { int pivot; if(low < high) { pivot = Partition(array,low,high); QuickSort(array, low, pivot - 1); QuickSort(array, pivot + 1, high); } } static int Partition(int[] array, int low, int high) { int pivotkey = array[low]; while (low < high) { while (low < high && array[high] >= pivotkey) high--; swap(array, low, high); while (low < high && array[low] <= pivotkey) low++; swap(array, low, high); } return low; }
1 优化选取枢轴
优化后的快速排序：
static void QuickSort(int[] array, int low, int high) { int pivot; //优化小数组时的排序方案 if ((high - low) > 50) { //优化递归操作 while (low < high) { pivot = Partition(array, low, high); QuickSort(array, low, pivot - 1);//对低子表进行递归排序 //QuickSort(array, pivot + 1, high); low = pivot + 1;//尾递归 } } //else //直接插入排序 } static int Partition(int[] array, int low, int high) { //优化选取枢轴 int m = low + (high - low) / 2; if (array[low] > array[high]) swap(array, low, high); if (array[m] > array[high]) swap(array, m, high); if (array[m] > array[low]) swap(array, m, low); int pivotkey = array[low]; int temp = pivotkey; while (low < high) { while (low < high && array[high] >= pivotkey) high--; //优化不必要的交换 //swap(array, low, high); array[low] = array[high]; while (low < high && array[low] <= pivotkey) low++; //优化不必要的交换 //swap(array, low, high); array[high] = array[low]; } array[low] = temp; return low; }
快速时间复杂度O(nlogn)
net SDK版本
void QuickSort(int[] map, int left, int right) { do { int i = left; int j = right; int x = map[i + ((j - i) >> 1)]; do { while (i < map.Length && CompareKeys(x, map[i]) > 0) i++; while (j >= 0 && CompareKeys(x, map[j]) < 0) j--; if (i > j) break; if (i < j) { int temp = map[i]; map[i] = map[j]; map[j] = temp; } i++; j--; } while (i <= j); if (j - left <= right - i) { if (left < j) QuickSort(map, left, j); left = i; } else { if (i < right) QuickSort(map, i, right); right = j; } } while (left < right); }
不稳定
转载于:https://www.cnblogs.com/smileberry/archive/2013/02/01/2889579.html