基本概念和術語
數據：客觀事物的符號表示，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。如：整數、實數、字符串、圖形、圖像、聲音等經過特殊編碼后的數據。
數據元素：數據的基本單位，在計算機中通常作為一個整體進行考慮和處理。（數據元素也稱為元素、記錄等）。數據元素用于完整地描述一個對象，如：學生記錄、樹中棋盤的一個格局、圖中的一個頂點等。
數據項：組成數據元素的、有獨立含義的、不可分割的最小單位。例如：學生基本信息表中的學號、姓名、性別等。
數據對象：性質相同的數據元素的集合，是數據的一個子集。（只要集合內元素性質均相同，都可稱之為一個數據對象）
數據結構：相互之間存在一種或多種特定關系的數據元素的集合。換句話說，數據結構是帶“結構”的數據元素的集合，“結構”就是指數據元素之間存在的關系。
邏輯結構：從具體問題抽象出來的數學模型，從邏輯關系上描述數據，它與數據的存儲無關。
非線性結構：具有多個分支的層次結構
集合結構：數據元素之間除了“屬于同一集合”的關系外，別無其他關系。
樹形結構：數據元素之間存在一對多的關系。
樹
二叉樹
圖狀結構：數據元素之間存在多對多的關系。
有向圖（邊是頂點的有序對）
無向圖（邊是頂點的無序對）
線性結構：數據元素之間存在一對一的關系。
線性表
一般線性表
線性表
特殊線性表
棧與隊列
字符串
線性表的推廣
數組
廣義表
存儲結構（物理結構）：邏輯結構在計算機中的存儲表示
順序存儲結構：連續的存儲空間
鏈式存儲結構：無需占用一整塊存儲空間
抽象數據類型：由用戶定義的、表示應用問題的數據模型，以及定義在這個模型上的操作的總稱。
數據對象
數據對象上關系的集合
對數據對象的基本操作的集合
順序表
順序存儲定義
把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。
簡言之，邏輯上相鄰，物理上也相鄰
順序存儲方法
用一組地址連續的存儲單元依次存儲線性表的元素，可通過數組V[n]來實現。
順序表的特點
利用數據元素的存儲位置表示線性表中相鄰數據元素之間的前后關系，即線性表的邏輯結構與存儲結構一致
在訪問線性表時，可以快速地計算出任何一個數據元素的存儲地址。因此可以粗略地認為，訪問每個元素所花時間相等
順序表的優缺點
優點
存儲密度大（結點本身所占存儲量/結點結構所占存儲量）
可以隨機存取表中任一元素
缺點
在插入、刪除某一元素時，需要移動大量元素
浪費存儲空間
屬于靜態存儲形式，數據元素的個數不能自由擴充
C++代碼實現
#include #include 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 請按任意鍵繼續. . .
數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
