首页 > 代码库 > <数据结构与算法分析 C++描述> 表/栈/队列
<数据结构与算法分析 C++描述> 表/栈/队列
这一章主要内容：
* 抽象数据类型(ADT)的概念
* 实现表/栈/队列
* 了解这三个数据结构的应用场景
1. ADT
ADT: abstract data type, 是抽象的数学模型，在该模型上定义了一系列的操作。使用它的人，不需要了解它的存储方式，只关心它的逻辑特征。可以使用三元组的方法来表示（D,S,P),D是数据对象，S是数据之间的关系，P是对数据的基本操作，具体介绍，可以参考帖子：点击打开链接
2. 表ADT
表的数据自然是单个元素，而元素之间的关系是前驱与后继，操作包括查找/插入/删除等操作。
2.1 表的简单数组实现
数组是静态分配的，查找是花费常数时间(O(1))的，而插入和删除是线性时间(O(N)),如果操作发生在表的末尾，就不需要移动任何时间，花费常数时间(O(1)).
在C++中，包含有公共数据结构的实现--STL(standard template library)-标准模板库。
Vector基于数组实现，可以复制并且其占用的内存可以自动回收（通过析构函数），可以调整Vector的大小，以及容量（容量的改变是通过为基本数组分配一个新的内存块，然后复制旧的内存块到新块中，再释放旧块的内存）。在进行插入和删除操作时，需要位置标记，这里使用通用的迭代器（其实就是指针）。有三个问题：如何得到迭代器；迭代器执行什么操作；哪些表ADT方法需要迭代器作为形参。源码如下：
/*
* 用数组的方式实现线性表
*/
#include<iostream>
using namespace std;
template <typename Object>
class Vector
{
private:
int theSize;
int theCapacity;
Object * objects;
public:
//构造函数
explicit Vector(int initSize = 0) : theSize(initSize), theCapacity( initSize + SPACE_CAPACITY) {
objects = new Object[theCapacity];
}
//复制构造函数
Vector( const Vector &rhs) : objects(NULL) {
operator=( rhs);
}
//析构函数
~Vector() {
delete[] objects;
}
//重载复制操作符
const Vector & operator= (const Vector &rhs) {
if( this != &rhs) {
delete [] objects;
theSize = rhs.size();
theCapacity = rhs.capacity();
objects = new Object[ capacity() ];
for(int k=0; k<size(); k++) {
objects[k] = rhs.objects[k];
}
}
return this;
}
//调整Vector的大小
void resize(int newSize) {
if(newSize > theCapacity)
reserve( newSize*2 + 1);
theSize = newSize;
}
//调整容量
void reserve( int newCapacity) {
if( newCapacity < theSize)
return;
Object *oldArray = objects;
objects = new Object[newCapacity];
for( int k=0; k < newCapacity; k++)
objects[k] = oldArray[k];
theCapacity = newCapacity;
delete[] oldArray;
}
//重载取元素字符[]
Object & operator[] (int index) {
return objects[index];
}
//重载取元素字符[],并且返回的元素为左值，不能修改
const Object & operator[] (int index) const {
return objects[index];
}
//判断Vector是否为空
bool empty() const {
return size()==0;
}
//获得Vector的大小
int size() const {
return theSize;
}
//获得Vector的容量
int capacity() const {
return theCapacity;
}
//在尾部插入元素
void push_back(const Object &x) {
if(theSize == theCapacity) {
reserve( 2*theCapacity +1);
}
objects[theSize] = x;
theSize++;
}
//弹出尾部元素
void pop_back() {
theSize--;
}
//返回尾部元素
const Object & back() const {
return objects[theSize-1];
}
//使用指针来定义迭代器
typedef Object * iterator;
typedef const Object * const_iterator;
//获取Vector开始的迭代器
iterator begin() {
return &objects[0];
}
const_iterator begin() const {
return &objects[0];
}
//获取Vector结束的迭代器
iterator end() {
return &objects[ size() ];
}
const_iterator end() const {
return &objects[size()];
}
enum { SPACE_CAPACITY = 16 };
};
int main()
{
Vector<int> test;
test.push_back(2);
test.push_back(3);
//通过迭代器来打印Vector的内容
//TODO:怎么调用前面定义的迭代器呢
for(Vector<int>::iterator itr = test.begin(); itr < test.end(); itr++) {
//for(int i=0; i < test.size(); i++) {
cout << *itr << " ";
}
cout << endl;
bool vectorEmpty = test.empty();
if(vectorEmpty)
cout << "the vector is empty" << endl;
return 0;
}2.2 双向链表的实现
Vector是静态分配的数组，而List的空间则不是连续的，通过前向和后向指针来表明元素之间的关系。源码如下：
#include<iostream>
using namespace std;
template <typename Object>
class List
{
private:
//链表节点的定义，包括数据、指向前驱节点的指针、指向后驱节点的指针
struct Node {
Object data;
Node *prev;
Node *next;
Node(const Object & d = Object(), Node *p = NULL, Node *n = NULL) : data(d), prev(p), next(n) {}
};
private:
int theSize;
Node *head;
Node *tail;
void init()
{
theSize = 0;
head = new Node;
tail = new Node;
head->next = tail;
tail->prev = head;
}
public:
//const_iterator define
class const_iterator
{
protected:
Node *current;
Object & retrieve() const
{
return current->data;
}
const_iterator(Node *p) : current(p) { }
friend class List<Object>;
public :
const_iterator():current(NULL) {}
const Object & operator*() const
{
return retrieve();
}
//前缀，++itr
const_iterator & operator++ ()
{
current = current->next;
return *this;
}
//后缀，itr++
const_iterator & operator++(int)
{
const_iterator old = *this;
++(*this);
return old;
}
bool operator== (const const_iterator &rhs) const
{
return current == rhs.current;
}
bool operator!= (const const_iterator &rhs) const
{
return !( *this == rhs);
}
};
//iterator define
class iterator : public const_iterator
{
protected:
iterator(Node *p) : const_iterator(p) {}
friend class List<Object>;
public:
iterator() {}
Object & operator* ()
{
return this->retrieve();
}
const Object & operator* () const
{
return const_iterator::operator*();
}
iterator & operator++ ()
{
this->current = this->current->next;
return *this;
}
iterator operator++(int)
{
iterator old = *this;
++(*this);
return old;
}
};
public:
List()
{
init();
}
List(const List & rhs)
{
init();
*this = rhs;
}
~List()
{
clear();
delete head;
delete tail;
}
const List & operator= (const List & rhs)
{
if( this == &rhs)
return *this;
clear();
for( const_iterator itr = rhs.begin(); itr != rhs.end(); itr++) {
push_back( *itr);
}
}
iterator begin()
{
return iterator( head-> next );
}
const_iterator begin() const
{
return const_iterator( head->next);
}
iterator end()
{
return iterator(tail);
}
const_iterator end() const
{
return const_iterator(tail);
}
int size() const
{
return theSize;
}
bool empty()
{
return size() == 0;
}
void clear()
{
while( !empty() )
pop_front();
}
Object & front()
{
return *begin();
}
const Object & front() const
{
return *begin();
}
Object & back()
{
return *--end();
}
const Object & back() const
{
return *--end();
}
void push_front( const Object &x)
{
insert( begin(), x);
}
void push_back( const Object &x)
{
insert( end(), x);
}
void pop_front()
{
erase( begin() );
}
void pop_back()
{
erase(--end());
}
//插入节点，先创建这个节点，给它的prev和next赋值，然后再让p->prev->next和p->prev都指向这个新创建的节点
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));
Node *newNode = new Node(x, p->prev, p);
p->prev->next = newNode;
p->prev = newNode;
return iterator(newNode);
}
//删除节点，让p->prev->next指向p->next即可
iterator erase(iterator itr)
{
Node *p = itr.current;
p->prev->next = p->next;
p->next->prev = p->prev;
iterator result(p->next);
delete p;
theSize--;
return result;
}
iterator erase(iterator start, iterator end)
{
for( iterator itr = start; itr != end;)
itr = erase(itr);
return end;
}
};
int main()
{
List<int> test;
test.push_back(1);
test.push_back(2);
test.push_back(3);
for(List<int>::iterator itr = test.begin(); itr != test.end(); itr++) {
cout << *itr << " " ;
}
cout << endl;
return 0;
}issues:在编写代码中，出现了一次段错误，使用gdb调试是在执行插入操作时，p->prev->next这一句会出现段错误，查看p->prev指向了NULL，发现在初始化函数init中，将tail->prev=head,写成了tail->next=head了。这样逻辑上肯定就不对了。3. 栈ADT
栈其实就是一个表，只是操作有所不同而已。在栈中是后入先出(LIFO)。push是元素入栈－－输入，pop是元素出栈，top是取出元素。这里通过继承的方式，使用Vector来实现简单的栈。
#include "vector.cpp"
template<typename Object>
class Stack: public Vector<Object>
{
public:
void push(const Object & data)
{
this->push_back(data);
}
void pop()
{
this->pop_back();
}
const Object &top()
{
return this->back();
}
};
int main()
{
Stack<int> test;
test.push(1);
test.push(2);
test.pop();
int a = test.top();
cout << "the top element is " << a << endl;
return 0;
}应用：平衡符号（编译器的检查语法的规则－括号匹配）/后缀表达式/函数调用。这里讲一下尾递归。 递归是直接或者间接调用自己，也就是分而治之的思想，可以使程序更加容易理解，但是会占用栈空间，如果递归很多次的话，会导致栈空间的耗尽。 测试程序如下：
#include<iostream>
using namespace std;
//循环输出多个元素
void print(int start, int end)
{
if(start == end)
return;
cout << start << endl;
start++;
print(start, end);
}
int main()
{
print(1,20000000);
return 0;
}在我的PC上，运行到261812次就会出错。使用:ulimit -s可以查看PC的默认栈空间，我的为8192,我将空间*2=16384之后，运行次数也会加倍，变为：523989。当然现在编译器都可以做相应的优化（gcc -O2)，将尾递归转化为循环，常量栈，具体帖子可以参见清水河畔的交流贴：点击打开链接 点击打开链接
3. 队列ADT
同样，队列ADT也是表，是一个先进先出的表(FIFO). 可以考虑用循环数组实现。代码后面会补上。。明天回家。。
应用：排队论等
<数据结构与算法分析 C++描述> 表/栈/队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。