精华内容
下载资源
问答
  • c++ 实现线性表 数组 #include <iostream> #include "stdlib.h" using namespace std; #define MAXSIZE 20 //设置存储空间初始分量 #define OK 1 #define ERROR 0 typedef int ElemType;//ElemType 相当与int ...
    `在这里插入代码片`# c++ 实现线性表_数组_链表_顺序存储结构_链式存储结构
    
    ## 数组
    
    ~~~c++
    #include <iostream>
    #include "stdlib.h"
    using namespace std;
    #define MAXSIZE 20 //设置存储空间初始分量
    #define OK 1
    #define ERROR 0
    typedef int ElemType;//ElemType 相当与int
    typedef int Status;
    class list1
    {
    public:
        list1();
        //~list1();
        Status GetElem(int i,ElemType &e); //获取
        Status ListInsert(int i,ElemType e);//插入
        Status show();
        Status ListDelete(int i,ElemType &e);//删除位置i的元素,并用e返回值
    private:
        ElemType data[MAXSIZE];
        int length;
    };
    //构造函数用于初始化
    list1::list1() {
        length = 0;
    }
    //获取指定位置元素的值
    Status list1::GetElem(int i,ElemType &e) {
        if(length==0||i<1||i>length) return ERROR;
        e=data[i-1];
        return 0;
    }
    //在数组指定位置插入元素
    Status list1::ListInsert(int i,ElemType e) {
        int k;
        if(length==MAXSIZE||i<1||i>length+1) //当数组满或者当要求插入位置小于1或者要求插入位置在数组最后以为后面时
            return ERROR;
        if(i<=length) {
            //将前面位置的元素均向后移动一位
            for(k=length-1;k>=i-1;k--) {
                data[k+1]=data[k];
            }
        }
        data[i-1]=e;
        length++;
        return OK;
    }
    //删除
    Status list1::ListDelete(int i,ElemType &e) {
        int k;
        if(length==0||i<1||i>length) {
            cout<<"ERROR"<<endl;
            return ERROR;
        }
        e = data[i-1];
        if(i<length) for(k=i;k<length;k++) data[k-1]=data[k];
        length--;
        return OK;
    }
    Status list1::show() {
        if(length == 0) {
            cout<<"data is empty"<<endl;
            return ERROR;
        }
        else {
            cout<<"length is "<<length<<endl;
            cout<<"data is ";
            for(int i=0;i<length;i++) cout<<data[i]<<"  ";
            cout<<endl;
            return OK;
        }
    }
    int main()
    {
        //构造函数用于初始化
        list1 q;
        q.show();
        //1.插入
        for(int i=0;i<=10;i++) q.ListInsert(i,i+1);
        q.show();
        /*q.ListInsert(1,22);
        q.show();*/
        //2.获取
        int e;
        q.GetElem(2,e);//使用了引用的方法
        cout<<"e is "<<e<<endl;
        //3.删除
        q.show();
        q.ListDelete(3,e);
        q.show();
        return 0;
    }
    ~~~
    
    ## 静态链表
    
    ~~~c++
    #include <iostream>
    using namespace std;
    #define MAXSIZE 1000 //假设链表的最大长度是1000
    struct Node
    {
        int data;
        int cur; 
    };
    class list3_oneself
    {
    public:
        list3_oneself();
        list3_oneself(int a[],int n);
        void show();//打印当前链表
        void show_real();//打印真实的顺序列表
        int length();//获当前链表长度
        void Insert(int n, int x);//在指定位置n前面插入元素x
        void Delete(int n);// 删除第i个节点
        int Get(int n);//获取指定位置的元素
        int Locate(int x);// 查找值为x的元素
    private:
        Node StaticLinkList[MAXSIZE];
    };
    list3_oneself::list3_oneself() {
        for(int i=0;i<MAXSIZE-1;i++) StaticLinkList[i].cur = i+1; 
        StaticLinkList[MAXSIZE-1].cur = 0;
    }
    list3_oneself::list3_oneself(int a[],int n) {
        for(int i=0;i<MAXSIZE-1;i++) StaticLinkList[i].cur = i+1; 
        for(int i=1;i<n+1;i++) StaticLinkList[i].data = a[i-1];
        StaticLinkList[0].cur = n+1;//头节点存放备用链表第一个节点的下标
        StaticLinkList[MAXSIZE-1].cur = 1;//数组尾节点存放第一个插入元素的下标
        StaticLinkList[n].cur=0;//下一个数据为空则用0表示
    }
    void list3_oneself::show() {
        int len = length();
        cout<<"StaticLinkList's length is "<<len<<endl;
        cout<<"StaticLinkList is ";
        int k=StaticLinkList[MAXSIZE-1].cur;
        for(int i=1;i<=len;i++) {
            cout<<StaticLinkList[k].data<<"  ";
            k=StaticLinkList[k].cur;
        }
        //cout<<endl<<"cur is "<<StaticLinkList[len].cur<<endl;
        cout<<endl;
    }
    void list3_oneself::show_real() {
        int len = length();
        cout<<"StaticLinkList's length is "<<len<<endl;
        cout<<"real StaticLinkList is ";
        for(int i=1;i<=len;i++) {
            cout<<StaticLinkList[i].data<<"  ";
        }
        //cout<<endl<<"cur is "<<StaticLinkList[len].cur<<endl;
        cout<<endl;
    }
    int list3_oneself::length() {
        int k=StaticLinkList[MAXSIZE-1].cur;
        int num=0;
        while(k) {
            k=StaticLinkList[k].cur;
            num++;
        }
        return num;
    }
    void list3_oneself::Insert(int m,int x) {
        if(m>length()+1 || m<1 || m>MAXSIZE-2) {
            cout<<"overstep the boundary!!!"<<endl;
            exit(1);
        }
        int Cur=StaticLinkList[0].cur;//找到备用链表的第一个节点的下标
        ++StaticLinkList[0].cur;//备用链表的下标+1
        StaticLinkList[Cur].data = x;//插入新节点
        int k=MAXSIZE-1;
        for(int i=1;i<m;i++) { //找到第m个位置之前的位置
            k=StaticLinkList[k].cur;
        }
        StaticLinkList[Cur].cur=StaticLinkList[k].cur;//第m个位置
        StaticLinkList[k].cur=Cur;//指向插入节点的下标
    }
    void list3_oneself::Delete(int m) {
        if(m>length() || m<1) {
            cout<<"overstep the boundary!!!"<<endl;
            exit(1);
        }
        int k=MAXSIZE-1;
        for(int i=1;i<m;i++) {
            k=StaticLinkList[k].cur;//找到第m个元素的下标
        }
        int Cur=StaticLinkList[k].cur;//当前元素的下标
        StaticLinkList[k].cur = StaticLinkList[Cur].cur;//前一个元素的下标指向下一个元素
        StaticLinkList[Cur].cur = StaticLinkList[0].cur;//当前位置元素的下一个元素的下标指向原备用链表的第一个元素的位置
        StaticLinkList[0].cur = Cur;//将删除的元素的位置加入备用链表
    }
    int main()
    {
        int arry[30];
        for(int i=0;i<30;i++) arry[i]=i;
        list3_oneself *StaticList = new list3_oneself(arry,30);
        StaticList->show();
        StaticList->Insert(1,100);
        StaticList->show();
        StaticList->Insert(32,101);
        StaticList->show();
        StaticList->show_real();
        StaticList->Delete(1);
        StaticList->show();
        StaticList->show_real();
    
        /*cout<<"StaticLinkList is ";
        for(int i=0;i<MAXSIZE;i++) {
            if(i%20==0) cout<<endl;
            cout<<StaticList.StaticLinkList[i].data<<"  ";
        }*/
        return 0;
    }
    ~~~
    
    ## 链式存储结构
    
    ~~~c++
    #include <iostream>
    using namespace std;
    // 单链表的节点
    template<class T> //加入模板
    struct Node
    {
        T data;//数据域
        Node<T> *next;// 指针域,指向后继节点
    };
    // 单链表的类实现
    template<class T>
    class LinkList
    {
    public:
        LinkList();// 无参构造函数,建立只有头节点的空链表
        LinkList(T a[],int n);// 有参构造函数,建立有n个元素的单链表
        ~LinkList();// 析构函数
        int Length();// 求单链表的长度
        T Get(int i);// 查找第i个元素
        int Locate(T x);// 查找值为x的元素
        void Insert(int i, T x);// 在第i个元素处插入x
        T Delete(int i);// 删除第i个节点
        void PrintList();// 遍历各个元素
    private:
        Node<T>* first;// 单链表的头节点
    };
    
    template<class T>
    inline LinkList<T>::LinkList()
    {
        first = new Node<T>;    // 生成头节点
        first->next = NULL;      // 头节点指针域为空
    }
    
    // 头插法建立单链表
    template<class T>
    LinkList<T>::LinkList(T a[], int n)
    {
        first = new Node<T>;
        first->next = NULL;        // 初始化一个空链表
        for (int i = 0; i < n; i++)
        {
            Node<T>* S = new Node<T>;
            S->data = a[i];        // 为每个数据元素建立一个节点
            S->next = first->next;
            first->next = S;    // 将节点S插入头节点之后
        }
    }
    // 尾插法建立单链表
    /*template<class T>
    LinkList<T>::LinkList(T a[], int n)
    {
        first = new Node<T>;// 建立头节点
        first->next = NULL;
        Node<T>* r = first;// 尾指针初始化
        for(int i = 0; i < n; i++)
        {
            Node<T>* S = new Node<T>;
            S->data = a[i];        // 为每个数据元素建立一个节点
            r->next = S;
            r = S;                // 插入节点S,并将尾指针指向S节点
        }
        r->next = NULL;            // 单链表建立完毕之后,将尾指针置空
    }*/
    
    template<class T>
    LinkList<T>::~LinkList()
    {
        while (first != NULL)
        {
            Node<T>* p = first;        // 暂存将被释放节点
            first = first->next;    // 指向下一个节点
            delete p;
        }
    }
    
    template<class T>
    int LinkList<T>::Length()
    {
        int count = 0;                // 计数
        Node<T>* p = first->next;    // 将工作指针指向第一个节点
        while (p != NULL)
        {
            count++;
            p = p->next;
        }
        return count;
    }
    
    template<class T>
    T LinkList<T>::Get(int i)
    {
        int count = 0;                // 计数
        Node<T>* p = first->next;    // 将工作指针指向第一个节点
        while (p != NULL)
        {
            count++;
            if (count == i)
                return p->data;
            p = p->next;
        }
        return -1;                    // 越界
    }
    
    template<class T>
    int LinkList<T>::Locate(T x)
    {
        int count = 0;                // 计数
        Node<T>* p = first->next;    // 将工作指针指向第一个节点
        while (p != NULL)
        {
            count++;
            if (p->data == x)
                return count;
            p = p->next;
        }
        return 0;                // 查找失败
    }
    
    template<class T>
    void LinkList<T>::Insert(int i, T x)
    {
        int count = 0;                // 计数
        Node<T>* p = first;            // 将工作指针指向头节点
        while (p != NULL)
        {
            if (count == i - 1)        // 找第i-1个节点
            {
                Node<T>* S = new Node<T>;
                S->data = x;
                S->next = p->next;
                p->next = S;
            }
            p = p->next;
            count++;
        }
        if (p == NULL)
            throw "位置越界";
    }
    
    template<class T>
    T LinkList<T>::Delete(int i)
    {
        int count = 0;                // 计数
        Node<T>* p = first;            // 将工作指针指向头节点
        while (p != NULL)
        {
            if (count == i - 1)
            {
                Node<T>* q = p->next;// 暂存被删节点
                T x = q->data;
                p->next = q->next;
                delete q;
                return x;
            }
            p = p->next;
            count++;
        }
        return -1;
    }
    
    template<class T>
    void LinkList<T>::PrintList()
    {
        Node<T>* p = first->next;    // 将工作指针指向第一个节点
        while (p != NULL)
        {
            cout << p->data << " ";
            p = p->next;
        }
    }
    int main()
    {
        int arry[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        LinkList<int>* linklist = new LinkList<int>(arry, 10);
        cout << linklist->Length() << endl;
        cout << linklist->Get(5) << endl;
        cout << linklist->Locate(6) << endl;
        linklist->Insert(3, 11);
        linklist->Delete(10);
        linklist->PrintList();
    
        //system("pause");
        return 0;
    }
    ~~~
    
    ### 链式存储结构
    
    ~~~c++
    #include <iostream>
    using namespace std;
    struct Node
    {
        int data;
        Node *next;
    };
    class list2_oneself
    {
    public:
        list2_oneself();
        list2_oneself(int a[],int n);
        //~list2_oneself();
        void PrintList();//打印当前链表
        int length();//获当前链表长度
        int Get(int n);//获取指定位置的元素
        int Locate(int x);//查找值为x的元素
        void Insert(int n, int x);//在指定位置插入元素x
        void Delete(int n);//删除第i个节点
    private:
        Node *first;
    };
    list2_oneself::list2_oneself() {
        first = new Node;
        first->next = NULL;
    }
    //头插法
    /*list2_oneself::list2_oneself(int a[],int n) {
        first = new Node;
        first->next = NULL;
        for(int i=0;i<n;i++) {
            Node *s=new Node;
            s->data = a[i];
            s->next = first->next;
            first->next = s;
        }
    }*/
    //尾插法
    list2_oneself::list2_oneself(int a[],int n) {
        first = new Node;
        first->next = NULL;
        Node* r = first;     //尾指针初始化,尾指针指first
        for(int i=0;i<n;i++) 
        {
            Node* S = new Node;
            S->data = a[i];     //为每个数据元素建立一个节点
            r->next = S;        //指针r指向的节点(first)指向s
            r = S;              //将新的节点插入链表,此时r代表s
        }              
        r->next = NULL;         //单链表建立完毕之后,将尾指针置空
    }
    //打印数据
    void list2_oneself::PrintList() {
        Node* p = first->next;    // 将工作指针指向第一个节点
        while(p != NULL)
        {
            cout << p->data << " ";
            p = p->next;
        }
        cout<<endl;
    }
    //求长度
    int list2_oneself::length() {
        int count =0;
        Node* p=first->next;
        while(p!=NULL) {
            count++;
            p=p->next;
        }
        return count;
    }
    //获得指定位置的数据
    int list2_oneself::Get(int n) {
        int count = 0;
        Node* p=first->next;
        while(p!=NULL) {
            count++;
            if(count == n) return p->data;
            p=p->next;
        }
        return -1;
    }
    //查找值为x的元素
    int list2_oneself::Locate(int n) {
        int count =0;
        Node* p=first->next;
        while(p!=NULL) {
            count++;
            if(p->data == n) return count;
            p=p->next;
        }
        return 0;
    }
    //在指定位置插入元素
    void list2_oneself::Insert(int n,int x) {
        int count=0;
        Node* p=first->next;
        while(p!=NULL) {
            count++;
            if(count == n) {
                Node* S = new Node;
                S->data = x;
                S->next = p->next;
                p->next = S;
            }
            p=p->next;
        }
    }
    //删除第i个节点
    void list2_oneself::Delete(int n) {
        int count=0;
        Node* p=first->next;
        while(p!=NULL) {
            //count++;
            if(count == n-1) {
                Node* q=p->next;//要删除的节点
                p->next=q->next;
                delete(q);
            }
            count++;
            p=p->next;
        }
    }
    int main()
    {
        int arry[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        list2_oneself *linklist = new list2_oneself(arry, 10);
        linklist->PrintList();
        cout<<"length is "<<linklist->length()<<endl;
        cout<<"data[5] is "<<linklist->Get(6)<<endl;
        cout<<"5 is on "<<linklist->Locate(5)<<endl;
        linklist->Insert(5,226);
        linklist->PrintList();
        cout<<"length is "<<linklist->length()<<endl;
        cout<<"delete 4"<<endl;
        linklist->Delete(4);
        linklist->PrintList();
        cout<<"length is "<<linklist->length()<<endl;
        return 0;
    }
    ~~~
    
    展开全文
  • C++编写线性表

    千次阅读 2019-10-27 22:32:54
    数据结构:用C++编写顺序表 ...采用顺序存储结构存储的线性表。 元素的追加只需要在尾部处增加一个地址,顺序表的长度增大一,把值赋给该地址。 元素的插入稍微复杂一点,要先判断插入的位置...

    数据结构:用C++编写顺序表

    数据结构实验心得

    1. 用c++语言编写一段程序,以实现顺序表的功能:元素的插入、删除、追加。

    2. 实验心得:
      本次的实验让我对于顺序表有了更深的理解,顺序表是通过数据元素物理存储的连续性。来反应元素之间逻辑上的相邻关系。采用顺序存储结构存储的线性表。
      元素的追加只需要在尾部处增加一个地址,顺序表的长度增大一,把值赋给该地址。
      元素的插入稍微复杂一点,要先判断插入的位置是否合理,后面的元素都需要往后移一位,长度加一。
      元素的删除,首先要判断删除的位置上是否有元素,有的话就删除,后面的元素都需要往前移一位。
      实验课带来的好处就是走出课本,真真正正的接触代码,有了实践性的效果。

    3. 我的编程思想

      核心部分:
      
    typedef struct A
    		{
    		int * pA ;//存放地址
    		int max;//表的最大长度
    		int size;
    		} S;
    
    ==利用c++语言中的结构体,将顺序表中的不同类型集中起来,统一类型。
    	有利于处理不同数据类型的变量。==
    

     顺序表的初始化:

    void csh(S & pArr,int max)//初始化顺序表
    {
    pArr.pA = new int[max];
    if(!pArr.pA)
    exit(-1); //非正常退出
    pArr.max=max;
    pArr.size=0;
    }
    

     判断顺序表是否为空还是满

    bool isempty(S & pArr)
    {
    	if(0==pArr.size){
    		return true;
    	}
    	else{
    		return false;}
    }
    bool isfull(S & pArr)
    {
    if(pArr.max==pArr.size)
    return true;
    else
    return false;
    }
    

     元素的追加

    bool append(S & pArr,int val)//尾部添加数据
    {
    if(isfull(pArr))
    return false;
    else
    {
    pArr.pA[pArr.size++]=val;
    return true;
    }
    }
    

     元素的插入

    bool insert(S & pArr,int pos,int val)
    {
    if(isfull(pArr))
    return false;
    if(pos<1||pos>pArr.size+1)
    return false;
    if(pos<=pArr.size)
    {
    	for(int i=pArr.size-1; i>=pos-1; i--)
    	{
    		pArr.pA[i+1]=pArr.pA[i];
    	}
    }
    pArr.pA[pos-1]=val;
    pArr.size++;
    return true;
    }
    

     元素的删除:

    bool Delete(S & pArr,int pos)
    {
    if(isempty(pArr))
    return false;
    if(pos<0||pos>pArr.size)
    return false;
    for(int i=pos; i<pArr.size; i++)
    {
    	pArr.pA[i-1]=pArr.pA[i];
    }
    pArr.size--;
    return true;
    }
    

    源代码如下:

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    
    typedef struct A
    {
    int * pA ;//存放地址
    int max;//表的最大长度
    int size;
    } S;
    
    void csh(S & pArr,int max);//新建顺序表
    bool append(S & pArr,int val);//往顺序表中追加元素
    bool isempty(S & pArr);//判断顺序表是否为空
    bool isfull(S & pArr);//判断顺序表是否为满
    bool insert(S & pArr,int pos,int val);//在指定位置插入一个元素
    void show(S & pArr);//遍历整个顺序表
    bool Delete(S & pArr,int pos);//删除顺序表指定位置的元素
    bool xh(S & pArr);//销毁顺序表
    
    void csh(S & pArr,int max)//初始化顺序表
    {
    pArr.pA = new int[max];
    if(!pArr.pA)
    exit(-1); //非正常退出
    pArr.max=max;
    pArr.size=0;
    }
    
    bool isempty(S & pArr)
    {
    	if(0==pArr.size){
    		return true;
    	}
    	else{
    		return false;}
    
    }
    
    bool isfull(S & pArr)
    {
    if(pArr.max==pArr.size)
    return true;
    else
    return false;
    }
    
    void show(S & pArr)
    {
    if(isempty(pArr))
    cout<<"顺序表为空!!"<<endl;
    else
    {
    for(int i=0; i<pArr.size; i++)
    {
    cout<<pArr.pA[i]<<" ";
    }
    cout<<endl;
    }
    }
    
    bool append(S & pArr,int val)//尾部添加数据
    {
    if(isfull(pArr))
    return false;
    else
    {
    pArr.pA[pArr.size++]=val;
    return true;
    }
    }
    
    bool insert(S & pArr,int pos,int val)
    {
    if(isfull(pArr))
    return false;
    if(pos<1||pos>pArr.size+1)
    return false;
    if(pos<=pArr.size)
    {
    	for(int i=pArr.size-1; i>=pos-1; i--)
    	{
    		pArr.pA[i+1]=pArr.pA[i];
    	}
    }
    pArr.pA[pos-1]=val;
    pArr.size++;
    return true;
    }
    
    bool Delete(S & pArr,int pos)
    {
    if(isempty(pArr))
    return false;
    if(pos<0||pos>pArr.size)
    return false;
    for(int i=pos; i<pArr.size; i++)
    {
    	pArr.pA[i-1]=pArr.pA[i];
    }
    pArr.size--;
    return true;
    }
    
    bool xh(S & pArr)
    {
    if(pArr.pA==NULL)
    return false;
    delete pArr.pA;
    pArr.pA=NULL;
    return true;
    }
    
    void main(){
    S ArrayList;
    csh(ArrayList,10);
    int a[10];
    
    cout<<"请按顺序依次输入5个数"<<endl;
    cin>>a[0]>>a[1]>>a[2]>>a[3]>>a[4];
    for(int i=0;i<=4;i++){
    append(ArrayList,a[i]);
    }
    
    cout<<"顺序表的5个数如下"<<endl;
    show(ArrayList);
    int aa;
    int bb;
    cout<<"请输入需要插入的位置"<<endl;
    cin>>aa;
    cout<<"请输入需要插入的元素"<<endl;
    cin>>bb;
    insert(ArrayList,aa,bb);
    show(ArrayList);
    
    cout<<"请输入需要删除的元素的位置"<<endl;
    cin>>aa;
    Delete(ArrayList,aa);
    show(ArrayList);
    
    }
    
    展开全文
  • 数据结构详解——线性表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++版)王红梅等编著
    展开全文
  • C++ 类实现线性表

    千次阅读 2018-10-14 18:22:12
    下图是标准C语言实现的...下面可以用C++实现,第一个参数就是this的指针 list.h函数 #pragma once typedef int Elem; class List { public: List(int size); ~List(); void ClearList(); // 将数组长度设为...

    下图是标准C语言实现的函数定义

    下面可以用C++实现,第一个参数就是this的指针

    list.h函数

    #pragma once
    typedef  int Elem;
    class List
    {
    public:
    	List(int size);
    	~List();
    	void ClearList();                                   // 将数组长度设为0
    	bool ListEmpty();                                   // 判断数组是否为空
    	int ListLength();                                   // 获取数组长度
    	bool GetElem(int i, Elem *e);                       // 查找指定下标元素
    	int LocateElem(Elem *e);                            // 查找指定元素
    	bool PriorElem(Elem *currentElem, Elem *preElem);   // 查找元素的前驱元素
    	bool NextElem(Elem *currentElem, Elem *nextElem);   // 查找元素的后继元素
    	void ListTraverse();                                // 遍历线性表,输出元素
    	bool ListInsert(int i, Elem *e);                    // 在指定位置插入一个元素
    	bool ListDelete(int i, Elem *e);                    // 删除指定位置元素
    private:
    	int *m_pList;                                       // 指向一块内存
    	int m_iSize;                                        // 内存的大小
    	int m_iLength;                                      // 数组的长度
    };
    

    类的实现,list.cpp

    #include<iostream>
    #include "List.h"
    using namespace std;
    
    List::List(int size)
    {
    	m_iSize = size;
    	m_pList = new Elem[m_iSize];
    	m_iLength = 0;
    }
    
    
    List::~List()
    {
    	delete[] m_pList; // 释放数组内存
    	m_pList = NULL;
    }
    
    void List::ClearList()
    {
    	m_iLength = 0;
    }
    
    bool List::ListEmpty()
    {
    	return m_iLength == 0 ? true : false;
    }
    
    int List::ListLength()
    {
    	return m_iLength;
    }
    
    bool List::GetElem(int i, Elem *e)
    {
    	if (i < 0 || i >= m_iSize)
    	{
    		return false;
    	}
    	*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::PriorElem(Elem *currentElem, Elem *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(Elem *currentElem, Elem *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;
    	}
    }
    
    void List::ListTraverse()
    {
    	for (int i = 0; i < m_iLength; i++)
    	{
    		cout << m_pList[i] << endl;
    	}
    }
    
    bool List::ListInsert(int i, Elem *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;
    }
    
    bool List::ListDelete(int i, Elem *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;
    }
    
    

    测试主程序

    #include<iostream>
    #include "List.h"
    using namespace std;
    
    int main()
    {
    	Elem temp;
    	Elem arry[11] = { 3,5,7,2,9,1,8 };
    	List *list1 = new List(10);
    	cout << "length:" << list1->ListLength() << endl;
    	for (int i = 0; i < 7; i++)
    	{
    		list1->ListInsert(i, &arry[i]);
    	}
    	cout << "length:" << list1->ListLength() << endl;
    	// 删除第一个元素
    	list1->ListDelete(0, &temp);
    	cout << temp << endl;
    	// 搜索前驱元素
    	list1->PriorElem(&arry[4], &temp);
    	cout << temp << endl;
    	list1->NextElem(&arry[4], &temp);
    	cout << temp << endl;
    	list1->ListTraverse();
    	delete list1;
        return 0;
    }
    

     

    展开全文
  • } /***********计算线性表的长度*******************/ int SLLenght(SLType *SL) { return(SL->ListLen);//返回顺序表的元素数量 } /*********插入结点*******************************/ int SLInsert(SLType *...
  • 哇 好久没更博客了 因为从上次更文到现在为止,我一直在学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;...
  • 前言线性表包括两部分顺序表和链表,是数据结构的基础,在此主要就算法进行分析和总结,作为记忆了解,未做具体实现。提示:以下是本篇文章正文内容,下面案例可供参考一、顺序表#define LISST_INIT_SIZE 100#define...
  • 提要:这是我新开的一个专栏(数据结构学习) 很多的数据结构的书籍都是以C为基础实现的,主要是由于C强大的...这是本专栏的第一篇内容 介绍的是线性表的顺序存储结构以及C++实现方法,话不多说,下面就开始的线性表...
  • //获取线性表元素的操作 Status GetElem(SqList L,int i,ElemType *e) { if (L.length==0 || i|| i>L.length) { return ERROR; } *e = L.data[i-1]; return OK; } //在L中第i个位置插入元素e的函数(第i个...
  • C++线性表

    2020-08-12 22:48:44
    C++线性表(arrayList) 线性表根据存储方式分为:顺序存储(数组描述)、链式存储(链表描述) 线性表的抽象类(常用的API): 判断是否为空; 返回元素个数; 返回索引元素; 返回指定元素第一次出现的索引值; ...
  • 线性表存储结构(五选一):1、 带头结点的单链表2、 不带头结点的单链表3、 循环链表4、 双链表5、 静态链表线性表的基本功能:1、 构造:使用头插法、尾插法两种方法2、 插入:要求建立的链表按照关键字从小到大...
  • 线性表的基本操作 文章目录线性表的基本操作前言一、顺序表1、定义2、初始化构建3、插入操作1、算法2、代码实现4、删除操作1、算法2、代码实现5、合并操作二、链表1.单链表2.循环链表3.双向链表总结1 前言 线性表...
  • C++实现数据结构之线性表List.h#ifndef LIST_H #define LIST_H #include <iostream> using namespace std;class List { public: List(int size); //创建线性表 ~List();
  • 1.0 线性表的顺序存储及实现 啥子叫做线性表呢,原来我的理解就是数组,后来才知道这么理解并不准确,但是也差不多吧 线性表: 是表 是一种具有相同类型的数据元素的有序序列 1.1 线性表的顺序存储结构——–...
  • } 创建顺序表: void Create(Sqlist &L)//创建顺序表 { int i,num; cout请输入顺序表元素个数:"; cin>>num; for(i=0;i;i++) { cin>>L.elem[i]; L.Length++; } cout创建顺序表成功!"; } 求直接前驱: int ...
  • 顺序表 函数声明 List.h(顺序表的定义,各项功能和...//创建线性表 ~List();//销毁线性表 void ClearList();//清空线性宝 bool ListEmpty();//判断线性表是否为空 int ListLengh();//获取线性表的长度 bool GetE
  • C++实现线性表的链式存储结构(单链表)       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。也就是说,...
  • 线性表的顺序表示C++实现一,线性表的定义和特点1,线性表的定义2,线性表的特点二,线性表的顺序存储表示1,顺序存储定义2,顺序存储举例3,顺序存储优缺点三,线性表顺序表示的实现 一,线性表的定义和特点 1,...
  • 在讨论线性表的顺序及链式存储映像,并在此基础上给出其基本操作的实现之前,先以模板的形式为ADT List建立一个抽象类。 //List.h #pragma once template <class ElemType> class List { public: //后面加个...
  • c++实现线性表

    2012-05-21 13:07:50
    线性表的实现代码 #include using namespace std; template class List { public: virtual void clear()=0;//清空 virtual int leng()=0;//求线性表的长度 virtual Telem gete(int loc,Telem ⪙)=0;//返回第i...
  • 主要介绍了C++ 数据结构线性表-数组实现的相关资料,需要的朋友可以参考下
  • 文章目录一、链表相关概念1,相关名词2,链表的特点3,链表分类4,单链表表示二、单链表的C++实现 一、链表相关概念 1,相关名词 2,链表的特点 3,链表分类 4,单链表表示 二、单链表的C++实现 typedef ...
  • C++ 线性表 实验及代码

    千次阅读 2020-06-04 21:49:08
    1.实验内容: (1)了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中 表示这种关系有顺序存储结构和链式存储结构; (2)掌握这两种存储结构的描述方法...(2)建立一个循环单链表,其节点有 prior,
  • 算法基础_线性表 线性表也称为有序表,他的每一个实例...1.创建一个线性表。 2.撤销一个线性表。 3.确定线性表是否为空。 4.确定线性表的长度。 5.按一个给定的索引查找一个元素。 6.按一个给定的元素查找其索引。 7...
  • c++实现的线性表排序算法 插入排序,希尔排序,冒泡排序,快速排序,堆排序,归并排序等
  • 创建LinkList.h头文件,一般类的声明和成员函数的实现都是分文件编写的,但这里用的是模板编程,就放在一个文件夹下了。 #pragma once template<class T> class LinkNode { template<class T> friend ...
  • 线性表及其操作一.线性表基本概念二.线性表的顺序存储结构三.线性表的链式存储结构 [2020年7月6号] 一.线性表基本概念 1.基本概念 线性表(List):零个或多个数据元素的有限序列 性质①:第一个元素无前驱,最后一...
  • //下标从0开始,但是对线性表的操作中的下标从1开始:第1个元素其实就是下标为0的元素 int length ; } ; # endif // SEQUENCELIST_H SqList :: SqList ( ) { length = 0 ; } SqList :: SqList...
  • 线性表C++实现

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,691
精华内容 4,276
关键字:

c++建立线性表

c++ 订阅