學習內容來自數據結構詳解——線性表（C++實現）
線性表（List）:零個或多個數據元素的有限序列俊犯。
順序表（數組）：元素地址單元連續(xù)。
鏈表：結點地址不連續(xù)伤哺，由指針指向下個元素地址燕侠。
一、線性表的抽象數據類型
ADT 線性表(List)
Data
線性表的數據對象集合為{a1,a2,....,an},每個元素的類型均為DataType立莉。其中绢彤，除了第一個元素a1外，每一個元素有且只有一個直接前驅元素桃序，除最后一個元素an外杖虾，每一個元素有且只有一個直接后繼元素烂瘫。數據元素之間的關系是一對一的關系媒熊。
Operation
InitList(*L):初始化操作，建立一個空的線性表坟比。
ListEmpty(L):若線性表為空芦鳍，返回true，否則返回false葛账。
ClearList(*L):線性表清空柠衅。
GetElem(L,i,*e):將線性表L中第i個位置元素返回給e。
LocateElem(L,e):在線性表L中查找與給定值e相等的元素籍琳，如果查找成功,返回該元素在表中的序列號菲宴；否則，返回0表示失敗趋急。
ListInsert(*L,i,e):在線性表的第i個位置插入元素e喝峦。
ListDelete(*L,i,*e):刪除線性表L中的第i個元素，并用e返回其值
ListLength(L):返回線性表L的元素個數呜达。
PrintList(L):打印線性表
對于不同的應用谣蠢，線性表的基本操作是不同的，上述操作是最基本的。
對于實際問題中涉及的關于線性表的更復雜操作眉踱，完全可以用這些基本操作的組合來實現挤忙。
二、順序儲存結構
定義：用一段連續(xù)地址單元依次儲存
結構：
順序表模板類代碼：
//順序存儲
const int MaxSize = 100;
template <class DataType>
class SeqList
{
public:
SeqList() { length = 0; } //無參數構造
SeqList(DataType[], int n); //有參數構造
~SeqList() {}
int Length() { return length; }//返回線性表長度
DataType Get(int i);//按位查找
int Locate(DataType x);//按值查找
void Insert(int i, DataType x);//插入
DataType Delete(int i);//刪除
void PrintList();//遍歷
private:
DataType data[MaxSize]; //順序列表采用數組實現
int length;
};
順序表描述需要三個屬性：
- 儲存空間的起始位置：數組
data - 線性表最大儲存容量：數組長度
MaxSize - 線性表當前長度：
length
有參數構造：
創(chuàng)建一個長度為n的順序表谈喳，需要將給定的數組元素作為線性表的數據元素傳入順序表中册烈，并將傳入的元素個數作為順序表的長度。
template <class DataType>
SeqList<DataType>::SeqList(DataType a[],int n)
{
if (n > MaxSize) throw"wrong parameter";
for (int i = 0; i < MaxSize; i++)
data[i] = a[i];
length = n;
}
按位查找
時間復雜度O(1).
template <class DataType>
DataType SeqList<DataType>::Get(int i)
{
if (i<1 && i>length) throw "wrong locate";
else
return data[i - 1];
}
按值查找
對順序表元素依次比較叁执，返回下標+1茄厘。
template<class DataType>
int SeqList<DataType>::Locate(DataType x)
{
for (int i = 0; i < length; i++)
if (data[i] == x) return i + 1;
return 0;
}
插入
- 注意移動方向，必須從最后一個元素開始移動谈宛。
-
表滿次哈，引發(fā)上溢異常；插入位置不合理吆录，引發(fā)位置異常窑滞。
template<class DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
if (length == MaxSize) throw "overSize";
if (i<1 || i>length + 1) throw "eror Location";
for (int j=length; j > i-1; j--)
{
data[j] = data[j-1];
}
data[i - 1] = x;
length++;
}
刪除
- 注意元素移動方向，移動元素前需取出被刪元素恢筝。
-
表為空哀卫，則發(fā)生下溢；位置不合理異常撬槽，引發(fā)位置
template<class DataType>
DataType SeqList<DataType>::Delete(int i)
{
if (i<1 || i>length + 1) throw "eror Location";
DataType x = data[i - 1];
for (int j = i; j < length; j++)
{
data[j-1] = data[j];
}
length--;
return x;
}
遍歷
template<class DataType>
void SeqList<DataType>::PrintList()
{
for (int i = 0; i < length; i++)
std::cout << data[i] << std::endl;
}
順序儲存的優(yōu)缺點
優(yōu)點：
- 隨機訪問特性此改，查找時間O(1),存儲密度高
- 無須為邏輯關系增加額外儲存空間
缺點： - 插入、刪除需移動大量數據元素
- 線性表長度變化大侄柔，難以確定儲存空間
- 造成儲存空間“碎片化”
三共啃、鏈式儲存
1.鏈式儲存定義
鏈表的定義是遞歸的，它或者為空null暂题，或者指向另一個節(jié)點node的引用移剪，這個節(jié)點含有下一個節(jié)點或鏈表的引用，線性鏈表的最后一個結點指針為“空”（通常用NULL或“^”符號表示）薪者。
2.鏈式儲存實現方式
儲存方法
//鏈表
template<class DataType>
struct Node //結構體模板
{
DataType data; //儲存數據
Node<DataType> *next; //儲存下一節(jié)點地址（傳遞自定義類型參數DataType）
};
結點由存放數據元素的數據域和存放后繼結點地址的指針域組成纵苛。
結構
單鏈表模板類代碼：
template<class DataType>
class LinkList
{
public:
LinkList();
LinkList(DataType [],int n);
~LinkList();
int Length();//返回線性表長度
DataType Get(int i);//按位查找
int Locate(DataType x);//按值查找
void Insert(int i, DataType x);//插入
DataType Delete(int i);//刪除
void PrintList();//遍歷
private:
Node<DataType> *first;
};
特點
- 一組任意儲存單元儲存線性表數據元素——未被占用的任意位置
- 鏈式儲存需存放數據、后繼元素存儲地址
無參數構造
生成只有頭結點的空鏈表
template<class DataType>
LinkList<DataType>::LinkList()
{
first = new Node<DataType>; //new頭指針指向的頭地址
first->next = NULL; //初始化頭指針
}
有參數構造單鏈表
-
頭插法構造
//頭插法：將新申請的結點插在頭結點后面
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
first = new Node<DataType>;
first->next = NULL;
for (int i = 0; i < n; i++)
{
Node<DataType> *s = new Node<DataType>;
s->data = a[i];
s->next = first->next;
first->next = s;
}
}
-
尾插法構造
//尾插法:將新申請的結點插在終端節(jié)點的后面
template<class DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{
first = new Node<DataType>;
Node<DataType> *r = first;
for (int i = 0; i < n; i++)
{
Node<DataType> *s = new Node<DataType>;
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL; //終端結點指針域置空
}
析構函數
單鏈表中結點通過new申請言津，需通過析構中的delete進行釋放攻人。
template<class DataType>
LinkList<DataType>::~LinkList()
{
while (first != NULL) //頭地址不為空，鏈表有值
{
Node<DataType> *q = first;
first = first->next;
delete q;
}
}
計算長度
將單鏈表掃描一遍,悬槽，時間復雜度為O(n)
//時間復雜度O(n)
template<class DataType>
int LinkList<DataType>::Length()
{
Node<DataType> *p = first->next;
int count = 0;
while (p != NULL)
{
p = p->next;
count++;
}
return count;
}
按位查找
單鏈表中即使知道節(jié)點位置也不能直接訪問怀吻，需要從頭指針開始逐個節(jié)點向下搜索，平均時間性能為O(n)陷谱，單鏈表是順序存取結構
DataType LinkList<DataType>::Get(int i)
{
Node<DataType> *p = first->next;
int count = 1;
while (p != NULL && count < i)
{
p = p->next;
count++;
}
if (p == NULL) throw "no data"; //未找到
else return p->data;
}
按值查找
單鏈表中按值查找與順序表中的實現方法類似烙博，對鏈表中的元素依次進行比較瑟蜈，平均時間性能為O(n).
template<class DataType>
int LinkList<DataType>::Locate(DataType x)
{
Node<DataType> *p = first->next;
int count = 1;
while (p != NULL)
{
if (p->data == x)
return count;
p = p->next;//移動查詢指針
count++;
}
return 0;//no found
}
插入
單鏈表在插入過程中需要注意分析在表頭、表中間渣窜、表尾的三種情況铺根，由于單鏈表帶頭結點，這三種情況的操作語句一致乔宿，不用特殊處理位迂，時間復雜度為O(n).
template<class DataType>
void LinkList<DataType>::Insert(int i, DataType x)
{
Node<DataType> *p = first;
int count = 0;
while (p != NULL && count < i - 1){
p = p->next;
count++;
}
if (p == NULL) throw"Location";
else {
Node<DataType> *s = new Node<DataType>;
s->data = x;
s->next = p->next;
p->next = s;
}
}
刪除
刪除操作時需要注意表尾的特殊情況，此時雖然被刪結點不存在详瑞，但其前驅結點卻存在掂林。因此僅當被刪結點的前驅結點存在且不是終端節(jié)點時，才能確定被刪節(jié)點存在坝橡，時間復雜度為O(n)
template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
Node<DataType> *p = first;
int count = 0;
while (p != NULL && count < i -1 )
{
p = p->next;
count++;
}
if (p == NULL || p->next == NULL) throw "Location"; //注意不能是終端結點
else
{
Node<DataType> *q = p->next;
p->next = q->next;
return q->data;
}
}
遍歷
template<class DataType>
void LinkList<DataType>::PrintList()
{
Node<DataType> *p = first->next;
while (p != NULL )
{
std::cout << p->data << std::endl;
p = p->next;
}
}
鏈式儲存優(yōu)缺點
優(yōu)點：
- 插入泻帮、刪除無需移動其他元素，只用改變指針
- 鏈表各結點內存空間無需連續(xù)计寇，利用率高
缺點：
- 查找需遍歷
四锣杂、其他類型鏈表
循環(huán)鏈表
- 特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)番宁。（通常為了使空表和非空表的處理一致元莫，通常也附加一個頭結點）
-
通常以判斷指針是否等于某一指定指針來判定是否掃描了整個循環(huán)鏈表。
雙鏈表
循環(huán)鏈表雖然可以從任意結點出發(fā)掃描其他結點蝶押，但是如果要查找其前驅結點踱蠢，則需遍歷整個循環(huán)鏈表。為了快速確定任意結點的前驅結點棋电，可以再每個節(jié)點中再設置一個指向前驅結點的指針域茎截，這樣就形成了雙鏈表。
儲存方法：
template<class DataType>
struct Node
{
DataType data;
Node<DataType> *prior,*next;
};
結點p的地址既存儲在其前驅結點的后繼指針域內离陶，又存儲在它后繼結點的前驅指針域中
需要注意：
- 循環(huán)雙鏈表中求表長稼虎、按位查找衅檀、按值查找招刨、遍歷等操作的實現與單鏈表基本相同。
- 插入操作需要修改4個指針哀军，并且要注意修改的相對順序沉眶。
靜態(tài)鏈表
靜態(tài)鏈表是用數組來表示單鏈表，用數組元素的下標來模擬單鏈表的指針.
靜態(tài)鏈表儲存儲存：
const int MaxSize = 100;
template<class DataType>
struct Node{
DataType data;
int next;
}SList[MaxSize];
靜態(tài)鏈表雖然是用數組來存儲線性表的元素杉适，但在插入和刪除操作時谎倔，只需要修改游標，不需要移動表中的元素猿推，從而改進了在順序表中插入和刪除操作需要移動大量元素的缺點片习，但是它并沒有解決連續(xù)存儲分配帶來的表長難以確定的問題
