數據結構——線性表

線性表（Linear List）

定義：由同類型數據元素構成有序序列的線性結構

• 表中元素個數稱爲線性表的長度
• 線性表沒有元素時，稱爲空表
• 表起始位置稱爲表頭，表結束位置稱表尾

---

線性表的順序儲存實現

部分操作的實現

typedef struct LNode*List
 - struct LNode
 - {
 - ElementType Data[MAXSIZE]；
 - int Last；
 - }
 - struct LNode L;
 - List PtrL;
存取小標爲i的元素：L.Data[i]或PtrL->Data[i]
線性表的長度：L.Last+1或PrtL->last+1

初始化的實現

初始化一個空線性表L

 - List MakeEmpty（）

{
	List PtrL;
	Ptrl=(List)malloc(sizeof(struct LNode));
	PtrL->Last=-1;
	return PtrL;
}

查詢的實現

線上性表L中查詢X第一次出現位置

• 查詢成功的平均次數爲（n+1）/2
• 查詢成功的平均時間效能爲O（n）

 - int Find（ElementType X，List L）
{
	int i=0;
	while(i<=PtrL->Last&&PtrL->Data[i]!=X)i++;
	if(i>PtrL->Last) return -1;
	else return i;	
}

插入的實現

在爲序i前插入一個新元素X

• 先移動，後插入
• 平均移動次數爲n/2
• 平均時間效能爲O(n)

 - void Insert（ElementType X，int i，List L)
{
	int j;
	if(PtrL->Last==MAXSIZE-1)//表空間已滿，不能插入
	{
		printf("表滿");
		return;
	}
	if(i<1||i>PtrL->Last+2)
	{
		printf("位置不合法");
		return;
	}
	for(j=PtrL->Last;j>=i-1;j--)
		PtrL->Data[j+1}=PtrL->Data[j];//a1~an倒序想後移動
	PtrL->Data[i-1]=X;//新元素插入
	PtrL->Last++;//Last仍指向最後元素
	return;
}

刪除的實現

刪除指定位序i的元素

• 平均移動次數爲（n-1）/2
• 平均時間效能爲O（n）

 - void Delete（int i，List L）
{
	int j;
	if(i<1lli > PtrL->Last+1 )
	{
		printf("不存在第%d個元素",i)
		return ;
		}
	for ( j = i; j<= PtrL->Last; j++)
		PtrL->Dataj-1]=PtrL->Datai;//將a+1~an,順序向前移動
	PtrL->Last--;//Last仍指向最後元素*
	return;

}

 - int Length（List L）//返回線性表L的長度n
 - ElementType FindKth（int K，List L）//更具位序K，返回相應元素

---

線性表的順序儲存實現

---

內容來自mooc浙江大學數據結構課程由陳越老師，何欽銘老師任課