数据结构-顺序表的实现 [王道]

本博客记录个人寒假学习内容。此篇博客内容为 顺序表的定义。

博客中截图来自王道数据结构公开课

目录

顺序表的定义

顺序表的特点

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

顺序表的实现--动态分配

顺序表的定义--知识结构框架

顺序表的定义

>线性表是具有相同(每个数据元素所占的空间一样大)数据类型的个数据元素的有限序列。

>顺序表：用顺序存储方式实现的线性表。

>顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

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

-- 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;
}