4.替换空格
6,23,39二叉树(1) 打印,深度,重建 Binary Search Tree (1)

5. 逆序打印单向链表 Print linked list reversely using C++ class implementation

Author posted @ 2013年10月03日 14:20 in 剑指Offer with tags c++ , 2925 阅读

书中用struct实现了节点(node):

struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};

然后用ListNode **head表示链表的头。

个人不喜欢这样表示。我相信现在应该没有多少人愿意去看有“指针的指针”的程序。一个程序中出现指针是很正常的,但是出现“指针的指针”就很讨厌了。属于overuse of pointers。不仅容易出错而且降低程序可读性。还有一点就是这样表示链表明显能看出有C-style。没有充分发挥C++语言良好的封装性。我没用书上的例程。参考了[1]用class实现了list。(注意到[1]中的代码有bug:如果用原程序中的Delete函数从头开始删除节点,那么就会产生segmentation fault)。

class Node{
    int data; 
    Node* next;
public:
    Node(){};
    void SetData(int aData) {data = aData;}
    void SetNext(Node* aNext){ next = aNext;}
    int GetData(){ return data;}
    Node* GetNext() {return next;}
};


class List{
    Node *head;
public:
    List() {head = NULL;}
    void Print();
    void Append(int _data);
    void Delete(int _data);
    void PrintReversely();
};

我参考了[2]重新写了List::Delete(int) 函数如下:

void List::Delete(int _data){ 
    // empty list
    if(head == NULL)
	return;
   
    Node* ToBeDeleted = NULL;
    if(head->GetData() == _data){
	ToBeDeleted = head;
    	head = head->GetNext();
    }else{
	// create a copy of list head pointer
	Node* ptr = head;
	while(ptr->GetNext() != NULL){
	    if(ptr->GetNext()->GetData() == _data ){
		// ptr --> [ptr.next] --> ...
		Node* tmp = ptr->GetNext()->GetNext();
		ToBeDeleted = ptr->GetNext();
		ptr->SetNext(tmp);
		break;
	    }else{
		ptr = ptr->GetNext();
	    }
	}	 
    }
    if(ToBeDeleted != NULL){
	delete ToBeDeleted; // free the memory it pointed to
	ToBeDeleted = NULL; //point the dangling ptr to null
    }
}

在删除一个指针时,为避免内存泄露,要首先进行delete操作释放内存,此时该指针变为dangling pointer。然后应将此迷途指针重置为NULL.[3][4]

最后逆序打印链表的函数是照着书里的思路来的。用STL中的stack实现:

void List::PrintReversely(){
    stack<Node*> nodes;
    Node* ptr = head;
    if(ptr==NULL){
	cout<<" Empty List"<<endl;
	return;
    }

    while(ptr!=NULL){
	nodes.push(ptr);
	ptr= ptr->GetNext();
    }
    cout<<"NULL ";
    while(!nodes.empty()){
	Node* tmp = nodes.top();
	cout<<" <-- ";
	cout<<tmp->GetData();
	nodes.pop();
    }
    cout<<endl;
}

完整程序在:

git clone https://github.com/zhutiti/Hehaitao.git

参考:

[1] C++ singly linked list: http://login2win.blogspot.com/2008/07/c-singly-linked-lists.html

[2] How do I delete a node from linked list http://stackoverflow.com/questions/3732399/how-do-i-delete-a-node-from-linked-list-c

[3] C++ deleting a pointer http://stackoverflow.com/questions/13223399/c-deleting-a-pointer

[4] Dangling pointer - Wiki http://en.wikipedia.org/wiki/Dangling_pointer

merckseo 说:
2021年10月10日 08:16

Best Social Plan is the most trusted company for providing social media marketing services. Within some years it has gained popularity as a reliable company to its customers. This company is now managing its activity successfully. It is proved number one company by its quality services. It is noticed that more and more customers are showing their intention to take service from this company. Best Social Plan


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter