线性表

admin

线性表是由n（n>=0）个相同元素的数据元素组成的有限序列，他是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每个元素都有唯一的直接前驱，除了最后一个元素外，每个元素都有唯一的直接后继。

顺序表
顺序表是顺序储存方式，即逻辑上相邻的数据在计算机内的储存位置也是相邻的。顺序储存方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，所以插入、删除时需要移动大量元素。时间复杂度往往过高。

链表
链表是线性表的一种线性储存方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那该如何表示逻辑上的相邻关系呢？


单链表

基本操作：
1.初始化

Linklist L;
L=new lnode;
L->next=NULL;
if(!L) return 0;//竞赛可以不要这句

2.创建
头插法建表又称：逆序建表；尾插法又称：正序建表。

s=new Lnode;
s->data=2;

Attention:变量名调用它的域时用变量.，指针名则用->
例如：

struct st1{
    name...
}st1;//后面调用时用st1.name
struct st1{
    name...
}st1 *p;//后面调用时用p->name,指针可以说一个存储地址的变量
3.取值+查找
注意：链表的头指针不可以随意改动。


先p=L->next，再p=p->next......直到j=i停止。a为目标数据。

4.插入

记住：单向链表向后插入。双向链表才可以双向操作。

5.删除（跳过）

必须要知道它的前一个节点，否则删不了。
使用delect q;将其空间释放。

双向链表

在单向链表的基础上，每个结点增加了一个域。
a的左右两个域为prior和next，prior指向前一个（前指针），next指向后一个（后指针）。

1.双向链表的插入


修改四个指针。秘诀：未标记的一端先修改。

p->prior->next=s;//①
s-prior=p->prior;//②
s->next=p;//③
p->prior=s;//④
2.删除