C语言基础学习：抽象数据类型（ADT）

基础概念

抽象数据类型（ADT）是一种数据类型，它定义了一组数据以及可以在这组数据上执行的操作，但隐藏了数据的具体存储方式和实现细节。在C语言中，抽象数据类型（ADT）是一种非常重要的概念，它允许程序员定义和操作自定义的数据结构，而无需关心其底层实现细节。通过ADT可以创建出既安全又高效的数据管理方案，为复杂问题的解决提供有力支持。
使用ADT的优点：
封装性：隐藏数据表示和实现细节，只暴露操作接口，提高了代码的安全性和可维护性。
复用性：ADT可以作为独立的模块进行开发和测试，方便在不同项目中复用。
抽象性：通过ADT，我们可以更关注于数据操作的逻辑，而不是数据的具体存储方式。

ADT由以下两部分组成:
数据表示：定义数据的存储结构，通常使用结构体来封装数据成员。
操作接口：定义可以在数据上执行的操作，如创建、销毁、访问、修改等，这些操作通过函数来实现。

基于链表的ADT实现数据封装

这里使用基于链表的ADT实现数据封装来进行展示，数据封装是一种把数据和操作数据的函数捆绑在一起的机制，在C语言中，可以通过结构体和函数来实现数据封装，结构体用于存储数据，而函数则用于操作这些数据。
操作步骤如下：
1.定义链表节点的结构体：包含数据域和指针域。
2.定义链表ADT的操作函数：如初始化链表、在链表末尾添加元素、清空链表等。
3.实现这些操作函数：通过函数来操作链表，隐藏链表的具体实现细节。

#include <stdio.h>
#include <stdlib.h>// 定义链表节点的结构体
typedef struct ListNode {int data;struct ListNode* next;
} ListNode;// 定义链表ADT的操作函数
typedef struct {ListNode* head;
} List;// 初始化链表
void initList(List* list) {list->head = NULL;
}// 在链表末尾添加一个元素
void appendToList(List* list, int value) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = value;newNode->next = NULL;if (list->head == NULL) {list->head = newNode;} else {ListNode* current = list->head;while (current->next != NULL) {current = current->next;}current->next = newNode;}
}// 清空链表
void clearList(List* list) {ListNode* current = list->head;while (current != NULL) {ListNode* next = current->next;free(current);current = next;}list->head = NULL;
}// 打印链表
void printList(List* list) {ListNode* current = list->head;while (current != NULL) {printf("%d -> ", current->data);current = current->next;}printf("NULL\n");
}int main() {List myList;initList(&myList);appendToList(&myList, 1);appendToList(&myList, 2);appendToList(&myList, 3);printList(&myList);clearList(&myList);printList(&myList);return 0;
}

运行后在终端显示以下内容

接口实现

接口是ADT与用户之间的桥梁。它规定了用户可以如何访问和操作ADT中的数据，而不涉及数据的内部表示。在C语言中，接口通常通过头文件（.h文件）来定义，其中包含了数据类型的声明和函数原型的声明。实现接口意味着为ADT定义具体的操作。这些操作在C语言中通过函数来实现。函数的定义通常放在源文件（.c文件）中，并且这些函数会操作ADT的内部数据。
这里通过定义一个栈的ADT来实现数据封装，并通过接口来访问栈的操作。
步骤如下：
定义栈的ADT：在头文件中声明栈的结构体和函数原型。
实现栈的操作：在源文件中定义栈的操作函数。
使用栈的ADT：在主程序中通过接口来操作栈。

先定义一个栈操作的头文件

// stack.h
#ifndef STACK_H
#define STACK_H// 定义栈的ADT
typedef struct {int* data;int top;int capacity;
} Stack;// 栈的操作函数原型
void initStack(Stack* stack);
int isStackEmpty(Stack* stack);
void push(Stack* stack, int value);
int pop(Stack* stack);
int peek(Stack* stack);
void clearStack(Stack* stack);#endif

在编写一个用来实现栈操作的C语言文件

