线性表的类型定义

线性表的类型定义2013-05-24线性表简介

线性结构是一个数据元素的有序（次序）集合。

线性结构的基本特征为：

1. 集合中必存在唯一的一个“第一元素”；

2．集合中必存在唯一的一个 “最后元素” ；

3．除最后元素在外，均有唯一的后继；

4．除第一元素之外，均有唯一的前驱

线性表的类型定义

ADT（抽象数据类型）是描述逻辑结构的，它的的实现用物理存储来实现，有两种：顺序存储结构和链式存储结构。

抽象数据类型线性表的定义如下：

ADT List{数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n,n≥0 }{称 n 为线性表的表长（也是元素个数）; 称 n=0 时的线性表为空表。}数据关系：R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D,i=2,...,n } i是位序基本操作：初始化->InitList（&L）{构造空的线性表L}销毁->Destroy（&L）{销毁}是否为空表->ListEmpty（L）{若L为空 返回TRUE}求表长->ListLength（L）{返回L中的元素个数，即表长}取前驱->PriorElem（L,cur_e,&pre_e）{cur_e为一个元素且不是第一个，则用pre_e返回它的前驱}去后继->NextElem（L,cur_e,&next_e）取元素->GetElem（L,i,&e）{用e返回L中第i个元素的值}定位->LocateElem（L,e,compare（））{返回L中第一个与e满足compare（）的元素位序，否则返回0} 遍历->ListTraverse（L,visit（））{依次对L的每个元素调用visit（）函数}置空->ClearList（&L）{置空}改变元素->PutElem（&L，i,e）{把e覆盖第i个位置，是改变元素，不是插入}插入->ListInsert（&L,i,e）{插入的位置是i的前面}删除->ListDelete（&L,i,&）}ADT List

例1：集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B

分析：扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入

到线性表 LA 中去。

void union（List &LA, List LB） {LA_len = ListLength（LA）;// 求线性表的长度  LB_len = ListLength（LB）;   for （i = 1;i <= LB_len;i++） {  GetElem（LB, i, e）; // 取LB中第i个数据元素赋给e   if （！LocateElem（LA, e, equal（ ）） ）//e 与LA元素比较，如果没有，则插入   ListInsert（LA, ++LA_len, e）;// LA中不存在和 e 相同的数据元素，则插入之   }}O（ListLength（La）×ListLength（Lb） ）

例2：线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据仍按值非递减有序排列。

分析： LC先设为空表，然后将LA或LB中的元素逐个插入到LC中。可设两个整型变量i、j，分别指向LA和LB，比较i、j所指元素的大小，决定哪个元素插入LC。插入后，在LA 或LB 中顺序后移

void MergeList（List LA, List LB, List &LC） { InitList（LC）;// 构造空的线性表 LC i = j = 1;k = 0;LA_len = ListLength（LA）; LB_len = ListLength（LB）; while （（i <= LA_len） && （j <= LC_len））{ //LA和LB都不为空GetElem（LA,i,ai）; GetElem（LB,j,bj）;if（ai<bj）{ListInsert（LC, ++k ,ai）;++i } else{ListInsert（LC, ++k, bj） ;++j; } } while （i<=LA_len） { // 若 La 不空GetElem（LA,i++,ai）; ListInsert（LC, ++k ,ai）;} //插入LA表中剩余元素 while （j<=LB_len）{// 若 Lb 不空GetElem（LB,j++,bj）; ListInsert（LC, ++k ,bj）;}//插入LB表中剩余元素} // merge_listO（ ListLength 2（La）+ListLength 2（Lb） ）

本文出自 “赵玉强的博客” 博客，请务必保留此出处http://zhaoyuqiang.blog.51cto.com/6328846/1160126