精华内容
下载资源
问答
  • 数据类型: 是一个值的集合和定义在此集合上一组操作的总称。 数据类型有两种:简单型和结构类型。...抽象数据类型(Abstract Datat Type, ADT): 是一个数学模型和定义在此数学模型上一组操作。 ...

    数据类型: 是一个值的集合和定义在此集合上一组操作的总称。
    数据类型有两种:简单型结构类型
    对于结构类型,比如数组,它的值是可以分割的,它是某个结构的值,因此数组这个数据类型的子集是一个数据结构。所以数据类型也可以看做是一个数据结构和定义在这个数据结构上一组操作的总称。

    抽象数据类型(Abstract Datat Type, ADT): 是一个数学模型和定义在此数学模型上一组操作。
    在数据结构中,这个数学模型指的就是数据结构。因此在数据结构中,讨论的抽象数据类型是:一个数据结构和定义在这个数据结构上的一组操作
    因为ADT有两个重要特征,所以从抽象数据类型这个角度讨论数据结构有很多好处。
    【ADT的两个重要特征】
    1.数据抽象
    数据的抽象性指的是:用ADT描述程序处理的实体时,强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)。
    强调的是本质特征,自然会忽略掉无关紧要的属性;描述的是外部使用的接口,能保证外部用户正确地使用它们。
    例如: 抽象复数的数据类型
    复数类型在高级语言里不能直接进行加减,为了使外部用户能够直接使用它,这时就可以定义抽象数据类型复数。
    抽象数据类型复数的定义:

    ADT Complex{
    数据对象:
        D={e1,e2 | e1,e2∈RealSet}
        
    数据关系:
        R1={<e1,e2> | e1是复数的实数部分,e2是复数的虚数部分}
        
    基本操作:
        InitComplex(&Z,v1,v2)   //初始化一个复数
        操作结果:构造复数Z,其实部和虚部分别被赋以参数v1和v2值。
        DestroyComplex(&Z)     //销毁一个复数
        操作结果:复数Z被销毁。
        GetReal(Z,&realPart)   //取复数的实部
        初始条件:复数已存在。
        操作结果:用realPart返回复数Z的实部值。
        GetImageNet(Z,&imagPart)   //取复数的虚部
        初始条件:复数已存在。
        操作结果:用imagPart返回复数Z的虚部值。
        Add(z1,z2,&sum)   // 两个复数相加
        初始条件:z1,z2是复数。
        操作结果:用sum返回两个复数z1,z2的和值。
    }ADT Complex
    

    外部用户对复数操作的时候,只需要简单地调用相加的函数就能实现,这样就实现了抽象数据类型的抽象性。
    2.数据封装
    数据的封装性指的是:将实体的外部特性和其内部实现的细节分离,并且对外部用户隐藏其内部实现细节。
    例如:对于刚才的抽象数据类型复数,外部用户想要实现两个复数的相加,只需要调用相加的函数就可以了,不需要关心复数在计算机内部是怎么表示的。

    抽象数据类型的描述方法: 抽象数据类型可用(D, S, P)三元组表示,其中,D是数据对象,即具有相同特性的数据元素的集合,S是D上的关系集,P是对D的基本操作集。
    说明: D+S实际上就是数据结构,P就是定义在这个数据结构上的操作集。当在讨论数据结构的时候,都是从抽象数据类型出发的,也就是说数据结构和它的操作集是一个整体。

    抽象数据类型的表示方法: 抽象数据类型通过已有的数据类型来实现。

    展开全文
  • 实验项目名称: 抽象数据类型的实现 实验项目性质: 设计性实验 ...以教材中讨论的各种抽象数据类型为对象,利用C语言的数据类型表示和实现其中某个抽象数据类型。 本资源包括了可执行文件、源代码以及实验报告电子版
  • 1.3抽象数据类型表示与实现

    千次阅读 多人点赞 2015-12-06 15:00:54
    记得大二的时候学习严蔚敏大神的《数据结构》,满本书的抽象结构,抽象这个,抽象那个,直接整蒙了。最困难的就是概念本来就晦涩难懂,而且书里面也没有可以直接运行的代码,真头疼。好在最近发现高一凡编写的《数据...

            记得大二的时候学习严蔚敏大神的《数据结构》,满本书的抽象结构,抽象这个,抽象那个,直接整蒙了。最困难的就是概念本来就晦涩难懂,而且书里面也没有可以直接运行的代码,真头疼。好在最近发现高一凡编写的《数据结构算法解析》,里面是全是按照严奶奶的《数据结构》一书编排的代码。终于可以把数据结构全部转化成代码的形式了,趁着现在有时间再把数据结构以代码的形式梳理一遍,再提高一点点能力。 今天复习了数据结构第一章绪论,借鉴高一凡的《数据结构算法解析》,用代码实现了抽象数据类型的表示和实现,还有复习了引用&的用法。至于第一章中讲到的时间复杂度和空间复杂度,大概看来一下。

     注意:

            1. 抽象数据类型(Abstract Data Type ,ADT)是指一个数学模型以及定义在该模型上的一组操作(教材P7)。当然这个抽象数据类型也就是严奶奶写的数据结构的精髓----抛开具体的数据类型来讲解数据结构。

            2.其中教材P9中的例1-6就是一个抽象数据类型三元组定义的例子,这个定义可以看出抽象数据类型是如何定义的。当然这些都不是重点,这些我们《数据结构》开课的时候都学过,重点是如何用具体的代码来表示和实现抽象数据类型。

            3.还要讲解几个代码中的概念:1 )数据结构的表示(存储结构)用类型定义(typedef)描述,例 typedef int  Status  //该语句的意思是在程序int的另一别名是Status,用Status表示int;2)在代码中方法的形参表中,以&打头的参数是C++的引用,引用类型的变量,其值若在函数张发生变化,则变化的值会带回主调函数中;3)程序中数据元素类型约定为ElemType。

            代码实现抽象数据类型的八个函数(教材P9)

    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include<math.h>//其中定义OVERFLOW为3
    #define OK 1
    #define ERROR 0
    typedef int Status;//Status表示函数的类型,其值是函数的结果状态码
    typedef int ElemType;//定义抽象数据类型ElemType在本程序中为整型s In
    typedef ElemType *Triplet;//由InitTriplet分配3个元素存储空间,Triplet类型是ElemType类型的指针,存放ElemType类型的地址
    
    Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3){
    //操作结果:构造三元组T,依次置T的3个元素的初值为v1,v2和v3(教科书第12页)
    	T=(ElemType *)malloc(3* sizeof(ElemType));
    	if(!T)
    		exit(OVERFLOW);//分配失败则退出
    	T[0]=v1,T[1]=v2,T[2]=v3;
    	return OK;
    	
    }
    Status Get(Triplet T,int i,ElemType &e){
    	//初始条件:三元组T已存在,1≤i≤3。操作结果:用e返回T的第i元的值(教科书第12页)
    	if(i<1||i>3)//i不在三元组的范围之内
    		return ERROR;
    	e=T[i-1];//将三元组T的第i个元素的值赋给e
    	return OK;
    }
    Status Put(Triplet &T,int i,ElemType e){//此处的引用符&可加可不加,教科书上加了
    	//初始条件:三元组T已存在,1≤i≤3。操作结果:改变T的第i元的值为e(教科书第12页)
    	if(i<1||i>3)
    		return ERROR;
    	T[i-1]=e;
    	return OK;
    }
    Status IsAscending(Triplet T){//教科书第13页
    	//初始条件:三元组T已存在。操作结果;如果T的3个元素按升序排列,则返回1,否则返回0
    	return (T[0]<=T[1]&&T[1]<=T[2]);
    }
    Status IsDescending(Triplet T){
    	//初始条件;三元组T已存在。操作结果;如果T的3个元素按降序排列,则返回1,否则返回0
    	return (T[0]>=T[1]&&T[1]>=T[2]);
    }
    Status Max(Triplet T,ElemType &e){
    //初始条件:三元组T已存在。操作结果:用e返回指向T的最大元素的值(教科书第13页)
    	e=(T[0]>=T[1])?(T[0]>=T[2]?T[0]:T[2]):(T[1]>=T[2]?T[1]:T[2]);
    	return OK;
    }
    Status Min(Triplet T,ElemType &e){
    	//初始条件:三元组T已存在。操作结果:用e返回指向T的最小元素的值(教科书第13页)
    	e=(T[0]<=T[1])?(T[0]<=T[2]?T[0]:T[2]):(T[1]<=T[2])?T[1]:T[2];
    	return OK;
    }
    Status DestroyTriplet(Triplet &T){
    //操作结果:三元组T被销毁(教科书第12页)
    	free(T);//释放T所指的三元组存储空间
    	T=NULL;//T不在指向任何存储单元
    	return OK;
    }
    void PrintT(Triplet T)//依次输出三元组的值
    {
    	printf("%d,%d,%d\n",T[0],T[1],T[2]);
    }
    void PrintE(ElemType e)//输出元素的值
    {
    printf("%d\n",e);
    }
    void main(){
    Triplet T;
    ElemType m;
    Status i;
    i=InitTriplet(T,5,7,9);//初始化三元组T,其3个元素依次为5,7,9
    printf("调用初始化函数后,i=%d(1:成功)。T的3个值为",i);
    PrintT(T);//输出T的3个值
    i=Get(T,2,m);//将三元组T的第2个值赋给m
    if(i=OK){//调用Get()成功
    	printf("T的第2个值为");
    	PrintE(m);//输出m(=T[1])
    }
    i=Put(T,2,6);//将三元组T的第2个值改为6
    if(i==OK){//调用Put()成功
    	printf("将T的第2个值改为6后,T的3个值为");
    	PrintT(T);//输出T的3个值
    }
    i=IsAscending(T);//测试升序函数
    printf("调用测试升序的函数后,i=%d(0:否 1:是)\n",i);
    i=IsDescending(T);//测试降序的函数
    printf("调用测试降序的函数后,i=%d(0:否 1:是)\n",i);
    if(i=Max(T,m)==OK){
    	printf("T中的最大值为");
    	PrintE(m);//输出最大值m
    }
    if(i=Min(T,m)==OK){
    	printf("T中的最小值为");
    	PrintE(m);//输出最小值m
    }
    DestroyTriplet(T);//函数也可以不带返回值
    printf("销毁T后,T=%u\n",T);
    }
    



    最后再展现下高一凡所编写的《数据结构算法分析》中关于&引用的介绍。引用类型&是C++语言特有的。引用类型的变量,其值若在函数中发生变化,则变化的值会带回主调函数中。下面这个程序表现了引用型变量和非引用型变量的区别。
    #include<stdio.h>
    void fa(int n){//在函数中改变n,将不会带回主调函数(主调函数中的n仍是原值)
    n++;
    printf("在函数fa中:n=%d\n",n);
    }
    void fb(int &n){//由于n为引用类型,在函数中改变n,其值将带回主调函数
    	n++;
    	printf("在函数fb中:n=%d\n",n);
    
    }
    void main(){
    int n=1;
    printf("在主程序中,调用函数fa之前:n%d\n",n);
    fa(n);
    printf("在主程序中,调用函数fa之后:n=%d\n",n);
    printf("在主程序中,调用函数fb之前:n=%d\n",n);
    fb(n);
    printf("在主程序中,调用函数fb之后:n=%d\n",n);
    }

    展开全文
  • 1.抽象数据类型可通过原有的数据类型组合来表示和实现。 2.C语言中,预定义常量格式如下:  #define OK 1 预定义常量用于在程序中多次用到且不想改变变量的值的情况下。 3.typedef int status; 4.值调用,...

    1.抽象数据类型可通过原有的数据类型组合来表示和实现。

    2.C语言中,预定义常量格式如下:

      #define OK 1

    预定义常量用于在程序中多次用到且不想改变变量的值的情况下。

    3.疑问typedef  int status;

    4.值调用,引用调用(C++:在形参表中,以&打头的参数即为引用参数)

    5.switch语句格式:

    格式一

    switch(表达式){

    case 值1:语句序列1;break;

    case 值2:语句序列2;break;

    ......

    case 值n:语句序列n;break;

    default:语句序列n+1;

    }


    格式二

    switch{

    case 条件1:语句序列1;break;

    case 条件2:语句序列2;break;

    ......

    case 条件n:语句序列n;break;

    default:语句序列n+1;

    }

    6.三个循环语句结构

     for语句

    for(赋初值表达式序列;条件;修改表达式序列)

    语句;


    while语句

    while(条件)

    语句;


    do-while语句

    do{

    语句序列;

    }while(条件);


       note:

    while与do-while的区别是while先判断条件是否满足,条件满足后再执行循环体中语句,此结构最少可以执行0次循环体中的语句;而do-while先执行循环体中语句,再判断条件是否满足,从而判断是否继续执行循环体中语句,此结构最少可以执行1次循环体中的语句。

    7.疑问结束语句

    函数结束语句

    格式一:return 表达式;

    格式二:return;


    case语句结束语句:

    break;


    异常结束语句:
    exit(异常代码);

    8.输入输出语句格式

    C语言:

    输入语句  scanf([格式串],变量1,.....,变量n);

    输出语句  printf([格式串],表达式,......,表达式n);

    9.基本函数

    C语言:

    求最大值  max(表达式,......,表达式n);

    求最小值  min(表达式,......,表达式n);

            求绝对值  abs(表达式);

            向下取整  floor(表达式);

    向上取整 ceil(表达式);

    判断文件结束 eof(文件变量); 或 eof

    判断行结束 eoln(文件变量)或 eoln

    10.逻辑运算符

    &&   A&&B  当A为0时,不再对B求值。

    || A||B     当A非0时,不再对B求值。

    展开全文
  • 常见抽象数据类型

    千次阅读 2019-03-27 15:48:25
    一、栈 结构:栈顶、栈底 特点:后进先出。从栈顶压入栈,从栈顶压出栈 二、队列 1、队列 结构:队头、队尾 特点:先进先出。从队尾入队列,从队头出队列 2、双端队列 结构:队头、队尾 特点:队头队尾均可入队/出队...

    一、栈

    结构:栈顶、栈底
    特点:后进先出。从栈顶压入栈,从栈顶压出栈

    二、队列

    1、队列

    • 结构
      队头、队尾
    • 特点
      先进先出。从队尾入队列,从队头出队列

    2、双端队列

    结构:队头、队尾
    特点:队头队尾均可入队/出队

    3、优先级队列

    三、树

    1、树

    结构

    • 一种分层的结构,由根节点 + 根节点的子孙节点(子树)组成

    重要概念

    • 节点
      根节点、内部节点、外部节点(叶子节点)
      父亲节点、兄弟节点、孩子节点(左孩子、右孩子)

    • 一对父子节点(u,v)
    • 路径
      指一系列的节点,其中任意两个连续的节点都是一条边
    • 深度
      节点祖先的个数,根节点的深度是0
    • 高度
      从叶子节点往上数的层数,叶子节点的高度是0

    • 同一深度的所有节点位于1层,根节点是第0层

    2、二叉树

    特点:每个节点最多有两个孩子节点(被称为左孩子或右孩子)

    2.1 满二叉树

    特点:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。

    2.2 完全二叉树

    特点:和满二叉树的区别是,它的最后一行可能不是完整的,但绝对是右方的连续部分缺失。即叶子结点只可能在最大的两层出现

    2.2.1 堆(headq)
    • 特点:
      堆是一颗完全二叉树
      除了根节点之外的每个位置,该位置中存储的键值大于等于其父节点的键值

    2、AVL树

    3、伸展树

    4、(2,4)树

    5、红黑树

    四、图

    1、图
    2、无向图
    3、有向图

    五、映射

    1、映射

    每个唯一的关键字(key)都被关联到对应的一个值(value)上。这种关系被称为映射(map)或关联数组。

    2、哈希表

    一种,支持使用键作为索引的结构,语法如M[key]

    2.1 哈希函数

    哈希函数 h :将每个键k映射到[0,N-1]区间内的整数,其中N是哈希表桶数组的容量

    • 哈希码
    • 压缩函数
    2.2 桶数组

    2.3 负载因子

    3、跳跃表

    六、集合

    展开全文
  • 抽象数据类型三元组Triplet的表示和实现
  • 抽象数据类型(abstract data type,ADT)是指一个数学模型以及定义在该模型上的一组操作。 ADT 抽象数据类型名{ 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> ...
  • 第七话:抽象数据类型ADT

    千次阅读 2021-07-27 06:01:07
    抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。为什么有了数据类型,还要有抽象数据类型呢?各个计算机,不管是大型机、小型机、PC、平板电脑、PDA, 甚至智能手机都拥有...
  • 数据结构、数据类型、抽象数据类型之间的区别

    千次阅读 多人点赞 2019-11-03 20:15:37
    数据元素是最基本的数据单位,最基本的数据元素是一个二进制位。) 逻辑结构指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关系,而与他们在计算机中的存储位置无关。包括: ...
  • 数据结构-抽象数据类型

    千次阅读 2017-12-19 14:19:27
    抽象数据类型 Abstract Data Type  抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成,数据结构又包括数据元素以及元素之间的关系。因此抽象数据元素类型一般由元素、关系及操作三种元素来定义。...
  • 功能有初始化,求最大值,最小值,按升序排序、按降序排序等等
  • 抽象数据类型ADT

    2018-11-26 15:32:36
    1.3抽象数据类型ADT 数据类型: 数据对象集 数据集合相关联的操作集 抽象 描述数据类型的方法不依赖具体实现 ...一个抽象数据类型的软件模块应包含定义、表示和实现三部分 ...抽象数据类型表示与实现...
  • 抽象数据类型表示与实现

    千次阅读 2016-09-28 17:05:30
    预定义常量和类型 //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INEASIBLE -1 #define OVERFLOW -2 ...数据结构的表示(存储结构)用类型定义(typedef)描述。数
  • 抽象数据类型案例

    千次阅读 2021-11-16 21:28:55
    数据结构-第一章-抽象数据类型案例数据结构前言一、介绍二、c++实现总结 前言 一、介绍 抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。其定义取决于它的一组逻辑特性,而其在计算机内部...
  • 数据类型和抽象数据类型

    千次阅读 2020-02-22 16:31:35
    二、抽象数据类型(ADT) 1.定义:由用户定义的表示应用问题的数据模型,即数据结构以及定义在此结构上的一组运算。 2.特征: (1)数据抽象:用ADT描述程序程序处理的实体时,强调的是其本质特征、其所能完成的功能...
  • 什么是抽象数据类型

    千次阅读 2021-04-29 23:15:13
    什么是抽象数据类型?前言1.数据类型和数据构造2.抽象数据类型的概念3.抽象数据类型的描述 前言 抽象数据类型(Abstract Data Type,ADT)是计算机领域中被广泛接受的一种思想和方法,也是一种用于设计和实现程序...
  • 抽象数据类型(三元组ADT、复数四则运算) 数据结构 湖南大学
  • 抽象数据类型三元组Triplet的表示和实现。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。按“值”的不同特性,高级程序语言中的数据类型可分为两类:一类是非结构的原子类型,原子类型的值是不可分解...
  • 如何理解数据结构中的抽象数据类型

    万次阅读 多人点赞 2018-09-04 18:49:23
    抽象数据类型的标准格式 ADT 抽象数据类型名 { Data: 数据元素之间逻辑关系的定义;...抽象数据类型的定义仅仅取决于它的一组逻辑特性,而与它在计算机中的表示和实现无关。 例如,int类型的数据表示的...
  • 学习目的*了解抽象数据类型表示与实现;掌握算法的特征和算法分析的方法;1.3 抽象数据类型表示和实现;1.3抽象数据类型表示和实现(P9;1. 预定义常量和类型 //函数结果状态代码 #define TRUE 1 #define FALSE 0 #...
  • 抽象数据类型

    千次阅读 2019-04-15 20:25:33
    数据结构中有一个非常重要的概念:即抽象数据类型(Abstract Data Type,...抽象数据类型是与表示无关的数据类型,是一个数据模型及定义在该模型上的一组运算。 对一个抽象数据类型进行定义时,必须给出它的名字及各...
  • 5-抽象数据类型(ADT)

    千次阅读 多人点赞 2018-05-25 11:40:53
    1. 以数据为核心的思维   在现实中计算机能够解决非常多的问题,如图1所示,可以用计算机去实现一个GIS地理信息系统,也可以实现一个电子病历系统,或者实现一个计算机管理资源的图形化界面等。包括现在我们使用...
  • 抽象数据类型的实例

    千次阅读 2020-03-20 15:21:38
    重新学习数据结构,主要了解了一些关于数据结构的一些相关的概念; 数据结构是一种带结构的数据集合;它包括逻辑结构还有存储结构,然后学习了一下数据类型的表示以及实现...抽象数据类型的定义仅仅取决于它的一组逻...
  • 人们在使用计算机解决客观世界中存在的具体问题时,通常过程如下:首先通过对客观世界的认知形成印象和概念从而得到了信息,在此基础上... 数据结构主要与在上述过程中从建立概念模型到实现模型转化并为后续程序设...
  • C语言实现抽象数据类型(ADT)

    千次阅读 多人点赞 2020-12-22 20:49:02
    C语言实现抽象数据类型(ADT)什么是抽象数据类型(ADT)C语言通过怎样的方式来实现ADT举例前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结学习目标:学习内容:学习时间:学习产出: 什么是抽象数据类型...
  • 1.3 抽象数据类型表示和实现

    千次阅读 2013-07-28 16:35:25
    和数据结构的形式定义相对应,抽象数据类型可用以下三元组表示: (D,S,P) 其中,D是数据对象,S是D上的关系集,P是对D的基本操作集。一般抽象数据类型定义的格式: ADT 抽象数据类型名{ 数据对象: 数据关系: ...
  • 抽象数据类型(ADT)

    千次阅读 2018-09-17 19:07:13
    一、抽象数据类型定义(ADT) 作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或图描述遗传关系。 定义:一个数学模型以及定义在该模型上的一组操作。 关键:使用它的人...
  • 学习第二课抽象数据类型表示与实现.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 407,448
精华内容 162,979
关键字:

抽象数据类型的表示