数据结构之顺序表——王道

时间：2024-10-15 07:07:19

文章目录

  • 一.线性表的定义（逻辑结构）和基本操作（运算）
  • 二.顺序表的定义
  • 三.顺序表的插入删除
    • 1.插入操作
    • 2.顺序表的删除
  • 四.顺序表的查找
    • 1.按位查找
      • 1.1静态分配
      • 1.2动态分配
    • 2.按值查找

一.线性表的定义（逻辑结构）和基本操作（运算）

由绪论知，
学习一个具体的数据结构时需关注数据结构的：

  1. 逻辑结构（数据元素之间存在的逻辑关系，线性结构和非线性结构，线性结构如队列、链表等，非线性结构如树、图）
  2. 物理结构（存储结构）(逻辑结构用计算机语言的实现，包括顺序存储，链式存储，索引存储和散列存储）
  3. 数据的运算
    用不同存储结构实现线性表不同
    线性表： 大白话：数据被一条线串在一起
    相同数据类型的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. 按位查找
  2. 按值查找

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

在这里插入图片描述

相关文章