数据结构 链表改进

主要介绍循环链表和双向循环链表

循环链表

双向循环链表

2-1

对于一非空的循环单链表,hp分别指向链表的头、尾结点,则有()

循环单链表判空:

设头结点front,尾节点rear:

(front->next = front),rear->next = rear;

 2-2

在双向循环链表结点p之后插入s的语句是

过程就是,画个如下的图,然后按照选项给出的数据,挨个尝试,

当然,对于这类题目,记住一个点,可以大大减少选择难度:

最后一个一定是:  p->(next) = s;

翻译成通用的就是,两个操作点的直接关系,放在最后!

2-4

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用什么存储方式最节省运算时间?

设尾指针为 rear,尾部插入p,rear->next = p,rear = rear-next; 复杂度O(1)

删除第一个元素,rear->next = rear->next->next,复杂度O(1)

2-5

若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间

头结点设为front;

最后一个节点插入;front->prior->next = p,p->prior = front->prior,p->next=front,front->prior=p;,复杂度O(1)

删除尾节点:front->prior->prior->next=front,front->prior = front->prior->prior;复杂度O(1)

这种题型就是想法设法,把几种操作的时间复杂度求解出来,然后进行比对,选择出正确答案;

2-18

已知指针ha和hb分别是两个单链表的头指针,下列算法将这两个链表首尾相连在一起,并形成一个循环链表(即ha的最后一个结点链接hb的第一个结点,hb的最后一个结点指向ha),返回该循环链表的头指针。请将该算法补充完整。

typedef struct node{
ElemType data;
    struct node *next;
}LNode;
LNode *merge(LNode *ha, LNode *hb) {
LNode *p=ha;
     if (ha==NULL || hb==NULL) {
cout<<”one or two link lists are empty!”<<endl;
          return NULL;
     }
     while ( p->next!=NULL ) 
           p=p->next;
     p->next=hb;
     while ( p->next!=NULL ) 
           p=p->next;
           __________         
}

 这种类型的题目,先把代码里面最后的指针位置弄清楚,代码里进行的操作已经把ha , hb 连接了起来,p现在指向hb 尾节点,你的目的是实现循环,p->next = ha;这是候的p->next正好是循环链表的头指针 , return p->next!==ha;

2-21

采用多项式的非零项链式存储表示法,如果两个多项式的非零项分别为N​1​​和N​2​​个,最高项指数分别为M​1​​和M​2​​,则实现两个多项式相乘的时间复杂度是()

数学问题,非零项*和 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

第十九天 集合-Map接口容器工具类集合框架总结【悟空教程】

Map集合的特点,如是否可重复,是否有序仅作用在键上,如HashMap集合的键不得重复,值可以重复。

1823
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

984
来自专栏Python爱好者

Java基础笔记17

1396
来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

4256
来自专栏待你如初见

Day10

1462
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题15求链表中倒数第K个结点

算法的分析过程均在代码注释中: /** * 题目:输入一个单链表,输出该链表从后往前的第k个数。 * PS:从后往前数时从1开始计数。 * @author...

2926
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

892
来自专栏数据结构与算法

P1341 无序字母对

题目描述 给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。...

3508
来自专栏JavaEdge

LinkedHashMap源码分析(基于Java8)概要示例代码节点构造函数增删查遍历

4145
来自专栏有趣的Python

4-Java常用工具类-集合

问题: 存储20名学生的学生信息。20是不变的,就是这么多。 问题: 存储商品信息。不知道自己要买多少商品。

1472

扫码关注云+社区