【数据结构】静态顺序表

Hi，要再一次开始写关于数据结构相关的知识了。
之前写还是在学习数据结构的时候，现在是要加深一下这块的知识了。
我的数据结构专栏：数据结构与算法
在这一篇，我们先来实现一下静态顺序表。

首先，我们新建好我们的项目后，我们新建一个源文件test.c，用于测试我们静态表的功能；然后我们再新建一个源文件SeqList.c，用于实现顺表的基本操作，包括初始化、增删改查等;然后新建一个头文件SeqList.h，将我们定义好的顺序表结构以及函数的声明放在头文件中。

下面我们一步一步实现顺序表的基本操作。

定义顺序表的结构

我们使用结构体来定义顺序表的结构。

#define N 100
typedef int DataType;
typedef struct SeqList {DataType a[N];int size;
}SeqList;

首先，对于以上这几行代码，我们定义一个顺序表，它的优点是：

• 使用了宏定义，可以随时调整顺序表容量的大小，而不至于一下写“死”顺序表的容量。
• 使用了typedef 给数据类型int起了一个别名，而不至于限制了顺序表中数据的类型。
• size 用于记录当前顺序表的容量。
• 将结构体 struct SeqList 起个别名叫做，SeqList，方便我们的使用，不需要任何时候用到结构体的时候都写上struct了，更加简洁。

初始化顺序表

在定义好顺序表的结构之后，我们一一实现顺序表的基本功能。

首先，我们先来初始化一个顺序表。

//初始化一个顺序表
void InitSeqList(SeqList* p) {int n;p->size=0;printf("请输入元素的个数：\n");scanf("%d", &n);printf("请依次输入各元素：\n");for (int i = 0; i < n; i++){scanf("%d", &p->a[i]);p->size++;}printf("\n");
}

• 我们函数的参数通过SeqList类型的指针来实现，表示我们要初始化的顺序表。
• 通过传递指针参数，我们可以直接修改顺序表中内容。
• 也就是，可以修改顺序表中的两个成员，一个是用于存储顺序表的数组a[N],一个是记录顺序表当前个数的size。
• 该函数实现简单地交互，用户可以动态地向顺序表中存入数据。

此时我们一个简单地项目结构如下：


这里应该加上p->size=0；来对size进行一个初始化。

在下面一些基础的函数实现上面，就是在上面三个文件中不断的添加内容，完善我们的项目。

打印顺序表

刚刚我们实现了初始化顺序表的操作，然后实现打印顺序表各结点的值。

//打印顺序表
void PrintSeqList(SeqList* p)
{int i = 0;printf("顺序表各结点值为:\n");for (i = 0; i < p->size; i++)printf("%d ", p->a[i]);printf("\n");
}

这个函数很简单，就不过多解释了。

插入和删除

在上面，我们可以完成对顺序表创建、初始化、以及打印各结点的值，以便于查看顺序表的信息。
下面，我们接着实现，顺序表的数据的插入和数据的删除。
插入可以分为头插和尾插，删除可以分为头删和尾删。
下面我们一一实现。

头插

头插就是在顺序表的最前面插入一个数据，后面的数据依次右移。
然后我们代码实现：

//头插
void PushFront(SeqList* p,DataType x)
{//先来判断容量有没有满if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}for (int i = p->size ;i>=0; i--){p->a[i] = p->a[i - 1];}p->a[0] = x;p->size++;}

• 如果顺序表已满，则程序会打印错误信息，并通过 exit(-1) 终止程序。
• p->a[i] = p->a[i - 1]：将前一个元素的值赋值给当前位置。

尾插

当我们头插结束后，尾插就变得很简单很简单了，只需要判断一下顺序表有没有满，没有满的话，在我们的尾部插入一个数据即可。

//尾插
void PushBack(SeqList* p, DataType x)
{if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}p->a[p->size] = x;p->size++;
}

头删

//头删
void PopFront(SeqList* p)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}for (int i = 0; i < p->size - 1; i++){p->a[i] = p->a[i + 1];}p->size--;
}

• p->a[i] = p->a[i + 1];将后一个结点的值赋值给当前位置。

尾删

//尾删
void PopBack(SeqList* p)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}p->size--;
}

查找

在查找这里，我们实现一个查找指定结点的值，以及查找值为x的结点。

查找指定结点的值

