线性表——单链表(C++)
)
前言：此文章是介绍线性表中单链表的实现，参考视频数据结构与算法——第3周01--2.5线性表的链式表示和实现1--链表概念_哔哩哔哩_bilibili
视频里面实现基本是c语言和c++混合，此文章将视频中代码所有用c++进行重写，里面涉及到许多c++知识，如果还没有这方面知识，可以查阅对应博客后，再进行阅读！
目录
链表的特性：
1 数据准备
2 初始化单链表
3 销毁单链表
4 清空链表
5 获取链表长度
6 获取指定位置单链表的数据
7 获取指定数据单链表的位置
8 在指定位置插入数据
9 删除指定位置的元素
10 创建固定长度的单链表
11 打印单链表所有数据
12 主程序测试
整个代码
链表的特性：
| 链表 | |
|---|---|
| 存储空间 | 动态分配，不会出现空间闲置或者溢出 |
| 存储密度 | 存储密度小于1，要借助指针域来表示元素之间的逻辑关系 |
| 存取元素 | 顺序存取，访问某位置的元素的时间复杂度为O(n) |
| 插入、删除 | 不需要移动元素，只需要改变指针位置，继而改变结点之间的链接关系。时间复杂度O(1) |
| 适用情况 | 1.长度变化较大 2.频繁的插入和删除 |
1 数据准备
#include <iostream>
#include <string>using namespace std;class Stuedents
{
public:string _mane;string _num;int _score;Stuedents();//初始化bool operator==(Stuedents& s);//运算符重载friend istream& operator>>(istream &is, Stuedents& s);friend ostream& operator<<(ostream &os, Stuedents& s);
};Stuedents::Stuedents()
{_mane = "";_num = "";int _score = 0;
}
//运算符重载
bool Stuedents::operator==(Stuedents& s)
{if (_mane == s._mane && _num == s._num && _score == s._score){return true;}else{return false;}
}
istream& operator>>(istream &is, Stuedents& s)
{cout << "name：";is >> s._mane;cout << "num：";is >> s._num;cout << "score：";is >> s._score; return is;
}
ostream& operator<<(ostream &os, Stuedents& s)
{cout << "name：" << s._mane << " num：" << s._num << " score：" << s._score << endl;return os;
}typedef Stuedents ElemType;class Lnode
{
public:ElemType data;//结点的数据域Lnode* next;//结点的指针域
private:};class LinkList :public Lnode
{
public:Lnode* head;//头结点LinkList();//初始化单链表~LinkList();//销毁单链表bool ListIsEmpty();//判断链表是否为空void ListClear();//清空链表int ListLength();//获取链表长度bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据bool ListDelete(int i);//删除指定位置的元素void ListCreate(int i);//头插法：创建固定长度的单链表void ListCreate(int i,int);//尾插法：创建固定长度的单链表void ListPrint();//打印单链表所有数据
};2 初始化单链表
//初始化单链表
LinkList::LinkList()
{head = new Lnode;head->next = nullptr;//头结点置空
}3 销毁单链表
//销毁单链表
LinkList::~LinkList()
{Lnode *p;while (head != nullptr){p = head;head = p->next;delete p;}
}4 清空链表
//清空链表
void LinkList::ListClear()
{Lnode *p, *q;p = head->next;while (p != nullptr)//一直循环到表尾{q = p->next;delete p;p = q;}head->next = nullptr;//头结点指针域置空
}5 获取链表长度
//获取链表长度
int LinkList::ListLength()
{Lnode *p;p = head->next;int length = 0;while (p != nullptr){length++;p = p->next;}return length;
} 6 获取指定位置单链表的数据
//获取指定位置单链表的数据
bool LinkList::ListGetElem(int i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr && temp <= i){if (temp == i){e = p->data;return true;}p = p->next;temp++;}return false;
}7 获取指定数据单链表的位置
//获取指定数据单链表的位置
bool LinkList::ListLocateElem(int& i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr){if (e == p->data){i = temp;return true;}temp++;p = p->next;}return false;
}8 在指定位置插入数据
//在指定位置插入数据
bool LinkList::ListInsertElem(int i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr){if (temp == i){break;}temp++;p = p->next;}if (temp >= i)//找到数据位置,插入新数据{Lnode *q = new Lnode;q->data = e;q->next = p->next;p->next = q;return true;}else{return false;}
}9 删除指定位置的元素
//删除指定位置的元素
bool LinkList::ListDelete(int i)
{Lnode *p,*q;p = head->next;int temp = 1;while (p != nullptr){if (temp == i){break;}temp++;p = p->next;}if (temp >= i)//找到数据位置，删除数据{q = p->next;p->next = q->next;delete q;return true;}else{return false;}
}10 创建固定长度的单链表
void LinkList::ListCreate(int i)
{Lnode *p,*q;p = head;int temp = 1;while (temp <= i){q = new Lnode;cin >> q->data;q->next = p->next;//插入到表头p->next = q;temp++;}
}
//尾插法：创建固定长度的单链表
void LinkList::ListCreate(int i, int)
{Lnode *p, *q;p = head;int temp = 1;while (temp <= i){q = new Lnode;cin >> q->data;q->next = nullptr;p->next = q;//插入到表尾p = q;//p指向新的尾节点temp++;system("cls");}
}11 打印单链表所有数据
//打印单链表所有数据
void LinkList::ListPrint()
{Lnode *p;p = head->next;while (p != nullptr){cout << p->data;p = p->next;}
}12 主程序测试
void Show_Menu()
{cout << "****************************************************" << endl;cout << "1: ListCreate 2: ListDelete 3: ListInsertElem" << endl;cout << "4: ListLength 5: ListGetElem 6: ListPrint" << endl;cout << "****************************************************" << endl;
}int main()
{LinkList L;//测试区域ElemType E,E1;E._mane = "张三";E._num = "11";E._score = 88;int num = 1;while (true){//进行菜单显示Show_Menu();int select = 0;cout << "请输入你想操作功能的编号： ";cin >> select;switch (select){case 0: //退出管理程序cout << "欢迎下次使用！" << endl;cout << endl;return 0;case 1:L.ListCreate(2);break;case 2:L.ListDelete(1);break;case 3:L.ListInsertElem(1, E);break;case 4:cout<<L.ListLength()<<endl;break;case 5:L.ListGetElem(num, E1);cout << E1 << endl;break;case 6:L.ListPrint();break;default://输入错误cout << endl;cout << "输入错误，请输入正确的功能编号!!!" << endl;cout << endl;break;}system("pause");system("cls");}system("pause");return 0;
}整个代码
//2 单链表
#include <iostream>
#include <string>using namespace std;class Stuedents
{
public:string _mane;string _num;int _score;Stuedents();//初始化bool operator==(Stuedents& s);//运算符重载friend istream& operator>>(istream &is, Stuedents& s);friend ostream& operator<<(ostream &os, Stuedents& s);
};Stuedents::Stuedents()
{_mane = "";_num = "";int _score = 0;
}
//运算符重载
bool Stuedents::operator==(Stuedents& s)
{if (_mane == s._mane && _num == s._num && _score == s._score){return true;}else{return false;}
}
istream& operator>>(istream &is, Stuedents& s)
{cout << "name：";is >> s._mane;cout << "num：";is >> s._num;cout << "score：";is >> s._score; return is;
}
ostream& operator<<(ostream &os, Stuedents& s)
{cout << "name：" << s._mane << " num：" << s._num << " score：" << s._score << endl;return os;
}typedef Stuedents ElemType;class Lnode
{
public:ElemType data;//结点的数据域Lnode* next;//结点的指针域
private:};class LinkList :public Lnode
{
public:Lnode* head;//头结点LinkList();//初始化单链表~LinkList();//销毁单链表bool ListIsEmpty();//判断链表是否为空void ListClear();//清空链表int ListLength();//获取链表长度bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据bool ListDelete(int i);//删除指定位置的元素void ListCreate(int i);//头插法：创建固定长度的单链表void ListCreate(int i,int);//尾插法：创建固定长度的单链表void ListPrint();//打印单链表所有数据
};
//初始化单链表
LinkList::LinkList()
{head = new Lnode;head->next = nullptr;//头结点置空
}
//销毁单链表
LinkList::~LinkList()
{Lnode *p;while (head != nullptr){p = head;head = p->next;delete p;}
}
//判断链表是否为空
bool LinkList::ListIsEmpty()
{if (head->next == nullptr){return true;}else{return false;}
}
//清空链表
void LinkList::ListClear()
{Lnode *p, *q;p = head->next;while (p != nullptr)//一直循环到表尾{q = p->next;delete p;p = q;}head->next = nullptr;//头结点指针域置空
}
//获取链表长度
int LinkList::ListLength()
{Lnode *p;p = head->next;int length = 0;while (p != nullptr){length++;p = p->next;}return length;
}//获取指定位置单链表的数据
bool LinkList::ListGetElem(int i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr && temp <= i){if (temp == i){e = p->data;return true;}p = p->next;temp++;}return false;
}//获取指定数据单链表的位置
bool LinkList::ListLocateElem(int& i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr){if (e == p->data){i = temp;return true;}temp++;p = p->next;}return false;
}//在指定位置插入数据
bool LinkList::ListInsertElem(int i, ElemType &e)
{Lnode *p;p = head->next;int temp = 1;while (p != nullptr){if (temp == i){break;}temp++;p = p->next;}if (temp >= i)//找到数据位置,插入新数据{Lnode *q = new Lnode;q->data = e;q->next = p->next;p->next = q;return true;}else{return false;}
}//删除指定位置的元素
bool LinkList::ListDelete(int i)
{Lnode *p,*q;p = head->next;int temp = 1;while (p != nullptr){if (temp == i){break;}temp++;p = p->next;}if (temp >= i)//找到数据位置，删除数据{q = p->next;p->next = q->next;delete q;return true;}else{return false;}
}
//头插法：创建固定长度的单链表
void LinkList::ListCreate(int i)
{Lnode *p,*q;p = head;int temp = 1;while (temp <= i){q = new Lnode;cin >> q->data;q->next = p->next;//插入到表头p->next = q;temp++;}
}
//尾插法：创建固定长度的单链表
void LinkList::ListCreate(int i, int)
{Lnode *p, *q;p = head;int temp = 1;while (temp <= i){q = new Lnode;cin >> q->data;q->next = nullptr;p->next = q;//插入到表尾p = q;//p指向新的尾节点temp++;system("cls");}
}//打印单链表所有数据
void LinkList::ListPrint()
{Lnode *p;p = head->next;while (p != nullptr){cout << p->data;p = p->next;}
}
//bool ListIsEmpty();//判断链表是否为空
//void ListClear();//清空链表
//int ListLength();//获取链表长度
//bool ListGetElem(int i, ElemType &e);//获取指定位置单链表的数据
//bool ListLocateElem(int& i, ElemType &e);//获取指定数据单链表的位置
//bool ListInsertElem(int i, ElemType &e);//在指定位置插入数据
//bool ListDelete(int i);//删除指定位置的元素
//void ListCreate(int i);//头插法：创建固定长度的单链表
//void ListCreate(int i, int);//尾插法：创建固定长度的单链表
//void ListPrint();//打印单链表所有数据
void Show_Menu()
{cout << "****************************************************" << endl;cout << "1: ListCreate 2: ListDelete 3: ListInsertElem" << endl;cout << "4: ListLength 5: ListGetElem 6: ListPrint" << endl;cout << "****************************************************" << endl;
}int main()
{LinkList L;//测试区域ElemType E,E1;E._mane = "张三";E._num = "11";E._score = 88;int num = 1;while (true){//进行菜单显示Show_Menu();int select = 0;cout << "请输入你想操作功能的编号： ";cin >> select;switch (select){case 0: //退出管理程序cout << "欢迎下次使用！" << endl;cout << endl;return 0;case 1:L.ListCreate(2);break;case 2:L.ListDelete(1);break;case 3:L.ListInsertElem(1, E);break;case 4:cout<<L.ListLength()<<endl;break;case 5:L.ListGetElem(num, E1);cout << E1 << endl;break;case 6:L.ListPrint();break;default://输入错误cout << endl;cout << "输入错误，请输入正确的功能编号!!!" << endl;cout << endl;break;}system("pause");system("cls");}system("pause");return 0;
}