数据结构：线性表的基本操作与链式表达

个人主页

文章专栏

成名之作——赛博算命之梅花易数的Java实现

陆续回三中，忘回漏回滴滴~感谢各位大佬的支持

一.线性表的定义和基本操作

1.1定义

线性表是具有相同数据类型的n个数据元素的有序数列，n为表长

第一个元素叫表头元素，除了他，每个元素有且仅有一个直接前驱

最后一个元素叫表尾元素，除了他，每个元素有且仅有一个直接后继

1.2特点

• 个数有限
• 逻辑上有顺序性
• 每个元素都是数据元素，且数据类型都相同，占用空间相同
• 有抽象性

注：线性表是逻辑结构，顺序表和链表是存储结构

1.3基本操作

● InitList(&L): 初始化表。构造一个空的线性表。

● Length(L):求表长。返回线性表L 的长度，即L 中数据元素的个数。

● LocateElem(L,e): 按值查找操作。在表工中查找具有给定关键字值的元素。

● GetElem(L,i): 按位查找操作。获取表L 中 第i 个位置的元素的值。

● ListInsert(&L,i,e): 插入操作。在表L 中的第i 个位置上插入指定元素e。

● ListDelete(&L,i,&e):删除操作。删除表L 中第i 个位置的元素，并用e 返回删除元素的值。

● PrintList(L): 输出操作。按前后顺序输出线性表L 的所有元素值。

● Empty(L): 判空操作。若L 为空表，则返回true, 否则返回false。

● DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L 所占用的内存空间。

二.线性表的顺序表示

2.1定义

线性表的顺序存储称为顺序表，逻辑顺序与物理存储顺序相同，是一种随机存取的存储结构

位序：就是第几个，相当于下标但不是下标，数组的下标从0开始，位序从1开始

2.2静态分配与动态分配

一维数组可以静态分配也可以动态分配。

静态分配：空间是固定的，多于最大值时，新数据就会溢出，导致数据崩溃

#define MaxSize 50//定义线性表的最大长度
typedef struct {
    ElemType data [MaxSize];//顺序表的元素
    int length;//顺序表的当前长度
}SqList;//顺序表的类型定义

动态分配：不是一次性划分所有空间，多余最大值时，会重新开辟更大的新空间，并且把原来的数据copy到新的空间中（不是链式存储，仍是顺序存储结构）

#define IntSize 100//表长度的初始定义
typedef struct{
    ElemType *data;//指示动态分配数组的指针
    int MaxSize , length;//数组的最大容量和当前个数
}SeqList;//动态分配数组顺序表的类型定义

C的初始动态分配语句为：

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

2.3顺序表的优缺

优点：可以随机访问，存储密度高

缺点：不方便变动，不够灵活

2.4基本操作实现

顺序表的初始化

静态分配

void InitList(SqList *L) {
    L->length = 0;//顺序表初始长度为0
}

动态分配

void InitList(SqList *L) {
    L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);//分配动态存储空间
    L->length = 0;//顺序表初始长度为0
    L->MaxSize=IntSize;//初始存储容量
}

插入操作

//在指定位置插入元素
bool ListInsert(SqList *L, int i, ElemType e) {
    //判断位序i是否合法
    if (i<1 || i>L->length+1) {
        return false;
    }
    //判断顺序表是否已满
    if (i>L->length+1) {
        return false;
    }
    //将第i个位置及之后的元素后移
    for (int j=L->length; j>i; j--) {
        L->data[j] = L->data[j-1];
    }
    //在第i个位置插入元素
    L->data[i-1] = e;
    L->length++;
    return true;
}

顺序表插入元素的平均时间复杂度是O(n)

删除操作

