线性表的定义和基本操作

小半 • 2023年1月22日下午6:24 • 技术随笔 • 阅读 163

线性表的定义：

线性表是具有相同数据类型[每个数据元素所占的空间相同]的n（n>=0）个数据元素的有限序列[表中的元素必须是有限的，并且按照一定的次序进行排列]，其中n为表长，当n=0时线性表是一个空表，若用L命名线性表，则一般表示为：L=（a1,a2…ai,ai+1…an）

注：

ai是线性表中的‘第i个’元素线性表中的位序[位序是从1开始，而数组下标是从零开始]

a1是表头元素，an是表尾元素

除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的基本操作：

lnitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

Listlnsert(&L,i,e):插入操作。在表L中第i个位置上，插入元素e.

ListDelete(&L,i,&e):删除操作。删除表中第i个位置上的元素，并用e返回删除元素的值。

LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

GetElem(L,i):按位查找操作。获取表L中第i个位置元素的值

其他常见操作：

length(L):求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L):输出操作。按先后顺序输出线性表L的所有元素的值。

Empty(L):判空操作。若L为空表，则返回True,否则返回False.

注：

函数名和参数形式，命名都可发生改变，但是命名必须具有可读性。

什么时候要传入参数的引用“&”？—–对参数的修改结果需要“传递回来”

举例：

#include<stdio.h>
void test(int x)
{
	x = 1024;
	printf("test函数内部 x=%d\n", x);
}
int main()
{
	int x = 1;
	printf("调用test前 x=%d\n", x);
	test(x);
	printf("调用test后 x=%d\n", x);
	return 0;
}

通过输出结果，我们会发现即使调用了test函数，但x的值依然没有被修改，其原因就是在函数调用的过程中，我们传递给test函数的是x的值，在test函数内部将该值修改了，这个操作只在test函数内部生效，但实际上该数据并没有真正的被修改，因此返回给主函数的x值依然是修改前的值，有点类似于C语言指针部分的值传递和地址传递问题。

要想实现跨函数修改，就要使用”&”引用

修改如下：

#include<stdio.h>
void test(int *x)
{
	*x = 1024;
	printf("test函数内部 x=%d\n", *x);
}
int main()
{
	int x = 1;
	printf("调用test前 x=%d\n", x);
	test(&x);
	printf("调用test后 x=%d\n", x);
	return 0;
}