//查找指定结点的值
DataType Get(SeqList* p, int i)
{if (i <= 0 || i >= p->size){printf("指定位置的结点不存在\n");exit(-1);}printf("指定位置的结点值为%d\n", p->a[i]);return p->a[i];
}

查找值为x的结点

//查找指定值为x的结点
void Find(SeqList* p, DataType x)
{for (int i = 0; i < p->size; i++ ){if (p->a[i] == x){printf("找到了！\n");printf("下标为%d\n", i);}}
}

在test.c文件中，我们进行调试，

int main()
{SeqList s;//创建顺序表sInitSeqList(&s);//初始化我们刚建的顺序表sPrintSeqList(&s);//打印顺序表Get(&s , 1);Find(&s, 3);return 0;
}

插入或删除指定位置的元素

插入指定位置的元素

//在指定的位置i插入元素x
void Insert(SeqList* p,int i, DataType x)
{if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}if (i <= 0 || i >= p->size){printf("指定插入位置的结点不存在\n");exit(-1);}for (int j = p->size; j > i; j--){p->a[j] = p->a[j - 1];}p->a[i] = x;p->size++;
}

删除指定位置的元素

void Delete(SeqList* p, int i)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}if (i <= 0 || i >= p->size){printf("指定删除位置的结点不存在\n");exit(-1);}for (int j = i; j < p->size - 1; j++){p->a[j] = p->a[j + 1];}p->size--;
}

调试信息如下：

完整代码

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>//顺序表结构
#define N 100
typedef int DataType;
typedef struct SeqList {DataType a[N];int size;
}SeqList;//函数声明
void InitSeqList(SeqList* p);
void PrintSeqList(SeqList* p);
void PushFront(SeqList* p, DataType x);
void PushBack(SeqList* p, DataType x);
void PopFront(SeqList* p);
void PopBack(SeqList* p);
DataType Get(SeqList* p, int i);
void Find(SeqList* p, DataType x);
void Insert(SeqList* p, int i, DataType x);
void Delete(SeqList* p, int i);

SeqList.c

#include "SeqList.h"//初始化一个顺序表
void InitSeqList(SeqList* p) {int n;p->size = 0;printf("请输入元素的个数：\n");scanf("%d", &n);printf("请依次输入各元素：\n");for (int i = 0; i < n; i++){scanf("%d", &p->a[i]);p->size++;}printf("\n");
}//打印顺序表
void PrintSeqList(SeqList* p)
{int i = 0;printf("顺序表各结点值为:\n");for (i = 0; i < p->size; i++)printf("%d ", p->a[i]);printf("\n");
}//头插
void PushFront(SeqList* p,DataType x)
{//先来判断容量有没有满if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}for (int i = p->size ;i>=0; i--){p->a[i] = p->a[i - 1];}p->a[0] = x;p->size++;}//尾插
void PushBack(SeqList* p, DataType x)
{if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}p->a[p->size] = x;p->size++;
}//头删
void PopFront(SeqList* p)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}for (int i = 0; i < p->size - 1; i++){p->a[i] = p->a[i + 1];}p->size--;
}//尾删
void PopBack(SeqList* p)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}p->size--;
}//查找指定结点的值
DataType Get(SeqList* p, int i)
{if (i <= 0 || i >= p->size){printf("指定位置的结点不存在\n");exit(-1);}printf("指定位置的结点值为%d\n", p->a[i]);return p->a[i];
}//查找指定值为x的结点
void Find(SeqList* p, DataType x)
{for (int i = 0; i < p->size; i++ ){if (p->a[i] == x){printf("找到了！\n");printf("下标为%d\n", i);}}
}//在指定的位置i插入元素x
void Insert(SeqList* p,int i, DataType x)
{if (p->size == N) {printf("该顺序表已满，无法插入！\n");exit(-1);}if (i <= 0 || i >= p->size){printf("指定插入位置的结点不存在\n");exit(-1);}for (int j = p->size; j > i; j--){p->a[j] = p->a[j - 1];}p->a[i] = x;p->size++;
}
void Delete(SeqList* p, int i)
{if (p->size == 0){printf("当前顺序表为空，不可删除！");exit(-1);}if (i <= 0 || i >= p->size){printf("指定删除位置的结点不存在\n");exit(-1);}for (int j = i; j < p->size - 1; j++){p->a[j] = p->a[j + 1];}p->size--;
}

测试文件test.c大家自己根据函数测试其功能就可以了。