複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/順序存儲/23162204
複製
複製成功

順序存儲

鎖定
順序存儲是所有的結點元素存放在一塊連續的存儲區域中，用存儲結點的物理位置來體現結點之間的邏輯關係的存儲方法。在高級語言中，一塊連續的存儲空間通常可用一個數組來表示。因此，順序存儲通常用一個數據元素類型的數組來存儲。最經典的順序存儲結構是順序表，將線性結構的元素按序存放在一個數組中 [1]  。
中文名
順序存儲
外文名
Sequential Storage
學    科
計算機科學與技術
領    域
數據結構
優    點
存儲空間利用概率高
特    點
邏輯與物理統一

目錄

  1. 1 簡介
  2. 2 鏈接存儲
  3. 3 順序表

順序存儲簡介

順序存儲是指用一段地址連續的存儲單元存儲相鄰數據元素，或把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關係由存儲單元的鄰接關係來體現（邏輯與物理統一），要求內存中可用的存儲單元的地址必須是連續的。優點：存儲密度大，存儲空間利用概率高。缺點：插入或刪除元素時不方便。與順序存儲相對應是鏈接存儲。這種方法主要用於線性的數據結構。對非線性結構也可以採用局部線性化的方法實現順序存儲。例如，在樹形結構中可以把結點按某種規則排成序列，用順序存儲方法把結點內部的信息稠密地存放在一起，而對結點之間的關係採用其他的存放方法。
順序存儲主要使用數組，採用順序存儲的優點：可以隨機訪問數組中的元素，即通過下標去訪問數組的元素；其缺點主要有二：其一，由於C語言中，數組一旦被聲明，其長度即該結構佔用的存儲空間是固定的，申請的空間過大，造成空間的浪費同時也為維護該結構造成困難，申請過小，在程序運行過程中，有可能會造成結構空間不足，導致程序故障；其二，在插入，刪除數據時，通常會導致大量數據的移動，在等概率的前提下，平均需要移動整個結構中一半的元素，如果元素個體比較複雜問題將更為明顯 [2]  。

順序存儲鏈接存儲

數據元素之間的關係有兩種不同的表示方法：順序映象和非順序映象，並由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。數據的存儲結構，也稱為數據的物理結構，是數據的邏輯結構在計算機中的實現。
鏈接存儲方法它不要求邏輯上相鄰的結點在物理位置上亦相鄰，結點間的邏輯關係是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構，鏈式存儲結構通常藉助於程序設計語言中的指針類型來實現。數據的鏈式存儲結構可用鏈接表來表示。
其中data表示值域，用來存儲節點的數值部分。P1, P2, …Pn(n≥1)均為指針域，每個指針域為其對應的後繼元素或前驅元素所在結點（以後簡稱為後繼結點或前驅結點）的存儲位置。通過結點的指針域(又稱為鏈域)可以訪問到對應的後繼結點或前驅結點，若一個結點中的某個指針域不需要指向其他結點，則令它的值為空（NULL）。在數據的順序存儲中，由於每個元素的存儲位置都可以通過簡單計算得到，所以訪問元素的時間都相同；而在數據的鏈接存儲中，由於每個元素的存儲位置保存在它的前驅或後繼結點中，所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到，訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。

順序存儲順序表

順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關係來反映數據元素之間邏輯上的相鄰關係，採用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中 [3]  。
/* 線性表的動態分配順序存儲結構 */
#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");
}
參考資料
  • 1.    夏徵農，陳至立主編；幹福熹編,大辭海 信息科學卷,上海辭書出版社,2015.12,第107頁
  • 2.    線性結構的順序存儲和鏈式存儲  ．中國知網[引用日期2019-06-14]
  • 3.    李淑芬．計算機軟件技術基礎：機械工業出版社，2013