范文一：线性表的抽象数据类型 抽象数据类型线性表的定义

导读:就爱阅读网友为您分享以下“抽象数据类型线性表的定义”资讯，希望对您有所帮助，感谢您对92to.com的支持!

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

ADT List {

数据对象:D={ ai | ai ? ElemSet, i =1, 2, … …, n, n?0 }

数据关系:R1 = { ai-1 , a i | ai-1 , a i ? D , i =2, … …, n } 基本操作: InitList (&L ) 操作结果:构造一个空的线性表L 。 DestoryList (&L) 初始条件:线性表L 已存在。 操作结果:销毁线性表L 。

ClearList (&L)

初始条件:线性表L 已存在。 操作结果:将L 重置为空

1

表。

ListEmpty (L)

初始条件:线性表L 已存在。 操作结果:若L 为空表，则返回TRUE ，否则返回 FALSE 。

ListLength (L)

初始条件:线性表L 已存在。 操作结果:返回L 中数据元素个数。

GetElem ( L, i, &e )

初始条件:线性表L 已存在，1?i ?ListLength(L)+1。

操作结果:用e 返回L 中第i 个数据元素的值。

LocateElem ( L,e, compare() )

初始条件:线性表L 已存在，compare()是判定函数。

操作结果:返回L 中第1个与e 满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值0。

PriorElem ( L, cur_e, &pre_e )

初始条件:线性表L 已存在。

操作结果:若cur_e是L 的数据元素且不是第1个，则用pre_e返回它的前驱，否则操作失败。

NextElem ( L, cur_e, &next_e )

初始条件:线性表L 已存在。

2

操作结果:若cur_e是L 的数据元素且不是最后一个，则用next_e返回它的后继，否则操作失败。

ListInsert ( &L, i, e )

初始条件:线性表L 已存在，1?i ?ListLength(L)+1。

操作结果:在L 中第i 个位置之前插入新的数据元素e ，L 的长度加1。

ListDelete( &L, i, &e )

初始条件:线性表L 已存在且非空，1?i ?ListLength(L)。

操作结果:删除L 的第i 个数据元素，并用e 返回其值，

L 的长度减1。

ListTraverse ( L,visit())

初始条件:线性表L 已存在。

操作结果:依次对L 的每个数据元素调用函数 visit()。一旦visit()失败，则操作失败。

} ADT List

百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网92to.com,您的在线图书馆

3

范文二：抽象数据类型线性表的定义

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

ADT List {

数据对象:D={ ai | ai ∈ ElemSet, i =1, 2, … … , n, n≥ 0} 数据关系:R1 = { < ai-1="" ,="" a="" i=""> | ai-1 , a i ∈ D , i =2, … … , n } 基本操作:

InitList (&L )

操作结果:构造一个空的线性表 L 。

DestoryList (&L)

初始条件:线性表 L 已存在。

操作结果:销毁线性表 L 。

ClearList (&L)

初始条件:线性表 L 已存在。

操作结果:将 L 重置为空表。

ListEmpty (L)

初始条件:线性表 L 已存在。

操作结果:若 L 为空表,则返回 TRUE ,否则返回 FALSE 。

ListLength (L)

初始条件:线性表 L 已存在。

操作结果:返回 L 中数据元素个数。

GetElem ( L, i, &e )

初始条件:线性表 L 已存在, 1≤ i ≤ ListLength(L)+1。

操作结果:用 e 返回 L 中第 i 个数据元素的值。 LocateElem ( L,e, compare() )

初始条件:线性表 L 已存在, compare()是判定函数。 操作结果:返回 L 中第 1个与 e 满足关系 compare()的数据元素的位序。若这样的数据元素不存在,则返 回值 0。

PriorElem ( L, cur_e, &pre_e )

初始条件:线性表 L 已存在。

操作结果:若 cur_e是 L 的数据元素且不是第 1个, 则用 pre_e返回它的前驱,否则操作失败。

NextElem ( L, cur_e, &next_e )

初始条件:线性表 L 已存在。

操作结果:若 cur_e是 L 的数据元素且不是最后一个, 则用 next_e返回它的后继,否则操作失败。

ListInsert ( &L, i, e )

初始条件:线性表 L 已存在, 1≤ i ≤ ListLength(L)+1。 操作结果:在 L 中第 i 个位置之前插入新的数据元素 e , L 的长度加 1。

ListDelete( &L, i, &e )

初 始 条 件 :线 性 表 L 已 存 在 且 非 空 , 1≤ i ≤ ListLength(L)。

操作结果:删除 L 的第 i 个数据元素, 并用 e 返回其值,

L 的长度减 1。

ListTraverse ( L,visit())

初始条件:线性表 L 已存在。

操作结果:依次对 L 的每个数据元素调用函数 visit()。 一旦 visit()失败,则操作失败。

} ADT List

