【数据结构】线性表

2024-07-12 09:10| 来源: 网络整理| 查看: 265

线性表的物理/存储结构之——顺序表

【写在前面】本博客是笔者按照2021王道数据结构考研复习指导的视频课程整理的笔记，均已用编译器测试过可行，部分函数按照老师的提示做了一些代码健壮性的提升，可以放心使用。

目录导航（点击跳转）线性表的物理/存储结构之——顺序表一、顺序表的相关知识1.1、顺序存储的概念1.2、如何知道一个数据元素的大小二、顺序表的实现：静态分配2.1、静态分配2.2、静态分配一个存放整型数据的顺序表，初始化顺序表，并输出2.3、【注】如果不给data[i]赋初值，则会输出内存中遗留的脏数据。2.4、其他笔记三、顺序表的实现：动态分配3.1、动态分配3.2、动态分配的关键：动态的申请和释放内存空间——malloc及free函数的使用2.1 malloc函数 3.3、扩大动态分配顺序表的内存空间四、顺序表的特点五、顺序表的基本操作5.1、插入操作（静态分配）5.2、删除操作5.3、按位查找：时间复杂度O(1)5.4、按值查找：时间复杂度最好O(1)、最坏O(n)、平均O(n) 六、测试代码

一、顺序表的相关知识 1.1、顺序存储的概念

顺序存储：是指把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

1.2、如何知道一个数据元素的大小

C语言中为sizeof(ElemType) ElemType就是你的顺序表中存放的数据元素类型。 eg：

sizeof(int)=4B; sizeof(Customer)=8B;//Customer为包含两个整型元素的结构体二、顺序表的实现：静态分配 2.1、静态分配使用数组的方式来存放顺序表，数组的长度大小一旦确定了之后就不可以改变，这是静态数组的特点。分配一整片连续的存储空间，大小为MaxSize*sizeof(ElemType)。 #define Maxsize 10 //宏定义一个常量，定义最大长度 typedef struct{ ElemType data[MaxSize]; //定义了一个静态数组，大小为Maxsize，用来存放数据元素 int length; //顺序表的当前长度 }SqList; //Sq表示sequence（顺序、序列） //自己写代码的时候ElemType是什么类型吧ElemType替换掉就可以了。 2.2、静态分配一个存放整型数据的顺序表，初始化顺序表，并输出 #include #define Maxsize 10 //定义最大长度 typedef struct { int data[Maxsize]; //定义一个长度为Maxsize的数组用来存放数据元素 int length; //顺序表的当前长度 }SqList; //基本操作——初始化一个顺序表 void InitList(SqList &L) { for (int i = 0;i for (int i = 0;i SqList L; //声明一个顺序表 InitList(L); //初始化顺序表 PrintList(L); return 0; }

打印输出内容：在这里插入图片描述

2.3、【注】如果不给data[i]赋初值，则会输出内存中遗留的脏数据。

测试如下。将上一个代码中的初始化函数改为如下内容，编译测试，输出如下。

//基本操作——初始化一个顺序表 void InitList(SqList &L) { //for (int i = 0;i < Maxsize;i++) { // L.data[i] = 0; //将所有数据元素设置为默认初始值0 //} L.length = 0; }

打印输出内容：在这里插入图片描述【注】而实际上上面的用i int *data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度 }SeqList; //顺序表的定义类型（动态分配方式） //基本操作——初始化一个顺序表 void InitList(SeqList &L) { //用malloc函数申请一片连续的存储空间 L.data = (int *)malloc(sizeof(int)*InitSize); L.length = 0; L.MaxSize = InitSize; } //增加动态数组的长度 void IncreaseSize(SeqList &L,int len) { int *p = L.data; L.data = (int *)malloc(sizeof(int)*(L.MaxSize+len));//新申请一篇长度为Maxsize+len的区域 for (int i = 0;i for (int i = 0;i SeqList L; //声明一个顺序表 InitList(L); //初始化顺序表 IncreaseSize(L,5); PrintList(L); return 0; }

VS中编译的打印输出内容：在这里插入图片描述内存创销过程：

四、顺序表的特点随机访问：可以在O(1)时间内找到第i个元素（代码实现为data[i-1]，静态分配动态分配都一样）。存储密度高：每个节点只存储数据元素（而链式存储中还要存放指向下一个数据元素的指针）。拓展容量不方便（静态分配方式不能拓展容量，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）。插入、删除操作不方便，需要移动大量的元素。五、顺序表的基本操作 5.1、插入操作（静态分配） //基本操作：插入元素 void ListInsert(SqList &L, int i, int e) { for (int j = L.length;j >= i;j--) { L.data[j] = L.data[j - 1]; } L.data[i - 1] = e; L.length++; }

增加代码的健壮性，修改后：

//基本操作：插入元素 bool ListInsert(SqList &L, int i, int e) { if(iL.length+1){ //判断i的范围是否有效，无效返回false return false; } if (L.length >= Maxsize) { //当前存储空间已满，不能插入 return false; } for (int j = L.length;j >= i;j--) { L.data[j] = L.data[j - 1]; } L.data[i - 1] = e; L.length++; return true; }

时间复杂度分析：最深层循环L.data[j] = L.data[j - 1]; 最好O(1)、最坏O(n)、平均O(n).

5.2、删除操作 //基本操作：删除位序为i的元素 bool ListDelete(SqList &L, int i, int &e) { if (iL.length) { return false; } e = L.data[i - 1]; for (int j = i;j return L.data[i - 1];//动态和静态都是用这一条查找 } 5.4、按值查找：时间复杂度最好O(1)、最坏O(n)、平均O(n) int LocateElem(SeqList L, int e) { for (int i = 0;i

【本文地址】

公司简介

联系我们