数据结构--第二章 线性表

注：根据严蔚敏等人的数据结构（C语言版）（第二版）记录，用于自己的复习记录。

线性结构特点：除第一个元素无直接前驱，最后一个元素无直接后继外，其他每个数据元素都有一个前驱和一个后继。

线性表的定义和特点

线性表是最基本且最常用的一种线性结构。

线性表：由()个数据特性相同的元素构成的有限序列。表中元素的个数为线性表的长度，时称为空表。

非空的线性表或者线性结构的特点：

（1）存在唯一一个被称为”第一个“的数据元素。

（2）存在唯一一个被成为”最后一个“的数据元素。

（3）除第一个外，结构中每个数据元素有且仅有一个前驱。

（4）除最后一个外，结构中每个数据元素有且仅有一个后继。

线性表的顺序存储

线性表的顺序存储指的是利用一组地址连续的存储单元存储线性表中的元素。这种存储结构的线性表称为顺序表。线性表的顺序存储结构是一种随机存取的存储结构。

假设每个元素占有L个存储单元，则有：

顺序表的存储结构

#define MAXSIZE 100  //顺序表可能达到的长度
typedef struct{
ElemType *elem;  //存储空间的基地址
int length; //当前长度
}SqList; //顺序表的结构类型为SqList

1.构造空表

1. 为顺序表L动态分配一个预定义大小的数组空间，使得elem指向这个地址空间的基地址。
2. 将当前链表长度设置为0.

Status InitList(SqList &L){
L.elem = new ElenType[MAXSIZE]; //为顺序表分配一块MAXSIZE的数组空间
if(!L.elem) exit(OVERFLOW); //分配失败
L.length = 0；
return 0;
}

2.取顺序表中第i个元素的值

1. 判断i是否合理，若不合理，返回REEOR；
2. 如果i合理，将L.elem[i-1]赋值给e，返回e。

Status GetElem(Sqlist L, int i, ElemType &e){
if(i<1|i>L.length) return ERROE;
e = L.elem[i-1];
return OK;
}

3.查找顺序表中值为e的元素

1. 从第一个元素开始，依次和e比较，若找到则查找成功，返回序号i+1；
2. 若遍历完依旧没有，则返回0；

int LocateElem(SqList L, ElemType e){
for(i=1,i<=L.length,i++)
if(L.elem == e) return i+1
return 0;
}

4.在第i个位置之前插入一个元素

1. 判断i是否合法，若不合法返回ERROE。
2. 判断顺序表的存储空间是否已满，若满则返回ERROE。
3. 将第n个元素到第i个元素均往后移一个，空出第i个位置。
4. 将e放入第i个位置。

Status ListInsert(SqList &L, int i, ElenType e){
if(i<1|i>L.length+1) return ERROR;
if(L.length == MAXSIZE) return ERROR;
for(j=n; j>=i-1; j--)
L.elem[j+1] = L.elem[j];
L.elem[i-1] = e;
++L.length; //别忘记列表长度+1
return OK;
}

顺序表插入的平均复杂度为O（n）。

5.将表中第i个元素删除

1. 判断i是否合法，若不合法返回ERROR。
2. 将第i+1到第n个元素往前移动。
3. 表长减一。

Status ListDelete(SqList &L,int i){
if(i<1|i>L.length) return ERROR;
for(j=i+1; j<=n; j++)
L.elem[j-1] = L.elem[j];
--L.length;
return OK;
}

顺序表删除的平均复杂度为O（n）。

线性表的链式存储

线性表的链式存储是用任意一组存储单元存储线性表中的元素（可连续，可不连续）。

在存储过程中，除了存储表中元素本身，还要存储一个指向其直接后继的信息。这两部分组成存储的元素的存储映像，称之为结点。其包括两个域，一个是存储元素本身的域称为数据域，另一个是指向其后继信息的域称为指针域。

若链表中每个结点只含有一个指针域，则成为线性链表或者单链表。

头指针指示链表中第一个结点（即第一个数据的存储映像，也称首元结点）的存储位置。

一、单链表

单链表的存储结构

typedef struct LNode{
ElemType data; //结点中的数据域
struct LNode *next; //结点中的指针域
}LNode,*LinkList;  //LinkList为指向结构体Lnode的指针类型

在单链表第一个结点之前附设一个结点，称为头结点。

链表增加头结点的作用：

1. 便于首元结点的处理，使得第一个结点的处理和其他结点相同。
2. 便于空表和非空表的统一处理。增加头结点后，无论链表是否为空，头指针都是指向头结点的空指针。

1.1构造单链表

1. 生成新的结点作为头结点，用头指针L指向头结点。
2. 头结点的指针域置为空。

