线性表(SequenceList)的顺序表示与实现----线性结构

最近在准备考研数据结构，之前大二已经学过了一次，再次复习只看书总也看不下去，越看越不像看，总觉得要想学得透彻敲敲代码才理解得更深，嘿嘿，这可能就是预备程序员的觉悟吧。

如果有写的不对的地方和需要探讨的地方，欢迎小伙伴们评论讨论~

线性表的顺序表示和实现

参考自严蔚敏版《数据结构》第二章第二节----线性表的顺序表示和实现

数据结构分为3种结构：顺序结构、树状结构、图状结构（加上集合的话就是4种结构啦）
今天主要讲顺序结构中的线性表的顺序(逻辑顺序与物理顺序一致)表示和实现，主要采用数组实现，之后还会有链式表示和实现，两者各有优缺点。

头文件的引入和变量定义

主要引入C语言的头文件和定义常量标识符，定义了线性表List(包括表的基本元素类型Student， 表的长度length，表的最大容量listsize)。

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

//----- 线性表的动态分配顺序存储结构 ----- 
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

//定义线性表操作的数据元素Student学生类型, 即数据元素 
typedef struct{
    
	int id;			//定义student学生的序号id, 即数据项1 
	int age;		//定义student学生的年龄age, 即数据项2 
}Student;

//定义线性表 
typedef struct{
    
	Student *student;		//表内存储的主要信息为学生Student类型的信息 
	int length;				//length代表线性表的长度 
	int listsize;			//listsize代表线性表的最大容量范围 
}List;

所有的函数(声明)

对于线性表的所有基本操作的定义声明

//声明线性表存储的基本操作 
int initList(List &list);											//初始化线性表 
int destoryStudentList(List &list);									//销毁线性表 
int insertStudentList(List &list, int i, Student student);			//为线性表指定位置插入一个数据元素 
Student deleteStudentList(List &list, int i, Student &student);		//删除指定位置的一个数据元素，并返回该元素 
int mergeOrderList(List &list_a, List &list_b, List &list_c);		//对有序的两个线性表合并 
int locateStudent(List &list, Student student);						//根据数据元素定位到线性表中的位置 
int getListLength(List &list);										//获取线性表长度 
int isEmptyList(List &list);										//判断是否为空表 
void printStudentList(List &list);									//打印线性表

线性表的初始化操作

线性表的初始化操作很容易理解，主要就是通过molloc函数动态为Student类型开辟内存空间(即相当于容量为100的Student数组)，初始化List表的长度为0，存储容量的范围为LIST_INIT_SIZE=100个。

//数据结构 算法2.3实现---> 初始化线性表操作 
int initList(List &list)
{
    
	//构造一个空的线性表 
	list.student = (Student *)malloc(LIST_INIT_SIZE*sizeof(Student));
	if(!list.student) return OVERFLOW;				//如果分配失败，返回数据溢出信息 
	list.length = 0;								//空表的长度初始化为0 
	list.listsize = LIST_INIT_SIZE;					//初始存储容量为默认容量 
	return OK;
}

线性表的插入增加操作(重要)

线性表的插入增加算法是本节的一个重点，要求给定顺序表List，插入位置i(顺序表以1，2，3，4…表示位置)，把待插入的数据元素student插入到顺序表中。

抛开其它判断条件，难点就是如何在顺序表的指定位置进行插入操作？

我们可以这样设想，假如我们从线性表的最后一个元素开始，依次进行后挪操作(即前面的一个会覆盖后面的一个)，一直挪到待插入的位置，这时第i个位置和第i+1个位置的元素是一样的，我们直接再把student赋值给第i个位置的元素，就能够完成插入操作了。

操作如该图(对应算法如下)
插入完毕以后，对线性表长度进行增加，之后返回操作结果。

代码实现：

//数据结构 算法2.4实现 ----> 学生线性表的插入操作
int insertStudentList(List &list, int i, Student student)
{
    
	if(i < 1 || i > list.length+1)	return ERROR;		//若插入位置不合法，直接返回 
	if(list.length >= list.listsize)
	{
    
		//调用realloc()函数 对list.student的容量大小再次进行动态开辟 
		list.student = (Student *)realloc(list.student, (list.listsize + LISTINCREMENT)*sizeof(Student));
		if(!list.student) return OVERFLOW;				//如果开辟失败，返回失败信息 
		list.listsize += LISTINCREMENT;					//线性表的最大容量更新 
	}
	
	Student *q = &list.student[i-1];			//保存 q为线性表的插入位置 
	 
	for(Student *p = &list.student[list.length-1]; p >= q; p--)			//核心代码，待插入元素后的元素层层后挪 
	*(p+1) = *p;								//层层后挪操作，前面的数据元素覆盖后面的数据元素 
	
	list.student[i-1] = student;				//把待插入数据进行插入到指定位置 
	list.length++;								//学生列表数量增加 
	
	return OK;
}

线性表的删除操作(重要)

