資料結構總結（二）連結清單

線性表：

1、是最基本的、最簡單的資料結構，元素之間僅有單一的前驅後繼關系。

2、一般有兩種存儲方式：鍊式存儲和順序存儲

**定義：線性表是n(n>=0)個資料元素的有限序列，線性表中的資料元素的個數稱為線性表的長度，長度等于0的稱為空表，一個非空表通常記為 L=(a1,a2,……an）,ai為連結清單的第i個元素，任意一對相鄰的資料元素存在序偶關系，或者稱為前後繼關系。**線性表中的資料元素具有抽象的資料類型。

一、連結清單用途

1、可以任意處删除 ，增加等功能。

二、鍊式存儲的實作。

1、定義：線性的順序存儲稱為順序表，實作通過一段位址的連續依次存儲線性表中的元素。是以線性表需要提前确定好需要的空間的大小。

2、線性表實作：

1）确定數組大小，構造空表（len=0）

2）插入将插入的位置之後的元素全部後移一位，從後往前執行。

3）删除一個元素，将删除位置之後的元素全部前移一位，從前往後執行。

4）按位查找，直接利用下标獲得（複雜度 O(1) )。

需要注意的是表目前資料量，防止非法删除（下溢）,以及插入記憶體不足，上溢。

#define  Maxsize 100
template <class T>
class SeqList{ 
　private: 
　　T data[MaxSize]; // 存放資料元素的數組 
　　int length; // 線性表的長度 
　public: 
　　SeqList ( ) ;// 無參構造函數   
　　SeqList ( T a[ ], int n ) ; // 有參構造函數 
　　~SeqList( ) { } // 析構函數為空 
　　int Length ( ) {return length;} // 求線性表的長度 
　　T Get ( int i ); // 按位查找，取線性表的第 i 個元素 
　　int Locate ( T x ) ; // 按值查找，求線性表中值為 x 的元素序号 
　　void Insert ( int i, T x ) ; // 線上性表中第 i 個位置插入值為 x 的元素 
　　T Delete ( int i ) ; // 删除線性表的第 i 個元素 
　　void PrintList ( ) ; // 周遊線性表，按序号依次輸出各元素 
}; 
template <class T> 
SeqList<T>:: SeqList(T a[], int n)
{
  if (n>MaxSize) throw "參數非法";
  for (int i=0; i<n; i++)  
    data[i]=a[i];
  length=n;
}
emplate <class T>
T SeqList<T>::Delete(int i){ 
   int j; 
   T  x;
  if (length==0) throw "下溢";
  if (i<1 || i>length) throw "位置";
  x=data[i-1];
  for (j=i; j<length; j++)
    data[j-1]=data[j]; 
  length--;
  return x;
}
template <class T> 
T SeqList<T>::Get(int i)
{
    if (i<1 && i>length) throw "查找位置非法";
    else return data[i-1];
}
template <class T>
int SeqList<T>::Locate(T x){     
	  for (int i=0; i<length; i++)
	   if (data[i]==x) 
	     return i+1 ;  //下标為i的元素等于x，傳回其序号i+1
	  return 0;  //退出循環，說明查找失敗
}
　　
           

缺點：插入或删除運算不友善，由于順序表要求占用連續的存儲空間，存儲配置設定隻能預先進行靜态配置設定，是以當表長變化較大時，難以确定合适的存儲規模

三、連結存儲

預備知識：指針使用

五、STL中的連結清單使用

#include

#include

using namespace std;

bool cmp(int a,int b)

{

return a<b;

}

int main()

{

listl;

list::iterator it,itb,ite;

l.push_front(1);//頭部插入一個元素
l.push_front(4);
l.push_back(3);//尾部插入一個元素
l.push_back(2);
l.pop_back();//尾部插入一個元素
l.pop_front();//頭部插入一個元素
itb=l.begin();
ite=l.end();
for(it=itb;it!=ite;it++)
{
    l.insert(it,1000);//在此位置前插入一個元素
}
l.push_back(1000);
l.push_back(1000);
l.erase(l.begin());//删除第一個元素
l.remove(1000);//删除全部等于elem的元素,無傳回
itb=l.begin();
ite=l.end();
for(it=itb;it!=ite;it++)//疊代器輸出
{
    cout<<*it<<endl;
}
l.sort();
l.sort(cmp);
           

//其他操作

//swap()交換兩個list

//splice()合并兩個list

//remove_if()删除指定條件的元素

//sort()排序

//back()、front() 傳回引用

未完>>>>