单链表的建立(尾插法,头插法,链表的删除,链表的初始化)

最近学习了数据结构,我们现在来实现单链表的操作实现.

所谓单链表,就是

 

 存储数据的,带有指针的,单向指引的数据结构. 头结点一般是识别链表的,所以不包含数据,如果链表为空,那么头结点指向第一个节点的尾指针也是NULL.

所以我们现在开始建立一个链表.

首先我们刚开始只有一个头结点,我们还需要新建结点,所以我们要申请链表结点同类型的空间,引入

#include
#include

接下来,我们既然是存储链表,链表结点包括数据和指针,所以我们要建立链表这个数据类型,就要定义相关的类型

typedef int ElemType;                

---

自定义结点的数据类型

接着定义单链表结点的指针和数据

typedef struct LNode
{
    ElemType data;                //节点的数据区,用类型定义的结构属性
    struct LNode *next;
}LinkList;

我们现在,就已经,定义出结点的数据和指针了,接下来的工作就是链表初始化,和链表的插入,输出,清空链表的操作了,我们一  一进行.

我们看一个代码,首先从其主函数入手,所以我们首先建立相关的函数接口,把他们的操作逻辑上链接起来,这样有助于我们熟悉大致的框架.然后再去着手函数细节,就有助于我们操作.

主函数的相关操作:

int main()
{
    LinkList *L1,*L2;        //定义两个链表                        
    ElemType a[8] = {1,2,3,4,5,6,7,8};        //链表数据数组
    CreatListF(L1,a,8);                        //头插法建立链表,输入的参数分别是建立的链表,输入的数据数组, 建立的数据个数
    printf("头插法的结果");

    DispList(L1);                                //展示链表
    CreatListR(L2,a,8);                        
    printf(尾插法的结果);                        //同理
    DispList(L2);
    DestroyList(L1);                        //清空链表
    DestroyList(L2);
    return 0;
}

---

我们要建立单链表,那就需要有数据插入,所以我们先用链表结点的数据类型来定义一个数据,然后建立链表的时候,就可以从数组来获取数据了(数组也是指针类型,并且不可修改)

这样我们的大概操作就已经完成了,接下来就是去处理具体的操作了.

头插法建立链表:

我们头插法,就是在头结点后面插入数据,然后新结点指针指向后面的数据

 所以,我们现在就要实现的是,头结点的尾指针指向新结点,新结点的尾指针指向后面的结点.

开始我们的操作,

定义成员函数

