正文开始

一、数据结构概述

数据结构是研究数据元素集合及其相互关系与构造方法的学科。其中：

• • 逻辑结构描述元素间抽象关系，分为线性结构和非线性结构
• • 存储结构实现数据的物理存储方式，主要包含顺序存储和链式存储

线性结构包括线性表、栈、队列、串，非线性结构主要有树和图。本文重点解析线性结构的核心内容。

二、线性表

1. 基本概念

线性表是n个数据元素组成的有限序列，主要操作包括插入、删除和查找。

2. 存储结构对比

衍生链表结构：

• • 双向链表：包含前驱/后继指针，支持双向遍历
• • 循环链表：尾结点指向头结点，形成环形结构
• • 静态链表：利用数组模拟链式结构

三、栈与队列

1. 栈（LIFO结构）

核心操作：

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):  # 入栈
        self.items.append(item)
    
    def pop(self):         # 出栈
        return self.items.pop()
    
    def peek(self):        # 查看栈顶
        return self.items[-1]

存储实现：

• • 顺序栈：数组+栈顶指针（需处理上溢）
• • 链栈：头插法链表（无容量限制）

典型应用：

• • 表达式求值：中缀转后缀表达式
• • 括号匹配验证
• • 函数调用栈

2. 队列（FIFO结构）

循环队列实现：

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;
} CircularQueue;

void enQueue(CircularQueue *q, int x) {
    q->rear = (q->rear+1) % MAXSIZE;
    q->data[q->rear] = x;
}

特殊队列类型：

• • 双端队列：两端均可操作
• • 优先队列：按优先级出队
• • 阻塞队列：线程安全模型

四、字符串处理

1. 基本概念

• • 空串：长度0的串（∅）
• • 子串：主串中连续字符序列
• • 串相等：长度与内容完全一致

2. 存储优化

// 动态字符串实现示例
class MyString {
    char[] value;
    int length;
    
    public MyString concat(MyString s) {
        char[] newVal = Arrays.copyOf(value, length+s.length);
        System.arraycopy(s.value, 0, newVal, length, s.length);
        return new MyString(newVal);
    }
}

3. 模式匹配算法

• • Brute-Force：O(mn)时间复杂度
• • KMP算法：通过部分匹配表优化至O(m+n)

五、应用实践

1. 1. 文本编辑器：使用栈实现撤销操作
2. 2. 消息队列：基于循环队列实现生产者-消费者模型
3. 3. DNA序列分析：通过字符串匹配算法进行基因比对

六、重要考点

1. 1. 顺序表插入删除元素时的移动次数计算
2. 2. 链表头结点作用与边界条件处理
3. 3. 循环队列队空/队满判断条件：
• • 队空：front == rear
• • 队满：(rear+1)%MAXSIZE == front

线性结构作为数据结构的基础，其设计思想延伸至非线性结构。理解不同存储结构的实现原理与时空复杂度特性，是进行高效算法设计的关键。