線性表 - 順序存儲結構 - 順序表上的基本運算

　　順序表上實現的基本運算

　　表的初始化

　　void InitList(SeqList *L)

　　{\\順序表的初始化即將表的長度置為

　　L>length=;

　　}

　　求表長

　　int ListLength(SeqList *L)

　　{ \\求表長只需返回L>length

　　return L>length;

　　}

　　取表中第i個結點

　　DataType GetNode(Li)

　　{\\取表中第i個結點只需返回和L>data[i]即可

　　if (i<||i> L>length)

　　Error(position error);

　　return L>data[i];

　　}

　　查找值為x的結點

　　【參見參考書】

　　 插入

　　() 插入運算的邏輯描述

　　線性表的插入運算是指在表的第i(≤i≤n+)個位置上插入一個新結點x使長度為n的線性表

　　(a …a i a i …a n )

　　變成長度為n+的線性表

　　(a …a i x a i …a n )

　　注意

　　① 由於向量空間大小在聲明時確定當L>length≥ListSize時表空間已滿不可再做插入操作

　　② 當插入位置i的值為i>n或i<時為非法位置不可做正常插入操作

　　() 順序表插入操作過程

　　在順序表中結點的物理順序必須和結點的邏輯順序保持一致因此必須將表中位置為n n…i上的結點依次後移到位置n+

　　n…i+上空出第i個位置然後在該位置上插入新結點x僅當插入位置i=n+時才無須移動結點直接將x插入表的末尾

　　具體過程見【 動畫演示 】

　　()具體算法描述

　　void InsertList(SeqList *LDataType xint i)

　　{//將新結點 x插入L所指的順序表的第i個結點a i 的位置上

　　int j;

　　if (i<||i>L>length+)

　　Error(position error);//非法位置退出運行

　　if (L>length>=ListSize)

　　Error(overflow); //表空間溢出退出運行

　　for(j=L>length;j>=i;j)

　　L>data[j+]=L>data[j];//結點後移

　　L>data[i]=x; //插入x

　　L>Length++; //表長加

　　}

　　()算法分析

　　① 問題的規模

　　表的長度L>length(設值為n)是問題的規模

　　② 移動結點的次數由表長n和插入位置i決定

　　算法的時間主要花費在for循環中的結點後移語句上該語句的執行次數是ni+

　　當i=n+移動結點次數為即算法在最好時間復雜度是()

　　當i=移動結點次數為n即算法在最壞情況下時間復雜度是(n)

　　③ 移動結點的平均次數E is (n)

　　

　　其中

　　在表中第i個位置插入一個結點的移動次數為ni+

　　p i 表示在表中第i個位置上插入一個結點的概率不失一般性假設在表中任何合法位置(≤i≤n+)上的插入結點的機會是均等的則

　　p =p =…=p n+ =/(n+)

　　因此在等概率插入的情況下

　　

　　即在順序表上進行插入運算平均要移動一半結點

　　 刪除

　　()刪除運算的邏輯描述

　　線性表的刪除運算是指將表的第i(≤i≤n)個結點刪去使長度為n的線性表

　　(a …a i a i a i+ …a n )

　　變成長度為n的線性表

　　(a …a i a i+ …a n )

　　注意

　　當要刪除元素的位置i不在表長范圍(即i<或i>L>length)時為非法位置不能做正常的刪除操作

　　()順序表刪除操作過程

　　在順序表上實現刪除運算必須移動結點才能反映出結點間的邏輯關系的變化若i=n則只要簡單地刪除終端結點無須移動結點;若

　　≤i≤n則必須將表中位置i+i+…n的結點依次前移到位置ii+…n上以填補刪除操作造成的空缺其刪除過程【 參見

　　動畫演示 】

　　()具體算法描述

　　void DeleteList(SeqList *Lint i)

　　{//從L所指的順序表中刪除第i個結點a i

　　int j;

　　if(i<||i>L>length)

　　Error(position error); //非法位置

　　for(j=i;j<=L>length;j++)

　　L>data[j]=L>data[j]; //結點前移

　　L>length; //表長減小

　　}

　　()算法分析

　　①結點的移動次數由表長n和位置i決定

　　i=n時結點的移動次數為即為()

　　i=時結點的移動次數為n算法時間復雜度分別是(n)

　　②移動結點的平均次數E DE (n)

　　

　　其中

　　刪除表中第i個位置結點的移動次數為ni

　　p i 表示刪除表中第i個位置上結點的概率不失一般性假設在表中任何合法位置(≤i≤n)上的刪除結點的機會是均等的則

　　p =p =…=p n =/n

　　因此在等概率插入的情況下

　　順序表上做刪除運算平均要移動表中約一半的結點平均時間復雜度也是(n)

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