数据结构之线性表

线性表或者说线性结构的特点:
1. 存在唯一的一个首位元素.
2. 存在唯一的一个末位元素.
3. 除首位外,结构中的每个数据元素都有且只有一个前驱.
4. 除末位外,结构中的每个数据元素都有且只有一个后继.

## 顺序线性表

顺序线性表指的是使用一组地址连续的存储单元一次存储线性表的数据元素,也称作顺序存储结构或者顺序顺序映像.

其特点是:

> 逻辑上相邻的数据元素,其物理次序也是相邻的,因此占用空间紧凑.

### 初始化

“`CPP
int InitList(List &L){
L.elem =new ElemType[MaxSize];
if(!L.elem) return ERROR;
L.length=0;
return SUCCESS;
}
“`

### 查找

“`CPP
int LocateElem(List L,ElemType e){
for(int i=0;i<L.length;++i)
if(L.elem[i]==e) return i+1; //返回从1开始计数的位置
return 0;
}
“`

时间复杂度 $O(n)$ .

### 插入

“`CPP
int InsertElem(List &L,int locate,ElemType e){
if(locate<1||locate>L.length+1) return ERROR;
if(L.length==MaxSize) return ERROR;
for(j=L.length-1;j>=locate-1;–j)
L.elem[j+1] = L.elem[j];
L.elem[locate-1] = e;
++L.length;
return SUCCESS;
}

“`

时间复杂度 $O(n)$ .

### 删除

“`CPP
int DeleteElem(List &L,int locate,ElemType &e){
if(locate<1||locate>L.length) return ERROE;
e=L.elem[locate-1];
for(int j=locate;j<=L.length-1;j++)
L.elem[j-1] = L.elem[j];
–L.length;
return SUCCESS;
}

“`

时间复杂度 $O(n)$ .

## 链式线性表

链式的线性表存储单元可以是连续的也可以是不连续的,因此除了需要存储本身的信息外还需要存储其直接后记的存储单元信息,这两部的存储映像称为结点(Node),它包括两个域:
1. 存储数据元素信息的称之为数据域.
2. 存储直接后继存储位置的称之为指针域.指针域中存储的信息称之为指针或链.

而根据指针域中所包含的指针个数/指针指向/指针连接方式,可将链表分为:
1. 单链表
2. 循环链表
3. 双向链表
4. 二叉链表
5. 十字链表
6. 邻接表
7. 邻接多重表

其中单链表/循环链表/和双向链表用于实现线性表的链式存储结构.

### 单链表初始化

“`CPP
int InitList(LinkList &L){
L=new LNode;
L->next = NULL; //(*L).next=0;
return SUCCESS;
}
“`

### 单链表查找

按序查找

“`CPP
int LocateElem(LinkList L,int locate,ElemType &e){
LNode* p=L->next;
int j=1;
while(p&&j<locate){
p=p->next;
++j;
}
if(!p||j>1) return ERROR;
e=p->data;
return SUCCESS;
}
“`

按值查找

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

两者时间复杂度都是 $O(n)$ .

### 单链表插入

“`CPP
int InsertElem(LinkList &L,int locate,ElemType e){
LNode *p = L;
int j=0;
while(p&&j<locate-1){
p=p->next;
++j;
}
if(!p||j>locate-1) return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return SUCCESS;
}
“`

时间复杂度为 $O(n)$ .

### 单链表删除

“`CPP
int DeleteElem(LinkList &L,ElemType e){
LNode *p = L;
LNode *q = NULL;
while(p&&p->data!=e) p=p->next;
if(!p) return ERROR;
q=p->next;
p->next=q->next;
delete q;
return SUCCESS;
}
“`

时间复杂度为 $O(n)$ .

– – – – – –

其他诸如循环链表或双向链表,其实是在指针域中在添加一些节点的连接信息,比如循环链表的特点是表的最后一个节点的指针域指向头节点,使得整个链表形成一个环,从任意一个节点出发都能找到其他的节点.而双向链表则是将指针域中增加一个前驱连接点指针,直接指向前节点.虽然增加了更多信息方便查找,但相应也增加了增删改节点时的操作难度.