// stack.h
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"// 栈的内部表示
struct Stack {int* data;int top;int capacity;
};// 初始化栈
void initStack(Stack* stack) {stack->data = (int*)malloc(100 * sizeof(int));stack->top = -1;stack->capacity = 100;
}// 检查栈是否为空
int isStackEmpty(Stack* stack) {return stack->top == -1;
}// 压栈
void push(Stack* stack, int value) {if (stack->top < stack->capacity - 1) {stack->data[++stack->top] = value;} else {// 如果栈满，输出提示printf("被填满了\n");}
}// 出栈
int pop(Stack* stack) {if (!isStackEmpty(stack)) {return stack->data[stack->top--];} else {// 栈空，处理栈下溢，返回特殊值表示错误return -1; // -1不是栈中的有效值}
}// 查看栈顶元素
int peek(Stack* stack) {if (!isStackEmpty(stack)) {return stack->data[stack->top];} else {return -1; }
}// 清空栈
void clearStack(Stack* stack) {free(stack->data);stack->top = -1;stack->capacity = 0;
}

最后编写出主文件

// main.c
#include <stdio.h>
#include "stack.h"int main() {Stack myStack;initStack(&myStack);push(&myStack, 10);push(&myStack, 20);push(&myStack, 30);printf("栈顶部的元素是： %d\n", peek(&myStack));while (!isStackEmpty(&myStack)) {printf("弹出的元素是： %d\n", pop(&myStack));}clearStack(&myStack);return 0;
}

代码运行后在终端输出以下内容：

队列ADT

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入（队尾），在另一端进行删除（队头），任务按照它们被添加到队列中的顺序被调度执行。

队列ADT的操作步骤如下：
入队（EnQueue）：
将一个元素添加到队列的末尾（队尾）。
这是队列的核心操作之一，用于在队列中插入新元素。
出队（DeQueue）：
从队列的开头（队头）移除一个元素，并返回该元素的值。
出队操作遵循先进先出（FIFO）的原则，即最先入队的元素最先被移除。
判空（QueueEmpty）：
检查队列是否为空。
这是一个常用的辅助操作，用于确定队列中是否还有元素。
获取队头元素（GetHead 或 Front）：
返回队列开头元素的值，但不移除该元素。
这允许用户查看队列的当前状态，而不改变队列的内容。
队列长度（QueueLength）：
返回队列中元素的数量。
这个操作对于需要知道队列大小的情况非常有用。
清空队列（ClearQueue）：
移除队列中的所有元素，使队列变为空。
这在需要重置队列或释放内存时很有用。
销毁队列（DestroyQueue）：
释放队列所占用的所有资源，包括内存。
这是在队列不再需要时进行的清理操作。

以下代码运行后程序会提示用户输入队列元素的数量，然后输入具体的元素。接着程序会遍历队列、出队一个元素、获取队头元素、显示队列长度，并判断队列是否为空。最后销毁队列。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int QElemType;typedef struct QNode {QElemType data;struct QNode* next;
} QNode, *QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;
} LinkQueue;// 初始化队列
bool InitQueue(LinkQueue* q) {if (!q) {printf("队列不存在!\n");return false;}q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));if (!q->front) {printf("内存分配失败!\n");return false;}q->front->next = NULL;return true;
}// 销毁队列
bool DestroyQueue(LinkQueue* queue) {if (!queue) {printf("队列不存在!\n");return false;}while (queue->front != NULL) {queue->rear = queue->front->next;free(queue->front);queue->front = queue->rear;}return true;
}// 清空队列
bool ClearQueue(LinkQueue* q) {if (!q) {printf("队列不存在!\n");return false;}QueuePtr p = q->front->next, tmp;while (p) {tmp = p->next;free(p);p = tmp;}q->front = q->rear;return true;
}// 判断队列是否为空
bool QueueEmpty(LinkQueue q) {if (!&q) {printf("空队列!\n");return false;}if (q.front == q.rear) {return true;}return false;
}// 插入元素e为q的新队尾元素
bool EnQueue(LinkQueue* q, QElemType e) {QueuePtr p = (QueuePtr)malloc(sizeof(QNode));if (!p) {printf("内存分配失败!\n");return false;}p->data = e;p->next = NULL;q->rear->next = p;q->rear = p;return true;
}// 出队
bool DeQueue(LinkQueue* q, QElemType* e) {if (!q) {printf("队列不存在!\n");return false;}if (QueueEmpty(*q)) {printf("空队列!\n");return false;}QueuePtr p = q->front->next;*e = p->data;q->front->next = p->next;if (q->front == q->rear) {q->rear = q->front;}free(p);return true;
}// 获取队首元素
bool GetHead(LinkQueue q, QElemType* e) {if (!(&q)) {printf("队列不存在!\n");return false;}if (QueueEmpty(q)) {printf("空队列!\n");return false;}*e = q.front->next->data;return true;
}// 队列长度
int QueueLength(LinkQueue q) {if (!&q) {printf("队列不存在!\n");return 0;}int len = 0;QueuePtr p = q.front->next;while (p) {len++;p = p->next;}return len;
}// 遍历队列
void QueueTraverse(LinkQueue q) {if (!(&q)) {printf("队列不存在!\n");return;}if (QueueEmpty(q)) {printf("队列为空!\n");return;}QueuePtr p = q.front->next;while (p) {printf("%d ", p->data);p = p->next;}printf("\n");
}int main() {LinkQueue que;QElemType data;int n;if (!InitQueue(&que)) {return 1;}printf("输入队列元素数量:\n");scanf("%d", &n);printf("输入队列中元素:\n");while (n--) {scanf("%d", &data);EnQueue(&que, data);}printf("遍历队列:\n");QueueTraverse(que);if (DeQueue(&que, &data)) {printf("出队元素: %d\n", data);}if (GetHead(que, &data)) {printf("队头元素: %d\n", data);}printf("队列长度: %d\n", QueueLength(que));if (QueueEmpty(que)) {printf("队列为空!\n");} else {printf("队列不为空!\n");}DestroyQueue(&que);return 0;
}

代码运行后显示：