线性表的链式存储结构——单链表

单链表是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身信息外，还需要存放一个指向其后继的指针。

data

next

单链表中结点类型的描述如下：

typedef struct LNode {            //定义单链表结点类型
    ElemType data;                //数据域
    struct LNode* next;           //指针域
}LNode,*LinkList;    

 

头结点和头指针的区分：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点后，可以带来两个优点：

①由于第一个数据结点的位置被存放头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。

②无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到统一。

 

单链表上基本操作的实现

1.采用头插法建立单链表

LinkList List_HeadInsert(LinkList& L) {    //逆向建立单链表
    LNode* s; int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点
    L->next = NULL;                        //初始为空链表
    printf("输入x的值：");
    scanf("%d", &x);                    //输入结点的值
    while (x != 9999) {
        s = (LNode*)malloc(sizeof(LNode));    //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;                    //将新结点插入表中，L为头指针
        printf("输入x的值：");
        scanf("%d", &x);
    }
    return L;
}

2.采用尾插法建立单链表

LinkList List_TailInsert(LinkList& L) {    //正向向建立单链表
    int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点

    LNode* r = L;
    printf("输入x的值：");
    scanf("%d", &x);                    //输入结点的值
    while (x != 9999) {
        LNode* s = (LNode*)malloc(sizeof(LNode));    //创建新结点
        s->data = x;
        r->next = s;
        r = s;                            //r指向新的表位结点
        printf("输入x的值：");
        scanf("%d", &x);
    }
    r->next = NULL;                        //尾结点指针置空
    return L;
}

3.按位置查找

LNode* GetElem(LinkList L, int i) {
    int j = 1;            //计数，初始为1
    LNode* p = L->next;    //头结点指针赋值给p
    if (i == 0)
        return L;        //若i等于0，则返回头结点
    if (i < 1)
        return NULL;    //若i无效，则返回NULL
    while (p && j < i) {    //若从第1个结点开始找，查找第i个结点
        p = p->next;
        j++;
    }
    return p;
}

4.按值查找

void LocateElem(LinkList L, int e) {
    LNode* p = L->next;
    int i = 1;
    while (p && e != p->data) {
        p = p->next;
        i++;
    }
    if (p)
        printf("该节点的位置为：%d", i);
    else
        printf("为查找到此数值。");
}

5.插入结点（前插）

LNode* HInsertLNode(LinkList& L, LNode* s, int i) {
    LNode* p = GetElem(L, i - 1);
    s->next = p->next;
    p->next = s;
    return L;
}

6.插入结点（后插）

LNode* TInsertLNode(LinkList& L, LNode* s, int i) {
    LNode* p = GetElem(L, i);
    s->next = p->next;
    p->next = s;
    return L;
}

 7.删除结点（按位置）

LNode* DeleteLNode(LinkList& L, int i) {
    LNode* p = GetElem(L, i - 1);        //查找删除结点的位置
    LNode* q = p->next;                    //令q指向被删除的结点
    p->next = q->next;                    //将q指向结点从链中断开
    free(q);
    return p;
}

8.删除结点（按结点）

void DeleteLNodE(LNode* p) {
    LNode* q=p->next;                //创建q指向p的后继结点
    p->data = q->data;                //和后继节点交换数据
    p->next = q->next;                //将*q结点从链中删除
    free(p);                        //释放后继结点的存储空间
}

9.输出单链表

void Print(LinkList& L) {
    LNode* p = L->next;
    printf("输出链表：");
    while (p)
    {
        printf("%3d", p->data);
        p = p->next;
    }
}