精华内容
下载资源
问答
  • 作业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

    展开全文
  • /线性表定义(顺序表) //////////////////////// typedef struct { ElemType * elem; int length; }SqList; //////////// /线性表定义(单链表) //////////////////////// typedef struct LNode { ...
    #include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #define MAXSIZE 1000
    #define ERROR 0
    #define OK 1
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    /线性表定义(顺序表)
    typedef struct
    {
        ElemType *elem;
        int length;
    }SqList;
    /线性表定义(单链表)
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    }LNode,*LinkList;
    /线性表初始化
    Status InitList(SqList &L)
    {
        L.elem = new ElemType[MAXSIZE];
        if(!L.elem) exit(ERROR);
        L.length = 0;
        return OK;
    }
    Status InitList(LinkList &L)
    {
        L = new LNode;
        L->next = NULL;
        return OK;
    }
    /线性表销毁//
    Status DestoryList(SqList &L)
    {
        delete L.elem;
        L.elem = NULL;
        L.length = 0;
        return OK;
    }
    Status DestoryList(LinkList &L)
    {
        LinkList p;
        while(L)
        {
            p = L;
            L = L->next;
            delete p;
        }
        return OK;
    }
    /线性表清空//
    Status ClearList(SqList &L)
    {
        L.length = 0;
        return OK;
    }
    Status ClearList(LinkList &L)
    {
        LinkList p;
        L = L->next;
        while(L)
        {
            p = L;
            L = L->next;
            delete p;
        }
        L->next = NULL;
        return OK;
    }
    /线性表是否为空//
    Status ListEmpty(SqList L)
    {
        if(L.length == 0)
            return OK;
        return ERROR;
    }
    Status ListEmpty(LinkList L)
    {
        if(L->next == NULL)
            return OK;
        return ERROR;
    }
    /线性表长度//
    Status ListLength(SqList L)
    {
        return L.length;
    }
    Status ListLength(LinkList L)
    {
        LinkList p;
        int sum = 0;
        p = L->next;
        while(p)
        {
            p = p->next;
            sum++;
        }
        return sum;
    }
    /获取线性表元素值////
    Status GetElem(SqList L,int i,ElemType &e)
    {
        if(i<1 || i>L.length)   return ERROR;
        e = L.elem[i-1];
        return OK;
    }
    Status GetElem(LinkList L,int i,ElemType &e)
    {
        LinkList p;
        p = L->next;
        int j = 1;
        while(p&&j<i)
        {
            p=p->next;
            ++j;
        }
        if(!p||j>i) return ERROR;
        e = p->data;
        return OK;
    }
    /获取线性表元素位置//
    int LocateElem(SqList L,ElemType e)
    {
        for(int i=0;i<L.length;i++)
            if(L.elem[i]==e)    return i+1;
        return ERROR;
    }
    LNode *LocateElem(LinkList L,ElemType e)
    {
        LinkList p;
        p = L->next;
        while(p && p->data!=e)
            p = p->next;
        return p;
    }
    /返回线性表前驱//
    Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
    {
        int i = 0;
        while(L.elem[i]!=cur_e && i<L.length)
            i++;
        if(i == 0 || i == L.length)    return ERROR;
            L.elem[i-1] = pre_e;
        return OK;
    }
    Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
    {
        LinkList p,q;
        p = L->next;
        q = L;
        while(p->next)
        {
            q = p->next;
            if(q->data = cur_e)
            {
                pre_e = q->data;
                return OK;
            }
            p = q;
        }
        return ERROR;
    }
    /返回线性表后继//
    Status NextElem(SqList L,ElemType cur_e,ElemType &pre_e)
    {
        int i = 0;
        while(L.elem[i]!=cur_e && i<L.length)
            i++;
        if(i == 0 || i == L.length)    return ERROR;
            pre_e = L.elem[i-1];
        return OK;
    }
    Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
    {
        LinkList p;
        p=L->next;
        while(p->next)
        {
            if(p->data == cur_e)
            {
                next_e = p->next->data;
                return OK;
            }
            p = p->next;
        }
        return ERROR;
    }
    /线性表插入//
    Status ListInsert(SqList &L,int i,ElemType &e)
    {
        if((i<1)||(i>L.length)) return ERROR;   //如果插入元素不在表的范围之内,插入失败
        if(L.length == MAXSIZE) return ERROR;   //如果顺序表已满,插入失败
        for(int j = L.length;j >= i-1;j--)      //从第i位开始,每个元素依次向后移动一个单位
        {
            L.elem[j+1] = L.elem[j];
        }
        L.elem[i-1] = e;    //将第i位元素数据域设置为e
        ++L.length;         //表长+1
        return OK;
    }
    Status ListInsert(LinkList &L,int i,ElemType &e)
    {
        LinkList p,s;
        int j=0;
        p=L;
        while(p && (j<i-1)) //查找第i-1个结点,使p指向该结点
        {
            p = p->next;
            ++j;
        }
        if(!p || j>i-1) return ERROR;   //i>n+1或者i<1,插入失败
        s = new LNode;  //为新结点分配内存
        s->data = e;    //新结点数据域置为e
        s->next = p->next;  //新结点的后继设置为p的后继
        p->next = s;    //p的后继设置为s
        return OK;
    }
    /线性表删除//
    Status ListDelete(SqList &L,int i)
    {
        if((i<1) || (i>L.length))   return ERROR;   //如果删除元素不在表的范围之内,删除失败
        for(int j = i;j <= L.length;j++)
            L.elem[j-1] = L.elem[j];    //被删除元素之后的元素前移
        --L.length;  //表长-1
        return OK;
    }
    Status ListDelete(LinkList &L,int i)
    {
        LinkList p,q;int j = 0;
        p = L;
        while((p->next) && (j<i-1)) //查找第i-1个结点,p指向该结点
        {
            p = p->next;
            ++j;
        }
        if(!(p->next) || (j>i-1))   return ERROR;   //当i>n或i<1时,删除位置不合适
        q = p->next;    //临时保存被删结点的位置以备释放
        p->next = q->next;  //改变删除结点前驱结点的指针域
        delete q;       //释放删除结点的空间
        return OK;
    }
    /线性表元素遍历//
    Status TraverseList(SqList L)
    {
        for(int i=0;i<L.length;i++)
        {
    
        }
        return OK;
    }
    Status TraverseList(LinkList L)
    {
        while(L->next)
        {
            L = L->next;
            cout<<L->data<<' ';
        }
        return OK;
    }
    /创建单链表(头插法)(带头节点)//
    void CreateList_H(LinkList &L,int n)
    {
        LinkList p;
        L = new LNode;
        L->next = NULL;
        for(int i = 0;i < n;i++)
        {
            p = new LNode;
            cin>>p->data;
            p->next = L->next;
            L->next = p;
        }
    }
    /创建单链表(头插法)(不带头节点)//
    void CreateList_NH(LinkList &L,int n)
    {
        LinkList p;
        L->next = NULL;
        for(int i = 0;i < n;i++)
        {
            p = new LNode;
            cin>>p->data;
            p->next = L->next;
            L->next = p;
        }
    }
    /创建单链表(尾插法)(带头节点)//
    void CreateList_R(LinkList &L,int n)
    {
        LinkList p,r;
        L = new LNode;
        L->next = NULL;
        r=L;
        for(int i = 0;i < n;i++)
        {
            p = new LNode;
            cin>> p->data;
            p->next = NULL;
            r->next = p;
            r = p;
        }
    }
    /创建单链表(尾插法)(不带头节点)//
    void CreateList_NR(LinkList &L,int n)
    {
        LinkList p,r;
        L->next = NULL;
        r=L;
        for(int i = 0;i < n;i++)
        {
            p = new LNode;
            cin>> p->data;
            p->next = NULL;
            r->next = p;
            r = p;
        }
    }
    /双向链表定义//
    typedef struct DuLNode
    {
        ElemType data;          //数据域
        struct DuLNode *prior;  //指向直接前驱
        struct DuLNode *next;   //指向直接后继
    }DuLNode,*DuLinkList;
    /双向链表插入//
    Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
    {
        DuLinkList p,s;
        int j=0;
        p=L;
        while(p && (j<i-1)) //查找第i-1个结点,使p指向该结点
        {
            p = p->next;
            ++j;
        }
        if(!p || j>i-1) return ERROR;   //i>n+1或者i<1,插入失败
        s = new DuLNode;
        s->data = e;            //s的数据域设置为e
        s->prior = p->prior;    //s的前驱设置为p的前驱
        p->prior->next = s;     //p的前驱元素的后继设置为s
        s->next = p;            //s的后继设置为p
        p->prior = s;           //p的前驱设置为s
        return OK;
    }
    /双向链表删除//
    Status ListDelete_DuL(DuLinkList &L,int i)
    {
        DuLinkList p,q;int j = 0;
        p = L;
        while((p->next) && (j<i-1)) //查找第i-1个结点,p指向该结点
        {
            p = p->next;
            ++j;
        }
        if(!(p->next) || (j>i-1))   return ERROR;   //当i>n或i<1时,删除位置不合适
        p->prior->next = p->next;   //p的前驱元素的后继设置为p的后继
        p->next->prior = p->prior;  //p的后继元素的前驱设置为p的前驱
        delete p;      //删除元素p
        return OK;
    }
    /线性表的合并(顺序表)(无序表)//
    void MergeList(SqList &LA,SqList LB)
    {
        int m = LA.length;
        int n = LB.length;
        ElemType e;
        for(int i = 1;i<=n;i++)
        {
            GetElem(LB,i,e);
            if(!LocateElem(LA,e))
                ListInsert(LA,++m,e);
        }
    }
    /线性表的合并(顺序表)(有序表)//
    void MergeList_Sq(SqList LA,SqList LB,SqList &LC)
    {   //将AB两表中的有序数据统一有序放到一个C表中
        LC.length = LB.length+LA.length;//新表的长度等于两表的长度和
        LC.elem  = new ElemType[LC.length];//为新表申请空间
        ElemType *pa,*pb,*pc,*pa_last,*pb_last;//定位三个表中各个结点的位置
        pc = LC.elem;
        pa = LA.elem;
        pb = LB.elem;
        pa_last = LA.elem + LA.length-1;
        pb_last = LB.elem + LB.length-1;
        while((pa<pa_last)&&(pb<pb_last))//依次摘取两表中数值较小的结点放到c表的最后
        {
            if(*pa<=*pb)    *pc++ = *pa++;//如果当前A表的数据小于B表的数据,先取A表数据
            else    *pc++ = *pb++;      //否则取B表的数据
        }
        while(pa <= pa_last)  *pc++ = *pa++;//如果A表的数据还没有取完,继续取
        while(pb <= pb_last)  *pc++ = *pb++;//如果B表的数据还没有取完,继续取
    }
    /线性表的合并(链式表)//
    void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC)
    {
        LinkList pa,pb,pc;
        pa = LA->next;
        pb = LB->next;
        LC = LA;
        pc = LC;
        while(pa && pb)
        {
            if(pa->next <= pb->next)
            {
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else
            {
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
        }
        pc->next = pa? pa:pb;
        delete LB;
    }

     

    转载于:https://www.cnblogs.com/basketball616/p/11143597.html

    展开全文
  • 线性表抽象数据类型

    2017-12-30 19:53:42
    template class List { private: void clear(); bool isEmpty(); bool append(const T &); bool insert(int a, const T&); bool position(int &p, const T&); };
    template <class T>
    class List
    {
    private:
        void clear();
        bool isEmpty();
        bool append(const T &);
        bool insert(int a, const T&);
        bool position(int &p, const T&);
    };

    展开全文
  • 线性表抽象数据类型 ADT 线性表(List) Data //数据元素关系之间逻辑关系的定义 线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。 其中,除了第一个元素a1意外,每个元素都有且只有一个...

    线性表的抽象数据类型

    ADT 线性表(List)
    Data  //数据元素关系之间逻辑关系的定义
    	线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。
    	其中,除了第一个元素a1意外,每个元素都有且只有一个前驱元素,
    	除了最后一个元素an之外 ,每个元素有且只有一个后继元素。
    	数据元素之间的关系是一对一的关系 
    Operation
    	InitList(*L): 初始化操作,建立一个空的线性表
    	ListEmpty(L): 若线性表为空,返回true,否则返回false
    	ClearList(*L): 将线性表清空
    	GetElem(L,i,*e): 将线性表L中的第i个位置元素值返回给e
    	LocateElem(L,e): 在线性表L中查找与给定的值e相等的元素,如果查找成功,返回该元素在表中序号
    					表示成功,否则返回0表示失败
    	ListInsert(*L,i,e): 在线性表L的第i个位置插入新元素e 
    	Listdelete(*L,i,*e): 删除线性表L中第i个元素,并用e返回值
    	ListLength(L): 返回线性表L中的元素个数
    endADT
    
    展开全文
  • 2.线性表抽象数据类型定义 ADT List{ 数据对象a_i 数据关系a_{i-1}和a_i 基本操作: InitList(&L) //构造一个空的线性表L DestroyList(&L) //销毁线性表L ClearList(&L) //将线性表L置为空表 ...
  • 线性表-抽象数据类型

    2020-04-29 19:27:17
    线性表定义: 线性表(List):由零个或多...在搞懂抽象数据类型之前,我们需要首先搞清楚什么是数据类型。 数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 原子类型:不可以再分解...
  • 抽象数据类型线性表的定义与实现

    千次阅读 2018-09-12 10:36:37
    最近刚刚上完数据结构的第一章,好久没有写线性表了,正好借着老师的作业温习一下,主程序实现的就是简单的list有序合并。不多比比,直接上代码 第一部分 de.hpp文件 // // main.cpp // test // // Created by ...
  • 数据结构——线性表抽象数据类型 ADT (SequenceList)         线性表(list) Data        线性表的数据对象集合为{a1,a2,a3,…,an},每个...
  • 线性表定义线性表:由零个或多个数据元素组成的有限序列。所以线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,称为空表。例如: 当天黑队伍解散各自回家了,队伍《梦之队》还在,只不过队伍没人,解散了。...
  • 从本章开始正式进入数据结构学习...... () 1.线性表的定义 Definition:零个或多个数据... 线性表数据元素个数是有限的。 注意:零个数据元素的有限序列又被称为空表 操作: 1.创建和初始化 2.插入 3.查找 ...
  • 线性表抽象数据类型 线性表抽象数据类型定义: ADT:线性表(list) data 线性表的数据对象集合为{a1,a2,…an},每个元素的类型均为datatype,其中除第一个元素a1和最后一个元素an外每一个元素有且只有一个前驱...
  • 线性表抽象数据类型描述

    千次阅读 2016-11-16 19:12:14
    public interface IList { public void clear();...//判断线性表中的数据元素个数是否为0,若为0反回true,否则反回false。 public int length();//求线性表中的元素个数并返回其值。 public
  • 线性表抽象数据类型定义

    千次阅读 2018-03-22 11:18:17
     //返回第i个数据元素的值(返回类型可能不同) public int indexOf(Object obj); //第一个与obj满足关系equals()数据元素的位序。若这样的数据元素不存在,则返回值为-1(obj的类型根据实际不同)  public ...
  • 实验项目名称: 抽象数据类型实现 实验项目性质: 设计性实验 所属课程名称: 数据结构 以教材中讨论的各种抽象数据类型为对象,利用C语言的数据类型表示和实现其中某个抽象数据类型。 本资源包括了可执行文件、源...
  • 掌握线性表的顺序存储结构和链式存储结构,熟练掌握顺序表和链表基本算法的实现
  • 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(T) 提示:访问直接根据结点位置,增加需要后移 1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和...
  • 目录线性表的定义线性表抽象数据类型 线性表的定义 线性表(List):0或多个数据元素的有限数列。 将线性表记为(a1,a2,…,ai-1,ai,ai+1,…,an),当i=1,2,…,n-1时,ai有且只有一个直接后驱,当i=2,…...
  • 线性表数据元素的个数是有限的 。零个元素的有限序列被称为空表 线性表的常见操作:(增删改查) 创建和初始化(排队),查找(寻找),插入,删除,清空 ADT 线性表(SequenceList) Data  1.线性表数据...
  • @TOC初识线性表抽象数据类型(数据结构预算法笔记(三)) 线性表 线性表是什么,简单来说线性表就如同生活中的排队一样,具有线一样性质的数据结构.线性表有0个(当数据元素为0时,称该线性表为空表)或者多个数据元素组成...
  • =0)个数据特性相同的元素构成的有限序列称为线性表线性表中元素的个数n(n>=0)定义为线性表的长度,n=0时线性表称为空表。 二、非空线性表及线性结构的特点 1、存在唯一的一个被称为“第一个”的数据元素; 2、...
  • 数据结构实战开发中类继承关系图中总体概括了数据结构实战开发中所有类的继承关系,本文分析线性表中顺序表的实现,下一篇实现包括静态顺序表StaticList和...既然是线性表,那么首先需要线性表抽象类List,主要是...
  • 本章主要介绍线性表的定义和抽象数据类型线性表的顺序存储结构以及每种线性表操作在顺序存储结构上的具体实现,链接存储的概念,线性表的链接存储结构以及每种线性表操作在链接存储结构上的具体实现等内容。
  • 数据对象:D={ai|ai=ElemSet,i=1,2,..,n,n≥0} 数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} 基本操作: IniList(&L) 操作结果:构造一个新的线性表L。 DestroyList(&L) 操作结果:销毁...
  • //初始条件:线性表L已经存在 //操作结果:销毁线性表L ClearList(&L) //初始条件:线性表L已存在 //操作条件:将L重置为空表 ListEmpty(L) //初始条件:线性表L已经存在 //操作结果:若L为空表,则返回TRUE,否则...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,428
精华内容 5,371
关键字:

线性表的抽象数据类型的实现