//删除指定位置的元素
bool ListDelete(SqList *L, int i, ElemType *e) {
    //判断位序i是否合法
    if (i<1 || i>L->length) {
        return false;
    }
    //保存被删除的元素
    *e = L->data[i-1];
    //将第i个位置及之后的元素前移
    for (int j=i; j<L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    //顺序表长度减1
    L->length--;
    return true;
}

顺序表删除元素的平均时间复杂度是O(n)

按位查找

//按位查找
bool GetElem(SqList L, int i, ElemType *e) {
    //判断位序i是否合法
    if (i<1 || i>L.length) {
        return false;
    }
    *e = L.data[i-1];
    return true;
}

顺序表按位查找的平均时间复杂度是O(1)

按值查找（顺序查找）

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

顺序表按值查找的平均时间复杂度是O(n)

以上是基于c语言的代码实现，以下是java的代码实现

public class SequentialList {
    // 定义常量和数据类型
    private static final int MAX_SIZE = 100;
    private int[] data;
    private int length;
    
    // 构造函数：初始化顺序表
    public SequentialList() {
        data = new int[MAX_SIZE];
        length = 0;
    }
    
    // 在指定位置插入元素
    public boolean insert(int index, int element) {
        // 判断索引是否合法（1~length+1）
        if (index < 1 || index > length + 1) {
            return false;
        }
        // 判断顺序表是否已满
        if (length >= MAX_SIZE) {
            return false;
        }
        // 将第index个位置及之后的元素后移
        for (int j = length; j >= index; j--) {
            data[j] = data[j-1];
        }
        data[index-1] = element;  // 在第index个位置插入元素
        length++;                 // 顺序表长度加1
        return true;
    }
    
    // 删除指定位置的元素
    public boolean delete(int index, int[] element) {
        // 判断索引是否合法（1~length）
        if (index < 1 || index > length) {
            return false;
        }
        element[0] = data[index-1];  // 保存被删除的元素
        // 将第index+1个位置及之后的元素前移
        for (int j = index; j < length; j++) {
            data[j-1] = data[j];
        }
        length--;  // 顺序表长度减1
        return true;
    }
    
    // 按位查找：获取顺序表中第index个位置的元素
    public boolean getElement(int index, int[] element) {
        // 判断索引是否合法（1~length）
        if (index < 1 || index > length) {
            return false;
        }
        element[0] = data[index-1];  // 将第index个位置的元素赋值给element
        return true;
    }
    
    // 打印顺序表中的所有元素
    public void printList() {
        System.out.print("顺序表中的元素: ");
        for (int i = 0; i < length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println("\n顺序表长度: " + length);
    }

三.线性表的链式表示

3.1单链表

3.1.1 定义

单链表是一种链式存储结构，通过节点（Node）连接而成。每个节点包含：

• 数据域：存储数据元素的值
• 指针域：存储下一个节点的地址（null表示无后继节点）

逻辑结构：
head -> Node1 -> Node2 -> ... -> Node(n) -> null
（head为头指针，指向链表第一个节点；最后一个节点的指针域为null）

3.1.2 节点定义

typedef int ElemType;

// 单链表节点结构体
typedef struct LNode {
    ElemType data;          // 数据域
    struct LNode *next;     // 指针域，指向下一个节点
} LNode, *LinkList;        // LinkList为指向结构体的指针类型

3.1.3 核心操作实现

（1）初始化空链表

// 初始化空链表（带头节点）
bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));  // 分配头节点
    if (*L == NULL) return false;         // 内存分配失败
    (*L)->next = NULL;                    // 头节点指针域置空
    return true;
}

（2）按位序插入节点

// 在第i个位置插入元素e（带头节点）
bool ListInsert(LinkList L, int i, ElemType e) {
    if (i < 1) return false;              // 位序i不能小于1
    LNode *p = L;                        // p指向头节点，从第0个位置开始遍历
    int j = 0;                           // 当前位置j=0（头节点位置）
    
    // 找到第i-1个节点
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;          // i超过链表长度+1
    
    // 创建新节点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;                    // 新节点指向p的后继节点
    p->next = s;                          // p的后继节点改为新节点
    return true;
}

（3）按位序删除节点

// 删除第i个位置的元素，并用e返回值（带头节点）
bool ListDelete(LinkList L, int i, ElemType *e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    
    // 找到第i-1个节点
    while (p != NULL && j < i-1) {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL) return false;  // i不合法或链表为空
    
    LNode *q = p->next;          // q指向待删除节点
    *e = q->data;                // 保存删除元素的值
    p->next = q->next;           // 跳过待删除节点
    free(q);                     // 释放内存
    return true;
}