线性表的删除算法也是本节的一个重点，要求给定顺序表List，删除位置i(顺序表以1，2，3，4…表示位置)，并且把删除的元素以student返回。

该难点就是如何在顺序表的指定位置进行删除元素操作？

其实这个算法和上一个算法有异曲同工之妙，我们可以这样设想，假如我们从线性表的i个元素开始，依次进行前挪操作(即后面的一个会覆盖前面的一个)，一直覆盖到第length-1个元素，此时覆盖已完毕，删除完毕，会形成下图的结果，直接对线性表的长度减1即可，视为删除成功。

算法如下:

//数据结构 算法 2.5实现 ----> 学生线性表的删除操作 ，以参数student保存输出信息 
Student deleteStudentList(List &list, int i, Student &student)
{
    
	if(i < 1 || i > list.length) return student;		//若删除位置不合法， 删除失败，返回原始信息 
	
	student = list.student[i-1];			//对待删除元素进行保存备份 
	for(Student *p = &list.student[i-1]; p < &list.student[list.length-1]; p++)		//核心代码，从指定位置开始从后往前依次覆盖 
	*p = *(p+1);							//从后向前层层覆盖 
	
	list.length--;							//长度减1 
	
	return student;							//返回已删除的保存元素 
}

两个有序线性表的合并操作

两个有序线性表的合并要求合并两个线性表，要求合并以后的线性表依然是有序的，例如：

L1: 1 2 3 5 6
L2: 1 1 2 3 5
L3: 1 1 1 2 2 3 3 5 5 6

算法实现：

//数据结构 算法2.7实现 ----> 将两个有序的线性表合成一个新的有序表，要求它也有序 
int mergeOrderList(List &list_a, List &list_b, List &list_c)
{
    
	//定义pa为线性表1的第一个元素, pa_last为线性表的最后一个元素, pb同理 
	Student *pa = &list_a.student[0], *pa_last = &list_a.student[list_a.length-1]; 
	Student *pb = &list_b.student[0], *pb_last = &list_b.student[list_b.length-1];
	
	//将pa和pb的长度和容量加起来为pc的长度和容量 
	list_c.length = list_a.length + list_b.length;
	list_c.listsize = list_a.listsize + list_b.listsize;
	
	//为pc开辟存放有序排列的两个线性表的内存空间 
	list_c.student = (Student *)malloc((list_c.listsize)*sizeof(Student));
	
	//pc为指向线性表3学生元素的首元素s 
	Student *pc = &list_c.student[0];
	
	//核心代码 
	while(pa<=pa_last && pb<=pb_last)		//若线性表1和线性表2都未遍历完 
	{
    
		//若线性表1的元素小于(升序排列)线性表2的元素，则把pa中的元素进行pc插入, pa、pc都指向其线性表的下个元素单元 
		if(pa->id <= pb->id) *pc++ = *pa++; 
		else *pc++ = *pb++;							//否则把pb中的元素进行pc插入, 同理改变指向 
	}
	
	while(pa <= pa_last) *pc++ = *pa++;			//若pa插入未完全，则把pa的左右元素都追加至pc 
	while(pb <= pb_last) *pc++ = *pb++;			//pb亦然， 但pa、pb至多有一个未完成 
	
	return OK;			//返回状态信息 
}

查找线性表的某个数据元素的位置

通过暴力循环查找出线性表中符合条件的元素，返回其位置

//数据结构 算法2.6实现 ---->学生线性表的查找操作，根据指定元素检索元素在线性表中的位置 
int locateStudent(List &list, Student student)
{
    
	int i = 1;
	for(int i = 1; i <= list.length; i++)			//通过循环暴力查找 
	{
    
		if(student.id==list.student[i-1].id && student.age==list.student[i-1].age)
		return i;								//成功找到返回序号 
	}
	return FALSE;								//无法找到返回失败信息 
}

其它重要的方法

输出列表方法PrintStudentList()、销毁学生列表方法destoryStudentList()、获取列表长度getListLength()、判断空列表函数isEmptyList()

//输出所有学生信息 
void printStudentList(List &list)
{
    
	printf("学生信息表如下:\n");
	for(int i = 0; i <= list.length-1; i++)
	printf("id = %d, age = %d.\n", list.student[i].id, list.student[i].age);
	printf("学生容量:\t%d.\n共有 %d 行信息.\n", list.student, list.length);
}

//销毁学生列表 
int destoryStudentList(List &list)
{
    
	free(list.student);
	list.student = NULL;
	list.length = 0;
	list.listsize = 0;
	return OK;
}

//获取列表长度 
int getListLength(List &list)
{
    
	return list.length;
}

//判断非空列表函数 
int isEmptyList(List &list)
{
    
	if(list.length == 0) return TRUE;
	else return FALSE;
}

总结，线性表的顺序存储和表示随机存取元素比较方便，元素的插入和删除等操作需要不断地移动数据元素，较为麻烦。

下次再次学习更新线性表的链式存储与表示，诸君共勉~