线性表的顺序存储结构具体实现 代码实战 赛博图书馆搭建指南（使用C\C++语言）
目录
顺序存储结构的线性表（顺序表）
开端：创建并打印一个顺序表
进阶：插入&删除操作
最终操作：查找（按值）
——阅读全文大约需要30分钟以上，需要C语言基础以及对数据结构的简单了解，可以参考笔者之前的文章或直接观看对应慕课
顺序存储结构的线性表（顺序表）
开端：创建并打印一个顺序表
#include<stdio.h>
#include<stdlib.h>
//定义顺序表最大长度
#define MaxSize 100
//给int起别名，允许将数据替换为其他类型
typedef int ElemType;
//定义顺序表结构体
typedef struct {
//包含：顺序表元素值（用名为data的数组存放），表长
ElemType data[MaxSize];
int length;
}SeqList;//起名叫SeqList
//操作包含：插入、删除、查找、打印
//1.打印顺序表
void PrintList(SeqList L)
{
//遍历输出L.data[n]
for (int i = 0; i < L.length; i++)
{
printf("%-3d", L.data[i]);
}
}
//主函数部分，操作顺序表：初始化、向表中输入值、插入、删除、打印等
int main()
{
SeqList L1;//创建名为L1的顺序表变量
//初始化变量值
L1.data[0] = 1;
L1.data[1] = 2;
L1.data[2] = 3;
L1.length = 3;
//看看我们创建的东西吧
PrintList(L1);
}结果如下：（因为设置了3格左对齐（%-3d），所以输出格式是这样）
恭喜，现在你已经创建了一个顺序表并看到了其中的值
下面你决定让这个顺序表变得更有意思一些——用它来作为存放书籍的解决方案
#define _CRT_SECURE_NO_WARNINGS//VS需要
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxSize 100
//更改类型为字符型
typedef char ElemType;
typedef struct {
//为了存储书名，需要字符串数组，类型为char*
ElemType *data[MaxSize];
int length;
}SeqList;
void PrintList(SeqList L)
{
for (int i = 0; i < L.length; i++)
{
//这里改为输出字符串
printf("%s\n", L.data[i]);
}
}
int main()
{
//创建一个名为BookList的顺序表变量
SeqList BookList;
//先存个三本书
BookList.length = 3;
//结构体字符串不能直接赋值，且需要先申请空间，这里就申请20个字节
BookList.data[0] = (char*)malloc(sizeof(char) * 20);
BookList.data[1] = (char*)malloc(sizeof(char) * 20);
BookList.data[2] = (char*)malloc(sizeof(char) * 20);
//结构体字符串用拷贝字符串间接赋值，为方便计算字节数就用英文书名吧
strcpy(BookList.data[0], "The Great Gatsby");
strcpy(BookList.data[1], "Pride and Prejudice");
strcpy(BookList.data[2], "The little prince");
//看看我们创建的书架吧
PrintList(BookList);
}结果如下： 
进阶：插入&删除操作
书接上文，你的书架上总不能只摆三本书吧？当你买了一本新书，该如何插进书架里呢？
你决定先用数字代替一下书本做个演示
定义、PrintList等略去
//插入元素，参数分别为要插入的表（&表示C++引用）、插入的位置、插入元素的值
bool InsertElem(SeqList& L, int position, ElemType e)
{
//第一步：判断插入位置是否合法
int i = position;
if (i<1 || i>L.length + 1)
//合法的位置应该为：数组的第一位~此时数组的长度+1位
//为什么要加一呢？比如现在数组长度是3，如果想追加一位
//则必须使原本超出的一位合法
{
printf("插入失败，位置不合法\n");
return false;
}
//第二步：判断数组是否已满，空间不够就不能插入了
if (L.length == MaxSize)
return false;
//第三步：将插入位置之后的元素全部往后移动一位，且按从后往前顺序
for (int j = L.length; j >= i; j--)
{
//依次将前面一位的值赋给后面一位，空出插入位
L.data[j] = L.data[j - 1];
}
//第四步：插入元素，覆盖原来的值
L.data[i - 1] = e;
//第五步：顺序表长度加一
L.length++;
}
int main()
{
SeqList L1;
L1.data[0] = 1;
L1.data[1] = 2;
L1.data[2] = 3;
L1.length = 3;
InsertElem(L1, 2, 15);
//看看我们插入后的结果吧
PrintList(L1);
}- 在第二位插入，测试结果如图：
- 在第四位（追加项）插入
InsertElem(L1, 4, 15);//追加一项
PrintList(L1);
- 在第0位插入
InsertElem(L1, 0, 15);//非法位置
PrintList(L1); 
——为追求高效，你了解到可以用一个bool类型变量ret接收返回值
int main()
{
SeqList L1;
bool ret;
L1.data[0] = 1;
L1.data[1] = 2;
L1.data[2] = 3;
L1.length = 3;
ret = InsertElem(L1, 2, 15);
//看看我们插入后的结果吧
PrintList(L1);
}现在有了理论基础，你决定继续实现一下图书馆的项目：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MaxSize 100
typedef char ElemType;
typedef struct {
ElemType *data[MaxSize];
int length;
}SeqList;
void PrintList(SeqList L)
{
for (int i = 0; i < L.length; i++)
{
printf("%s\n", L.data[i]);
}
}
//插入元素是字符串，所以参数修改为char *e
bool InsertElem(SeqList& L, int position, ElemType* e)
{
int i = position;
if (i<1 || i>L.length + 1)
{
printf("插入失败，位置不合法\n");
return false;
}
if (L.length == MaxSize)
return false;
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
}
int main()
{
SeqList BookList;
BookList.length = 3;
//经发现，直接强转也可以赋值^_^
BookList.data[0] = (ElemType*)"The Great Gatsby";
BookList.data[1] = (ElemType*)"Pride and Prejudice";
BookList.data[2] = (ElemType*)"The little prince";
InsertElem(BookList, 4, (ElemType*)"asda");
PrintList(BookList);
}结果如图：
糟了，不小心打错了书名，你想到了两种选择，一是重新在第四位这个位置插入书名（覆盖插入），二是删掉它。不如借这个机会来学习删除操作吧！仍然是先拿数字版做铺垫——
//插入元素，参数分别为要插入的表、插入的位置、插入元素的值
bool InsertElem(SeqList& L, int position, ElemType e)
{
//第一步：判断插入位置是否合法
int i = position;
if (i<1 || i>L.length + 1)
//合法的位置应该为：数组的第一位~此时数组的长度+1位
//为什么要加一呢？比如现在数组长度是3，如果想追加一位
//则必须使原本超出的一位合法
{
printf("插入失败，位置不合法\n");
return false;
}
//第二步：判断数组是否已满，空间不够就不能插入了
if (L.length == MaxSize)
return false;
//第三步：将插入位置之后的元素全部往后移动一位，且按从后往前顺序
for (int j = L.length; j >= i; j--)
{
//依次将前面一位的值赋给后面一位，空出插入位
L.data[j] = L.data[j - 1];
}
//第四步：插入元素，覆盖原来的值
L.data[i - 1] = e;
//第五步：顺序表长度加一
L.length++;
}
//删除元素，函数参数表与插入类似，最后一个参数的目的是取出被删除元素,验证它确实是被删掉的
//直接return这个元素不好吗？当然不好，C只能返回一次，一个值。因此仍然是使用引用
bool DeleteElem(SeqList& L, int position, ElemType& del)
{
int i = position;
//第一步：同样判断删除的位置是否合法，由于不存在追加一位的需求，合法位置上线为数组长度
if (i<1 || i>L.length)
return false;
//第二步：先存一下被删除元素
del = L.data[i - 1];
//第三步：移动被删元素位置之后的每一个元素，这次是从前往后移动一位
for (int j = i - 1; j < L.length; j++)
{
//将后一位的值赋给前一位
L.data[j] = L.data[j+1];
}
//第四步：顺序表长度减一
L.length--;
return true;
}
//主函数部分
int main()
{
SeqList L1;
ElemType del;
bool ret;
L1.data[0] = 1;
L1.data[1] = 2;
L1.data[2] = 3;
L1.length = 3;
//插入后打印一下
ret = InsertElem(L1, 1, 15);
PrintList(L1);
//删除
ret = DeleteElem(L1, 1, del);
if (ret)
{
printf("被删除的是：%d\n", del);
PrintList(L1);
} else {
printf("Failed");
}
}结果如下：
再回到图书馆项目，有了前面的铺垫，删除操作实现起来也就比较轻松了，简单替换下参数类型即可
前面的部分略去了
//最后的参数需要是ElemType*&
bool DeleteElem(SeqList& L, int position, ElemType*& e)
{
int i = position;
if (i<1 || i>L.length)
return false;
e = L.data[i - 1];
for (int j = i - 1; j < L.length; j++)
{
L.data[j] = L.data[j + 1];
}
L.length--;
return true;
}
int main()
{
SeqList BookList;
ElemType* DelBook;
bool ret;
BookList.length = 3;
BookList.data[0] = (ElemType*)"The Great Gatsby";
BookList.data[1] = (ElemType*)"Pride and Prejudice";
BookList.data[2] = (ElemType*)"The little prince";
//插入书籍
InsertElem(BookList, 4, (ElemType*)"asda");
PrintList(BookList);
//删除书籍
ret = DeleteElem(BookList, 4, DelBook);
if (ret)
{
printf("删除的书籍是：%s\n", DelBook);
PrintList(BookList);
}else {
printf("Failed");
}
}结果如下：
最终操作：查找（按值）
过了很久，你已经往书架里塞了好多本书，每看完一本书就塞里面，你读的书越来越多，还加入了读者协会。有天一个协会的朋友来访，问你家书架上有没有一本《如来神掌》，这下你可无语啦，但是你看着他热切的眼神说行吧我给你找找，请问你如何找这本书呢？
老办法！你决定仍然先用数字法：
前面略去
//查询元素，按输入的元素值查询，返回位置数值
int LocalElem(SeqList L, ElemType e)
{
//第一步：判断是否合法。————不需要，遍历不到就返回0
for (int i = 0; i < L.length; i++)
{
//找到了，提前结束循环，退出函数
if (e == L.data[i])
return i + 1;//i是数组下标，i+1才是位置
}
//循环结束还没找到那就是没有了
return 0;
}
int main()
{
SeqList L1;
bool ret;
int pos = 0;
L1.data[0] = 1;
L1.data[1] = 2;
L1.data[2] = 3;
L1.length = 3;
ret = InsertElem(L1, 4, 15);
PrintList(L1);
//寻找15这个数字在哪
pos = LocalElem(L1, 15);
if (pos)
printf("成功！元素在第%d位", pos);
else
printf("Failed");
}
因为有了前面的铺垫，你轻松搞定了这个操作，你决定一鼓作气，写出图书馆解决方案最后一环：
//老朋友了，ElemType* e
int LocalElem(SeqList L, ElemType* e)
{
for (int i = 0; i < L.length; i++)
{
if (e == L.data[i])
return i + 1;
}
return 0;
}
int main()
{
SeqList BookList;
ElemType* DelBook;
bool ret;
int pos = 0;//新建整型变量
BookList.length = 3;
BookList.data[0] = (ElemType*)"The Great Gatsby";
BookList.data[1] = (ElemType*)"Pride and Prejudice";
BookList.data[2] = (ElemType*)"The little prince";
//某天看完的《如来神掌》
InsertElem(BookList, 4, (ElemType*)"如来神掌");
PrintList(BookList);
//查询《如来神掌》这本书
pos = LocalElem(BookList, (ElemType*)"如来神掌");
if (pos)
printf("成功！书籍在第%d排", pos);
else
printf("Failed");
}
我去，还真找到了？书友对你崇拜的目光又加深了一分~
至此你已经完整地实现了用顺序表存储元素，并且通过将数据类型改为字符串结构体而搭建了一个“赛博图书馆”，虽然这个图书馆还非常初级，也存在许多问题，比如插入一本书需要移动其之后的全部书，当书有几千万本的时候，插入一次可要伤筋动骨咯。下篇文章将介绍一种不需要“伤筋动骨”的数据结构——线性表的链式存储。但总的来说，你已经开启了数据结构第一步，Keep on going!