文档章节

【数据结构】回顾表ADT

NoMasp
 NoMasp
发布于 2015/09/08 21:48
字数 601
阅读 4
收藏 0

1.对于表的所有操作来说,都可以使用数组来实现,而且数组虽然是静态分配的,但内部存储数组的vector类却允许在需要时将数组的大小增加一倍。

2.正是因为数组的实现,使得printList以线性时间来执行,而findkth甚至是通过常数时间。最不济的是插入和删除了,如果位置不好,比如说在0号位置插入就需要将整个数组的所有元素都向后移,为O(N)。正是为了避免插入和删除的线性开销,我们就开始使用一种叫做链表(Linked List)的技术。

这里写图片描述

3.链表由许多在内存中相连的结点(Node)组成,而每一个结点都有表元素和该元素后续元的结点的链(link)。这个叫做next链,自然而然地,最后一个单元的next链指向NULL。

4.STL的全称是“Standard Template Library”,中文名叫做“标准模板库”。表ADT就在其中。

5.数组就是一块指向内存的指针变量,内存块可以通过new[]来分配,同时也必须用delete[]来释放,内存块的大小不能改变。

6.将一个包含x的新结点通过p和p.prev指向的结点结合,指针的赋值可以按下面的方式来写。

Node *newNode=new Node(x,p->prev,p);
p->prev->next=newNode;
p->prev=neweNode;

但它还可以得到合并:

Node *newNode=new Node(x,p->prev,p);
p->prev=p->prev->next=newNode;

然后它还可以进一步合并:

p->prev=p->prev->next=new Node(x,p->prev,p);

因此可以这样来写insert操作:

iterator insert(iterator itr,const Object & x)
{
    Node *p=itr.current;
    theSize++;
    return iterator(p->prev=p->prev->next=new Node(x,p->prev,p));
}   

7.同样的,对于双向列表的delete操作来说,会是这样:

p->prev->next=p->next;
p->next->prev=p->prev;
delete p;

修改之后的insert函数。

iterator insert(iterator itr,const Object & x)
{
    itr.assertIsValid();
    if(itr.theList!=this)
        throw IteratorMismatchException();

    Node *p=itr.current;
    theSize++;
    return iterator(* this,p->prev=p-prev->next=new Node(x,p->prev,p));
}


欢迎大家点击左上角的“关注”或右上角的“收藏”方便以后阅读。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp

版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/45567763

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
加载中

评论(0)

nomasp 博客导读:Lisp/Emacs、Algorithm、Android

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/44966625 Profile Introduction to Blog 您能看到这篇博客导读...

nomasp
2015/09/17
0
0
《数据结构》笔记三:线性表之顺序存储结构

前言: 关于源码的几个说明: 编码工具:Xcode 语言:C语言 参考书:《大话数据结构》 为了方便不熟悉的小伙伴们,文中关于代码的部分给出了详细的步骤,只要按照步骤,都可以实现。 另:小编...

小曼blog
2019/06/28
0
0
数据结构那些事(二)线性表及其连续存储的实现

一、基本概念 首先,还是来回顾线性结构的基本概念。 线性结构:在这些数据元素中有一个可以被称为“第一个”(元素01)的数据元素;还有一个可以被称为“最后一个”(元素04)的数据元素;除...

零下三度
2014/06/07
216
0
数据结构——第一章线性表:01线性表的逻辑结构

1.线性结构的基本特征:线性结构是一个数据元素的有序集。 (1)集合中必定存在一个唯一的“第一元素” (2)集合中必定存在一个唯一的“最后元素” (3)除最后一个元素外,集合中的元素均有...

H36Phaeton
2018/10/29
0
0
SQLite设计问题

本人开发一个基于Android 4.2.2 的 Ticcit-system(demo) 用于学校学生自学计算机技术 数据库:SQLite3 平台:ADT 物理机:win7 (run ADT) ip:A 虚拟机 :ubuntu (run NFS sever) IP B OOA...

JoneWisso
2014/02/27
315
0

没有更多内容

加载失败,请刷新页面

加载更多

做了几年程序员,某天居然发现自己没学过数据结构。。。

原创声明 本文作者:黄小斜 转载请务必在文章开头注明出处和作者。 简介 学习编程,数据结构是你必须要掌握的基础知识,那么数据结构到底是什么呢? 根据百度百科的介绍,数据结构是计算机存...

黄小斜
12分钟前
28
0
正则表达式:删除包含“帮助”等的行

我有一个很长的命令文件。 使用Notepad ++或regex,我想删除所有包含“help”的行,包括keyboard_help等。 如何才能做到这一点? #1楼 在Notepad ++中执行此操作的另一种方法是在“查找/替换...

javail
14分钟前
32
0
百度飞桨口罩人脸检测与识别模型再升级,视频教学带你实战

自百度开源业界首个口罩人脸检测及分类模型之后,开发者社区进行了充分讨论并提出了该模型存在的一些问题和不足。在本文中,百度飞桨官方对这些反馈积极回应,同时提出四大升级方案,为开发者...

飞桨PaddlePaddle
21分钟前
26
0
2020教你如何更好地学习Java

学习是需要规划时间的,对于自学来说,需要有一个学习路线,因为大部分的人都是从零基础进行学习的,所以我建议大家一定要跟着大纲走,不然非常容易走偏。 首先放大纲 1.制定一个学习计划,没...

即将秃头的Java程序员
37分钟前
41
0
作为一名程序员找到一份java的工作需要学习哪些知识?

首先是Javase作为Java最基本的学习内容,不在多说。 然后是掌握JavaScript的基本原理,因为做Java编程开发必须学会JavaScript,用到JavaScript非常多,但是现在很多公司是不用去写原生的Jav...

Java天天
43分钟前
49
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部