精华内容
下载资源
问答
  • 抽象数据类型定义(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); 
    }

    展开全文
  • 抽象数据类型定义 类型名称: 数据对象集:G(V,E)由一个非空有限顶点集合V和一个有限边集合E组成 操作集:对于任意图 G∈Graph,以及v∈V,e∈E Graph Create():建立并返回空 Graph InsertVertex(Graph G,...

    什么是图
    表示多对多的关系
    包含:
    一组顶点:通常用V(Vertex)表示顶点集合
    一组便:通常用E(Edge)表示边的集合

    抽象数据类型定义

    类型名称:图
    数据对象集:G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成
    操作集:对于任意图 G∈Graph,以及v∈V,e∈E

    Graph Create():建立并返回空图
    Graph InsertVertex(Graph G, Vertex v):将v插入G
    Graph InsertEdge(Graph G, Edge e):将e插入G
    void DFS(Graph G, Vertex v):从顶点v出发深度优先遍历图G
    void BFS(Graph G,Vertex v):从顶点v出发宽度优先遍历图G
    void ShortestPath(Graph G, Vertex v, int Dist[]):计算图G中顶点v到任意其他顶点的最短距离
    void MST(Graph G):计算图G的最小生成树

    /* 图的邻接矩阵表示法 */
    
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
           
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
        DataType Data[MaxVertexNum];      /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data[]可以不用出现 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
    
    
    
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
        
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)  
                Graph->G[V][W] = INFINITY;
                
        return Graph; 
    }
           
    void InsertEdge( MGraph Graph, Edge E )
    {
         /* 插入边 <V1, V2> */
         Graph->G[E->V1][E->V2] = E->Weight;    
         /* 若是无向图,还要插入边<V2, V1> */
         Graph->G[E->V2][E->V1] = E->Weight;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
        
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
        
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
    
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->Data[V]));
    
        return Graph;
    }
    
    /* 图的邻接表表示法 */
    
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
    
    /* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        Vertex AdjV;        /* 邻接点下标 */
        WeightType Weight;  /* 边权重 */
        PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
    };
    
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        PtrToAdjVNode FirstEdge;/* 边表头指针 */
        DataType Data;            /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */
    } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{  
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
    
    
    
    LGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V;
        LGraph Graph;
        
        Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接表头指针 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
           for (V=0; V<Graph->Nv; V++)
            Graph->G[V].FirstEdge = NULL;
                
        return Graph; 
    }
           
    void InsertEdge( LGraph Graph, Edge E )
    {
        PtrToAdjVNode NewNode;
        
        /* 插入边 <V1, V2> */
        /* 为V2建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V2;
        NewNode->Weight = E->Weight;
        /* 将V2插入V1的表头 */
        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
            
        /* 若是无向图,还要插入边 <V2, V1> */
        /* 为V1建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V1;
        NewNode->Weight = E->Weight;
        /* 将V1插入V2的表头 */
        NewNode->Next = Graph->G[E->V2].FirstEdge;
        Graph->G[E->V2].FirstEdge = NewNode;
    }
    
    LGraph BuildGraph()
    {
        LGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
        
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
        
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
    
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->G[V].Data));
    
        return Graph;
    }
    
    展开全文
  • 图的抽象数据类型

    2020-04-23 12:24:48
    CreateGraph(*G,V,VR): 按照顶点集V和边弧集VR的定义构造 DestroyGraph(*G): G存在则销毁 LocateVex(G,u): 若G中存在顶点u,则返回位置 GexVex(G,v,) 返回G中顶点v值 PutVex(G,v,val...

    ADT 图(graph)
    Data
    顶点的有穷非空集合和边的集合
    Opeation
    CreateGraph(*G,V,VR): 按照顶点集V和边弧集VR的定义构造图
    DestroyGraph(*G): 图G存在则销毁
    LocateVex(G,u): 若图G中存在顶点u,则返回图中的位置
    GexVex(G,v,) 返回图G中顶点v的值
    PutVex(G,v,value) 将图G中顶点v赋值给value
    FirstAdjwet(G,*V) 返回顶点v的一个邻接顶点,若顶点在G中 无邻接顶点则返回空
    NextAdjVex(G,v,*w)返回顶点v相对于w的下一个邻接顶点,若w是v的最后一个邻接点则返回空。
    InsertVex(*G,v) 在图G中新增顶点v及相关的弧
    DeleteVex(*G,v,w)删除图G中顶点v及相关的弧
    InsertArc(*G,v,w) 在图G中顶点增添弧<v,w>若G是无向图 还需要增添对称弧<w,v>
    DelectArc(*G,v,w)在图G中删除弧<v,w>若G是无向图,则还需删除对称弧<w,v>
    DFSTraverse(G)对图中进行深度优先遍历,在遍历过程中对每个顶点调用
    HFSTraverse(G)对图中进行广度优先遍历,在遍历过程对每个人调用
    endADT

    展开全文
  • 一、 题目:图的抽象数据类型实现 利用VC++的工作环境实现教材里图的基本抽象数据类型。按照课本的要求运用c语言以及数据结构课程所学的知识,设计合理的数据存储结果,实现图的基本操作。 二、 抽象数据类型定义...
  • CreateGraph(*G,V,VR): 按照顶点集V和边弧集VR的定义构造 DestroyGraph(*G): G存在则销毁 LocateVex(G,u): 若G中存在顶点u,则返回位置 GexVex(G,v,) 返回G中顶点v值 PutVex(G,v,value) 将G中...

    我的首发平台是公众号【CodeAllen】,学习交流QQ群:736386324,转载请注明出处

    ADT 图 (Graph)
    
    Data
        顶点的有穷非空集合和边的集合
    Opeation
    	CreateGraph(*G,V,VR): 按照顶点集V和边弧集VR的定义构造图
    	DestroyGraph(*G): 图G存在则销毁
    	LocateVex(G,u): 若图G中存在顶点u,则返回图中的位置
    	GexVex(G,v,) 返回图G中顶点v的值
    	PutVex(G,v,value) 将图G中顶点v赋值给value
    	FirstAdjwet(G,*V) 返回顶点v的一个邻接顶点,若顶点在G中 无邻接顶点则返回空
    	NextAdjVex(G,v,*w)返回顶点v相对于w的下一个邻接顶点,若w是v的最后一个邻接点则返回空。
    	InsertVex(*G,v) 在图G中新增顶点v及相关的弧
    	DeleteVex(*G,v,w)删除图G中顶点v及相关的弧
    	InsertArc(*G,v,w) 在图G中顶点增添弧<v,w>若G是无向图 还需要增添对称弧<w,v>
    	DelectArc(*G,v,w)在图G中删除弧<v,w>若G是无向图,则还需删除对称弧<w,v>
    	DFSTraverse(G)对图中进行深度优先遍历,在遍历过程中对每个顶点调用
    	HFSTraverse(G)对图中进行广度优先遍历,在遍历过程对每个人调用
    endADT

     

    展开全文
  • 1. 定义 在图结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。...(2) 图的顶点与边间的关系 无向图: 边数等于各顶点度数和的一半(因为重复两次计数) ...
  • 抽象数据类型一般指由用户定义的,表示应用问题数学模型,以及定义在这个模型上一组操作总称,具体包括三部分:数据对象,数据对象上关系集合以及数据对象基本操作集合。 抽象数据类型的定义格式如下: ...
  • 抽象数据类型

    2021-03-28 22:51:59
    抽象数据类型是数学的抽象;在ADT的定义中没有地方提到关于这组操作是如何实现的具体解释。诸如线性表、集合、以及它们各自的操作一起形成的这些对象都可以被看作是抽象数据类型,这就像整数、实数、布尔数都是...
  • 图抽象数据类型:ADT Graph ADT Graph 实现方法: (1)邻接矩阵 矩阵每行和每列都代表顶点,若两各顶点之间有边连接,设定行列值或权重。无权边则将分量标注为1。 优点:简单,直观,但边数很少时效率...
  • 数据结构学习笔记22(北大公开课)目录图一、知识概览1.1 概念及定义1.2 图抽象数据类型实现1.3图的应用二、代码实现2.1 实现2.2 实例 图 一、知识概览 1.1 概念及定义 1.2 图抽象数据类型实现 1.3图的应用 下节...
  • 什么是 表示“多对多”关系 包含 一组顶点:通常用V (Vertex) 表示顶点集合 一组边:通常用E (Edge) 表示边集合 边是顶点对:(v,w)∈E(v, w) \in\mathbb E(v,w)∈E,其中v,w∈Vv, w ...抽象数据类型定义 ...
  • 抽象数据类型ADT Graph定义如下: Graph():创建一个空的图; addVertex(vert):将顶点vert加入中 addEdge(fromVert, toVert):添加有向边 addEdge(fromVert, toVert, weight):添加带权有向边 getVertex(vKey)...
  • 一、树的定义 树(有根树)是n(n>=0)个结点有序集合T。 当n等于0时,T为空树; 当n>0时,T是非空树,并且可表示为T={r,T1,T2……Tn}; 其中r是根结点(root). e.g. 如所示,(a)是空树,连一个结点都没有;...
  • 抽象数据类型(ADT)

    千次阅读 2018-09-17 19:07:13
    一、抽象数据类型定义(ADT) 作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或描述遗传关系。 定义:一个数学模型以及定义在该模型上一组操作。 关键:使用它人...
  • 教学目标通过本章学习同学们应该能够:定义数据结构了解其分类抽象数据类型的定义熟练掌握栈和队列原理及应用广义表的定义及操作树与森林转换二叉树及其应用二叉排序树应用哈夫曼树与哈夫曼编码及其应用最...
  • 一、实验目的(1)了解抽象数据类型(ADT)基本概念和及描述方法(2)熟悉文件读写操作(3)熟悉C/C++语言语法及程序设计,为以后章节学习打下基础二、实验相关知识(1)C/C++语言程序设计基础(2)结构体类型...
  • 一、抽象数据类型定义(ADT)作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或描述遗传关系。定义:一个数学模型以及定义在该模型上一组操作。关键:使用它人可以只关心...
  • 第二课 本课主题: 抽象数据类型...一、抽象数据类型定义(ADT) 作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或描述遗传关系。 定义:一个数学模型以及定义在该模...
  • 一、抽象数据类型定义(ADT) 作用:抽象数据类型可以使我们更容易描述现实世界。例:用线性表描述学生成绩表,用树或描述遗传关系。 定义:一个数学模型以及定义在该模型上一组操作。 关键:使用它人可....
  • 图论学的认真,这章很自信,嘻嘻 文章目录 线性表表示的是线性关系,所有元素一对一,每个元素都有一个直接前驱和直接后继。 树更复杂一些,表示的是层次关系,元素之间一对多,一个结点...图的定义: 看个例子 ...
  • 数据结构 - 图的存储结构

    千次阅读 2015-05-01 07:21:34
    图的抽象数据类型定义图是一种数据结构,加上一组基本操作就构成了图的抽象数据类型。 图的抽象数据类型定义如下: ADT Graph{ 数据对象V:具有相同特性的数据元素的集合,称为顶点集。 数据关系R:R={VR} VR={,w>|,...
  • 抽象数据类型定义 几个重要的操作 图的基本概念: 引入: 定义: 图:必须有点(顶点),可以没有边。 如: 这个图是由V1,V2,V3,V4,V5五个顶点和七条边组成的。 相关术语: 有向图:每条边都没有方向的图 无向图...
  • 文章目录1.概述2.单向链表:3. 双向链表4. 二叉树 1.概述 数据结构 = 逻辑结构 + 物理结构 逻辑结构:集合结构、线性结构、树形结构、图形结构 ...抽象数据类型(Abstract Data Type,ADT): 指一个数学模型及定...
  • 集合结构,线性结构,树结构,结构)计算机世界里数据结构是指存储结构(也是物理结构,包括:顺序结构,链接结构,索引结构,散列结构)1.2抽象数据类型(ADT)定义:由一种数据结构和在该数据结构上一组操作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,097
精华内容 438
关键字:

图的抽象数据类型定义