剑指offer之C++语言实现链表（两种删除节点方式）
【摘要】 1 问题
用C++语言实现链表
2 代码实现
#include <iostream>#include <stdlib.h> using namespace std; class List{public: List(); ~List(); List*...
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
头指针是指向这块内存的地址，如果我们用指针变量保存了，然后这个指针变量也指向了这里，用指针变量去操作后，然后头指针也是指向这里，后面数据的指向也会改变
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/86516967
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）