DS线性表之顺序表的讲解和实现(1)

---

前言

  哈哈，第一篇干货内容，这还是不算太难的！

---

一、线性表

线性表的具体分类

我们今天讲的就是顺序存储的顺序表，其中链式存储我们后面再来讲解~

线性表的概念与存储

线性表（linear list）n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等。线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储

二、顺序表

顺序表的概念

顺序表属于线性表的其中一种。顺序表在逻辑、物理结构上是连续，顺序表底层逻辑实现一般是数组。关于物理结构上连续是指一段物理地址连续的存储单元依次存储数据元素的结构

顺序表的分类

1. 静态顺序表：使用定长数组存储元素。（缺陷：空间给少了不够用，给多了造成空间浪费）
   

2. 动态顺序表：使用动态开辟的数组存储。（优势：动态开辟空间，使用相对灵活，相比于静态开辟空间也可以少空间浪费）
   

顺序表的接口实现

顺序表不仅仅只要下面实现的这些函数，且每个函数的实现方式也不是唯一的

我在前文说，数据结构的学习要以坚实的结构体、指针、动态内存管理等为基础，才可走的常远，如果你是第一次看见顺序表要实现那么多的接口的话，那应该是会蛮惊讶的

// SeqList.h
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h> // 断言用，下文会介绍

//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a; //指向动态开辟的数组
int size;      //有效数据个数
int capacity;  //容量空间的大小
}SL;

//初始化
void SeqListInit(SL* s);

//销毁
void SeqListDestroy(SL* s);

//头插
void SeqListPushFront(SL* s, SLDataType x);

//尾插
void SeqListPushBack(SL* s, SLDataType x);

//头删
void SeqListPopFront(SL* s);

//尾删
void SeqListPopBack(SL* s);

//指定位置插入
void SeqListInsert(SL* s, int pos, SLDataType x);

//指定位置删除
void SeqListErase(SL* s, int pos);

//大小
int SeqListLength(SL* s);

//修改指定位置数据
void SeqListModify(SL* s, int pos, SLDataType x);

// 顺序表查找
int SeqListFind(SL* s, SLDataType x);

//打印
void SeqListPrint(SL* s);

// SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//打印
void SeqListPrint(SL* s)
{
assert(s); //S指针不为空
for (int i = 0; i < s->size; i++)
{
printf("%d ", s->a[i]);
}
printf("\n");
}

//初始化
void SeqListInit(SL* s)
{
assert(s);
assert(s->a); //数据起始地址不为空才初始化
s->a = NULL;
s->size = s->capacity = 0;
}

//销毁  
void SeqListDestroy(SL* s)
{
assert(s);
free(s->a);
s->a = NULL;
s->size = s->capacity = 0;
}

//检查容量
void SeqListCheckCapacity(SL* s)
{
assert(s);
if (s->size == s->capacity)
{
//两种情况 一种没有元素 一种满元素扩容
int newcapacity = s->capacity == 0 ? 4 : 2 * s->capacity;
//开辟空间
SLDataType* tmp = (SLDataType*)realloc(s->a, sizeof(SLDataType) * newcapacity);

//判断是否开辟成功
if (tmp == NULL)
{
//失败则直接退出程序
printf("realloc fail\n");
exit(-1);
}
else
{
//把空间和容量给原来顺序表
s->a = tmp;
s->capacity = newcapacity;
}
}
}

//头插
void SeqListPushFront(SL* s, SLDataType x)
{
assert(s);
SeqListCheckCapacity(s);
int end = s->size - 1;
while (end >= 0)
{
s->a[end + 1] = s->a[end];
end--;
}
s->a[0] = x;
s->size++;
}

//尾插
void SeqListPushBack(SL* s, SLDataType x)
{
assert(s);
//检查容量空间  注意形参写什么定义为一级指针用一级指针
SeqListCheckCapacity(s);
s->a[s->size] = x;
s->size++;
}

//头删
void SeqListPopFront(SL* s)
{
assert(s);
assert(s->size > 0);
int start = 0;
while (start < s->size - 1)
{
s->a[start] = s->a[start + 1];
start++;
}
s->size--;
}

//尾删
void SeqListPopBack(SL* s)
{
assert(s);
assert(s->size > 0);
s->size--;
}

//顺序表查找 
int SeqListFind(SL* s, SLDataType x)
{
assert(s);
assert(s->size > 0);
for (int i = 0; i < s->size; i++)
{
if (s->a[i] == x);
return i;
}
return -1;
}

//指定位置插入 pos是下标
void SeqListInsert(SL* s, int pos, SLDataType x)
{
assert(s);
//pos在数组大小范围内
assert(pos >= 0 && pos < s->size);
SeqListCheckCapacity(s);
int end = s->size - 1;
while (end >= pos)
{
s->a[end + 1] = s->a[end];
end--;
}
s->a[pos] = x;
s->size++;
}

//指定位置删除
void SeqListErase(SL* s, int pos)
{
assert(s);
assert(pos >= 0 && pos < s->size);
assert(s->size > 0);
int start = pos;
while (start < s->size - 1)
{
s->a[start] = s->a[start + 1];
start++;
}
s->size--;
}

//大小
int SeqListLength(SL* s)
{
assert(s);
return s->size;
}

// 修改
void SeqListModify(SL* s, int pos, SLDataType x)
{
assert(s);
s->a[pos] = x;
}

顺序表接口函数实现思想

关于上述的接口实现，你可能会有很多疑问，那么敬请细览以下图片
其实这个顺序表用的不多，至少跟我们下一篇的单链表比起来，但是作为我们的第一篇，那还是蛮有教学意义的

顺序表接口的一些实现细节补充

1. 当有效元素个数等于当前空间容量为了下一次的插入元素，需要进行扩容操作。由于扩容功能需要多次调用，对此可以考虑设计为一个接口SLChekckCapacity进行复用
2. 空表无法进行删除数据，需要在删除操作之前进行断言检查assert(phead->a)，我们得先实例化（分配内存空间，即给数组指针a、数组大小size、数组容量capacity分配一块内存）
3. 尾插的时候，这里删除不是将数据设为0就是删除数据。正确的做法是，通过size（有效数据个数）个数控制。顺序表不访问size外的无效数据（否则会报错），那么从某种意义上是删除了数据，不需要空间是否浪费，尾插数据时，可能下次还是用到那个空间

班里有位同学退学，班里人数少一位，同学还是存在，只是座位没有它，同学就是数据，座位就是空间

4. 遍历顺序表的时候，如果满足条件返回当前位置的下标，没有找到返回一个负数表示找不到
5. 支持下标随机访问，但是在实现插入和删除操作过程中，通过大量的移动数据，效率较低，空间不足需要扩容并且需要付出一定的代价，可能存在空间浪费

---

总结

  下篇就是单链表！

原文地址：https://blog.csdn.net/2301_80392199/article/details/142877642

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！