（4）按位序查找节点

// 按位序i查找节点（返回节点指针）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;       // i=0时返回头节点
    LNode *p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;                    // 找到返回节点，否则返回NULL
}

3.1.4 特点

• 优点：
  • 动态分配内存，无需预先确定长度
  • 插入 / 删除操作无需移动大量元素，时间复杂度为 (O(1))（找到前驱节点后）
• 缺点：
  • 无法随机访问元素，按位查找需遍历链表（时间复杂度 (O(n))）
  • 存储密度低（每个节点需额外存储指针域）

3.2 双链表

3.2.1 定义

双链表的节点包含两个指针域：

• prior：指向前驱节点
• next：指向后继节点

逻辑结构： head <-> Node1 <-> Node2 <-> ... <-> Node(n) （头节点的prior为null，尾节点的next为null）

3.2.2 节点定义

typedef struct DNode {
    ElemType data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DLinkList;

3.2.3 核心操作实现（插入与删除）

（1）插入节点（在 p 节点后插入 s 节点）

void InsertAfter(DNode *p, DNode *s) {
    s->next = p->next;      // s的后继指向p的后继
    if (p->next != NULL) {  // 若p不是尾节点，更新后继的前驱
        p->next->prior = s;
    }
    p->next = s;            // p的后继指向s
    s->prior = p;           // s的前驱指向p
}

（2）删除节点（删除 p 节点的后继节点 q）

bool DeleteNext(DNode *p) {
    if (p == NULL || p->next == NULL) return false;
    DNode *q = p->next;          // q为p的后继节点
    p->next = q->next;           // p的后继改为q的后继
    if (q->next != NULL) {       // 若q不是尾节点，更新后继的前驱
        q->next->prior = p;
    }
    free(q);                     // 释放内存
    return true;
}

3.2.4 特点

• 优点：
  • 支持双向遍历，可快速找到前驱节点
  • 插入 / 删除操作更安全（避免单向链表的 “断链” 风险）
• 缺点：
  • 结构更复杂，占用内存更多
  • 操作需同时维护两个指针域

3.3 循环链表

3.3.1 定义

循环链表是首尾相连的链表，分为单循环链表和双循环链表：

• 单循环链表：尾节点的next指向头节点
• 双循环链表：头节点的prior指向尾节点，尾节点的next指向头节点

逻辑结构（单循环链表）： head -> Node1 -> Node2 -> ... -> Node(n) -> head

3.3.2 核心特点

• 判空条件：头节点的next是否指向自身（单循环链表）
• 遍历终止条件：是否回到头节点
• 合并操作：可通过修改首尾节点的指针实现 (O(1)) 时间复杂度合并

3.3.3 单循环链表初始化

// 初始化单循环链表（带头节点）
bool InitCircList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = *L;  // 头节点指针指向自身
    return true;
}

3.3.4 遍历操作（单循环链表）

void TraverseCircList(LinkList L) {
    LNode *p = L->next;  // p指向第一个节点
    while (p != L) {      // 未回到头节点时继续遍历
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

4. 顺序表 vs 链表 对比

总结：

• 若需要高效查询，选顺序表；
• 若需要灵活增删，选链表；
• 循环链表适合环形结构场景（如约瑟夫环问题）；
• 双链表适合双向遍历需求（如文件历史记录）。

------- | --------------------------- | ----------------------------- |
| 存储方式 | 连续内存空间 | 离散内存空间，指针连接 |
| 随机访问 | 支持（时间复杂度 (O(1))） | 不支持（需遍历，(O(n))） |
| 插入 / 删除 | 平均 (O(n))（移动元素） | 平均 (O(n))（查找节点） |
| 内存利用率 | 高（无额外指针） | 低（指针占用空间） |
| 适用场景 | 频繁访问、固定长度场景 | 频繁插入 / 删除、动态长度场景 |

总结：

• 若需要高效查询，选顺序表；
• 若需要灵活增删，选链表；
• 循环链表适合环形结构场景（如约瑟夫环问题）；
• 双链表适合双向遍历需求（如文件历史记录）。