单链表逆转(递归&&非递归)

2013年4月9日 由 Creater 留言 »

命题:链表的转置(递归与非递归实现)  A-B-C-D-E  变为 E-D-C-B-A

链表相邻两元素的逆转  A-B-C-D-E 变为  B-A-D-C-E                      A-B-C-D变为B-A-D-C

# include <iostream>
#include <string>
#include <algorithm>
#include <functional>//标准库函数对象头文件
using namespace std;

class CNode {
public:
	CNode():head(NULL){ }
	void reverse();
	void ins(int x);
	void display () const ;
	void diGuiReverse() {Node *p = head;head = diguiReverse(head); p->next = NULL;}
	void diGui3Reverse() {
		head = digui3Reverse(head);
	}
private:
	struct Node {
		int data;
		Node *next;
		Node(int d = 0, Node *n = NULL):data(d), next(n) {}
	};
	Node *head;
	Node* diguiReverse(Node *t);
	Node *digui3Reverse(Node *t);
};
void CNode::display () const {
	Node *node = head;
	while(node !=NULL ){
		//system("pause");
		cout<<node->data<<" ";
		node = node->next;
	}
	cout<<endl<<endl;
	
}
void CNode::reverse(){
	if((head == NULL) ||(head->next == NULL))
		return ;
	Node *p,*q, *r;
	p = head;
	r = head->next;
	q = r;
	while(r!= NULL) {
		r = q->next;
		q->next = p;
		p = q;
		q =r;
	}
	head->next = NULL;
	head = p;
}

void CNode::ins(int x){ 
	Node *p = head;
	Node *node = new Node(x, NULL);
	if(head == NULL)
		head = node;
	else {
		while(p->next!= NULL) {
			p = p->next;
		}
		p->next = node;
	}
	cout<<"Insert a node,the data is "<<x<<endl;
}

CNode::Node* CNode::diguiReverse(Node *t) {//递归逆序链表
	if((t== NULL) ||(t->next == NULL))
		return t;

	Node *p = diguiReverse(t->next);
	t->next->next = t;
	return p;
}

CNode::Node* CNode::digui3Reverse(Node *t) {//递归交换相邻元素
	if((t== NULL) ||(t->next == NULL))
		return t;
	Node *p = t->next;
	Node *q =digui3Reverse(t->next->next);
	t->next->next=t;
	t->next =q;
	return p;
}


int main() {
	CNode List;
	List.ins(1);
	List.ins(2);
	List.ins(3);
	List.ins(4);
	List.ins(5);
	List.ins(6);
	List.ins(7);
	List.ins(8);
	List.ins(9);
	List.ins(10);
	cout<<endl;
	cout<<"原链表"<<endl;
	List.display();
	cout<<"非递归逆转链表"<<endl;
	List.reverse();
	List.display();
	cout<<"递归逆转链表"<<endl;
	List.diGuiReverse();
	List.display();

	//List.diGui2Reverse();
	//List.display();
	cout<<"递归逆转相邻元素后链表"<<endl;
	List.diGui3Reverse();
	List.display();
	system("pause");
}

递归逆序相邻元素
1335578702_8023

广告位

发表评论

你必须 登陆 方可发表评论.