一 順序表的定義： 即把線性表的結點按邏輯次序依次存放在一組位址連續的存儲單元裡的方法。
二 順序表類型定義：
#define listsize 100 //定義表空間大小
typedef int datatype;//假設為int類型
typedef struct {
datatype data[listsize];
int length;//順序表的大小
}seqlist
注意：
① 用向量這種順序存儲的數組類型存儲線性表的元素外，順序表還應該用一個變量來表示線性表的長度屬性，是以用結構類型來定義順序表類型。
② 存放線性表結點的向量空間的大小listsize應仔細選值，使其既能滿足表結點的數目動态增加的需求，又不緻于預先定義過大而浪費存儲空間。
③ 由于c語言中向量的下标從0開始，是以若l是seqlist類型的順序表，則線性表的開始結點a1和終端結點an分别存儲在l．data[0]和l．data[l．length-1]中。
④ 若l是seqlist類型的指針變量，則a1和an分别存儲在l-＞data[0]和l-＞data[l-＞length-1]中。
三 順序表的運算
①表的初始化
<pre name="code" class="cpp">void initlist(seqlist *l)
{
l->length = 0;//順序表的初始化即就是講表的長度置為0
}
②求表長
void listlength(seqlist *l)
return l->length ;//隻需要傳回length即可
③取表中第i個結點
datatype getnode(seqlist *l,int i)
{//取表中第i個結點傳回l->data[i-1]即可
if(i<1||l->length-1)
error("position error");
else
return l->data[i];
④查找x是否在表中
int findnode(seqlist *l,int x)
int i,p;
for(i=0;i<l->length;i++)
{
p = l->data[i];//取表中第一個節點
if(p!=x)
{
i++;
}
else break;
if(i==length-1)
printf("sorry not fonud!");
return 0;
}
}
printf("the position is %d",i+1);
return 1
⑤将資料x插入到第i個位置上
void insertlist(seqlist *l,datatype x,int i)
int j;
if(i<1||i>l->length+1)
if(l->length>=listsize)
error("overflow")//表空間溢出
for(j=l->length-1;j>=i-1;i--)
l->data[j+1] = l->data[j]; //全體後移
l->data[i-1] = x; //插入資料
l->length++; //表長增加
四 算法分析
① 問題的規模
表的長度l-＞length（設值為n）是問題的規模。
② 移動結點的次數由表長n和插入位置i決定
算法的時間主要花費在for循環中的結點後移語句上。該語句的執行次數是n-i+1。
當i=n+1：移動結點次數為0，即算法在最好時間複雜度是0(1)
當i=1：移動結點次數為n，即算法在最壞情況下時間複雜度是0(n)
③ 移動結點的平均次數eis(n)
其中：
在表中第i個位置插入一個結點的移動次數為n-i+1
pi表示在表中第i個位置上插入一個結點的機率。不失一般性，假設在表中任何合法位置（1≤i≤n+1）上的插入結點的機會是均等的，則
p1=p2=…=pn+1=1/(n+1)
是以，在等機率插入的情況下，
即在順序表上進行插入運算，平均要移動一半結點。
轉載：http://blog.csdn.net/xsf50717/article/details/39895835