# 【数据结构】回顾表、栈、队列

2015/09/08 21:46

1.如何通过调整链而不是数据来交换两个相邻的元素？

    // 单向链表
Node *p,*afterp;
p=beforep->next;
afterp=p->next;

p->next=afterp->next;
beforep->next=afterp;
afterp->next=p;

// 双向链表
Node *beforep,*afterp;
beforep=p->prev;
afterp=p->next;

p->next=afterp->next;
beforep->next=afterp;
afterp->next=p;
p->next->prev=p;
p->prev=afterp;
afterp->prev=beforep;

2.如何求出两个已排序的表L1和L2的交集和并集。

// 交集
template <typename Object>
list<Object> intersection( const list<Object> & L1,
const list<Object> & L2)
{
list<Object> intersect;
typename list<Object>:: const_iterator iterL1 = L1.begin();
typename list<Object>:: const_iterator iterL2 = L2.begin();
while(iterL1 != L1.end() && iterL2 != L2.end())
{
if (*iterL1 == *iterL2)
{
intersect.push_back(*iterL1);
iterL1++;
iterL2++;
}
else if (*iterL1 < *iterL2)
iterL1++;
else
iterL2++;
}
return intersect;
}
// 并集
// Assumes both input lists are sorted
template <typename Object>
list<Object> listUnion( const list<Object> & L1,
const list<Object> & L2)
{
list<Object> result;
typename list<Object>:: const_iterator iterL1 = L1.begin();
typename list<Object>:: const_iterator iterL2= L2.begin();
while(iterL1 != L1.end() && iterL2 != L2.end())
{
if (*iterL1 == *iterL2)
{
result.push_back(*iterL1);
iterL1++;
iterL2++;
}
else if (*iterL1 < *iterL2)
{
result.push_back(*iterL1);
iterL1++;
}
else
{
result.push_back(*iterL2);
iterL2++;
}
}
return result;
}

3.一个有表头结点，没有尾结点，还有一个指向表头结点的指针的单向链表，写一个类包括以下函数：

template <typename Object>
struct Node
{
Object data;
Node *next;
Node (const Object & d = Object(),Node *n=NULL)
:data(d),next(n){}
};

template <typename Object>
class singleList {
public:
singleList(){init();}
~singleList()
{
}

singleList(const singleList & rhs)
{
init();
*this=rhs;
}

{
if(contains(x))
{
return false;
}
else
{
Node<Object> *ptr =new Node<Object>(x);
theSize++;
}
return true;
}

bool remove(Object x)
{
if(!contains(x))
return false;
else
{
Node<Object>*trailer;
while(ptr->data!=x)
{
trailer=ptr;
ptr=ptr->next;
}
trailer->next=ptr->next;
delete ptr;
theSize--;
}
return true;
}

int size()
{
return theSize;
}

void print()
{
while(ptr!=NULL)
{
count<<ptr->data<<" ";
ptr=ptr->next;
}
count<<endl;
}

bool contains(const Object & x)
{
while(ptr!=NULL)
{
if(x==ptr->data)
return true;
else
ptr=ptr->next;
}
return false;
}

void init()
{
theSize=0;
}

void eraseList(Node<Object> * h)
{
Node<Object> *ptr=h;
Node<Object> *nextPtr;
while(ptr!=NULL)
{
nextPtr=ptr->next;
delete ptr;
ptr=nextPtr;
}
}

private:
int theSize;
};

4.如何给List迭代器类添加对operator–的支持。

const_iterator & operator-- ()
{
current=current->prev;
return *this;
}

const_iterator operator-- (int)
{
const_iterator old=*this;
--(*this);
return old;
}

5.前面谈到过的双端队列（deque），给它添加以下功能：

push(x) 将项x插入到双端队列的前段
pop() 从双端队列删除前段项并返回
inject(x) 将项x插入到双端队列的尾端
eject() 从双端队列中删除尾端项并将其返回
template <typename Object>
class deque
{
public:
deque(){ l();}
void push (Object obj) {l.push_front(obj);}
Object pop () {Object obj=l.front();pop_front();return obj;}
void inject (Object obj) {l.push_back(obj);}
Object eject() {pop_back(obj);}
private:
list<Object> l;
}

6.不包含表头结点和尾结点，用单向链表高效地实现栈类。

template<typename Object>
struct node
{
node() {next=NULL;}
node(Object obj):data(obj){}
node(Object obj,node * ptr):data(obj),next(ptr){}
Object data;
node *next;
};

template<typename Object>
class stack { public: stack(){head=NULL;} ~stack(){while(head) pop();} void push(Object obj) { node<object> *ptr=new node<Object>(obj,head); head=ptr; } Object top() { return (head->data); } void pop() { node<Object> *ptr=head->next; delete head; head=ptr; } private: node<Object> *head; }

7.不包含表头结点和尾结点，用单向链表高效地实现队列类。

template<typename Object>
class queue
{
public:
queue(){front=NULL;rear=NULL;}
~queue(){while(front)deque();}
void deque(Object obj)
{
node<Object> *ptr=new node<Object>(obj,NULL);
if(rear)
rear=rear->next=ptr;
else
front=rear=ptr;
}
Object deque()
{
Object temp=front->data;
node<Object> *ptr=front;
if(front->next==NULL)
front=rear=NULL;
else
front=front->next;
delete ptr;
return temp;
}
private:
node<Object> *front;
node<Object> *rear;
}

8.使用由vector作为基本的数据结构的循环数组高效地实现队列类。

template<typename Object>
class queue
{
public:
queue(int s):maxSize(s),front(0),rear(0){elements.resize(maxSize);}
queue(){maxSize=100;front=0;rear=0;elements.resize(maxSize);}
~queue(){while(front!=rear) deque();}
void enque(Object obj)
{
if(!full())
{
elements[rear]=obj;
rear=(rear+1)%maxSize;
}
}
Object deque()
{
Object temp;
if(!empty())
{
temp=elements[front];
front=(front+1)%maxSize;
return temp;
}
}
bool empty(){return front==rear;}
bool full(){return (rear+1)%maxSize==front;}
private:
int front,rear;
int maxSize;
vector<Object> elements;
}

http://blog.csdn.net/nomasp

0
0 收藏

0 评论
0 收藏
0