数据结构之顺序表

在了解顺序表之前我们需要先了解什么是线性表

1.线性表的定义

线性表(Linear List)：是n个具有相同特征的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串

线性表在逻辑上是线性结构，也就是说一条连续的直线。但在物理结构上并不一定是连续的

线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表

2.1顺序表的概念以及结构

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

2.2顺序表的类型

->1.静态顺序表：使用定长数组存储元素

开辟一个固定长度的数组，向数组中存储数据

缺点：

这样开辟的顺序表空间是固定的，如果我们需要存储的空间大于这个固定空间，那我们就需要重新来开辟空间，如果我们只需要存放几个数据，那就会浪费不少空间

->2.动态顺序表：使用动态开辟的数组存储

相比于静态顺序表的优点：

更加的灵活，不会出现空间不足或者浪费大量空间的情况，所以现实中基本都是使用动态顺序表

下面我们实将现动态顺序表

3.顺序表的增删查改

->1.实现顺序表所需要用到的接口

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4
typedef int SLDATATYPE;

//初始化
void INITSeqList(SL* ps);//清除顺序表
void SLDestroy(SL* ps);//增容
void IncrCapacity(SL* ps);//打印
void print(SL* ps);//尾插
void SLPushBack(SL* ps, SLDATATYPE x);//尾删
void SLPopBack(SL* ps);//头插
void SLPushFront(SL* ps, SLDATATYPE x);//头删
void SLPopFront(SL* ps);//顺序表再pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x);//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos);//查找元素
int SLFind(SL* ps, SLDATATYPE x);

->2.顺序表的创建

//顺序表的动态存储
typedef struct SeqList
{SLDATATYPE* a;int size;       //有效数据的个数int capacity;	//空间容量}SL;

->3.初始化

//顺序表初始化
void INITSeqList(SL* ps)
{assert(ps);ps->a = (SLDATATYPE*)malloc(sizeof(int) * INIT_CAPACITY);if (ps->a == NULL){perror("INITSeqList::malloc");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

->4.销毁数据表

//销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}

->5.在进行增删的时候检查一下空间是否为满

//检查容量是否已满
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDATATYPE* ptr = (SLDATATYPE*)realloc(ps->a, sizeof(int) * (INIT_CAPACITY * 2));if (NULL == ptr){perror("IncrCapacity::realloc");return;}ps->a = ptr;ps->capacity *= 2;}
}

->6.打印

//打印内容
void print(SL* ps)
{assert(ps);for(int i = 0; i < ps->size; i++)printf("%d ", ps->a[i]);printf("\n");
}

->7.头插

//头插
void SLPushFront(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);//整体向后移动for (int end = ps->size - 1; end >= 0; --end){ps->a[end + 1] = ps->a[end];}ps->a[0] = x;++ps->size;
}

->8.头删

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

->9.尾插

//尾插
void SLPushBack(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}

->10.尾删

//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->a[ps->size--] = 0;
}

->11.在顺序表pos处增加元素

//在顺序表pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];}ps->a[pos] = x;++ps->size;
}

->12.删除在pos位置的元素

//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);SLDATATYPE begin = pos + 1;while (begin < ps->size){ps->a[begin] = ps->a[begin - 1];++begin;}--ps->size;
}

->13.顺序表查找

//查找
int SLFind(SL* ps, SLDATATYPE x)
{assert(ps);for (int i = 0; i < ps->size - 1; ++i){if (ps->a[i] == x)printf("找到了！！！%d\n", i);}return -1;
}

4.源代码

->1.test.c

#include "SeqList.h"int main()
{SL a;INITSeqList(&a);test();int input = -1;//尾插SLPushBack(&a,1);print(&a);SLPushBack(&a, 2);print(&a);SLPushBack(&a, 3);print(&a);SLPushBack(&a, 4);print(&a);//尾删SLPopBack(&a);print(&a);//在pos位置插入8SLInsert(&a, 3, 8);print(&a);//查找该元素的位置，返回下标int pos = SLFind(&a, 2);return 0;
}

->2.SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4
typedef int SLDATATYPE;typedef struct SeqList
{SLDATATYPE* a;int size;       //有效数据的个数int capacity;	//空间容量}SL;//初始化
void INITSeqList(SL* ps);//清除顺序表
void SLDestroy(SL* ps);//增容
void IncrCapacity(SL* ps);//打印
void print(SL* ps);//尾插
void SLPushBack(SL* ps, SLDATATYPE x);//尾删
void SLPopBack(SL* ps);//头插
void SLPushFront(SL* ps, SLDATATYPE x);//头删
void SLPopFront(SL* ps);//顺序表再pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x);//顺序表删除再pos位置的元素
void SLErase(SL* ps, SLDATATYPE pos);//查找元素
int SLFind(SL* ps, SLDATATYPE x);

->3.SeqList.c

#include "SeqList.h"//顺序表初始化
void INITSeqList(SL* ps)
{assert(ps);ps->a = (SLDATATYPE*)malloc(sizeof(int) * INIT_CAPACITY);if (ps->a == NULL){perror("INITSeqList::malloc");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}//清除顺序表
void SLDestroy(SL* ps)
{assert(ps);assert(ps->size > 0);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->size = 0;
}//打印内容
void print(SL* ps)
{assert(ps);assert(ps->size > 0);for(int i = 0; i < ps->size; i++)printf("%d ", ps->a[i]);printf("\n");
}//检查容量是否已满
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDATATYPE* ptr = (SLDATATYPE*)realloc(ps->a, sizeof(int) * (INIT_CAPACITY * 2));if (NULL == ptr){perror("IncrCapacity::realloc");return;}ps->a = ptr;ps->capacity *= 2;}
}//尾插
void SLPushBack(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);ps->a[ps->size--] = 0;
}//头插
void SLPushFront(SL* ps, SLDATATYPE x)
{assert(ps);SLCheckCapacity(ps);for (int end = ps->size - 1; end >= 0; --end){ps->a[end + 1] = ps->a[end];}ps->a[0] = x;++ps->size;
}//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}--ps->size;
}//在顺序表pos处增加元素
void SLInsert(SL* ps, SLDATATYPE pos, SLDATATYPE x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];}ps->a[pos] = x;++ps->size;
}//删除顺序表pos处的元素
void SLErase(SL* ps, SLDATATYPE pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);SLDATATYPE begin = pos + 1;while (begin < ps->size){ps->a[begin] = ps->a[begin - 1];++begin;}--ps->size;
}//查找
int SLFind(SL* ps, SLDATATYPE x)
{assert(ps);for (int i = 0; i < ps->size - 1; ++i){if (ps->a[i] == x)printf("找到了！！！%d\n", i);}return -1;
}

测试结果：