singlelinklist
2024-10-20 18:05:04
C++实现单链表
阅读先知
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。
可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。
结点中只有一个next指针的链表称为单链表，这是最简单的链表结构。
具体实现
首先定义一个结构体，表示链表的节点
typedef struct Node
{
ElemType data;
struct Node *next;
}LinkList;
建立单链表类
class Mylist
{
private:
LinkList* L;
public:
//初始化一个带头结点的单链表
bool InitList()
{
L = new LinkList;
if (L==NULL)
{
cout << "Not have enough memory!";
return false;
}
L->next = NULL;
return true;
}
bool CreateNode(int size)
{
int i = 0;
ElemType e;
LinkList* p =L;
cout << ">>>>please input "<<size<<" nodes with space to split:";
while(i<size)
{
LinkList* q = new LinkList;
cin >> e;
q->data = e;
q->next = NULL;
p->next = q;
p = q;
i++;
}
return true;
}
void DispList()
{
LinkList* p = L->next;
while (p!=NULL)
{
cout << p->data<<' ';
p = p->next;
}
cout << endl;
}
int ListLength()
{
int i = 0;
LinkList* p = L->next;
while (p!=NULL)
{
++i;
p = p->next;
}
return i;
}
bool ListEmpty()
{
return L->next == NULL;
}
bool GetElem(int site,ElemType &e)
{
int i =0;
LinkList* p = L;
while (i<site && p!=NULL)
{
i++;
p = p->next;
}
if (p == NULL || site == 0)
return false;
else
{
e = p->data;
return true;
}
}
bool LocateElem(int &site,ElemType e)
{
int i = 1;
LinkList* p = L->next;
while (p!= NULL && p->data!=e)
{
i++;
p = p->next;
}
if (p==NULL)
return false;
else
site = i;
return true;
}
//插入元素
bool ListInsert(int site,ElemType e)
{
int i = 0;
LinkList* p = L->next;
while (i < site && p!=NULL)
{
i++;
p = p->next;
}
if (p == NULL)
return false;
else
{
LinkList* q = new LinkList;
q->data = e;
q->next = NULL;
p->next = q;
return true;
}
}
//删除元素
bool ListDelete( int site, ElemType &e )
{
int i = 0;
LinkList* p = L;
while ( i<site-1 && p!=NULL )
{
i++;
p = p->next;
}
if ( NULL == p )
return false;
else
{
LinkList* q = p->next;
if ( NULL == q )
return false;
e = q->data;
p->next = q->next;
delete q;
return true;
}
}
// (带头一起)销毁链表
void DestoryList()
{
LinkList *p, *q;
p = L;
while ( p!=NULL )
{
q = p->next;
delete p;
p = q;
}
}
};
主函数代码
int main()
{
Mylist h;
ElemType e;
int temp=0;
h.InitList();
cout << ">>>>please input the length of linklist:";
cin >> temp;
h.CreateNode(temp);
cout <<"show:";
h.DispList();
cout <<"the length of linklist is:"<<h.ListLength()<<endl;
cout <<"is it empty?"<<h.ListEmpty()<<endl;
cout << ">>>>which element do you want to find:";
cin >> temp;
h.GetElem(temp,e);
cout <<"this element is "<<e<<endl;
cout << ">>>>Which element index do you want to find:";
cin >> temp;
h.LocateElem(temp,temp);
cout <<"this element index is "<<temp<<endl;
return 0;
}
拓展应用
_题目描述：_判断链表是否带环，以及环的入口
- 有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的任意一个节点，这样在链表尾部形成一个环。
主要思想：
- 如果判断一个链表是否存在一个环？设定两个指针slow，fast，均从头指针开始，每次分别前进1步、2步。如果存在环，则两者相遇；如不存在环，fast遇到NULL退出。
- 如果链表存在环，如何找到环的入口点？当fast与slow相遇时，slow肯定没有遍历完链表或者恰好遍历一遍。于是我们从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，则相遇的第一个点为环入口点。
数学解析：
代码部分：
bool findloopport(ElemType &e)
{
LinkList* fast = L;
LinkList* slow = L;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
if (fast == NULL || fast->next == NULL)
return false;
slow = L;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
e = slow->data;
return true;
}
温馨提示：代码可以根据个人习惯编写，本文还有待补缺的地方。。。。
最新文章
- cal 命令
- Visual Studio Code初探
- Repeater的ItemCreated和ItemDataBind的区别
- ulua学习笔记（二）：官方资料及问题解决方案
- 使用HttpClient进行Get方式通信
- java随机生成验证码
- 2017-2018-1 20155215 第九周 加分项 PWD命令的实现
- （Python基础）字典的使用
- 小程序开发--template模板
- nodejs和ionic小助手
- python scrapy爬虫框架概念介绍(个人理解总结为一张图)
- idea中deBug方法
- jstypeof方法判断undefined类型
- solr 6.6 基础环境搭建 (一)
- Xor Sum（HDU4825 + 字典树）
- 170612、web如何项目优化
- Mybatis实现了接口绑定，使用更加方便。
- jenkins邮箱配置以及结合ansible进行批量构建
- 利用COOKIE保存历史浏览商品的一个简单思路
- .NET环境下的DPAPI加密编程