线性表之顺序表（SqList）

数据结构第二章线性表的定义、特点和存储结构。顺序表的定义、特点和存储结构。附加完整代码实现

线性表

注：SqList为简写，完整名为Sequential List。

线性表的定义

线性表是n个具有相同数据类型（特性）的数据元素的有限 序列，其中n为表长，当n = 0时，线性表是一个空表。

相同：每个数据元素所占空间一样大

序列：有次序

有限：所有的整数按递增次序排列，不是线性表。所有的整数是无限的

注意：线性表的位序从1开始，数组下标是从0开始的

线性表的特点

1．集合中必存在唯一的一个“第一元素”。

2．集合中必存在唯一的一个 “最后元素” 。

3．除最后一个元素之外，均有唯一的后继(后件)。

4．除第一个元素之外，均有唯一的前驱(前件)。

线性表存储结构

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

• 数组存储即顺序存储结构
• 链表即链式存储结构

顺序表

顺序表是用顺序存储的方式实现的线性表

顺序表的定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表的特点

1. 随机访问，即可在O（1）时间内找到第i个元素。
2. 存储密度高，每个节点只存储数据元素本身
3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
   静态分配不能拓展容量。
4. 插入、删除操作不方便，需要移动大量元素

顺序存储结构

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

//顺序表结构
typedef struct
{
	Book* elem; //定义Book指针
	int length; //顺序表的长度
	int MaxSize;//此处为扩展知识,书上没有
}SqList;

顺序表的完整代码实现

#include<iostream>
#include<string>

using namespace std;

#define MAXSIZE 10  //宏定义，定义数组最大长度，对应顺序表的容量

//图书结构
typedef struct
{
	string no; //图书ISBN编号
	string name;  //图书名称
	float price;  //图书价格
}Book;

//顺序表结构
typedef struct
{
	Book* elem; //定义Book指针
	int length; //顺序表的长度
	int MaxSize;//此处为扩展知识,书上没有
}SqList;

//给Book类型取外号为ElemType
typedef Book ElemType;
//给int类型取外号为Status
typedef int Status;


/*
	顺序表的初始化:
	参数一：要初始化的顺序表
	注意：成功：返回1；失败：退出程序，错误代码：3。
*/
Status InitList(SqList& L)//使用int类型的外号Status作为函数的返回值类型
{
	L.MaxSize = MAXSIZE;
	//L.elem = (Book*)malloc(MAXSIZE*sizeof(int)); //或者用malloc开辟空间
	L.elem = new ElemType[MAXSIZE]; //使用Book类型的外号ElemType
	//exit是退出整个进程，OVERFLOW的默认值为3，意思为栈溢出
	if (!L.elem) exit(OVERFLOW);
	L.length = 0;
	return 1;
}

/*
	顺序表的扩容（扩展知识，书上并没有这个）
	扩容会大量移动数据，时间复杂度为O(n)
*/
void IncreaseSize(SqList &L,int len)
{
	Book *p = L.elem;//将原来的地址给p
	L.MaxSize += len;//容量加上扩容的数据
	
	L.elem = new Book[L.MaxSize];//开辟新空间
	//L.elem = (Book*)malloc(L.MaxSize*sizeof(int));
	for (int i = 0; i < L.length; i++)//将原来的数据拷贝回来
	{
		/*
			此处编译器警告：代码：C6385 说明：正在从"L.elem"读取无效数据。
			尚不清楚是怎么回事，然而并不影响程序运行。
		*/
		L.elem[i] = p[i];
	}

	//delete(p);//这里应当释放的，但是这样编译器报错，程序崩溃。
	//free(p);//如果用malloc开辟空间，就用free释放
}

/*
	顺序表的取值:
	参数一：要取值的顺序表
	参数二：要取值的位置
	参数三：待保存的对象
	注意：成功：返回1；失败：返回0。
*/
Status GetElem(SqList& L, int num, ElemType& e)//使用Book类型的外号ElemType作为传入参数e的类型，使用int类型的外号Status作为函数的返回值类型
{
	if (num<1 || num>L.length)//先判断输入是否合法
	{
		return 0;
	}
	e = L.elem[num - 1]; //将获取的数值赋值给Book对象e
	return 1;
}

/*
	顺序表的查找:
	参数一：要查找的顺序表
	参数二：要查找的数据
	注意：成功：返回下标位置；失败：返回0。
*/
Status LocateElem(SqList L, ElemType e)//使用Book类型的外号ElemType作为传入参数e的类型，使用int类型的外号Status作为函数的返回值类型
{
	for (int i = 0; i < L.length; i++)
	{
		//对比Book中的数据是否相等
		if (L.elem[i].name == e.name && L.elem[i].no == e.no && L.elem[i].price == e.price)
		{
			return i + 1;//因为线性表是从1开始的
		}
	}
	return 0;
}