void CreateListF(LinkList *&L,ElemType a[],int n){                //传入修改建立的链表, 传入的数据数组,  结点的个数

//首先定义链表节点

LinkList *s;

然后分配头结点空间

L=(LinkList*)malloc(sizeof(LinkList));

L->next = NULL;                //初始的时候,头结点尾指针是空的,头结点的数据区无内容起到表示作用

---

我们会想到,既然头结点分配空间了,为什么新建街店不分配空间呢?不慌,我们需要插入很多次,所以每次插入就要为新节点分配空间.

    for(i=0;i     {
        s=(LinkList*)malloc(sizeof(LinkList));        //每次插入都为新节点分配空间
        s->data=a[i];                                                //节点的数据区,用自定义类型定义的结构属性
        s->next = L->next;
        L->next=s;
    }

}

上面两行不可调换

我们直接把L-＞next送给新节点的后继指针，就把新节点和后面一个节点链接起来了

然后再把新节点的位置送到头结点发后继指针

这样就把新节点插入了

不能强行调换的原因是，L-＞next里面存放的是下一个节点的位置，不能直接覆盖，我们一会儿还要用，所以覆盖指针前要三思，先把要覆盖的指针处理好，再进行操作。

尾插法建表:

 尾插法就是在单链表的最后一个结点上,添加一个节点,实质就是让最后一个节点的尾指针指向新的节点,

开始我们的实操:

定义成员变量传入参数

---

void CreateListR(LinkList *&L,ElemType a[], int n){

        //我们要用到的节点是新建节点 ,  一直标志尾结点的节点,这样我们才能定位到尾结点,然后进行变换指针 

       LinkList *s,*r;

        //头结点初始化,先分配空间

       L = (LinkList*)malloc(sizeof(LinkList));

        //头结点置空

        L->next=NULL;

        //然后尾结点

        r=L;                    //r始终指向终端结点,开始时指向头结点
    for (i=0; i     {
        s=(LinkList *)malloc(sizeof(LinkList));  //创建新结点,分配空间
        s->data=a[i];                //新节点赋值
        r->next=s;          //将*s插入*r之后
        r=s;
    }
    r->next=NULL;           //终端结点next域置为NULL

 

}

---

顺序不能调换,我们要在结尾插入结点,依据就是,让链表最后一个结点的尾指针指向这个新的结点, 所以我们就要把新结点的指针赋值给尾结点的尾指针 r->next

然后,我们再让这个新结点,成为尾结点  r 

销毁单链表

void DestroyList(LinkList *&L)  //销毁单链表
{
    LinkList *p=L,*q=p->next;
    while (q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
    }
    free(p);    //此时q为NULL,p指向尾结点,释放它
}
 

---

我们想要销毁链表就需要从头开始,因为这是单链表,单向联系

用一个指针*p表示头指针, 用一个q来存放下一个结点的位置,其实就是存放头结点的尾指针

直到下一个结点是null, 就说明就剩一个头结点没有覆盖了,我们就可以进行最后的销毁了

 

单链表的输出:

void DispList(LinkList*L)  //输出单链表

{

        LinkList *p = L->next;

        while(p!=NULL)

        {

                printf("%d",p->data);

                p=p->next;

         }        

        printf("\n");

}

---

输出链表就更简单了,参照链表销毁,我们只是遍历了一下尾指针,接连遍历

注意:每当我们修改结点,或者覆盖指针的时候,注意一下,那个指针是否对我们后续操作有用,我们是否进行了存储, 再进行下一步操作

源代码如下:

#include 
#include 
typedef int ElemType;
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;
    struct LNode *next;     //指向后继结点
} LinkList;
 
void CreateListF(LinkList *&L,ElemType a[],int n);//头插法建立单链表
void CreateListR(LinkList *&L,ElemType a[],int n);//尾插法建立单链表
void DestroyList(LinkList *&L); //销毁单链表
void DispList(LinkList *L);  //输出单链表
 
int main()
{
    LinkList *L1, *L2;
    ElemType a[8]= {7, 9, 8, 2, 0, 4, 6, 3};
    CreateListF(L1, a, 8);
    printf("头插法建表结果：");
    DispList(L1);
    CreateListR(L2, a, 6);
    printf("尾插法建表结果：");
    DispList(L2);
    DestroyList(L1);
    DestroyList(L2);
    return 0;
}
 
void CreateListF(LinkList *&L,ElemType a[],int n)//头插法建立单链表
{
    LinkList *s;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));     //创建头结点
    L->next=NULL;
    for (i=0; i
    {
        s=(LinkList *)malloc(sizeof(LinkList));//创建新结点
        s->data=a[i];
        s->next=L->next;            //将*s插在原开始结点之前,头结点之后
        L->next=s;
    }
}
void CreateListR(LinkList *&L,ElemType a[],int n)//尾插法建立单链表
{
    LinkList *s,*r;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));     //创建头结点
    L->next=NULL;
    r=L;                    //r始终指向终端结点,开始时指向头结点
    for (i=0; i
    {
        s=(LinkList *)malloc(sizeof(LinkList));//创建新结点
        s->data=a[i];
        r->next=s;          //将*s插入*r之后
        r=s;
    }
    r->next=NULL;           //终端结点next域置为NULL
}
 
void DestroyList(LinkList *&L)  //销毁单链表
{
    LinkList *p=L,*q=p->next;
    while (q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
    }
    free(p);    //此时q为NULL,p指向尾结点,释放它
}
 
void DispList(LinkList *L)  //输出单链表
{
    LinkList *p=L->next;
    while (p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}