精华内容
下载资源
问答
  • <数据结构> ADT例子

    千次阅读 2014-09-24 15:25:12
    ADT English_scores  Data  线性表中的数据类型为int,相邻元素具有前驱和后继关系    Operation  Init  前置条件:线性表不存在  输入:班级同学的上学期的英语成绩  功能:成绩表的初始化...
    ADT English_scores


     Data
       线性表中的数据类型为int,相邻元素具有前驱和后继关系
     
     Operation


       Init
           前置条件:线性表不存在
           输入:班级同学的上学期的英语成绩
           功能:成绩表的初始化
           输出:成绩表建立是否成功(成功1,失败0)
           后置条件:一个非空的成绩表
       
       Insert
           前置条件:成绩表已存在
           输入:插入元素x
           功能:在成绩表的y位置插入元素x
           输出:插入是否成功(成功1,失败0)
           后置条件:若插入成功,成绩表增加了一个元素


       Find_Location
           前置条件:成绩表已存在
           输入:元素的序号i
           功能:在成绩表中查找序号为i的数据元素
           输出:查找是否成功(如果成功,查找成功,并返回查找元素的值,否则返回,并输出无此元素)
           后置条件:成绩表无变化


       Find_value
           前置条件:成绩表已存在
           输入:元素的值x
           功能:在成绩表中查找值等于x的元
           输出:查找是否成功(如果成功,输出查找成功,并返回该元素在表中的序号,否则返回,并输出无此元素)
           后置条件:成绩表无变化


       Delete
           前置条件:成绩表已存在
           输入:删除元素的序号i
           功能:在表中删除序号为i的元素
           输出:删除是否成功(如果成功,输出删除成功,并返回该元素的值,否则返回)
           后置条件:成绩表减少一个元素


       Show
           前置条件:成绩表已存在
           输入:无
           功能:按序号依次输出成绩表里所有的元素
           输出:表中的所有的数据元素
           后置条件:成绩表无变化


       Average
           前置条件:成绩表已存在
           输入:无
           功能:计算成绩表中所有元素的平均值
           输出:成绩表中所有元素的平均值
           后置条件:成绩表无变化
       
       Max_Min
           前置条件:成绩表已存在
           输入:无
           功能:找出成绩表中元素值最大和最小的
           输出:成绩表中的最大值和最小值及其元素的序号
           后置条件:成绩表无变化
           
       Seqencing
           前置条件:成绩表已存在
           输入:无
           功能:把成绩表中元素按值从大到小排序
           输出:排序后的成绩表的全部元素
           后置条件:成绩表无变化


    endADT
    展开全文
  • 1、【平衡符号】:做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号,则将其推入栈中。如果字符是一个封闭符号,则当栈空时报错。否则,将栈元素弹出,如果弹出的符号不是对应的开放符号,则报错。...

    1、【平衡符号】:

    做一个空栈。读入字符直到文件结尾。如果字符是一个开放符号,则将其推入栈中。如果字符是一个封闭符号,则当栈空时报错。否则,将栈元素弹出,如果弹出的符号不是对应的开放符号,则报错。在文件结尾,如果栈非空则报错。

    2、【后缀表达式】
    例如一个计算表示:4*1.6 + 5+6*1.6
    写成后缀(逆波兰)记法为: 4 1.6 * 5 + 6 1.6 * +
    计算这个问题最容易的方法是使用一个栈。当见到一个数时就把他推入栈中;在遇到一个运算符时该算符就作用于从该栈弹出的两个数(符号)shang ,再将所得结果推入栈中。

    3、【中缀到后缀的转换】
    这个算法的思想是,当看到一个操作符的时候,把他放到栈中。栈代表挂起的操作符。然而,栈中有些具有高优先级的操作符现在知道当他们不再被挂起时要完成使用,应该被弹出。这样,在把当前操作符放入栈中之前,那些在栈中并在当前操作符之前要完成使用的操作符被弹出。

    4、【方法调用 】

    展开全文
  • 栈是一种特殊的线性表,是一种线性数据结构,其特殊性是表现在操作定义上:插入和删除操作只能在两端进行(不允许在线性表的中间插入和删除)。...这里我以链式栈为例子给大家讲解栈ADT的定义。...

    栈是一种特殊的线性表,是一种线性数据结构,其特殊性是表现在操作定义上:插入和删除操作只能在两端进行(不允许在线性表的中间插入和删除)。

    栈(Stack):

    数据结构————线性关系

    操作————一端固定,只允许一端插入删除

    特性————“先进的先出,后进的后出”

    栈有两种存储方式,一种是顺序存储(顺序栈),另一种是链式存储(链式栈)。

    这里我以链式栈为例子给大家讲解栈ADT的定义。

    单链栈:

    1.存储结构:

    特点:栈空间容易扩充,减少了溢出的可能。只有在系统没有空间时才会溢出。

    2.C++类实现

    链式栈类的定义:

    //栈节点类定义
    struct StackNode{
    public:
        T data;//栈节点数据
        StackNode *link;//节点链指针
        StackNode(T d=0,StackNode *next=NULL):data(d),link(next){}
        ~StackNode(){};
    };
    //链式栈类定义
    class LinkedStack{
    private:
        StackNode *top;//栈顶指针
    public:
        LinkedStack():top(NULL){}//构造函数
        ~LinkedStack(){MakeEmpty();}//析构函数
        void Push(T &x);//进栈
        bool Pop();//出栈
        bool GetTop();//取栈顶元素
        bool IsEmpty() const{return(top==NULL)?true:false;}
        int GetSize();
        void MakeEmpty();//清空栈内容
    };

    (1)栈置空:和单链表置空原理相同

    //单链表栈置空
    void LinkedStack::MakeEmpty(){
        //逐次删去链式栈中的元素直至栈顶指针为空
        StackNode *p;
        while (top!=NULL){
            p = top;
            top = top->link;
            delete p;
        }
    };

    (2)入栈

    //入栈
    void LinkedStack::Push(T &x){
        //将元素值x插入到链式栈的栈顶,即链头
        top = new StackNode(x,top);//创建新节点
        //assert(top!=NULL);//创建失败退出
    };

    (3)出栈

    //出栈
    bool LinkedStack::Pop(){
        //删除栈顶节点,返回被删除的栈顶元素
        if (IsEmpty()==true) return false;
        StackNode *p = top;//记录退栈节点
        top = top->link;//退栈
        int x = p->data;//返回退栈元素
        cout<<"退栈元素为:"<<x<<endl;
        delete p;//释放节点
        return true;
    };

    (4)获得栈顶元素

    bool LinkedStack::GetTop(){
        if (IsEmpty()==true) return false;
        T x;
        x = top->data;
        cout<<"栈顶元素为:"<<x<<endl;
        return true;
    };

    (5)获得栈的大小

    int LinkedStack::GetSize(){
        StackNode *p=top;
        int Size = 0;
        while (p!=NULL){
            p = p->link;
            Size = Size + 1;
        }
        return Size;
    };

    完整ADT代码如下:

    #include <iostream>
    
    using namespace std;
    
    typedef int T;
    
    //栈节点类定义
    struct StackNode{
    public:
        T data;//栈节点数据
        StackNode *link;//节点链指针
        StackNode(T d=0,StackNode *next=NULL):data(d),link(next){}
        ~StackNode(){};
    };
    
    //链式栈类定义
    class LinkedStack{
    private:
        StackNode *top;//栈顶指针
    public:
        LinkedStack():top(NULL){}//构造函数
        ~LinkedStack(){MakeEmpty();}//析构函数
        void Push(T &x);//进栈
        bool Pop();//出栈
        bool GetTop();//取栈顶元素
        bool IsEmpty() const{return(top==NULL)?true:false;}
        int GetSize();
        void MakeEmpty();//清空栈内容
    };
    
    bool LinkedStack::GetTop(){
        if (IsEmpty()==true) return false;
        T x;
        x = top->data;
        cout<<"栈顶元素为:"<<x<<endl;
        return true;
    };
    
    int LinkedStack::GetSize(){
        StackNode *p=top;
        int Size = 0;
        while (p!=NULL){
            p = p->link;
            Size = Size + 1;
        }
        return Size;
    };
    
    //单链表栈置空
    void LinkedStack::MakeEmpty(){
        //逐次删去链式栈中的元素直至栈顶指针为空
        StackNode *p;
        while (top!=NULL){
            p = top;
            top = top->link;
            delete p;
        }
    };
    
    //入栈
    void LinkedStack::Push(T &x){
        //将元素值x插入到链式栈的栈顶,即链头
        top = new StackNode(x,top);//创建新节点
        //assert(top!=NULL);//创建失败退出
    };
    
    //出栈
    bool LinkedStack::Pop(){
        //删除栈顶节点,返回被删除的栈顶元素
        if (IsEmpty()==true) return false;
        StackNode *p = top;//记录退栈节点
        top = top->link;//退栈
        int x = p->data;//返回退栈元素
        cout<<"退栈元素为:"<<x<<endl;
        delete p;//释放节点
        return true;
    };

    测试代码:

    int main()
    {
        LinkedStack ls;
        for(int i=0;i<10;i++){
            ls.Push(i);
        }
        int Size;
        Size = ls.GetSize();
        cout<<"栈大小:"<<Size<<endl;
    
        ls.Pop();
        Size = ls.GetSize();
        cout<<"栈大小:"<<Size<<endl;
    
        ls.GetTop();
        return 0;
    }

    测试结果:

    展开全文
  • 队列是一种特殊的线性表,数据元素之间是线性关系,其插入和删除操作分别在两边进行,一端只能插入,另一端只能删除。 队首(front):进行删除操作的一端; 队尾(rear):进行插入操作的一端; 入队:在队尾插入一个...

    队列是一种特殊的线性表,数据元素之间是线性关系,其插入和删除操作分别在两边进行,一端只能插入,另一端只能删除。

    队首(front):进行删除操作的一端;

    队尾(rear):进行插入操作的一端;

    入队:在队尾插入一个元素;

    出队:在队首插入一个元素;

    特性:元素的操作顺序符合“先进先出(FIFO)”或“后进后出(LILO)”。

    我以链式队列为例子讲解队列的一般操作。

    链式队列的存储方式同一般的链式表的存储结构完全相同;队列与栈不同的是,队列两端都有操作,为了方便,需要设置两个指示器(front和rear),而栈只在一端操作,只需要一个指示器。

    接下来说一下链式队列C++类实现。

    1.链式队列的类定义:

    //队列节点类的定义
    struct QueueNode{
    public:
        int data;//队列数据元素
        QueueNode *link;//节点链指针,指向下一个元素
    public:
        QueueNode(int d,QueueNode *next=NULL):data(d),link(next){}
    };
    //队列类的定义
    class LinkedQueue{
    public:
        QueueNode *Front,*Rear;//队头、队尾指针
    public:
        LinkedQueue():Rear(NULL),Front(NULL){}//构造函数
        ~LinkedQueue(){MakeEmpty();}//析构函数
        bool EnQueue(int x);//入队
        bool DeQueue();//出队
        bool GetFront();//取队首元素
        void MakeEmpty();//队列置空
        bool IsEmpty() const{return (Front==NULL)?true:false;}//队列判空
        int GetSize();//求队列长度
    };

    2.成员函数的实现:

    (1)置空队列操作:同单链表释放

    void LinkedQueue::MakeEmpty(){
        //释放链表中所有节点
        QueueNode *p;
        while (Front!=NULL){
            //逐个释放节点
            p = Front;
            Front = Front->link;//从链上摘下
            delete p;//释放
        }
    };
    

    (2)入队操作:分为队列为空和队列不空两种情况

    //入队
    bool LinkedQueue::EnQueue(int x){
        if(Front==NULL){
            //创建第一个节点
            Front = Rear = new QueueNode(x);
            if(Front==NULL) return false;//分配失败
        }
        else{
            //队列不空,插入
            Rear->link = new QueueNode(x);
            if(Rear->link==NULL) return false;//分配失败
            Rear = Rear->link;
        }
        return true;
    };

    (3)出队操作:队头出去一个,队头指针后移一个节点

    //出队
    bool LinkedQueue::DeQueue() {
        if (IsEmpty() == true) return false;//判队空
        QueueNode *p = Front;
        int x = Front->data;
        Front = Front->link;
        cout<<"出队元素:"<<x<<endl;
        delete p;
        return true;
    };

    (4)取队首元素

    //获取队首元素
    bool LinkedQueue::GetFront() {
        if (IsEmpty() == true) return false;
        int x = Front->data;
        cout<<"队首元素:"<<x<<endl;
        return true;
    };

    (5)求队列长度

    //求队长度
    int LinkedQueue::GetSize(){
        QueueNode *p = Front;
        int k=0;
        while(p!=NULL){
            k++;
            p= p->link;
        }
        return k;
    };

    完整ADT代码:

    #include <iostream>
    
    using namespace std;
    
    //队列节点类的定义
    struct QueueNode{
    public:
        int data;//队列数据元素
        QueueNode *link;//节点链指针,指向下一个元素
    public:
        QueueNode(int d,QueueNode *next=NULL):data(d),link(next){}
    };
    
    //队列类的定义
    class LinkedQueue{
    public:
        QueueNode *Front,*Rear;//队头、队尾指针
    public:
        LinkedQueue():Rear(NULL),Front(NULL){}//构造函数
        ~LinkedQueue(){MakeEmpty();}//析构函数
        bool EnQueue(int x);//入队
        bool DeQueue();//出队
        bool GetFront();//取队首元素
        void MakeEmpty();//队列置空
        bool IsEmpty() const{return (Front==NULL)?true:false;}//队列判空
        int GetSize();//求队列长度
    };
    
    void LinkedQueue::MakeEmpty(){
        //释放链表中所有节点
        QueueNode *p;
        while (Front!=NULL){
            //逐个释放节点
            p = Front;
            Front = Front->link;//从链上摘下
            delete p;//释放
        }
    };
    
    //入队
    bool LinkedQueue::EnQueue(int x){
        if(Front==NULL){
            //创建第一个节点
            Front = Rear = new QueueNode(x);
            if(Front==NULL) return false;//分配失败
        }
        else{
            //队列不空,插入
            Rear->link = new QueueNode(x);
            if(Rear->link==NULL) return false;//分配失败
            Rear = Rear->link;
        }
        return true;
    };
    
    //出队
    bool LinkedQueue::DeQueue() {
        if (IsEmpty() == true) return false;//判队空
        QueueNode *p = Front;
        int x = Front->data;
        Front = Front->link;
        cout<<"出队元素:"<<x<<endl;
        delete p;
        return true;
    };
    
    //获取队首元素
    bool LinkedQueue::GetFront() {
        if (IsEmpty() == true) return false;
        int x = Front->data;
        cout<<"队首元素:"<<x<<endl;
        return true;
    };
    
    //求队长度
    int LinkedQueue::GetSize(){
        QueueNode *p = Front;
        int k=0;
        while(p!=NULL){
            k++;
            p= p->link;
        }
        return k;
    };

    测试:

    int main()
    {
        LinkedQueue lq;
        for(int i=1;i<=10;i++){
            lq.EnQueue(i);
        }
        lq.GetFront();
        int sz = lq.GetSize();
        cout<<"队列大小:"<<sz<<endl;
        lq.DeQueue();
        lq.GetFront();
        sz = lq.GetSize();
        cout<<"队列大小:"<<sz<<endl;
        return 0;
    }

    结果:

    展开全文
  • 数据结构与算法学习笔记——栈ADT C++实现1 特点2 包含的操作3 实现方式3.1 基于数组实现(应用较多)3.2 基于单链表实现 1 特点 栈的数据结构为线性结构 栈只能在同一位置进行插入和删除,这个位置叫做栈顶。后进...
  • 数据结构与算法学习笔记——队列ADT C++实现1 特点2 包含的操作3 实现方式4 队列与循环队列4.1 队列4.2 循环队列 1 特点 队列的数据结构为线性结构 队列只能在一端完成插入,在另一端完成删除。先进先出(FIFO),...
  • 其递归结构如图所示: 二叉树的一个性质是平均二叉树的深度要比节点个数N小得多,分析表明,这个深度是,对于特殊类型的二叉树,即二叉查找树(binary search tree),其深度的平均值为。 二叉树有许多与搜索...
  • 数据结构入门 清华大学刘汝佳 什么是数据结构 数据结构的含义 关系 操作 例子:数组 [] 关系:前驱/后继 操作:随机存取,插入,删除. 数据结构为算法服务 根据算法对数据的操作要求,设计合适的数据结构 实现同一套操作,...
  • 什么是数据结构

    2017-10-29 23:09:00
    又如《数据结构与算法分析》中的解释:“数据结构ADT(抽象数据类型 Abstract Data Type)的物理实现” .....很多资料中对于“数据结构”的解释都相当晦涩抽象,有没有一种比较生动形象的例子可以来介绍数据结构呢...
  • 抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。 它包括数据对象、数据关系、操作集合 例子:arraylist ADT ArrayList{ 数据对象:D={a1,a2,a...
  • 例子是《数据结构与算法c++描述》中的线性表中抽象数据类型 (abstract data type, ADT): 目录 基本概念: 构造函数与析构函数: 是否为空: Find函数: 查找函数: 删除数据: 插入函数: 输出函数与...
  • 数据结构之——队列

    2021-03-30 21:58:02
    数据结构之——队列 一:队列的定义 队列是允许在一端进行插入操作,而在另一端进行删除操作的线性表,简称FIFO。(队列就像我们平时在超市买东西之后在收银台排队付钱一样,正在付钱的那一端即为队头,没付完一个人...
  • 本文讨论三种最简单的数据结构,也是抽象数据类型(ADT)的最基本的例子:表、栈和队列。1、ADTADT即带有一组操作的一些对象的集合。诸如表、集合、图以及它们与各自的操作一起形成的这些对象都可以被看做是ADTADT...
  • 数据结构与算法分析

    2014-01-15 02:05:59
    第12章 高级数据结构及其实现  12.1 自顶向下伸展树  12.2 红黑树  12.2.1 自底向上插入  12.2.2 自顶向下红黑树  12.2.3 自顶向下删除  12.3 确定性跳跃表  12.4 AA树  12.5 treap树  12.6 k-d...
  • 目录数据结构学习笔记——表、栈、队列的Java实现概念介绍应用场景代码实现测试结果 数据结构学习笔记——表、栈、队列的Java实现 首先介绍抽象数据类型(Abstract data type, ADT)是带有一组操作的一些对象的集合...
  • 数据结构与算法分析—C语言描述 高清版

    千次下载 热门讨论 2008-04-05 21:01:56
    本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的...
  • 例子:圆 ADT Circle{ 数据对象:D={r,x,y|r,x,y都是实数} 数据关系:R={<r,x,y>|r是半径,<x,y>是圆心坐标} 基本操作: Circle(&C,r,x,y) 操作结果:构造一个圆 double Area(C) 初始条件:圆已...
  • 第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下删除 12.3 确定性跳跃表 12.4 aa-树 12.5 treap树 12.6 k-d树 ...
  •  本节以包为例子,继续阐述抽象数据类型。  包用于储存数据项的简单容器。具有如下性质 访问其中的具体某个数据项;增删数据项;判断一个数据项是否在包内;遍历包内所有数据项。  1.3.1 包ADT  包这...
  •  本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
  • 他的主要研究方向是数据结构,算法和教育学。 目录 : 第1章 引论   1.1 本书讨论的内容   1.2 数学知识复习   1.2.1 指数   1.2.2 对数   1.2.3 级数   1.2.4 模运算   1.2.5 证明方法   ...
  • 教材学习内容总结 第三章:集合概述-栈 3.1集合 集合是一种隐藏了实现细节的抽象...抽象数据类型:一个抽象数据类型(ADT)是由数据和在该数据上所实施的操作构成的集合,一个ADT有名称、值域和一组允许执行的操作...
  • 数据结构与算法分析(Java语言描述)学习--第六天第4章 树预备知识树的实现树的遍历及应用二叉树实现例子:表达式树查找树ADT--二叉查找树contains方法findMin和findMax方法insert方法remove方法平均情况分析 ...
  • 有很多东西都讲的比较清楚,很有点意思,例子也比较多,代码注释也还可以让人明白。对于ADT算是真正讲到点子上了。 最完整
  • 中文名: 数据结构与算法分析_Java语言描述(第2版) 作者: 韦斯 译者: 冯舜玺 图书分类: 软件 资源格式: PDF 版本: 扫描版 出版社: 机械工业出版社 书号: ISBN:9787111231837 发行时间: 2009年01月01日 地区...
  • 计算机科学丛书·数据结构与算法分析:Java语言描述(原书第3版) [美]马克·艾伦·维斯 (Mark Allen Weiss) (作者), 冯舜玺 (译者), 陈越 (译者) 目录 出版者的话 前言 第1章引论1 1.1本书讨论的内容1 1.2数学知识...
  • java的数据结构和算法

    2008-10-27 15:42:00
    先看一个例子:/* * 列表ADT接口 */package dsa;public interface List {//查询列表当前的规模 public int getSize();//判断列表是否为空 public boolean isEmpty();//返回第一个元素(的位置) public ...
  • 他是著名的计算机教育专家,在数据结构与算法分析方面卓有建树,著有多部畅销书籍. 本书特点: 31个相对短的章可以按各种顺序阅读。 单独但相关的章将ADT的说明与实现分开。 用很多例子说明新的概念。 突出的“注”...

空空如也

空空如也

1 2 3
收藏数 54
精华内容 21
关键字:

数据结构adt例子

数据结构 订阅