第十章 基本数据结构——链表

 链表

  链表与数组的区别是链表中的元素顺序是有各对象中的指针决定的,相邻元素之间在物理内存上不一定相邻。采用链表可以灵活地表示动态集合。链表有单链表和双链表及循环链表。书中着重介绍了双链表的概念及操作,双链表L的每一个元素是一个对象,每个对象包含一个关键字和两个指针:next和prev。链表的操作包括插入一个节点、删除一个节点和查找一个节点,重点来说一下双向链表的插入和删除节点操作,图例如下:

链表是最基本的数据结构,凡是学计算机的必须的掌握的,在面试的时候经常被问到,关于链表的实现,百度一下就知道了。在此可以讨论一下与链表相关的练习题。

(1)在单链表上插入一个元素,要求时间复杂度为O(1)。

解答:一般情况在链表中插入一元素是在末尾插入的,这样需要从头遍历一次链表,找到末尾,时间为O(n)。要在O(1)时间插入一个新节点,可以考虑每次在头节点后面插入,即每次插入的节点成为链表的第一个节点。

(2)在单链表上删除一个给定的节点p,要求时间复杂度为O(1)。

解答:一般情况删除一个节点时候,我们需要找到该节点p的前驱节点q,需要对链表进行遍历,运行时间为O(n-1)。我们可以考虑先将q的后继节点s的值替换q节点值,然后删除s即可。如下图删除节点q的操作过程:

(3)单链表逆置,不允许额外分配存储空间,不允许递归,可以使用临时变量,执行时间为O(n)。

解答:这个题目在面试笔试中经常碰到,基本思想上将指针逆置。如下图所示:

(4)遍历单链表一次,找出链表中间节点。

解答:定义两个指针p和q,初始都指向链表头节点。然后开始向后遍历,p每次移动2步,q移动一步,当p到达末尾的时候,p正好到达了中间位置。

(5)用一个单链表L实现一个栈,要求push和pop的操作时间为O(1)。

解答:根据栈中元素先进后出的特点,可以在链表的头部进行插入和删除操作。

(6)用一个单链表L实现一个队列,要求enqueue和dequeue的操作时间为O(1)。

解答:队列中的元素是先进先出,在单链表结构中增加一个尾指针,数据从尾部插入,从头部删除。

3、有根树的表示

  采用链表数据结构来表示树,书中先降二叉树的链表表示法,然后拓展到分支数无限制的有根数。先来看看二叉树的链表表示方法,用域p、left和right来存储指向二叉树T中的父亲、左孩子和右孩子的指针。如下图所示:

  对于分支数目无限制的有根树,采用左孩子、右兄弟的表示方法。这样表示的树的每个节点都包含有一个父亲指针p,另外两个指针:

(1)left_child指向节点的最左孩子。

(2)right_sibling指向节点紧右边的兄弟。

时间: 2024-10-09 13:06:25

第十章 基本数据结构——链表的相关文章

c-一个数据结构 链表的问题

问题描述 一个数据结构 链表的问题 #include #include #include typedef int ElemType; typedef struct Node{ int data; struct Node *next; }NODE,*PNODE; int main(void){ PNODE Head=NULL;//定义初始头结点 Head=creat_list();//初始建立链表 traversal_list(Head);//遍历输出链表 int len=length_list(

数据结构链表问题 为什么不能实现

问题描述 数据结构链表问题 为什么不能实现 首先 我定义的链表类型是(飞机票查询系统) typedef struct flight{ string origin; string destination; string flt; //航班号 int time[2]; int tim[2]; // time[0]表示小时,time[1]表示分钟 int money; struct flight *next;}flight,*Flight; 然后又主函数调用information() 程序具体实现为:

单链表-数据结构 链表的创建 不知道怎么改

问题描述 数据结构 链表的创建 不知道怎么改 #include #include #include typedef struct Node //创建新的数据类型 { int data; //数据域 struct Node * pNext; //指针域 }NODE, *PNODE; //NODE等价与struct Node //PNODE等价于struct Node * //函数声明 PNODE create_list(); void traverse_list(NODE pHead); int

JavaScript数据结构链表知识详解_javascript技巧

最近在看<javascript数据结构和算法>这本书,补一下数据结构和算法部分的知识,觉得自己这块是短板. 链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的.每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成. 好处:可以添加或移除任意项,它会按需扩容,且不需要移动其他元素. 与数组的区别:     数组:可以直接访问任何位置的任何元素:     链表:想要访问链表中的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素. 做点小笔

Java 数据结构链表操作实现代码_java

 链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个

c语言 链表-数据结构链表创建出错

问题描述 数据结构链表创建出错 麻烦大家帮我看看哪里出错了,十分感谢啊 #include "stdio.h" #include "malloc.h" #include "stdlib.h" #define NULL 0 #define OK 1 typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data; struct LNode *next; }LN

数据结构 链表 c语言 简单问题

问题描述 数据结构 链表 c语言 简单问题 正在学习数据结构 有个问题想问一下 下面的代码中为什么 pt == NULL 就说明列表满? //如果列表满则返回真 bool ListIsFull (const List * plist) { Node * pt; bool full; pt = (Node *)malloc(sizeof (Node)); if (pt == NULL) full = true; else full = false; free (pt); return full;

数据结构 链表 插入出错

问题描述 数据结构 链表 插入出错 #include <stdio.h> #include <string> #include <iostream> using namespace std; struct LNode{ string name; string sex; int age; LNode *next; }; LNode *students; void InitList(LNode *list){ list=(LNode *)malloc(sizeof(LNod

泛型思想理解数据结构链表

前言 1. 本文用到一个很重要的思想--泛型编程思想:不熟悉泛型的话,请自行搜索相关资料学习(void *,如memcpy,memmove,qsort,memset等库函数均使用到了泛型思想) . 2. 本文最后会提供一个demo程序附件,该demo程序以c99标准进行编写的,在Linux-gcc下调试通过,vc6下可能会有错误. 3. 本文图示中,红色实线表示要添加的地方,黑色虚线表示要断开的地方,黑色实线保持原样. 4. 本文链表设计为最简单的非循环单链表. 数组与链表比较 数组 链表 优点