当前位置:   article > 正文

不同表结构数据迁移_Mrain哥带你学数据结构 顺序表

不同表结构数据迁移

Mrain哥带你学数据结构 - 顺序表


写在前面

  • 注:这篇博文主要是用来总结这周学习的内容,因个人水平对问题的理解可能有不对的地方,欢迎大家一起来交流学习。

  • 本博文内容倾向于总结性,可能很多内容对小白理解起来并不友好,后期会开放更多小白科普文和一些易上手的编程小项目,想了解更多计算机基础知识就关注我吧,Mrain哥带你学编程!

  • Mrain哥的CSDN博客首页:https://blog.csdn.net/weixin_48670869。

  • 个人独立博客也正在搭建中,不日开放。

正文

1. 数据结构

f77300948d7f7e1f39a543a4baf5e19f.png

2. 线性表、顺序表、链表、栈、队列和数组之间的区别

  • 线性表是一种逻辑结构,不涉及存储结构。

  • 线性表顺序存储时,就是顺序表,顺序表既包含了逻辑结构也包含了存储结构。

  • 顺序表的顺序存储一般通过数组来实现。

  • 一维数组具有与顺序表相同的逻辑结构和存储结构,可以将一维数组等价为顺序表。

  • 线性表链式存储时就是链表,链表既包含了逻辑结构也包含了存储结构。

  • 链表的链式存储一般通过指针来实现。

  • 当线性表受到限制,只能在一端插入删除时,就变成了栈。

  • 当线性表受到限制,只能在一端插入,在另一端删除,就变成了队列。

3. 静态数组的建立

//Maxsize可以采用宏定义,或者const定义//尽量用const定义,a.宏定义不能指定类型 b.宏定义没有作用域::const int MaxSize = 10;  //数组的最大长度typedef struct{  int data[MaxSize];  int length;}Arr;void init_list(Arr& A){  A.length = 0;}

Note: 静态分配后数组的大小和空间时是固定的,不可以更改。

4. 动态数组的建立

const int MaxSize = 10;  //数组的最大长度typedef struct {  int* data;  int MaxSize;  //length相当与index的作用  int length;}Arr;void init_array(Arr& A) {  A.data = (int*)malloc(InitSize * sizeof(int));  A.length = 0;  A.MaxSize = InitSize;}void increase_size(Arr& A, int len){  int* p = A.data;  A.data = (int*)malloc((A.MaxSize + len) * sizeof(int));  for (int i = 0; i < A.length; i++)    A.data[i] = p[i];  A.MaxSize = A.MaxSize + len;  free(p);}

Note: 顺序存储需要连续的内存空间,扩大数组容量时,会重新申请一片更大的存储空间,然后将之前的数据全部拷贝过来。

5. 按位查找

//返回值为int, 与上文的返回值void不同,返回值void需要通过引用才能更改值,返回值为int可通过返回值的到更改后的值//引用型的改值方法可以同时改变多个值,用返回值改变数值,一次只能返回一个数值int get_elem(arr A, int i){  if (i<1 || i>A.length)    return false;  //是否溢出  if (A.length >= MaxSize)    return false;    //i和数组的index不同,i表示元素的位序范围是:1-n,数组的index的范围是:0-(n-1)    return A.data[i-1];}

时间复杂度

O(1)

6. 按值查找

int locate_elem(arr A, int e){    //此时的i表示的index,范围是0-(n-1)    for(int i=0;i        if(A.data[i]==e)            //范围元素的序号            return i+1;    return 0;}

时间复杂度

best case: O(1), 数据在头部

worst case: O(n), 数据在尾部

average case: O(n), 目标数据出现在任一位置的概率相等,1/n

1*1/n+2*1/n+3*1/n+......+n*1/n=1/n*n(n+1)/2=(n+1)/2

O((n+1)/2)=O(n)

7. 插入

bool array_insert(Arr& A, int i, int e){  //i的值是否正确    //可以插在n+1if (i<1 || i>A.length+1)    return false;  //是否溢出  if (A.length >= MaxSize)    return false;  //插入时需要先将第i到n个元素全部后移  //先移动最后一个  for (int j = L.length; j >= i; j--)    A.data[j] = A.data[j - 1];  //插入元素  A.data[i - 1= e;  //数组长度加1  A.length++;  return true;}

时间复杂度:

best case: O(1), 数据插在尾部(i=n+1, i代表元素的位序)

worst case: O(n), 数据在头部,n个数据全需要后移

average case: O(n), 目标数据出现在任一位置的概率相等,1/(n+1)

8. 删除

//需要返回的值,要加引用bool array_delete(Arr& A, int i, int& e){  //i的值是否正确  if (i<1 || i>A.length)    return false;  e = A.data[i - 1];  //删除元素时,需要将(i+1)-n所有的值全部前移    //先从第i+1个值开始移动  //不需要先删除i,可以通过i+1覆盖自动删除    for(int j = i; j < A.length; j++)    A.data[j-1] = A.data[j];  //系统内存会自动回收,不需要释放    A.length--;  return true;}

时间复杂度:

best case: O(1), 删除尾部数据(i=n+1, i代表元素的位序)

worst case: O(n), 删除头部数据,n-1个数据全需要前移

average case: O(n), 目标数据出现在任一位置的概率相等,1/n

9. 遍历

void traverse(){    for(int i=0;i        cout<"\t";    cout<<endl;}

交个朋友

  • 微信公众号:miaoyuwangyan

  • CSDN博客首页:https://blog.csdn.net/weixin_48670869

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/675195
推荐阅读
相关标签
  

闽ICP备14008679号