数据结构与算法之美学习笔记(二)线性表

发布于:2023-01-20 ⋅ 阅读:(17) ⋅ 点赞:(0) ⋅ 评论:(0)

一、数组

一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

1.特性

(1)随机下标访问
因为数组定义在一组连续的内存中,因此数组可以通过下标来进行时间复杂度为O(1)的随机访问
(2)低效的插入和删除操作
同样是因为数组定义在一组连续的内存中,对数组进行插入和删除操作时,需要先移动其他元素,通常会产生一段时间复杂度为O(n) 的操作

2.谨防数组下标越界

当在数组操作中,出现下标越界的情况时,当前下标所访问的地址将会是一个随机的值,这会对程序带来无法预知的问题

二、链表

链表通过指针将一组零散的内存块串联在一起

1.单链表

(1)定义:通常将链表中的每个内存块称为一个“结点”,而每个结点除了存储本身的数据之外,还需要记录下一个结点的地址,通常被称为后继指针(next),在一条链表中,把第一个结点称为头结点,把最后一个结点称为尾结点。
ps.尾结点的next指针指向NULL
(2)特性
插入和删除操作执行效率高,时间复杂度为O(1)
随件访问效率低,若要实现随件访问,时间复杂度为O(n)

2.循环链表

循环链表是一种特殊的单链表。

(1)定义:循环链表和单链表唯一的区别在于,循环链表尾结点的next指针指向循环链表的头结点。

3.双向链表

链表中的每一个结点都有一个前驱和后继指针

(1)特性:可以以O(1)的时间复杂度找到当前结点的前驱指针

4.注意链表边界条件

(1)如果链表为空时,代码是否能正常工作?
(2)如果链表只包含一个结点时,代码是否能正常工作?
(3)如果链表只包含两个结点时,代码是否能正常工作?
(4)代码逻辑在处理头结点和尾结点的时候,是否能正常工作?

三、栈

一种先进后出的数据结构

1.定义

(1)只能对栈顶数据进行操作
(2)一个栈通常具有入栈和出栈两种操作

int stack[n];
int top=0;

void push(int value) { //入栈
	stack[top++] = value;
}

int pop() { //出栈
	return stack[--top];
}

int top() { //获取栈顶数据
        return stack[top-1];
}

以上代码实现了一个基本的栈

四、队列

一种先进先出的数据结构

1.定义

(1)入队操作在队尾进行,出队操作在队头进行
(2)一个队列通常具有入队和出队两种操作

int queue[n];
int head=0,tail=0;

void push(int value) { //入队
	queue[tail++] = value;
}

int pop() { //出队
	return queue[head++];
}

int front() { //获取队头数据
        return queue[head];
}

以上代码实现了一个基本的队列


网站公告

欢迎关注微信公众号

今日签到

点亮在社区的每一天
签到