用C++实现了一个链表类，附上可执行代码
本帖最后由 爱学习520 于 2020-8-10 21:33 编辑上午发了一个Vector类，昨天做了一天，即可动态扩容的数组，今天做了一个链表，刚刚写完链表类，附上链表类的代码和main的测试案例，有什么可以优化的地方欢迎提出来，共同进步。明天接着写，争取把二叉搜索树写完
链表LinkList类
#include<iostream>
using namespace std;
#define Index_Error -1 //索引错误
template<class T_ELE>
class LinkList
{
//私有结构体、函数
private:
typedef struct Node
{
T_ELE data;
struct Node* pNext;
}NODE,*PNODE;
//以下的索引都是从1开始的，而非0
PNODE GetIndexPreviousNode(int index)
{
PNODE p = pHead->pNext;
//因为下面的for循环是考虑index从2开始的，所以这里考虑只有一个结点的情况
if (index == 1)
return pHead;
for (int i = 0; i < index -2; i++)
p = p->pNext;
return p;
}
PNODE GetIndexCurrentNode(int index)
{
PNODE p = pHead->pNext;
for (int i = 0; i < index - 1; i++)
p = p->pNext;
return p;
}
PNODE GetIndexNectNode(int index)
{
PNODE p = pHead->pNext;
for (int i = 0; i < index ; i++)
p = p->pNext;
return p;
}
//私有成员
private:
PNODE pHead;
PNODE pTail;
int Length;
//构造、析构函数
public:
LinkList() :pHead (nullptr),pTail(nullptr),Length(0)
{
//申请一块空的节点，仅作为后续使用方便
pHead =pTail= new NODE;
pHead->pNext = nullptr;
pTail->pNext = nullptr;
}
~LinkList()
{
Clear();
}
//链表类的函数功能
public:
//向当前链表插入元素
void Insert(T_ELE Element)
{
//申请新空间，存放元素
PNODE cur = new NODE;
cur->data = Element;
//将新节点连接到之前的结点上
pTail->pNext = cur;
cur->pNext = nullptr;
//修改类成员其他对应的参数
pTail = cur;
Length++;
}
//向指定索引的位置插入元素
int Insert(int index,T_ELE Element)
{
//判断是否在正确区间
if (index<1 || index>Length + 1)
{
cout << index << "不在该链表区域，插入失败！！！" << endl;
return Index_Error;
}
//新申请一块空间
PNODE pNew=new NODE;
pNew->data = Element;
//插入操作
PNODE temp = GetIndexPreviousNode(index)->pNext;
GetIndexPreviousNode(index)->pNext=pNew;
pNew->pNext = temp;
//其他对应的成员值的修改
Length++;
}
//向指定索引位置删除元素
int Delete(int index)
{
//判断删除区间是否有误
if (index<1 || index>Length)
{
cout << index << "不在链表区域，删除失败！！！" << endl;
return -1;
}
//删除操作
PNODE temp = GetIndexPreviousNode(index)->pNext;
GetIndexPreviousNode(index)->pNext = GetIndexPreviousNode(index)->pNext->pNext;
delete temp;
//修改类成员对应的值
Length--;
}
//判断链表是否为空
bool IsEmpty()
{
if (pHead->pNect == nullptr)
{
cout << "链表为空" << endl;
return false;
}
return true;
}
//清除链表
void Clear()
{
PNODE p= pHead->pNext;
for (int i = 0; i < Length; i++)
{
PNODE temp = p->pNext;
delete p;
p = temp;
}
//修改对应的成员变量值
Length = 0;
}
//遍历链表
void Traverse()
{
PNODE p=pHead->pNext;
for(int i=0;i<Length;i++,p=p->pNext)
cout << p->data << endl;
}
};
main测试LinkList类，测试用例
#include "LinkList.cpp"
//测试LinkList
int main()
{
LinkList<int> p;
p.Insert(1);
p.Insert(2);
p.Insert(3);
p.Insert(4);
p.Insert(5);
p.Insert(6);
p.Insert(7);
//插入测试,以下每行分开测试，不然链表长度增加后失去测试效果
cout << "插入测试开始......" << endl;
//p.Insert(0, 520);
//p.Insert(1, 520);
//p.Insert(4, 520);
//p.Insert(8, 520);
//p.Insert(9, 520);
//测试删除
//p.Delete(0);
//p.Delete(1);
//p.Delete(4);
//p.Delete(7);
//p.Delete(8);
p.Traverse();
}
页:
[1]