【数据结构】知识点一：线性表之顺序表
内容导航
- 一、什么是线性表？
- 二、什么是顺序表？
- 1、顺序表的概念
- 2、顺序表的结构
- a. 静态顺序表：使用定长数组存储元素。
- b. 动态顺序表：使用动态开辟的数组存储。
- 三、顺序表的接口实现精讲
- 1.接口一：打印数据
- 2.接口二：表初始化
- 3.接口三：数据销毁
- 4.接口四：尾插数据
- 5.接口五：尾删数据
- 6.接口六：头插数据
- 7.接口七：头删数据
- 8.接口八：容量检查
- 9.接口九：任意位置的插入
- 9.接口九：任意位置的删除
- 10.接口十：任意数据的查找
- 四、源代码分享
- 1.SeqList.h
- 2.SeqList.c
- 3.test.c
一、什么是线性表？
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、什么是顺序表？
1、顺序表的概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
2、顺序表的结构
a. 静态顺序表：使用定长数组存储元素。
b. 动态顺序表：使用动态开辟的数组存储。
三、顺序表的接口实现精讲
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
1.接口一：打印数据
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLPrint(SL* ps1) //打印数据
{assert(ps1);for (int i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\n");
}
2.接口二：表初始化
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLInit(SL* ps1) //初始化顺序表，全部为0
{assert(ps1);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}
3.接口三：数据销毁
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLDestroy(SL* ps1) //销毁顺序表
{assert(ps1);if (ps1->a != NULL) {free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;}
}
4.接口四：尾插数据
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLPushBack(SL* ps1, SLDataType x) //尾插入
{assert(ps1);SLCheckCapacity(ps1); //检查容量ps1->a[ps1->size] = x;ps1->size++;
}
5.接口五：尾删数据
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLPopBack(SL* ps1) //尾删除
{assert(ps1);assert(ps1->size > 0); //有效数据为0则不需要删ps1->size--;
}
6.接口六：头插数据
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLPushFront(SL* ps1, SLDataType x) //头插入
{assert(ps1);SLCheckCapacity(ps1); //检查容量//往后挪动数据int end = ps1->size - 1;while (end >= 0){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[0] = x;ps1->size++;
}
7.接口七：头删数据
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLPopFront(SL* ps1) //头删除
{assert(ps1);assert(ps1->size > 0); //有效数据为0则不需要删//往前挪动数据int begin = 1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}
8.接口八：容量检查
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLCheckCapacity(SL* ps1) //检查空间是否充足，若否，使空间充足，头插尾插都要用到
{assert(ps1);if (ps1->size == ps1->capacity){int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = NewCapacity;}
}
9.接口九：任意位置的插入
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLInsert(SL* ps1, int pos, SLDataType x) //任意位置的插入
{assert(ps1);assert(pos >= 0 && pos <= ps1->size); //确保pos大小的有效性SLCheckCapacity(ps1); //检查容量//往后挪动数据int end = ps1->size - 1;while (end > pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++;
}
9.接口九：任意位置的删除
<font color=black size=4 font face=黑体" >代码之函数的定义：
void SLErase(SL* ps1, int pos) //任意位置的删除
{assert(ps1);assert(pos >= 0 && pos <= ps1->size); //确保pos大小的有效性//往前挪动数据int begin = pos+1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}
10.接口十：任意数据的查找
<font color=black size=4 font face=黑体" >代码之函数的定义：
int SLFind(SL* ps1, SLDataType x) //查找某个数据，找到返回下标，未找到返回-1
{assert(ps1);for (int i = 0; i < ps1->size; i++) //直接遍历查找{if (ps1->a[i] == x){return i;}}return -1;
}
四、源代码分享
1.SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;typedef struct SeqList
{SLDataType* a; //开辟的数组地址int size; //有效数据个数int capacity; //容量空间的大小
}SL;void SLPrint(SL* ps1); //打印数据
void SLInit(SL* ps1); //初始化顺序表，全部为0
void SLDestroy(SL* ps1); //销毁顺序表void SLPushBack(SL* ps1, SLDataType x); //尾插入
void SLPushFront(SL* ps1, SLDataType x); //头插入
void SLPopBack(SL* ps1); //尾删除
void SLPopFront(SL* ps1); //头删除void SLInsert(SL* ps1, int pos, SLDataType x); //任意位置的插入
void SLErase(SL* ps1, int pos); //任意位置的删除int SLFind(SL* psl, SLDataType x); //查找某个数据，找到返回下标，未找到返回-12.SeqList.c
#include"SeqList.h"void SLPrint(SL* ps1) //打印数据
{assert(ps1);for (int i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\n");
}void SLInit(SL* ps1) //初始化顺序表，全部为0
{assert(ps1);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}void SLDestroy(SL* ps1) //销毁顺序表
{assert(ps1);if (ps1->a != NULL) {free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;}
}void SLCheckCapacity(SL* ps1) //检查空间是否充足，若否，使空间充足，头插尾插都要用到
{assert(ps1);if (ps1->size == ps1->capacity){int NewCapacity = ps1->capacity == 0 ? 4 : ps1->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * NewCapacity);if (tmp == NULL){perror("realloc fail");return;}ps1->a = tmp;ps1->capacity = NewCapacity;}
}
void SLPushBack(SL* ps1, SLDataType x) //尾插入
{assert(ps1);SLCheckCapacity(ps1); //检查容量ps1->a[ps1->size] = x;ps1->size++;
}void SLPushFront(SL* ps1, SLDataType x) //头插入
{assert(ps1);SLCheckCapacity(ps1); //检查容量//往后挪动数据int end = ps1->size - 1;while (end >= 0){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[0] = x;ps1->size++;
}void SLPopBack(SL* ps1) //尾删除
{assert(ps1);assert(ps1->size > 0); //有效数据为0则不需要删ps1->size--;
}void SLPopFront(SL* ps1) //头删除
{assert(ps1);assert(ps1->size > 0); //有效数据为0则不需要删//往前挪动数据int begin = 1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}void SLInsert(SL* ps1, int pos, SLDataType x) //任意位置的插入
{assert(ps1);assert(pos >= 0 && pos <= ps1->size); //确保pos大小的有效性SLCheckCapacity(ps1); //检查容量//往后挪动数据int end = ps1->size - 1;while (end > pos){ps1->a[end + 1] = ps1->a[end];end--;}ps1->a[pos] = x;ps1->size++;
}void SLErase(SL* ps1, int pos) //任意位置的删除
{assert(ps1);assert(pos >= 0 && pos <= ps1->size); //确保pos大小的有效性//往前挪动数据int begin = pos+1;while (begin < ps1->size){ps1->a[begin - 1] = ps1->a[begin];begin++;}ps1->size--;
}int SLFind(SL* ps1, SLDataType x) //查找某个数据，找到返回下标，未找到返回-1
{assert(ps1);for (int i = 0; i < ps1->size; i++) //直接遍历查找{if (ps1->a[i] == x){return i;}}return -1;
}
3.test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"void menu()
{printf("********************************\n");printf("****1、尾插数据 2、尾删数据****\n");printf("****3、头插数据 4、头删数据****\n");printf("****5、打印数据 0、退出 ****\n");printf("********************************\n");
}int main()
{SL s;SLInit(&s);int option = 0;do{menu();printf("请输入你的选择:>");scanf("%d", &option);if (option == 1){printf("请依次输入你的要尾插数据个数和数据:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){int x = 0;scanf("%d", &x);SLPushBack(&s, x);}}else if (option == 2){printf("请依次输入你的要尾删数据的个数:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopBack(&s);}}else if (option == 3){printf("请依次输入你的要头插数据个数和数据:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){int x = 0;scanf("%d", &x);SLPushFront(&s, x);}}else if (option == 4){printf("请依次输入你的要头删数据的个数:>");int n = 0;scanf("%d", &n);for (int i = 0; i < n; i++){SLPopFront(&s);}}else if (option == 5){SLPrint(&s);}else if (option == 0){break;}else{printf("无此选项，请重新输入\n");}} while (option != 0);SLDestroy(&s);return 0;
}