1. 基本概念

线性表：

（1）.其中的各个元素，数据类型相同。

（2）.元素之间，有次序。

（3）.都有表头元素和表尾元素。

（4）.除了表头表尾，每个元素都可以找到一个直接前驱和直接后继。

2.线性表的基本操作

表的从无到有

InitList(&L)：初始化一个线性表

DestroyList(&L)：销毁

。

ListInsert(&L, i, e)：插入，在表L的第 i 处插入元素 e

ListDelete(&L, i, &e)：删除，将表L的第 i 处元素删除，并用 e 返回该被删除的元素

。

LocateElem(L, e)：按值查找，在表中查找特定关键字e 的元素

GetElem(L, i)：按位查找，获取表中第 i 个元素的值

。

其他常规操作：

Length(L)：求表长度

PrintList(L)：输出表的所有元素

Empty(L)：判断表是否为空，返回true or false

高度概括，即为，创销与增删改查

3.顺序表

以顺序存储方式储存数据的线性表

（1）.静态分配

#define MAX 10
//顺序表（静态分配）
class SqList
{
public:
    int data[MAX];
    int length;
};
//初始化
void InitList(SqList &l)
{
    for(int i = 0 ;i < 10 ;i++)
    {
        l.data[i] = 0;
    }
    l.length = 0;
}
//打印所有元素
void PrintList(SqList &l)
{
    for (int i = 0; i < 10; i++)
        cout << "第" << i << "个数：" << l.data[i] << endl;
}

//测验
void test01()
{
    SqList l;
    InitList(l);
    PrintList(l);
}

（2）.动态分配

#define InitSize 10
//顺序表（动态分配）
class SqList
{
public:
	int* data;		//指示动态分配数组的指针
	int MaxSize;	//指示最大容量
	int length;		//指示当前长度
};
//初始化顺序表
void InitList(SqList& l)
{
	l.data = new int[InitSize];
	l.MaxSize = InitSize;
	l.length = 0;
	for (int i = 0; i < l.MaxSize; i++)
	{
		l.data[i] = 0;
	}
}
//增长数组空间
void IncreaseSize(SqList& l, int len)
{
	int* p = l.data;					//暂存原数组中的数据
	l.data = new int[10 + len];			//扩展新的数组
	for (int i = 0; i < l.length; i++)	//将原数据拷贝进新数组中
	{
		l.data[i] = p[i];
	}
	l.MaxSize = InitSize + len;			//修改数组的状态数据
	delete p;							//将p释放
}
//打印所有元素
void PrintList(SqList& l)
{
	for (int i = 0; i < 10; i++)
		cout << "第" << i << "个数：" << l.data[i] << endl;
}

void test01()
{
	SqList l;
	InitList(l);
	PrintList(l);
}

（3）.顺序表的插入（以静态分配为例）（示例代码中包含了一下必要的基本函数）

bool ListInsert(SqList& l, int d, int e)
{
    if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
    {
        cout << "插入失败，已达上限" << endl;
        return false;
    }
        
    if (d < 1 || d > l.length + 1)
    {
        cout << "插入失败,无直接前驱" << endl;
        return false;
    }
    for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
        l.data[j] = l.data[j - 1];
    l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一
    l.length++;
    return true;
}

示例代码

#define MAX 10
//顺序表（静态分配）
class SqList
{
public:
    int data[MAX];
    int length;
};
//初始化
void InitList(SqList& l)
{
    for (int i = 0; i < 10; i++)
    {
        l.data[i] = 0;
    }
    l.length = 0;
}
//打印所有元素
void PrintList(SqList& l)
{
    for (int i = 0; i < 10; i++)
        cout << "第" << i << "个数：" << l.data[i] << endl;
}
//存入数据
void InputElem(SqList& l, int e)
{
    int i = 0;
    while (i < MAX)
    {
        if (l.data[i] == 0)
        {
            l.data[i] = e;
            l.length++;
            break;
        }
        i++;
    }
}
//获取顺序表长度
int GetLength(SqList l)
{
    //cout << l.length << endl;
    return l.length;
}
//插入
bool ListInsert(SqList& l, int d, int e)
{
    if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
    {
        cout << "插入失败，已达上限" << endl;
        return false;
    }
        
    if (d < 1 || d > l.length + 1)
    {
        cout << "插入失败,无直接前驱" << endl;
        return false;
    }
    for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
        l.data[j] = l.data[j - 1];
    l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一
    l.length++;
    return true;
}
//查看情况
void CheckList(SqList& l)
{
    PrintList(l);
    cout << "当前长度为" << GetLength(l) << endl;
}

//测验
void test01()
{
	SqList l;
	InitList(l);
    //输入部分数据
    InputElem(l, 1);
    InputElem(l, 2);
    InputElem(l, 3);
    InputElem(l, 4);
    CheckList(l);
    //开始插入
    if(ListInsert(l, 5, 6))
        CheckList(l);
}

 （4）.顺序表的删除