数据结构总结

1.冒泡与快速排序#includestdio.h void show(int *arr,int len){ for(int k0;klen;k){ printf(%d ,arr[k]); } printf(\n); } void Bubblesort(int *arr,int len){ for(int i0;ilen-1;i){ for(int j0;jlen-1-i;j){ if(arr[j]arr[j1]){ int tem arr[j]; arr[j] arr[j1]; arr[j1] tem; } } } } //low是数组最小下标,high是数组最大下标 void quicksort(int *arr,int low,int high){ if(low high){return;} int first low; int last high; int key arr[first]; while(first last){ while(first last arr[last] key){ last--; } arr[first] arr[last]; while(first last arr[first] key){ first; } arr[last] arr[first]; } arr[first] key; quicksort(arr,low,first-1); quicksort(arr,first1,high); } int main(){ int arr[10] {9,10,20,8,4,6,15,7,14,102}; int len 10; show(arr,len); quicksort(arr,0,9); show(arr,len); }2.顺序表基础数组的缺点:空间固定,有越界风险,有效位数不确定优点:空间利用率高,空间连续,支持随机访问顺序表:优化了越界风险和有效位数不确定问题 有效位(最大的下标1)逆序:从第二个节点开始打断成两个链表遍历第二个链表,依次取出节点,头插到第一个链表中排序:从第二个节点开始打断成两个链表;遍历第二个链表,将元素依次取出,按条件插入到第一个链表内3.数据结构物理结构:数据的存储方式,空间利用率,性能1.顺序存储结构:连续空间依次存放数据,逻辑相邻的数据在物理上也相邻2.链式存储结构:使用任意的空间存储数据,使用指针链接元素3.散列存储结构(哈希存储):根据hash函数计算出存储地址4.索引存储结构:存储数据时,建立一个索引表(关键字-地址),通过索引快速定位逻辑结构:数据间的组织形式1.线性结构:元素直接存在一对一的线性关系2.树形结构:元素直接存在一对多的层次关系3.图状结构(网状结构):元素直接存在多对多的层次关系4.集合结构:数据元素同属同一个集合,无特定关系查询:索引,hash(快)增删:链式结构访问:顺序结构