范文三：抽象数据类型三元组的定义[宝典]

抽象数据类型三元组的定义

ADT Triplet{

数据对象:D= {e1,e2,e3 | e1,e2,e3属于Elemset(定义了关系的某个集合)}

数据关系:R1={|}

基本操作:

—InitTriplet(&T,v1,v2,v3)— 初始条件:

— 操作结果:用e值取代三元组T的第i个元素

— DestroyTriplet(&T)

— 初始条件:三元组T已经存在。 — 操作结果:销毁三元组T。

—Get(T,i,&e)

— 初始条件:三元组T已经存在，1<><=3, —="" 操作结果:用e返回三元组t的第i个元素。="">

— Put(&T,i,e)

— 初始条件:三元组T已经存在，1<><=3,>

— 操作结果:用e值取代三元组T的第i个元素。

— IsAscending(T)

— 初始条件:三元组T已经存在。 — 操作结果:如果三元组T的三个元素按升序排列，则返回TRUE;否则返回FALSE

—IsDescending(T)

— 初始条件:三元组T已经存在。 — 操作结果:如果三元组T的三个元素按降序排列，则返回TRUE;否则返回FALSE

— Max(T,&e)

— 初始条件:三元组T已经存在。 — 操作结果:用e返回三元组T的最大值。

—Min(T,&e)

— 初始条件:三元组T已经存在。 — 操作结果:用e返回三元组T的最小值。 }ADT Triplet

抽象数据类型的表示与实现

类C语言(做了扩充和修改)的表示

如:预定义常量和类型

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIVLE -1

#define OVERFLOW -2

Typedef int Status

Status Get(Triple T,int i,Elemtype *e) // 初始条件:三元组T已经存在，1<><=3. 操作结果:用e返回三元组t的第i个元素="" {="">

If(i<1 ||="" i="">3) return ERROR;

*e = T[i-1];

Return OK;

}

算法和算法分析

算法(Algorithm):对特定问题求解步骤的一种描述。 算法的五个重要特性:

1有穷性 2确定性 3可行性 4输入 4输出

算法举例————气泡排序算法

初始条件:N个待排序的数a[0]—a[n-1]

结果:排序后a[0]—a[n-1]从小到大排列

1 置标记change=TRUE;

2 i从n-1知道i=2做(3)-- (6)步

3 change = FALSE;

4 j从0知道j=i-1做(5)

5 若a[j]>a[j+1]则交换他们并置change = TRUE

6 若change = FALSE 则结束

7 算法结束

i从n-1知道i=2 做 2—3 步1

2 j从0知道j=i-1做 3

3 若a[j]>a[j+1]则交换他们

4 算法结束

