以图明志

数据结构

获取单链表中的指定位置的元素

工作指针的概念
单链表作为一种数据结构,存取数据是其很基本的操作。今天我们来看一下,如何获取单链表指定位置的元素。在单链表中,由于第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即可。这两个函数如果要测试的话可以自行加入到上一篇的完整可运行代码里。

数据结构

第05话:线性表的遍历、插入操作

详细介绍插入操作的算法思路
插入算法的思路:如果插入位置不合理,抛出异常;如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;将要插入元素填入位置i处;表长加1。插入操作会改变原有链表,所以要用地址传递。

数据结构

第04话:线性表的初始化

开始用代码去理解数据结构
初始化的函数怎么写呢。初始化就是建立一个空线性表,那直接把长度置为0就行了。因为要初始化,要对线性表本身进行操作,所以不能用值传递。值传递不会改变实参的值嘛。地址传递的话呢,实际上在函数内部执行了这么一个操作:L = &L. 所以操作函数内部的L,也就相当于操作外部的线性表L。

数据结构

第03话:线性表的顺序存储结构

线性表的结构体设计
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。既然线性表的毎个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。

数据结构

第02话:线性表的抽象数据类型ADT定义

线性表有哪些基本操作?
前面我们已经给了线性表的定义,现在我们来分析一下,线性表应该有一些什么样的操作呢?然后再定义线性表的ADT。对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的,对于实际问题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。

数据结构

第01话:线性表的概念与定义

什么是线性表
线性表(List):零个或多个数据元素的有限序列。首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。如果一个小朋友去拉两个小朋友后面的衣服,那就不可以排成一队了。
7 / 22 首页 < Prev 5 6 7 8 9 Next > 尾页 页码: