【数据结构】顺序表

线性表的定义和特点

线性表是具有相同特性的数据元素的一个有限序列 $$ (a_1，a_2，…a_(i-1)，a_i，a_(i+1)，…，a_n)$$ 线性表（Linear List）: 由n(n>=0)个数据元素（结点） $$ a_1，a_2，…，a_n$$ 组成的有限序列 其中数据元素的个数n定义为表的长度 当n为0时称为空表 将非空的线性表记作： $$ a_1，a_2，…，a_n$$ 这里的数据元素 $$ a_i(1<=i<=n)$$ 只是一个抽象的符号，其具体含义在不同的情况下可以不同。

线性表的例子

同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系

线性表的逻辑特征

线性表是一种典型的线性结构

案例引入

线性表A=（（7，0），（3，1），（9，8），（5，17）） 线性表B=（（8，1），（22，7），（-9，8）） 创建一个新的数组c 分头从头遍历比较a和b的每一项 指数相同，对应系数相加，若其和不为0，则在c中增加一个新项 指数不相同，则将指数较小的项复制到c中 一个多项式已遍历完毕时，将另一个剩余项一次复制到c中即可 需要的功能 查找 插入 删除 修改 排序 计数 图书表抽象为线性表，表中每本图书抽象线性表中数据元素 总结 线性表中数据元素的类型可以为简单类型，也可以为复杂类型。 许多实际应用问题所涉及的基本操作有很大相似性，不应为每个具体应用单独编一个程序。 从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。

线性表的类型定义

基本操作（一）

基本操作（二）

基本操作（三）

基本操作（四）

基本操作（五）

基本操作（六）

线性表的顺序表示和实现

线性表的顺序表示又称为顺序存储结构或顺序映像

例如：线性表（1，2，3，4，5，6）的存储结构：

顺序表中元素存储位置的计算

顺序表的顺序存储表示

顺序表元素的特点：地址连续、依次存放、随即存取、类型相同，类似于数组，可用一维数组表示顺序表。 线性表长度可变，而数组长度不可动态定义 解决办法：用一变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#defien LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct
{
	ElemType *elem;//存储空间的基地址

	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;

顺序表的初始化

顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为0

Status InitList_Sq(SqList &L)
{
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem) exit(OVERFLOW);//存储分配失败
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	return OK;
}

类C语言有关操作

传地址方式————指针变量作参数 传地址方式————数组名作参数 传递的是数组的首地址，对形参数组所做的任何改变都将反映到实参数组中 传地址方式————引用类型作参数（C++的语法） 引用就是用来给一个对象提供一个替代的名字 引用类型作形参的三点说明 （1）传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化。 （2）引用类型作形参，在内存中并没有产生实参的副本，它直接对实参操作；而一般变量作参数，形参与实参就占用不同的存储单元，所以形参变量的值是实参变量的副本。因此，当参数传递的数据量较大时，用引用比一般变量传递参数的时间和空间效率都好。 （3）指针参数虽然也能达到与使用引用的效果，但在被调函数中需要重复使用“指针变量名”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。

顺序表的插入

算法思想 1.判断插入位置是否合法，数组元素是否在1~n+1,下标是否在0~n 2.判断顺序表的存储空间是否已满，若已满返回ERROR 3.将第n至第i位的元素依次向后移动一个位置，空出第i个位置 4.将要插入的新元素e放入第i个位置。 5.表长加1，插入成功返回OK 算法：

Status ListInsert_Sq(Sqlist &L,int i,ElemType e)
{//在顺序表L中的第i个元素之前插入元素e
//判断插入位置的合法性
if(i<1||i>length+1) return ERROR;
//判断顺序表的存储空间是否已满，已满则扩容
if(L.length>=L.listsize)//当前存储空间已满，增加分配
{
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))
if(!newbase) exit(OVERFLOW);//存储分配失败
L.elem=newbase;//分配新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
q=&(L.elem[i-1]);//插入位置
for(&(L.elem[length-1]);p>=q;p--)
*(p+1)=*p;//插入位置及之后的元素后移
*q=e;//插入e
++length;//表长加1
return OK;
}

