【数据结构】线性表的链式存储结构简单实现及应用

淩亂°似流年 2022-04-08 18:20 196阅读 0赞

链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：

（1）存储数据元素自身信息的部分，称为数据域；

（2）存储与前驱或后继结点的逻辑关系，称为指针域；

![20181219102952152.png][]

其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。

显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即NULL（图示中常用^表示)。

#include<iostream>//单链表基本操作插入 删除 增加 获得长度 打印
    using namespace std;
    typedef int ElemType;
    typedef struct lnode
    {
        int data;
        lnode *next;//lnode 类的啊啊啊
    }lnode;
    class LinkList
    {
    private:
        lnode *head;
        int length = 0 ;
    public:
        void CreatList1(int n);//头插法
        void CreatList2(int n);//尾插法
        void ListInsert(int i,int e);//插入i个位置某个数e
        int ListDelete(int i);//删掉第i个数
        int GetElem(int i);//获得第i个数
        int LocateElem(int e);//获得数e的地址
        int Listlength();//获得长度
        void printList();//打印链表；
        void reverse(lnode *& head);
    };
    void LinkList::CreatList1(int n)
    {
        lnode *p;
        cout<<"输入"<<n<<"个数据元素值"<<endl;
        for(int i=0;i<n;i++)
        {
            p=new lnode;
            cin>>p->data;
            p->next=head->next;
            head->next=p;
            length++;
        }
    }
    void LinkList::CreatList2(int n)
    {
        lnode *p,*s=head;
        cout<<"输入"<<n<<"个数据元素"<<endl;
        for(int i=0;i<n;i++)
        {
            p=new lnode;
            cin>>p->data;
            p->next=NULL;
            s->next=p;
            s=p;
            length++;
        }
    }
    
    int LinkList::LocateElem(int e)
    {
        lnode *p=head->next;
        int j=1;
        while(p&&p->data!=e)
        {
            p=p->next;
            j++;
        }
        if(p==NULL)
            return 0;
        else
            return j;
    }
    int LinkList::GetElem(int i)
    {
        lnode *p=head->next;
        int j=1;
        while(p&&j<i)
        {
            p=p->next;
            j++;
        }
        if(!p||j>i)
            return -1;
        else
            return p->data;
    }
    void LinkList::ListInsert(int i,int e)
     {
         int j=0;
         lnode*p=head;
         while (p&&j<i-1)
         {
             p=p->next;
             j++;
         }
         if(!p||j>i-1)
         {
             cout<<"failure"<<endl;
             return ;
         }
         else
         {
             lnode*s=new lnode;
             s->data=e;
             s->next=p->next;
             p->next=s;
             length++;
         }
     }
    int LinkList::ListDelete(int i)
    {
        int j=0;
        lnode*p=head;
        while (p&&j<i-1)
        {
            p=p->next;
            j++;
        }
        if(!p||j>i-1)
        {
            cout<<"fail to delete"<<endl;
            return -1;
        }
        else
        {
            lnode*s=p->next;
            p->next=s->next;
            j=s->data;
            delete s;
            return j;
        }
    }
    int LinkList::Listlength()
    {
        return length;
    }
    void LinkList::printList()
    {
        int i = length;
        lnode* p = head;
        while(i --)
        {
            p = p -> next;
            cout<<p -> data <<" ";
        }
    }
    void LinkList::reverse(lnode *& head)
    {
        lnode* p = head -> next;
        if(!p || ! p -> next)
        {
            cout<<" wrong"<<endl;
            return;
        }
        lnode * qr = p -> next, * q;
        p ->next = NULL;
    }
    int main()
    {
        LinkList LinkLista;
        LinkLista.CreatList1(5);
        LinkLista.printList();
        cout << "length:"<<LinkLista.Listlength()<<endl;
        LinkLista.ListInsert(2,5);
        LinkLista.printList();
    
        return 0;
    }

[20181219102952152.png]: /images/20220404/bcc2b858883c480aabbe47bd63d8032a.png