C语言数据结构：常见面试问题剖析

wufei123 2025-01-26 阅读:36 评论:0

数据结构是 c 语言面试中的关键知识点：指针和数组：理解指针指向数组起始地址并用于访问和修改数组元素。链表：实现单向链表，掌握创建、插入和删除操作。栈：利用数组构建栈，理解压栈、出栈和查看栈顶操作。队列：使用数组实现队列，掌握入队、出队和查...

数据结构是 c 语言面试中的关键知识点：指针和数组：理解指针指向数组起始地址并用于访问和修改数组元素。链表：实现单向链表，掌握创建、插入和删除操作。栈：利用数组构建栈，理解压栈、出栈和查看栈顶操作。队列：使用数组实现队列，掌握入队、出队和查看队首操作。

C语言数据结构：常见面试问题剖析

C 语言数据结构：常见面试问题剖析

在许多编程面试中，数据结构都是不可避免的话题。掌握 C 语言中的常见数据结构及其应用对于求职者来说至关重要。

1. 指针和数组

理解指针指向数组起始地址的原理。

int arr[] = {1, 2, 3, 4, 5};
int *ptr = arr;  // 指向数组首元素

使用指针访问和修改数组元素。

printf("%d
", *ptr);  // 输出 1
*ptr++;  // 指向下一个数组元素
printf("%d
", *ptr);  // 输出 2

2. 链表

实现单向链表及其基本操作（创建、插入、删除）。

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

struct node *head = NULL;  // 链表头部

// 创建链表
void create_list(int data) {
  struct node *new_node = malloc(sizeof(struct node));
  new_node-&gt;data = data;
  new_node-&gt;next = NULL;

  if (head == NULL) {
      head = new_node;
  } else {
      struct node *current = head;
      while (current-&gt;next != NULL) {
          current = current-&gt;next;
      }
      current-&gt;next = new_node;
  }
}

// 插入节点到链表特定位置
void insert_node(int data, int position) {
  struct node *new_node = malloc(sizeof(struct node));
  new_node-&gt;data = data;

  if (position == 0) {
      new_node-&gt;next = head;
      head = new_node;
  } else {
      struct node *current = head;
      for (int i = 0; i next;
      }

      if (current != NULL) {
          new_node-&gt;next = current-&gt;next;
          current-&gt;next = new_node;
      }
  }
}

// 删除链表特定位置的节点
void delete_node(int position) {
  struct node *current = head;

  if (position == 0) {
      head = head-&gt;next;
  } else {
      for (int i = 0; i next;
      }

      if (current != NULL &amp;&amp; current-&gt;next != NULL) {
          struct node *temp = current-&gt;next;
          current-&gt;next = temp-&gt;next;
          free(temp);
      }
  }
}

3. 栈

实现栈并使用数组模拟，理解栈的基本操作（压栈、出栈、查看栈顶）。

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;  // 栈顶指针

// 压栈
void push(int data) {
  if (top == MAX_SIZE - 1) {
      printf("Stack overflow
");
  } else {
      stack[++top] = data;
  }
}

// 出栈
int pop() {
  if (top == -1) {
      printf("Stack underflow
");
      return -1;
  } else {
      return stack[top--];
  }
}

// 查看栈顶元素
int peek() {
  if (top == -1) {
      printf("Empty stack
");
      return -1;
  } else {
      return stack[top];
  }
}

4. 队列

使用数组实现队列，理解队列的基本操作（入队、出队、查看队首）。

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = -1, rear = -1;

// 入队
void enqueue(int data) {
  if ((front == 0 &amp;&amp; rear == MAX_SIZE - 1) || (rear + 1 == front)) {
      printf("Queue overflow
");
  } else if (front == -1) {
      front = rear = 0;
      queue[rear] = data;
  } else if (rear == MAX_SIZE - 1) {
      rear = 0;
      queue[rear] = data;
  } else {
      rear++;
      queue[rear] = data;
  }
}

// 出队
int dequeue() {
  if (front == -1) {
      printf("Queue underflow
");
      return -1;
  } else if (front == rear) {
      int data = queue[front];
      front = rear = -1;
      return data;
  } else {
      int data = queue[front];
      front++;
      return data;
  }
}

// 查看队首元素
int peek() {
  if (front == -1) {
      printf("Queue empty
");
      return -1;
  } else {
      return queue[front];
  }
}