正文

C语言数据结构实战习题解析：轻松掌握常见算法与技巧

/0 浏览量
0412

引言

在编程的世界里，数据结构是构建高效程序的基础。C语言作为一种高效、灵活的编程语言，在数据结构的学习和实践中扮演着重要角色。本文将通过实战习题解析，帮助读者轻松掌握C语言中的常见算法与技巧。

1. 线性表

1.1 线性表的创建

线性表是数据结构中最基础的形式，它由一系列元素组成，每个元素只包含一个数据项。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int length;
} LinearList;

// 创建线性表
void createList(LinearList *list, int size) {
    list->length = size;
    for (int i = 0; i < size; i++) {
        list->data[i] = i;
    }
}

1.2 线性表的查找

线性表的查找可以通过顺序查找或二分查找实现。

// 顺序查找
int sequentialSearch(LinearList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1;
}

// 二分查找
int binarySearch(LinearList *list, int value) {
    int low = 0;
    int high = list->length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (list->data[mid] == value) {
            return mid;
        } else if (list->data[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

2. 链表

2.1 链表的创建

链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

#include <stdio.h>
#include <stdlib.h>

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

// 创建链表
Node* createList() {
    Node *head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
        return NULL;
    }
    head->data = 0;
    head->next = NULL;
    return head;
}

// 插入节点
void insertNode(Node *head, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        return;
    }
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
}

2.2 链表的查找

链表的查找可以通过顺序查找实现。

// 顺序查找
Node* sequentialSearch(Node *head, int value) {
    Node *current = head->next;
    while (current != NULL) {
        if (current->data == value) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

3. 栈与队列

3.1 栈的创建

栈是一种后进先出（LIFO）的数据结构。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

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

// 创建栈
void createStack(Stack *stack) {
    stack->top = -1;
}

// 入栈
void push(Stack *stack, int value) {
    if (stack->top < MAX_SIZE - 1) {
        stack->data[++stack->top] = value;
    }
}

// 出栈
int pop(Stack *stack) {
    if (stack->top >= 0) {
        return stack->data[stack->top--];
    }
    return -1;
}

3.2 队列的创建

队列是一种先进先出（FIFO）的数据结构。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 创建队列
void createQueue(Queue *queue) {
    queue->front = queue->rear = 0;
}

// 入队
void enqueue(Queue *queue, int value) {
    if ((queue->rear + 1) % MAX_SIZE == queue->front) {
        printf("Queue is full!\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
}

// 出队
int dequeue(Queue *queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty!\n");
        return -1;
    }
    return queue->data[queue->front++];
}

4. 树与图

4.1 树的创建

树是一种非线性数据结构，由一系列节点组成，每个节点包含一个数据项和若干子节点。

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

// 创建树
Node* createTree(int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    if (node == NULL) {
        return NULL;
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点
void insertNode(Node *root, int data) {
    if (root == NULL) {
        root = createTree(data);
    } else if (data < root->data) {
        insertNode(root->left, data);
    } else {
        insertNode(root->right, data);
    }
}

4.2 图的创建

图是一种非线性数据结构，由一系列节点和边组成。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

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

typedef struct {
    Node *nodes[MAX_SIZE];
    int numNodes;
} Graph;

// 创建图
Graph* createGraph() {
    Graph *graph = (Graph*)malloc(sizeof(Graph));
    if (graph == NULL) {
        return NULL;
    }
    graph->numNodes = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        graph->nodes[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph *graph, int start, int end) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        return;
    }
    newNode->data = end;
    newNode->next = graph->nodes[start];
    graph->nodes[start] = newNode;
}

5. 总结

本文通过实战习题解析，介绍了C语言中常见的线性表、链表、栈、队列、树和图等数据结构及其算法与技巧。通过学习和实践，读者可以轻松掌握这些数据结构，为编写高效程序打下坚实基础。

-- 展开阅读全文 --