2.2.1線性表的順序表示和實現------順序映像

【順序存儲】在【查找時】的時間復雜度為【O(1)】，因為它的地址是連續的，只要知道首元素的地址，根據下標可以很快找到指定位置的元素
【插入和刪除】操作由于可能要在插入前或刪除后對元素進行移動，所以順序存儲的時間復雜度為【O(n)】。

1）初始化操作
思想：構造一個空表
設置表起始位置、表長及可用空間

#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef struct
{
ElemType *elem;   //定義個地址變量，使其后面能指向線性表占用的數組空間
int length;  // 線性表的長度
int listsize;  // 當前分配的存儲容量
}SqList;//初始化操作
Status InitList_Sq(SqList &L)  //初始化
{ //構造一個空表
L.elem=(ElemType)malloc(LIST_INIT_SIZE*size of(ElemType));
if(!L.elem)  exit(OVERFLOW);  //存儲分配失敗
L.length=0;   //空表長度為0
L.listsize=LIST_INIT_SIZE;  //初始存儲容量
return OK;}

2.2.3順序表的插入

2）順序插入操作

目的：在線性表L第i個元素前插入一個元素e

【基本思想
1）判斷i是否在允許范圍
2）存儲空間是否已滿
3）將第i個元素和后面的所有元素向后移動
4）新元素寫在空出的第i個位置
5）線性表長度加1

【注意】
長度為n的順序表第i個位置插入移動n-i+1個元素

Status ListInsert_Sq(SqList&L,int i,ElemType e){if(i<1||i>1.lenth+1)
return ERROR;   //插入位置不合法if(L.length>=L.listsize)
{}     //判斷空間足夠q=&(L.elem[i-1]);   //q指向插入位置for(p=&(L.elem[L.elem-1]);p>-q;--q)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}

2.2.4順序表的刪除和插入

【基本思路
1）判斷i是否在允許范圍
2）將線性表的第i個元素給e
3）將第i個元素和后面的所有元素向前移動一個位置
4）線性表長度減1

Status ListDelete_Sq(SqList&L,int i,ElemType e){//刪除第i個元素并用e返回值if(i<1||i>1.lenth+1)
return ERROR;   //刪除位置不合法p=&(L.elem[i-1]);   //q指向插入位置
e=*p;
q=L.elem+L.length-1; //表尾元素位置
for(++p;p<=q;++p)
*(p-1)=*p;    //p-1指向p--L.length;
return OK;
}

【圖】：平均移動次數

【查找操作】11:42

int LocateElem_Sq(SqList,ElseType e)
{
//查詢第一個 滿足條件的元素，若存在，返回位序，否則返回0；
int i;
i=1;
while (i<=L.length&&L.elem[i-1]!=e)
++i;
if(i<=L.length)
return i;
else return 0;
}// locateElem_Sqi<=L.length&&L.elem[i-1]!=e
i>L.length

【順序結構優缺點14:15
【優點：
邏輯相鄰，物理相鄰
可隨機存取一元素
存儲空間使用緊湊
【缺點：
插入，刪除需要移動大量元素
預先分配空間需按最大空間分配，利用不充分表難以擴充

【】線性表的合并問題
【圖：例1】
基本思路：
1）初始化Lc為空表
2）分別從La和Lb取得當前元素ai和bi
3)若ai<bj，則將ai插入到Lc中，否則
bj插入到Lc中

代碼：

Viod MergeList(SqList La,SqList lb,SqList &Lc)
{
Pa=La,elem;
Pb=Lb.elem;
Lc.listsize=Lc.length=La,elem+Lb.elem;
Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem)
exit(overflow);
Pa_last=La.elem+La.length-1;
Pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last)
{
if(*pa<=*pb)
*pc++=*pa++;
else
*pa++=*pb++;
}
while(pa<=pa_last)
*pa++=*pa++;
while (pb<=pb_last)
*pc++=*pb++;
}