线性表的定义和基本操作

定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，一般表示为：L = (a1,a2,a3,...,an)

注：

• 所有的相同的数据类型意味着每个数据元素所占空间一样大
• 各个数据元素有顺序而且是有限的
• ai是线性表中的第i个元素线性表的位序
• a1是表头元素，an是表尾元素

线性表的基本操作

• InitList（&L）：初始化表，构造一个空的线性表L，分配内存空间

• DestroyList（&L）：销毁操作，销毁线性表，并释放线性表L所占用的内存空间

• ClearList（&L）：将已经存在的线性表L重置为空表

• ListInsert（&L，i，e）：插入操作，在表L中的第i个位置上插入指定元素e

• ListDelete（&L，i，&e）：删除表L中的第i个位置的元素，并用e返回删除元素的值

• LocateElem（L，e，compare()）：按值查找操作：在表L中查找具有给定关键字值的元素，compare()数据元素判定函数

• 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);
}

运行后的结果为：

如果我们把函数test稍稍修改：

void test(int & x)

这时候调用test后的x就被修改了

例题

用线性表LA和LB分别表示两个有限集合A、B，现在需要求一个新的集合 A U B

分析：求取集合 A U B及是A、B的并集，即将集合B的元素插入到A的集合，但是不能插入含有A集合相同的元素。

实现：

1. 通过Length（L）判断线性表的长度
2. 通过GetElem（L，i）取线性表Lb中的i个元素赋给e
3. 判断La中不存在e相同的数据元素，插入

void union(List &La, List Lb){
	La_len=Length(La);
	Lb_len=length(Lb);
	for(int i=1; i<=Lb_len; i++){
		GetEmel(Lb,i,e);
		if(!LocateElem(La,e,equal)){
			ListInsert(La,++La_len,e);
		}
	}
}