单链表_牛客博客

1）顺序表与链式表的比较

顺序表：存储密度高、可以随机存取，但是扩展容量不方便，删除、插入元素开销大。

链式表：需要存储指针信息，不能随机存取，只能依次遍历，删除、插入元素开销小，扩展容量很容易。

2）单链表定义

不带头结点

#include <stdio.h>

typedef struct LNode{
    int data;
    struct LNode * next;
}LNode,*LinkList;

//无头节点
bool InitList(LinkList &L)
{
    L=NULL; //把头指针置空
    return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
    return (L==NULL);
}

int main(void)
{
    LinkList L; //声明一个指向单链表的指针
    InitList(L);
    printf("%d",IsListEmpty(L));
    return 0;
}

带头结点

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
    int data;
    struct LNode * next;
}LNode,*LinkList;

//带头节点
bool InitList(LinkList &L)
{
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)return false; //上面头指针指向了头结点，头指针还指向NULL,说明内存空间不足，返回false；
    L->next=NULL; //头结点置空
    return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
    return (L->next==NULL);
}

int main(void)
{
    LinkList L; //声明一个指向单链表的指针
    InitList(L);
    printf("%d",IsListEmpty(L));
    return 0;
}

3）单链表的插入

按序号插入——带头结点(推荐)

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
    int data;
    LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
    L=(LNode *)malloc(sizeof(LNode)); //分配一个空间作为头结点，头指针指向头结点
    L->next=NULL; //头节点的next域置空
}

//按位序插入
bool ListInsert(LinkList &L,int i,int e)
{
    if(i<1) return false;
    LNode * p=L; //指针p指向头结点
    int j=0; //下标j用来记录指针p指向第几个结点
    while(p!=NULL&&j<i-1) //循环找到第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(p==NULL) return false; //i值超过了链表的范围，不合法
    LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
    s->data=e; //将要插入的数据e存到结点中
    s->next=p->next;
    p->next=s;
    return true;
}

int main(void)
{
    LinkList L; //申请一个LinkList类型的头指针
    InitList(L);
    if(ListInsert(L,1,1))
    {
        printf("%d\n",L->next->data);
    }
    else
        printf("Failed!\n");
    return 0;
}

最好时间复杂度：O(1),最坏时间复杂度：O(n),平均时间复杂度：O(n)

按序号插入——不带头结点

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
    int data;
    LNode * next;
}LNode,*LinkList;

//不带头结点
bool InitList(LinkList &L)
{
    L=NULL; //将头指针置空
    return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
    if(i<1) return false; //非法输入
    if(i=1)
    {
        LNode * s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    int j=1; //用来记录p指向第几个结点
    //找到第i-1个结点
    LNode * p=L;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL) return false;
    LNode * s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

int main(void)
{
    LinkList L;//声明一个头指针
    InitList(L);
    if(ListInsert(L,0,1))
    {
        printf("%d\n",L->data);
    }
    else
        printf("Failed!\n");
    return 0;
}

指定结点后插操作

bool InsertNextNode(LNode * p,int e)
{
    if(p==NULL) return false; //i值超过了链表的范围，不合法
    LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
    s->data=e; //将要插入的数据e存到结点中
    s->next=p->next;
    p->next=s;
    return true;
}

时间复杂度:O（1）

指定结点前插操作

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
    int data;
    LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
    LNode * p;
    L=(LNode *)malloc(sizeof(LNode));
    p=L;
    p->next=NULL;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
    if(i<1) return false; //非法输入
    int j=0; //用来记录p指向第几个结点
    //找到第i-1个结点
    LNode * p=L;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL) return false;
    LNode * s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//核心代码块，插入制定结点之前
bool InsertPrioList(LNode * p,int e)
{
    if(p==NULL)return false;
    LNode * s=(LNode *)malloc(sizeof(LNode));
    if(s==NULL)return false;
    //把s插入p结点之后
    s->next=p->next;
    p->next=s;
    //把p的数据拷贝到s，再把要插入的数据存入p
    s->data=p->data;
    p->data=e;
    return true;
}

int main(void)
{
    LinkList L;
    InitList(L);
    ListInsert(L,1,1);
    LNode * r=L->next;
    InsertPrioList(r,5);
    printf("%d",L->next->data);
    return 0;
}

时间复杂度：O（1）

4）单链表的删除

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
    int data;
    LNode * next;
}LNode,*LinkList;

