数据结构线性结构总结性知识点

附件：人工智能学院作业任务单（线性结构） - ...

一、线性表

1. 逻辑结构特点及存储方式对比

逻辑结构特点：

• 元素间存在一对一的线性关系，除首元素外，每个元素有唯一前驱；除尾元素外，每个元素有唯一后继。

顺序存储 vs 链式存储：

2. 关键运算实现（以C语言为例）

顺序表插入（第3个位置插入X）

过程：

1. 将第3个位置及之后的元素后移一位。
2. 在第3个位置填入X。

代码：

void insert(int arr[], int *size, int pos, int x) {
    for (int i = *size; i > pos; i--) {
        arr[i] = arr[i-1];  // 元素后移
    }
    arr[pos] = x;  // 插入X
    (*size)++;  // 长度+1
}
// 调用示例：insert(arr, &size, 2, X);  // 第3个位置索引为2

顺序表删除（删除第4个位置元素）

过程：

1. 将第5个位置及之后的元素前移一位。
2. 长度减1。

代码：

void delete(int arr[], int *size, int pos) {
    for (int i = pos; i < *size - 1; i++) {
        arr[i] = arr[i+1];  // 元素前移
    }
    (*size)--;  // 长度-1
}
// 调用示例：delete(arr, &size, 3);  // 第4个位置索引为3

单链表插入（第3个位置插入X）

过程：

1. 找到第2个节点（插入位置的前驱）。
2. 创建新节点X，将其next指向原第3个节点。
3. 将第2个节点的next指向X。

代码：

struct Node {
    int data;
    struct Node* next;
};

void insert(Node* head, int pos, int x) {
    Node* prev = head;
    for (int i = 0; i < pos-1; i++) {  // 找到第2个节点
        prev = prev->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = prev->next;  // 新节点指向原第3个节点
    prev->next = newNode;  // 第2个节点指向新节点
}

单链表删除（删除第4个位置元素）

过程：

1. 找到第3个节点（删除位置的前驱）。
2. 将第3个节点的next指向原第5个节点。
3. 释放原第4个节点的内存。

代码：

void delete(Node* head, int pos) {
    Node* prev = head;
    for (int i = 0; i < pos-1; i++) {  // 找到第3个节点
        prev = prev->next;
    }
    Node* toDelete = prev->next;  // 原第4个节点
    prev->next = toDelete->next;  // 跳过第4个节点
    free(toDelete);  // 释放内存
}

二、栈

1. 栈的特点

• 后进先出（LIFO）：最后入栈的元素最先出栈。
• 仅允许在栈顶进行插入（push）和删除（pop）操作。

2. 关键运算实现

顺序栈进栈（元素X入栈）

过程：

1. 检查栈是否已满。
2. 栈顶指针+1，将X存入新栈顶位置。

代码：

#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;

void push(int x) {
    if (top == MAX_SIZE - 1) {
        printf("Stack overflow!\n");
        return;
    }
    stack[++top] = x;  // 栈顶指针+1，存入X
}

顺序栈出栈（栈顶元素出栈）

过程：

1. 检查栈是否为空。
2. 返回栈顶元素，栈顶指针-1。

代码：

int pop() {
    if (top == -1) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack[top--];  // 返回栈顶元素，指针-1
}

链栈进栈（元素X入栈）

过程：

1. 创建新节点X，将其next指向原栈顶。
2. 更新栈顶指针为新节点。

代码：

struct Node {
    int data;
    struct Node* next;
};
Node* top = NULL;

void push(int x) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = top;  // 新节点指向原栈顶
    top = newNode;  // 更新栈顶
}

链栈出栈（栈顶元素出栈）

过程：

1. 检查栈是否为空。
2. 保存原栈顶节点，更新栈顶为其next。
3. 释放原栈顶节点的内存。

代码：

int pop() {
    if (top == NULL) {
        printf("Stack underflow!\n");
        return -1;
    }
    int data = top->data;
    Node* temp = top;
    top = top->next;  // 更新栈顶
    free(temp);  // 释放内存
    return data;
}

三、队列

1. 队列的特性

• 先进先出（FIFO）：最先入队的元素最先出队。
• 插入（enqueue）在队尾进行，删除（dequeue）在队头进行。

2. 关键运算实现

循环队列

结构定义：

#define MAX_SIZE 5
int queue[MAX_SIZE];
int front = 0, rear = 0;  // 初始均指向0

判空/判满：

bool isEmpty() {
    return front == rear;
}

bool isFull() {
    return (rear + 1) % MAX_SIZE == front;  // 牺牲一个位置
}

进队（元素X入队）：

void enqueue(int x) {
    if (isFull()) {
        printf("Queue overflow!\n");
        return;
    }
    queue[rear] = x;
    rear = (rear + 1) % MAX_SIZE;  // 循环后移
}

出队（队头元素出队）：

int dequeue() {
    if (isEmpty()) {
        printf("Queue underflow!\n");
        return -1;
    }
    int data = queue[front];
    front = (front + 1) % MAX_SIZE;  // 循环后移
    return data;
}

链队列

结构定义：

struct Node {
    int data;
    struct Node* next;
};
struct Queue {
    Node* front;
    Node* rear;
};

进队（元素X入队）：

void enqueue(Queue* q, int x) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;

    if (q->rear == NULL) {  // 队列为空
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;  // 原队尾指向新节点
        q->rear = newNode;  // 更新队尾
    }
}

出队（队头元素出队）：

int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("Queue underflow!\n");
        return -1;
    }
    Node* temp = q->front;
    int data = temp->data;

    q->front = q->front->next;  // 更新队头
    if (q->front == NULL) {  // 若队列为空，更新队尾
        q->rear = NULL;
    }
    free(temp);
    return data;
}

以上代码均为核心逻辑实现，实际使用时需根据具体需求添加错误处理和内存管理。