# 顺序表数据结构

**Repository Path**: shaobufan/sequence-table

## Basic Information

- **Project Name**: 顺序表数据结构
- **Description**: 顺序表数据结构
- **Primary Language**: C++
- **License**: MulanPSL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-10-03
- **Last Updated**: 2022-05-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 顺序表
## 顺序表的模板类

```c++
template <class ElemType>
//标记类是使用的类模板，ElemTypek可以是任何类型的数据（int/char/double...）
class SqList:public List<ElemType>
{
public:
	SqList(int m = 0);
    //表的构造函数，m是初始化顺序表的长度
	SqList(const SqList<ElemType> &);
    //表的拷贝构造函数
	~SqList();
    //析构函数
	bool IsEmpty()const  {return len<=0;}
    //判断是否为空，函数体简单直接类内定义
	int Length()const   {return len;}
    //返回表的长度
	void Clear()  {len=0;}
    //长度清零，格式化表
	bool GetElem(ElemType &,int)const;
    //取i号元素值,ElemType为取出的元素类型，int为i号
	bool SetElem(const ElemType &,int);
    //在第i个位置存入元素
	int LocateElem(const ElemType&)const;
    //定位元素，查找符合要求的元素位置
	int LocatePrior(const ElemType&)const;
    //定位元素前一个位置，查找符合要求的元素位置的上一个位置
	int LocateNext(const ElemType&)const;
    //定位元素后一个位置，查找符合要求的元素位置的后一个位置
	bool Insert(const ElemType&, int);
    //在第i个位置插入元素
	bool Append(const ElemType&);
    //在表末尾添加元素
	bool Delete(ElemType&, int);
    //删除第i个位置的元素
	void Inverse();
    //倒置表
	void Traverse(void(*visit)(const ElemType& e))const;
    //遍历
	SqList<ElemType>& operator=(const SqList<ElemType>&);
    /*
    重载符号‘=’，使之可以让两个表可以直接赋值
    扩展=号的适用范围，让其不仅仅可以i=8，还可以A表=B表。
    */
private://私有成员
	int len;
    //表的长度
	int size;
    //表的大小
	ElemType* elem;
    //表的实际数据储存的位置的头标号（数组指针）
	void CopyFrom(const SqList<ElemType>&);
    //拷贝函数
};
```

**注意**：len是表中已经存存储的数据的个数，而size是在内存中表被分配的内存。

## 顺序表的初始化

```c++
//顺序表初始化
template<class ElemType>                 
SqList<ElemType>::SqList(int m)
{
	len = 0;
	if (m == 0)
		elem = NULL;
	else
		elem = new ElemType[m];
	size = m;
}
```

由于是初始化所以表中没有任何元素故len=0，但是初始化表就意味着要给表分配内存所以将m赋值于size，预先开辟m个位置。如果m=0，那么表将毫无意义。表为空（真正意义上的空表，就连表的头指针都为空/NULL）若m不等于零那么就为表动态分配内存。

```c++
ElemType *elem;
//定义类型指针
elem = new ElemType[m];
//为指针开辟动态内存
------------------------------
int *a = new int[5];
//等价于
int a[5];
//a就是头指针
```

分配完内存后，使size的值为m。

## 拷贝构造函数

拷贝构造函数并不是独立的函数，而是调用了Append和CopyFrom函数，故依次展开。

```c++
//拷贝构造函数
template<class ElemType>
SqList<ElemType>::SqList(const SpList<ElemType> &r)
{
    len=0;
    size=0;
    elem=NULL;
    CopyFrom(r);
}

//复制所有元素
template<class ElemType>
SqList<ElemType>::CopyFrom(const SqList<ElemType> &r)
{
    ElemType* p=r.elem;
    for(int i=0;i<r.len;i++)
        Append(*p++);
}

//在表尾插入新元素
template<class ElemType>
bool SqList<ElemType>::Append(const ElemType&e)
{
    ElemType* newbase;
    if(len>=size){
        newbase = new ElemType[size+10];
        if(!newbase)
            return 0;
        for(int j=0;j<len;j++)
            newbase[j]=elem[j];
        delete[] elem;
        elem = newbase;
        size += 10;
    }
    elem[len++] = e;
    return true;
}
```

