順序表結點結構的定義？

順序表的定義

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

假設線性表的元素類型是ElemType，線性表的順序存儲類型描述為:

#定義MaxSize50

typedef結構

{

ElemType數據[MaxSize]

int長度

}SqList

一維數組可以靜態或動態分配。在靜態分配中，由于數組的大小和空間已經提前固定，一旦空間滿了，添加新的數據就會溢出，導致程序崩潰甚至其他未知的異常。

在動態分配中，存儲數組的空間是在程序執行過程中通過動態存儲分配語句來分配的。一旦存儲空間滿了，就會打開另一個更大的存儲區間來復制原來的元素，從而在不需要一次性分配大量空間的情況下，擴展存儲數組的空間。

#定義InitSize100

typedef結構

{

ElemType*dataPtr

int長度

int大小

}SqList

C語言的初始動態分配語句是:(elemtype*)malloc(Sizeof(elemtype)*initsize)。

C語言的初始化動態分配語句是:ElemType[InitSize]。

注意:動態存儲不是市場存儲，它也屬于順序存儲。物理結構沒有改變，它仍然與邏輯結構相鄰，但分配的空間不再由編譯器決定，而是在運行時分配。

2、序列表的特點

隨機存取:通過首地址和元素序號，可以在單位時間O(1)內找到指定的元素。

存儲密度高:存儲密度高是因為每個節點的存儲空間指的是數據元素的存儲，沒有額外的開銷。

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

3.序列表上基本操作的實現

只顯示了搜索、添加、刪除等三個操作，其余的在線性表中比較簡單，在比較復雜的鏈表中顯示。

3.1、插入操作

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

boollistinsert(SQLlistampL，inti，ElemTypee)

{

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

返回false

If(L.lengthgtMaxSize)//判斷是否超出存儲空間。

返回false

for(intjl.lengthjgtIj-)///將第I個元素及其后的元素向后移動一個位置。

[j][j-1]

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

L.length//序列表長度加1

返回true

}

最好的情況:在表的末尾插入(即in1)，原元素不移動，時間復雜度為O(1)。

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

平均情況:假設Pi(Pi1/(n-1))是在第I個位置插入一個節點的概率，在長度為n的序列表中插入一個節點時，移動節點的平均次數為n/2，時間復雜度為O(n)。

3.2.刪除操作

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

boollistdelete(SQLlistampL，inti，ElemTypeampe)

{

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

返回false

E[i-1]//將要刪除的數據保存到e。

For(intji-1jltL.lengthj)//將第I個元素和后續元素向后移動一個位置。

[j][j1]

長度length-//序列表長度加1

返回true

}

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

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

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

intlocateelem(SQLlistL，const

倒序插入法的詳細計算步驟？

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

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

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

為了避免重復比較是否出格，下面的插入排序使用"哨兵"。即在插入結束時，復制一份要插入的數據(a[0])的副本，一物兩用，既能保存數據，又能有效防止搜索越界，反復檢測是否越界。在每一輪中，比要插入的數字大的數字被一個一個地向后移動，最后一個[0]被正確地放在適當的位置。

1)存儲在a[1]~a[n]中的數據，i2

②一[0]一[i]，紀

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

4)a[j]a[0]

5)i若iltn，則ji，轉3)，否則結束。

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