计算机中的三原：数据结构简介以及抽象数据类型的实现

2024-05-03 03:21:25 0 0

数据结构简介

数据结构（英语：data structure）是计算机中存储、组织数据的方式。
数据结构意味着接口或封装：一个数据结构可被视为两个函数之间的接口，或者是由数据类型联合组成的存储内容的访问方法封装。
大多数数据结构都由数列、记录、可辨识联合、引用等基本类型构成。举例而言，可为空的引用（nullable reference）是引用与可辨识联合的结合体，而最简单的链式结构链表则是由记录与可空引用构成。
数据结构可透过编程语言所提供的数据类型、引用及其他操作加以实现。一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下，支持各种程序运行。
不同种类的数据结构适合不同种类的应用，部分数据结构甚至是为了解决特定问题而设计出来的。例如B树即为加快树状结构访问速度而设计的数据结构，常被应用在数据库和文件系统上。

基本概念和术语

数据是对客观事物的符号表示，在计算机科学中指的是所有能输入到计算机中并且被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机中通常作为一个整体进行考虑与处理。一个数据元素可以由若干个数据项组成，例如一个数名是一个数据元素，则书名信息的每一项例如书名，作者的都可为数据项。数据项是数据的不可分割的最小单位。
数据项是相同性质的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，它们之间的关系可分为4类：集合，线性，树，图。

数据结构可定义为一个二元组：
DATA Structure=(D,S);
其中D为数据元素的有限集合,S为D上关系的有限集合。
数据类型是一个值得集合和定义在这个值上的一组操作的总称。例如int是一个整型变量，其值为某个区间上的整数以及定义在其上的加减乘除操作。

抽象数据类型表现与实现

基本定义

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
定义如下：
ADT complex{
数据对象：D={real, image | real∈实数, image∈实数} [3]
数据关系：R={<real,image>} [3]
基本操作}

具体实现

#include <stdio.h>#define ok 1;#define ERROR 0;typedef int Status;typedef int ElemType;typedef struct{ElemType e[3];}Triplet;Status free(Triplet *T) //数组内容清空{for (int i = 0; i < 3; i++){T->e[i] = 0;}return ok;}Status InitTriplet(Triplet *T, ElemType v0, ElemType v1, ElemType v2) //三元数组初始化{//if (!T) exit(_CRT_GUARDOVERFLOW);T->e[0] = v0;T->e[1] = v1;T->e[2] = v2;return ok;}Status DestroyTriplet(Triplet *T) //三原数组销毁{free(T);T = NULL;return ok;}Status Get(Triplet *T, int i, ElemType *e) //得到位置i的数组值{if (i < 0 || i>3)return ERROR;e = T->e[i - 1];return e;}Status Put(Triplet *T, int i, ElemType e) //将第i个位置的数组值赋值给e{if (i < 0 || i>3)return ERROR;T->e[i - 1] = e;return ok;}Status IsAscending(Triplet *T) //判断数组是否升序排列{return ((T->e[0] < T->e[1]) && (T->e[1] < T->e[2]));}Status IsDescending(Triplet *T) //判断是否降序排列{return ((T->e[0] > T->e[1]) && (T->e[1] > T->e[2]));}Status Max(Triplet *T, ElemType *e) //找出数组的最大值{if (T->e[0] > T->e[1]){if (T->e[0] > T->e[2]){e = T->e[0];}elsee = T->e[2];}else{if (T->e[1] > T->e[2]){e = T->e[1];}elsee = T->e[2];}return e;}Status Min(Triplet *T, ElemType *e) //找出数组的最小值{if (T->e[0] < T->e[1]){if (T->e[0] < T->e[2]){e = T->e[0];}elsee = T->e[2];}else{if (T->e[1] < T->e[2]){e = T->e[1];}elsee = T->e[2];}return e;}Status ShowTriplet(Triplet *T) //打印数组{printf("三元组的值为：\n");for (int i = 0; i < 3; i++){printf("%d ", T->e[i]);}return ok;}int main(){Triplet T;Status i, flag;ElemType v0, v1, v2, e,e1,e2,e3;printf("请输入三元组的值：\n");scanf_s("%d %d %d", &v0, &v1, &v2);getchar();flag = InitTriplet(&T, v0, v1, v2);printf("初始化函数后，flag=%d\n，", flag);printf("三元组中三个值分别为：%d,%d,%d\n", T.e[0], T.e[1], T.e[2]);ShowTriplet(&T);Put(&T, 2, 5);printf("赋值之后的数组为%d %d %d", T.e[0], T.e[1], T.e[2]);e1=Get(&T, 1, &e);printf("得到数组第一个数字为：%d\n",e1);e2=Max(&T, e);printf("得到数组最大数字为：%d\n", e2);e3=Min(&T, e);printf("得到数组最小数字为：%d\n", e3);printf("判断三元组是否为升序：%d\n", IsAscending(&T));printf("判断三元组是否为降序：%d\n", IsDescending(&T));DestroyTriplet(&T);printf("三元组内容为：%d %d %d", T.e[0], T.e[1], T.e[2]);getchar();return 0;}