数据结构：线性表顺序存储结构———顺序表

目录

顺序表的定义

初始化线性表

销毁线性表

求线性表的长度

判断是否为空表

插入数据元素

逻辑序号与物理序号的区别

删除数据元素

输出线性表

?按序号求线性表中的元素

按元素值查找

整体上创建顺序表

顺序表实验

---

线性表的顺序存储是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的空间。

说直白点就是在内存中找了一块地，通过占位的形式，把一定的内存空间给占了，把你要存的数据元素按照顺序存进这块空间。仔细想想存进一维数组里是不是挺契合的，数组下标从0开始存第一数据，依次往后存，这样就保证了相邻数据元素存在了相邻的位置。

顺序表的定义

#include <stdio.h>
#define MaxSize 100
typedef  char ElemType;
typedef struct
{
	ElemType data[MaxSize];
	int length;
}SqList;

typedef struct{ ............} SqList ;是指把结构体类型名struct重命名为SqList,SqList是等价于struct的，SqList是类型名；

如果没有typedef,直接struct {.......}SqList,那么SqList是结构体变量，不是类型名。

开头定义了typedef char ElemType；，其实就是把char用ElemType表示了，ElemType其实就是char。

而#define MaxSize 100等价于，MaxSize=100；

所以ElemType data[MaxSize]其实就是一个大小为100，类型为char的数组，char data[100]，用来存放数据元素

length是这个顺序表已经存了多少元素

初始化线性表

void InitList(Sqlist*& L)
{
	L = (SqList*)malloc(sizeof(SqList));
	L->length = 0;
}

用malloc函数给结构体SqList顺序表分配一个空间?，以方便给顺序表存元素，结构体指针L去接收这片新开辟空间的首地址，结构体指针L访问结构体内部成员int length将其初始化为0。为什么顺序表长度length为0呢，这个length其实代表的是顺序表已经存了多少个元素，此时没有元素，所以为0，后续增加元素和删除元素操作会改length的值。

这个SqList *&L其实是结构体指针SqList *L，为什么会写得这么奇怪呢SqList*& L，这个&不是取地址的意思，而是引用的意思。c语言里传值传参，形参的改变不会影响实参，通过引用可以在函数内部修改指针L所指向的结构体，而不是仅仅修改指针本身的值。但是需要注意的是c语言没有引用，引用是c++里面的，所以有些纯c语言编译器可能会报错。

同样纯c语言编译器中，可以通过用二级指针SqList **L接收L这个指针变量的地址，这时也可以在函数内部修改指针L所指向的结构体。

销毁线性表

在上面操作中可以知道malloc分配了空间给线性表存元素，用指针L去接收，现在要销毁线性表怎么操作。直接把这一片空间全部销毁就行了，free(L)意思就是释放了L所指向的空间。

void DestroyList(SqList*& L)
{
	free(L);
}//销毁顺序表

求线性表的长度

?结构体SqList里成员length记录的就是线性表的长度直接输出就可以了

void lengtht(SqList*L)
{
	return L->length;
}

判断是否为空表

依旧要用到length，length代表的是顺序表已经存了多少个元素，增加元素和删除元素操作会改length的值。?删除就是length--，增加就是length++。如果为空表要么就是一个也没插进去，此时保持初始化length=0;要么就是全删完了，length--一直到length为0。

所以直接判断length是不是等于0就行

bool ListEmpty(SqList* L)
{
	if (L->length == 0)
	{
		return 0;
	}
	else
		return 1;
}

其实也可以直接写成这样

bool ListEmpty(SqList* L)
{
	return (L->length==0);
}

?返回的是布尔（bool）值，如果为真返回0，如果为假返回1。不支持c99标准的c语言编译器使用bool函数会报错。

插入数据元素

逻辑序号与物理序号的区别

我们日常生活中，数数都是从1开始的，比如排队买东西，排在首尾的就是第1位。而数组是从0开始的，排在首位的是第0位，而不是第1位。

bool ListInsert(SqList*& L, int i, ElemType e)
{
	if (i<1 || i>L->length + 1 || L->length == MaxSize)
		return false;
	i--;
	for (int j = L->length; j > i; j--)
		L->data[j] = L->data[j - 1];
	L->data[i] = e;
	L->length++;
	return true;
}

?bool ListInsert(SqList*& L, int i, ElemType e) 是指在第i个位置上插入元素e，这个i要注意是逻辑序号，对应数组0

1.首先要考虑这个位置是不是合适，它可以在第一个位置上插进去，也可以在最后的位置插进去，也就是length+1的位置

2.所以合理的范围应该是1<=i<=length+1,同时也应该注意存数据是往数组data[MaxSize]里存，数组是定长MaxSize大小的，超过MaxSize就越界了

写成代码就是这样了? if (i<1 || i>L->length + 1 || L->length == MaxSize)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return false;??

如果在这个范围内那应该怎么存呢，举个例子现在有个一个长队买东西王二，李明，张三，李四，王五，我要插队插在李明后面张三前面，该怎么办。张三李四王五挨个往后退就能空出个位置让我插了

