【数据结构】_顺序表

目录

1. 概念与结构

1.1 静态顺序表

1.2 动态顺序表

2. 动态顺序表实现

2.1 SeqList.h

2.2 SeqList.c

2.3 Test_SeqList.c

3. 顺序表性能分析

---

线性表是n个具有相同特性的数据元素的有限序列。

常见的线性表有：顺序表、链表、栈、队列、字符串等；

线性表在逻辑上是连续的线性结构，在物理结构上并不一定是连续的。

线性表在物理上存储时，通常以数组和链式结构的形式存储，分别称之为顺序表和链表。

本文介绍顺序表。

1. 概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构，一般情况下采取数组存储，在数组上完成数据的增删查改；

要求数据必须从第一个位置开始连续存放；

顺序表在逻辑上是连续的，在物理上也是连续的；

1.1 静态顺序表

#define N 100
typedef int SLDataType;
// 静态顺序表
typedef struct SeqList{SLDataType arr[N]; // 定长数组size_t size;  // 有效数据个数
}SeqList;

在定义时使用定长数组，会造成数组大小若太小则导致不够用，数组若太大则导致空间浪费； 

1.2 动态顺序表

#define N 100
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList {SLDataType* arr;size_t size;    // 有效数据个数size_t capacity;  // 空间大小
}SeqList;

在定义时仅给定数组首元素地址，并且基于size和capacity实现动态增容，相较而言更灵活。

注：1、通常会将顺序表的结构体命名为struct SeqList，即Sequence List；

2、建议目录结构：（注意自定义头文件的包含）

.h头文件：顺序表结构、声明顺序表的方法；

.c/.cpp源文件：实现顺序表的方法+测试；

3、为便于修改程序，通常会将顺序表结构体中的数据类型进行重命名，可命名为SLDataType；

      为便于编写程序，通常也会对顺序表结构体进行重命名，可重命名为SeqList或SL；

2. 动态顺序表实现

2.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef int SLDataType;
typedef struct SeqList {SLDataType* arr;int size;   // 有效数据个数int capacity;  // 空间大小
}SL;
// 空间检查
void SLCheckCapacity(SL* psl);
// 打印
void SLPrint(SL* psl);
// 初始化
void SLInit(SL* psl);
// 销毁
void SLDestory(SL* psl);
// 尾插
void SLPushBack(SL* psl, SLDataType x);
// 头插
void SLPushFront(SL* psl, SLDataType x);
// 尾删
void SLPopBack(SL* psl);
// 头删
void SLPopFront(SL* psl);
// 指定位置插入
void SLInsert(SL* psl,int pos, SLDataType x);
// 指定位置删除
void SLErase(SL* psl,int pos);
// 查找
int SLFind(SL* psl, SLDataType x);
// 修改
void SLModify(SL* psl, int pos, SLDataType x);

2.2 SeqList.c

