C语言基础（二十五）

2024-08-29 21:04

文章标签 语言基础二十五

本文主要是介绍C语言基础（二十五），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

栈排序不是最高效的方法，因为栈是一种后进先出（LIFO, Last In First Out）的数据结构，而排序要求根据元素的顺序（如升序或降序）重新排列。但是，可以利用栈的特性，结合其他排序算法的思想，或者通过多次入栈和出栈操作间接实现排序。

测试代码：

#include "date.h"
#include <stdio.h>  
#include <stdlib.h>  typedef int ElementType;  typedef struct Node {  ElementType data;  struct Node* next;  
} Node;  typedef struct {  Node* top;  
} Stack;  // 初始化栈  
void InitStack(Stack* s) {  s->top = NULL;  
}  // 检查栈是否为空  
int IsEmpty(Stack* s) {  return s->top == NULL;  
}  // 入栈  
void Push(Stack* s, ElementType e) {  Node* newNode = (Node*)malloc(sizeof(Node));  if (!newNode) {  printf("Memory allocation failed.\n");  return;  }  newNode->data = e;  newNode->next = s->top;  s->top = newNode;  
}  // 出栈  
ElementType Pop(Stack* s) {  if (IsEmpty(s)) {  printf("Stack is empty. Cannot pop.\n");  return -1; // 假设-1是错误值  }  Node* temp = s->top;  ElementType popped = temp->data;  s->top = s->top->next;  free(temp);  return popped;  
}  // 计算栈中元素数量  
int CountElements(Stack* s) {  int count = 0;  Node* current = s->top;  while (current != NULL) {  count++;  current = current->next;  }  return count;  
}  // 打印栈  
void PrintStack(Stack* s) {  Node* current = s->top;  while (current != NULL) {  printf("%d ", current->data);  current = current->next;  }  printf("\n");  
}  // 排序并重新入栈（使用插入排序）  
void SortAndPushBack(Stack* s) {  int count = CountElements(s);  ElementType* array = (ElementType*)malloc(sizeof(ElementType) * count);  if (!array) return;  int i = 0;  Node* current = s->top;  while (current != NULL) {  array[i++] = current->data;  current = current->next;  }  // 插入排序  for (int j = 1; j < count; j++) {  ElementType key = array[j];  int k = j - 1;  while (k >= 0 && array[k] > key) {  array[k + 1] = array[k];  k = k - 1;  }  array[k + 1] = key;  }  // 清空栈并重新入栈  InitStack(s);  for (int j = 0; j < count; j++) {  Push(s, array[j]);  }  free(array);  
}  int main() {  int time = getTime();Stack s;  InitStack(&s);  Push(&s, 3);  Push(&s, 1);  Push(&s, 4);  Push(&s, 6);  Push(&s, 5);  printf("Original stack: ");  PrintStack(&s);  SortAndPushBack(&s); printf("Sorted stack: ");  PrintStack(&s);// 出栈  printf("Popping: ");  while (!IsEmpty(&s)) {  printf("%d ", Pop(&s));  }  printf("\n");  return 0;  
}

运行结果如下：

...........................................................................................................................................................

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。队列的尾部用于添加元素（入队），而队列的头部用于移除元素（出队）。实现队列的方法有很多种，一般基于数组和链表实现。

测试代码;

#include "date.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 10  // 定义队列的最大容量typedef struct {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = q->rear = -1;
}// 检查队列是否满
bool isFull(Queue *q) {return q->rear == MAX_SIZE - 1;
}// 检查队列是否为空
bool isEmpty(Queue *q) {return q->front == -1;
}// 入队操作
bool enqueue(Queue *q, int element) {if (isFull(q)) {printf("Queue is full!\n");return false;}if (isEmpty(q)) {q->front = 0;}q->rear++;q->items[q->rear] = element;printf("Enqueued %d to queue\n", element);return true;
}// 出队操作
bool dequeue(Queue *q, int *element) {if (isEmpty(q)) {printf("Queue is empty!\n");return false;}*element = q->items[q->front];q->front++;if (q->front > q->rear) { // 若队列为空，重置front和rearq->front = q->rear = -1;}return true;
}// 打印队列元素
void printQueue(Queue q) {if (isEmpty(&q)) {printf("Queue is empty\n");return;}printf("Queue elements:\n");for (int i = q.front; i <= q.rear; i++) {printf("%d ", q.items[i]);}printf("\n");
}int main() {int time = getTime();Queue q;initQueue(&q);// 入队操作enqueue(&q, 6);enqueue(&q, 2);enqueue(&q, 18);enqueue(&q, 0);enqueue(&q, 3);// 出队操作  int element;while (dequeue(&q, &element)) {  printf("Element dequeued: %d\n", element);  }  // 再次入队  enqueue(&q, 4);  enqueue(&q, 5);enqueue(&q, 10);enqueue(&q, 1);// 打印队列元素  printQueue(q);return 0;
}

运行结果如下：