bool InitList(LinkList &L)
{
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL)return false;
    L->next=NULL;
    return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
    if(i<1) return false; //非法输入
    int j=0; //用来记录p指向第几个结点
    //找到第i-1个结点
    LNode * p=L;
    while(p!=NULL&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL) return false;
    LNode * s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//核心代码，按位序删除
bool ListDelete(LinkList &L,int i,int &e)
{
    if(L->next==NULL)return false;
    if(i<1)return false;
    //找到第i-1个位置
    LNode * p=L;
    int j=0;
    while(j<i-1&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    if(p==NULL) return false;
    //在第i-1个位置后执行删除操作
    LNode * q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

void PrintList(LinkList L)
{
    LNode * p=L;
    while(p->next!=NULL)
    {
        p=p->next;
        printf("%d ",p->data);
    }
    printf("\n");
}

int main(void)
{
    LinkList L;
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    LNode * p=L;
    PrintList(L);
    int e;
    ListDelete(L,2,e);
    p=L;
    PrintList(L);
    return 0;
}

最好时间复杂度：O（1）、最坏、平均时间复杂度O（n).

指定结点的删除

bool DeleteNode(LNode * p)
{
    if(p==NULL) return false;
    LNode * q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
}

时间复杂度:O(1)

[注]若要删除最后一个结点，p->next为NULL，故q不存在data域，这种解法不适用了。

5）单链表的查找

按位查找

LNode * GetElem(LinkList L,int i)
{
    if(i<0) return NULL;
    LNode * p=L;
    int j=0;
    while(j<i&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    return p;
}

平均时间复杂度:O（n）

按值查找

LNode * GetElem(LinkList L,int i)
{
    if(i<0) return NULL;
    LNode * p=L;
    int j=0;
    while(j<i&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    return p;
}

表长

int ListLength(LinkList L)
{
    int i=0;
    LNode * p=L->next;
    while(p!=NULL)
    {
        p=p->next;
        i++;
    }
    return i;
}

6）单链表的建立

尾插法

可以通过每一次插入都调用

while 循环
{
    //取数据元素
    ListInsert(LinkList,length+1,e); //插至链表尾部
    length++;
}

但每次插入一个元素都要从头开始遍历，时间复杂度为O（n^2);可以通过一个指针来指向表尾，每次移动尾指针改良；

LinkList Link_TailInsert(LinkList &L) //正向建立单链表
{
    //初始化
    L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
    LNode * p=L; //指针p指向头结点
    //用户输入数据、并依次生成结点,直至用户输入9999退出
    int x;
    scanf("%d",&x);
    while(x!=9999)
    {
        LNode * q=(LNode *)malloc(sizeof(LNode));
        p->next=q;
        p=q;
        p->data=x;
        scanf("%d",&x);
    }
    p->next=NULL; //尾指针置空，不做这一步，最后尾指针会指向自己
    return L;
}

头插法

LinkList Link_HeadInsert(LinkList &L)
{
    int a;
    LNode * p;
    //初始化
    L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
    L->next=NULL; //必须指向NULL
    //输入数据、并把输入的数据插入到头结点之后
    scanf("%d",&a);
    while(a!=9999)
    {
        p=(LNode *)malloc(sizeof(LNode));
        p->data=a;
        p->next=L->next;
        L->next=p;
        scanf("%d",&a)；
    }
    return L;
}

头插法的应用：实现链表的逆置

//法一：通过新建一个链表实现
LinkList ReverseList(LinkList &L)
{
    LNode * p; //指针
    LinkList s=(LNode *)malloc(sizeof(LNode)); //生成一个新的链表
    s->next=NULL;
    while(L->next!=NULL)
    {
        //从头开始依次取下链表L的结点
        p=L->next; //指向要被取下的结点
        L->next=p->next;
        //把取下的数据使用头插法插入到新的链表s
        p->next=s->next;
        s->next=p;
    }
    return s;
}

//法二：就地转置，将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法），直到最后一个结点为止。 
LinkList ReverseList2(LinkList &L)
{
    LNode *p,*q; //p指针指向位序为一的结点
    p=L->next;
    L->next=NULL; //取下头结点
    //使用头插法把结点从头依次插入头结点后面
    while(p!=NULL)
    {
        q=p->next; 
        p->next=L->next;
        L->next=p;
        p=q;
    }
    return L;
}

其实以上两个方法基本上原理是相同的，用法二更好，因为是原地转置，用法一也可以再最后把头指针L->s;