线性表核心概念

由n（n ≥ 0）个相同类型的数据元素组成的有限序列即为线性表。其逻辑特征包括：存在唯一首元素与末元素，除首元素外每个节点仅有一个前驱，除末元素外每个节点仅有一个后继。

存储方式分类

• 顺序存储：数据元素在内存中连续存放，通过下标访问。
• 链式存储：元素可分散在非连续内存区域，通过指针链接。

单向链表实现

// 定义节点结构
typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode, *LinkList;

// 初始化空链表
int initialize(LinkList &list) {
    list = (ListNode*)malloc(sizeof(ListNode));
    if (!list) return -1;
    list->next = nullptr;
    return 1;
}

// 按位置获取元素
int getElement(LinkList list, int pos, int &result) {
    ListNode *curr = list->next;
    int index = 1;
    while (curr && index < pos) {
        curr = curr->next;
        index++;
    }
    if (!curr || index > pos) return -1;
    result = curr->value;
    return 1;
}

// 头插法构建链表
int createHeadInsert(LinkList &list, int count) {
    list = (ListNode*)malloc(sizeof(ListNode));
    list->next = nullptr;
    for (int i = 0; i < count; ++i) {
        ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        std::cin >> node->value;
        node->next = list->next;
        list->next = node;
    }
    return 1;
}

// 遍历输出
void traverse(LinkList list) {
    ListNode *curr = list->next;
    while (curr) {
        std::cout << curr->value << " ";
        curr = curr->next;
    }
}

双向链表设计

// 双向节点定义
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode, *DLinkList;

// 插入操作（按位置）
int insertAt(DLinkList &list, int pos, int val) {
    DNode *current = list;
    int index = 0;
    while (current && index < pos) {
        current = current->next;
        index++;
    }
    if (!current || index > pos) return -1;

    DNode *newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->next = current;
    newNode->prev = current->prev;
    current->prev->next = newNode;
    current->prev = newNode;
    return 1;
}

循环链表构造

将尾节点的 next 指针指向头节点，形成闭环。遍历时需判断是否回到起点。

void makeCircular(LinkList list) {
    ListNode *tail = list->next;
    while (tail->next) tail = tail->next;
    tail->next = list->next;
}

一元多项式加法

基于指数排序的链表合并，同类项系数相加，结果保留非零项。

int addPolynomials(LinkList &A, LinkList &B) {
    LinkList p1 = A->next, p2 = B->next;
    LinkList resultTail = A;

    while (p1 && p2) {
        if (p1->exp == p2->exp) {
            float sum = p1->coef + p2->coef;
            if (sum != 0.0f) {
                resultTail->next = p1;
                p1->coef = sum;
                resultTail = p1;
            }
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp < p2->exp) {
            resultTail->next = p1;
            resultTail = p1;
            p1 = p1->next;
        } else {
            resultTail->next = p2;
            resultTail = p2;
            p2 = p2->next;
        }
    }
    resultTail->next = p1 ? p1 : p2;
    free(B);
    return 1;
}

有序表合并算法

使用双指针技术，从两个有序数组中逐个选取最小值插入新数组。

int mergeSortedArrays(int* A, int lenA, int* B, int lenB, int* C) {
    int i = 0, j = 0, k = 0;
    while (i < lenA && j < lenB) {
        if (A[i] <= B[j]) C[k++] = A[i++];
        else C[k++] = B[j++];
    }
    while (i < lenA) C[k++] = A[i++];
    while (j < lenB) C[k++] = B[j++];
    return k;
}