i--是将逻辑序号转变为了物理序号，毕竟是要存到数组里，所以还是用数组下标的物理序号好一点

for (int j = L->length; j > i; j--)
?? ??? ?L->data[j] = L->data[j - 1];

王二，李明，张三，李四，王五 这五个人对应的数组下标为0，1，2，3，4

从后往前挪动，此时L->length=5， L->data[5]=L->data[4]这就是把王五往后面挪了一个位置，从数组下标为4的位置放到下标为5的位置。

重复上述操作，数组下标为2的地方就空出来了，L->data[i] = e;把值写进去，然后length加1就行
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L->length++;

length是指数组里现在存了多少个元素

这是在中间插的，如果是在开头开始插，那么后面所有的都得往后挪，也是适用于这个循环的，要挪动后面n个元素，此时是最坏的情况

如果是在最后一个位置插元素，那么就直接L->data[i] = e;?? L>length++;?

删除数据元素

bool ListDelete(SqList*& L, int i)
{
	if (i<1 || i>L->length || L->length == MaxSize)
	{
		return false;
	}
	for (int j = i; j < L->length; j++)
	{
		L->data[j] = L->data[j+1];
	}
	L->length--;
	return true;
}

删除数据元素与插入数据元素类似，都是不能超过1<=i<=length+1这个范围

所以i<1 || i>L->length || L->length == MaxSize过了这个范围，直接返回false就行

怎么做到删除呢，其实就是把后项的数据直接覆盖前一项的数据，然后把length减1就行，而不是释放i这个位置的空间。for (int j = i; j < L->length; j++)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L->data[j] = L->data[j+1];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?L->length--;

从i开始，用i后面的数据覆盖i这个位置的数据

有些书上可能会把代码写成这样

bool ListDelete(SqList*& L, int i, ElemType &e)
{
	if (i<1 || i>L->length || L->length == MaxSize)
		return false;
	i--;
	e = L->data[i];
	for (int j =i; j<L->length; j++)
	{
		L->data[j - 1] = L->data[j];
	}
	L->length--;
	return true;
}  

为什么要用e去保存要删除的值呢，使用e来记录删除的元素值的原因是为了给调用者提供该元素的值。在某些情况下，当从顺序表中删除一个元素时，可能会需要知道该元素的值，例如在需要检查被删除元素是否满足特定条件的情况下。通过将删除的元素值赋给e，函数调用者可以获得该值并进行进一步的处理或使用

如果你用不到的话，用上一个代码也行，不过考试还是用下面那个完整的代码

输出线性表

void DispList(SqList* L)
{
	if (ListEmpty(L))
		return;
	for (int i = 0; i < L->length; i++)
	{
		printf("%c", L->data[i]);
		printf("\n");
	}
}

先判断是不是空，如果是空就return空，剩下的就是打印数组的值，这就不加多赘述了

?按序号求线性表中的元素

bool GetElem(SqList* L, int i, ElemType& e)
{
	if (i<1 || i>L->length)
		return false;
	e = L->data[i - 1];
	return true;
}

就是直接通过下标去访问数组，得到这个下标对应的值

bool GetElem(SqList* L, int i, ElemType& e) 意思是去找数组里第i个元素的值，并把值用e去接收。第i个元素对应的是逻辑序号，物理序号从0开始，要转变为数组下标的物理序号需要减1

按元素值查找

int LocateElem(SqList* L, ElemType e)
{ 
	int i = 0;
	while(i < L->length && L->data[i] != e)
		i++;
	if (i >= L->length)
		return 0;
	else
		return i + 1;
}

?while(i < L->length && L->data[i] != e)
?? ??? ?i++;

退出循环有两种条件，要么i>=L->length,意思是查找到表末尾都没有L->data[i]=e，那么就返回0；

要么退出循环就只是因为找到值了，因为此时是数组物理下标，但是一般要返回逻辑序号，所以要加1。

整体上创建顺序表

void CreateList(SqList*& L, ElemType a[], int n)
{
	int i = 0; int k = 0;
	L = (SqList*)malloc(sizeof(SqList));
	while (i<n)
	{
		L->data[k] = a[i];
		i++; k++;
	}
	L->length = k;
}

实质上就是把要存的元素，事先先放进一个数组里，然后把这个数组整体存进data[MaxSize]数组中，也就是从一个数组存到另一个数组

1. 初始化两个整数变量i和k，都为0。这两个变量将用于遍历数组和顺序表。
2. 使用malloc函数为顺序表分配内存。sizeof(SqList)返回顺序表结构的大小，确保足够的空间用于存储数据。
3. 使用while循环遍历数组的前n个元素。循环条件是索引i小于n
4. 在循环内部，将数组元素a[i]赋值给顺序表的当前位置L->data[k]。增加索引i和k的值，以便在下一次迭代中处理下一个数组元素和顺序表位置。
5. 将顺序表的长度设置为已复制的元素数量，即变量k的值

?你也可以不用这个，直接用ListInsert,把需要的元素一个一个地插进去

顺序表实验

如果你不知道对应的main函数里写什么，可以参考我之前写的实验

http://t.csdnimg.cn/leA25