线性表是最基本、最常用的一种数据结构，它是由n个数据元素组成的有限序列。线性表在计算机科学中应用广泛，是许多高级数据结构和算法的基础。本文将全面系统地介绍线性表的相关概念、实现原理、操作方法和实际应用。

1. 线性表概述

1.1 线性表的定义

线性表（Linear List）是由n（n≥0）个数据元素（节点）a₁，a₂，…，an组成的有限序列。数据元素的个数n定义为线性表的长度，n=0时称为空表。

线性表的形式化表示为：(a₁, a₂, a₃, …, an)

其中：

• a₁是第一个数据元素，称为表头元素
• an是最后一个数据元素，称为表尾元素
• 当i=1,2,…,n-1时，ai有且仅有一个直接后继ai+1
• 当i=2,3,…,n时，ai有且仅有一个直接前驱ai-1

1.2 线性表的特点

1. 存在唯一的第一元素：线性表中存在唯一的一个被称为"第一个"的数据元素
2. 存在唯一的最后元素：线性表中存在唯一的一个被称为"最后一个"的数据元素
3. 除第一个元素外，每个元素都有且仅有一个直接前驱
4. 除最后一个元素外，每个元素都有且仅有一个直接后继

1.3 线性表的抽象数据类型定义

ADT List {
    数据对象：D = {ai | ai ∈ ElemSet, i = 1, 2, ..., n, n ≥ 0}
    数据关系：R = {<ai-1, ai> | ai-1, ai ∈ D, i = 2, 3, ..., n}
    
    基本操作：
        InitList(&L)：初始化线性表
        DestroyList(&L)：销毁线性表
        ClearList(&L)：清空线性表
        ListEmpty(L)：判断线性表是否为空
        ListLength(L)：获取线性表长度
        GetElem(L, i, &e)：获取第i个元素
        LocateElem(L, e, compare())：定位元素位置
        PriorElem(L, cur_e, &pre_e)：获取前驱元素
        NextElem(L, cur_e, &next_e)：获取后继元素
        ListInsert(&L, i, e)：插入元素
        ListDelete(&L, i, &e)：删除元素
        ListTraverse(L, visit())：遍历线性表
}

2. 顺序表

2.1 顺序表的概念

顺序表是用一段地址连续的存储单元依次存储线性表的数据元素，通常采用数组实现。顺序表的特点是逻辑上相邻的元素在物理存储上也相邻。

2.2 顺序表的实现

#include <iostream>
#include <cstdlib>
using namespace std;

#define MAXSIZE 100  // 顺序表的最大长度
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;  // 状态码类型
typedef int ElemType;  // 元素类型

// 顺序表的结构定义
typedef struct {
    ElemType *elem;  // 存储空间基地址
    int length;      // 当前长度
    int listsize;    // 当前分配的存储容量
} SqList;

// 初始化顺序表
Status InitList(SqList &L) {
    L.elem = new ElemType[MAXSIZE];  // 分配数组空间
    if (!L.elem) {
        exit(OVERFLOW);  // 存储分配失败
    }
    L.length = 0;        // 空表长度为0
    L.listsize = MAXSIZE; // 初始存储容量
    return OK;
}

// 销毁顺序表
Status DestroyList(SqList &L) {
    if (L.elem) {
        delete[] L.elem;  // 释放存储空间
        L.elem = NULL;
    }
    L.length = 0;
    L.listsize = 0;
    return OK;
}

// 清空顺序表
Status ClearList(SqList &L) {
    L.length = 0;  // 将线性表的长度置为0
    return OK;
}

// 判断顺序表是否为空
Status ListEmpty(SqList L) {
    return L.length == 0 ? true : false;
}

// 获取顺序表长度
int ListLength(SqList L) {
    return L.length;
}

// 获取第i个元素
Status GetElem(SqList L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return ERROR;  // 判断i值是否合理
    }
    e = L.elem[i - 1];  // 第i-1单元存储着第i个数据
    return OK;
}

// 定位元素位置
int LocateElem(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) {
    for (int i = 0; i < L.length; i++) {
        if (compare(L.elem[i], e)) {
            return i + 1;  // 返回序号
        }
    }
    return 0;  // 查找失败
}