### Addend函数

1、Addend函数为bool类型
2、由于我们分配的的数组内存是动态内存，所以在size之内可以存取甚至空着都行但是在size之外我们不能扩展。这就导致我们如果在表中存满了数据 **（len==size）** 我们就不能再存了。所以为了解决这个问题我们要重新开辟一个新的表（size比原来大10）再把原来的表放进新表这样新表就有10个空位了，然后删除原来表的空间吧新表的空间赋给原来的表。若size够使则直接存入即可。
3、new分配内存的方式为动态分配，所以释放内存要用delete关键字。若删除的是单个数据则用delete，若删除的是一组对象则用delete [ ]。好处：空间删除了但名字还在即头指针还在。
4、**++len与len++**;在c++中这两个++号是有具体的等价函数实现的，i++是先自增，然后返回之前的值；++i是先自增，然后返回自增后的值。共同特点是先自增。由于表的数组计数是从0开始的所以程序计数比实际的元素个数少一个（第5个元素在第4号位置上），所以elem[len++]=e;就是在表的末尾赋值，后len++;
5、==!==的意义：逻辑运算符非，故非零值为真，零值为假。若分配空间失败则elem为NULL（0），返回0（错误）;

### CopyFrom函数

1、**引用符号&**俗称起别名

```c++
void fun(int &a,int &b)
{
    ...
}

int main(){
    fun(c,d);
}
```

​	c的别名为a，d的别名为b。一个在函数体内用，一个在主函数里用。不是传值，不是指针，就是不同的地方用不同的名字操作。操作的都是同一个数据。**好处**：由于函数体在建立的时候并不知道主函数中的表会命名成什么，所以起别名在函数体中统一命名。而且还可以对主函数的表直接操作。
2、成员的调用"."; elem是SqList类的私有成员，并且是数组的头指针，所以调用时

```c++
ElemType* p=r.elem;
```

让其左边数据类型与右边数据类型相等。==意义：==左边的为指针p而右边为指针r.elem。为了配合Append函数而定义的，事实上可以省略为

```c++
//先前的样式
Append(*p++);
//之后的样式
Append(*r.elem++);
//展开为
Append(*r.elem);
r.elem++;
```

3、指针数组的相关知识。

```c++
int *a = new int [5];
```

a为数组的头指针（指向第一个数组元素的指针）。后面的5为分配的5个int型内存空间，在c++中定义指针时要指明什么类型的指针，这并不是不同类型的指针占的字节不同（都是四字节），而是便于我们对它操作。下面详细说明：Append函数用到的参数为 *p，p 为头指针则 *p 为第一个元素，p++并不是单纯的地址+1，而是加上了一个int型的地址空间

```c++
int a[]={1,2,3,4};
*a=1;
*a+1=2;
*a+2=3;
*a+3=4;
```

这就使得程序符合常识+1就是下一个，这也就是为什么定义指针时候要指明数据类型，方便程序+1是准确的指向下一个元素。

## 析构函数

```c++
//顺序表结构销毁
template<class ElemType>                     
SqList<ElemType>::~SqList()
{
	delete[] elem;
}
```

析构函数中delete [ ] elem; 是释放内存：len=0，size=0，elem=NULL。但是elem成员的这个名字还在。只是存储空间没了。

## 格式化函数

```c++
void Clear()  {len=0;}
```

**为什么将len清零就能格式化线性表？**
	因为我们操作表中的元素时靠的就是len来规范行为，例如：插入、查找、倒置、遍历、设置特定位置的数据元素，都要用len来判断是否溢出等等。len为零表就操作不了。变为不可见，但是内存中还是有这个表的数据还是没变，甚至内存地址都没变，再次录入数据时会覆盖原来的数据。宏观上达到清除的效果。（这也就时为什么删除文件要远远快于下载同样大小的文件，删除只是打上一个不可见的标记而已，这也就是为什么文件删除了还是可以恢复的原因）

