数据结构和算法_零基础入门03_线性表

一、线性表的一些定义1、线性表(List）2、数据类型3、抽象数据类型 二、线性表的抽象数据类型1.线性表的抽象数据类型定义2.基本操作的组合

---

b站学习小甲鱼的数据结构与算法，自留笔记。

---

一、线性表的一些定义

1、线性表(List）

线性表(List）：0个或多个数据元素组成的有限序列。 线性表元素个数n（n>=0）定义为线性表的长度，n=0是空表。 关键点： 1、序列：有先后顺序 2、多元素时，除了首尾，其他元素都有且只有一个前驱和后继。 3、元素是有限的

2、数据类型

数据类型：一组性质相同的值的集合，以及定义在集合上的一些操作的总称。例如编程语言中的整型、浮点型.…

数据类型的意义：不同的数据在内存中开辟不同大小的空间。

数据类型分类：（按照取值不同） 原子类型：不可再分，如整型、字符型等。 结构类型：若干个类型组合而成，可再分解。如整型数组可分为若干整型数据。

3、抽象数据类型

抽象数据类型（Abstract Data Type, ADT）：一个数学模型及定义在该模型上的一组操作。（把数据类型和相关操作捆绑在一起） 抽象的意义：数据类型的数学抽象特性。 计算机编程者在设计软件程序时可以自己定义的数据类型。

抽象数据类型的标注格式：

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

二、线性表的抽象数据类型

1.线性表的抽象数据类型定义

ADT 线性表(List) Data 数据元素之间的逻辑关系的定义 线性表的数据对象集合为{a1,a2,...,an},每个元素的类型为DataType。数据元素间关系是一对一的。 Operation 操作： InitList(*L):初始化操作，建立一个空的线性表L ListEmpty(L):判断线性表是否为空表，为空返还ture；否则false ClearList(*L):清空线性表 GetElem(L,i,*e):线性表L中第i个位置的元素值返还给e LocateElem(L,e):线性表L中查找与给定的值e相等的元素，查找到：返回该元素在表中的序号；否，返回0. ListInsert(*L,i,e):线性表L中第i个位置插入新元素e ListDelete(*L,i,*e):删除线性表L中第i个位置的元素，并用e返回其值 ListLength(L):返回线性表中元素的个数 endADT

注意：线性表中的序号从1开始的。

2.基本操作的组合

线性表A,B并集操作，A=A∪B 分析：把存在于B中但不在A中的元素插入A。循环遍历B中每个元素，判断是否在A中，不在则插入。 基础操作： ListLength(L); GetElem(L,i,*e); LocateElem(L,e); ListInsert(*L,i,e);

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(L,i,*e); if(!LocateElem(L,e)) { ListInsert(*L,i,e); } } }

---

组合代码仍然存在学习疑惑，后期学习跟进