【数据结构】回顾表ADT

2015/09/08 21:48
阅读数 4

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

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部