线性表--单链表的基本操作(对小白友好)

发布时间:2024年01月21日


??以下的单链表都是带头结点的单链表。

1.单链表的定义

??1.LinkList 强调这是一个单链表。
??2.LNode* 强调这是一个结点。

typedef struct LNode {
	int data;//数据与
	struct LNode* next;//指针域
}LNode,*LinkList;
/*
  LinkList 强调这是一个单链表
  LNode*   强调这是一个结点
*/

左边数据域,右边指针域!!!
在这里插入图片描述

2.单链表的初始化

bool InitList(LinkList& L)
{
	L = (LNode*)malloc(sizeof(LNode));//分配一个头结点
	if (L == NULL)
		return false;
	L->next = NULL;
	return true;
}

在这里插入图片描述

3.给单链表添加元素

尾插法

??解释说明:当我们进行尾插法时:例如插入数据顺序为1,2,3,4,5。那么在单链表中的存储数据也为1,2,3,4,5。

LinkList List_TailInsert(LinkList& L)
{
    int e = 0;
    LNode* s, * r = L;     // r为表尾指针
	cout << "输入你要插入的元素:";
	cin >> e;
    while (e != 9999) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        r->next = s;
        r = s;
		cout << "输入你要插入的元素:";
		cin >> e;
    }
    r->next = NULL;
    return L;
}

在这里插入图片描述

头插法

??解释说明:当我们进行头插法时:例如插入数据顺序为1,2,3,4,5。那么在单链表中的存储数据为5,4,3,2,1。
??头插法适合链表的逆置。

LinkList List_HeadInsert(LinkList& L)
{
	int e = 0;
	LNode* s;
	cout << "输入你要插入的元素:";
	cin >> e;
	while (e != 9999)
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L->next;
		L->next = s;
		cout << "输入你要插入的元素:";
		cin >> e;
	}
	return L;
}

4.插入元素(在第i个位置插入元素e)

bool ListInsert(LinkList& L, int i, int e)
{
	//判断i值的合理性
	if (i < 1)
		return false;
	LNode* p;//指针p指向当前扫描到的结点
	int j = 0;//当前p指向的第几个结点
	p = L;  //L指向头结点,头结点使第0个元素(不存元素)
	while (p != NULL && j < i - 1)
	{
		//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

在这里插入图片描述

5.删除元素(删除第i个位置的元素)

bool DeleteNode(LinkList& L, int i)
{
	//判断i的值是否合理
	if (i < 1)
		return false;
	LNode* p = L;//指针p指向当前扫描结点
	int j = 0;
	while (p != NULL && j < i-1)
	{
		//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)
		return false;
	if (p->next == NULL)//在第i-1个结点之后无其他结点
		return false;
	LNode* q = p->next; //令q指向被删除结点
	p->next = q->next; //将q结点从链表中断开
	free(q);
	return true;
}

6.改变第i个位置的元素

bool ChangeList(LinkList& L, int i)
{
	int e = 0;
	cout << "输入你要改变的值:";
	cin >> e;
	if (i < 1)
		return false;
	LNode* p = L;
	int j = 0;
	while (p != NULL && j < i)
	{
		p = p->next;
		j++;
	}
	p->data = e;
	return true;
}

7.打印单链表

void PrintList(LinkList L)
{
	while (L->next!= NULL)
	{
		cout << L->next->data << " ";
		L=L->next;
	}
}

8.源代码

??主函数中的函数调用可以根据自己需求进行相应的调整。

int main()
{
	LinkList L;
	//初始化
	InitList(L);
	//给链表输入元素(尾插法)
	List_TailInsert(L);

	给链表输入元素(头插法)
	//List_HeadInsert(L);
	
	// 插入一个元素
	int i = 0,e = 0; 
	cout << "输入你要插入的位置:";
	cin >> i;
	cout << "输入你要插入的元素:";
	cin >> e;
	ListInsert(L, i, e);

	//删除一个元素
	cout << "输入你要删除的位置:";
	cin >> i;
	DeleteNode(L,i);

	//改变第i个位置的元素值
	cout << "输入你要改变的位置:";
	cin >> i;
	ChangeList(L, i);
	//打印全部元素
	PrintList(L);
	return 0;
}

在这里插入图片描述

对你有帮助,点一个关注哟!!!

文章来源:https://blog.csdn.net/m0_63112274/article/details/135734862
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。