之前在写Java中的容器时,有写到一些关于数据结构的部分,可以参考《Java的List、Set、Map容器》一文。这里再详细回顾一下对数据结构的学习。
C语言及指针回顾
字节:存储数据的单元,是硬件所能访问的最小单位。
1字节=8位,1k=1024字节,1M=1024k,1G=1024M。对于4G内存的电脑来说,所能存放数据最多是(4*1024*1024*1024*8)位的二进制数据。
物理内存地址:内存单元的编号,从零开始的非负整数
指针:指针就是地址,地址就是指针。
指针变量:存放内存单元编号的变量,就是存放地址的变量。
结构体:把一些基本类型数据组合在一起,形成一个新的复合数据类型。
一个指针变量,无论它指向的变量占几个字节,该指针变量本身只占4个字节。用第一个字节的地址表示整个变量的地址。一个变量的地址是用该变量首字节的地址来表示。CPU通过地址总线、控制总线、数据总线,俗称三根总线,来操作物理内存。
看懂一个程序的三个步骤
- 程序的流程
- 每个语句的功能
- 试数
问题规模的增加,算法对运算处理的性能消耗
|
|
从上图的运行结果可以明显的看到,当问题计算的规模n=10000时,好像method1、method2、method3彼此的计算耗时都是0毫秒。但是当n再扩大10倍时,method1花了2毫秒,method3直接抛异常了,而method2而然是0毫秒。
method1是用for循环的方式,method2则是高斯公式,method3是用递归的方式。
在数据结构领域,关于算法的时间复杂度,有一个计算公式,大O表示法。这里不做过多说明,教科书上有该公式的计算方法跟定论。
线性结构
数据结构中关于数据的逻辑结构,只分为线性结构、非线程结构。所谓的线性结构,我们可以用一个生活化的场景来理解它,用穿好线的针能够一次把元素都串起来。线性结构是指元素只能有一个顶点、一个端点,中间的元素只有一个前驱跟一个后继。
顺序表
可以把串在一起的元素,紧紧的挤压在一个方向。让元素紧挨着元素。这就可以理解成是一个顺序表。顺序表其实就是数组,一次给一片连续的空间,然后把空间按一个一个的小格子划分好。其特点是:当CPU在内存中找不到连续一片的符合要求的空间,会导致分配失败。可以通过存放元素格子的宽度,也就是偏移量乘以第几个元素,获取指定地址空间上的元素。
代码示例
|
|
链式结构
可以把串在一起的元素,中间的线还流出一点点来。只要顺着线能找到元素。这就可以理解成是一个链式结构。每一个数据元素的地址可以是分散开来的,动态分配,彼此通过指针相连。每个结点只有一个后续结点,首结点没有前驱,尾结点没有后续。链式结构,也就是俗称的链表。对于链表的操作,额外增加一个头结点,以方便对整个链表的操作。头结点跟头指针是两个不同的概念。头结点的数据域部分是空的。
单链表
在单链表的结构中,数据元素要有两部分,一部分存放数据元素的数据部分,一部分存放下一个数据元素的地址。
代码示例
|
|
双链表
在双链表的结构中,数据元素要有三部分,一部分存放数据元素的数据部分,一部分存放下一个数据元素的地址,一部分存放上一个数据元素的地址。
线性结构的应用-队列、栈
队列
操作受限的线性表,也称先进先出表。队尾插入,队头取出元素。在非空队列中,队头指针始终指向队头元素,队尾指针始终指向队尾元素的下一个位置。
循环队列
链式栈
栈是限定在表的一端进行插入和删除运算的线性表,通常将插入、删除的一端称为栈顶。链式栈,将对链表的操作进行一定的限制,在一端进行插入、删除即可。链式栈,适合开口向上或向下的操作。
栈的四种不同操作方式。
顺序表栈
顺序表栈,适合开口向左或向右的操作。顺序存储结构,采用数组实现。
|
|