资源描述：
《C语言数据结构_第02讲 线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线性表线性表知识点线性数据结构的定义与存储单链表的基本运算和算法循环链表的基本特点双链表的结点形式和特点双链表的基本运算和算法顺序表与链表比较难点双链表插入、删除运算的算法利用链表结构的特点设计算法要求熟练掌握以下内容:顺序表存储地址的计算单链表的结构特点和基本运算双链表的结构特点和基本运算目录2-1线性表的定义与运算2-2线性表的顺序存储2-3线性表的链式存储结构小结实验2线性表子系统习题22-1线性表的定义与运算2-1-1线性表的定义1．线性表的定义线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，通常记为：(a1，a2，…ai-1，
2、ai，ai+1，…an)其中n为表长，n＝0时称为空表。在线性表中相邻元素之间存在着顺序关系。对于元素ai而言，ai-1称为ai的直接前趋，ai+1称为ai的直接后继。即：（1）有且仅有一个开始结点（a1），它没有直接前趋；（2）有且仅有一个终端结点（an），它没有直接后继；（3）除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。2．线性表举例（1）简单的线性表例如一年12个月：（1，2，3，4，5，6，7，8，9，10，11，12）在C或C++语言中我们可以把它们定义为数值型。又例如26个英文字母表：（a，b，c，d，e，
3、f，g，……，x，y，z）在C或C++语言中我们可以把它们定义为字符型。（2）复杂的线性表例如我们曾经在绪论中引用的一个学生入学情况表（表1-1）可以是用户自定义的学生类型（如C语言中的结构体或数据库管理系统中的记录）。由于表格中各记录之间存在“一对一”的关系，所以它也是一种线性表。3．线性表的二元组表示：Linearity=（D，R）数据对象：D=｛ai∣1<=i<=nn>=0｝数据关系：｛∣2<=i<=n｝ai-1,ai∈D关系中是一个序偶的集合，它表示线性表中数据元素的相邻关系，即ai-1领先ai，ai领先a
4、i+1。2-1-2线性表的基本操作线性表上的基本操作有：⑴创建线性表：CreateList()初始条件：表不存在操作结果：构造一个空的线性表⑵求线性表的长度：LengthList(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数(3)按值查找：SearchList(L,x)，ｘ是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功；否则，在L中未找到值为ｘ的数据元素，返回一个特殊值表示查找失败。(4)插入操作：InsList(L,i,x)初始
5、条件：线性表L存在，插入位置正确(1<=i<=n+1,ｎ为插入前的表长)。操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i,i+1,...,n的数据元素的序号变为i+1,i+2,...,n+1，插入后表长=原表长+1。(5)删除操作：DelList(L,i)初始条件：线性表L存在，1<=i<=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号为i,i+1,...,n-1，新表长＝原表长-１。(6)显示操作：ShowList(L)初始条件：线性表L存在，且非空。操作结果：显
6、示线性表L中的所有元素。2-2-1顺序表线性表的顺序存储是指在用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。顺序表的逻辑顺序和物理顺序是一致的。设a1的存储地址LOC(a1)为首地址B，每个数据元素占d个存储单元，则第i个数据元素的地址为：LOC(ai)=LOC(a1)+(i-1)*d1<=i<=n即：LOC(ai)=B+(i-1)*d这就是说只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。2-2线性表的顺序存储
7、在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，可以用一维数组来表示：datatypedata[MAXLEN];intlast;如顺序表中，设表长为last+1，则数据元素分别存放在data[0]到data[last]中。从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型：typedefstruct{datatypedata[MAXLEN];intlast;}SeqList;定义一个顺序表：SeqList*L；2-2-2顺序表上基本运算的实现1．顺序表的初始化顺序表的初始化即构造一个空表，将L设为指针参数，
8、动态分配存储空间，然后，将表中last指针置为-1，表示表为空。算法如下：SeqList*InitList(
