四  单链表(1)

四 单链表(1)

概述

单链表是链式存储的线性表,单链表为线性表中的每一个数据单元开辟一块空间,每块空间在物理位置上并不连续,每块空间中都有一个指针域用来存储下一块空间的位置,这样每一块空间在逻辑上便有了联系(逻辑上线性相连,每一块空间里都有下一个空间的地址)。

如下图所示:

整理一下:

头结点(head)的相关问题

每一个单链表都有一个头指针,头指针始终指向单链表的第一个空间,若有头结点则指向头结点,没有头结点指向第一个结点。

通常情况下,单链表都有一个头结点,这个结点并不存储数据(数据域实际可以使用,但通常不使用),但其指针域指向第一个结点所在的位置。

使用头结点之后,链表非空与空的两种情况下,无须进行特殊情况处理,因为头指针必定不为空。

在不实使用头结点的情况下,链表为空表时,头指针L为NULL。

单链表结点结构体的定义

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

data是数据域,用来存储数据的。

next是指针域,用来存放下一个空间的地址,next是一个结构体指针类型的变量,只能存放LNode类型结构体的地址。

LinkList是结构体LNode类型的指针。

每一个结点占用一块空间,每一块空间物理上不连续,每一个结点使用next指针域指向下一结点的位置。

图片:

单链表的创建

1.头插法建立单链表

LinkList CreatList1(LinkList  &L){
    LNode *s;int x;
    L = (LinkList)malloc(sizeof(LNode));
    L -> next = NULL;
    scanf("%d",&x);
    while(x != 9999){
        s = (Node*)malloc(sizeof(Node));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
   return L;
}

第一步,s->next = L->next; 将头结点之后的东西转接到新结点后面。

第二步, L->next = s; 将新结点接到头结点后面,成为第一个结点。

*** 第二步的时候头结点的指针域改变,指向a2的链会断开。

2.尾插法建立单链表


LinkList CreatList2(LinkList &L){
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r = L;
    scanf("%d",&x);
    while(x != 9999){
        s = (Node*)malloc(sizeof(Node));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d",&x);
    }
    r -> next = NULL;
    return L;
}

第一步,s = (Node*)malloc(sizeof(Node));s->data = x;开辟一个新的节点;

第二步,r->next = s;将新的结点接到最后一个结点后面。其中 指针 R 始终指向单链表的最后一个结点,每次插入一个新的结点,新结点的地址S最后要赋值给R,所以R每次都指向最后一个结点。

3.建立单链表的时间复杂度

  • 两种建表方式的时间复杂度都为 O(n) 。

编辑于 2017-08-02 11:44