单链表的九种基本操作(2021.5)

1. 定义单链表结点Node:

    单链表的结点由数据域和指针域共同构成, 数据域负责存储当前结点的数据信息, 指针域负责存储其直接后继结点在内存中的地址信息.

/* 单链表结点的定义 */
struct Node
{
    short data;
    struct Node* next;
};

2. 初始化头结点:

[注]通过malloc函数申请内存空间不一定会成功, 要根据其返回值判断是否申请到需要的内存空间. 如果malloc函数返回一个非NULL的地址信息, 那么说明内存空间申请成功, 该地址就是已申请内存空间的起始地址; 如果malloc函数返回NULL, 那么说明没有申请到内存空间, 此时程序应另作处理. 另外, 在创建好头结点后, 令链表尾指针rear指向头结点, 即rear = head, 设置尾指针rear可极大地方便我们获取表尾元素的信息.

/* 创建头结点 */
short InitLinkList(struct Node* &head, struct Node* &rear)
{
    head = (struct Node*)malloc(sizeof(struct Node));
    if(head != NULL)
    {
        /* 头结点申请成功 */
        printf("头结点申请成功.\n");
        head -> data = 0;
        head -> next = NULL;
        rear = head;
        return 1;
    }
    else
    {
        printf("头结点申请失败.\n");
        return -1;
    }
}

3. 数据的插入(分为头插法和尾插法):

(1)尾插法:

    这