数据结构考研攻略：一本让你轻松掌握核心知识的复习宝典

引言

数据结构是计算机科学的基础知识之一，对于考研学子来说，掌握数据结构的核心知识是至关重要的。本文将为你提供一份详细的数据结构考研攻略，帮助你轻松掌握核心知识，顺利通过考研。

一、数据结构的基本概念

1.1 数据的定义

数据是描述现实世界中事物的符号记录，它是信息的载体。在计算机科学中，数据通常以数字、字符等形式表示。

1.2 数据结构的概念

数据结构是组织数据的方式，它决定了数据的存储、检索和操作效率。数据结构分为线性结构和非线性结构两大类。

1.3 数据结构的分类

线性结构：数组、链表、栈、队列等。
非线性结构：树、图等。

二、线性结构

2.1 数组

数组是一种基本的数据结构，它是一组具有相同数据类型的元素集合。数组在内存中连续存储，具有良好的随机访问性能。

2.1.1 数组的定义

#define MAX_SIZE 100 // 数组最大容量
typedef struct {
    int data[MAX_SIZE]; // 数组元素
    int length;        // 数组长度
} Array;

2.1.2 数组的基本操作

初始化

void InitArray(Array *a) {
    a->length = 0;
}

插入

void InsertArray(Array *a, int i, int e) {
    if (i < 1 || i > a->length + 1 || a->length == MAX_SIZE) {
        return;
    }
    for (int j = a->length; j >= i; j--) {
        a->data[j] = a->data[j - 1];
    }
    a->data[i - 1] = e;
    a->length++;
}

删除

void DeleteArray(Array *a, int i) {
    if (i < 1 || i > a->length) {
        return;
    }
    for (int j = i; j < a->length; j++) {
        a->data[j - 1] = a->data[j];
    }
    a->length--;
}

2.2 链表

链表是一种非连续的内存结构，由节点组成。每个节点包含数据域和指针域，指针域指向下一个节点。

2.2.1 链表的定义

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

2.2.2 链表的基本操作

创建

Node *CreateList() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}

插入

void InsertList(Node *head, int i, int e) {
    if (i < 1 || i > head->length + 1) {
        return;
    }
    Node *p = head;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = e;
    newNode->next = p->next;
    p->next = newNode;
}

删除

void DeleteList(Node *head, int i) {
    if (i < 1 || i > head->length) {
        return;
    }
    Node *p = head;
    for (int j = 1; j < i; j++) {
        p = p->next;
    }
    Node *delNode = p->next;
    p->next = delNode->next;
    free(delNode);
}

2.3 栈

栈是一种后进先出（LIFO）的线性结构，元素按照一定的顺序入栈和出栈。

2.3.1 栈的定义

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

2.3.2 栈的基本操作

初始化

void InitStack(Stack *s) {
    s->top = -1;
}

入栈

void Push(Stack *s, int e) {
    if (s->top == MAX_SIZE - 1) {
        return;
    }
    s->data[++s->top] = e;
}

出栈

int Pop(Stack *s) {
    if (s->top == -1) {
        return -1;
    }
    return s->data[s->top--];
}

2.4 队列

队列是一种先进先出（FIFO）的线性结构，元素按照一定的顺序入队和出队。

2.4.1 队列的定义

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

2.4.2 队列的基本操作

初始化

void InitQueue(Queue *q) {
    q->front = q->rear = 0;
}

入队

void EnQueue(Queue *q, int e) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        return;
    }
    q->data[q->rear] = e;
    q->rear = (q->rear + 1) % MAX_SIZE;
}

出队

int DeQueue(Queue *q) {
    if (q->front == q->rear) {
        return -1;
    }
    return q->data[q->front++];
}

三、非线性结构

3.1 树

树是一种层次结构，由节点组成，每个节点包含若干子节点和一个父节点。

3.1.1 树的定义

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

3.1.2 树的基本操作

创建

TreeNode *CreateTree(int data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

插入

void InsertTree(TreeNode *root, int data) {
    if (data < root->data) {
        if (root->left == NULL) {
            root->left = CreateTree(data);
        } else {
            InsertTree(root->left, data);
        }
    } else {
        if (root->right == NULL) {
            root->right = CreateTree(data);
        } else {
            InsertTree(root->right, data);
        }
    }
}

遍历

void PreOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

3.2 图

图是一种复杂的数据结构，由节点和边组成，节点表示实体，边表示实体之间的关系。

3.2.1 图的定义

typedef struct GraphNode {
    int vertex; // 节点编号
    int *edges; // 邻接表
    int numEdges; // 边的数量
} GraphNode;

3.2.2 图的基本操作

创建

GraphNode *CreateGraph(int numVertices) {
    GraphNode *graph = (GraphNode *)malloc(numVertices * sizeof(GraphNode));
    for (int i = 0; i < numVertices; i++) {
        graph[i].vertex = i;
        graph[i].edges = (int *)malloc(numVertices * sizeof(int));
        graph[i].numEdges = 0;
    }
    return graph;
}

添加边

void AddEdge(GraphNode *graph, int u, int v) {
    graph[u].edges[graph[u].numEdges++] = v;
    graph[v].edges[graph[v].numEdges++] = u;
}

遍历

void DFS(GraphNode *graph, int start) {
    int visited[MAX_SIZE] = {0};
    Stack stack;
    InitStack(&stack);
    visited[start] = 1;
    Push(&stack, start);
    while (!IsEmptyStack(&stack)) {
        int node = Pop(&stack);
        printf("%d ", node);
        for (int i = 0; i < graph[node].numEdges; i++) {
            int adj = graph[node].edges[i];
            if (!visited[adj]) {
                visited[adj] = 1;
                Push(&stack, adj);
            }
        }
    }
}

四、总结

数据结构是计算机科学的核心知识之一，掌握数据结构对于考研学子来说至关重要。本文详细介绍了数据结构的基本概念、线性结构和非线性结构，并通过代码示例说明了基本操作。希望这份复习宝典能帮助你轻松掌握数据结构的核心知识，顺利通过考研。