浙江工业大学计算机学院数据结构总复习.ppt

* * * * * * * * * * Main Index Contents Queue application Queue based on Linkedlist; 循环队列(bounded queue) * * Main Index Contents Search algorithms Simple search algorithm //O(n) Binary search //O(log2n) Hash算法：O(1) 1.Hash函数 2.碰撞解决方法 　开散列/闭散列（开放定址法、线性地址探测法/链地址法） 3.计算平均成功查找长度(ASL) * Sorting algorithm summary O(n2) ---strictly comparing adjacent vector element insertionsort bubblesort selectionsort --- exchange sort O(nlog2n)---- comparing nonadjacent vector element mergesort quicksort heapsort O(n) ---- no use comparison radix sort ---- O(2*d*n)=O(n) * Sorting algorithm summary Insertion sort direct insertion sort shell sort Exchange sort bubble sort quick sort Select sort simple select sort heap sort Merge sort Radix sort * Sorting algorithm summary 排序方法 最好时间 最坏时间 平均时间 辅助空间 稳定性 直接插入 O(n) O(n2) O(n2) O(1) 稳定 简单选择 O(n2) O(n2) O(n2) O(1) 不稳定 冒泡排序 O(n) O(n2) O(n2) O(1) 稳定 希尔排序 ---- ---- O(n1.25) O(1) 不稳定 快速排序 O(nlog2n) O(n2) O(nlog2n) O(log2n) (辅助栈) 不稳定 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 基数排序 O(d*n) O(d*n) O(d*n) O(n*d) 稳定 * * * * * * * * * * * * * * * * * * * * * * * * * * * Main Index Contents * * Main Index Contents 数据结构总复习 线性结构： 1.数组array 2.向量vector　　　　　　　　　　　线性表 3.链表(Linked list/Double list) 4.栈　　　　　　　　　　　　　　　受限线性表 5.队列/优先队列　　　　　　　　　　 非线性结构 1.树/二叉树（平衡二叉树、堆、霍夫曼树、B/B+） 2.图 * 数据结构总复习 数据结构复习纲要： 对于任何一种数据结构 1.基本逻辑特性（逻辑结构）：例如访问方式、插入删除方式、遍历方式 2.物理存储方式（物理实现） 3.基本逻辑特性的实现：例如访问实现、插入删除实现、遍历实现 4.特定算法的实现，如图中最短路径算法等。 * * Main Index Contents Vector Concept private: int vCapacity; int vSize; T *vArr; // the dynamic array /////////////////////////////////////////////////////////// T *Arr; Arr = new T[n]; /////////////////////////////////////////////////////////// Int intArray[]={1,2,3,4,5}; Int arrSize=sizeof(intArray)/sizeof(int); Vectorint intVector(intArray, intArray+arrSize); * * Main Index Contents Vector Oper