Status InitList(LinkList &L){
L = new LNode; //生成新结点作为头结点，用头指针L指向头结点
L->next = NULL;
return OK;
}

1.2取单链表中序号为i的元素值

1. 用指针p指向首元结点，用j做计数器初始值为1.
2. 从首元结点依次往下遍历，只要指向当前结点的p不是空的且没有到达序号i，就循环操作（1）p指向下一个结点 （2）j加一
3. 退出循环，如果p指向空或者j>i，说明指定的序号i不合法（i>n或i<0）取值失败返回ERROR；否则成功，此时j=i,p所指的结点就是要找的第i个结点，用保存其数据域。

Status GetElem(LinkList L,int i, ElemType &e){
p = L->next;
j = 1;
while(p && j<i){
p = p->next;
++j;}
if(!p || j>i) return ERROR;
e = P->data;
return OK;
}

单链表取值的平均复杂度是O（n）。

1.3单链表的按值查找

1. 指针p指向首元结点
2. 从首元结点开始依次遍历，只要当前结点不为空且p所指结点的数据域不为e，则循环p指向下一个结点。
3. 返回p，若查找成功，则此时p刚好为结点的地址；否则，返回NULL。

Status *LocateElem(LinkList L,ElemType e){
p = L->next;
while(p && p->data != e){
p = p->next}
return p;
}

其平均复杂度也为O（n）。

1.4在第i个位置插入新结点，数值为e

1. 查找结点，并将指针p指向该结点。
2. 生成一个新结点*s。
3. 将新结点*s的数据域指向e。
4. 将新结点*s的指针域指向。
5. 将结点*p的指针域指向新节点*s。

Status ListInsert(LinkList &L, int i, ElemType e){
p=L;j=0;
while(p && j < i-1){
p = p->next;
++j;
}
if(!p || j>i-1) return ERROR; //j>n+1或者i<1
s = new LNode;
s -> data = e;
s -> next = p ->next;
p -> next = s;
return OK;
}

1.5删除单链表的第i个结点

1. 查找第i-1个结点，并由p指针指向该结点。
2. 临时保存删掉的结点i在q中，以便释放。
3. 将结点*p的指针域指向的后继结点。
4. 释放结点的空间。

Status ListDelete(LinkList &L, int i){
p=L;j=0;
while(p->next && j<i-1){
p = p->next;
++j;}
if(!(p -> next) || j>i-1 ) return ERROE;
q = p->next;
p->next = q->next;
delete q;  //不要忘记释放掉
return OK;
}

1.6前插法创建单链表

1. 创建一个只有头结点的空链表。
2. 根据创建链表中元素的个数n，循环n次下面操作：（1）生成一个新结点*p；（2）输入元素赋值给新结点的数据域；（3）将新结点插入到头结点之后。

void CreateList_H(LinkList &L, int n){
L = new LNode;
L->next = NULL;
while(i=0;i<n;++i){
p = new LNode;
cin>>p->data;
p -> next = L -> next;
L -> next = p;
}
}

1.7后插法创建单链表

1. 创建一个只有头结点的空链表。
2. 尾指针r初始化，指向头结点。
3. 根据创建链表的元素个数n，循环n次以下操作：（1）创建一个新的结点q。（2）输入元素赋值给新结点的数据域。
4. 将新结点插入尾指针之后。
5. 将尾指针指向新的结点*p。

Status CreateList_R(LinkList &L, int n){
L = new LNode;
L->next = NULL;
r = L;
for(i = 0;i<n;++i){
p = new LNode;
cin>>p->data;
p -> next = NULL;
r -> next = p;
r = p;
}
}

二、循环链表

循环链表特点：表中最后一个元素的指针域指向头指针。

判别当前指针是否指向表尾指针的终止条件为p->next!=L或则p!=L。

在某些情况下，在循环链表中仅设尾指针不设头指针会使得一些操作简化。

三、双向链表

双向链表的结点中有两个指针域，一个指向结点的前驱，一个指向结点的后继。

双向链表的存储结构

typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLnode *next;
}DuLNode,*DuLinkList;

3.1双向链表的插入

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
在第i个元素之前插入
if(!(p = GetElem_DuL(L,i)))  // 在L中确定第i个元素的指针为p
return ERROR;  // p为NULL，返回ERROR
s = new DuLNode;
s -> data = e;
s -> prior = p -> prior;
p -> prior -> next = s;
s -> next = p;
p -> prior = s;
return OK;
}

3.2双向链表的删除

Status ListDelete_DuL(DuList &L, int i)
{删除第i个结点
if(!(p = GetElem_DuL(L,i)))
return ERROR;
p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
delete p;
return OK;
}

小结