2.1 线性表的逻辑结构
2.1.1 线性表的定义：
线性表：简称表，是n个具有相同类型的数据元素的有限序列。
长度：线性表中数据元素的个数。
空表：长度为0；非空表记作：L=（a1,a2,….,an)
任意一对相邻的数据元素ai-1和ai(1<i<=n)之间存在序偶 关系<ai-1,ai>,ai-1称为ai的前驱，ai称为ai-1的后继。
2.1.2 线性表的抽象数据类型定义
线性表表示一个相当灵活的数据结构
,
对线性表的数据元素不仅可以进行存取访问
,
还可以进行插入和删除 作
.
其抽象数据类型定义
:
ADT List
Date
Operation
InitList
功能：线性表初始化
DestroyList
功能：销毁线性表
Length
功能：求线性表的长度
Get
功能：按位查找，在线性表中查找序号为
i
的数据元素
Locate
功能：按值查找，在线性表中查找值等于
x
的元素
Insert
功能：插入操作，在线性表的第
i
个位置插入一个新元素
x
Delete
功能：删除操作，删除线性表中的第
i
个元素
Empty
功能：判空操作，判断线性表是否为空表
PrintList
功能：遍历操作，按序号依次输出线性表中的元素
endADT
2.2
线性表的顺序存储结构
—-
顺序表
顺序表：线性表的顺序存储结构。它是用一段地址连续的存储单元依次存储线性表的数据元素。
C++
中数组下标是从
0
开始的，而线性表中元素的序号是从
1
开始的，即线性表中第
i
个元素存储在数组中下标为
i-1
的位置。顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址，计算任意一个元素的存储地址时间是相等的（随机存取）。
2.2.2
顺序表的实现
const int MaxSize=100;
template<class T>
class SeqList
{
public:
SeqList(){length=0;}
SeqList(T int a[],int n);
~SeqList(){}
Int Length(){return length;}
T Get(int i);
void Insert(int i,T x);
T Delete(int i);
int Locate(T x);
void PrintList();
private:
T data[MaxSize];
int length;
};
1、
构造函数
无参构造函数
SeqList()
创建一个空的顺序表，只简单地将顺序表的长度
length
初始化
0
有参构造函数SeqList(T a[],int n)需要将给定的数组元素作为线性表的数据元素顺序表中，并将传入的元素个数作为顺序表的长度。
顺序表有参构造函数
SeqList
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;
}
2、
求线性表的长度
只需要返回变量
length
的值
3、
查找操作
（
1
）、按位查找：算法的时间复杂度为
O（1）
顺序表按位查找算法
Get
template<class T>
T SeqList<T>::Get(int i)
{
if(i<1 && i>length) throw”
查找位置非法
”;
else return data[i-1];
}
(2)
、按值查找：如果成功，返回元素序号（不是下标）；不成功返回查找失败的标志“
0
”；平均时间性能是
O
（
n
）。
顺序表按值查找算法Ｌ
ocate
template<class T>
int SeqList<T>::Locate(T x)
{
for (int i=0;i<length;i++)
if(data[i]==x)return i+1;
return 0;
}
4、插入操作
顺序表插入算法
Insert
template<class T>
void SeqList<T>::Insert(int i,T x)
{
if (length>=MaxSize)throw”
上溢
“;
if (i<1||i>length+1)throw”
位置
“;
for (j=length;j>=i;j–)
data[j]=data[j-1];
data[i-1]=x;
length++;
}
注意
:
元素移动的方向必须从第
i+1
个元素开始移动，直至将最后一个元素前移为止，并且在移动元素之前要取出被删除元素。若表空则下溢异常，若删除位置不合理则异常。
顺序表删除算法
Delete
Template<class T>
T SeqList<T>::Delete (int i)
{
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;
}
算法的平均时间复杂度为
O
（
n
）。
6
、遍历操作
顺序表遍历算法PrintList
Template<class T>
void SeqList<T>::PrintList()
{
for(i=0;i<length;i++)
cout<<data[i];
}
2.3
线性表的链接存储结构及实现
2.3.1
单链表
1
、单链表的存储方法
单链表：用一组任意的存储单元存放线性表的元素，可连续可零散分布。
指针：为了能正确表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储其后继元素所在的地址信息，此地址信息为指针。
C++
的模板机制
Template<class T>
class LinkList
{
public:
LinkList();
LinkList(T a[],int n);
~LinkList();
int Locate(T x);
T Get(int i);
Int Length();
void Insert(int i,T x);
T Delete(int i);
void PrintList();
private:
Node<T> *first;
};
在单链表中，结点
p
由两个域组成：存放数据元素的部分和存放后继结点地址的指针部分，分别用
p->
data
和
p->
next
来标识，且它们各有自己的值：
p->
data
的值是一个数据元素，
p->
next
的值是一个指针，单链表的操作必须从头指针开始进行，通常设置一个工作指针
p
，当指针
p
指向某结点时执行相应的处理，然后将指针
p
修改为指向其后继结点，直到
p
为
NULL
为止。
1、
遍历操作
单链表遍历算法
PrintList
template<class T>
void LinkList<T>::PrintList()
{
p=first->next;
while(p!=NULL)
{
cout<<p->data;
p=p->next;
}
}
时间复杂度为
O
（
n
）
注意：工作指针
p
后移不能写作
p++,
因为单链表的存储单元可能不连续。
2
、求线性表的长度
求线性表长度的算法
template<class T>
void LinkList<T>::Length()
{
p=first->next;
count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return count;
}
时间复杂度为
O
（
n
）
2、
查找操作
（
1
）、按位查找
单链表按位查找算法
Get
template<class T>
T LinkList<T>::Get(int i)
{
p=first->next;
count=1;
while(p!=NULL&&count<i)
{
p=p->next;
count++;
}
if(p==NULL)throw”
位置
”;
else return p->data;
}
平均时间性能为
O(n)
（
2
）、按值查找
单链表按值查找算法
Locate
template<class T>
int LinkList<T>::Locate(T x)
{
Node<T>*p=first->next;
int count=1;
while(p!=NULL)
{
if(p->data==x)
return count;
p=p->next;
count++;
}
return 0;
}
4
、插入操作
单链表插入算法
Insert
template<class T>
void LinkList<T>::Insert(int i,T x)
{
p=first
；
count=0;
while(p!=NULL && count<i-1)
{
p=p->next;
count++;
}
if(p==NULL)throw”
位置
“;
else
{
s=new Node<T>;
s->data=x;
s->next=p->next;
p->next=s;
}
}
时间复杂度为
O(n)
5
、构造函数
无参构造函数
LinkList
template<class T>
LinkList<T>::LinkList()
{
first=new Node;
first->next=NULL;
}
有参构造函数
LinkList
（
T a[],int n)
有两种构造方法：头插法和尾插法
（
1
）、头插法
头插法建立单链表
LinkList
template<class T>
LinkList<T>::LinkList(T a[],int n ）
{
first=new Node;
first->next=NULL ；
for(int i=0;i<n;i++)
{
s=new Node;
s->data=a[i];
s->next=first->next;
first->next=s;
}
}
(2)
、尾插法
尾插法建立单链表
LinkList
template<class T>
LinkList<T>::LinkList(T a[],int n)
{
first=new Node;
r=first;
for(int i=0;i<n;i++)
{
s=new Node;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
6、
删除操作
单链表删除算法
Delete
template<class T>
T LinkList<T>::Delete(int i)
{
p=first;
count=0;
while(p!=NULL && count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL)
throw”
位置
“;
else
{
q=p->next;
x=q->data;
p->next=q->next;
delete q;
return x;
}
}
时间复杂度为
O
（
n
）
7
、析构函数
单链表析构函数算法
~LinkList
template<class T>
LinkList<T>::~LinkList()
{
while(first!=NULL)
{
q=first;
first=first->next;
delete q;
}
}
2.3.2
循环链表
单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环列表，简称循环列表。
2.3.3
双链表
双链表：在单链表的每个结点中在设置一个指向其前驱结点的指针域。
Data
为数据域，存放数据元素
Prior
为前驱指针域，存放该结点的前驱结点的地址
Next
为后继指针域，存放该结点的后继结点的地址
采用
C++
模板机制
template<class T>
struct DulNode
{
T data;
DulNode<T>*prior,*next;
};
设指针p指向循环双链表中某一结点，则循环双链表具有以下对称性：
（
p->prior
）
->next=p=(p->next)->prior
1、
插入
在结点
p
的后面插入一个新结点
s
，需要修改
4
个指针
1
）
s->prior=p;
2) s->next=p->next;
3） p->next->prior=s;
4)p->next=s;
注意指针修改的相对顺序。
2、
删除
设指针
P
指向待删除结点，其操作
1）
（
p->prior
）
->next=p->next;
2）
(p->next)->prior=p->prior;
2.4顺序表和链表的比较
2.4.1 时间性能的比较
作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和数据元素在线性表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，则宜采用链表作为存储结构。
2.4.2 空间性能比较
作为一般规律，当线性表中的元素个数变化较大或者未知时，最好使用链表实现，如果事先知道线性表的大致长度，使用顺序表的空间效率会更高。
2.5 线性表的其他存储方法
静态链表：用数组来表示单链表，用数组元素的小标来模拟单链表的指针。
其结构定义：
const int MaxSize=100;
template<class T>
struct sNode
{
T data;
int next;
}SList[MaxSize];
间接寻址：将数组和指针结合起来的一种方法，它将数组中存储数据元素的单元改为存储指向该元素的指针。