1.定義:
線性表表示0個或者多個數據元素的有限序列
線性表的特性有:
除第一個元素外,每一個元素均有一個直接前驅
出最後一個元素外,每一個元素均有一個直接後繼
2.線性表抽象數據類型
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中的偽代碼如下所示：
[cpp]
//實現線性表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);
}
}
}
//實現線性表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 數據結構
[cpp]
//線性表的順序存儲結構
#define MAXSIZE 20;//存儲空間初始分配量為20
typedef int ElemType;//數據類型為int
type struct
{
ElemType data[MAXSIZE];//數組存儲數據元素
intlength;//線性表長度
};
//線性表的順序存儲結構
#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 獲取元素操作
[cpp]
//////////////////////////////////////////////////////////////////////////
//獲取順序鏈表中第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;
}
//////////////////////////////////////////////////////////////////////////
//獲取順序鏈表中第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;
}
4.2插入操作
插入操作算法的思路是：
1.如果插入位置不合理，拋出異常.
2.如果線性表長度大於等於數組長度，則拋出異常或者增加數組長度
3.從最後一個元素開始像前便利到第i個位置，分別將它們像後移動一個位置
4.第i個元素位置插入e
5.表長度加1
[cpp]
//在線性表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 ++;
}
//在線性表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 ++;
}
