数据结构学习心得——单链表

骑猪看日落 2022-06-10 11:23 386阅读 0赞

## 一、线性表的存储结构 ##

1.  顺序表（顺序表操作见上一篇博客）
2.  链表  
    在链表存储中，每个结点不仅包含所有的元素的信息，还包含元素之间逻辑关系的信息，如单链表中前驱结点包含后继结点的地址信息，这样就可以通过前驱结点中的地址信息找到后继结点的位置。  
    （2）单列表  
    在每个节点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。下图所示为带头结点的单链表。  
    ![这里写图片描述][SouthEast]  
    a.带头结点的单链表中，头指针head指向头结点，头结点的值域不包含任何信息，从头结点的后继结点开始存储数据信息。  
    b.不带头结点的单链表中的头指针head直接指向开始结点。

## 二、单链表的操作实现代码 ##

本篇博客主要见得是单链表得操作，双链表和循环链表见下篇博客。  
关于下面的代码，这里我再啰嗦两句，单链表得创建有两种：一种是头插法建立单链表，另一种是尾插法建立单链表，下面代码两种方法都实现了，请注意区分。

#include <iostream>
    
    using namespace std;
    
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    
    //尾插法创建链表
    void createList(LNode *&head,int a[],int n)
    {
        int i;
        LNode *p = head;
        for(i=0;i<n;i++)
        {
            LNode *q = new LNode;
            q->data = a[i];
            p->next = q;
            p=q;
        }
        p->next = NULL;
    }
    
    /*
    //头插法创建链表
    void createList(LNode *&head,int a[],int n)
    {
        int i;
        LNode *p = head;
        for(i=0;i<n;i++)
        {
            LNode *q = new LNode;
            q->data = a[i];
            q->next = p->next;
            p->next = q;
        }
    }*/
    
    //输出链表中所有元素的值
    void printList(LNode *head)
    {
        LNode *p = head->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    
    //第p位插入值为e的元素
    void insertElem(LNode *&head,int p,int e)
    {
        int i;
        LNode *r = head;
        LNode *s = new LNode;
        s->data = e;
        for(i=1;i<p;i++)
        {
            r = r->next;
        }
        s->next = r->next;
        r->next = s;
    }
    
    //删除第p位元素
    void deleElem(LNode *&head,int p)
    {
        int i;
        LNode *r = head;
        LNode *s;
        for(i=0;i<p;i++)
        {
            s = r;
            r = r->next;
        }
        s->next = r->next;
        delete r;
    }
    
    void findElem(LNode *head,int e)
    {
        int i = 0;
        LNode *p = head->next;
        while(p!=NULL)
        {
            i++;
            if(p->data == e)
            {
                cout<<"元素在第"<<i<<"位";
                break;
            }
            p=p->next;
        }
    }
    int main()
    {
        LNode *head = new LNode;
        head->next = NULL;
        int a[6]={
       2,3,4,7,9,8};
        createList(head,a,6);
        printList(head);
        insertElem(head,2,5);
        printList(head);
        deleElem(head,2);
        printList(head);
        findElem(head,8);
        return 0;
    }

代码运行结果截图如下：  
![这里写图片描述][SouthEast 1]

[SouthEast]: /images/20220610/5a06dc966e4747f88d2fe52cc02dec27.png
[SouthEast 1]: /images/20220610/4516cb4dee93423a806ed01f6581ff67.png