数据结构之线性表——链表的链式存储（链式描述）注释版

忘是亡心i 2022-05-29 13:21 233阅读 0赞

# ![70][]    #

![70 1][]

# 线性表的链式存储 #

## 1、基本概念 ##

链式存储定义

为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。

![70 2][]     ![70 3][]

//LinkList.h
    #ifndef _LINKLIST_H_
    #define _LINKLIST_H_
    
    
    //节点的指针域
    typedef struct _tag_LinklListNode
    {
    	struct _tag_LinklListNode *next;
    }LinkListNode;
    
    typedef void LinkList;//链表的句柄
    
    //链表的创建
    LinkList* LinkList_Create();
    
    //链表的销毁
    void LinkList_Destroy(LinkList *list);
    
    //链表的清除
    void LinkList_Clear(LinkList *list);
    
    //链表的长度
    int LinkList_Length(LinkList *list);
    
    //链表的插入
    int LinkList_Insert(LinkList *list, LinkListNode* node, int pos);
    
    //获取链表中的元素
    LinkListNode* LinkList_Get(LinkList *list, int pos);
    
    //删除链表中的元素
    LinkListNode* LinkList_Delete(LinkList *list, int pos);
    
    
    #endif

//LinkList.c
    #include "LinkList.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    //头结点定义
    typedef struct _tag_LinkList
    {
    	LinkListNode header;//包含指针域节点
    	int		     length;//头结点自身的信息
    }TLinkList;
    
    //链表的创建
    LinkList* LinkList_Create()
    {
    	int ret = 0;
    	TLinkList *tmp = NULL;
    	//1 申请一个动态内存空间
    	tmp = (TLinkList *)malloc(sizeof(TLinkList));
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkList_Create() malloc:%d\n",ret);
    		return NULL;
    	}
    	//2 初始化链表
    	tmp->header.next = NULL;//链表的头结点的指针域指向NULL
    	tmp->length = 0;
    	return tmp;
    }
    
    //链表的销毁
    //链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
    void LinkList_Destroy(LinkList *list)
    { 
    	int        ret = 0;
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkList_Destroy():%d\n",ret);
    	}
    	free(tmp);//释放头结点空间
    }
    
    //链表的清除
    //链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0  
    void LinkList_Clear(LinkList *list)
    {
    	int        ret = 0;
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;//强制类型转换 把链表接过来
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkList_Clear():%d\n", ret);
    	}
    	tmp->header.next = NULL;
    	tmp->length = 0;
    }
    
    //链表的长度
    int LinkList_Length(LinkList *list)
    {
    	int        ret = 0;
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;//强制类型转换 把链表接过来
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkList_Length():%d\n", ret);
    	}
    	return tmp->length;
    }
    
    //链表的插入
    int LinkList_Insert(LinkList *list, LinkListNode *node, int pos)
    {
    	int           ret = 0;
    	LinkListNode *pCur = NULL;
    	TLinkList *tmp = NULL;//1 缓存链表
    	tmp = (TLinkList *)list;//强制类型转换 把链表接过来
    	if (NULL == tmp||NULL == node || pos < 0)
    	{
    		ret = -1;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    	pCur = &(tmp->header);//2 让当前指针指向头结点
    	for (int i = 0; i < pos&&(pCur->next!=NULL); i++)//3 寻找插入位置前一结点
    	{
    		pCur = pCur->next;
    	}
    	//4 进行连接
    	node->next = pCur->next;//4.第一步连接
    	pCur->next = node;//4.第二步连接
    	tmp->length++;
    	return ret;
    }
    //获取链表中的元素
    LinkListNode* LinkList_Get(LinkList *list, int pos)
    {
    	int           ret = 0;
    	LinkListNode *pCur = NULL;
    	TLinkList *tmp = NULL;//1 缓存链表
    	tmp = (TLinkList *)list;//强制类型转换 把链表接过来
    	if (NULL == tmp || pos < 0)
    	{
    		ret = -1;
    		printf("func err LinkList_Get():%d\n", ret);
    		return ret;
    	}
    	pCur = &(tmp->header);//2 让当前指针指向头结点
    	for (int i = 0; i < pos && (pCur->next != NULL); i++)//3 寻找要获取的位置前一结点
    	{
    		pCur = pCur->next;
    	}
    	return pCur->next;//链表是单向的，n号结点的位置贮存在n-1结点的next域
    }
    
    //删除链表中的元素
    LinkListNode* LinkList_Delete(LinkList *list, int pos)
    {
    	int           ret = 0;
    	LinkListNode *pCur = NULL;
    	LinkListNode *pDel = NULL;
    	TLinkList *tmp = NULL;//1 缓存链表
    	tmp = (TLinkList *)list;//强制类型转换 把链表接过来
    	if (NULL == tmp || pos < 0)
    	{
    		ret = -1;
    		printf("func err LinkList_Delete():%d\n", ret);
    		return ret;
    	}
    	pCur = &(tmp->header);//2 让当前指针指向头结点
    	for (int i = 0; i < pos && (pCur->next != NULL); i++)//3 寻找要获取的位置前一结点
    	{
    		pCur = pCur->next;
    	}
    	//4 缓存要删除的结点
    	pDel = pCur->next;
    	//5 进行删除操作
    	pCur->next = pDel->next;
    	tmp->length--;
    
    	return pDel;
    }

//线性表的链式存储结构实现与设计测试框架.c
    #include "LinkList.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include  <string.h>
    
    
    
    typedef struct _Teacher
    {
    	LinkListNode node;//包含指针域节点
    	//下面是业务域
    	char		name[32];
    	int			age;
    }Teacher;
    
    int main()
    {
    	int ret = 0;
    	Teacher t1, t2, t3;//节点生命周期在这里由main函数管理
    	t1.age = 31;
    	t2.age = 32;
    	t3.age = 33;
    	//1 申请一个空的线性表的链式存储结构
    	LinkList *list = NULL;
    	list = LinkList_Create();
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err LinkList_Create():%d\n",ret);
    		return ret;
    	}
    	//2 插入元素
    	//业务结点 转化为链表的节点
    	ret = LinkList_Insert(list ,(LinkListNode *)&t1,0);
    	if (ret!=0)
    	{
    		ret = -2;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    	ret = LinkList_Insert(list, (LinkListNode *)&t2, 0);
    	if (ret != 0)
    	{
    		ret = -3;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    	ret = LinkList_Insert(list, (LinkListNode *)&t3, 0);
    	if (ret != 0)
    	{
    		ret = -4;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    
    	//遍历链表
    	for (int i = 0; i < LinkList_Length(list); i++)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Get(list,i);
    		if (NULL == tmp)
    		{
    			ret = -5;
    			printf("func err LinkList_Get():%d\n", ret);
    			return ret;
    		}
    		printf("tmp->age:%d\t",tmp->age);
    	}
    
    	//删除链表结点
    	while (LinkList_Length(list))
    	{
    		Teacher *tmp = (Teacher *)LinkList_Delete(list,0);
    		if (NULL == tmp)
    		{
    			ret = -6;
    			printf("func err LinkList_Delete():%d\n", ret);
    			return ret;
    		}
    		printf("tmp->age:%d\t", tmp->age);
    	}
    
    	//销毁链表
    	LinkList_Destroy(list);
    
    	printf("hello...\n");
    	system("pause");
    	return ret;
    }

[70]: /images/20220529/8e4c643db4984af1895a1cbfa7af4c89.png
[70 1]: /images/20220529/77df7a0cc17c4665b166b16253788ddc.png
[70 2]: https://img-blog.csdn.net/20180324192223131?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: /images/20220529/0e15cec681134a47b37026ad8bdca1ae.png