基本介紹
- 中文名：順序存儲
- 外文名：Sequential Storage
- 學科：計算機科學與技術
- 領域：數據結構
- 優點：存儲空間利用機率高
- 特點：邏輯與物理統一
簡介,連結存儲,順序表,
簡介
順序存儲是指用一段地址連續的存儲單元存儲相鄰數據元素，或把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關係由存儲單元的鄰接關係來體現（邏輯與物理統一），要求記憶體中可用的存儲單元的地址必須是連續的。優點：存儲密度大，存儲空間利用機率高。缺點：插入或刪除元素時不方便。與順序存儲相對應是連結存儲。這種方法主要用於線性的數據結構。對非線性結構也可以採用局部線性化的方法實現順序存儲。例如，在樹形結構中可以把結點按某種規則排成序列，用順序存儲方法把結點內部的信息稠密地存放在一起，而對結點之間的關係採用其他的存放方法。
順序存儲主要使用數組，採用順序存儲的優點：可以隨機訪問數組中的元素，即通過下標去訪問數組的元素；其缺點主要有二：其一，由於C語言中，數組一旦被聲明，其長度即該結構占用的存儲空間是固定的，申請的空間過大，造成空間的浪費同時也為維護該結構造成困難，申請過小，在程式運行過程中，有可能會造成結構空間不足，導致程式故障；其二，在插入，刪除數據時，通常會導致大量數據的移動，在等機率的前提下，平均需要移動整個結構中一半的元素，如果元素個體比較複雜問題將更為明顯。
連結存儲
數據元素之間的關係有兩種不同的表示方法：順序映象和非順序映象，並由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。數據的存儲結構，也稱為數據的物理結構，是數據的邏輯結構在計算機中的實現。
連結存儲方法它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關係是由附加的指針欄位表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常藉助於程式設計語言中的指針類型來實現。數據的鏈式存儲結構可用連結表來表示。
其中data表示值域，用來存儲節點的數值部分。P1, P2, …Pn(n≥1)均為指針域，每個指針域為其對應的後繼元素或前驅元素所在結點（以後簡稱為後繼結點或前驅結點）的存儲位置。通過結點的指針域(又稱為鏈域)可以訪問到對應的後繼結點或前驅結點，若一個結點中的某個指針域不需要指向其他結點，則令它的值為空（NULL）。在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的連結存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。
順序表
順序表是在計算機記憶體中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關係來反映數據元素之間邏輯上的相鄰關係，採用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機記憶體中一組地址連續的存儲單元中。
/* 線性表的動態分配順序存儲結構 */#define LIST_INIT_SIZE 10 /* 線性表存儲空間的初始分配量 */#define LIST_INCREMENT 2 /* 線性表存儲空間的分配增量 */typedef struct{ ElemType *elem; /* 存儲空間基址 */ int length; /* 當前長度 */ int listsize; /* 當前分配的存儲容量(以sizeof(ElemType)為單位) */}SqList;/* 順序表示的線性表的基本操作(12個) */void InitList(SqList *L) /* 算法2.3 */{ /* 操作結果：構造一個空的順序線性表L */ L->elem=malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW); /* 存儲分配失敗 */ L->length=0; /* 空表長度為0 */ L->listsize=LIST_INIT_SIZE; /* 初始存儲容量 */}void DestroyList(SqList *L){ /* 初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L */ free(L->elem); L->elem=NULL; L->length=0; L->listsize=0;}void ClearList(SqList *L){ /* 初始條件：順序線性表L已存在。操作結果：將L重置為空表 */ L->length=0;}Status ListEmpty(SqList L){ /* 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */ if(L.length==0) return TRUE; else return FALSE;}int ListLength(SqList L){ /* 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數 */ return L.length;}Status GetElem(SqList L,int i,ElemType *e){ /* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)。操作結果：用e返回L中第i個數據元素的值 */ if(i<1||i>L.length) return ERROR; *e=*(L.elem+i-1); return OK;}int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){ /* 初始條件：順序線性表L已存在，compare()是數據元素判定函式(滿足為1，否則為0) */ /* 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。 */ /* 若這樣的數據元素不存在，則返回值為0。 */ ElemType *p; int i=1; /* i的初值為第1個元素的位序 */ p=L.elem; /* p的初值為第1個元素的存儲位置 */ while(i<=L.length&&!compare(*p++,e)) ++i; if(i<=L.length) return i; else return 0;}Status PriorElem(SqList L,ElemType cur_e,ElemType *pre_e){ /* 初始條件：順序線性表L已存在 */ /* 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅， */ /* 否則操作失敗，pre_e無定義 */ int i=2; ElemType *p=L.elem+1; while(i<=L.length&&*p!=cur_e) { p++; i++; } if(i>L.length) return INFEASIBLE; /* 操作失敗 */ else { *pre_e=*--p; return OK; }}Status NextElem(SqList L,ElemType cur_e,ElemType *next_e){ /* 初始條件：順序線性表L已存在 */ /* 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼， */ /* 否則操作失敗，next_e無定義 */ int i=1; ElemType *p=L.elem; while(i<L.length&&*p!=cur_e) { i++; p++; } if(i==L.length) return INFEASIBLE; /* 操作失敗 */ else { *next_e=*++p; return OK; }}Status ListInsert(SqList *L,int i,ElemType e) { /* 初始條件：順序線性表L已存在，1≤i≤ListLength(L)+1 */ /* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */ ElemType *newbase,*q,*p; if(i<1||i>L->length+1) /* i值不合法 */ return ERROR; if(L->length>=L->listsize) /* 當前存儲空間已滿,增加分配 */ { newbase=realloc(L->elem,(L->listsize+LIST_INCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); /* 存儲分配失敗 */ L->elem=newbase; /* 新基址 */ L->listsize+=LIST_INCREMENT; /* 增加存儲容量 */ } q=L->elem+i-1; /* q為插入位置 */ for(p=L->elem+L->length-1;p>=q;--p) /* 插入位置及之後的元素右移 */ *(p+1)=*p; *q=e; /* 插入e */ ++L->length; /* 表長增1 */ return OK;}Status ListDelete(SqList *L,int i,ElemType *e) { /* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */ /* 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1 */ ElemType *p,*q; if(i<1||i>L->length) /* i值不合法 */ return ERROR; p=L->elem+i-1; /* p為被刪除元素的位置 */ *e=*p; /* 被刪除元素的值賦給e */ q=L->elem+L->length-1; /* 表尾元素的位置 */ for(++p;p<=q;++p) /* 被刪除元素之後的元素左移 */ *(p-1)=*p; L->length--; /* 表長減1 */ return OK;}void ListTraverse(SqList L,void(*vi)(ElemType*)){ /* 初始條件：順序線性表L已存在 */ /* 操作結果：依次對L的每個數據元素調用函式vi() */ /* vi()的形參加'&'，表明可通過調用vi()改變元素的值 */ ElemType *p; int i; p=L.elem; for(i=1;i<=L.length;i++) vi(p++); printf("\n");}