第2章线性表 2.1线性表的类型定义 2.2线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4一元多项式的表示及相加
第2章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加
21线性表的类型定义 线性结构的特点 在数据元素的非空有限集中,1)有且仅 有一个开始结点;2)有且仅有一个终端结点; 3)除第一个结点外,集合中的每个数据元素 均有且只有一个前驱;4)除最后一个结点外 集合中的每个数据元素均有且只有一个后继 线性序列:线性结构中的所有结点按其关系 可以排成一个序列,记为(a1,,a1n1.n)
2.1 线性表的类型定义 ◼ 线性结构的特点： 在数据元素的非空有限集中，1）有且仅 有一个开始结点；2）有且仅有一个终端结点； 3）除第一个结点外，集合中的每个数据元素 均有且只有一个前驱；4）除最后一个结点外， 集合中的每个数据元素均有且只有一个后继。 ◼ 线性序列：线性结构中的所有结点按其关系 可以排成一个序列，记为(a1 ,…,ai ,ai+1,…an )
2.1线性表的类型定义 1.线性表 1)线性表是n(n20)个数据元素的有限序列 2)线性表是一种最常用且最简单的数据结构 含有n个数据元素的线性表是一个数据结构: List=(D,R) 其中:D={a;|a∈Do=1,2…n,no} R={N}N={a1,a1|an1,a1∈Do,i=23…r Do为某个数据对象一一数据的子集 ◆特性:均匀性,有序性(线性序列关系
2.1 线性表的类型定义 1. 线性表 1）线性表是n(n ≥0)个数据元素的有限序列。 2）线性表是一种最常用且最简单的数据结构。 含有n个数据元素的线性表是一个数据结构： List = (D,R) 其中：D = {ai | ai∈D0 ,i=1,2,…n,n≥0} R = {N}, N = {< ai-1 , ai > | ai-1 , ai ∈D0 , i = 2,3,…n} D0 为某个数据对象——数据的子集 ◆ 特性：均匀性，有序性（线性序列关系）
2.1线性表的类型定义 1.线性表 3)线性表的长度及空表 ◆线性表中数据元素的个数n(n2O)定义为线性表的长度 ◆当线性表的长度为O时,称为空表 ◆a1是第个数据元素,称i为a在线性表中的位序
2.1 线性表的类型定义 1. 线性表 3）线性表的长度及空表 ◆ 线性表中数据元素的个数n（n≥0）定义为线性表的长度 ◆ 当线性表的长度为0 时，称为空表。 ◆ ai 是第i个数据元素，称i为ai 在线性表中的位序
2.线性表的基本操作p19~p20 1) InitList(ω&L)初始化,构造一个空的线性表 2) ListLength(L)求长度返回线性表中数据元 素个数 3) GetElem(Li&e)取表L中第i个数据元素赋值 给e 4) LocateElem(L,e)按值查找,若表中存在 个或多个值为e的结点,返回第一个找到的数 据元素的位序,否则返回一个特殊值。 5) ListInser(&Li,e)在L中第i个位置前插入新 的数据元素e,表长加1。 6) ListDelete(&L,i,e)删除表中第i个数据元素, e返回其值,表长减1
2. 线性表的基本操作 p19~p20 1）InitList(&L) 初始化，构造一个空的线性表 2）ListLength(L) 求长度,返回线性表中数据元 素个数 3）GetElem(L,i,&e) 取表L中第i个数据元素赋值 给e 4）LocateElem(L,e) 按值查找，若表中存在一 个或多个值为e的结点，返回第一个找到的数 据元素的位序，否则返回一个特殊值。 5）ListInsert(&L,i,e) 在L中第i个位置前插入新 的数据元素e，表长加1。 6）ListDelete(&L,i,e) 删除表中第i个数据元素， e返回其值，表长减1