// 比较函数
Status equal(ElemType a, ElemType b) {
    return a == b;
}

// 获取前驱元素
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e) {
    int pos = LocateElem(L, cur_e, equal);
    if (pos <= 1) {
        return ERROR;  // 第一个元素无前驱
    }
    pre_e = L.elem[pos - 2];  // 前驱元素
    return OK;
}

// 获取后继元素
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e) {
    int pos = LocateElem(L, cur_e, equal);
    if (pos == 0 || pos == L.length) {
        return ERROR;  // 最后一个元素无后继
    }
    next_e = L.elem[pos];  // 后继元素
    return OK;
}

// 插入元素
Status ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) {
        return ERROR;  // i值不合法
    }
    if (L.length == L.listsize) {
        return ERROR;  // 当前存储空间已满
    }
    
    // 将第i个元素及之后的元素后移
    for (int j = L.length - 1; j >= i - 1; j--) {
        L.elem[j + 1] = L.elem[j];
    }
    L.elem[i - 1] = e;  // 插入新元素
    L.length++;         // 表长增1
    return OK;
}

// 删除元素
Status ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        return ERROR;  // i值不合法
    }
    e = L.elem[i - 1];  // 被删除元素的值赋给e
    
    // 将第i个位置之后的元素前移
    for (int j = i; j < L.length; j++) {
        L.elem[j - 1] = L.elem[j];
    }
    L.length--;  // 表长减1
    return OK;
}

// 遍历顺序表
Status ListTraverse(SqList L, Status (*visit)(ElemType)) {
    for (int i = 0; i < L.length; i++) {
        if (!visit(L.elem[i])) {
            return ERROR;
        }
    }
    return OK;
}

// 访问函数
Status visit(ElemType e) {
    cout << e << " ";
    return OK;
}

// 打印顺序表
void PrintList(SqList L) {
    cout << "顺序表内容：";
    for (int i = 0; i < L.length; i++) {
        cout << L.elem[i] << " ";
    }
    cout << endl;
}

// 顺序表操作示例
void SequenceListDemo() {
    SqList L;
    ElemType e;
    
    cout << "=== 顺序表操作演示 ===" << endl;
    
    // 初始化顺序表
    InitList(L);
    cout << "顺序表初始化成功！" << endl;
    
    // 插入元素
    for (int i = 1; i <= 10; i++) {
        ListInsert(L, i, i * 2);  // 插入2,4,6,...,20
    }
    cout << "插入10个元素后：";
    PrintList(L);
    
    // 获取元素
    GetElem(L, 5, e);
    cout << "第5个元素是：" << e << endl;
    
    // 定位元素
    int pos = LocateElem(L, 12, equal);
    cout << "元素12的位置是：" << pos << endl;
    
    // 删除元素
    ListDelete(L, 3, e);
    cout << "删除第3个元素：" << e << endl;
    cout << "删除后：";
    PrintList(L);
    
    // 获取前驱和后继
    PriorElem(L, 8, e);
    cout << "8的前驱是：" << e << endl;
    NextElem(L, 8, e);
    cout << "8的后继是：" << e << endl;
    
    // 销毁顺序表
    DestroyList(L);
    cout << "顺序表已销毁！" << endl << endl;
}

2.3 顺序表的优缺点分析

优点：

1. 随机访问：可以通过下标直接访问任何元素，时间复杂度为O(1)
2. 存储密度高：不需要额外空间存储元素间的关系
3. 缓存友好：连续存储有利于CPU缓存

缺点：

1. 插入删除效率低：平均需要移动一半元素，时间复杂度为O(n)
2. 长度固定：需要预先分配固定大小的存储空间
3. 扩容困难：当存储空间不足时，扩容需要重新分配内存和复制数据

2.4 顺序表的应用场景

1. 数据量固定或变化不大的情况
2. 需要频繁随机访问元素的场景
3. 对内存使用效率要求较高的场景
4. 元素大小相对固定的情况

3. 链表

链表通过指针将一组零散的内存块串联起来，每个节点包含数据域和指针域。链表不需要连续的内存空间，可以动态地进行内存分配。

