当前位置： 首页 > article >正文

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

article 2024/11/23 20:01:36

基础概念

抽象数据类型（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;
}

代码运行后显示：
在这里插入图片描述


http://www.kler.cn/a/406181.html

相关文章：

  • VSCode【下载】【安装】【汉化】【配置C++环境】【运行调试】（Windows环境）
  • 核间通信-Linux下RPMsg使用与源码框架分析
  • 基于RTEMS项目学习waf build system
  • 2024信创数据库TOP30之蚂蚁集团OceanBase
  • MongoDB 更新集合名
  • 雅思阅读TFNG题型7大解题思路
  • 远程服务器Docker使用本地代理加速访问外部资源
  • gitlab:使用脚本批量下载项目，实现全项目检索
  • 关于Linux中线程优先级的问题探讨
  • 【Linux】-学习笔记04
  • [ruby on rails] 安装docker
  • 量化交易系统开发-实时行情自动化交易-4.3.1.跨市场套利策略实现
  • JAVA中的Lamda表达式
  • Lua 实现继承的一种方式
  • n、nvm、nrm、pnpm、yarn各种指令大全
  • 设计模式之 责任链模式
  • .net 7.0 解决“The keyword field is required”的问题
  • 面向服务的软件工程——巨详细讲解商务流程建模符号 (BPMN)，一篇章带你入门BPMN！！！（week1）
  • 在win10环境部署opengauss数据库（包含各种可能遇到的问题解决）
  • 基于RTEMS项目学习waf build system
  • 「漏洞复现」ArcGIS 地理信息系统 任意文件读取漏洞
  • pycharm在使用conda虚拟环境时Terminal爆红问题
  • 2.STM32之通信接口《精讲》之IIC通信---软件实现IIC《深入浅出》面试必备！
  • Javaee文件的io操作
  • 使用 PyTorch 实现并训练 VGGNet 用于 MNIST 分类
  • Frida反调试对抗系列（二）