• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-04-09)  算法/数据结构 |   2 条评论  13 
    文章评分 0 次,平均分 0.0

    命题:链表的转置(递归与非递归实现)  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");
    }
    

    递归逆序相邻元素
    单链表逆转(递归&&非递归)

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/512.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享