資料結構——順序表

基本概念和術語

• 資料：客觀事物的符号表示，是所有能輸入到計算機中并被計算機程式處理的符号的總稱。如：整數、實數、字元串、圖形、圖像、聲音等經過特殊編碼後的資料。
• 資料元素：資料的基本機關，在計算機中通常作為一個整體進行考慮和處理。（資料元素也稱為元素、記錄等）。資料元素用于完整地描述一個對象，如：學生記錄、樹中棋盤的一個格局、圖中的一個頂點等。
• 資料項：組成資料元素的、有獨立含義的、不可分割的最小機關。例如：學生基本資訊表中的學号、姓名、性别等。
• 資料對象：性質相同的資料元素的集合，是資料的一個子集。（隻要集合内元素性質均相同，都可稱之為一個資料對象）
• 資料結構：互相之間存在一種或多種特定關系的資料元素的集合。換句話說，資料結構是帶“結構”的資料元素的集合，“結構”就是指資料元素之間存在的關系。
  • 邏輯結構：從具體問題抽象出來的數學模型，從邏輯關系上描述資料，它與資料的存儲無關。
    • 非線性結構：具有多個分支的層次結構
      • 集合結構：資料元素之間除了“屬于同一集合”的關系外，别無其他關系。
      • 樹形結構：資料元素之間存在一對多的關系。
        • 樹
        • 二叉樹
      • 圖狀結構：資料元素之間存在多對多的關系。
        • 有向圖（邊是頂點的有序對）
        • 無向圖（邊是頂點的無序對）
    • 線性結構：資料元素之間存在一對一的關系。
      • 線性表
        • 一般線性表
        • 特殊線性表
          • 棧與隊列
          • 字元串
        • 線性表的推廣
          • 數組
          • 廣義表
  • 存儲結構（實體結構）：邏輯結構在計算機中的存儲表示
    • 順序存儲結構：連續的存儲空間
    • 鍊式存儲結構：無需占用一整塊存儲空間
• 抽象資料類型：由使用者定義的、表示應用問題的資料模型，以及定義在這個模型上的操作的總稱。
  • 資料對象
  • 資料對象上關系的集合
  • 對資料對象的基本操作的集合

順序表

順序存儲定義

• 把邏輯上相鄰的資料元素存儲在實體上相鄰的存儲單元中的存儲結構。
• 簡言之，邏輯上相鄰，實體上也相鄰

順序存儲方法

• 用一組位址連續的存儲單元依次存儲線性表的元素，可通過數組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
請按任意鍵繼續. . .