单链表
前置文章:顺序表的代码实现
1、链表的定义
每个结点除了存放数据元素外,还要存储指向下一个结点的指针。
2、链表的特点
- 不要求大片连续空间
- 改变容量方便
- 不可随机存取
- 要耗费一定空间存放指针
3、链式存储结构
//单链表的存储结构
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode,*LinkList;
4、完整实现代码
代码结构:
- 定义单链表结构
- 初始化单链表
- 单链表的取值方法
- 单链表的查找方法
- 单链表的插入方法
- 单链表的删除方法
- 主函数用以测试
代码详情:
#include<iostream>
#include<string>
using namespace std;
/*
单链表(带头结点)
*/
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data;
struct LNode* next;
}LNode,*LinkList;
//初始化 有头结点
Status InitList(LinkList &L)
{
L = new LNode;
L->next = NULL;
return 1;
}
/*
单链表的取值(按位序取值): 时间复杂度O(n)
参数一:要取值的单链表
参数二:要取值的位置
参数三:待保存的对象
注意:成功:返回1;失败:返回0。
*/
Status GetElem(LinkList L,int i,ElemType &e)
{
LNode *p = L->next;
int j = 1;
while (p && j<i)
{
p = p->next;
j++;
}
if (!p || j > i)
{
return 0;
}
e = p->data;
return p->data;
}
/*
单链表的查找(按位序查找): 时间复杂度O(n)
参数一:要查找的单链表
参数二:要查找的数据
注意:成功:返回下标地址;失败:返回NULL。
*/
LNode* LocateElem(LinkList L, ElemType e)//使用Book类型的外号ElemType作为传入参数e的类型,使用int类型的外号Status作为函数的返回值类型
{
LNode* p = L->next;//创建新结点,并指向第一块数据
while (p && p->data!=e)//如果p不为空且data == e,返回p的地址
{
p = p->next;
}
return p;
}
/*
单链表的插入(按位序插入(后插法)): 时间复杂度O(n)
参数一:要插入的单链表
参数二:要插入的位置
参数三:要插入的数据
注意:成功:返回1;失败:返回0。
*/
Status ListInsert(LinkList& L, int i, ElemType e)
{
if (i<1)
{
return 0;
}
LNode* p = L;//创建临时结点指向头结点,头结点不存数据
int j = 0;//记录p指向的是第几个结点,第0个结点为头结点,头结点不存数据,只存地址
while (p && (j<i-1))//循环找到第i-1个结点
{
p = p->next;
j++;
}
if (!p || j>i-1)//如果地址p为NULL就退出,头结点的地址也不为空
{
return 0;
}
LNode* s = new LNode; //创建新结点
s->data = e;//新结点存放新数据e
s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
p->next = s;//p的指针指向新节点s
return 1;
}
/*
单链表的删除(按位序删除): 时间复杂度O(n)
参数一:要删除的单链表
参数二:要删除的位置
注意:成功:返回1;失败:返回0。
*/
Status ListDelete(LinkList& L, int i)
{
LNode* p = L;//创建临时结点指向头结点,头结点不存数据
int j = 0;//记录p指向的是第几个结点,第0个结点为头结点,头结点不存数据,只存地址
while (p->next&&(j<i-1))//循环找到第i-1个结点的前一个结点
{
p = p->next;
j++;
}
if (!(p->next)||(j>i-1))
{
return 0;
}
LNode* q = p->next;//创建新结点q,指向要删除的数据内存地址
p->next = q->next;//p的指针指向q的指针指向的下一个数据地址
delete q;//释放q结点
return 1;
}
int main()
{
LinkList L;
//创建单链表
//CreateList_H(L,5);
//初始化单链表
InitList(L);
//插入单链表
for (int i = 1; i < 6; i++)
{
ListInsert(L, 1, i);
}
//取值
int e;
for (int i = 1; i <= 5; i++)
{
cout << GetElem(L, i, e) << endl;
}
//查找
cout << "5的地址为:" << LocateElem(L, 5) << endl;
//删除
ListDelete(L, 1);
cout << "删除第一个元素5:" << endl;
for (int i = 1; i < 5; i++)
{
cout << GetElem(L, i, e) << endl;
}
return 1;
}
5、知识补充
补充创建单链表的两种方法:前插法和尾插法。还有单链表插入的两种方法:前插法和尾插法。
注:此段知识补充内容,未经本人实践验证,只是遇到了,总结到此处,仅供参考。
相关代码:
/*
前插法创建单链表
*/
//void CreateList_H(LinkList& L, int n)
//{
// L = new LNode;
// L->next = NULL;
// for (int i = 0; i < n; i++)
// {
// LNode* p = new LNode;
// cin >> p->data;
// p->next = L->next;
// L->next = p;
// }
//}
/*
尾插法创建单链表
*/
//void CreateList_R(LinkList& L, int n)
//{
// L = new LNode;
// L->next = NULL;
// LNode* r = L;
// for (int i = 0; i < n; i++)
// {
// LNode* p = new LNode;
// cin >> p->data;
// p->next = NULL;
// r->next = p;
// r = p;
// }
//}
/*
单链表的插入(前插法): 时间复杂度O(1)
参数一:要插入的结点
参数二:要插入的数据
注意:成功:返回1;失败:返回0。
原理:前插法即开辟新结点s,复制p结点的值,然后将数据e存给p结点,再将s的指针指向p的指针指向,p的指针指向s。可谓是偷天换日、原地TP。
*/
Status ListPriorInsert(LNode *p, ElemType e)
{
if (p == NULL)
{
return 0;
}
LNode* s = new LNode;//创建新结点
if (s == NULL)
{
return 0;
}
s->data = p->data;//复制插入的前一个数据到新开辟的空间
p->data = e; //前一个数据存放新数据e
s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
p->next = s;//p的指针指向新节点s
return 1;
}
/*
单链表的插入(后插法): 时间复杂度O(1)
参数一:要插入的结点
参数二:要插入的数据
注意:成功:返回1;失败:返回0。
*/
Status ListNextInsert(LNode* p, ElemType e)
{
if (p == NULL)
{
return 0;
}
LNode* s = new LNode;//创建新结点
if (s == NULL)
{
return 0;
}
s->data = e;//新结点存放新数据e
s->next = p->next;//将p的指针指向的下一个数据地址赋值给新结点s的指针
p->next = s;//p的指针指向新节点s
return 1;
}
6、最后
以上为个人实践总结,如有错误和疏漏的地方,欢迎大佬评论区指正和补充…
觉得写还不错的话,还请点赞、收藏、评论和分享,非常感谢~文章来源:https://www.toymoban.com/news/detail-723168.html
参考文献:文章来源地址https://www.toymoban.com/news/detail-723168.html
- 《数据结构》C 语言版,严为敏 吴伟民编,清华大学出版社,2009.
到了这里,关于【数据结构】单链表完整代码实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!