順序表

順序表

． 順序表的定義
() 順序存儲方法
　    即把線性表的結點按邏輯次序依次存放在一組地址連續的存儲單元裡的方法
() 順序表（Sequential List）
　    用順序存儲方法存儲的線性表簡稱為順序表（Sequential List）

． 結點ai 的存儲地址
    　不失一般性設線性表中所有結點的類型相同則每個結點所占用存儲空間大小亦相同假設表中每個結點占用c個存儲單元其中第一個單元的存儲地址則是該結點的存儲地址並設表中開始結點a的存儲地址（簡稱為基地址）是LOC（a）那麼結點ai的存儲地址LOC（ai）可通過下式計算
            LOC（a_i）= LOC（a）+（i）*c   ≤i≤n
 注意
    　在順序表中每個結點ai的存儲地址是該結點在表中的位置i的線性函數只要知道基地址和每個結點的大小就可在相同時間內求出任一結點的存儲地址是一種隨機存取結構

．順序表類型定義
  #define ListSize //表空間的大小可根據實際需要而定這裡假設為
  typedef int DataType; //DataType的類型可根據實際情況而定這裡假設為int
  typedef struct {
      DataType data[ListSize]//向量data用於存放表結點
      int length//當前的表長度
     }SeqList
       
注意
　    ① 用向量這種順序存儲的數組類型存儲線性表的元素外順序表還應該用一個變量來表示線性表的長度屬性因此用結構類型來定義順序表類型
    　② 存放線性表結點的向量空間的大小ListSize應仔細選值使其既能滿足表結點的數目動態增加的需求又不致於預先定義過大而浪費存儲空間
    　③ 由於C語言中向量的下標從開始所以若L是SeqList類型的順序表則線性表的開始結點a和終端結點an分別存儲在L．data[]和L．Data[L．length]中
    　④ 若L是SeqList類型的指針變量則a和an分別存儲在L＞data[]和L＞data[L＞length]中

．順序表的特點
    　順序表是用向量實現的線性表向量的下標可以看作結點的相對地址因此順序表的的特點是邏輯上相鄰的結點其物理位置亦相鄰

 

From:http://tw.wingwit.com/Article/program/sjjg/201311/23959.html