8 单链表---带表头节点

发布时间:2024年01月06日

上节课所学的顺序表的缺点

请添加图片描述
顺序表的最大问题:插入和删除时需要移动大量元素

链式存储的定义

请添加图片描述

链式存储的逻辑结构

请添加图片描述

链表中的基本概念:

请添加图片描述
注意:表头节点并不属于数据元素

单链表图示:

请添加图片描述

把3个需要的结构体定义出来:

请添加图片描述

typdef struct _tag_LinkList{
	LinkListNode header; //指针域
	int length; //单链表的长度
}TLinkList

获取第pos个元素

请添加图片描述
请添加图片描述

插入元素到pos位置

请添加图片描述

请添加图片描述
请添加图片描述
注意:新的链表形成之前,旧的链表不能断

删除元素:

请添加图片描述

请添加图片描述
请添加图片描述
一定要注意:index是从0开始还是从1开始【程序员永恒问题】

代码实现—单链表—带表头节点—头插法

linklist.c

#include "LinkList.h"

typedef struct _tag_LinkList
{
	LinkListNode* header;//头指针
	int length;//单链表的长度
}TLinkList; //类型:即代表头结点,又代表整个单链表

LinkList* LinkList_Create() {
	TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));

	if (ret) {
		ret->length = 0;
		ret->header = NULL;
	}
}

void LinkList_Destory(LinkList* list) {
	free(list);
}

void LinkList_Clear(LinkList* list) {
	((TLinkList*)list)->length = 0;
}

int LinkList_Length(LinkList* list) {
	return ((TLinkList*)list)->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) {
	TLinkList* tll = (TLinkList*)list;
	int i = 0;

	int ret = -1;
	ret = (tll != NULL) && (pos >= 0) && (node != NULL);

	if (ret) {
		LinkListNode* current = (LinkListNode*)tll;

		//移动current指针到pos位置
		for (i=0; (i<pos)&&(current->next!=NULL); i++)
		{
			current = current->next;
		}

		//关键
		node->next = current->next;
		current->next = node;

		tll->length++;
	}

	return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos) {
	TLinkList* tll = (TLinkList*)list;
	LinkListNode* ret = NULL;

	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		LinkListNode* current = (LinkListNode*)tll;

		for (i=0;i<pos;i++)
		{
			current = current->next;
		}

		ret = current->next;
	}

	return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos) {
	TLinkList* tll = (TLinkList*)list;

	LinkListNode* ret = NULL;
	int i = 0;

	if ((tll != NULL) && (pos >= 0) && pos < tll->length) {
		LinkListNode* current = (LinkListNode*)tll;
		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
		current->next = ret->next;

		tll->length--;
	}

	return ret;
}


linklist.h

#pragma once
#pragma once
#include <stdio.h>

typedef void LinkList;
//定义包含指针next的结构体
typedef struct _tag_LinkListNode LinkListNode;
typedef struct _tag_LinkListNode
{
	LinkListNode*  next;
};


/*
该方法用于创建并且返回一个空的线性表
*/
LinkList* LinkList_Create();

/*
该方法用于销毁一个线性表LinkList
*/
void LinkList_Destory(LinkList* list);

/*
该方法用于将一个线性表LinkList中的所有元素清空
使得线性表回到创建时的初始状态
*/
void LinkList_Clear(LinkList* list);

/*
该方法用于返回一个线性表LinkList中的所有元素个数
*/
int LinkList_Length(LinkList* list);

int LinkList_Capacity(LinkList* list);

/*
该方法用于向一个线性表LinkList的pos位置处插入新元素node
返回值为1表示插入成功,0表示插入失败
*/
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

/*
该方法用于获取一个线性表LinkList的pos位置处的元素
返回值为pos位置处的元素,NULL表示获取失败
*/
LinkListNode* LinkList_Get(LinkList* list, int pos);

/*
该方法用于删除一个线性表LinkList的pos位置处的元素
返回值为被删除的元素,NULL表示删除失败
*/
LinkListNode* LinkList_Delete(LinkList* list, int pos);


main.c


#include "LinkList.h"

//普通节点的结构体
struct Value
{
	LinkListNode* header; //指针域
	int v;//数据域
};
int main() {
	int i = 0;
	LinkList* list = LinkList_Create();

	struct Value v1;
	struct Value v2;
	struct Value v3;
	struct Value v4;
	struct Value v5;

	v1.v = 1;
	v2.v = 2;
	v3.v = 3;
	v4.v = 4;
	v5.v = 5;

	//头插法
	LinkList_Insert(list, (LinkListNode*)&v1, 0);
	LinkList_Insert(list, (LinkListNode*)&v2, 0);
	LinkList_Insert(list, (LinkListNode*)&v3, 0);
	LinkList_Insert(list, (LinkListNode*)&v4, 0);
	LinkList_Insert(list, (LinkListNode*)&v5, 0);

	for (i = 0; i < LinkList_Length(list); i++)
	{
	  	struct Value* pv = LinkList_Get(list, i);
		printf("%d\n", pv->v);
	}

	while (LinkList_Length(list) >0)
	{
		struct Value* pv = LinkList_Delete(list, LinkList_Length(list) - 1);
		printf("%d\n", pv->v);
	}

	LinkList_Destory(list);

	return 0;
}

运行结果:
请添加图片描述

尾插法

请添加图片描述

小结:单链表的优点和缺点

请添加图片描述

末尾问题:

请添加图片描述
这也是我想问的!

请添加图片描述
单链表:在选择表头结点和无表头结点的实现方式时,应根据具体的应用场景和需求来考虑。一般而言,表头结点方式更为常见和直观,更容易管理和操作链表但无表头结点的实现方式可能更加节省一些空间

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