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

数据结构第1问：什么是数据结构？

news 2025/7/28 8:03:36

什么是数据结构

数据结构指的是相互之间存在某种特定关系的数据元素的集合。"数据"则是指存在关系的数据元素的集合；“结构”则是指数据元素之间的特定关系，这种关系不仅体现在逻辑上，也体现在存储上，同时也包含对数据元素的具体操作。

数据结构由数据元素集合，逻辑结构，存储结构，数据的运算三要素组成。

eg：建立一张线性表，并用顺序存储的方式将表内数据元素存放在内存中，设计并实现对线性表的创建、修改、删除等操作。这就是一个数据结构。

逻辑结构：指的是数据元素在逻辑上呈现出来的一种关系，这种关系与数据的存储无关。例如：一张线性表，既可以用顺序存储的方式存放在内存中，也可以用链式存储的方式存放在内存中。数据的逻辑结构分为线性结构和非线性结构。
1. 线性结构：数据元素之间存在“一对一”的相邻关系，除了第一个元素和最后一个元素，每个元素都有且只有一个直接前驱和一个直接后继。
2. 非线性结构：数据元素之间是一对多或多对多的关系，没有简单的“前驱-后继”线性顺序，比如分支、层次等。
存储结构：指的是数据结构在计算机中的表示，也叫物理结构。包括数据元素的表示和关系的表示。
1. 数据元素的表示：即每个数据元素的具体位置和存放方式，比如：把温度值放在内存地址0x0001的那个字节里。
2. 关系的表示：即数据元素之间怎么联系起来的，比如：链表节点是通过指针将前后两个元素连接的。
存储结构主要有顺序存储、链式存储、索引存储和散列存储。
1. 顺序存储：数据元素在内存中按顺序连续存放的存储方式。
2. 链式存储：数据元素存储在任意位置，每个元素包含数据及“指针”（或链接），指向下一个元素的存储地址。
3. 索引存储：在顺序存储的基础上，为数据建立一个“索引表”，索引表中存储关键字和对应数据的地址。
4. 散列存储：通过哈希函数把关键字映射到存储位置，实现数据的快速查找和插入。
数据的运算：即对数据的运算，包括运算的定义和实现。运算的定义是针对逻辑结构的，确定运算的功能；运算的实现是针对存储结构的，确定运算的具体操作步骤。比如：确定一个线性表具有增删改查初始化这些功能，然后编程实现这些功能。细分下来有5个部分：
1. 基本操作：指对数据元素及其集合所能进行的最基本的操作。常见的基本操作包括：创建、插入、删除、查找、更新、遍历等。
2. 性能分析：评估这些基本操作在不同数据结构和实现方法上的效率。主要用时间复杂度和空间复杂度来描述。
3. 抽象数据类型（ADT）：抽象数据类型是对数据及相关操作的数学模型。它定义了数据的逻辑结构和行为规范，而不涉及具体的存储和实现细节。例如：栈（Stack）、队列（Queue）、列表（List）、集合（Set）等都是ADT。ADT为数据运算提供统一的接口和操作集合。
4. 运算定义：对基本操作进行形式化描述，明确输入、输出以及具体功能。通过规范的定义，精确描述操作的语义和约束。有利于后续实现和验证操作的正确性。例如，栈的“入栈”操作定义为：将元素插入栈顶，若栈满则报错。
5. 运算实现：根据抽象定义，利用具体的数据结构和计算机语言实现基本操作。实现时需要考虑存储结构（顺序存储、链式存储等）和算法设计。目标是保证操作的正确性和效率。

分析单链表数据结构

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct Node {int data;           // 数据元素（节点存储的具体数据）struct Node *next;  // 指向下一个节点的指针，表示节点之间的逻辑关系
} Node;// 创建新节点
Node* createNode(int value) {Node* newNode = (Node*)malloc(sizeof(Node)); // 在堆上分配内存if (newNode == NULL) {printf("内存分配失败！\n");exit(-1);}newNode->data = value;  // 设置数据newNode->next = NULL;   // 初始化指针为空return newNode;
}// 插入节点到链表头部
void insertAtHead(Node** head, int value) {Node* newNode = createNode(value);newNode->next = *head;  // 新节点指向原来的头节点*head = newNode;        // 头指针指向新节点
}// 打印链表
void printList(Node* head) {Node* current = head;while (current != NULL) {printf("%d -> ", current->data);  // 输出节点数据current = current->next;           // 移动到下一个节点}printf("NULL\n");
}// 释放链表内存
void freeList(Node* head) {Node* current = head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}
}int main() {Node* head = NULL; // 初始化空链表insertAtHead(&head, 10);insertAtHead(&head, 20);insertAtHead(&head, 30);printList(head); // 输出：30 -> 20 -> 10 -> NULLfreeList(head);  // 释放链表内存return 0;
}

针对上面给出的单链表数据结构，这里对逻辑结构、存储结构、数据的运算分别进行阐述：

逻辑结构

单链表是线性表的逻辑结构，表现为：
- 一组数据元素（节点）按照顺序排列，
- 每个节点只有一个直接后继（除了最后一个节点），
- 头结点指向第一个元素，链接表示元素的顺序关系，符合线性结构。
存储结构
存储结构定义：单链表采用链式存储结构。在内存中，每个节点动态分配一个连续的存储单元，存储数据元素和一个指针。指针字段存储的是下一个节点的内存地址，通过这个地址实现链式连接。这种存储结构可以实现动态分配，不需要连续分配内存，灵活且节省空间。头节点指针head保存了整个链表的入口地址。
数据的运算
1. 基本操作
  1. 创建节点：createNode函数负责分配节点空间、初始化数据和指针。
  2. 插入操作：insertAtHead在链表头部插入新节点。
  3. 遍历和访问：printList顺序访问链表所有节点的数据。
  4. 释放内存：freeList释放整个链表占用的内存，防止内存泄漏。
2. 性能分析
  1. 插入头节点时间复杂度为O(1)，因为直接操作头指针，无需遍历。
  2. 遍历链表打印所有元素，时间复杂度O(n)，必须访问每个节点。
  3. 内存使用动态分配，节点数量随着插入变化，节省空间。
  4. 链表不支持随机访问（例如访问第k个节点），访问需从头节点开始，效率较数组低。
3. 抽象数据类型
  1. 链表实现对应一个线性表的ADT，具体抽象规范例如：
    - 存放数据元素的有序集合；
    - 支持插入、遍历、删除等操作；
    - 逻辑上每个元素有唯一直接后继。
4. 运算定义
  1. 对各基本操作的定义明确了输入、输出和功能：
    - createNode(value)生成一个数据为value的节点。
    - insertAtHead(&head, value)将value插入链表头。
    - printList(head)遍历打印链表所有值。
    - freeList(head)释放链表所有节点内存。
  这些定义保证操作有明确执行规范，有利于程序正确实现。
5. 运算实现
  1. 利用C语言指针动态内存分配实现链表节点。
  2. insertAtHead通过修改指针改变链表连接关系，完成链式添加。
  3. printList和freeList通过循环指针操作遍历链表结构。
  4. 结合存储结构实现ADT的抽象操作，保证各操作功能完整且有效。