顺序表的删除

Status ListDelete_Sq(SqList* L, int i, ElemType* e)
{
	//判断删除位置i是否合法
	if ((i < 1) || (i > L->length))
		return ERROR;
	p = &(L.elem[i - 1]);//p为被删除元素的位置
	e = *p；//被删除元素的值赋给e
	q = L.elem + L->length - 1;//表尾元素的位置
	for (++p; p <= q; ++p)//被删除元素之后的元素左移
		*(p - 1) = *p;
	--L.length;
	return OK;

顺序表的查找

算法实现

int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
//在顺序线性表中查找第一个值与e满足compare()的元素的位序
//若找到，则返回其在L中的位序，否则返回0
i；//i的初值为第一个元素的位序
p=L.elem//p的初值为第一个元素的存储位置
while(i<=L.length&&!(*compare)(*p++,e))
++i;
if(i<=L.length)
return i;
else
return 0;
}

补充：函数指针

插入、删除、查找C语言实现

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define OVERFLOW -2
#define OK 1
typedef int Status;
typedef int ElemType;
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
	ElemType* elem;
	int length;
	int listsize;
}SqList;
Status InitList_Sq(SqList *L)
{
	L->elem = (ElemType*)malloc(sizeof(ElemType));
	if (!L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	int n;
	printf("输入顺序表的长度:\n");
	scanf_s("%d", &n);
	printf("输入数据:\n");
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &L->elem[i]);
		L->length++;
	}
	printf("顺序表为:\n");
	for (int i = 0; i < L->length; i++)
	{
		printf("%d ", L->elem[i]);
	}
	printf("\n");
	return OK;
}
Status ListInsert_Sq(SqList* L, int i, ElemType e)
{
	ElemType* p=NULL,* q=NULL;
	
	if (i<1 || i>L->length + 1)
		return ERROR;
	if (L->length >= L->listsize)
	{
		ElemType* newbase;
		newbase = (ElemType*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
		if (!newbase)
			exit(OVERFLOW);
		L->elem = newbase;
		L->listsize += LISTINCREMENT;
	}
	q = &(L->elem[i - 1]);
	for (p = &(L->elem[L->length - 1]); p >= q; p--)
		*(p + 1) = *p;
	*q = e;
	++L->length;
	return OK;
}
Status ListDelete_Sq(SqList* L, int i, ElemType* e)
{
	ElemType* p, * q;
	if (i<1 || i>L->length)
		return ERROR;
	p = &(L->elem[i - 1]);
	e = *p;
	q = L->elem + L->length - 1;
	for (++p; p <= q; ++p)
		*(p - 1) = *p;
	--L->length;
	return OK;
}
int LocateElem_Sq(SqList L, ElemType  e,Status(*compare)(ElemType, ElemType))
{
	int i = 1;
	ElemType* p = L.elem;
	while (i <= L.length && !(*compare)(*p++, e))
		++i;
	if (i <= L.length)
		return i;
	else
		return 0;
}
Status fun2(ElemType x, ElemType e)
{
	if (x == e)
		return 1;
	else
		return 0;
}
int main()
{
	SqList L;
	InitList_Sq(&L);
	int ipos;
	ElemType e;
	printf("\n请输入插入元素及插入位置:\n");
	scanf_s("%d %d", &e, &ipos);
	ListInsert_Sq(&L,ipos,e);
	printf("\n插入后的顺序表为:\n");
	for (int i= 0; i< L.length; i++)
		printf("%d ", L.elem[i]);
	printf("\n请输入要删除元素的位置:\n");
	int delpos;
	scanf_s("%d", &delpos);
	printf("删除后的顺序表为:\n");
	ListDelete_Sq(&L, delpos, &e);
	for (int i = 0; i < L.length; i++)
		printf("%d ", L.elem[i]);
	printf("\n请输入要查找的元素:\n");
	int locate;
	scanf_s("%d", &locate);
	int i=LocateElem_Sq(L, locate, fun2);
	printf("查找元素位序为%d\n", i);
	return 0;
}