数据结构-2.8.单链表的建立

---

一.尾插法建立单链表：取数据元素插入单链表表尾

1.图解：

对于时间复杂度，最好的时间复杂度是第一次，因为此时内层循环即找第i-1个结点就不执行了(不满足j<i-1)，

内层循环和外层循环时间复杂度都是O(n)，所以整个尾插操作的时间复杂度为O(n * n)。

(i为1时内层循环走0次，i为2时内层循环走1次，以此类推，i为n时内层循环走n-1次，那么一共走

0+1+2+...+（n-1）次，易知时间复杂度为O(n * n) )

但这个时间复杂度较高，因此没必要每次都从头开始寻找，可以设置一个指针指向表尾的最后一个数据结点，

然后当要在尾部插入一个新的数据元素时只需要对尾部结点进行后插操作即可：

后插后还需要把表尾指针向后移指向新的表尾数据结点：

2.代码演示：

#include<stdio.h>
#include<stdlib.h>
​
​
//定义单链表结点类型 
typedef struct LNode
{ 
    int data; //每个结点存放的数据元素 
    struct LNode *next; //指向下一个节点的指针，是链表型 
}LNode,*LinkList;
​
​
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{
    //1.分配一个头结点
    L = (LNode*)malloc( sizeof(LNode) );
    //2.头结点判断
    if( L==NULL )
    {
        //代表头结点分配失败，比如内存不足 
        return false;
    }  
    /*3.走到这儿说明头结点分配成功
        由于第一个结点没存数据，所以第一个结点为NULL*/
    L->next = NULL;
    //4.分配成功
    return true;     
} 
​
​
//正向建立单链表
LinkList List_TailInsert(LinkList &L)
{
    //1.设置结点
    int x;
    /*2.建立头结点(头结点里的指针没必要设为NULL了，
                   因为之后必要加一个元素，头结点指向的元素一定不为空) */
    L = (LinkList)malloc( sizeof(LNode) );//初始化单链表 
    //3.设置表尾指针r
    LNode *r=L;
    LNode *s;
    //4.输入结点的值即要插入单链表的元素 
    scanf("%d",&x);
    //5.输入9999表示结束,9999不是固定的 
    while( x!=9999 )
    {
        s = (LNode *)malloc( sizeof(LNode) );
        s->data = x;
        r->next = s;
        //6.r指向新的表尾结点
        r=s;
        scanf("%d",&x); 
    } 
    //7.把尾结点指针置空
    r->next = NULL;
    return L; 
} 
​
​
int main()
{
    //1.声明一个指向单链表的指针
    LinkList L;
    //2.初始化一个空表
    InitList(L); 
    return 0;
}

该代码的图解：while循环就是插入操作核心

x为要插入单链表的元素，L为头结点(头结点里的指针没必要设为NULL了，因为之后必要加一个元素，头结点指向的元素一定不为空)，*r代表表尾指针，一开始只有一个，表头即表尾：

假设x(x为要插入单链表的元素)为10，符合while循环条件，给要插入单链表的元素先分配一个空间，在再空间中存入元素，最后修改指针即r->next=s，此时表尾结点为s，则r=s：

注：r始终指向新的表尾结点。

之后以此类推，直到x不符合循环条件时停止插入，while循环结束(此时x为9999)后r->next=NULL即表尾后就是空的，代表单链表结束，最后返回新的单链表：

3.时间复杂度：如果插入n个结点则循环n次，所以时间复杂度为O(n)

---

二.头插法建立单链表：取数据元素插入单链表表头->可以使数据元素逆置

例如：

单链表表头插入11后为：

核心：相当于对头结点的后插操作即对指定结点的后插操作

1.图解：

2.代码演示：

#include<stdio.h>
#include<stdlib.h>
​
​
//定义单链表结点类型 
typedef struct LNode
{ 
    int data; //每个结点存放的数据元素 
    struct LNode *next; //指向下一个节点的指针，是链表型 
}LNode,*LinkList;
​
​
//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{
    //1.分配一个头结点
    L = (LNode*)malloc( sizeof(LNode) );
    //2.头结点判断
    if( L==NULL )
    {
        //代表头结点分配失败，比如内存不足 
        return false;
    }  
    /*3.走到这儿说明头结点分配成功
        由于第一个结点没存数据，所以第一个结点为NULL*/
    L->next = NULL;
    //4.分配成功
    return true;     
} 
​
​
//逆向建立单链表
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    //1.设置结点即要插入的元素 
    int x;
    //2.创建头结点
    L = (LinkList)malloc( sizeof(LNode) );
    //3.初始为空链表
    L->next = NULL;
    //4.输入结点的值
    scanf("%d",&x);
    //5.输入9999表示结束
    while( x!=9999)
    {
        s = (LNode *)malloc( sizeof(LNode) ); //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s; //将新结点插入表中，L为头指针
        scanf("%d",&x); 
    } 
    return L; 
} 
​
​
int main()
{
    //1.声明一个指向单链表的指针
    LinkList L;
    //2.初始化一个空表
    InitList(L); 
    return 0;
}

该代码的图解：while循环就是插入操作核心

1）x为要插入单链表的元素，先对单链表初始化即分配存储空间，再让p->next=NULL，初始为空链表：

注：

左部分代码中L->next=NULL不能省，如果省了，L->next(头结点指针)就有可能是一片神秘的未知区域，因为像这种

malloc动态分配申请的这片内存空间中可能有脏数据，如果不把L->next初始化，就不知道L->next是何物了，而且最后

实现插入后始终指向一片未知区域(每次插入都在头结点之后插，不影响尾结点)：

2）while循环实现了后插操作，只不过每次执行后插操作的指定结点都是头结点：

while循环中首先给要插入单链表的元素分配一个空间，在再空间中存入元素，再修改指针，

L->next一开始是秘：

根据题意，要让插入的元素即x指向秘，因此s->next = L->next ：

最后把x接到头指针后面即可：

3.举例：

依次插入10，16，27，9999：

结果刚好和输入的顺序相反(因为每次插入都在头结点之后插)，因此头插法建立单链表可以实现数据元素逆置

->对此，要想逆置一个单链表，可以依次取出该单链表的元素(用指针循环扫描依次取得元素)，再利用头插法就可以实现

该单链表的原地逆置，也可以建立新链表把取出的元素利用头插法存入该新链表中；

也可以建立新链表，把要逆置的链表从后往前依次存入新链表实现逆置。

---

三.总结：

---

原文地址：https://blog.csdn.net/ADCvbV/article/details/142188546

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！