数据结构总结（二）链表

线性表：

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() 返回引用

未完>>>>