一直以来，对于数据结构都是后怕，但还是要啃下这骨头的：
#pragma once/*
* Copyright (c) 侯文斌
* All rights reserved.
*
* 作 者：houwenbin1986@gmail.com
* 摘 要：链表的操作
*///带头节点的链表
class LinkedList
{
struct Node
{
public:
int data;
Node* prev;
Node* next;
public:
Node(){
data = https://www.it610.com/article/-1;
prev = nullptr;
next = nullptr;
}
};
public:
LinkedList();
~LinkedList();
public:
void Reset();
bool isEmpty();
void Insert(int data, int key=-1);
void Delete(int data);
void Modify(int key, int data);
Node* Find(int data);
void Print();
//打印链表private:
Node* head;
Node* tail;
};
#include "LinkedList.h"
#include LinkedList::LinkedList()
{
head = new Node();
std::cout << sizeof(head) << " " << sizeof(Node) << std::endl;
//x64指针8字节 tail = head;
//增加尾指针，方便追加
}LinkedList::~LinkedList()
{
Reset();
if (head){
delete head;
head = nullptr;
}
tail = nullptr;
}void LinkedList::Reset()
{
Node* pNode = head->next;
while (pNode)
{
Node* pTemp = pNode;
pNode = pNode->next;
//注意顺序！！！
delete pTemp;
pTemp = nullptr;
}
}bool LinkedList::isEmpty()
{
if (head && head->next == nullptr){
return true;
}
return false;
}void LinkedList::Insert(int data, int key)
{
Node* pTemp = tail;
if (key == -1){//追加
pTemp = tail;
}
else {//指定位置
pTemp = Find(key);
pTemp->prev = nullptr;
//重置标识
} Node* pNew = new Node();
//新增节点
pNew->data = https://www.it610.com/article/data;
pNew->next = nullptr;
if (key == -1){//追加
pTemp->next = pNew;
tail = pNew;
//尾指向最新节点
}
else{//插入
pNew->next = pTemp->next;
pTemp->next = pNew;
}
}void LinkedList::Delete(int data)
{
Node* pNode = Find(data);
if ( pNode ){
//前一个位置怎么找，查找时通过pNode->prev返回
pNode->prev->next = pNode->next;
//删除操作
//回收空间
delete pNode;
pNode = nullptr;
}
}void LinkedList::Modify(int key, int data)
{
Node* pNode = Find(key);
if (pNode){
pNode->data = https://www.it610.com/article/data;
pTemp->prev = nullptr;
//重置标识
}
}LinkedList::Node* LinkedList::Find(int data)
{
Node* pTemp = head->next;
Node* pPrev = head;
while ( pTemp )
{
if (pTemp->data =https://www.it610.com/article/= data){
break;
}
pPrev = pTemp;
pTemp = pTemp->next;
}
pTemp->prev = pPrev;
//记录该节点前一节点
return pTemp;
}void LinkedList::Print()
{
Node* pTemp = head->next;
while ( pTemp )
{
std::cout << pTemp->data << " ";
pTemp = pTemp->next;
}
std::cout << std::endl;
} int main(void)
//链表的操作
std::cout << "-----链表操作演示-----" << std::endl;
LinkedList directList;
std::cout << sizeof(directList) << " empty:" << directList.isEmpty() << std::endl;
directList.Insert(1);
directList.Insert(3);
directList.Insert(5);
directList.Insert(7);
std::cout << "empty:" << directList.isEmpty() << std::endl;
directList.Print();
directList.Insert(10,3);
//在节点3后面添加10
directList.Print();
directList.Modify(7,9);
//修改节点
directList.Print();
directList.Delete(5);
//删除节点
directList.Print();
system("pause");
return 0;
}
文章图片
【纯手工打造C++单链表，实现增删改查等基本功能】
