数据结构之顺序表——王道
一.线性表的定义（逻辑结构）和基本操作（运算）
由绪论知，
学习一个具体的数据结构时需关注数据结构的：
- 逻辑结构（数据元素之间存在的逻辑关系，线性结构和非线性结构，线性结构如队列、链表等，非线性结构如树、图）
- 物理结构（存储结构）(逻辑结构用计算机语言的实现，包括顺序存储，链式存储，索引存储和散列存储）
- 数据的运算
用不同存储结构实现线性表不同
线性表： 大白话：数据被一条线串在一起
相同数据类型的n个数据元素的有限序列。
线性表的创销、增删改查
改之前要查
InitList（&L）：初始化表，构造一个空的线性表L，分配内存空间。
DestroyList（&L）：销毁线性表，释放线性表L所占的内存空间。
ListInsert（&L,i，e)：插入操作，在第i个位置上插入元素e
ListDelete(&L,i,&e)：删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。
LocateElem（L，e）：按值查找
GetElem（L，i）按位查找
- 这些接口具有抽象性，一般函数定义为<返回值类型>函数名（<参数1类型> 参数1，······），因为这些元素可以存储各种类型变量
- 函数名，参数名等都可以变
- &：把参数的修改结构带回来
- 位序从1开始，程序下标从0开始
二.顺序表的定义
线性表——用顺序存储的方式实现线性表
顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
如何知道数据元素大小？
答：sizeof（ElemType）
tyepedef struct{
int num;
int people;
}Customer;
sizeof(Customer):8B
下面顺序表实现方式：静态分配
#define int N 10
typedef int ElemType;
typedef struct{
ElemType a[N];//用静态数组存放数据元素
int length;//顺序表当前长度
}Customer;
给各个空间分配连续存储空间，大小：N*sizeof（ElemType）
//定义顺序表
#include <stdio.h>
#typedef MaxSize 10
typedef int ElemType;
typedef struct
{
ElemType a[MaxSize];
int length;//顺序表当前长度
}SqList;
//初始化顺序表
void InitList(SqList &L){//用SqList定义顺序表L
for(int i=0;i<MaxSize;i++)
L.data[i]=0;//初始化i中的所有数据元素，可省略
L.length=0;//长度初始化为0
}
int main(){
SqList L;//声明一个顺序表
InitList(L);//初始化顺序表
return 0;
}
静态分配有局限性，可动态分配
#define InitList 10//初始长度为10
typedef struct
{
ElemType*a;//动态分配数组的指针
int MaxSize;//最大数组长度
int length；//当前数组长度
}SqList;
动态申请和释放空间在C语言中有malloc和free
L.data=(ElemType*)malloc(sizeof(ElemType)* InitSize);
因为存储空间存储数据元素，因此需要把malloc申请的空间强转为ElemType类型指针。
InitSIze为malloc函数的参数，指明要分配多少连续空间
malloc和free包含在#include<stdlib.h>文件中
三.顺序表的插入删除
1.插入操作
ListInsert（&L,i，e);在线性表L第i个位置上插入指定元素e
顺序表长度：5，b的后驱结点，d的前驱节点
基于静态顺序表实现
#include <stdio.h>
#typedef MaxSize 10
typedef int ElemType
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList &L)
{
L.length=0;//在L数组上所以都要加L.
}
void InsertList(SqList &L,int i,int e){
if(i<1||i>L.length+1||L.length>=MaxSize)//要有健壮性
{
return false;//插入失败
}
//for(int a=i-1;a<MaxSize:a++)
//错误，应该从最后一个往后移，否则会被覆盖
for(int a=L.length;a>=i;a--)
{
L.data[a+1]=L.data[a];//记得加L，因为是数组
}
data[i-1]=e;//i是位序
length++;
return true;//插入成功
}
int main()
{
SqList(&L);
InitList(L);
//省略一些代码，插入数据
InsertList(&L,3,7);
return 0;
}//O（n）时间复杂度，n=L.length
2.顺序表的删除
DeleteList(&L,i,&e):在线性表L中的第i个位置，并用e返回删除元素的值。
void DeleteList(SqList &L,int i,int* e)
{
if(i<1||i>L.length)
return false;
//L.data[i-1]=e;//应该把值赋给e
e=L.data[i-1];
for(int j=i;j<L.length;j++)//j<L.length
{
L.data[j]=L.data[j+1];
}
L.length--;//记得把L.Length的值-1
return true;
}
int main()
{
SqList(&L);
InitList(L);
int e=-1;//用变量e把删除的元素带回来
//插入一些数据
if(DeleteList(L,3,e))
printf("已删除第3个位置的值，值为%d\n",e);
else
printf("不合法，无法删除");
return 0;
}//时间复杂度：O(n)
定义的的删除操作e的变量是引用类型的&e
所以这里的e和main函数里定义的e在内存中对应的是同一份数据
注意
- 更改length的值
- 删除的是数组下标还是位序
- 代码要有健壮性
四.顺序表的查找
代码实现与时间复杂度分析：
- 按位查找
- 按值查找
1.按位查找
GetElem（L，i）：在顺序表L中查找第i个位置的元素的值
1.1静态分配
Elemtype GetElem(SqList L,int i)
{
//判断i的值是否合法
return L.data[i-1];//直接返回第i-1个位置的值
}
1.2动态分配
#include <stdio.h>
#include <stdlib.h>
#typedef InitSize 10//定义初始长度10
typedef int ElemType;
typedef struct
{
ElemType* data;//动态分配数组的指针
int MaxSize;//当前能容纳的最大数组
int length;//占用的数组长度
}SqList;
void InitList(SqList &L)
{
//用malloc申请一片连续空间
ElemType* data=(ElemType*)malloc(InitSize*sizeof(ElemType);
L.MaxSize=InitSize;
L.length=0;
}
ElemType GetElem(SqList L,int i)
{
int n=0;
L.MaxSize=(ElemType*)malloc(sizeof(ElemType)*n);
return a[i-1];
}
时间复杂度：O(1)
表示每个数组下标对应哪几个数组的数据，与指针类型有关
符合顺序表随机存储的特性，因为顺序表的所有数据连续存放，且数据类型相同，所占空间一样大
2.按值查找
LocateElem(L,e); 在L中查找具有给定元素关键字值的元素。如果能找到，返回元素所在的存放位置
ElemType LocateElem(SqList L,ElemType e)
{
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i-1;
return 0;//退出循环，表明查找失败
}时间复杂度：O(n)
结构类型不能直接用==判断两个结构体是否相等，需要依次对比各个结构体的分量是否相等
bool Custom(Customer a,Cumstomer b)
{
if(a.num==b.num && a.people==b.people)
return true;
else
return false;
}
原文地址：https://blog.csdn.net/weixin_73236117/article/details/142902683
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！