順序表結(jié)點(diǎn)結(jié)構(gòu)的定義？順序表的定義線性表的順序存儲(chǔ)也稱為順序表。它利用一組地址連續(xù)的存儲(chǔ)單元將數(shù)據(jù)元素依次存儲(chǔ)在一個(gè)線性表中，使得兩個(gè)邏輯上相鄰的元素在物理位置上也是相鄰的。假設(shè)線性表的元素類型是El

順序表結(jié)點(diǎn)結(jié)構(gòu)的定義？

順序表的定義

線性表的順序存儲(chǔ)也稱為順序表。它利用一組地址連續(xù)的存儲(chǔ)單元將數(shù)據(jù)元素依次存儲(chǔ)在一個(gè)線性表中，使得兩個(gè)邏輯上相鄰的元素在物理位置上也是相鄰的。

假設(shè)線性表的元素類型是ElemType，線性表的順序存儲(chǔ)類型描述為:

#定義MaxSize 50

typedef結(jié)構(gòu)

{

ElemType數(shù)據(jù)[MaxSize]

int長(zhǎng)度

}SqList

一維數(shù)組可以靜態(tài)或動(dòng)態(tài)分配。在靜態(tài)分配中，由于數(shù)組的大小和空間已經(jīng)提前固定，一旦空間滿了，添加新的數(shù)據(jù)就會(huì)溢出，導(dǎo)致程序崩潰甚至其他未知的異常。

在動(dòng)態(tài)分配中，存儲(chǔ)數(shù)組的空間是在程序執(zhí)行過(guò)程中通過(guò)動(dòng)態(tài)存儲(chǔ)分配語(yǔ)句來(lái)分配的。一旦存儲(chǔ)空間滿了，就會(huì)打開另一個(gè)更大的存儲(chǔ)區(qū)間來(lái)復(fù)制原來(lái)的元素，從而在不需要一次性分配大量空間的情況下，擴(kuò)展存儲(chǔ)數(shù)組的空間。

#定義InitSize 100

typedef結(jié)構(gòu)

{

ElemType* dataPtr

int長(zhǎng)度

int大小

}SqList

C語(yǔ)言的初始動(dòng)態(tài)分配語(yǔ)句是:(elem type *)malloc(Sizeof(elem type)* initsize)。

C語(yǔ)言的初始化動(dòng)態(tài)分配語(yǔ)句是:ElemType[InitSize]。

注意:動(dòng)態(tài)存儲(chǔ)不是市場(chǎng)存儲(chǔ)，它也屬于順序存儲(chǔ)。物理結(jié)構(gòu)沒有改變，它仍然與邏輯結(jié)構(gòu)相鄰，但分配的空間不再由編譯器決定，而是在運(yùn)行時(shí)分配。

2、序列表的特點(diǎn)

隨機(jī)存取:通過(guò)首地址和元素序號(hào)，可以在單位時(shí)間O(1)內(nèi)找到指定的元素。

存儲(chǔ)密度高:存儲(chǔ)密度高是因?yàn)槊總€(gè)節(jié)點(diǎn)的存儲(chǔ)空間指的是數(shù)據(jù)元素的存儲(chǔ)，沒有額外的開銷。

物理位置是相鄰的:物理位置和邏輯位置是一樣的，所以在插入和刪除元素的時(shí)候移動(dòng)大量的元素是很耗時(shí)的。這是所有與物理結(jié)構(gòu)相鄰的數(shù)據(jù)結(jié)構(gòu)的通病。雖然訪問速度很快，但是如果有頻繁的添加、刪除、移動(dòng)等操作，效率會(huì)很低。

3.序列表上基本操作的實(shí)現(xiàn)

只顯示了搜索、添加、刪除等三個(gè)操作，其余的在線性表中比較簡(jiǎn)單，在比較復(fù)雜的鏈表中顯示。

3.1、插入操作

在I (1 LTLTL中插入新元素e。序列表l的長(zhǎng)度1)位。

bool list insert(SQL list ampL，int i，ElemType e)

