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++ , 3319 阅读

书中用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

seo 说:
2021年11月03日 07:44

Has anyone heard of this door company? I am really in need of a barn door wall mounted sliding hardware for my renovation. Would gladly appreciate it if someone can check https://caldwells.com/interior-doors/glass-doors link to their site

anonymous 说:
2023年7月28日 05:31

I invite you to the page where     see how much we have in common. Wildlife Removal Kissimmee

anonymous 说:
2023年8月04日 23:44

I wrote about a similar issue, I give you the link to my site.  Wildlife Removal Orlando

anonymous 说:
2023年8月04日 23:46

Within this webpage, you'll see the page, you need to understand this data. Oviedo Squirrel Removal

Cheap Windows VPS Eu 说:
2023年8月29日 23:38

Welcome to CaVPS Host, your destination for the <a href="https://cavpshost.com/ "> cheapest Windows Server hosting </a> solutions! With our affordable plans and top-notch services, we guarantee a seamless hosting experience for your website or application. At CaVPS Host, we understand the importance of cost-effective solutions without compromising on quality. That's why we offer the cheapest Windows Server hosting options available in the market. Our prices are designed to fit your budget, making it easy for small businesses, startups, and individuals to establish their online presence without breaking the bank.

Cheapest windows ser 说:
2023年8月29日 23:40

Welcome to CaVPS Host, your destination for the cheapest Windows Server hosting solutions! With our affordable plans and top-notch services, we guarantee a seamless hosting experience for your website or application. At CaVPS Host, we understand the importance of cost-effective solutions without compromising on quality. That's why we offer the cheapest Windows Server hosting options available in the market. Our prices are designed to fit your budget, making it easy for small businesses, startups, and individuals to establish their online presence without breaking the bank.


登录 *


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