精华内容
下载资源
问答
  • 抽象数据类型定义(ADT)

    万次阅读 多人点赞 2014-03-16 16:03:56
    一、抽象数据类型定义(ADT) 作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或图描述遗传关系。 定义:一个数学模型以及定义在该模型上的一组操作。 关键:使用它的人...

    一、抽象数据类型定义(ADT)

    作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或图描述遗传关系。

    定义:一个数学模型以及定义在该模型上的一组操作。

    关键:使用它的人可以只关心它的逻辑特征,不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

    例:线性表这样的抽象数据类型,其数学模型是:数据元素的集合,该集合内的元素有这样的关系:除第一个和最后一个外,每个元素有唯一的前趋和唯一的后继。可以有这样一些操作:插入一个元素、删除一个元素等。

    抽象数据类型分类
    原子类型 值不可分解,如int
    固定聚合类型 值由确定数目的成分按某种结构组成,如复数
    可变聚合类型 值的成分数目不确定如学生基本情况

    抽象数据类型表示法:

    一、

    三元组表示:(D,S,P)

    其中D是数据对象,S是D上的关系集,P是对D的基本操作集。

    二、书中的定义格式:

    ADT 抽象数据类型名{

    数据对象:<数据对象的定义>

    数据关系:<数据关系的定义>

    基本操作:<基本操作的定义>

    }ADT 抽象数据类型名

    例:线性表的表示

    名称 线性表  
    数据对象 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 任意数据元素的集合
    数据关系 R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 除第一个和最后一个外,每个元素有唯一的直接前趋和唯一的直接后继
    基本操作 ListInsert(&L,i,e) L为线性表,i为位置,e为数据元素。
    ListDelete(&L,i,e)
    ...

    二、类C语言语法

    类C语言语法示例
    1、预定义常量和类型 #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef in Status; //Status是函数的类型,其值是函数结果状态代码。
    2、数据结构的存储结构 typedef ElemType first;
    3、基本操作的算法

    函数类型 函数名(函数参数表){
    //算法说明
    语句序列
    }//函数名

    4、赋值语句 简单赋值: 变量名=表达式;
    串联赋值: 变量名1=变量名2=...=变量名k=表达式;
    成组赋值: (变量名1,...,变量名k)=(表达式1,...,表达式k);
    结构名=结构名;
    结构名=(值1,...,值k);
    变量名[]=表达式;
    变量名[起始下标..终止下标]=变量名[起始下标..终止下标]; 
    交换赋值: 变量名<-->变量名;
    条件赋值: 变量名=条件表达式?表达式?表达式T:表达式F
    5、选择语句

    1、if(表达式) 语句;
    2、if(表达式) 语句;
    else 语句;
    3、switch(表达式){
    case 值1:语句序列1;break;

    ...
    case 值n:语句序列n;break; 
    default:语句序列n+1;break; 
    }
    4、switch{
    case 条件1:语句序列1;break;

    ...
    case 条件n:语句序列n;break; 
    default:语句序列n+1;break; 
    }

    6、循环语句 for(赋初值表达式;条件;修改表达式序列)语句;
    while(条件)语句;
    do{ 语句序列}while(条件);
    7、结束语句

    return [表达式];
    return; //函数结束语句
    break; //case结束语句
    exit(异常代码); //异常结束语句

    8、输入和输出语句 scanf([格式串],变量1,...,变量n);
    9、注释 //文字序列
    10、基本函数 max(表达式1,...,表达式n)
    min,abs,floor,ceil,eof,eoln
    11、逻辑运算 &&与运算;||或运算

    例:线性表的实现:
    ADT List{

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

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

    基本操作:

    InitList(&L)
    DestroyList(&L)
    ListInsert(&L,i,e)
    ListDelete(&L,i,&e)

    }ADT List

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

    {if(i<1||i>L.length+) 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;

    }

    下面是C语言编译通过的示例

    #define ERROR 0 
    #define OK 1 
    struct STU
    { char name[20];
    char stuno[10]; 
    int age; int score; 
    }stu[50]; 
    struct LIST 
    { struct STU stu[50]; 
    int length; 
    }L; 

    int printlist(struct LIST L)
    { int i;
    printf("name stuno age score/n"); 
    for(i=0;i<L.length;i++) 
    printf("%s %s/t%d/t%d/n", L.stu[i].name, L.stu[i].stuno, L.stu[i].age, L.stu[i].score); 
    printf("/n"); 
    }

    int listinsert(struct LIST *L,int i,struct STU e) 
    { struct STU *p,*q; 
    if (i<1||i>L->length+1) 
    return ERROR; 
    q=&(L->stu[i-1]); 
    for(p=&L->stu[L->length-1];p>=q;--p) 
    *(p+1)=*p; *q=e; ++L->length; 
    return OK; 
    }/*ListInsert Before i */

    main() 
    { struct STU e; 
    L.length=0; 
    strcpy(e.name,"zmofun"); 
    strcpy(e.stuno,"100001"); 
    e.age=80; 
    e.score=1000; 
    listinsert(&L,1,e); 
    printlist(L); 
    printf("List length now is %d./n/n",L.length);

    strcpy(e.name,"bobjin"); 
    strcpy(e.stuno,"100002"); 
    e.age=80; 
    e.score=1000; 
    listinsert(&L,1,e); 
    printlist(L); 
    printf("List length now is %d./n/n",L.length); 
    }

    展开全文
  • 作业3-线性表抽象数据类型定义与顺序表操作 1-1 对于顺序存储的长度为N的线性表, 访问结点和增加结点的时间复杂度 分别对应为O(1)和O(N)。(T) [解析]增加结点,不同位置复杂度不同,但平均复杂度在O(N) 1-2 若某...

    作业3-线性表抽象数据类型定义与顺序表操作
    1-1
    对于顺序存储的长度为N的线性表,
    访问结点和增加结点的时间复杂度
    分别对应为O(1)和O(N)。(T)
    [解析]增加结点,不同位置复杂度不同,但平均复杂度在O(N)

    1-2
    若某线性表最常用的操作是
    存取任一指定序号的元素和在最后进行插入和删除运算,
    则利用顺序表存储最节省时间。(T)
    [解析]顺序表的一个很大的缺点就是增删结点需要移动,
    但是此题只在表的末尾插入和删除,不需要移动,访问任意指定序号
    的元素用顺序表更方便

    1-3
    对于顺序存储的长度为N的线性表,
    删除第一个元素和插入最后一个元素的
    时间复杂度分别对应为O(1)和O(N)。(F)

    1-4
    (neuDS)在顺序表中逻辑上相邻的元素,
    其对应的物理位置也是相邻的。(T)

    1-5
    (neuDS)所谓随机存取,就是通过首地址和
    元素的位序号值可以在O(1)的时间内找到指定的元素。(T)

    1-6
    (neuDS)顺序存储的线性表不支持随机存取。(F)

    1-7
    (neuDS)在顺序表上进行插入、删除操作时
    需要移动元素的个数与待插入或待删除元素的位置无关。(F)

    2-1
    对于顺序存储的长度为N的线性表,
    访问结点和增加结点的时间复杂度为:(A)
    A.O(1), O(1)
    B.O(1), O(N)
    C.O(N), O(1)
    D.O(N), O(N)

    2-2
    在N个结点的顺序表中,算法的时间复杂度为O(1)的操作是:(A)
    A.访问第i个结点(1≤i≤N)和求第i个结点的直接前驱(2≤i≤N)
    B.在第i个结点后插入一个新结点(1≤i≤N)
    C.删除第i个结点(1≤i≤N)
    D.将N个结点从小到大排序

    2-3
    若某线性表最常用的操作是存取任一指定序号的元素和
    在最后进行插入和删除运算,
    则利用哪种存储方式最节省时间?(D)
    A.双链表
    B.单循环链表
    C.带头结点的双循环链表
    D.顺序表

    2-4
    顺序表中第一个元素的存储地址是100,
    每个元素的长度为2,则第5个元素的地址是()。©
    A.100
    B.105
    C.108
    D.110
    [解析]100, 102, 104, 106, 108

    2-5
    (neuDS)线性表的顺序存储结构是一种(B)
    A.随机存取的存储结构
    B.顺序存取的存储结构
    C.索引存取的存储结构
    D.散列存取的存储结构

    2-6
    (neuDS)一个顺序表所占用的存储空间大小与()无关。©
    A.表的长度
    B.元素的类型
    C.元素的存放顺序
    D.元素中各字段的类型

    2-7
    (neuDS)要将一个顺序表{a​0​​,a​1​​,……,a​n−1​​}中第i个数据元素a​i​​(0≤i≤n-1)删除,需要移动( )个数据元素。
    A.i
    B.n-i-1
    C.n-i
    D.n-i+1
    [解析]第i个元素的位序是i + 1, 需要移动的元素的个数是 n - (i + 1)

    2-8
    用数组表示线性表的优点是()。(B)
    A.便于插入和删除操作
    B.便于随机存取
    C.可以动态地分配存储空间
    D.不需要占用一片相邻的存储空间

    2-9
    若长度为n的线性表采用顺序存储结构,
    那么删除它的第i个数据元素之前,
    需要它一次向前移动()个数据元素。(A)
    A.n-i
    B.n+i
    C.n-i-1
    D.n-i+1

    2-10
    若长度为n的线性表采用顺序结构,
    在第i个数据元素之前插入一个元素,
    需要它依次向后移动()个元素。(B)
    A.n-i
    B.n-i+1
    C.n-i-1
    D.i
    [解析]n-i + 1 : 其中 "n-i"是指 第i+1个元素到 第n个元素,
    "+1"是指第i个元素

    2-11
    线性表L=(a1, a2 ,……,an)用一维数组表示,
    假定删除线性表中任一元素的概率相同(都为1/n),
    则删除一个元素平均需要移动元素的个数是()。©
    A.n/2
    B.(n+1)/2
    C.(n-1)/2
    D.n
    [解析]删除第一个需要 移动 n-1, 删除最后一个需要移动0个
    求和 为 (n-1)n/2, 平均 为 (n-1)/2

    展开全文
  • 线性表的讲解,分析。 线性表的抽象数据类型定义 线性表的存储结构 线性表的应用
  • 二叉树的抽象数据类型定义

    千次阅读 2019-08-29 16:22:23
    类型名称:二叉树 数据对象集:一个有穷的结点集合。 若不为空,则由根结点和其左、右二叉子树组成。 操作集: BT ∈ BinTree, Item ∈ElementType,重要操作有: 1、Boolean IsEmpty( BinTree BT ): 判别BT是否为...

    类型名称:二叉树
    数据对象集:一个有穷的结点集合。
    若不为空,则由根结点和其左、右二叉子树组成。
    操作集: BT ∈ BinTree, Item ∈ElementType,重要操作有:
    1、Boolean IsEmpty( BinTree BT ): 判别BT是否为空;
    2、void Traversal( BinTree BT ):遍历,按某顺序访问每个结点;
    3、BinTree CreatBinTree( ):创建一个二叉树。

    常用的遍历方法有:

    • void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树;
    • void InOrderTraversal( BinTree BT ): 中序—左子树、根、右子树;
    • void PostOrderTraversal( BinTree BT ):后序—左子树、右子树、根
    • void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右
    展开全文
  • 数据元素具有相同类型,相邻元素具有先驱和后继关系 operation InitList 输入:无 功能:线性表的初始化 输出:空的线性表 CreatList 输入:n个数据元素 功能:建立一个线性表 输出:具有n个元素的线性表 ...
    ADT List
    DataModel
         数据元素具有相同类型,相邻元素具有先驱和后继关系
    operation
         InitList
             输入:无
             功能:线性表的初始化
             输出:空的线性表
         CreatList
             输入:n个数据元素
             功能:建立一个线性表
             输出:具有n个元素的线性表
         DestoryList
             输入:无
             功能:销毁线性表
             输出:释放线性表的存储空间
         PrintList
             输入:无
             功能:遍历操作,按序号依次输出线性表中的元素
             输出:线性表中的各个元素
         Length
             输入:无
             功能:求线性表的长度
             输能:线性表中数据元素的个数
         Locate
             输入:数据元素X
             功能:按值查找,在线性表中查找值等于X的元素
             输出:如果查询成功输出值为X的元素,否则输出0
         Get
             输入:元素序号i
             功能:按位查找,在线性表中查找序号位i的元素
             输出:如果查找成功输出序号为i的元素,否则输出0
         Insert
             输入:插入位置i,插入元素X
             功能:插入操作,在位置i处插入元素X
             输出:如果插入成功,则返回新的线性表,否则返回0
         Delete
             输入:删除位置i
             功能:删除操作,删除位置i处的元素
             输出:如果删除成功,返回新的线性表,否则返回0
         Empty
             输入:无
             功能:判空操作,判断线性表是否为空表
             输出:如果是空表返回1,否则返回0
    endADT                                                 
    
    展开全文
  • 编写完成集合抽象数据类型定义及其运算,要求具有并、交、差运算
  • 一、线性表的定义 由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表。 线性表中元素的个数n(n>=0)定义为线性表的长度,n=0时线性表称为空表。 二、非空线性表及线性结构的特点 1、存在唯一的一个被称为...
  • 线性表的抽象数据类型定义

    千次阅读 2018-03-22 11:18:17
     //返回第i个数据元素的值(返回类型可能不同) public int indexOf(Object obj); //第一个与obj满足关系equals()数据元素的位序。若这样的数据元素不存在,则返回值为-1(obj的类型根据实际不同)  public ...
  • 用二位数组存放矩阵,c语言实现矩阵的加法和乘法 代码如下: #include<stdio.h> #include<stdlib.h> #define MAXR 100 //矩阵最大行数 #define MAXC 100 //矩阵最大列数 ...typedef int ElementType;...
  • 这是数据结构中的常见数据类型定义,里面实现了集合的一些基本操作,例如交并等。
  • 数据结构(C语言版) 严蔚敏 吴伟民 设计练习 线性表的定义构造 代码块: #include <stdio.h> #include <stdlib.h> //Function result status code #define TRUE 1 #define FALSE 0 #define OK 1 #...
  • 判断题 1-1 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(T) 提示:访问直接根据结点位置,增加需要后移 1-2 若某线性表最常用的操作是存取任一指定序号的元素和在...
  • 类型名称 :二叉树 数据对象集 :一个有穷的结点集合。若不为空,则由根节点和其左、右二叉子树组成。 操作集: Boolean isEmpty(BinTree BT);//判别BT是否为空 voidTraversal(BinTree BT);//遍历,按某个...
  •  英语成绩表中的数据具有相同类型,相邻元素具有前驱和后继关系。成绩的各种操作依据序号来进行。   Operation       InitEnglishScore list  前置条件:英语成绩表不存在  ...
  • 线性表的抽象数据类型定义 ADT 线性表 (list) Data 线性表的数据对象集合为 {a1,a2,a3,a4…,an},每个元素的类型均为DataType。其中,除了第一各元素a1以为每个元素有且只有一个直接前驱元素,除了最后一个...
  • 请问抽象数据类型定义到底有什么作用? 如线性表的定义,如果我要建立一个线性表,需要在编译过程中对它进行抽象数据类型定义吗?
  • 抽象数据类型定义

    千次阅读 2016-03-14 19:59:21
    抽象数据类型:(所谓抽象数据类型就是把数据类型和相关操作捆绑在一起) 数据类型:是一组性质相同的值的集合及定义在此集合上的一些操作。 按照取值的不同,数据类型可以分为两类: 1.原子类型:不可以再分解的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,431
精华内容 3,772
关键字:

抽象数据类型定义