剑指offer之C++语言实现链表(两种删除节点方式)

时间:2021-05-19

1问题

用C++语言实现链表

2代码实现

#include <iostream>#include <stdlib.h>using namespace std;class List{public: List(); ~List(); List* createNode(int value);//创建节点 bool insertNode(List *node);//插入节点 void printList();//打印节点 bool deleteNode(List *node);//删除节点不移动头节点 bool deleteNode1(List *node);//删除节点移动头节点 int listSize();//长度 void printNode();//打印但前的value void freeList();//释放链表private: int value; List *head; List *next;};bool List::deleteNode(List *node){ if (node == NULL) { std:cout << "node is NULL" << std::endl; return false; } if (head == NULL) { std::cout << "head is NULL" << std::endl; return false; } //如果node等于head if (head == node) { head = head->next; } List *p = head; while (p->next != NULL) { if (p->next == node) { p->next = p->next->next; return true; } p = p->next; } return false; }bool List::deleteNode1(List *node){ if (node == NULL) { std:cout << "node is NULL" << std::endl; return false; } if (head == NULL) { std::cout << "head is NULL" << std::endl; return false; } //如果node等于head if (head == node) { head = head->next; } List *p = head; while (head->next != NULL) { if (head->next == node) { head->next = head->next->next; std::cout << "delete node success head->value" << head->value << std::endl; //这里要记得把头节点的指针移动最后还原,这里的头节点是保存在这个类里面,改变了就是改变了 //如果这里是把head作为参数传递,最后head会被销毁那么不需要移动头指针 head = p; return true; } //注意,这里由于head是成员变量,改变了就是改变了,所以需要最后重新指定 head = head->next; } std::cout << "delete node fail head->value" << head->value << std::endl; //这里要记得把头节点的指针移动最后还原,这里的头节点是保存在这个类里面,改变了就是改变了 //如果这里是把head作为参数传递,最后head会被销毁那么不需要移动头指针 head = p; return false; }List::List(){ value = 0; head = NULL; next = NULL;}List::~List(){ delete head; delete next;}List* List::createNode(int value){ List *list = NULL; list = new List(); if (list) { list->value = value; return list; } return NULL;}bool List::insertNode(List *node){ node->next = head; head = node; return true; }void List::printList(){ if (head == NULL) { std::cout << "head is NULL" << std::endl; return; } List *p = head; while (p != NULL) { std::cout << p->value << std::endl; p = p->next; } return; }void List::printNode(){ std::cout << value << std::endl; }int List::listSize(){ if (head == NULL) { std::cout << "head is NULL" << std::endl; return 0; } int len = 0; List *p = head; while (p != NULL) { p = p->next; ++len; } return len;}void List::freeList(){ if (head == NULL) { std::cout << "head is NULL" << std::endl; return; } List *p; while (head != NULL) { p = head; head = head->next; free(p); }}int main(){ List list; List *list1 = list.createNode(5); list.insertNode(list1); List *list2 = list.createNode(6); list.insertNode(list2); List *list3 = list.createNode(1); list.insertNode(list3); List *list4 = list.createNode(3); list.insertNode(list4); List *list5 = list.createNode(2); list.insertNode(list5); list.printList(); std::cout << "list size is " << list.listSize() << std::endl; std::cout << "-----------开始删除节点值为3的节点" << std::endl; list.deleteNode1(list4); list.printList(); std::cout << "list size is " << list.listSize() << std::endl; list.freeList(); list.printList(); return 0; }

3 运行结果

2
3
1
6
5
list size is 5
-----------开始删除节点值为3的节点
delete node success head->value2
2
1
6
5
list size is 4
head is NULL

4小结

很明显用C语言实现,我们习惯在外面搞个头结点,然后用C++实现,我们直接在类的里面放一个head指针,然后我们在增加节点的时候我们会把head进行移动,放在最前面,所以后面的 便利和删除操作等最好是不要动head的位置了,因为head动了,下次便利就有问题,如果删除函数移动了head,我们最后需要复原head

比如我们的头指针尽量不要移动,我们可以用一个指针变量来保存这个head指针,然后我们移动保存的指针变量,同时把保存的指针变量在一些情况下改变下一个指向的指针,那么我们下次便利head也是生效的,这样保证了头指针不被污染

比如下面的例子

#include <stdio.h>void change(char *a){ *(a + 1) = 's';}int main(){ char value[10] = "chenyu"; change(value); printf("value is %s\n", value); return 0;}#include <stdio.h>void change(char *a){ char *p = a; *(p + 1) = 's';}int main(){ char value[10] = "chenyu"; change(value); printf("value is %s\n", value); return 0;}

其实最后的结果都是一样,csenyu

头指针是指向这块内存的地址,如果我们用指针变量保存了,然后这个指针变量也指向了这里,用指针变量去操作后,然后头指针也是指向这里,后面数据的指向也会改变

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章