3.1 单链表

3.1.1 单链表的概念

单链表是最简单的链表结构，每个节点包含数据域和指向下一个节点的指针域。

3.1.2 单链表的实现

#include <iostream>
using namespace std;

typedef int ElemType;
typedef int Status;

#define OK 1
#define ERROR 0

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

// 初始化单链表
Status InitList(LinkList &L) {
    L = new LNode;  // 创建头结点
    if (!L) {
        return ERROR;  // 内存分配失败
    }
    L->next = NULL;   // 头结点指针域置空
    return OK;
}

// 判断单链表是否为空
Status ListEmpty(LinkList L) {
    return L->next == NULL;
}

// 销毁单链表
Status DestroyList(LinkList &L) {
    LNode *p;
    while (L) {
        p = L;
        L = L->next;
        delete p;
    }
    return OK;
}

// 清空单链表
Status ClearList(LinkList &L) {
    LNode *p, *q;
    p = L->next;  // p指向第一个结点
    while (p) {
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;  // 头结点指针域置空
    return OK;
}

// 获取单链表长度
int ListLength(LinkList L) {
    int length = 0;
    LNode *p = L->next;  // p指向第一个结点
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

// 获取第i个元素
Status GetElem(LinkList L, int i, ElemType &e) {
    LNode *p = L->next;  // p指向第一个结点
    int j = 1;
    
    while (p && j < i) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i) {
        return ERROR;  // 第i个元素不存在
    }
    
    e = p->data;
    return OK;
}

// 定位元素位置
LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}

// 插入元素
Status ListInsert(LinkList &L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    
    // 寻找第i-1个结点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i - 1) {
        return ERROR;  // i值不合法
    }
    
    LNode *s = new LNode;  // 创建新结点
    s->data = e;
    s->next = p->next;
    p->next = s;
    
    return OK;
}

// 删除元素
Status ListDelete(LinkList &L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    
    // 寻找第i-1个结点
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    
    if (!(p->next) || j > i - 1) {
        return ERROR;  // 删除位置不合理
    }
    
    LNode *q = p->next;  // q指向被删除结点
    p->next = q->next;
    e = q->data;
    delete q;
    
    return OK;
}

// 头插法创建单链表
void CreateList_H(LinkList &L, int n) {
    L = new LNode;
    L->next = NULL;
    
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cout << "请输入第" << i + 1 << "个元素的值：";
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

// 尾插法创建单链表
void CreateList_R(LinkList &L, int n) {
    L = new LNode;
    L->next = NULL;
    LNode *r = L;  // 尾指针
    
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cout << "请输入第" << i + 1 << "个元素的值：";
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

// 遍历单链表
Status ListTraverse(LinkList L) {
    LNode *p = L->next;
    cout << "单链表内容：";
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    return OK;
}

// 单链表反转
Status ReverseList(LinkList &L) {
    if (!L || !L->next) {
        return ERROR;  // 空表或只有一个元素
    }
    
    LNode *prev = NULL;
    LNode *curr = L->next;
    LNode *next = NULL;
    
    while (curr) {
        next = curr->next;  // 保存下一个节点
        curr->next = prev;  // 反转指针
        prev = curr;        // 前移prev
        curr = next;        // 前移curr
    }
    
    L->next = prev;  // 头结点指向新的第一个节点
    return OK;
}

// 查找中间节点
LNode *FindMiddleNode(LinkList L) {
    if (!L || !L->next) {
        return L;  // 空表或只有一个节点
    }
    
    LNode *slow = L->next;  // 慢指针
    LNode *fast = L->next;  // 快指针
    
    while (fast && fast->next) {
        slow = slow->next;       // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
    }
    
    return slow;
}

// 检测环
bool HasCycle(LinkList L) {
    if (!L || !L->next) {
        return false;
    }
    
    LNode *slow = L->next;
    LNode *fast = L->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;  // 快慢指针相遇，存在环
        }
    }
    
    return false;
}

