线性表（数据结构学习笔记)

线性表的定义

• 线性线（list）：由零个或多个数据元素组成的有限序列。
• 需要强调的几个地方：
  1. 首先它是一个序列，也就是说元素之间是有先来后到的。
  2. 若元素存在多个，第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。
  3. 另处，线性表强调的是有限的。
• 如果用数学语言来进行定义，可如下：
• 若将线性表记为（a₁,…,a_i-1,a_i,a_i+1,…,a_n）,则表中a_i-1领先于a_i,a_i领先于a_i+1,称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。
• 所以线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。

抽象数据类型

• 例如在c语言中，按照取值的不同，数据结构可以分成两类：
  1. 原子类型：不可以再分解的基本类型，例如整型、浮点型、字符型等。
  2. 结构类型：由若干个类型组合而成，是可以再分解的，例如整型数组是由若干个整形数据组成的。
• 抽象：是指抽取出事物具有的普遍性的本质。它要求抽出问题特征而忽略非本质的细节，是对具体事物的一个概括。抽象是一种思维方式，它隐藏了事物的繁杂的细节。
• 我们对已有的数据类型进行抽象，就有了抽象数据类型。
• 抽象数据类型（Abstract Data Type,ADT）是指一个数学模型及定义在该模型上的一组操作。
• 抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如果表示和实现无关。
• “抽象”的意义在于数据类型的数学抽象特性。

抽象数据类型标准格式

ADT 抽象数据类型名
Data
	数据元素之间逻辑关系的定义
Operation
	操作
endADT

线性表的抽象数据类型

• 所谓抽象数据类型就是数据类型和相关操作捆绑到了一起。

• ADT 线性表（list）

• Data
  线性表的数据对象集合为{a₁,a₂,…,a_n}，每个元素的类型均为DataType。

• Operation
  InitList(*L):初始化操作，建立一个空的线性表L。
  ListEmpty(L):判断线性表是否为空表，若线性表为空，则返回true，否则返回false。
  ClearList(*L):将线性表清空。
  GetElem(L,i,*e):将线性表第I个位置元素值返回给e。
  LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
  ListInsert(*L,i,e):在线性表L中第i个位置插入新元素e。
  ListDelete(*L,i,e):删除线性表L中第i个位置元素，并用e返回其值。
  ListLength(L):返回线性表L的元素个数。

• endADT

• 举个例子：如果要实现两个线性表的A、B的并操作，即要使得A=A∪B。
  说白了就是把不存在于A中的B集合中的元素插入到A中即可。

  分析：我们只需要循环遍历集合B中的每个元素，判断当前元素是否存在A中，如果不存在，则插入A中。
  我们需要用到的操作：
  - ListLength(L);
  - GetElem(L,i,*e);
  - LocateElem(L,e);
  - ListInsert(*L,i,e);

• 代码：

//La表示A集合，Lb表示B集合。
void unionL(List *La,List Lb){
	int La_len,Lb_len,i;

	ElemType e;
	La_len = ListLength(*La);
	Lb_len = ListLength(Lb);

	for(i=1;i<=Lb_len;i++){
		GetElem(Lb,i,&e);
		if(!locateElem(*La,e)){
			ListInsert(La,++La_len,e);
		}
	}
}

TODO待补充…