当前位置：文档之家 › 2.1 线性表的类型定义1.线性表的定义 是由n(n=0)个数据元素a1.

2.1 线性表的类型定义1.线性表的定义 是由n(n=0)个数据元素a1.

  • 格式：ppt
  • 大小：482.50 KB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

线性表的类型定义、顺序表示和实现

线性表的类型定义、顺序表示和实现
– ①ai-1 和 ai逻辑关系发生变化 – ②需移动元素：
i=n 只删 an即可 1≤i≤n -1 将ai+1 ~an前移
23
bool deleteElem(SqList& L,int pos)
typedef int ElemType;
typedef char ElemType;
等；
②同一线性表中的数据元素必须具有相同的特性，属同一类 型；
③a2,关…系, ra是i-1,一a个i, a有i+1序, …偶,对an的）集，合a，i-1即领对先于于非ai，空表的示线了性数表据（元a1,素 之间的相邻关系，称ai-1是ai的直接前驱，ai是ai-1的直接后继 ；
6
2.1.3 操作举例
例：假设利用两个线性表La和Lb分别表示两 个集合A和B，求一个新的集合A=A∪B。
算法：
– ①取得Lb中的1个元素； – ②在La中查找这个元素； – ③若不存在：插入La中；若存在，取Lb中下一个
元素，重复 ①、②、③，直到取完Lb的每个元素 。
7
void unionList(SqList &la,SqList lb)
10
线性表的顺序存储结构示意图
存储地址
loc(a1) loc(a1)＋ k
内存空间状态 逻辑地址
a1
1
a2
2
…
…
…
loc(a1)＋ (i－ 1)k
ai
i
…
…
…
loc(a1)＋ (n－ 1)k
an
n 空闲
顺序存储结构可以借助于高级程序设计语言中的一维数组来表示。
11
用C++语言描述的顺序表类型如下所示： sqlist.h

第二章线性表1线性表定义及顺序存储

第二章线性表1线性表定义及顺序存储