// 单链表操作示例
void SinglyLinkedListDemo() {
    LinkList L;
    ElemType e;
    
    cout << "=== 单链表操作演示 ===" << endl;
    
    // 初始化单链表
    InitList(L);
    cout << "单链表初始化成功！" << endl;
    
    // 插入元素
    for (int i = 1; i <= 10; i++) {
        ListInsert(L, i, i * 3);  // 插入3,6,9,...,30
    }
    cout << "插入10个元素后：";
    ListTraverse(L);
    
    // 获取元素
    GetElem(L, 4, e);
    cout << "第4个元素是：" << e << endl;
    
    // 定位元素
    LNode *pos = LocateElem(L, 15);
    if (pos) {
        cout << "元素15的地址是：" << pos << "，值是：" << pos->data << endl;
    }
    
    // 删除元素
    ListDelete(L, 5, e);
    cout << "删除第5个元素：" << e << endl;
    cout << "删除后：";
    ListTraverse(L);
    
    // 反转链表
    ReverseList(L);
    cout << "反转后：";
    ListTraverse(L);
    
    // 查找中间节点
    LNode *middle = FindMiddleNode(L);
    if (middle) {
        cout << "中间节点的值是：" << middle->data << endl;
    }
    
    // 检测环
    cout << "链表是否存在环：" << (HasCycle(L) ? "是" : "否") << endl;
    
    // 清空链表
    ClearList(L);
    cout << "链表已清空！" << endl;
    
    // 销毁链表
    DestroyList(L);
    cout << "链表已销毁！" << endl << endl;
}

3.2 双向链表

3.2.1 双向链表的概念

双向链表在单链表的基础上增加了一个指向前驱节点的指针，使得可以从两个方向遍历链表。

3.2.2 双向链表的实现

#include <iostream>
using namespace std;

typedef int ElemType;
typedef int Status;

#define OK 1
#define ERROR 0

// 双向链表节点定义
typedef struct DuLNode {
    ElemType data;           // 数据域
    struct DuLNode *prior;   // 前驱指针
    struct DuLNode *next;    // 后继指针
} DuLNode, *DuLinkList;

// 初始化双向链表
Status InitList(DuLinkList &L) {
    L = new DuLNode;  // 创建头结点
    if (!L) {
        return ERROR;
    }
    L->prior = NULL;
    L->next = NULL;
    return OK;
}

// 在节点p之后插入节点s
Status ListInsertAfter(DuLinkList &L, DuLNode *p, ElemType e) {
    if (!p) return ERROR;
    
    DuLNode *s = new DuLNode;
    s->data = e;
    
    s->next = p->next;
    s->prior = p;
    
    if (p->next) {
        p->next->prior = s;
    }
    p->next = s;
    
    return OK;
}

// 在节点p之前插入节点s
Status ListInsertBefore(DuLinkList &L, DuLNode *p, ElemType e) {
    if (!p) return ERROR;
    
    DuLNode *s = new DuLNode;
    s->data = e;
    
    s->prior = p->prior;
    s->next = p;
    
    if (p->prior) {
        p->prior->next = s;
    } else {
        L = s;  // 更新头指针
    }
    p->prior = s;
    
    return OK;
}

// 删除节点p
Status ListDelete(DuLinkList &L, DuLNode *p, ElemType &e) {
    if (!p) return ERROR;
    
    e = p->data;
    
    if (p->prior) {
        p->prior->next = p->next;
    } else {
        L = p->next;  // 更新头指针
    }
    
    if (p->next) {
        p->next->prior = p->prior;
    }
    
    delete p;
    return OK;
}