{

if (ilt1 || igtL.lenGth 1) //判斷我要插入的位置是否有效。

返回false

If (L.length gt MaxSize) //判斷是否超出存儲(chǔ)空間。

返回false

for(int j l . length j gt I j-)///將第I個(gè)元素及其后的元素向后移動(dòng)一個(gè)位置。

[j] [j - 1]

[i-1] e //在第I個(gè)位置插入元素E。

L.length //序列表長(zhǎng)度加1

返回true

}

最好的情況:在表的末尾插入(即in 1)，原元素不移動(dòng)，時(shí)間復(fù)雜度為O(1)。

最差情況:在頭(即i1)插入時(shí)，所有元素都需要后移一位，元素后向語(yǔ)句執(zhí)行n次，時(shí)間復(fù)雜度為O(n)。

平均情況:假設(shè)Pi(Pi1/(n-1))是在第I個(gè)位置插入一個(gè)節(jié)點(diǎn)的概率，在長(zhǎng)度為n的序列表中插入一個(gè)節(jié)點(diǎn)時(shí)，移動(dòng)節(jié)點(diǎn)的平均次數(shù)為n/2，時(shí)間復(fù)雜度為O(n)。

3.2.刪除操作

刪除序列表l中i(1ltiltL.length)位置的元素

bool list delete(SQL list ampL，int i，ElemTypeamp e)

{

If (ilt1 || igtL.length) //判斷我要插入的位置是否有效。

返回false

E [i-1] //將要?jiǎng)h除的數(shù)據(jù)保存到e。

For (int j i-1 j lt L.length j) //將第I個(gè)元素和后續(xù)元素向后移動(dòng)一個(gè)位置。

[j] [j 1]

長(zhǎng)度length-//序列表長(zhǎng)度加1

返回true

}

時(shí)間復(fù)雜度與插入相同(平均而言，插入總是比刪除每多一步操作，即插入操作，但不會(huì)引起數(shù)量級(jí)的變化，所以平均時(shí)間復(fù)雜度仍為O(N))。

3.3、按值搜索(順序搜索)

在序列表中找到第一個(gè)元素值等于e的元素的位置，沒有找到return -1。

int locate elem(SQL list L，const

倒序插入法的詳細(xì)計(jì)算步驟？

插入排序法的基本操作是將一個(gè)數(shù)據(jù)插入。在有序數(shù)據(jù)中(一開始可以認(rèn)為只有一個(gè)元素的序列是有序序列，即從第二個(gè)數(shù)據(jù)開始一個(gè)一個(gè)插入)，從而得到一個(gè)新的增加1的有序數(shù)據(jù)。

該算法適合對(duì)少量數(shù)據(jù)進(jìn)行排序，時(shí)間復(fù)雜度為O (n 2)。是一種穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分:第一部分包含數(shù)組的所有元素，除了最后一個(gè)元素(讓數(shù)組有更多的空間可以插入)，第二部分只包含這個(gè)元素(也就是要插入的元素)。第一部分排序后，將最后一個(gè)元素插入排序后的第一部分。

插入排序的基本思想是:在每一步，將一條待排序的記錄按照其鍵值的大小插入到先前排序的序列中的適當(dāng)位置，直到所有記錄都入。

為了避免重復(fù)比較是否出格，下面的插入排序使用 "哨兵 "。即在插入結(jié)束時(shí)，復(fù)制一份要插入的數(shù)據(jù)(a[0])的副本，一物兩用，既能保存數(shù)據(jù)，又能有效防止搜索越界，反復(fù)檢測(cè)是否越界。在每一輪中，比要插入的數(shù)字大的數(shù)字被一個(gè)一個(gè)地向后移動(dòng)，最后一個(gè)[0]被正確地放在適當(dāng)?shù)奈恢谩?/p>

1)存儲(chǔ)在a [1] ~ a [n]中的數(shù)據(jù)，i2

②一[0]一[i]，紀(jì)

3)如果a[j-1]gta[0]，那么a[j]a[j-1]，然后j-轉(zhuǎn)到3)

4)a[j]a[0]

5)i若iltn，則ji，轉(zhuǎn)3)，否則結(jié)束。

排序后，a[1]~a[n]都是升序序列。