精华内容
下载资源
问答
  • 线性表C++源码.rar

    2020-04-09 12:16:59
    C++描述线性表,通过使用模板,写成通用的模板类,代码调试通过。描述了线性表的顺序存储和链式存储结构,并且富有测试代码,帮助初学者进行感性认知。
  • c++实现线性表完整代码,内涵注释,可视化操作线性表
  • C++编写的线性表,对大家理解数据的存储有帮助……
  • 通过C++模板实现了数据结构中的顺序链表的功能,采用动态分配数组的方法来时间顺序线性表。   #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 ...

     

    通过C++模板实现了数据结构中的顺序链表的功能,采用动态分配数组的方法来时间顺序线性表。

     

    #define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
    #define LISTINCREMENT  10   //线性表存储空间的分配增量
    
    template <typename ElemType>
    class SqList {
    private:
        ElemType *elem; //存储空间基址
        int length;     //当前长度
        int listsize;   //当前分配的存储容量(以sizeof(ElemType)为单位)
    public:
        //无参构造函数,构造一个空的线性表
        SqList() {
            elem = new ElemType[LIST_INIT_SIZE];  //为线性表分配初始空间
            length = 0;                           //当前线性表长度为0
            listsize = LIST_INIT_SIZE;            //容量为初始容量
        }
    
        //有参构造函数,参数为初始线性表的长度,构造一个空的线性表
        SqList(int init_size) {
            elem = new ElemType[init_size];  //为线性表分配初始空间
            length = init_size;              //线性表长度为用户指定长度init_size
            listsize = init_size;            //容量为用户指定容量
        }
    
        //有参构造函数,参数为初始线性表的长度,以及初始化某一个元素的值,构造一个空的线性表
        SqList(int init_size, ElemType init_elem) {
            elem = new ElemType[init_size];  //为线性表分配初始空间
            length = init_size;              //线性表长度为用户指定长度init_size
            listsize = init_size;            //容量为用户指定容量
            for (int i = 0; i < length; i++)
                elem[i] = init_elem;          //初始化为用户指定的元素
        }
    
        //析构函数,用于释放线性表空间,销毁线性表
        ~SqList() {
            length = 0;       //使线性表长度为0
            listsize = 0;     //使线性表容量也为0
            delete[]elem;  //释放线性表空间
        }
    
        //将线性表置为空
        void ClearList() {
            for (int i = 0; i < length; i++)
                elem[i] = NULL;   //将线性表内的元素全部置为空
        }
    
        //判断线性表是否为空
        bool ListEmpty() {
            if (!elem)        //若线性表基址为空,则认为是空表,也可以用(!length)来判断
                return true;
            else
                return false;
        }
    
        //返回线性表中第i个数据元素的值
        ElemType GetElem(int i) {
            //  1<=i<=length
            return elem[i - 1];
        }
    
        //获取线性表的长度
        int LinkLength() {
            return length;
        }
    
        //判断线性表中第一个与e相等的数据元素的位序,如果不存在返回-1
        int LocateElem(ElemType e) {
            int i = 0;
            for (i = 0; i < length; i++) {
                if (e == elem[i])
                    return i + 1;
            }
            if (i == length)
                return -1;
        }
    
        // 在线性表中第i个位置之前插入新的数据元素e,线性表的长度加1,1<=i<=length
        void ListInsert(int i, ElemType e) {
            if (i < 1 || i > length + 1)
                return;                        //i值不合法
            if (length >= listsize) {          //当前存储空间已满,增加分配
                ElemType *newbase = new ElemType[listsize + LISTINCREMENT];
                elem = newbase;                //新基址
                listsize += LISTINCREMENT;     //增加存储容量
            }
            ElemType *q = &elem[i - 1];          //q为插入位置
            for (ElemType *p = &elem[length - 1]; p >= q; --p)
                *(p + 1) = *p;                      //插入位置及之后的元素右移
            *q = e;           //插入e
            ++length;   //表长增1
        }
    
        // 在顺序线性表中删除第i个元素,i的合法值为1<=i<=length
        void ListDelete(int i) {
            if (i < 1 || i > length)
                return;                         //i值不合法
            ElemType *p = &elem[i - 1];         //p为被删除元素的位置
            ElemType *q = &elem[length - 1];    //表尾元素的位置
            for (++p; p <= q; ++p)
                *(p - 1) = *p;                  //被删除元素之后的元素左移
            --length;                         //表长减1
        }
    };
    展开全文
  • (1)问题描述 设计一个“学生成绩管理系统”。主要实现学生信息的录入、添加、修改、删除、排序和查看等基本功能。 (2)设计要求 编写一个学生成绩管理程序。学生成绩以一个学生一条记录的形式存储,每个学生...
  • 数据结构详解——线性表C++实现)

    万次阅读 多人点赞 2018-03-11 15:46:00
    线性表   线性表是最常用且是最简单的一种数据结构。形如:A1、A2、A3….An这样含有有限的数据序列,我们就称之为线性表线性表 一、线性表的定义 二、线性表的抽象数据类型 三、线性表的顺序存储 1. 顺序...

    线性表

      线性表是最常用且是最简单的一种数据结构。形如:A1、A2、A3….An这样含有有限的数据序列,我们就称之为线性表。

    一、线性表的定义

    线性表:零个或多个数据元素的有限序列。

    线性表、包括顺序表和链表
    顺序表(其实就是数组)里面元素的地址是连续的,
    链表里面节点的地址不是连续的,是通过指针连起来的。

    二、线性表的抽象数据类型

      线性表的抽象数据类型定义如下:

    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):在线性表的第i个位置插入元素e。
        ListDelete(*L,i,*e):删除线性表L中的第i个元素,并用e返回其值
        ListLength(L):返回线性表L的元素个数。
        PrintList(L):打印线性表
    
    对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的。
    对于实际问题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。

    三、线性表的顺序存储

    1. 顺序存储定义

      顺序表,一般使用数组实现,事实上就是在内存中找个初始地址,然后通过占位的形式,把一定连续的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中,数组大小有两种方式指定,一是静态分配,二是动态扩展。

      顺序表相关的操作跟数组有关,一般都是移动数组元素。
    这里写图片描述

    2. 顺序存储的实现方式

    结构

      我们直接来看顺序表的模板类的代码:

    const int MaxSize = 100;
    template <class DataType>
    class SeqList
    {
    public:
        SeqList(){length=0;}            //无参数构造方法
        SeqList(DataType a[],int n);    //有参数构造方法
        ~SeqList(){}                    //析构函数
        int Length(){return length;}    //线性表长度
        DataType Get(int i);            //按位查找
        int Locate(DataType x);         //按值查找
        void Insert(int i,DataType x);  //插入
        DataType Delete(int i);         //删除
        void PrintList();               //遍历
    private:
        DataType data[MaxSize];         //顺序表使用数组实现
        int length;                     //存储顺序表的长度
    };

    顺序表的封装需要三个属性:

    1. 存储空间的起始位置。数组data的存储位置就是线性表存储空间的存储位置
    2. 线性表的最大存储容量。数组长度MAXSIZE
    3. 线性表的当前长度。length

    注意:数组的长度与线性表的当前长度是不一样的。数组的长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会改变的。

      下面我们将实现顺序表的各个功能:

    有参数构造

      创建一个长度为n的顺序表,需要将给定的数组元素作为线性表的数据元素传入顺序表中,并将传入的元素个数作为顺序表的长度
    这里写图片描述

    template <class DataType>
    SeqList<DataType>::SeqList(DataType a[],int n)
    {
        if(n>MaxSize) throw "wrong parameter";
        for(int i=0;i<n;i++)
            data[i]=a[i];
        length=n;
    }

    按位查找

      按位查找的时间复杂度为 O(1) O ( 1 )

    template <class DataType>
    DataType SeqList<DataType>::Get(int i)
    {
        if(i<1 && i>length) throw "wrong Location";
        else return data[i-1];
    }

    按值查找

      按值查找,需要对顺序表中的元素依次进行比较。

    template <class DataType>
    int SeqList<DataType>::Locate(DataType x)
    {
        for(int i=0;i<length;i++)
            if(data[i]==x) return i+1;
        return 0;
    }

    插入

      插入的过程中需要注意元素移动的方向,必须从最后一个元素开始移动,如果表满了,则引发上溢;如果插入位置不合理,则引发位置异常。
    这里写图片描述

    template <class DataType>
    void SeqList<DataType>::Insert(int i,DataType x)
    {
        if(length>=MaxSize) throw "Overflow";
        if(i<1 || i>length+1) throw "Location";
        for(int j=length;j>=i;j--)
            data[j]=data[j-1];
        data[i-1]=x;
        length++;
    }

    删除

      注意算法中元素移动方向,移动元素之前必须取出被删的元素,如果表为空则发生下溢,如果删除位置不合理,则引发删除位置异常。·
    这里写图片描述

    template <class DataType>
    DataType SeqList<DataType>::Delete(int i)
    {
        int x;
        if(length==0) throw "Underflow";
        if(i<1 || i>length) throw "Location";
        x = data[i-1];
        for(int j=i;j<length;j++)
            data[j-1] = data[j];
        length--;
        return x;
    }

    遍历

      按下标依次输出各元素

    template <class DataType>
    void SeqList<DataType>::PrintList()
    {
        for(int i=0;i<length;i++)
            cout<<data[i]<<endl;
    }

      完整代码示例(更多数据结构完整示例可见GitHub):

    #include<iostream>
    using namespace std;
    
    const int MaxSize = 100;
    template <class DataType>
    class SeqList
    {
    public:
        SeqList(){length=0;}            
        SeqList(DataType a[],int n);    
        ~SeqList(){}                    
        int Length(){return length;}    
        DataType Get(int i);            
        int Locate(DataType x);         
        void Insert(int i,DataType x);  
        DataType Delete(int i);         
        void PrintList();               
    private:
        DataType data[MaxSize];         
        int length;                     
    };
    
    template <class DataType>
    SeqList<DataType>::SeqList(DataType a[],int n)
    {
        if(n>MaxSize) throw "wrong parameter";
        for(int i=0;i<n;i++)
            data[i]=a[i];
        length=n;
    }
    
    template <class DataType>
    DataType SeqList<DataType>::Get(int i)
    {
        if(i<1 && i>length) throw "wrong Location";
        else return data[i-1];
    }
    
    template <class DataType>
    int SeqList<DataType>::Locate(DataType x)
    {
        for(int i=0;i<length;i++)
            if(data[i]==x) return i+1;
        return 0;
    }
    
    template <class DataType>
    void SeqList<DataType>::Insert(int i,DataType x)
    {
        if(length>=MaxSize) throw "Overflow";
        if(i<1 || i>length+1) throw "Location";
        for(int j=length;j>=i;j--)
            data[j]=data[j-1];
        data[i-1]=x;
        length++;
    }
    
    template <class DataType>
    DataType SeqList<DataType>::Delete(int i)
    {
        int x;
        if(length==0) throw "Underflow";
        if(i<1 || i>length) throw "Location";
        x = data[i-1];
        for(int j=i;j<length;j++)
            data[j-1] = data[j];
        length--;
        return x;
    }
    
    template <class DataType>
    void SeqList<DataType>::PrintList()
    {
        for(int i=0;i<length;i++)
            cout<<data[i]<<endl;
    }
    
    int main()
    {
        SeqList<int> p;
        p.Insert(1,5);
        p.Insert(2,9);
        p.PrintList();
        p.Insert(2,3);
        cout<<p.Length()<<endl;
        p.PrintList();
        cout<<p.Get(3)<<endl;
        p.Delete(2);
        p.PrintList();
        return 0;
    }

    3. 顺序存储的优缺点

    优点:

    • 随机访问特性,查找O(1)时间,存储密度高;
    • 逻辑上相邻的元素,物理上也相邻;
    • 无须为表中元素之间的逻辑关系而增加额外的存储空间;

    缺点:

    • 插入和删除需移动大量元素;
    • 当线性表长度变化较大时,难以确定存储空间的容量;
    • 造成存储空间的“碎片”

    四、线性表的链式存储

    1. 链式存储定义

      线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些元素可以存在内存未被占用的任意位置。
    这里写图片描述

      链表的定义是递归的,它或者为空null,或者指向另一个节点node的引用,这个节点含有下一个节点或链表的引用,线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)。
    这里写图片描述

    2. 链式存储的实现方式

    存储方法

    template<class DataType>
    struct Node
    {
        DataType data;              //存储数据
        Node<DataType> *next;       //存储下一个结点的地址
    };

      结点由存放数据元素的数据域和存放后继结点地址的指针域组成。
    这里写图片描述

    结构

      单链表的模板类的代码:

    template<class DataType>
    class LinkList
    {
    public:
        LinkList();                     
        LinkList(DataType a[], int n);  
        ~LinkList();                    
        int Length();                   
        DataType Get(int i);            
        int Locate(DataType x);         
        void Insert(int i, DataType x); 
        DataType Delete(int i);         
        void PrintList();               
    private:
        Node<DataType> *first;          
    };

    特点

    • 用一组任意的存储单元存储线性表的数据元素, 这组存储单元可以存在内存中未被占用的任意位置
    • 顺序存储结构每个数据元素只需要存储一个位置就可以了,而链式存储结构中,除了要存储数据信息外,还要存储它的后继元素的存储地址

    无参数构造

      生成只有头结点的空链表

    template<class DataType>
    LinkList<DataType>::LinkList()
    {
        first = new Node<DataType>;
        first->next = NULL;
    }

    头插法构造单链表

      头插法是每次将新申请的结点插在头结点后面
    这里写图片描述

    template<class DataType>
    LinkList<DataType>::LinkList(DataType a[], int n)
    {
        first = new Node<DataType>;
        first->next = NULL;
        for (int i = 0; i < n; i++)
        {
            Node<DataType> *s = new Node<DataType>;
            s->data = a[i];
            s->next = first->next;
            first->next = s;
        }
    }

    尾插法构造单链表

      尾插法就是每次将新申请的结点插在终端节点的后面
    这里写图片描述

    template<class DataType>
    LinkList<DataType>::LinkList(DataType a[], int n)
    {
        first = new Node<DataType>;
        Node<DataType> *r = first;
        for (int i = 0; i < n; i++)
        {
            Node<DataType> *s = new Node<DataType>;
            s->data = a[i];
            r->next = s;
            r = s;
        }
        r->next = NULL;
    }

    析构函数

      单链表类中的结点是用new申请的,在释放的时候无法自动释放,所以,析构函数要将单链表中的结点空间释放

    template<class DataType>
    LinkList<DataType>::~LinkList()
    {
        while (first != NULL)
        {
            Node<DataType>* q = first;
            first = first->next;
            delete q;
        }
    }

    计算长度

      单链表中不能直接求出长度,所以我们只能将单链表扫描一遍,所以时间复杂度为 O(n) O ( n )
    这里写图片描述

    template<class DataType>
    int LinkList<DataType>::Length()
    {
        Node<DataType>* p = first->next;
        int count = 0;
        while (p != NULL)
        {
            p = p->next;
            count++;
        }
        return count;
    }

    按位查找

      单链表中即使知道节点位置也不能直接访问,需要从头指针开始逐个节点向下搜索,平均时间性能为 O(n) O ( n ) ,单链表是顺序存取结构

    template<class DataType>
    DataType LinkList<DataType>::Get(int i)
    {
        Node<DataType>* p = first->next;
        int count = 1;
        while (p != NULL && count<i)
        {
            p = p->next;
            count++;
        }
        if (p == NULL) throw "Location";
        else return p->data;
    }

    按值查找

      单链表中按值查找与顺序表中的实现方法类似,对链表中的元素依次进行比较,平均时间性能为 O(n) O ( n ) .

    template<class DataType>
    int LinkList<DataType>::Locate(DataType x)
    {
        Node<DataType> *p = first->next;
        int count = 1;
        while (p != NULL)
        {
            if (p->data == x) return count;
            p = p->next;
            count++;
        }
        return 0;
    }

    插入

      单链表在插入过程中需要注意分析在表头、表中间、表尾的三种情况,由于单链表带头结点,这三种情况的操作语句一致,不用特殊处理,时间复杂度为 O(n) O ( n )
    这里写图片描述

    template<class DataType>
    void LinkList<DataType>::Insert(int i, DataType x)
    {
        Node<DataType> *p = first;
        int count = 0;
        while (p != NULL && count<i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL) throw "Location";
        else {
            Node<DataType> *s = new Node<DataType>;
            s->data = x;
            s->next = p->next;
            p->next = s;
        }
    }

    删除

      删除操作时需要注意表尾的特殊情况,此时虽然被删结点不存在,但其前驱结点却存在。因此仅当被删结点的前驱结点存在且不是终端节点时,才能确定被删节点存在,时间复杂度为 O(n) O ( n ) .
    这里写图片描述

    template<class DataType>
    DataType LinkList<DataType>::Delete(int i)
    {
        Node<DataType> *p = first;
        int count = 0;
        while (p != NULL && count<i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL || p->next == NULL) throw "Location";
        else {
            Node<DataType> *q = p->next;
            int x = q->data;
            p->next = q->next;
            return x;
        }
    }

    遍历

      遍历单链表时间复杂度为 O(n) O ( n ) .
    这里写图片描述

    template<class DataType>
    void LinkList<DataType>::PrintList()
    {
        Node<DataType> *p = first->next;
        while (p != NULL)
        {
            cout << p->data << endl;
            p = p->next;
        }
    }

      完整代码示例(更多数据结构完整示例可见GitHub):

    #include<iostream>
    using namespace std;
    
    template<class DataType>
    struct Node
    {
        DataType data;
        Node<DataType> *next;
    };
    
    template<class DataType>
    class LinkList
    {
    public:
        LinkList();                     
        LinkList(DataType a[], int n);  
        ~LinkList();                    
        int Length();                   
        DataType Get(int i);            
        int Locate(DataType x);         
        void Insert(int i, DataType x); 
        DataType Delete(int i);         
        void PrintList();               
    private:
        Node<DataType> *first;          
    };
    
    template<class DataType>
    LinkList<DataType>::LinkList()
    {
        first = new Node<DataType>;
        first->next = NULL;
    }
    
    template<class DataType>
    LinkList<DataType>::LinkList(DataType a[], int n)
    {
        first = new Node<DataType>;
        first->next = NULL;
        for (int i = 0; i < n; i++)
        {
            Node<DataType> *s = new Node<DataType>;
            s->data = a[i];
            s->next = first->next;
            first->next = s;
        }
    }
    
    template<class DataType>
    LinkList<DataType>::~LinkList()
    {
        while (first != NULL)
        {
            Node<DataType>* q = first;
            first = first->next;
            delete q;
        }
    }
    
    template<class DataType>
    int LinkList<DataType>::Length()
    {
        Node<DataType>* p = first->next;
        int count = 0;
        while (p != NULL)
        {
            p = p->next;
            count++;
        }
        return count;
    }
    
    template<class DataType>
    DataType LinkList<DataType>::Get(int i)
    {
        Node<DataType>* p = first->next;
        int count = 1;
        while (p != NULL && count<i)
        {
            p = p->next;
            count++;
        }
        if (p == NULL) throw "Location";
        else return p->data;
    }
    
    template<class DataType>
    int LinkList<DataType>::Locate(DataType x)
    {
        Node<DataType> *p = first->next;
        int count = 1;
        while (p != NULL)
        {
            if (p->data == x) return count;
            p = p->next;
            count++;
        }
        return 0;
    }
    
    template<class DataType>
    void LinkList<DataType>::Insert(int i, DataType x)
    {
        Node<DataType> *p = first;
        int count = 0;
        while (p != NULL && count<i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL) throw "Location";
        else {
            Node<DataType> *s = new Node<DataType>;
            s->data = x;
            s->next = p->next;
            p->next = s;
        }
    }
    
    template<class DataType>
    DataType LinkList<DataType>::Delete(int i)
    {
        Node<DataType> *p = first;
        int count = 0;
        while (p != NULL && count<i - 1)
        {
            p = p->next;
            count++;
        }
        if (p == NULL || p->next == NULL) throw "Location";
        else {
            Node<DataType> *q = p->next;
            int x = q->data;
            p->next = q->next;
            return x;
        }
    }
    
    template<class DataType>
    void LinkList<DataType>::PrintList()
    {
        Node<DataType> *p = first->next;
        while (p != NULL)
        {
            cout << p->data << endl;
            p = p->next;
        }
    }
    
    int main()
    {
        LinkList<int> p;
        p.Insert(1, 6);
        p.Insert(2, 9);
        p.PrintList();
        p.Insert(2, 3);
        p.PrintList();
        cout << p.Get(2) << endl;
        cout << p.Locate(9) << endl;
        cout << p.Length() << endl;
        p.Delete(1);
        p.PrintList();
        return 0;
    }

    链式存储的优缺点

    优点

    1. 插入、删除不需移动其他元素,只需改变指针.
    2. 链表各个节点在内存中空间不要求连续,空间利用率高

    缺点

    1. 查找需要遍历操作,比较麻烦

    五、其他线性表

    循环链表

      循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。(通常为了使空表和非空表的处理一致,通常也附加一个头结点)
    这里写图片描述

      在很多实际问题中,一般都使用尾指针来指示循环链表,因为使用尾指针查找开始结点和终端结点都很方便。
    这里写图片描述

      循环链表没有增加任何存储量,仅对链接方式稍作改变,循环链表仅在循环条件与单链表不同。从循环链表的任一结点出发可扫描到其他结点,增加了灵活性。但是,由于循环链表没有明显的尾端,所以链表操作有进入死循环的危险。通常以判断指针是否等于某一指定指针来判定是否扫描了整个循环链表。

    双链表

      循环链表虽然可以从任意结点出发扫描其他结点,但是如果要查找其前驱结点,则需遍历整个循环链表。为了快速确定任意结点的前驱结点,可以再每个节点中再设置一个指向前驱结点的指针域,这样就形成了双链表

    这里写图片描述

    存储方法

    template<class DataType>
    struct Node
    {
        DataType data;
        Node<DataType> *prior,*next;
    };

      结点p的地址既存储在其前驱结点的后继指针域内,又存储在它后继结点的前驱指针域中

    需要注意:

    1. 循环双链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同。
    2. 插入操作需要修改4个指针,并且要注意修改的相对顺序。

    静态链表

      静态链表是用数组来表示单链表,用数组元素的下标来模拟单链表的指针。

    静态链表的存储结构

    const int MaxSize = 100;
    template<class DataType>
    struct Node{
        DataType data;
        int next;
    }SList[MaxSize];

    静态链表存储示意图
    这里写图片描述

    静态链表插入操作示意图
    这里写图片描述

    静态链表删除操作示意图
    这里写图片描述

      静态链表虽然是用数组来存储线性表的元素,但在插入和删除操作时,只需要修改游标,不需要移动表中的元素,从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点,但是它并没有解决连续存储分配带来的表长难以确定的问题。

    间接寻址

      间接寻址是将数组和指针结合起来的一种方法,它将数组中存储的单元改为存储指向该元素的指针。
    这里写图片描述

      该算法的时间复杂度仍为

    O(n) O ( n )
    ,但当每个元素占用较大空间时,比顺序表的插入快的多。线性表的间接寻址保持了顺序表随机存取的优点,同时改进了插入和删除操作的时间性能,但是它也没有解决连续存储分配带来的表长难以确定的问题。

      具体代码实现均可在GitHub中找到。如有错误,请在评论区指正。

    参考

    • 数据结构(C++版)王红梅等编著
    展开全文
  • 顺序表 函数声明 List.h(顺序表的定义,各项功能和...//创建线性表 ~List();//销毁线性表 void ClearList();//清空线性宝 bool ListEmpty();//判断线性表是否为空 int ListLengh();//获取线性表的长度 bool GetE

    顺序表

    函数声明 List.h(顺序表的定义,各项功能和变量)

    #pragma once
    #define Elem int
    
    class List
    {
    public:
    	List(int size);//创建线性表
    	~List();//销毁线性表
    	void ClearList();//清空线性宝
    	bool ListEmpty();//判断线性表是否为空
    	int ListLengh();//获取线性表的长度
    	bool GetElem(int i, Elem* e);//获取位置i的元素(i就是下标)
    	int LocateElem(Elem* e);//获取元素值等于e的元素的位置
    
    	bool PreElem(Elem* currentElem, Elem* preElem);//获取指定元素的前驱	
    	bool NextElem(int* currentElem, int* nextElem);//获取指定元素的后继
    	void ListTravel();//遍历
    	bool ListInsert(int i, int* e);//在位置i插入元素e
    	bool ListDelete(int i, int* e);//删除位置i的元素,并将值记录到e
    private:
    	int* m_plist;
    	int m_iSize;
    	int m_iLength;
    };
    

    函数实现

    #include"List.h"
    #include<iostream>
    using namespace std;
    
    List::List(int size)
    {
    	m_iSize = size;
    	m_plist = new int[m_iSize];
    	m_iLength = 0;
    }
    List::~List()
    {
    	delete[]m_plist;
    	m_plist = NULL;
    }
    void List::ClearList()
    {
    	m_iLength = 0;
    }
    bool List::ListEmpty()
    {
    	if (m_iLength == 0)
    		return true;
    	else
    		return false;
    }
    int List::ListLengh()
    {
    	return m_iLength;
    }
    bool List::GetElem(int i, Elem* e)
    {
    	if (i<0 || i>=m_iSize)
    	{
    		return false;
    	}
    	else
    		*e = m_plist[i];
    	return true;
    }
    int List::LocateElem(Elem* e)
    {
    	for (int i = 0; i < m_iLength; i++)
    	{
    		if (m_plist[i] == *e)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    bool List::PreElem(Elem* currentElem, Elem* preElem)
    {
    	int temp = LocateElem(currentElem);
    	if (temp == -1)//没有指定元素时LocateElem()返回-1
    	{
    		return false;
    	}
    	else
    	{
    		if (temp == 0)	return false;//第一个元素(0号位置)没有前驱
    		else {
    			*preElem = m_plist[temp - 1];
    		}
    	}
    }
    bool List::NextElem(int* currentElem, int* nextElem)
    {
    	int temp = LocateElem(currentElem);
    	if (temp == -1)
    	{
    		return false;
    	}
    	else
    	{
    		if (temp == m_iLength - 1)	return false;//最后一个元素(位置为m_iLength-1)没有后继
    		else {
    			*nextElem = m_plist[temp + 1];
    		}
    	}
    
    }
    void List::ListTravel()
    {
    	for (int i = 0; i < m_iLength; i++)
    	{
    		cout << m_plist[i];
    	}
    }
    bool List::ListInsert(int i, int* e)
    {
    	if (i<0 || i>m_iLength)	return false;//i=m_iLength,插入末尾。i=0插在头部
    
    	for (int k = m_iLength - 1; k >= i; k--)
    	{
    		//从最后一个元素开始往后挪,把i号位置空出来
    		m_plist[k + 1] = m_plist[k];
    	}
    	m_plist[i] = *e;
    	m_iLength++;
    	return true;
    }
    bool List::ListDelete(int i, int* e)
    {
    	if (i < 0 || i >= m_iLength)	return false;
    	*e = m_plist[i];
    	for (int k = i; k < m_iLength - 1; k++)
    	{
    		m_plist[k] = m_plist[k + 1];
    	}
    }
    

    链表

    定义结点Node

    #pragma once
    
    
    class Node
    {
    public:
    	int date;
    	Node* next;
    	void printNode(){
    	cout<<this->date<<endl;
    	}
    };
    

    函数声明

    
    #ifndef LIST_H
    #define LIST_H
    
    #include"Node.h"
    class List
    {
    public:
    	List();//创建线性表
    	~List();//销毁线性表
    	void ClearList();//清空线性表
    	bool ListEmpty();//判断线性表是否为空,空返回true
    	int ListLength();//获取线性表的长度
    	bool GetElem(int i, Node* pNode);//获取指定位置i的元素
    	int LocateElem(Node* pNode);//获取某个元素的位置
    	bool PreElem(Node* pCurrentNode, Node* pPreNode);//获取某个元素的前驱
    	bool NextElem(Node* pCurrentNode, Node* pNextNode);//获取某个元素的后继
    	void ListTraval();//遍历链表
    	bool ListInsert(int i, Node* pNode);//插入结点
    	bool ListDelete(int i, Node* pNode);//删除结点
    	bool ListInsertHead(Node* pNode);//在头部插入结点
    	bool ListInsertTail(Node* pNode);//在末尾插入结点
    private:
    	Node* m_plist;
    	//int m_iSize;//链表用不到
    	int m_iLength;
    };
    #endif
    

    功能实现

    #include"List.h"
    #include<iostream>
    using namespace std;
    
    List::List()
    {
    	m_plist = new Node;
    	m_plist->date = 0;
    	m_plist->next = NULL;
    	m_iLength = 0;//第一个节点不算在当前的链表当中(空的头结点)
    }
    List::~List()
    {//释放所有节点
    	ClearList();
    	delete m_plist;
    	m_plist = NULL;
    }
    void List::ClearList()
    {//释放除头节点外的其他结点
    	Node* currentNode= m_plist->next;
    	while (currentNode != NULL)
    	{//释放当前结点,currentNode指向下一个结点
    		Node* temp = currentNode->next;
    		delete currentNode;
    		currentNode = temp;
    	}
    	m_plist->next = NULL;
    }
    bool List::ListEmpty()
    {
    	if (m_iLength == 0)	return true;
    	else return false;
    }
    int List::ListLength()
    {
    	return m_iLength;
    }
    bool List::ListInsertHead(Node* pNode)
    {
    	Node* temp=m_plist->next;
    	Node* newNode = new Node;
    	if (newNode == NULL)	return false;
    	newNode->date = pNode->date;
    	m_plist->next = newNode;//如果没用temp保存m_plist->next地址的话
    	newNode->next = temp;//需要换一下这两句的顺序
    	/*newNode->next=m_plist->next; m_plist->next=newNode*/
    	m_iLength++;
    	return true;
    }
    bool List::ListInsertTail(Node* pNode)
    {
    	Node* currentNode = m_plist;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    	}//调出while循环,此时的currentNode就是最后一个结点
    	Node* newNode = new Node;
    	if (newNode == NULL)	return false;
    	newNode->date = pNode->date;
    	newNode->next = NULL;
    	currentNode->next = newNode;
    	m_iLength++;
    	return true;
    }
    bool List::ListInsert(int i, Node* pNode)
    {//i=0插在头部,i=m_iLength插在尾部
    	if (i<0 || i>m_iLength)	return false;
    	Node* currentNode = m_plist;
    	for (int k = 0; k < i; k++)
    	{
    		currentNode = currentNode->next;
    	}//pNoide插在current Node之后(currentNode是待插入结点的前驱)
    	Node* newNode = new Node;
    	if (newNode == NULL) return false;
    	newNode->date = pNode->date;
    	newNode->next = currentNode->next;
    	currentNode->next = newNode;//这两句不能调换
    	return true;
    
    }
    bool List::ListDelete(int i, Node* pNode)
    {
    	if (i < 0 || i >= m_iLength)	return false;//
    	Node* currentNode = m_plist;
    	Node* currentNodeBefore = NULL;//需要找到上一个结点的前驱结点
    	for (int k = 0; k <= i; k++)
    	{
    		//currentNode 就是待删除结点
    		currentNodeBefore = currentNode;
    		currentNode = currentNode->next;
    	}
    	currentNodeBefore->next = currentNode->next;
    	pNode->date = currentNode->date;
    	delete currentNode;
    	currentNode = NULL;
    	m_iLength--;
    	return true;
    }
    bool List::GetElem(int i,Node* pNode)
    {
    	if (i<0 || i>m_iLength)	return false;
    	Node* currentNode = m_plist;//头结点
    	Node* currentNodeBefore = NULL;
    	for (int k = 0; k <= i; k++)//头结点的下一个结点才是第0号结点
    	{
    		currentNodeBefore = currentNode;
    		currentNode = currentNode->next;
    	}
    	pNode->date = currentNode->date;
    	return true;
    }
    int List::LocateElem(Node* pNode)
    {
    	Node* currentNode = m_plist;
    	int count = 0;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    		if (currentNode->date == pNode->date)
    		{
    			return count;
    		}
    		count++;
    	}//0 是head后的第一个结点
    	return -1;//没找到
    }
    bool List::PreElem(Node* pCurrentNode,Node* pPreNode)
    {
    	Node* currentNode = m_plist;
    	Node* tempNode = NULL;//currentNode 的前驱
    	while (currentNode->next != NULL)
    	{
    		tempNode = currentNode;
    		currentNode = currentNode->next;
    		if (currentNode->date == pCurrentNode->date)
    		{
    			if (tempNode == m_plist)	return false;
    			pPreNode->date = tempNode->date;
    			return true;
    		}
    	}
    	return false;
    }
    bool List::NextElem(Node* pCurrentNode, Node* pNextNode)
    {
    	Node* currentNode = m_plist;
    	while (currentNode->next!=NULL)
    	{
    		currentNode = currentNode->next;
    		if (currentNode->date == pCurrentNode->date)
    		{
    			if (currentNode->next == NULL)	return false;
    			pNextNode->date = currentNode->next->date;
    			return true;
    		}
    	}
    	return false;
    }
    void List::ListTraval()
    {
    	Node* currentNode = m_plist;
    	while (currentNode->next != NULL)
    	{
    		currentNode = currentNode->next;
    		currentNode->printNode();
    		//cout<<currentNode->date<<endl;
    	}
    }
    
    展开全文
  • 线性表C++实现

    千次阅读 2017-08-24 22:24:09
    线性表的分类:  以下是数据结构中顺序表的C++实现,如有需要,请访问我的Github获取完整源码。   //线性表类的定义 class List { public: List(int size); //创建线性表 ~List();

    线性表的分类:

    这里写图片描述

    以下是数据结构中顺序表的C++实现,如有需要,请访问我的Github获取完整源码。

    //线性表类的定义
    class List
    {
    public:
        List(int size);                                   //创建线性表
        ~List();                                          //释放空间
        void ClearList();                                 //清空线性表
        bool ListEmpty();                                 //线性表判空
        int ListLength();                                 //获取当前线性表的长度
        bool GetElem(int i, int *e);                      //获取第i个元素,放入e中
        int LocateElem(int *e);                           //获取值等于e的元素的位置
        bool PriorElem(int *currentElem, int *preElem);   //获取指定元素的前驱
        bool NextElem(int *currentElem, int *nextElem);   //获取指定元素的后继
        bool ListInsert(int i, int *e);                   //在第i个位置插入元素
        bool ListDelete(int i, int *e);                   //删除第i个位置的元素
        void ListTraverse(); 
    
    private:
        int *m_pList;                                     //指向存储线性表的内存
        int m_iSize;                                      //线性表大小
        int m_iLength;                                    //当前线性表长度
    };
    
    //类中各成员函数的实现
    #include"List.h"
    #include<iostream>
    using namespace std;
    
    List::List(int size)
    {
        m_iSize = size;
        //申请空间
        m_pList = new int[m_iSize];                                                
        m_iLength = 0;
    }
    
    List::~List()
    {
        delete []m_pList;
        m_pList = NULL;
    }
    
    void List::ClearList()
    {
        m_iLength = 0;
    }
    
    bool List::ListEmpty()
    {
        if(m_iLength == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    
    int List::ListLength()
    {
        return m_iLength;
    }
    
    //获取第i个元素的值存入e中
    bool List::GetElem(int i, int *e)
    {
        if(i < 0 || i >= m_iSize)
            return false;
        *e = m_pList[i];
        return true;
    }
    
    //确定值为e的元素的位置,找不到位置返回-1
    int List::LocateElem(int *e)
    {
        for(int i = 0; i < m_iLength; i++)
        {
            if(m_pList[i] == *e)
            {
                return i;
            }
        }
        return -1;
    }
    
    //获取当前元素的前驱
    bool List::PriorElem(int *currentElem, int *preElem)
    {
        //先确定当前元素的位置
        int temp = LocateElem(currentElem);
        if(temp == -1)
        {
            return false;
        }
        else if(temp == 0)
        {
            return false;
        }
        else
        {
            *preElem = m_pList[temp - 1];
            return true;
        }
    }
    
    //获取当前元素的后继
     bool List::NextElem(int *currentElem, int *nextElem)
     {
         int temp = LocateElem(currentElem);
         if(temp == -1)
         {
             return false;
         }
         else if(temp == m_iLength - 1)
         {
             return false;
         }
         else
         {
             *nextElem = m_pList[temp + 1];
             return true;
         }
     }
    
     //在第i个位置插入元素,第i个位置之后的元素全部后移
     bool List::ListInsert(int i, int *e)
     {
         if(i < 0 ||i > m_iLength)
         {
             return false;
         }
    
         for(int k = m_iLength - 1; k >= i; k--)
         {
             m_pList[k + 1] = m_pList[k];
         }
         m_pList[i] = *e;
    
         m_iLength ++;
         return true;
     }
    
     //删除第i个位置的元素,第i 个位置的元素全部前移
     bool List::ListDelete(int i, int *e)
     {
         if(i < 0 || i >= m_iLength)
         {
             return false;
         }
    
         *e = m_pList[i];
         for(int k = i + 1; k < m_iLength; k++)
         {
             m_pList[k - 1] = m_pList[k];
         }
    
         m_iLength--;
         return true;
     }
    
     void List::ListTraverse()
     {
         for(int i = 0; i < m_iLength; i++)
         {
             cout << m_pList[i] << " ";
         }
         cout << endl;
     }
    
    展开全文
  • C++线性表

    2020-08-12 22:48:44
    C++线性表(arrayList) 线性表根据存储方式分为:顺序存储(数组描述)、链式存储(链表描述) 线性表的抽象类(常用的API): 判断是否为空; 返回元素个数; 返回索引元素; 返回指定元素第一次出现的索引值; ...
  • 顺序线性表-C++实现

    2020-07-28 19:13:05
    顺序线性表-C++实现 1 #include <iostream> 2 using namespace std; 3 4 #define MAXSIZE 100 5 typedef int ElemType; 6 7 class SqList { 8 ElemType data[MAXSIZE]; 9 unsigned int length; 10...
  • 线性表c++代码)

    2018-03-14 22:26:38
    数据结构:线性表的创建、插入、查找、删除 vector的简单应用
  • 数据机构 线性表 c++/c

    2011-10-05 16:52:31
    数据机构 线性表 c++/c 学 习 之 用
  • C++编写线性表

    2019-10-27 22:32:54
    数据结构:用C++编写顺序表 ...采用顺序存储结构存储的线性表。 元素的追加只需要在尾部处增加一个地址,顺序表的长度增大一,把值赋给该地址。 元素的插入稍微复杂一点,要先判断插入的位置...
  • 栈是一种特殊的线性表,其插入(也称为入栈或压栈)和删除(也称为弹出或出栈)操作都在表的同一端进行;该插入和删除的端口称为栈顶(top),另一端称为栈底(bottom)。 1.2栈的基本运算 1.2.1基本运算 (1) 初始化...
  • 构造栈3.c++模板实现3.1 节点的数据结构3.2 用模板类构造一个简单的stack类 1.基本概念 栈中的元素遵守“先进后出”的原则(LIFO,Last In First Out) 只能在栈顶进行插入和删除操作 压栈(或推入、进栈)即push,将...
  • 主要介绍了C++ 数据结构线性表-数组实现的相关资料,需要的朋友可以参考下
  • 主要介绍了C++语言实现线性表之链表,实例分析了C++实现线性表中链表的原理与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • C++语言实现线性表

    2020-04-20 19:51:45
    //返回线性表的大小 bool full() const; //判满 bool empty() const; //判空 void clear(); //清空 void traverse(void (*visit)(List_entry &)); //遍历 Error_code retrieve(int position, List_entry &x) const;...
  • int SeqList<type>::GetLength()const//求线性表长度 { return len; } template type SeqList<type>::GetItem(int i)const//求第i个数据元素 { if (i >= 1 && i ) return data[i - 1]; else return NULL...
  • c++实现动态线性表

    2020-10-16 00:38:32
    #include<#iostream>//不知道为什么不加#后面显示不了,事实上正确的代码在<>...//线性表中每一个元素的组成成分 void increaseLinearList(L & linearList, int len); void initList
  • (1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中 表示这种关系有顺序存储结构和链式存储结构; (2)掌握这两种存储结构的描述方法; (3)掌握线性表的基本操作(查找、插入、删除); (4...
  • 线性表的是一个相当灵活的数据结构,它的长度可根据需要增长或缩短,即对线性表的数据元素不仅可以进行访问,还可进行插入和删除 线性表的特点: 插入方便 (优点) 空间利用率低 插入、删除麻烦 线性表的顺序表示 ...
  • 99koujuebiao,希望对你 有帮助
  • 线性表 线性表有两种存储方式:连续存储与链接存储。先更线性存储,连接存储待更。 线性表是由n个元素组成的有序序列。 连续存储 线性表的元素存储在一个表中,表的大小是固定的,大于或等于要表示的线性表的最大...
  • 线性表的合并C++实现

    千次阅读 2019-08-20 18:11:43
    // 将线性表L中的第i个位置元素返回给e Status GetElem(Sqlist L, int i, ElemType &e){ if (i || i > L.length) return ERROR; // 判断是否合理 e = L.elem[i-1]; // 第i-1的单元存储着第i个数据 return OK; } ...
  • Description请你定义一个线性表,可以对表进行“在某个位置之前插入一个元素”、“删除某个位置的元素”、“清除所有元素”、“获取某个位置的元素”等操作。键盘输入一些命令,可以执行上述操作。本题中,线性表...
  • 数据结构之C++实现合并线性表

    千次阅读 2018-06-22 14:20:28
    //归并两个线性表 //已知线性表La和Lb中的数据元素按值非递减排列 //归并La和Lb得到的新线性表Lc,Lc的数据元素也按值非递减排列 void mergeList(SqList La,SqList Lb,SqList &amp;Lc){ initList(Lc); int i=1;...
  • 链式线性表C++ 实现

    千次阅读 2015-07-29 14:33:10
    C++ 链式线性表 以类的方式实现 C++ 链式线性表 以类的方式实现 C++ 链式线性表 以类的方式实现
  • C++ 线性表之顺序表的构建

    千次阅读 2018-07-22 10:48:29
    (一)该顺序表下标从一开始,具有增删查等操作 实现如下: #include&lt;iostream&gt; using namespace std; const int maxSize = 100; class sqlist{ public: sqlist():length(0){} ... int insert(int ...
  • //成功删除返回1 } } 判断表是否为空 void EmptyList(Sqlist L)//判断表是否为空 { if(L.Length==0) cout线性表为空"; else cout线性表非空"; } int LengthList(Sqlist L)//求表长 { return L.Length; } void ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,226
精华内容 7,690
关键字:

线性表c++

c++ 订阅