#include "SeqList.h"
// 初始化
void SLInit(SL* psl) {psl->arr = NULL;psl->size = psl->capacity = 0;
}
// 销毁
void SLDestory(SL* psl) {if (psl->arr) {free(psl->arr);}psl->arr = NULL;psl->size = psl->capacity = 0;
}
// 打印
void SLPrint(SL* psl) {assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->arr[i]);}printf("\n");
}
// 空间检查
void SLCheckCapacity(SL* psl) {if (psl->capacity == psl->size) {// 常以2倍增容int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(psl->arr, newCapacity*sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail\n");exit(1);}psl->arr = tmp;psl->capacity = newCapacity;}
}
// 尾插
void SLPushBack(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);// 写法1/*psl->arr[psl->size] = x;psl->size++;*/// 写法2psl->arr[psl->size++] = x;
}
// 头插
void SLPushFront(SL* psl, SLDataType x) {assert(psl);SLCheckCapacity(psl);int count = psl->size;// 写法一while (count) {psl->arr[count] = psl->arr[count-1];count--;}// 写法二//for (int i = psl->size; i > 0; i--) {//	psl->arr[i] = psl->arr[i - 1];//}psl->arr[0] = x;psl->size++;
}
// 尾删
void SLPopBack(SL* psl) {assert(psl);assert(psl->size);psl->size--;
}
// 头删
void SLPopFront(SL* psl) {assert(psl);assert(psl->size);for (int i = 0; i < psl->size - 1; i++) {psl->arr[i] = psl->arr[i+1];}psl->size--;
}
// 指定位置插入
void SLInsert(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos>=0 && pos<psl->size);SLCheckCapacity(psl);for (int i = psl->size; i >psl->size - pos;i--) {psl->arr[i] = psl->arr[i-1];}psl->arr[pos] = x;psl->size++;
}
// 指定位置删除
void SLErase(SL* psl, int pos) {assert(psl);assert(pos >= 0 && pos < psl->size);for (int i = pos; i < psl->size - 1; i++) {psl->arr[i] = psl->arr[i + 1];}psl->size--;
}
// 查找
int SLFind(SL* psl, SLDataType x) {assert(psl);for (int i = 0; i < psl->size; i++) {if (psl->arr[i] == x)return i;}return -1;
}
// 修改
void SLModify(SL* psl, int pos, SLDataType x) {assert(psl);assert(pos >= 0 && pos < psl->size);psl->arr[pos] = x;
}

2.3 Test_SeqList.c

#include"SeqList.h"
int main() {SL sl1;SLInit(&sl1);printf("Test SLPushBack:PushBack5~10：\n");SLPushBack(&sl1, 5);SLPushBack(&sl1, 6);SLPushBack(&sl1, 7);SLPushBack(&sl1, 8);SLPushBack(&sl1, 9);SLPushBack(&sl1, 10);SLPrint(&sl1);printf("TestPushFront:PushFront 4~2：\n");SLPushFront(&sl1, 4);SLPushFront(&sl1, 3);SLPushFront(&sl1, 2);SLPrint(&sl1);printf("TestPopBack:PopBack 10：\n");SLPopBack(&sl1);SLPrint(&sl1);printf("TestPopFront:PopFront 2：\n");SLPopFront(&sl1);SLPrint(&sl1);printf("TestInsert:Insert arr[4]=99：\n");SLInsert(&sl1, 4, 99);SLPrint(&sl1);printf("TestErase:Erase arr[3]：\n");SLErase(&sl1, 3);SLPrint(&sl1);printf("TestFind: Find 99：\n");int retIndex = SLFind(&sl1, 99);printf("The index of 99 is: %d\n", retIndex);printf("TestModify:Modify 99 to 100：\n");SLModify(&sl1, 3, 100);SLPrint(&sl1);SLDestory(&sl1);
}

测试用例运行结果：

注：1、关于初始化与扩容问题：（方法多样，逻辑完整即可）

上文示例为SLInit使得psl->capacity初值为0，从而在SLCheckCapacity中对于0容量的扩容不能采取一概而论的二倍扩容法，上例使用三目操作符:?使得capacity被赋值为4。

也可在SLInit中就对capacity赋予一个初值，但对应的psl->arr就不可再赋值为NUL了，也需对应malloc相应大小的空间；

2、注意指定位置插入SLInsert与指定位置删除SLErase对pos参数的判定区别：

对于SLInsert，pos可取值size，即实现尾插效果；

对于SLErase，pos不可取值size，arr[psl->size]实际是数组arr最后一个有效数据的下一个位置；

3. 顺序表性能分析

优点：物理空间连续：便于利用下标随机访问；

缺点：（1）空间不够需扩容。

① 需要申请新的空间，拷贝数据，释放旧空间，有一定性能消耗；

② 一般增容呈2倍增长，存在空间浪费；

（2）头部或者中间位置的插入删除时涉及数据的移动，时间复杂度为O(N)，效率低下；

注：越界是不一定报错的，系统对于越界的检查是设岗抽查，以VS为例：

    int a[10];a[10] = 1;a[11] = 1;

当我们运行如上代码，系统会报错：

再运行下文代码：

    int a[10];a[12] = 1;a[13] = 1;

系统不会报错。说明系统只重点检查部分位置的越界情况。