一、数据结构概述
数据结构是计算机科学中研究数据组织、存储、检索和操作的技术。它是计算机程序设计的基础，对于提高程序性能、优化算法至关重要。数据结构可以分为线性结构和非线性结构两大类。
线性结构包括数组、链表、栈、队列等；非线性结构包括树、图、散列表等。在计算机专业面试中，深入理解数据结构及现方法是一个常见。
二、线性结构及现
1. 数组（Array）
数组是一种基本的数据结构，它是一个有序的元素集合，每个元素都存储在连续的内存地址中。数组具有特点：
（1）随机访问：可以快速访问数组中的任意元素。
（2）静态分配：在编译时分配内存空间，无法动态调整大小。
（3）元素类型相同：数组中的所有元素具有相同的类型。
数组可以通过实现：
c
int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
2. 链表（Linked List）
链表是一种非线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表具有特点：
（1）动态分配：可以动态调整大小。
（2）插入和删除操作方便。
（3）元素类型可以不同。
链表可以通过实现：
c
struct Node {
int data;
struct Node* next;
};
// 创建链表节点
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 创建链表
struct Node* createList(int data[], int size) {
struct Node* head = NULL;
for (int i = 0; i < size; i++) {
struct Node* newNode = createNode(data[i]);
newNode->next = head;
head = newNode;
}
return head;
}
3. 栈（Stack）
栈是一种后进先出（LIFO）的数据结构，它支持两种操作：入栈（push）和出栈（pop）。栈具有特点：
（1）动态分配：可以动态调整大小。
（2）插入和删除操作方便。
（3）元素类型可以不同。
栈可以通过实现：
c
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
// 入栈
void push(int data) {
if (top < MAX_SIZE – 1) {
stack[++top] = data;
} else {
printf("Stack overflow\n");
}
}
// 出栈
int pop() {
if (top >= 0) {
return stack[top–];
} else {
printf("Stack underflow\n");
return -1;
}
}
4. 队列（Queue）
队列是一种先进先出（FIFO）的数据结构，它支持两种操作：入队（enqueue）和出队（dequeue）。队列具有特点：
（1）动态分配：可以动态调整大小。
（2）插入和删除操作方便。
（3）元素类型可以不同。
队列可以通过实现：
c
#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = 0;
int rear = -1;
// 入队
void enqueue(int data) {
if ((rear + 1) % MAX_SIZE == front) {
printf("Queue overflow\n");
} else {
queue[++rear] = data;
}
}
// 出队
int dequeue() {
if (front == rear + 1) {
printf("Queue underflow\n");
return -1;
} else {
return queue[front++];
}
}
三、非线性结构及现
1. 树（Tree）
树是一种非线性数据结构，它由节点组成，每个节点有一个或多个子节点。树具有特点：
（1）层次结构：节点之间具有父子关系。
（2）递归结构：树的许多操作可以通过递归实现。
（3）元素类型可以不同。
树可以通过实现：
c
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建树节点
struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 创建二叉树
struct TreeNode* createBinaryTree(int data[], int size) {
struct TreeNode* root = NULL;
for (int i = 0; i < size; i++) {
struct TreeNode* newNode = createNode(data[i]);
if (root == NULL) {
root = newNode;
} else {
struct TreeNode* current = root;
struct TreeNode* parent = NULL;
while (current != NULL) {
parent = current;
if (data[i] < current->data) {
current = current->left;
} else {
current = current->right;
}
}
if (data[i] < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
}
}
return root;
}
2. 图（Graph）
图是一种非线性数据结构，它由节点和边组成。图具有特点：
（1）节点：表示数据对象。
（2）边：表示节点之间的关系。
（3）无向图和有向图：边可以是无向或有向。
图可以通过实现：
c
#define MAX_VERTICES 100
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int numVertices = 0;
// 添加顶点
void addVertex() {
if (numVertices < MAX_VERTICES) {
adjMatrix[numVertices][numVertices] = 0;
for (int i = 0; i < numVertices; i++) {
adjMatrix[i][numVertices] = 0;
adjMatrix[numVertices][i] = 0;
}
numVertices++;
} else {
printf("Graph overflow\n");
}
}
// 添加边
void addEdge(int start, int end) {
if (start >= 0 && start < numVertices && end >= 0 && end < numVertices) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
} else {
printf("Invalid vertices\n");
}
}
四、
在计算机专业面试中，深入理解数据结构及现方法是一个常见。本文介绍了线性结构（数组、链表、栈、队列）和非线性结构（树、图）及现方法。通过掌握这些知识，可以更好地应对面试中的相关。
还没有评论呢，快来抢沙发~