SList.h
#include#include using namespace std; typedef int DataType; struct Node { DataType data; struct Node* next; }; class SList { public: SList() :head(nullptr) {} SList(const SList& sl) { head = copySList(sl); } SList& operator=(const SList& sl) { Node* p = copySList(sl); free(); head = p; return *this; } ~SList() { free(); } public: void push_back(const DataType&); void push_front(const DataType&); void pop_back(); void pop_front(); void print()const; Node* find(const DataType&); // 以某值为索引，查找某节点 void insert(Node* p, const DataType&); // 在p结点之后插入一个值 void erase(Node* p); // 删除p结点 private: Node* head; void free() { while (head != nullptr) { Node* next = head->next; delete head; head = next; } head = nullptr; } Node* copySList(const SList& sl) { //SList newsl; //Node* cur = sl.head; //while (cur != NULL) //{ // newsl.push_back(cur->data); // cur = cur->next; //} //return newsl.head; Node ret{ 0,NULL }; Node* node = &ret; Node* cur = sl.head; while (cur != NULL) { Node* tmp = new Node{ cur->data,NULL }; node->next = tmp; node = node->next; cur = cur->next; } return ret.next; } Node* CreatNode(const DataType& x) { Node* newnode = new Node{ x, nullptr }; //newnode->data = x; //newnode->next = nullptr; return newnode; } };
SList.cpp
#include"SList.h"
void SList::push_back(const DataType& x)
{
Node* newnode = CreatNode(x);
if (head == nullptr)
{
head = newnode;
return;
}
Node* cur = head;
while (cur->next != nullptr)
{
cur = cur->next;
}
cur->next = newnode;
}
void SList::push_front(const DataType& x)
{
Node* newnode = CreatNode(x);
newnode->next = head;
head = newnode;
}
void SList::pop_back()
{
assert(head);
if (head->next == nullptr)
{
delete head;
head = nullptr;
}
else
{
Node* cur = head;
while (cur->next->next != nullptr)
{
cur = cur->next;
}
delete cur->next;
cur->next = nullptr;
}
}
void SList::pop_front()
{
Node* tmp = head;
head = head->next;
delete tmp;
}
void SList::print()const
{
if (head == nullptr)
cout << "null" << endl;
else
{
Node* cur = head;
while (cur != nullptr)
{
cout << cur->data << " -> ";
cur = cur->next;
}
cout << "null" << endl;
}
}
Node* SList::find(const DataType& x) // 以某值为索引，查找某节点
{
assert(head);
Node* cur = head;
while (cur != nullptr)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return nullptr;
}
void SList::insert(Node* p, const DataType& x)
{
Node* newnode = CreatNode(x);
assert(p);
newnode->next = p->next;
p->next = newnode;
}
void SList::erase(Node* p)
{
assert(p);
if (head == p)
{
Node* tmp = head->next;
delete head;
head = tmp;
}
{
Node* cur = head;
while (cur->next != p)
{
cur = cur->next;
}
cur->next = cur->next->next;
delete p;
}
}
测试
void test()
{
SList sl1;
sl1.push_back(1);
sl1.push_back(2);
sl1.push_back(3);
sl1.push_back(4);
sl1.push_back(5);
sl1.push_front(6);
sl1.push_front(7);
sl1.push_front(8);
sl1.print();
sl1.pop_back();
sl1.pop_front();
sl1.print();
sl1.insert(sl1.find(6), 66);
sl1.print();
sl1.erase(sl1.find(6));
sl1.print();
SList sl2(sl1);
sl2.push_back(88);
sl2.print();
sl1.print();
sl1 = sl2;
sl1.print();
}
int main()
{
test();
return 0;
}
顺便给出C语言实现的单链表
SList.h
#pragma once #include#include #include typedef int SListDataType; //typedef需要分号结尾 typedef struct SListNode { SListDataType data; //数据 struct SListNode* next; //下一个节点的地址 }SListNode; // 创建一个节点 SListNode* CreatSLTNode(SListDataType x); // 打印一个链表，传入头节点，因为不会更改，所以传一维指针即可。 void PrintSList(SListNode* pnode); // 尾插 void SListPushBack(SListNode** pphead, SListDataType x); // 头插 void SListPushFront(SListNode** pphead, SListDataType x); // 尾删 void SListPopBack(SListNode** pphead); // 头删 void SListPopFront(SListNode** pphead); // 查找某节点 SListNode* SListFind(SListNode* phead, SListDataType x); // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SListDataType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos); //链表的销毁 void SListDestroy(SListNode** phead);
SList.c
#include"SList.h" //单链表
SListNode* CreatSLTNode(SListDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode; //newnode是那个新的节点的地址，内容已经初始化，next为NULL。
}
void PrintSList(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}
void SListPushBack(SListNode** phead, SListDataType x) //phead是头节点地址的地址，*phead即那个节点的指针。
{
SListNode* newnode = CreatSLTNode(x);
if (*phead == NULL)
*phead = newnode;
else
{
SListNode* cur = *phead;
while (cur->next != NULL)
{
cur = cur->next;
}
(*cur).next = newnode;
//cur->next = newnode;
}
}
void SListPushFront(SListNode** pphead, SListDataType x)
{
SListNode* newnode = CreatSLTNode(x);
newnode->next = *pphead;
*pphead = newnode; //一维指针的地址进行解引用。
}
void SListPopBack(SListNode** pphead)
{
//尾删
assert(*pphead); //防止这是一个空链表
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SListNode* cur = *pphead;
while (cur->next->next != NULL)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
//SLTNode* tail = *pphead;
//SLTNode* Pretail = NULL;
//while (tail->next != NULL)
//{
// Pretail = tail;
// tail = tail->next;
//}
//free(tail);
//Pretail->next = NULL;
}
}
void SListPopFront(SListNode** pphead)
{
assert(*pphead); //断言头节点的指针不为空
//SListNode* tmp = (*pphead)->next;
//free(*pphead);
//*pphead = tmp;
SListNode* tmp = *pphead;
*pphead = (*pphead)->next;
free(tmp);
}
SListNode* SListFind(SListNode* phead, SListDataType x)
{
assert(phead); //如果这个结构体指针为空，表明这是一个空链表。
SListNode* cur = phead;//则这个结构体指针不为空，只少有一个节点。
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
void SListInsertAfter(SListNode* pos, SListDataType x)
{
assert(pos);
SListNode* newnode = CreatSLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if(!pos->next) //如果这个是最后一个节点，什么也不做
{
return;
}
else
{
SListNode* tmp = pos->next;
pos->next = pos->next->next;
free(tmp);
tmp = NULL;
}
}
void SListDestroy(SListNode** phead)
{
assert(*phead); //
SListNode* cur = *phead, *next = (*phead)->next;
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
*phead = NULL;
}
