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

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++;elseiterL2++;}return intersect;}<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.一个有表头结点，没有尾结点，还有一个指向表头结点的指针的单向链表，写一个类包括以下函数： 返回链表的大小， 打印链表， 检测值x是否在链表中， 如果x不在链表中则加入链表， 如果x在链表中则删除它。

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(){eraseList(head);}singleList(const singleList & rhs){eraseList(head);init();*this=rhs;}bool add(Object x){if(contains(x)){return false;}else{Node<Object> *ptr =new Node<Object>(x);ptr->next=head->next;head->next=ptr;theSize++;}return true;}bool remove(Object x){if(!contains(x))return false;else{Node<Object>*ptr=head->next;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(){Node<Object> *ptr=head->next;while(ptr!=NULL){count<<ptr->data<<” “;ptr=ptr->next;}count<<endl;}bool contains(const Object & x){Node<Object> * ptr=head->next;while(ptr!=NULL){if(x==ptr->data)return true;elseptr=ptr->next;}return false;}void init(){theSize=0;head=new Node<Object>;head->next=NULL;}void eraseList(Node<Object> * h){Node<Object> *ptr=h;Node<Object> *nextPtr;while(ptr!=NULL){nextPtr=ptr->next;delete ptr;ptr=nextPtr;}}private:Node<Object> *head;int theSize;};记录沿途的心情。那样的生活才是我想要的。