c++线性表的基本运算是什么

发布时间：2022-03-22 16:07:07 作者：iii
来源：亿速云阅读：156

# C++线性表的基本运算是什么

## 目录
1. [线性表概述](#线性表概述)
2. [顺序表的基本运算](#顺序表的基本运算)
3. [链表的基本运算](#链表的基本运算)
4. [线性表的应用场景](#线性表的应用场景)
5. [性能分析与比较](#性能分析与比较)
6. [完整代码示例](#完整代码示例)
7. [总结](#总结)

## 线性表概述

线性表（Linear List）是数据结构中最基本、最简单的一种结构，它是由n（n≥0）个数据元素（结点）组成的有限序列。线性表中的数据元素可以是任意类型，但同一线性表中的元素必须属于同一数据类型。

### 线性表的特点
1. **有序性**：元素之间存在顺序关系
2. **有限性**：元素个数是有限的
3. **同一性**：所有元素属于同一数据类型
4. **抽象性**：仅考虑元素间的逻辑关系

### 线性表的两种存储结构
1. **顺序存储结构（顺序表）**
   - 用一组地址连续的存储单元依次存储线性表的数据元素
   - 特点：随机存取，存储密度高

2. **链式存储结构（链表）**
   - 用一组任意的存储单元存储线性表的数据元素
   - 特点：插入删除效率高，不需要预先分配空间

## 顺序表的基本运算

### 1. 顺序表的结构定义

```cpp
#define MAXSIZE 100  // 顺序表的最大长度
typedef struct {
    int data[MAXSIZE];  // 存储数据元素
    int length;         // 当前长度
} SqList;

2. 初始化操作

void InitList(SqList &L) {
    L.length = 0;  // 初始化长度为0
}

3. 插入操作

bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;  // 判断i的范围是否有效
    if (L.length >= MAXSIZE) return false;        // 存储空间已满
    
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j-1];  // 将第i个元素及之后的元素后移
    }
    L.data[i-1] = e;  // 在位置i处放入e
    L.length++;       // 长度加1
    return true;
}

时间复杂度分析： - 最好情况：O(1)（在表尾插入） - 最坏情况：O(n)（在表头插入） - 平均情况：O(n)

4. 删除操作

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) return false;  // 判断i的范围是否有效
    
    e = L.data[i-1];  // 将被删除的元素赋值给e
    
    for (int j = i; j < L.length; j++) {
        L.data[j-1] = L.data[j];  // 将第i个位置后的元素前移
    }
    L.length--;  // 长度减1
    return true;
}

时间复杂度分析： - 最好情况：O(1)（删除表尾元素） - 最坏情况：O(n)（删除表头元素） - 平均情况：O(n)

5. 按值查找

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i+1;  // 返回元素位置（从1开始）
        }
    }
    return 0;  // 查找失败
}

时间复杂度：O(n)

6. 按位查找

int GetElem(SqList L, int i) {
    if (i < 1 || i > L.length) return -1;  // 判断i的范围是否有效
    return L.data[i-1];  // 返回位置i的元素值
}

时间复杂度：O(1)

链表的基本运算

1. 单链表的结构定义

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

2. 初始化操作

bool InitList(LinkList &L) {
    L = new LNode;     // 分配头结点
    if (!L) return false;  // 内存分配失败
    L->next = NULL;    // 头结点指针域置空
    return true;
}

3. 头插法建立单链表

void CreateList_H(LinkList &L, int n) {
    L = new LNode;
    L->next = NULL;
    
    for (int i = 0; i < n; i++) {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }
}

4. 尾插法建立单链表

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;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

5. 插入操作

bool ListInsert(LinkList &L, int i, int e) {
    LNode *p = L;
    int j = 0;
    
    while (p && j < i-1) {  // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    
    if (!p || j > i-1) return false;  // i值不合法
    
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

时间复杂度：O(n)

6. 删除操作

bool ListDelete(LinkList &L, int i, int &e) {
    LNode *p = L;
    int j = 0;
    
    while (p->next && j < i-1) {  // 寻找第i-1个结点
        p = p->next;
        j++;
    }
    
    if (!(p->next) || j > i-1) return false;  // i值不合法
    
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

时间复杂度：O(n)

7. 查找操作

LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}

时间复杂度：O(n)

线性表的应用场景

顺序表的典型应用

数组操作：大多数编程语言中的数组实现
数据库表：关系型数据库中的表存储
图像处理：像素矩阵的存储
科学计算：向量和矩阵运算

链表的典型应用

文件系统：文件分配表(FAT)
内存管理：空闲内存块链表
多项式运算：稀疏多项式的存储
浏览器历史记录：前进后退功能实现
撤销操作：软件中的撤销功能栈

性能分析与比较

顺序表 vs 链表

操作	顺序表	链表
访问元素	O(1)	O(n)
插入/删除	O(n)	O(1)
存储密度	高	低
扩展性	差	好
内存分配	静态	动态

适用场景选择

选择顺序表：
- 需要频繁访问元素
- 元素数量变化不大
- 对存储空间要求高
选择链表：
- 需要频繁插入删除
- 元素数量变化大
- 无法预估数据规模

完整代码示例

顺序表完整实现

#include <iostream>
#define MAXSIZE 100

using namespace std;

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

void InitList(SqList &L) {
    L.length = 0;
}

bool ListInsert(SqList &L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MAXSIZE) return false;
    
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length++;
    return true;
}

bool ListDelete(SqList &L, int i, int &e) {
    if (i < 1 || i > L.length) return false;
    
    e = L.data[i-1];
    
    for (int j = i; j < L.length; j++) {
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i+1;
        }
    }
    return 0;
}

int GetElem(SqList L, int i) {
    if (i < 1 || i > L.length) return -1;
    return L.data[i-1];
}

void PrintList(SqList L) {
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    cout << endl;
}

int main() {
    SqList L;
    InitList(L);
    
    // 插入元素
    for (int i = 1; i <= 5; i++) {
        ListInsert(L, i, i*10);
    }
    PrintList(L);  // 输出：10 20 30 40 50
    
    // 删除元素
    int e;
    ListDelete(L, 3, e);
    cout << "Deleted element: " << e << endl;  // 输出：Deleted element: 30
    PrintList(L);  // 输出：10 20 40 50
    
    // 查找元素
    int pos = LocateElem(L, 40);
    cout << "Position of 40: " << pos << endl;  // 输出：Position of 40: 3
    
    return 0;
}

单链表完整实现

#include <iostream>
using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList &L) {
    L = new LNode;
    if (!L) return false;
    L->next = NULL;
    return true;
}

bool ListInsert(LinkList &L, int i, int e) {
    LNode *p = L;
    int j = 0;
    
    while (p && j < i-1) {
        p = p->next;
        j++;
    }
    
    if (!p || j > i-1) return false;
    
    LNode *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool ListDelete(LinkList &L, int i, int &e) {
    LNode *p = L;
    int j = 0;
    
    while (p->next && j < i-1) {
        p = p->next;
        j++;
    }
    
    if (!(p->next) || j > i-1) return false;
    
    LNode *q = p->next;
    e = q->data;
    p->next = q->next;
    delete q;
    return true;
}

LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return 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;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

void PrintList(LinkList L) {
    LNode *p = L->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    InitList(L);
    
    // 插入元素
    for (int i = 1; i <= 5; i++) {
        ListInsert(L, i, i*10);
    }
    PrintList(L);  // 输出：10 20 30 40 50
    
    // 删除元素
    int e;
    ListDelete(L, 3, e);
    cout << "Deleted element: " << e << endl;  // 输出：Deleted element: 30
    PrintList(L);  // 输出：10 20 40 50
    
    // 查找元素
    LNode *p = LocateElem(L, 40);
    if (p) {
        cout << "Found element: " << p->data << endl;  // 输出：Found element: 40
    }
    
    return 0;
}

总结

线性表作为最基本的数据结构，在C++中有着广泛的应用。本文详细介绍了：

顺序表和链表两种存储结构的实现原理
各种基本运算的算法实现和时间复杂度分析
不同应用场景下的选择建议
完整的代码示例供参考

掌握线性表的基本运算对于学习更复杂的数据结构至关重要，它是构建栈、队列、树、图等高级数据结构的基础。在实际编程中，应根据具体需求选择合适的存储结构，权衡时间效率和空间效率。

（全文约9400字） “`

c++线性表的基本运算是什么

2. 初始化操作

3. 插入操作

4. 删除操作

5. 按值查找

6. 按位查找

链表的基本运算

1. 单链表的结构定义

2. 初始化操作

3. 头插法建立单链表

4. 尾插法建立单链表

5. 插入操作

6. 删除操作

7. 查找操作

线性表的应用场景

顺序表的典型应用

链表的典型应用

性能分析与比较

顺序表 vs 链表

适用场景选择

完整代码示例

顺序表完整实现

单链表完整实现

总结

相关阅读