// 遍历双向链表（向前）
void ListTraverseForward(DuLinkList L) {
    DuLNode *p = L;
    cout << "向前遍历：";
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 遍历双向链表（向后）
void ListTraverseBackward(DuLinkList L) {
    if (!L) return;
    
    // 找到尾节点
    DuLNode *p = L;
    while (p->next) {
        p = p->next;
    }
    
    cout << "向后遍历：";
    while (p) {
        cout << p->data << " ";
        p = p->prior;
    }
    cout << endl;
}

// 双向链表操作示例
void DoublyLinkedListDemo() {
    DuLinkList L;
    ElemType e;
    
    cout << "=== 双向链表操作演示 ===" << endl;
    
    // 初始化双向链表
    InitList(L);
    L->data = 0;  // 头结点数据
    
    // 创建一些节点
    DuLNode *current = L;
    for (int i = 1; i <= 5; i++) {
        ListInsertAfter(L, current, i * 10);
        current = current->next;
    }
    
    cout << "初始链表：" << endl;
    ListTraverseForward(L);
    ListTraverseBackward(L);
    
    // 在第二个节点后插入新节点
    DuLNode *secondNode = L->next;
    if (secondNode) {
        ListInsertAfter(L, secondNode, 99);
        cout << "在第二个节点后插入99后：" << endl;
        ListTraverseForward(L);
    }
    
    // 删除第三个节点
    DuLNode *thirdNode = L->next->next;
    if (thirdNode) {
        ListDelete(L, thirdNode, e);
        cout << "删除第三个节点：" << e << " 后：" << endl;
        ListTraverseForward(L);
    }
    
    cout << endl;
}

3.3 循环链表

3.3.1 循环链表的概念

循环链表是另一种形式的链式存储结构，其特点是表中最后一个节点的指针指向头节点，整个链表形成一个环。

3.3.2 循环链表的实现

#include <iostream>
using namespace std;

typedef int ElemType;
typedef int Status;

#define OK 1
#define ERROR 0

// 循环链表节点定义
typedef struct CNode {
    ElemType data;
    struct CNode *next;
} CNode, *CircularList;

// 初始化循环链表
Status InitList(CircularList &L) {
    L = new CNode;  // 创建头结点
    if (!L) {
        return ERROR;
    }
    L->next = L;    // 指向自己，形成环
    return OK;
}

// 在循环链表尾部插入节点
Status ListInsert(CircularList &L, ElemType e) {
    CNode *s = new CNode;
    s->data = e;
    
    // 如果是空表
    if (L->next == L) {
        s->next = L;
        L->next = s;
    } else {
        // 找到尾节点
        CNode *p = L->next;
        while (p->next != L) {
            p = p->next;
        }
        
        s->next = L;
        p->next = s;
    }
    
    return OK;
}

// 遍历循环链表
void ListTraverse(CircularList L) {
    if (L->next == L) {
        cout << "循环链表为空" << endl;
        return;
    }
    
    CNode *p = L->next;
    cout << "循环链表：";
    
    while (p != L) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 约瑟夫环问题
void JosephusProblem(int n, int m) {
    CircularList L;
    InitList(L);
    
    // 创建循环链表
    for (int i = 1; i <= n; i++) {
        ListInsert(L, i);
    }
    
    cout << "约瑟夫环问题：n=" << n << ", m=" << m << endl;
    cout << "出列顺序：";
    
    CNode *p = L->next;  // 从第一个节点开始
    CNode *pre = L;      // p的前驱
    
    // 找到尾节点
    while (pre->next != L) {
        pre = pre->next;
    }
    pre->next = L->next;  // 形成不带头节点的循环链表
    
    p = L->next;
    delete L;  // 删除头结点
    
    int count = 1;
    while (p->next != p) {
        if (count == m) {
            // 删除当前节点
            cout << p->data << " ";
            pre->next = p->next;
            delete p;
            p = pre->next;
            count = 1;
        } else {
            pre = p;
            p = p->next;
            count++;
        }
    }
    
    cout << p->data << endl;
    delete p;
}

// 循环链表操作示例
void CircularLinkedListDemo() {
    CircularList L;
    
    cout << "=== 循环链表操作演示 ===" << endl;
    
    // 初始化循环链表
    InitList(L);
    
    // 插入元素
    for (int i = 1; i <= 8; i++) {
        ListInsert(L, i);
    }
    
    cout << "循环链表内容：";
    ListTraverse(L);
    
    // 约瑟夫环问题演示
    JosephusProblem(8, 3);
    
    cout << endl;
}

4. 线性表的应用实例

4.1 多项式运算

#include <iostream>
using namespace std;

// 多项式项的定义
typedef struct PNode {
    float coef;     // 系数
    int expn;       // 指数
    struct PNode *next;
} PNode, *Polynomial;

// 创建多项式
void CreatePolyn(Polynomial &P, int n) {
    P = new PNode;
    P->next = NULL;
    
    for (int i = 0; i < n; i++) {
        PNode *s = new PNode;
        cout << "请输入第" << i + 1 << "项的系数和指数：";
        cin >> s->coef >> s->expn;
        
        // 寻找插入位置
        PNode *pre = P;
        PNode *q = P->next;
        
        while (q && q->expn < s->expn) {
            pre = q;
            q = q->next;
        }
        
        s->next = q;
        pre->next = s;
    }
}

// 多项式相加
void AddPolyn(Polynomial &Pa, Polynomial &Pb) {
    PNode *p1 = Pa->next;
    PNode *p2 = Pb->next;
    PNode *p3 = Pa;
    PNode *temp;
    
    while (p1 && p2) {
        if (p1->expn == p2->expn) {
            float sum = p1->coef + p2->coef;
            
            if (sum != 0) {
                p1->coef = sum;
                p3->next = p1;
                p3 = p1;
                p1 = p1->next;
                
                temp = p2;
                p2 = p2->next;
                delete temp;
            } else {
                temp = p1;
                p1 = p1->next;
                delete temp;
                
                temp = p2;
                p2 = p2->next;
                delete temp;
            }
        } else if (p1->expn < p2->expn) {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }
    }
    
    p3->next = p1 ? p1 : p2;
    delete Pb;
}

// 打印多项式
void PrintPolyn(Polynomial P) {
    PNode *p = P->next;
    bool firstTerm = true;
    
    while (p) {
        if (p->coef > 0 && !firstTerm) {
            cout << "+";
        }
        
        if (p->expn == 0) {
            cout << p->coef;
        } else if (p->expn == 1) {
            if (p->coef == 1) {
                cout << "x";
            } else if (p->coef == -1) {
                cout << "-x";
            } else {
                cout << p->coef << "x";
            }
        } else {
            if (p->coef == 1) {
                cout << "x^" << p->expn;
            } else if (p->coef == -1) {
                cout << "-x^" << p->expn;
            } else {
                cout << p->coef << "x^" << p->expn;
            }
        }
        
        firstTerm = false;
        p = p->next;
    }
    cout << endl;
}

// 多项式运算示例
void PolynomialDemo() {
    Polynomial P1, P2;
    
    cout << "=== 多项式运算演示 ===" << endl;
    
    cout << "创建第一个多项式（3项）：" << endl;
    CreatePolyn(P1, 3);
    cout << "P1 = ";
    PrintPolyn(P1);
    
    cout << "创建第二个多项式（3项）：" << endl;
    CreatePolyn(P2, 3);
    cout << "P2 = ";
    PrintPolyn(P2);
    
    cout << "P1 + P2 = ";
    AddPolyn(P1, P2);
    PrintPolyn(P1);
    
    cout << endl;
}

4.2 学生成绩管理系统

#include <iostream>
#include <string>
using namespace std;

// 学生信息结构
typedef struct Student {
    string id;      // 学号
    string name;    // 姓名
    float score;    // 成绩
} Student;

// 学生节点
typedef struct StuNode {
    Student data;
    struct StuNode *next;
} StuNode, *StudentList;

// 初始化学生链表
Status InitList(StudentList &L) {
    L = new StuNode;
    L->next = NULL;
    return OK;
}

// 添加学生信息
Status AddStudent(StudentList &L, Student stu) {
    StuNode *s = new StuNode;
    s->data = stu;
    s->next = L->next;
    L->next = s;
    return OK;
}

// 按学号查找学生
StuNode *FindStudentById(StudentList L, string id) {
    StuNode *p = L->next;
    while (p && p->data.id != id) {
        p = p->next;
    }
    return p;
}

// 删除学生信息
Status DeleteStudent(StudentList &L, string id) {
    StuNode *p = L;
    while (p->next && p->next->data.id != id) {
        p = p->next;
    }
    
    if (!p->next) {
        return ERROR;  // 未找到
    }
    
    StuNode *temp = p->next;
    p->next = temp->next;
    delete temp;
    return OK;
}

// 显示所有学生信息
void DisplayStudents(StudentList L) {
    StuNode *p = L->next;
    cout << "学号\t姓名\t成绩" << endl;
    cout << "-------------------" << endl;
    while (p) {
        cout << p->data.id << "\t" << p->data.name << "\t" << p->data.score << endl;
        p = p->next;
    }
}

// 计算平均成绩
float CalculateAverage(StudentList L) {
    if (!L->next) return 0;
    
    float sum = 0;
    int count = 0;
    StuNode *p = L->next;
    
    while (p) {
        sum += p->data.score;
        count++;
        p = p->next;
    }
    
    return sum / count;
}

// 学生成绩管理系统示例
void StudentManagementDemo() {
    StudentList L;
    InitList(L);
    
    cout << "=== 学生成绩管理系统演示 ===" << endl;
    
    // 添加测试数据
    Student stu1 = {"1001", "张三", 85.5};
    Student stu2 = {"1002", "李四", 92.0};
    Student stu3 = {"1003", "王五", 78.5};
    
    AddStudent(L, stu1);
    AddStudent(L, stu2);
    AddStudent(L, stu3);
    
    cout << "所有学生信息：" << endl;
    DisplayStudents(L);
    
    cout << "平均成绩：" << CalculateAverage(L) << endl;
    
    // 查找学生
    StuNode *found = FindStudentById(L, "1002");
    if (found) {
        cout << "找到学生：" << found->data.name << "，成绩：" << found->data.score << endl;
    }
    
    // 删除学生
    DeleteStudent(L, "1001");
    cout << "删除学号1001后：" << endl;
    DisplayStudents(L);
    
    cout << endl;
}

5. 线性表的性能分析与比较

5.1 时间复杂度比较

操作	顺序表	单链表	双向链表	循环链表
访问元素	O(1)	O(n)	O(n)	O(n)
插入元素	O(n)	O(1)*	O(1)*	O(1)*
删除元素	O(n)	O(1)*	O(1)*	O(1)*
查找元素	O(n)	O(n)	O(n)	O(n)

注：链表的插入删除操作在已知位置的情况下为O(1)，但查找位置需要O(n)

5.2 空间复杂度比较

• 顺序表：需要预分配固定大小的空间，可能存在空间浪费
• 链表：每个节点需要额外空间存储指针，但可以动态分配

5.3 适用场景总结

1. 顺序表适用场景：

   • 数据量相对固定
   • 需要频繁随机访问
   • 对内存使用效率要求高

2. 链表适用场景：

   • 数据量变化较大
   • 需要频繁插入删除
   • 无法预估数据量大小

6. 线性表的扩展与变种

6.1 静态链表

静态链表用数组来描述链表，数组元素由两个数据域组成：data和cur。data域存放数据元素，cur域存放该元素的后继在数组中的下标。

#define MAXSIZE 1000

typedef struct {
    ElemType data;
    int cur;  // 游标，为0时表示无指向
} Component, StaticLinkList[MAXSIZE];

// 初始化静态链表
Status InitList(StaticLinkList space) {
    for (int i = 0; i < MAXSIZE - 1; i++) {
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;  // 最后一个元素的cur为0
    return OK;
}

6.2 跳跃表

跳跃表是一种随机化的数据结构，通过维护多个层次的链表来实现快速查找，时间复杂度可以达到O(log n)。

7. 总结

线性表作为最基本的数据结构，在计算机科学中有着广泛的应用。本文详细介绍了线性表的各种实现方式：

1. 顺序表：适合随机访问，但插入删除效率低
2. 单链表：插入删除效率高，但只能单向遍历
3. 双向链表：可以双向遍历，但需要更多空间
4. 循环链表：适合循环访问的场景

每种实现都有其特定的应用场景和优缺点，在实际开发中需要根据具体需求选择合适的数据结构。理解线性表的原理和实现对于学习更复杂的数据结构和算法具有重要意义。

通过本文的学习，读者应该能够：

• 理解线性表的基本概念和特性
• 掌握各种线性表的实现方法和操作
• 能够根据实际问题选择合适的数据结构
• 理解不同实现的性能特点和适用场景

线性表是数据结构的基础，扎实掌握线性表将为学习栈、队列、树、图等更复杂的数据结构打下坚实的基础。