数据结构——顺序表

基本概念和术语数据：客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。如：整数、实数、字符串、图形、图像、声音等经过特殊编码后的数据。数据元素：数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。（数据元素也称为元素、记录等）。数据元素用于完整地描述一个对象，如：学生记录、树中棋盘的一个格局、图中的一个顶点等。数据项：组成数据元素的、有独立含义的、不可分割的最小单位。例如：学生基本信息表中的学号、姓名、性别等。数据对象：性质相同的数据元素的集合，是数据的一个子集。（只要集合内元素性质均相同，都可称之为一个数据对象）

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。

非线性结构：具有多个分支的层次结构

集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。

树形结构：数据元素之间存在一对多的关系。

树二叉树

图状结构：数据元素之间存在多对多的关系。

有向图（边是顶点的有序对）无向图（边是顶点的无序对）

线性结构：数据元素之间存在一对一的关系。

线性表

一般线性表

线性表

特殊线性表

栈与队列字符串

线性表的推广

数组广义表

存储结构（物理结构）：逻辑结构在计算机中的存储表示

顺序存储结构：连续的存储空间链式存储结构：无需占用一整块存储空间

抽象数据类型：由用户定义的、表示应用问题的数据模型，以及定义在这个模型上的操作的总称。

数据对象数据对象上关系的集合对数据对象的基本操作的集合顺序表顺序存储定义把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。简言之，逻辑上相邻，物理上也相邻顺序存储方法用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。顺序表的特点利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等 顺序表的优缺点

优点

存储密度大（结点本身所占存储量/结点结构所占存储量）可以随机存取表中任一元素

缺点

在插入、删除某一元素时，需要移动大量元素浪费存储空间属于静态存储形式，数据元素的个数不能自由扩充C++代码实现

#include stdlib.h 
#include iostream 
using namespace std;
#define MAXSIZE 100
#define OVERFLOW -2
#define ERROR -1
#define OK 1
typedef int Status;
typedef int ElemType; // 非整型
// 结点结构体
typedef struct {
 ElemType* elem;
 int length;
 // int listsize;
}Sqlist;
// 初始化顺序表
Status InitList_Sq(Sqlist L)
 L.elem = new ElemType[MAXSIZE];
 if (!L.elem) exit(OVERFLOW);
 L.length = 0;
 return OK;
// 销毁顺序表
void DestroyList(Sqlist L)
 if (!L.elem)
 delete[] L.elem;
// 清空顺序表
void ClearList(Sqlist L)
 L.length = 0;
// 获取顺序表的长度
int GetLength(Sqlist L)
 return L.length;
// 判断顺序表是否为空
int IsEmpty(Sqlist L)
 if (!L.elem)
 return 1;
 else
 return 0;
/*Status insert(Sqlist L, int i, ElemType e)
 int j;
 if (i 1 || i L.length + 1)
 return ERROR;
 if (L.length == MAXSIZE)
 return OVERFLOW;
 for (j = L.length - 1; j = i - 1; j--)
 L.elem[j + 1] = L.elem[j];
 L.elem[i - 1] = e;
 L.length++;
 return OK;
// 在 i 处插入元素
Status ListInsert_Sq(Sqlist L, int i, ElemType e)
 // 在顺序表L的第 i 个元素之前插入新的元素e
 if (i 1 || i L.length + 1)
 return ERROR;
 if (L.length == MAXSIZE)
 return OVERFLOW;
 ElemType* p, * q;
 q = (L.elem[i - 1]);
 for (p = (L.elem[L.length - 1]); p p--)
 * (p + 1) = *p;
 *q = e;
 L.length++;
 return OK;

本文转自网络，原文链接：https://developer.aliyun.com/article/786775
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！