## 取值函数

```c++
//取i号元素值
template<class ElemType>
bool SqList<ElemType>::GetElem(ElemType& e, int i) const
{
	if (i<1 || i>len)
		return false;
	e = elem[i - 1];
	return true;
}
```

1、参数为：缓存数据的e，数据位置i。
2、判断位置是否合理。
3、将值取出给到e，借由e推送到主函数的数据缓存变量中。
4、函数类型为bool，便于判断函数体执行状态。

## 存值函数

```c++
//第i个位置存入数据
template<class ElemType>
bool SqList<ElemType>::SetElem(const ElemType& e, int i)
{
	if (i<1 || i>len)
		return false;
	elem[i - 1] = e;
	return true;
}
```

和取值函数基本一致，唯一不同的是

```c++
//取值函数
e = elem[i - 1];
//存值函数
elem[i - 1] = e;
/*
关键是被赋值的对象（左值）不同
取值为从表中调取并推送到主函数
存值为从主函数拉取数据推送到表中
*/
```

## 查找函数

```c++
//查找顺序表中符合条件数据元素
template<class ElemType>
int SqList<ElemType>::LocateElem(const ElemType& e) const
{
	ElemType* p = elem;
	int i = 1;
	while (i <= len && *p != e)
	{
		p++;
		i++;
	}
	if (i <= len)
		return i;
	return 0;
}
```

1、参数 i 用于记录元素位置
2、while(){} 括号里的内容为true则进行循环。
3、p 为执行数组的指针。
4、返回值类型为int。

## 插入函数

```c++
//第i个数据元素之间插入新的数据元素
template<class ElemType>
bool SqList<ElemType>::Insert(const ElemType& e, int i)
{
	if (i<1 || i>len + 1)
		return false;
	if (len >= size) {
		ElemType* newbase;
		newbase = new ElemType[size + 10];
		if (!newbase)
			return false;
		for (int j = 0; j < len; j++)
			newbase[j] = elem[j];
		delete[] elem;
		elem = newbase;
		size += 10;
	}
	ElemType* p, * q;
	q = &elem[i - 1];
	for (p = &elem[len - 1]; p >= q; p--)
		*(p + 1) = *p;
	*q = e;
	len++;
	return true;
}
```

插入函数分为3个模块

```c++
//判断是否溢出模块
if (i<1 || i>len + 1)
	return false;
```

```c++
//扩容模块
if (len >= size) {
	ElemType* newbase;
	newbase = new ElemType[size + 10];
	if (!newbase)
		return false;
	for (int j = 0; j < len; j++)
		newbase[j] = elem[j];
	delete[] elem;
	elem = newbase;
	size += 10;
}
```

```c++
//迁移模块
ElemType* p, * q;
q = &elem[i - 1];
for (p = &elem[len - 1]; p >= q; p--)
	*(p + 1) = *p;
*q = e;
len++;
```

**扩容模块的意义**
	假如表被填满了即 len == size，则再插入时就会发生溢出，故需要扩容。扩容判断条件为 len >= size（真正起作用的为 len == size）。

**迁移模块的原理**
	定义两个数据指针 p、q。q用于存储原第i个位置的数据==地址==，for循环从表的最后一个位置开始向后依次移动一个位置直到把第i个位置的数据也移动完，此时q指向的位置空缺，用要插入的e填补。

## 删除函数

```c++
//删除第i个元素
template<class ElemType>
bool SqList<ElemType>::Delete(ElemType& e, int i)
{
	if (i<1 || i>len)
		return false;
	ElemType* p, * q;
	p = &elem[i - 1];
	e = *p;
	q = &elem[len - 1];
	for (p++; p <= q; p++)
		*(p - 1) = *p;
	len--;
	return true;
}
```

**删除模块的原理**
	定义两个数据指针 p、q。q用于标记表为的位置==地址==，p用于存储原第i个位置的数据==地址==并缓存到e，for循环从表的第i个位置的下一个位置开始向前依次移动一个位置直到把表尾的数据也移动完，此时p指向的位置被覆盖故被删除。