1.线性表定义

线性表（List）：零个或多个数据元素的有限序列。

线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。

2.顺序表

线性表的顺序存储结构

1.概念

用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

2.特点

逻辑上相邻的数据元素，物理次序也是相邻的。

只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

3.代码

1: .h

#pragma once
//预防头文件被重复引用
//定义与声明//定长顺序表
typedef struct SQList
{int elem[10];//存放数据,固定长度为10int length;//有效数据的个数
}SQList,*PSQList;//初始化
void InitSqlist(PSQList ps);//插入数据,在ps顺序表的pos位置插入val
bool Insert(PSQList ps, int pos, int val);//判空
bool IsEmpty(PSQList ps);//在ps中查找第一个val.找到返回下标,没有找到返回-1
int Search(PSQList ps, int key);//删除pos位置的值
bool DelPos(PSQList ps, int pos);//删除第一个val的值
bool DelVal(PSQList ps, int val);//返回key的前驱下标,如果不存在返回-1
int GetPrio(PSQList ps, int key);//返回key的后继下标,如果不存在返回-1
int GetNext(PSQList ps, int key);//输出
void Show(PSQList ps);//清空数据
void Clear(PSQList ps);//销毁整个内存
void Destroy(PSQList ps);

2: .cpp

1.头文件

#include
#include
#include"sqlist.h"

2.初始化,为了让程序正确运行

void InitSQList(PSQList ps)
{assert(ps != NULL);if (ps == NULL){return;}ps->length = 0;
}static bool IsFull(PSQList ps)
{return ps->length == 10;
}

3.插入数据，在ps顺序表的pos位置插入val

bool Insert(PSQList ps, int pos, int val)
{//判空assert(ps != NULL);if (ps == NULL){return false;}//判断是不是满的表if(pos<0||IsFull(ps)||pos> ps->length){return false;}//把数据移动到后for(int i=ps->length-1;i>=pos;i--){ps->elem[i+1] = ps->elem[i];}//插入数据ps->elem[pos] = val;//有效数据++ps->length++;
}

4.判空

bool IsEmpty(PSQList ps)
{return ps->length == 0;
}

5.查找,找到返回下标，没找到返回-1

int Search(PSQList ps, int key)
{//判空assert(ps != NULL);if (ps == NULL){return false;}for (int i = 0; i < ps->length; i++){if (ps->elem[i] == key){return i;}}return -1;
}

6.删除pos位置的值

bool Delpos(PSQList ps, int pos)
{//判空assert(ps != NULL);if (ps == NULL){return false;}if (pos < 0 || pos >= ps->length){return false;}for (int i = pos; i < ps->length-1; i++){ps->elem[i] = ps->elem[i + 1];}ps->length--;
}

7.删除第一个val的值

bool Delval(PSQList ps, int val)
{assert(ps != NULL);if (ps == NULL){return false;}int i = Search(ps, val);if (i < 0){return false;}return Delpos(ps, i);}

8.返回key的前驱下标，如果不存在返回-1

int GetPrio(PSQList ps, int key)
{assert(ps != NULL);if (ps == NULL){return false;}int i = Search(ps, key);if (i <= 0)//头无前驱return false;elsereturn i-1;
}

9.返回key的后继下标，如果不存在返回-1

int GetNext(PSQList ps, int key)
{assert(ps != NULL);if (ps == NULL){return false;}int i = Search(ps, key);if (i < 0||i==ps->length-1)//尾无后继return false;elsereturn i+1;
}

10.输出

void Show(PSQList ps)
{//判空assert(ps != NULL);if (ps == NULL){return ;}for (int i = 0; i < ps->length; i++){printf("%d ", ps->elem[i]);}printf("\n");
}

11.清空数据

void Clear(PSQList ps)
{ps->length = 0;
}

12.销毁 

void Destroy(PSQList ps)
{Clear(ps);
}

3. .test

#include 
#include "sqlist.h"
int main()
{SQList sq;printf("%d\n", sizeof(sq));InitSQList(&sq);for (int i = -1; i < 20; i++){Insert(&sq, i, i);}Show(&sq);int i = Search(&sq, 2);if (i >= 0){printf("该值位于%d号下标\n", i);}else{printf("没有找到\n");}int index;for (int i = -1; i < 11; i++){index = Search(&sq, i);if (index >= 0){printf("%d位于%d号下标\n", i, index);}else{printf("没有找到%d\n",i);}}Delpos(&sq, 5);Show(&sq);Delval(&sq, 0);Show(&sq);return 0;
}v

4.测试结果

 44                                        顺序表的大小
0 1 2 3 4 5 6 7 8 9                插入数据，只存10个（表的大小为10）
该值位于2号下标                  查找val=2的下标
没有找到-1                           查询不到-1
0位于0号下标                       
1位于1号下标
2位于2号下标
3位于3号下标
4位于4号下标
5位于5号下标
6位于6号下标
7位于7号下标
8位于8号下标
9位于9号下标
没有找到10                       查询不到10
0 1 2 3 4 6 7 8 9               删除5
1 2 3 4 6 7 8 9                  删除0