线性表链式存储结构下基本操作的实现（初始化、建表、取值、插入、删除、两个非递减有序线性表的归并等归并等）C语言版

1. 初始化

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

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node, *LinkList;

// 初始化链表
LinkList initList() {
    LinkList head = (LinkList) malloc(sizeof(Node));  // 分配头结点空间
    if (head == NULL) {  // 内存分配失败
        printf("内存分配失败！\n");
        exit(-1);
    }
    head->next = NULL;  // 头结点初始为空
    return head;
}

2. 建表

// 建立链表
void createList(LinkList head) {
    Node *p = head;
    int data;
    printf("请输入元素值，以-1结束：\n");
    while (scanf("%d", &data) != EOF && data != -1) {
        Node *newNode = (Node *) malloc(sizeof(Node));  // 创建新结点
        if (newNode == NULL) {  // 内存分配失败
            printf("内存分配失败！\n");
            exit(-1);
        }
        newNode->data = data;
        newNode->next = NULL;
        p->next = newNode;  // 将新结点插入到链表尾部
        p = newNode;        // 指向链表尾部
    }
}

3. 取值

// 获取指定位置结点的值
int getElem(LinkList head, int index) {
    Node *p = head->next;
    int i = 1;
    while (p != NULL && i < index) {  // 寻找第i个结点
        p = p->next;
        i++;
    }
    if (p == NULL || i > index) {  // 未找到
        printf("未找到该元素！\n");
        exit(-1);
    }
    return p->data;  // 返回结点值
}

4. 插入

// 在指定位置插入结点
void insertElem(LinkList head, int index, int data) {
    Node *p = head;
    int i = 0;
    while (p != NULL && i < index - 1) {  // 寻找第i-1个结点
        p = p->next;
        i++;
    }
    if (p == NULL || i > index - 1) {  // 未找到
        printf("未找到该元素！\n");
        exit(-1);
    }
    Node *newNode = (Node *) malloc(sizeof(Node));  // 创建新结点
    if (newNode == NULL) {  // 内存分配失败
        printf("内存分配失败！\n");
        exit(-1);
    }
    newNode->data = data;
    newNode->next = p->next;  // 将新结点插入到链表中
    p->next = newNode;
}

5. 删除

// 删除指定位置结点
void deleteElem(LinkList head, int index) {
    Node *p = head;
    int i = 0;
    while (p != NULL && i < index - 1) {  // 寻找第i-1个结点
        p = p->next;
        i++;
    }
    if (p == NULL || i > index - 1 || p->next == NULL) {  // 未找到
        printf("未找到该元素！\n");
        exit(-1);
    }
    Node *temp = p->next;
    p->next = temp->next;  // 删除结点
    free(temp);           // 释放空间
}

6. 两个非递减有序线性表的归并

// 归并两个非递减有序线性表
LinkList mergeList(LinkList head1, LinkList head2) {
    Node *p = head1->next, *q = head2->next;
    LinkList newList = initList();  // 初始化新链表
    Node *r = newList;              // 指向新链表尾部
    while (p != NULL && q != NULL) {  // 依次比较两个链表的元素
        if (p->data <= q->data) {
            r->next = p;  // 插入p结点
            r = p;        // 指向新链表尾部
            p = p->next;  // p指针后移
        } else {
            r->next = q;  // 插入q结点
            r = q;        // 指向新链表尾部
            q = q->next;  // q指针后移
        }
    }
    if (p != NULL) r->next = p;  // 将剩余的结点插入新链表
    if (q != NULL) r->next = q;
    return newList;
}