响应式布局模板网站免费下载,百度百度一下,专业设计自学网站,室内装饰设计学什么第1章 数据结构绪论 程序设计数据结构算法 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合 1.逻辑结构 #xff1a;是指数据对象中数据元素之间的相互关系 a#xff1a;集合结构 b#xff1a;线性结构 c#xff1a;树形结构 d#xff1a;图形结构 2.物理结…第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 ,当n0 1,当n1 F(n) F(n-1) F(n-2),当n1 四则运算表达式求值:后缀表达法逆波兰 ----------------------------------------------------------------- 队列:只允许在一端进行插入操作而在另一端进行删除操作的线性表 先进先出 第5章 串 由零个或多个字符组成的有限序列,字符串 朴素的模糊匹配算法最好O(nm),n为主串长度m为子串长度,最差:O((n-m1)*m) KMP模式匹配算法:O(nm) 第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(i1;in;i){if (a[i]key)return i;}return 0;
} /* 有哨兵顺序查找 */
int Sequential_Search2(int *a,int n,int key)
{int i;a[0]key;in;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;low1; /* 定义最低下标为记录首位 */highn; /* 定义最高下标为记录末位 */while(lowhigh){mid(lowhigh)/2; /* 折半 */if (keya[mid]) /* 若查找值比中值小 */highmid-1; /* 最高下标调整到中位下标小一位 */else if (keya[mid])/* 若查找值比中值大 */lowmid1; /* 最低下标调整到中位下标大一位 */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;low1; /* 定义最低下标为记录首位 */highn; /* 定义最高下标为记录末位 */while(lowhigh){midlow (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */if (keya[mid]) /* 若查找值比插值小 */highmid-1; /* 最高下标调整到插值下标小一位 */else if (keya[mid])/* 若查找值比插值大 */lowmid1; /* 最低下标调整到插值下标大一位 */elsereturn 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,使其相应的关键字满足kp1kp2...kpn 非递减或非递增关系即使得序列成为一个按关键字有序的序列{rp1,rp2...rpn},这样的操作叫做排序 排序的稳定性 假设kikj,且在排序前的序列中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/// //直接插入排序////// /summaryvoid 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
