ADT List

 Data

         /*線性表的數據對象集合為｛a1,a2,...,an｝,每個元素的類型均為DataType.其中，除第一個元素a1外，

  每一個元素有且隻有一個直接前驅元素，除了最後一個元素an外，每一個元素有且隻有一個直接後繼元素。

  數據元素直接是一對一的關係。*/

 Operation

         InitList(*L);//初始化操作，建立一個空的線性表

         ListEmpty(L);//若線性表為空，返回true,否則返回false

         ClearList(*L);//清空線性表

         GetElem(L,i,*e);//查找線性表中的第i個位置的元素值，並賦值給e

         LocateElem(L,e);//查找線性表L中與給定值e相等的元素，如果查找成功，則返回第一個相同的元素在L

                       //中的下標；否則，返回0表示失敗

         ListInsert(*L,i,e);//在線性表L的第i個位置插入元素e

         ListDelete(*L,i,*e);//刪除線性表L中第i個位置元素，並用e返回其值

         ListLength();//返回線性表L的長度

end ADT

實現線性表La和線性表Lb的並集操作，結果保存在La中的偽代碼如下所示：

//實現線性表La和線性表Lb的並集操作，結果保存在La中
	void UnionList(*La,Lb)
{
	//計算Lb長度
	int lblength = ListLength(Lb);
	//計算La長度
	int laLength = ListLength(La);
	int i ;
	//便利Lb中所有元素，判斷其是否在La中，若不在，則插入La中
	for (i=0;i<length;i++)
	{
		ElemType temp = GetElem(Lb,i,*e);
		if (LocateElem(La,temp)==0)
		{
			ListInsert(La,++laLength,temp);
		}
	}
}

3.順序存儲結構

3.1順序存儲結構的定義

線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。

3.2 數據結構

//線性表的順序存儲結構
#define MAXSIZE 20;//存儲空間初始分配量為20
typedef int ElemType;//數據類型為int
type struct
{
	ElemType data[MAXSIZE];//數組存儲數據元素
	intlength;//線性表長度
};

3.3 數組長度與線性表長度的區別

數組的長度是存放線性表的存儲空間的長度，存儲空間分配後這個量一般是不變的。

線性表的長度是線性表中數據元素的個數，隨著線性表的插入和刪除，這個量是變化的。

3.4 地址計算方法

由於順序存儲結構是按照順序存儲的，所以每個數據元素的地址都可以根據第一個元素的地址推算出來。

LOC(ai) = LOC(a1)+ (i-1)*c

4.順序存儲結構的操作

4.1 獲取元素操作

//////////////////////////////////////////////////////////////////////////
//獲取順序鏈表中第i個元素，並賦值給e
int GetElem(SqList L,int i, ElemType * e)
{
	//線性表長度等於0或者獲取元素位置錯誤返回0
	if (L.Length == 0 || i < 0 || i > L.Length)
	{
		return 0;
	}

	返回第i個元素
	*e = L.data[i-1];
	return 1;
}

3.從最後一個元素開始像前便利到第i個位置，分別將它們像後移動一個位置

//在線性表L的第i個位置插入元素e
int ListInsert(Sqlist *L, int i, ElemType e)
{
	//插入位置錯誤，返回0
	if (i < 0 || i > L.Length)
	{
		return 0;
	}

	//線性表的長度大於等於數組的最大長度，返回0
	if (L.Length >= MAXSIZE)
	{
		return 0;
	}

	int j = L.Length -1;
	//從第i個元素到最後一個元素，每個元素後移一位
	while (j >= i)
	 {
		 L.data[j+1] = L.data[j];
		 j--;
	 }

	//第i個元素的位置放入e
	L.data[i] = e;

	//線性表長度加1
	L.Length ++;

}

//線性表刪除操作
int ListDelete(SqList *L,int i,ElemType *e)
{
	//如果刪除的位置不對，則返回0
	if (i < 0 || i > L.Length -1)
	{
		return 0;
	}
	
	*e = L.data[i-1];

	for (j = i-1;i <L.Length-2;j++ )
	{
		L.data[j] = L.data[j+1];
	}

	L.Length --;
	return 1;

}

5.4 線性表存儲結構的優缺點

6.線性表的鏈式存儲結構

typedef struct Node
{
	ElemType data;
	struct Node *next;
} Node;
typedef struct Node *LinkList;

int GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;
	p = L->next;//p指向鏈表第一個節點
	while (p && j < i )
	{
		p = p->next;
		j++;
	}

	if(!p || count > i)
		return 0;
	 
	*e = p->data;
	return 1;
}