基本概念和术语

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

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

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

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

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

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

        • 树
        • 二叉树

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

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

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

      • 线性表

        • 一般线性表

          • 线性表

        • 特殊线性表

          • 栈与队列
          • 字符串

        • 线性表的推广

          • 数组
          • 广义表

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

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

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

  • 数据对象
  • 数据对象上关系的集合
  • 对数据对象的基本操作的集合

顺序表

顺序存储定义

• 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
• 简言之，逻辑上相邻，物理上也相邻

顺序存储方法

• 用一组地址连续的存储单元依次存储线性表的元素，可通过数组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 >= q; p--)
        * (p + 1) = *p;
    *q = e;
    L.length++;
    return OK;
}


/*Status insert(Sqlist& L, int i, ElemType e)
{
    if (i < 1 || i > L.length + 1)
        return ERROR;
    if (L.length == MAXSIZE)
        return OVERFLOW;
    int* p, * q;
    q = L.elem + i - 1;
    for (p = L.elem + L.length - 1; p >= q; p--)
        * (p + 1) = *p;
    *q = e;
    L.length++;
    return OK;
}*/

// 获取 i 处元素的值，并将其保存在 e 中
Status GetElem(Sqlist L, int i, ElemType& e)
{
    if (i < 1 || i > L.length) return ERROR;
    e = L.elem[i - 1];
    return OK;
}

// 在顺序表中查找值为 e 的元素，并返回其位置
int Search(Sqlist L, ElemType e) // 多种查找方式
{
    int i;
    for (i = 0; L.elem[i] != e && i < L.length; i++);
    if (i < L.length) return i + 1;
    else return 0;
}

/*int LocateElem(Sqlist L, ElemType e)
{
    // 在顺序表 L 中查找值为 e 的数据元素， 返回其序号
    for(i = 0; i < L.length; i ++)
        if(L.elem[i] == e) return i + 1;
    return 0;
}*/

// 删除顺序表中位置为 i 的元素，并将其值保存在 e 中
Status ListDelete(Sqlist &L, int i, ElemType& e) 
{
    if (i < 1 || i > L.length) return ERROR;
    e = L.elem[i - 1];
    int j;
    for (j = i; j < L.length; j++)
        L.elem[j - 1] = L.elem[j];
    L.length--;
    return OK;
}

// 创建顺序表
Status Create(Sqlist& L, int n)
{
    int i;
    if (n < 0) return ERROR;
    for (i = 0; i < n; i++)
        cin >> L.elem[i];
    L.length = n;
    return OK;
}

// 输出顺序表
void OutPut(Sqlist L)
{
    int i;
    for (i = 0; i < L.length; i++)
        cout << L.elem[i] << " ";
    cout << endl;
}

int main()
{
    // 以下为测试代码
    Sqlist L;
    int n, i, e;
    cout << "请输入顺序表的长度：";
    cin >> n;
    InitList_Sq(L);
    cout << "请输入数据：";
    Create(L, n);
    cout << "输出数据：";
    OutPut(L);
    cout << "顺序表的长度为：" << GetLength(L) << endl;  // 获取顺序表长度
    cout << IsEmpty(L) << endl;  // 查看顺序表是否为空
    cout << "请输入要查找的值：";
    cin >> e;
    cout << e << "所在位置为：" << Search(L, e) << endl;  // 查找
    cout << "请输入删除值的位置：";
    cin >> i;
    ListDelete(L, i, e);
    cout << "删除成功！ " << "您删除的值为：" << e << endl;
    cout << "此时的顺序表为：";
    OutPut(L);
    cout << "请输入您插入的位置：";
    cin >> i;
    cout << "请输入您要插入的值：";
    cin >> e;
    cout << ListInsert_Sq(L, i, e) << endl;
    cout << "此时的顺序表为：";
    OutPut(L);
    cout << "此时顺序表的长度为：" << GetLength(L) << endl;
    ClearList(L);
    cout << "此时顺序表的长度为：" << GetLength(L) << endl;
    DestroyList(L);
    return 0;
}

请输入顺序表的长度：5
请输入数据：1 2 3 4 5
输出数据：1 2 3 4 5
顺序表的长度为：5
0
请输入要查找的值：2
2所在位置为：2
请输入删除值的位置：3
删除成功！ 您删除的值为：3
此时的顺序表为：1 2 4 5
请输入您插入的位置：3
请输入您要插入的值：6
1
此时的顺序表为：1 2 6 4 5
此时顺序表的长度为：5
此时顺序表的长度为：0
请按任意键继续. . .