线性表是由n(n≥0)个数据元素 1，a2，... ... , an 组 个数据元素a ， ， 线性表是由 个数据元素 成的一个有限序列。表中的每一个数据元素， 成的一个有限序列。表中的每一个数据元素，除 了第一个外，有且仅有一个前驱； 了第一个外，有且仅有一个前驱；除了最后一个 有且仅有一个后继。即线性表或是一个空表， 外，有且仅有一个后继。即线性表或是一个空表， 或可以表示成(a 其中， 或可以表示成 1,a2,…,ai, ...,an )其中，ai(i=1,2,…,n) 其中 是属于数据对象的元素， 是属于数据对象的元素，通常也称为线性表中的 一个结点。 一个结点。
2. 线性表的其他表示方式
二元组表示 L= < D,S >，其中 ，其中D={ a1,a2, a3, ... an} S={< a1,a2>, < a2,a3 >, < a 3,a4 > … < an-1, an> } 图示表示
a1 a2 ai - 1 ai ai+1 an
顶点： 顶点：表示数据 边：表示是数据间的顺序结构关系
个的存储单元， 功能： 功能：在系统动态存储区中分配size个的存储单元， 并返回该空间的基址。若动态存储区空间已 并返回该空间的基址。 用完，则返回NULL，表示分配失败。 用完， 表示分配失败。
如: int m = 10；
ElemType
int *p; p = (int *) malloc(m*sizeof(int));
L.elem
0 1
3.顺序表的基本操作 3.顺序表的基本操作
LIST_INIT_SIZELIST_INIT_SIZE-1
①初始化操作算法： 初始化操作算法： 算法 0 L.length Status InitList_Sq(SqList &L){ LIST_INIT_SIZE L.listsize //构造一个空的顺序表 构造一个空的顺序表L 构造一个空的顺序表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (! L.elem) exit(OVERFLOW); //存储分配失败 存储分配失败 L. length=0; //空表长度为 空表长度为0 空表长度为 L.listsize=LIST_INIT_SIZE; //初始存储容量 初始存储容量 return OK; }//InitList_Sq

线性表的类型定义

线性表的类型定义

例2-2 已知一个非纯集合B，试构造一个纯 集合A，使A中只包含B中所有值各不相同 的数据元素。
void purge(List &La, List Lb) {
// 已知线性表Lb中的数据元素依值非递减 有序排列(Lb是有序表)，
// 构造线性表La，使其只包含Lb中所有值 不相同的数据元素
InitList(LA); La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if(!equal (en, e)) { //en初始化为LB中没有的值 ListInsert(La, ++La_len, e); en = e; } // La中不存在和 e 相同的数据元素，则插入之 } } // purge
{引用型操作}
ListEmpty( L ) 初始条件：线性表L已存在。 操作结果：若L为空表，则返回TRUE，否
则FALSE。 ListLength( L ) 初始条件：线性表L已存在。 操作结果：返回L中元素个数。
PriorElem( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的元素，但不是第
上述问题可演绎为，要求对线性表作如下 操作：扩大线性表LA，将存在于线性表 LB中而不存在于线性表LA中的数据元素 插入到线性表LA中去。
思路：
1．从线性表LB中依次取得每个数据元素; GetElem(LB, i)→e
2．依次在线性表LA中进行查访; LocateElem(LA, e, equal( ))

2.1 线性表的类型定义

2.1 线性表的类型定义

线性表是一种最简单的线性结构。

线性结构的特点为：在数据元素的非空有限集中，1．集合中存在唯一的一个“第一元素”；2．集合中存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。

2.1 线性表的类型定义抽象数据类型线性表的定义如下：ADT List {数据对象：D＝{ a i | a i∈ElemSet, i=1,2,...,n, n≥0 }{称n为线性表的表长；n=0时的线性表为空表。

}数据关系：R1＝{ <a i-1 ,a i >|a i-1 ,a i∈D, i=2,...,n }简言之，一个线性表是n个数据元素（a1，a2,…，a i，… ，a n）的有限序列。

称 i 为 a i在线性表中的位序。

基本操作：结构初始化操作结构销毁操作引用型操作加工型操作} ADT ListInitList( &L )操作结果：构造一个空的线性表L。

初始化操作结构销毁操作DestroyList( &L )初始条件：操作结果：线性表 L 已存在。

销毁线性表 L。

引用型操作:ListEmpty( L )ListLength( L )PriorElem( L, cur_e, &pre_e )NextElem( L, cur_e, &next_e ) GetElem( L, i, &e )LocateElem( L, e, compare( ) )ListTraverse(L, visit( ))ListEmpty( L ) （线性表判空）初始条件：操作结果：线性表L已存在。

若L为空表，则返回TRUE，否则FALSE。

ListLength( L )（求线性表的长度）初始条件：操作结果：线性表L已存在。

返回L中元素个数。

PriorElem( L, cur_e, &pre_e ) （求数据元素的前驱）初始条件：操作结果：线性表L已存在。

数据结构线性表总结(2023最新版)

数据结构线性表总结(2023最新版)

数据结构线性表总结线性表是一种常见的数据结构，它是由一系列元素组成的序列，其中元素的顺序是固定的。

线性表可以通过一维数组或链表来实现，在实际应用中起到了重要的作用。

本文将对线性表进行总结，包括线性表的定义、基本操作、常见实现方式以及一些应用场景。

一、线性表的定义线性表是由n（n>=0）个数据元素a[1]，a[2]，，a[n]组成的有限序列。

其中，元素a[i]所在的位置称为索引i，索引从1开始递增，最大到n。

线性表可以为空表，即n为0的情况。

二、线性表的基本操作⒈初始化操作：创建一个空的线性表，为后续的操作做准备。

⒉插入操作：在线性表的某个位置插入一个元素，需要考虑插入位置的合法性和元素的移动。

⒊删除操作：删除线性表中指定位置的元素，同样需要考虑合法性和元素的移动。

⒋查找操作：根据指定位置或者指定元素值查找线性表中的元素，查找到后可以返回位置或者元素的值。

⒌修改操作：根据指定位置或者指定元素值修改线性表中的元素。

⒍遍历操作：按照顺序访问线性表中的每个元素。

三、线性表的实现方式常见的线性表实现方式有两种：一维数组和链表。

⒈一维数组实现：一维数组是最简单的实现方式，每个元素的存储位置是连续的，可以直接通过下标进行访问。

但是数组的长度固定，删除和插入操作需要进行元素的移动，效率较低。

⒉链表实现：链表是通过节点之间的引用关系形成的动态数据结构。

除了数据部分，每个节点还包含指向下一个节点的引用。

链表的长度可以动态调整，插入和删除操作只需要改变节点的引用，效率较高。

常见的链表类型有单链表、双向链表和循环链表。

四、线性表的应用场景线性表在实际应用中有着广泛的应用场景，包括但不限于以下几种：⒈线性表作为数据结构的基础，被广泛应用在各种编程语言中，用于存储和操作数据。

⒉链表可以用于实现其他数据结构，如栈和队列。

⒊线性表可以用来存储字符串或者文本文档的内容，方便进行增删改查等操作。

⒋在图论中，线性表可以用来存储路径信息，便于实现图的遍历算法。

《数据结构C语言版》----第02章

《数据结构C语言版》----第02章

同理可证:顺序表删除一元素的时间效率为: 同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 ≈O(n) O(n) （
插入效 E = ∑ is 率： i=0
n
1 n n pi ( n − i ) = ∑ (n − i) = 2 n + 1 i=0
n −1 删除效 1 n −1 n −1 Edl = ∑ qi (n − i ) = ∑ (n − i ) = 率： n i =0 2 i =0
2.2 线性表的顺序表示和实现
顺序存储结构的线性表称作顺序表 1.顺序表的存储结构 顺序表的存储结构
实现顺序存储结构的方法是使用数组。数组把线性表 实现顺序存储结构的方法是使用数组。 使用数组 的数据元素存储在一块连续地址空间的内存单元中， 连续地址空间的内存单元中 的数据元素存储在一块连续地址空间的内存单元中，这样 线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。 线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。 数据元素间的逻辑上的前驱、 数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据 元素的存储单元的物理前后位置上。 元素的存储单元的物理前后位置上。 顺序表的存储结构如图所示
2.线性表抽象数据类型 2.线性表抽象数据类型
数据集合:｛ 的数据类型为DataType 数据集合 ｛ a0, a1, … , an-1 ｝, ai的数据类型为 (1) ListInitiate(L) 初始化线性表 (2) ListLength(L) 求当前数据元素个数 操作集合: 操作集合 (3) ListInsert(L,i,x) 插入数据元素 (4) ListDelete(L,i,x) 删除数据元素 (5) ListGet(L,i,x) 取数据元素
printf("参数 不合法 \n"); 参数i不合法 参数 不合法! return 0;

3线性表

3/48
线性表
线性结构特点: 线性结构特点 头 尾 线性 O O O O O 1 2 3 4 5
唯一头元素 唯一尾元素 除头元素外，均有一个直接前驱 除头元素外， 除尾元素外，均有一个直接后继 除尾元素外，
4/48
线性表的定义
1. 线性表的语言定义 线性表是n个数据元素的有限序列。 线性表是 个数据元素的有限序列。 个数据元素的有限序列
pa = La->next ； pb = Lb->next ；//分别指向第一个结点 分别指向第一个结点 Lc = pc = La ； while ( pa && pb ) { if ( pa->data <= pb->data ) { pc->next = pa ；pc = pa ；pa = pa->next ；} else { pc->next = pb ；pc = pb ；pb = pb->next ；} } pc->next = pa ? pa : pb ；//处理剩余部分 处理剩余部分 free (Lb) ； }
11/48
假设p 假设 i是在第 i 个元素之前插入一个新元素的概率 则长度为 n 的线性表中插入一个元素所需移动元 期望值为 素次数的期望值 素次数的期望值为: Eis = ∑ pi (n – i + 1)
i=1 n+1
1 设在任何位置插入元素等概率 等概率， 设在任何位置插入元素等概率， pi = n+1 1 Eis = ∑ (n – i + 1) = n n+1 i=1 2
15/48
假设q 假设 i是删除第 i 个元素的概率 则长度为 n 的线性表中删除一个元素所需移动元 素次数的期望值为 素次数的期望值为: Edl = ∑ qi (n – i) 期望值

线性表


n 1
n1 2 2
顺序表中插入操作的平均时间复杂度为O(n)
5. 删除
算法过程
序号 内容
0
1
a1
2
a2
3
a3
…
…
i-1
ai1
i
ai
i+1 ai1
…
…
n
an
n+1
maxsize -1
序号 内容
0
1
a1
2
a2
3
a3
…
…
i-1
ai1
i
ai1
i+1
ai 2
…
…
n-1
an
n
maxsize -1
删除前
删除后
把线性表(a1, a2, a3,......, an )顺序存放在内存中
地址 内存
b
a1
b+L
a2
b+2L
a3
…
…
…
…
b+(i-1)×L ai
… … b+(n -1)×L an
序号 0 1 2 3 … …
i
… … n
maxsize-1 顺序存储结构示意图
第二章 线性表
假设线性表的每个元素需占用L个存储单元，并以所占的 第一个单元的存储地址作为数据元素的存储位置(上图中 为b)。则线性表中第i+1个数据元素的存储位置LOC(ai+1) 和第i个数据元素的存储位置LOC(ai)之间满足下列关系：
第二章 线性表
例2-3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康

线性表


线性表的ADT定义为：
ADT List {
数据对象：D={ ai | ai∈ElemSet, i=1,2,…,n, n≥0}
数据关系：R={< ai-1, ai >| ai-1, ai ∈ElemSet,i=1,2,…,n} 基本操作： InitList( & L) //建立（初始化）线性表
DestroyList( &L ) //销毁线形表L
张三
李四 王五 赵六 ……..
男
女 男 男 …….
18
20 21 17 …….
端州
四会 广州 端州 …….
线性表的逻辑特征是：
①在非空的线性表，有且仅有一个开始元 素a1，它没有直接前趋，而仅有一个直接后继a2 ②有且仅有一个终端元素an，它没有直接后 继，而仅有一个直接前趋an-1； ③其余的内部元素ai(2<=i<=n-1)都有且仅有 一个直接前趋 ai-1 和一个直接后继 ai+1。
算法2.1
例2. 巳知线性表LA和线性表LB中的数据元
素按值非递减有序排列，现要求将LA和LB归并 为一个新的线性表LC，且LC中的元素仍按值非 递减有序排列。 如： LA={ 3，5，8，11 }， LB={2，6，8，9，11，15 ，20}， 则结果 LC={2，3，5，6，8，8，9，11，11，15，20}
#define List_Increment 30 //追加分配长度
在顺序表存储结构中，很容易实现线性表的操作，
如：线性表的构造、第i个元素的访问、求表长等操作。
要访问某个元素也很方便，这是顺序存储的最大优
点——随机访问 注意：在C语言中的数组下标从“0”开始，因此，若L 是Sqlist类型的顺序表，则表中第i个元素是L.data[i-1]。

线性表


void disp(sqlist L) //增加的测试函数，显示线性表中的元素 { int i; printf("线性表中的元素为："); for (i=0; i<L.length; i++) printf("%5d",L.data[i]); printf("\n"); } int locate(sqlist L,int e) //在L中查找值为e的元素，如果存在返回1，否则返回0 { int i; for (i=0; i<L.length; i++) if (L.data[i]==e) return 1; return 0; }
算法描述（P24算法2.4）
算法分析：
① 问题的规模：表的长度L-＞length（设值为n） ② 移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句 上，该语句的执行次数是n-i+1。 当i=n+1：移动结点次数为0，即算法在最好时间 复杂度是0(1)。 当i=1：移动结点次数为n，即算法 在最坏情况下时间复杂度是0(n)
③ 移动结点的平均次数为n/2 ，即在顺序表上进 行插入运算，平均要移动一半结点。
结论：顺序表上做插入运算，平均要移动表中约一 半的结点，平均时间复杂度也是O(n)。
顺序表完整操作举例1：
#include <stdio.h> #define MAXSIZE 100 typedef int elemtype; typedef struct /* 定义结点元素结构 */ { elemtype elem[MAXSIZE]; int len; }SEQLIST; void SQ_init(SEQLIST *L) { (*L).len=0; } int SQ_length( SEQLIST L ) { return L.len; } /* 顺序表初始化 */ /* 求顺序表的长度 */
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

18
20 21
健康
一般 健康
张立立
……..
790634
……..
男
…….
17
…….
神经衰弱
…….
3
• 注意：
（1）线性表中的所有数据元素的数据类型是一致的。 （2）数据元素在线性表中的位置只取决于它的序号。 （3）相邻数据元素之间存在着序偶关系。 （4）结点间的逻辑关系是线性的。
4
3.抽象数据类型线性表的定义如下：
11
（2）插入运算 在第i（1<=i<=n+1)个元素之前插入一个新的数据元素x。 使长度为n的线性表变为长度为n+1的线性表：
（a1,a2,…,ai-1,ai,…,an）
（a1,a2,…,ai-1,x, ai,…,an）
12
•
插入算法的思想：
1. 将线性表中的第i个至第n个数据元素后移一个位置（共需 移动n-i+1个数据元素),
1
2.线性表（a1,a2,a3, ……an）的特点：
在数据元素的非空有限集中， （1）存在唯一的一个被称为“第一个”的数据元素； （2）存在唯一的一个被称为“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个 前驱； （4）除最后一个外，集合中的每个数据元素均只有一个 后继。 线性表中的数据元素类型多种多样，但同一线性表 中的元素必定具有相同特性，在一些复杂的线性表中， 每一个数据元素又可以由若干个数据项组成，在这种情 况下，通常将数据元素称为记录（record）。
10
4.顺序表的几种基本运算
（1）初始化运算 Status InitList_Sq(Sqlist &L){ L.elem=(Elemtype *)malloc (LIST_INIT_SIZE*sizeof(Elemtype)); //分配内存单元 if (! L.elem) exit (OVERFLOW); //存储分配失败 L.Length=0; //空表长度为0 L.Listsize=LIST_INIT_SIZE; //初始存储容量 return OK; }//InitList_Sq
a1 a2
…
ai-1 ai …
பைடு நூலகம்
an
线性表的起始地址， 称作线性表的基地址
7
2.顺序表中数据元素的存储地址
若一个数据元素仅占一个存储单元，则其存储方式参见 下图。
从图中可见，第i个数据元素的地址为： LOC（ai）=LOC(a 1)+(i-1)
8
若每个数据元素占用l个存储单元，并以所占用的第一个单 元的存储地址作为数据元素的存储地址，则第i个数据元素的存 储位置为： LOC(ai) = LOC( a i-1 )+l
参数t的不同情况，前者的t是指针变量，通过指针=地址 和实参建立联系，从而t的改变将影响实参值同时改变； 后者的t与实参是值传递，所以t的改变将不影响实参值。
6
2.2 线性表的顺序表示和实现（顺序表）
1. 线性表的顺序表示： 是指用一组地址连续的存储单元依次存放线性表 的数据元素，称这种存储结构的线性表为顺序表。 特点：在顺序表中逻辑结构上相邻的数据元素， 其物理位置也是相邻的。
第二章 线性表（Linear_List)
2.1 线性表的类型定义
1.线性表的定义：
是由n(n>=0)个数据元素a1,a2,a3, ……an组成的有限序列。 其中：n为数据元素的个数，也称为表的长度。 当n=0 时，称为空表。 非空的线性表(n>0) 记作： （ a1,a2,a3, ……an） 表中ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。
2
例1：26个英文字母组成的字母表
（A，B，C、…、Z）
例2：某校从1978年到1983年各种型号的计 算机拥有量的变化情况。 （6，17，28，50，92，188） 例3：学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林
陈 红 刘建平
790631
790632 790633
男
女 男
ADT List { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
数据关系： R＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n } 基本操作： P19 } ADT List
5
注意： &L和L的区别
可类比merge(int *t, int n)和merge1(int t, int n)中
2. 将数据元素x插入到数据元素ai-1之后，将x存入elem[i]中，
3. 将线性表长度加1。
13
•
插入算法描述: status ListInsert-Sq(SqList &L, int i, ElemType e) { //在顺序线性表L中第i个位置之前插入新的元素e if (i<1 || i>L.length+1) return ERROR; //i值不合法 if (L.length>=L.listsize){ //当前存储空间已满，则增 加分配 newbase=(Elemtype* )realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(Elemtype)) if (!newbase) exit (OVERFLOW); //存储分配失败 L.elem=newbase; } //新基址 L.Listsize + =Listincrement; //增加存储容量
LOC（ai）=LOC(a1)+(i-1)* l LOC(a1)称为基地址（第一个数据元素的存储位置）。
显然，数据元素在顺序表中位置取决于数据元素在线性表中的 位置。
9
3.顺序表的描述：
可用C语言的一维数组实现： #define LIST_INIT_SIZE 100 //线性表存储空 间的初始分配量 #define LISTINCREMENT 10 //线性表存储空 间的分配增量 注意： typedef struct{ C语言中数组 ElemType *elem; //存储空间基址，数组 的下标是从0 开始的，因此， 指针elem指示线性表的基地址 若L是SqList int length; //线性表的当前长度 类型的顺序表， int listsize; //当前分配的存储容量，以 则表中第i个 一个数据元素存储长度为单位 数据元素是 }SqList; L.elem[i-1]。