2022.7.20 线性表

线性表

线性表是由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.取值+查找
\(\color{red}{注意:链表的头指针不可以随意改动。}\)

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

4.插入

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

5.删除(跳过)

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

双向链表


在单向链表的基础上,每个结点增加了一个域。
a[i]的左右两个域为prior和next,prior指向前一个(前指针),next指向后一个(后指针)。

1.双向链表的插入

修改四个指针。\(\color{red}{秘诀:未标记的一端先修改。}\)

p->prior->next=s;//①
s-prior=p->prior;//②
s->next=p;//③
p->prior=s;//④

2.删除

delect p;


文章标签:

原文连接:https://www.cnblogs.com/sqrthyy/p/16497320.html

相关推荐