整数抽象数据类型型线性表

来源：蜘蛛抓取(WebSpider) 时间：2018-03-22 15:18 标签： 抽象数据类型有哪些
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)下次自动登录
现在的位置:
& 综合 & 正文
抽象数据类型线性表的定义
抽象数据类型线性表的定义
　通常可以下列" n 个数据元素的序列"表示线性表 (Linear_List)　　序列中数据元素的个数 n 定义为线性表的表长；n=0 时的线性表被称为空表。称 i 为
在线性表中的位序。　 其抽象数据类型的定义如下：ADT List {　数据对象：D＝{
∈ ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ &ai-1 ,ai &|
,∈D, i=2,...,n }
基本操作：　　{结构初始化}　　InitList( &L )　　　操作结果：构造一个空的线性表 L 。
{销毁结构}　　DestroyList( &L )　　　初始条件：线性表 L 已存在。　　　操作结果：销毁线性表 L 。例如，26个小写英文字母是一个线性表　　　　　(a,b,…,z)同一花色的13张扑克牌　　(2,3,4,5,6,7,8,9,10,J,Q,K,A)可以构成一个线性表。序偶 &,& 表示
的直接前驱，反之，
的直接后继。 {引用型操作}　　ListEmpty( L )　　　初始条件：线性表L已存在。　　　操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。
ListLength( L )　　　初始条件：线性表 L 已存在。　　　操作结果：返回 L 中元素个数。PriorElem( L, cur_e, &pre_e )　　　初始条件：线性表 L 已存在。　　　操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，　　　　　　　　否则操作失败，pre_e 无定义。NextElem( L, cur_e, &next_e )　　　初始条件：线性表 L 已存在。　　　操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，　　　　　　　　否则操作失败，next_e 无定义。
GetElem( L, i, &e )　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)。　　　操作结果：用 e 返回 L 中第 i 个元素的值。LocateElem( L, e, compare( ) )　　　初始条件：线性表 L 已存在，compare( ) 是元素判定函数。　　　操作结果：返回 L 中第1个与 e 满足关系 compare( ) 的元素的位序。　　　　　　　　若这样的元素不存在，则返回值为0。
　ListTraverse(L, visit( ))　　初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。　　操作结果：依次对 L 的每个元素调用函数 visit( )。　　　　　　　一旦 visit( ) 失败，则操作失败。{加工型操作}
ClearList( &L )　　　初始条件：线性表 L 已存在。　　　操作结果：将 L 重置为空表。
　PutElem( &L, i, &e )　　　初始条件：线性表L已存在，1≤i≤LengthList(L)。　　　操作结果：L 中第 i 个元素赋值同 e 的值。　ListInsert( &L, i, e )　　　初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。　　　操作结果：在 L 的第 i 个元素之前插入新的元素 e，L 的长度增1。
　ListDelete( &L, i, &e )　　　初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。　　　操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。
} ADT List
【上篇】【下篇】网站已改版，请使用新地址访问：
ContList 数据结构中常见抽象 类型--线性表的自定义实现 Data structs
238万源代码下载- www.pudn.com
&文件名称: ContList
& & & & &&]
&&所属分类:
&&开发工具: Visual C++
&&文件大小: 2 KB
&&上传时间:
&&下载次数: 4
&&提 供 者:
&详细说明：数据结构中常见抽象数据类型--线性表的自定义实现-The custom implementation of
common abstract data types--continuous list in data structure
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&CONTLIST\LIST.CPP&&........\LIST.H&&CONTLIST
&输入关键字，在本站238万海量源码库中尽情搜索：
&[] - 数据结构中常见抽象数据类型--队列的自定义实现
&[] - 数据结构中常见抽象数据类型--链式表的自定义实现线性表_百度百科
清除历史记录关闭
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
[xiàn xìng biǎo]
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表定义
线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱[1]
线性表特征
1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有 唯一的后继(后件)。
4．除第一个元素之外，均有 唯一的前驱(前件)。
线性表基本操作
1）MakeEmpty(L) 这是一个将L变为空表的方法
2）Length（L） 返回表L的长度，即表中元素个数
3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
4）Prior（L，i） 取i的前驱元素
5）Next（L，i） 取i的后继元素
6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
8）Delete（L，p） 从表L中删除位置p处的元素
9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
10）Clear（L）清除所有元素
11）Init（L）同第一个，初始化线性表为空
12）Traverse（L）遍历输出所有元素
13）Find（L，x）查找并返回元素
14）Update（L，x）修改元素
15）Sort（L）对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
线性表存储结构
线性表主要由顺序表示或链式表示。在实际应用中，常以、、等特殊形式使用。
顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链[1]
线性表结构特点
1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。
线性表线性表的推广
时间有序表、排序表、和频率有序表都可以看做是线性表的推广。如果按照结点到达结构的时间先后，作为确定结点之间关系的，这样一种线性结构称之为时间有序表。例如，在红灯前停下的一长串汽车，最先到达的为首结点，最后到达的为尾结点；在离开时最先到达的汽车将最先离开，最后到达的将最后离开。这些汽车构成理一个队列，实际上就是一个时间有序表。栈和队列都是时间有序表。频率有序表是按照结点的使用频率确定它们之间的相互关系的，而排序表是根据结点的关键字值来加以确定的。
严蔚敏，吴伟民．数据结构（c语言版）．北京：清华大学出版社，2011年：18-27
清除历史记录关闭

我要回帖

更多关于 抽象数据类型有哪些 的文章

 

随机推荐