/*
	顺序表的插入:
	参数一：要插入的顺序表
	参数二：要插入的位置
	参数三：要插入的数据
	注意：成功：返回1；失败：返回0。
*/
Status ListInsert(SqList& L, int num, ElemType e)//使用Book类型的外号ElemType作为传入参数e的类型，使用int类型的外号Status作为函数的返回值类型
{
	if (L.length == MAXSIZE || num<1 || num >L.length + 1)//先判断输入是否合法
	{
		return 0;
	}
	for (int i = L.length - 1; i >= num - 1; i--)
	{
		L.elem[i + 1] = L.elem[i];
	}
	L.elem[num - 1] = e;
	L.length++;//成功插入数据，length长度+1
	return 1;
}

/*
	顺序表的删除:
	参数一：要删除的顺序表
	参数二：要删除的位置
	注意：成功：返回1；失败：返回0。
*/
Status ListDelete(SqList& L, int num)//使用int类型的外号Status作为函数的返回值类型
{
	if (num<1 || num >L.length || L.length == 0)//先判断输入是否合法
	{
		return 0;
	}
	//这里书上是i < L.length-1；是错误的
	for (int i = num; i < L.length; i++)//删除数据就把num后的数据逐个前移，将其覆盖掉
	{
		L.elem[i-1] = L.elem[i];
	}
	L.length--;//成功删除数据，length长度-1
	return 1;
}

int main()
{
	SqList L;
	Book book;
	int temp = 0; //临时数据，用来判断执行是否成功
	cout << "======================================" << endl;
	cout << "1、初始化顺序表...";
	temp = InitList(L);
	if (!temp)
	{
		cout << "\t失败" << endl;
	}
	cout << "\t成功！" << endl;
	
	book.no = "978-7-115-37950-4";
	book.name = "数据结构（c语言版）（第2版）";
	book.price = 35;
	cout << "======================================" << endl;
	cout << "2、往顺序表中插入数据...";
	for (int i = 1; i <= 10; i++)
	{
		book.price = i;
		temp = ListInsert(L, i, book);
	}
	

	if (!temp)
	{
		cout << "\t失败" << endl;
	}
	cout << "\t成功！" << endl;
	cout << "======================================" << endl;
	/*cout << "3、扩容...";
	IncreaseSize(L, 5);
	cout << "L.MaxSize :"<< L.MaxSize << endl;*/
	cout << "3、获取图书的下标位置数据...";
	temp = LocateElem(L, book);
	if (!temp)
	{
		cout << "\t失败!" << endl;
	}
	cout << "\t成功！" << endl;
	cout << "--------------------------------------" << endl;
	cout << "下标位置为：" << temp << endl;
	Book book1;
	cout << "======================================" << endl;
	cout << "4、在顺序表中取得数据...";
	temp = GetElem(L, 1, book1);
	if (!temp)
	{
		cout << "\t失败" << endl;
	}
	cout << "\t成功！" << endl;
	cout << "--------------------------------------" << endl;
	cout << "图书信息为：" << endl;
	cout << "图书ISBN :" << book1.no
		<< "\t图书名称：" << book1.name
		<< "\t图书价格：" << book1.price << endl;
	cout << "======================================" << endl;
	cout << "5、删除顺序表中的数据...";
	temp = ListDelete(L, 5);
	if (!temp)
	{
		cout << "失败" << endl;
	}
	cout << "成功" << endl;
	cout << "======================================" << endl;
	for (int i = 1; i <= L.length; i++)
	{
		GetElem(L, i, book1);
		cout << book1.price << endl;
	}

	system("pause");
	return 0;
}

运行结果：

======================================
1、初始化顺序表...      成功！
======================================
2、往顺序表中插入数据...        成功！
======================================
3、获取图书的下标位置数据...    成功！
--------------------------------------
下标位置为：1
======================================
4、在顺序表中取得数据...        成功！
--------------------------------------
图书信息为：
图书ISBN :978-7-115-37950-4     图书名称：数据结构（c语言版）（第2版）  图书价格：35
======================================
5、删除顺序表中的数据...成功
======================================
请按任意键继续. . .

动态分配方法（修改部分）

//顺序表结构
typedef struct
{
	Book* elem; //定义Book指针
	int length; //顺序表的长度
	int MaxSize;
}SqList;

/*
	顺序表的初始化:
	参数一：要初始化的顺序表
	注意：成功：返回1；失败：退出程序，错误代码：3。
*/
Status InitList(SqList& L)//使用int类型的外号Status作为函数的返回值类型
{
	L.MaxSize = MAXSIZE;
	L.elem = new ElemType[MAXSIZE]; //使用Book类型的外号ElemType
	//L.elem = (Book*)malloc(MAXSIZE*sizeof(int));
	//exit是退出整个进程，OVERFLOW的默认值为3，意思为栈溢出
	if (!L.elem) exit(OVERFLOW);
	L.length = 0;
	return 1;
}

/*
	顺序表的扩容
*/
void IncreaseSize(SqList &L,int len)
{
	Book *p = L.elem;
	L.MaxSize += len;
	L.elem = new Book[L.MaxSize];
    //L.elem = (Book*)malloc(L.MaxSize*sizeof(int));
    for (int i = 0; i < L.length; i++)
    {
        L.elem[i] = p[i];
    }
    delete(p);
    //free(p);
}