本博客记录个人寒假学习内容。此篇博客内容为 顺序表的定义。
博客中截图来自王道数据结构公开课
目录
顺序表的定义
顺序表的特点
顺序表的实现--静态分配
顺序表的实现--动态分配
顺序表的定义--知识结构框架
顺序表的定义
>线性表是具有相同(每个数据元素所占的空间一样大)数据类型的
个数据元素的有限序列。
>顺序表：用顺序存储方式实现的线性表。
>顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。
如何知道一个数据元素的大小？
-- C语言中，使用sizeof(ElemType)
顺序表的特点
优点：
(1)随机访问，即可以在O(1)时间内找到第i个元素。因为顺序表是线性表在内存空间中连续存放的，在代码中可以通过data[i-1]来实现随机访问(静态分配、动态分配都一样)。
(2)存储密度高，每个节点只存储数据元素。若线性表采用链表存储，则每个节点还需要额外存储指针内容。
缺点：
(1)拓展容量不方便。采用静态分配方式，数组长度不可以改变；采用动态分配方式，拓展长度的时间复杂度也比较高，因为此过程需要复制原来的内容到新开辟的内存空间中)。
(2)插入、删除操作不方便，需要移动大量元素。插入操作平均需要移动n/2个元素，删除操作平均需要移动(n-1)/2个元素。
顺序表的实现--静态分配
静态分配在声明一个顺序表时，就已经为其分配了数组空间，因此初始化时只需将顺序表当前长度设为0。
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表当前长度length
}SqList; //顺序表的类型定义(静态分配方式)
//Sq: sequence 顺序，序列
//SqList L; //声明一个顺序表
void InitList(SqList &L){
L.length = 0; //顺序表初始长度为0
}Q：如果“数组”存满了怎么办？
A：顺序表的表长，最初确定后就无法进行更改。因为存储空间是静态的。
Q：如果在最初就声明一个很大的内存空间，会存在什么问题?
A：会浪费存储空间。比如在一段代码中只用到了长度为10的数组，但是最初却申请了10000个存储单元空间，这样会浪费空间。
顺序表的实现--动态分配
动态分配的关键点：动态申请 和 释放内存空间。
C语言： malloc、free函数
malloc函数返回一个指针，需要强制转型为自己定义的数据元素的类型指针。
malloc函数，指明需要分配多大的连续内存空间。
>L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
C++ ： new、delete关键字
代码：
#include <iostream>
#include <stdlib.h> //malloc free函数的头文件
#define InitSize 10 // 顺序表的初始长度
using namespace std;
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)
void InitList(SeqList &L){
//使用malloc函数申请一片连续的存储空间
//malloc函数返回的是所申请的存储空间的起始地址
L.data = (int *)malloc(InitSize*sizeof(int)); //分配存储空间
L.length = 0; //顺序表初始长度为0
L.MaxSize = InitSize; //初始存储数量
}
int main(){
SeqList L; //声明一个顺序表
InitList(L); //初始化顺序表
return 0;
}操作实例： 增加动态数组的长度
内存分配情况 可看图右。将原始数据复制到新开辟的内存中，最终释放掉原来的内存空间。
//#include<bits/stdc++.h>
#include <iostream>
#include <stdlib.h> //malloc free函数的头文件
#define InitSize 10 // 默认的最大长度
using namespace std;
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SeqList &L){
//使用malloc函数申请一片连续的存储空间
//malloc函数返回的是所申请的存储空间的起始地址
L.data = (int *)malloc(InitSize*sizeof(int));
L.length = 0; //当前的有效长度为0
L.MaxSize = InitSize; //赋值为默认最大长度
}
//增加动态数组的长度
void IncreaseSize(SeqList &L,int len){
int *p = L.data; //设置指针，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(){
SeqList L; //声明一个顺序表
InitList(L); //初始化顺序表
//往顺序表中随便插入5个元素
IncreaseSize(L,5);
return 0;
}