Void bb_sort(int a[],int n){

for(i=n-1;i > 1; --i){

for(j=0;j

if(a[j]>a[j+1]){a[j]??a[j+1];}

} // bb_sort

算法设计的要求

算法应达到的目标

1正确性 2可读性 3健壮性 4效率与低存储量

算法效率的度量

1事后统计法

2事前分析估算法

] 算法的 时间复杂度 ;基本操作重复执行次数。

它是问题规模n的某个函数f(n);

T(n)= O(f(n))

平均时间复杂度——时间复杂度与输入数据有关时采用平均时间复杂度或最最坏时间复杂度

// 气泡排序

时间复杂度只考虑对问题规模的增长率

在难以精确计算基本操作执行次数时，仅需要求增长率(或阶)即可。

阶:for(i=2;i<=n:++i)>

For(j=2;j<=i;++j){++x;a[i,j]=x;}>

++x的执行次数关于n的增长率时O(n平方)

最大的数量阶 n的n次方 n～

线性表

线性表结构的特点:

存在唯一的第一个数据元素

存在唯一的最后一个数据元素

除第一个外。每个数据元素均有且只有一个前驱元素;

除最后一个外。每个数据元素均有且只有一个后继元素。

线性表举例;

字母表 (A,B,C ,,, X Y Z)

数据序列 (6.17.28.50)

N个元素的线性表

(a1.a2,a3...an)

第一个元素没有前驱 最后一个元素没有后继 第i个元素有唯一前驱 唯一后继

ADT List{

数据对象:D={ai | ai属于Elemset, (i=1, 2 ,,, n n大于等于0)}

数据关系 R1= { | ai-1,ai属于D。(i= 2.3...n)}

基本操作:

—InitList(&L); DestroyList(&L)

—ListInsert(8L,i,e) ListDelete(&L,i,e);

—等等

线性表ADT的基本操作;

InitList(&L)

操作结果:构造一个空的线性表L

DestroyList(&L)

初始条件:线性表L已经存在

操作结果:销毁线性表L

ClearList(&L)

初始条件:线性表L已经存在

操作结果:将线性表L重置为空表。

ListEmpty(L) 逻辑值

初始条件:线性表L已经存在

操作结果:线性表L为空表。则返回TURE;否则返回FALSE

ListLength(L)

初始条件:线性表L已经存在

操作结果:返回线性表L中的数据元素个数

GetElem(L,i,&e);

初始条件:线性表已经存在

1<><=listlength(l)>

操作结果:用e返回线性表L中第i个数据元素的值

LocateElem(L,e,conpare())

初始条件:线性表L已经存在， conpare()时数据元素判定函数。 操作结果:返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0. (返回位序)

PriorElem(L,cur_e,&pre_e)

初始条件:线性表已经存在。

操作结果:若cur_e时L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败;pre_e无意义 // 若 cur_e 为第一元素 则返回一个复制，否则返回它本身

NextElem(L,cur_e,&next_e)

初始条件:线性表L已经存在，

操作结果:若cur_e是L的数据元素。且不是最后一个。则用next_e返回它的后继，否则操作失败。Next_e无意义

ListInsert(&L,i,e)

初始条件:线性表L已经存在，i<><=listlength(l)+1.>

插入前(长度为N)

(a1,a2 ------- an)

插入后(长度为N+1)

(a1... ai-1,e,ai...an)

ListDelete(&L,i,&e)

初始条件:线性表L已经存在，1<><=listlength(l). 操作结果:删除l的第i个数据元素，并用e返回其值。="" l的长度减一="">

删除前 (a1.a2....an)

删除后 (a1...ai-1.ai+1...an)

范文四：1-4.什么是抽象数据类型试用C 的类声明定义复数的

第1章 绪论

1-4(什么是抽象数据类型,试用C++的类声明定义“复数”的抽象数据类型。要求

(1) 在复数内部用浮点数定义它的实部和虚部。

(2) 实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0;第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。

(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

(4) 定义重载的流函数来输出一个复数。

【解答】

抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。

//在头文件complex.h中定义的复数类

#ifndef _complex_h_

#define _complex_h_

#include

class comlex {

public:

complex ( ){ Re = Im = 0; } //不带参数的构造函数

complex ( double r ) { Re = r; Im = 0; } //只置实部的构造函数

( double r, double i ) { Re = r; Im = i; } //分别置实部、虚部的构造函数 complex

double getReal ( ) { return Re; } //取复数实部

double getImag ( ) { return Im; } //取复数虚部

void setReal ( double r ) { Re = r; } //修改复数实部

void setImag ( double i ) { Im = i; } //修改复数虚部

complex& operator = ( complex& ob) { Re = ob.Re; Im = ob.Im; } //复数赋值

complex& operator + ( complex& ob ); //重载函数:复数四则运算

complex& operator – ( complex& ob );

complex& operator * ( complex& ob );

complex& operator / ( complex& ob );

friend ostream& operator < (="" ostream&="" os,="" complex&="" c="" );=""><>

private:

double Re, Im; //复数的实部与虚部

};

endif #

//复数类complex的相关服务的实现放在C++源文件complex.cpp中

#include

#include

#include “complex.h”

complex& complex :: operator + ( complex & ob ) {

//重载函数:复数加法运算。

complex * result = new complex ( Re + ob.Re, Im + ob.Im );

return *result;

1

第1章 绪论

}

complex& complex :: operator – ( complex& ob ) {

//重载函数:复数减法运算

complex * result = new complex ( Re – ob.Re, Im – ob.Im );

return * result;

}

complex& complex :: operator * ( complex& ob ) {

//重载函数:复数乘法运算

complex * result =

new complex ( Re * ob.Re – Im * ob.Im, Im * ob.Re + Re * ob.Im );

return *result;

}

complex& complex :: operator / ( complex& ) {

//重载函数:复数除法运算

double d = ob.Re * ob.Re + ob.Im * ob.Im;

complex * result = new complex ( ( Re * ob.Re + Im * ob.Im ) / d,

( Im * ob. Re – Re * ob.Im ) / d );

return * result;

}

friend ostream& operator < (="" ostream&="" os,="" complex="" &="" ob="" )="" {="">

友元函数:重载<，将复数ob输出到输出流对象os中。>

return os < ob.re="">< (="" ob.im="">= 0.0 ) ? “+” : “-” < fabs="" (="" ob.im="" )="">< “i”;="">

}

n1-7 试编写一个函数计算n!*2的值，结果存放于数组A[arraySize]的第n个数组元素中，0 ,

n , arraySize。若设计算机中允许的整数的最大值为maxInt，则当n > arraySize或者对于某

k一个k (0 , k , n)，使得k!*2 > maxInt时，应按出错处理。可有如下三种不同的出错处理方

式:

(1) 用cerr<及exit (1)语句来终止执行并报告错误;="">

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回;

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。

试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。 【解答】

#include "iostream.h"

#define arraySize 100

#define MaxInt 0x7fffffff

int calc ( int T[ ], int n ) {

int i, value = 1;

if ( n != 0 ) {

int edge = MaxInt / n / 2;

for ( i = 1; i < n;="" i++="" )="" {="">

value *= i*2;

if ( value > edge ) return 0;

2

第1章 绪论

}

value *= n * 2;

}

T[n] = value;

cout < "a["="">< n="">< "]=" << T[n] << endl;

return 1;

}

void main ( ) {

int A[arraySize];

int i;

for ( i = 0; i < arraySize; i++ )

if ( !calc ( A, i ) ) {

cout << " failed="" at="" "="">< i="">< "="" ."="">< endl;="">

break;

}

}

1-9 (1) 在下面所给函数的适当地方插入计算count的语句:

void d (ArrayElement x[ ], int n ) {

int i = 1;

do {

x[i] += 2; i +=2;

} while (i <= n="" );="">

; i = 1;

while ( i <= (n/2)="" )="" {="">

x[i] += x[i+1]; i++;

}

}

(2) 将由(1)所得到的程序化简。使得化简后的程序与化简前的程序具有相同的count值。

(3) 程序执行结束时的count值是多少,

(4) 使用执行频度的方法计算这个程序的程序步数，画出程序步数统计表。

【解答】

(1) 在适当的地方插入计算count语句

void d ( ArrayElement x [ ], int n ) {

int i = 1;

count ++;

do {

x[i] += 2; count ++;

i += 2; count ++;

count ++; //针对while语句

} while ( i <= n="" );="">

i = 1;

count ++;

3

第1章 绪论

while ( i <= (="" n="" 2="" )="" )="" {="">

count ++; //针对while语句

x[i] += x[i+1];

count ++;

i ++;

count ++;

}

count ++; //针对最后一次while语句

}

(2) 将由(1)所得到的程序化简。化简后的程序与原来的程序有相同的count值:

void d ( ArrayElement x [ ], int n ) {

int i = 1;

do {

count += 3; i += 2;

} while ( i <= n="" );="">

i = 1;

while ( i <= (="" n="" 2="" )="" )="" {="">

count += 3; i ++;

}

count += 3;

}

(3) 程序执行结束后的count值为 3n + 3。

当n为偶数时，count = 3 * ( n / 2 ) + 3 * ( n / 2 ) + 3 = 3 * n + 3

当n为奇数时，count = 3 * ( ( n + 1 ) / 2 ) + 3 * ( ( n – 1 ) / 2 ) + 3 = 3 * n + 3

(4) 使用执行频度的方法计算程序的执行步数，画出程序步数统计表:

行 号 程 序 语 句 一次执行步数 执行频度 程序步数

1 void d ( ArrayElement x [ ], int n ) { 0 1 0

2 int i = 1; 1 1 1

3 do { 0 ，(n+1)/2， 0

4 x[i] += 2; 1 ，(n+1)/2， ，(n+1)/2，

5 i += 2; 1 ，(n+1)/2， ，(n+1)/2，

6 } while ( i <= n="" );="" 1="" ，(n+1)/2，="" ，(n+1)/2，="">

7 i = 1; 1 1 1

8 while ( i <= (="" n="" 2="" )="" )="" {="" 1="" ，n/2+1，="" ，n/2+1，="">

9 x[i] += x[i+1]; 1 ，n/2， ，n/2，

10 i ++; 1 ，n/2， ，n/2，

11 } 0 ，n/2， 0

12 } 0 1 0

( n , 0 ) 3n + 3

4

范文五：数据结构-线性表的抽象数据类型定义与类C实现

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

ADT List{

数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}

数据关系: R1={| ai-1,ai(- D,i=2,...,n}

基本操作：

InitList(&L)

操作结果：构造一个空的线性表L。

DestroyList(&L)

初始条件：线性表已经存在。

操作结果：销毁线性表L。

ClearList(&L)

初始条件：线性表已经存在。

操作结果：将L重置为空表。

ListEmpty(L)

初始条件：线性表已经存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。 ListLength(L)

初始条件：线性表已经存在。

操作结果：返回L中数据元素的个数。 GetElem(L,i,&e)

初始条件：线性表已经存在，1<><=listlength(l).>

操作结果：用e返回第i个数据元素的值。 LocateElem(L,e,compare())

初始条件：线性表已经存在，compare()是数据元素的判定函数。

操作结果：返回L中第1个与e满足关系compare()的数据元素的位序，若这样的数据元素不存在则返回

值为0。

PriorElem(L,cur_e,&pre_e)

初始条件：线性表已经存在。

操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则

操作失败，pre_e 无定义

NextElem(L,cur_e,&next_e)

初始条件：线性表已经存在。

操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，

否则操作失败，

next_e无定义

ListInsert(&L,i,e)

初始条件：线性表已经存在，１<><=listlength(l)+1.>

操作结果：在Ｌ中第i个元素位置之前插入新的数据元素e，Ｌ的长度加１。

ListDelete(&L,i,&e)

初始条件：线性表已经存在且非空，1<><=listlength(l).>

操作结果：删除Ｌ的第i个数据元素，并用e返回其值，Ｌ的长度减１。

ListTraverse(L,visit())

初始条件：线性表已经存在。

操作结果：依次对Ｌ的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADT List

2、部分操作的类C实现：

InitList(&L)

{

L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=LIST_INIT_SIZE;

return OK;

}//InitList

GetElem(L,i,&e)

{ *e=L.lem[i]

}//GetElem

ListInsert(List &L,int i,ElemType e)

{ if(i<1||i>L.length+1) return ERROR;

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e;

++L.length;

return OK;

}//ListInsert

void union(List &La,List &Lb)

//利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A?B。

La_len=ListLength(La);Lb_len=ListLength(Lb); for(i=1;i<=lb_len;i++){>

GetElem(Lb,i,e);

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);

}//union

void MergeList(List La,List Lb,List &Lc)

//巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为

一个新的线性表LC，且LC中的元素仍按值非递减有序排列。

{ InitList(Lc);

i=j=1;k=0;

La_len=ListLength(La);Lb_len=ListLength(Lb); while((i<>

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){ listinsert(lc,++k,ai);++i;="" }="">

else{ListInsert(Lc,++k,bj);++j;}

}

while(k<>

GetElem(La,i++,ai);ListInsert(Lc,++k,ai); }

while(j<=lb_len){>

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj); }

}//MergeList

转载请注明出处范文大全网 » 线性表的抽象数据类型抽象数据