数据结构——顺序表（静态分配、动态分配、基本操作）

一、静态分配

//顺序表的实现--静态分配

#include<stdio.h>

#define MaxSize 10?? //定义表的最大长度typedef struct{

int data[MaxSize];//用静态的"数组"存放数据元素int length; //顺序表的当前长度

}SqList;???????? //顺序表的类型定义（静态分配方式） void InitList(SqList &L){

for(int i=0;i<MaxSize;i++){

L.data[i]=0;? //将所有数据元素设置为默认初始值

}

L.length=0;

}

int main(){

SqList L;//声明一个顺序表InitList(L);//初始化一个顺序表for(int i=0;i<MaxSize;i++){

printf("data[%d]=%d\n",i,L.data[i]);

}

return 0;

}

二、动态分配

//顺序表的实现——动态分配#include<stdio.h>

#include<stdlib.h>//malloc、free函数的头文件#define InitSize 10 //默认的最大长度

typedef struct{

int? *data;//指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度

}SeqList;

//初始化

void InitList(SeqList &L){

//用malloc 函数申请一片连续的存储空间

L.data =(int*)malloc(InitSize*sizeof(int)) ; L.length=0;

L.MaxSize=InitSize;

}

//增加动态数组的长度

void IncreaseSize(SeqList &L,int len){ int *p=L.data;

L.data=(int*)malloc((L.MaxSize+len)*sizeof(int)); for(int i=0;i<L.length;i++){

L.data[i]=p[i];?? //将数据复制到新区域

}

L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len free(p);??? //释放原来的内存空间

}

int main(void){

SeqList L; //声明一个顺序表InitList(L);//初始化顺序表IncreaseSize(L,5);

return 0;

}

三、顺序表的特点：

1. ==随机访问== ，可以在O(1)时间内找到第i个元素。

? 2.存储密度高，每个节点只存储数据元素

? 3.拓展容量不方便

? 4.插入、删除操作不方便，需要移动大量元素

四、基本操作

1.插入操作 ：平均时间复杂度O(n)

bool ListInsert(SqList &L, int i, int e){

//判断i的范围是否有效if(i<1||i>L.length+1)

return false;

if(L.length>MaxSize) //当前存储空间已满，不能插入return false;

for(int j=L.length; j>=i; j--){???? //将第i个元素及其之后的元素后移L.data[j]=L.data[j-1];

}

L.data[i-1]=e;? //在位置i处放入e L.length++;????? //长度加1

return true;

}

2.删除操作：平均时间复杂度O(n)

bool LisDelete(SqList &L, int i, int &e){ // e用引用型参数

//判断i的范围是否有效if(i<1||i>L.length)

return false;

e = L.data[i-1]???? //将被删除的元素赋值给e

for(int j=L.length; j>=i; j--){???? //将第i个后的元素前移L.data[j-1]=L.data[j];

}

L.length--;?????? //长度减1

return true;

}

3.按位查找(获取L表中第i个位置的值)：平均时间复杂度O(1)

#define MaxSize 10

typedef struct{

ElemType data[MaxSize];? //用静态的“数组”存放数据元素

int Length;?????????????? //顺序表的当前长度

}SqList;?????????????????????? //顺序表的类型定义

ElemType GetElem(SqList L, int i){

// ...判断i的值是否合法

return L.data[i-1];?????? //注意是i-1

}

4.按值查找：平均时间复杂度O（n）

#define InitSize 10???????????? //定义最大长度

typedef struct{

ElemTyp *data;? //用静态的“数组”存放数据元素int Length;?????????? //顺序表的当前长度

}SqList;

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序

int LocateElem(SqList L, ElemType e){

for(int i=0; i<L.lengthl i++) if(L.data[i] == e)

return i+1;????? //数组下标为i的元素值等于e，返回其位序i+1

return 0;???????????????? //推出循环，说明查找失败

}

五、学习心得

1. 数据结构的选择对算法效率的影响
? ?顺序表（数组）提供了随机访问的能力，这意味着我们可以直接通过下标访问元素，这是因为顺序表的内存是连续的。但这种数据结构在插入和删除操作上效率较低，因为可能需要移动大量元素。

2. 静态分配与动态分配的区别
? ?静态分配的顺序表在编译时就已经确定了大小，而动态分配的顺序表则可以在运行时确定大小，并且能够根据需要扩展空间。了解这两种分配方式的区别对于编写灵活且高效的代码非常重要。

3. 内存管理的重要性
? ?在动态分配版本的顺序表中，我们需要手动管理内存，比如使用malloc和free。正确管理内存是防止内存泄露和指针错误的关键。

4. 算法的时间复杂度
? ??插入和删除操作的平均时间复杂度是O(n)，因为它们可能需要移动顺序表中的一半元素。这告诉我们，对于需要频繁插入和删除的应用场景，链表可能是更好的选择。

5. 理解引用传递
? ?在删除操作中，使用引用型参数来返回被删除的元素值。这种参数传递方式允许函数内部修改变量的值，而这些修改在函数外部也是可见的。

6.理解数据结构的适用场景
顺序表适合用于元素数量变化不大且主要进行查找操作的场景。

总的来说，通过学习顺序表的基本操作和特性，我们不仅能够更好地实现和使用顺序表，还能够加深对数据结构和算法选择的理解。在实际编程中，这些知识能够帮助我们写出更高效、更可靠的代码。