以图明志

数据结构

[专题] 单链表反转/逆序的两种方法

比较两种思路的差异
我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1的next域指向结点a3,最后将结点a2的next域指向结点a1,就完成了第一次交换。

数据结构

[专题] 将单链表重置为空表

释放结点前需要处理后继关系
当我们不打算使用某个单链表时,就需要把它销毁,其实也就是在内存中将它释放掉,以便于留出空间给其他程序或软件使用。在循环体内直接写free (p); p=p->next; 这样真的没问题吗?要知道p是一个结点,它除了有数据域,还有指针域。在free (p); 时,其实是在对它整个结点进行删除和内存释放的工作。

数据结构

[专题] 用尾插法实现单链表整表创建

与头插法的区别
昨天我们谈到了头插法,可事实上,我们还是可以不这样干,为什么不把新结点都放到最后呢,这才是排队时的正常思维,所谓的先来后到。我们把每次新结点都插在终端结点的后面,这种算法称之为尾插法。与头插法区别下?*L 是头结点,r这里的角色是尾结点,一开始他们是重合的。

数据结构

[专题] 用头插法实现单链表整表创建

头插法其实就是从表头开始的插入操作
不知道有没有注意到,前面我们在谈“单链表插入操作”的时候,其实我们是用插入操作来完成了单链表的整表创建的。那么创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。其实就是将 p->next 指向结点 (*L)->next,然后再将 结点 (*L)的后继指向p,这个很好理解。

数据结构

[专题] 查找某数在单链表中的位置

单链表的元素查找
这里也同样需要用到“工作指针”。首先声明一个工作指针,并让它指向链表的首元结点 LinkList p=L->next。参数 L 其实就是头指针,L->next 就是头结点。然后用工作指针遍历链表,当 p->data 与传入的查找数 e 相等,返回其位置即可。

数据结构

[专题] 获取单链表中的指定位置的元素

工作指针的概念
单链表作为一种数据结构,存取数据是其很基本的操作。今天我们来看一下,如何获取单链表指定位置的元素。在单链表中,由于第i个元素到底在哪是没办法一开始就知道,必须得从头开始找。我们可以先设计一下单链表实现获取第i个元素的数据的操作GetElem()函数。

数据结构

[专题] 单链表的删除某个元素的操作

详尽介绍单链表删除算法
单链表删除第i个数据结点的算法思路:声明一结点p指向链表第一个结点,初始化j从1开始;当j < i时,就遍历链表,让p的指针向后移动,不断指向下一个结点,j累加 1;若到链表末尾p为空,则说明第i个元素不存在;否则査找成功,将欲删除的结点p->next賦值给q;单链表的删除标准语句p->next=q->next;

数据结构

[专题] 单链表的插入与遍历操作

详细讲解单链表的插入过程
昨天我们说了,单链表如何进行初始化操作。初始化之后,我们就创建了一个单链表了,接下来,我们要往这个链表里填充数据,也就是常说的,插入操作。先把结点s的指针next指向ai+1,即 s->next = p->next. 然后再把ai的指针next指向s,即 p->next = s.

数据结构

[专题] 单链表的初始化

初始化函数的设计
初始化一个链表需要做什么事情呢?头指针是必须要有的,头结点为了规范化操作,最好也得有。那么第一步就是:创建一个头结点,并且让头指针指向这个头结点。其实头指针也有了。参数 *L 传入的 L其实就是链表的首地址,也就是头指针。接下来也就是在内存开辟一个区域来作为头结点。

数据结构

[专题] 单链表的结构体定义与声明

C语言结构体的知识
结点由存放数据元素的数据域存放后继结点地址的指针域组成。typedef为C语言的关键字,作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型(int,char等)和自定义的数据类型(struct等)。在编程中使用typedef目的一般有两个,一个是给变量一个易记且意义明确的新名字,另一个是简化一些比较复杂的类型声明。

数据结构

[专题] 单链表的头指针、头结点与首元结点

几种单链表的区别
链表也是一种线性表,所以总得有个头有个尾。链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点,其实就是上一个的后继指针指向的位置。这里有个地方要注意,就是对头指针概念的理解,这个很重要。“链表中第一个结点的存储位置叫做头指针”,如果链表有头结点,那么头指针就是指向头结点数据域的指针。

数据结构

[专题] 线性表链式存储结构的由来与基本概念

开始学习链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。以前在顺序结构中,每个数据元素只需要存数据元素信息就可以了。现在链式结构中,除了要存数据元素信息外,还要存储它的后继元素的存储地址。

数据结构

[专题] 线性表顺序存储的优缺点

插入与删除的时间复杂度
先来看最好的情况,如果元素要插入到最后一个位置,或者删除最后一个元素, 此时时间复杂度为0(1),因为不需要移动元素的,就如同来了一个新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。

数据结构

[专题] 第08话:线性表删除某个元素

线性表的删除操作
根据之前定义的线性表ADT,现在还剩下一个操作,就是删除了。今天把这个操作弄完。了解线性表的插入,就很容易理解线性表的删除了。删除就是插入的逆过程。删除算法的思路:如果删除位置不合理,抛出异常;取出删除元素;从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置。

数据结构

[专题] 第07话:线性表的查找操作

根据键或值去查找
如何设计查找功能的函数呢。首先参数,我们需要传入线性表L,仅仅查找的话是不需要对表进行变化的,所以用值传递就行。然后就是传入需要查找元素的位置 i,最后还需要一个参数 *e,这个需要用地址传递,因为要保存函数的查找结构。

数据结构

[专题] 第06话:判断线性表是否为空与置空操作

直接对表的length属性操作
ADT里判断线性表是否为空的函数设计如下:bool listEmpty(L); //判断一个线性表是否为空,不修改表传值。其实就是判断表的长度是否为0而已。将表置空的函数就更简单了,直接将长度赋值为0即可。这两个函数如果要测试的话可以自行加入到上一篇的完整可运行代码里。
4 / 10 首页 < Prev 2 3 4 5 6 Next > 尾页 页码: