線性表的順序表示和實作

一、前言

    線性表的順序表示是指用一組位址連續的存儲單元依次存儲線性表的資料元素。

    一般來說，線性表的第i個資料元素ai的存儲位置為：

        loc(ai) = loc(a0)+(i-1)xl;

         其中loc(a0)表示的是第一個資料元素的存儲位置，通常稱為線性表的起始位置或者基位址。

        l代表的時每個資料元素需要占用l個存儲單元。

二、順序表

    1、概念：線性表的這種機内表示稱為線性表的順序存儲結構或者順序映像，通常，稱這種存儲結構的線性表為順序表。

    2、特點：以元素在計算機内“實體位置相鄰”來表示線性表中資料u之間的邏輯關系。隻要确定存儲線性表的起始位置，線性表中的任一進制素都可以随機存取，是以線性的順序存儲結構式一種随機存儲的存儲結構。

    3、通常用數組來描述資料結構中的順序存儲結構。

    4、線性表的動态配置設定順序存儲結構

// 線性表的動态配置設定順序存儲結構

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

<code>#define list_init_size   100   //線性表存儲空間的初始配置設定量</code>

<code>#define listincrement     10   //線性表存儲空間的配置設定增量</code>

<code>typedef </code><code>struct</code>

<code>{</code>

<code>    </code><code>elemtype  *elem;   </code><code>//存儲空間基位址</code>

<code>    </code><code>int</code> <code>length;      </code><code>//目前長度</code>

<code>    </code><code>int</code> <code>listsize;     </code><code>//目前配置設定的的存儲容量（以sizeof(elemtype)為機關）</code>

<code> </code> 

<code>}sqlist;</code>

　　

    5、初始化線性表

18

19

20

21

22

23

24

25

26

27

<code>status initlist_sq(sqlist   &amp;l)</code>

<code>    </code><code>//構造一個空的線性表</code>

<code>    </code><code>l.elem = (elemtype *)malloc(list_init_size*</code><code>sizeof</code><code>(elemtype));</code>

<code>    </code><code>if</code><code>(!l.elem)  </code><code>//存儲空間配置設定失敗</code>

<code>    </code><code>{</code>

<code>        </code><code>exit(overflow);</code>

<code>    </code><code>}</code>

<code>    </code> 

<code>    </code><code>l.length = 0;   </code><code>//空表長度為0</code>

<code>    </code><code>l.listsize = list_init_size;  </code><code>//初始存儲容量</code>

<code>    </code><code>return</code> <code>ok;</code>

<code>}  </code><code>//initlist_sql</code>

     6、線性表的插入

        一般情況下，在第i（1&lt;=i&lt;=n）個元素之前插入一個元素時，需要将第n個到第i（共n-i+1）個元素向後移動一個位置。

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

<code>status listinsert_sq(sqlist &amp;l,</code><code>int</code> <code>i,elemtype e)</code>

<code>//在順序線性表l中第i個位置之前插入新的元素e ，i的合法值為1&lt;=i&lt;=listlength_sq(l)+1</code>

<code>if</code><code>(i&lt;1 || i&gt;l.length+1)</code>

<code>return</code> <code>error;       </code><code>//i值不合法</code>

<code>}</code>

<code>if</code><code>(l.length&gt;=l.listsize)   </code><code>//目前存儲空間已滿，增加配置設定</code>

<code>newbase = (elemtype *)realloc(l.elem,(l.listsize+listincrement)*</code><code>sizeof</code><code>(elemtype));</code>

<code>if</code> <code>(!newbase)</code>

<code>exit(overflow);  </code><code>//存儲配置設定失敗</code>

<code>l.elem = newbase;   </code><code>//新基址</code>

<code>l.listsize+=listincrement;   </code><code>//增加存儲容量</code>

<code>q = &amp;(l.elem[i-1]);   </code><code>//q為插入位置</code>

<code>for</code><code>(p=&amp;(l.elem[l.length-1]);p&gt;=q;--p);--p)*(p+1) = *p;</code>

<code>*q = e;</code>

<code>++l.length;</code>

<code>return</code> <code>ok;</code>

    7、線性表順序存儲結構的特點：

        邏輯關系上相鄰的兩個元素在實體位置上也相鄰，是以可以随機存取表中任一進制素，它的存儲位置可以用一個簡單直覺的公式表hi

    8、線性表順序存儲結構的缺點

        每次做插入和删除操作時，需要移動大量的元素。