线性表的链式存储

雨点打透心脏的1/2处 2022-05-29 09:14 234阅读 0赞

线性表的链式存储的插入操作：

![Image 1][]

线性表的链式存储的删除操作：

![Image 1][]

链式存储定义

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

线性表链式存储的结构图

![Image 1][]

链表的头文件：

//LinkList.h
    #ifndef _MYLINKLIST_H_
    #define _MYLINKLIST_H_
    
    typedef void LinkList;//链表的句柄
    
    //节点的指针域
    typedef struct _tag_LinkListNode
    {
    	struct _tag_LinkListNode* next;
    }LinkListNode;
    
    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

链表的.c文件：

#define  _CRT_SECURE_NO_WARNINGS   
    #include <stdlib.h>  
    #include <string.h>  
    #include <stdio.h>  
    #include "linklist.h"
    
    //头结点定义  链式存储头结点：表示链表中的第一个节点，包含指向第一个数据元素的指针以及链表自身的一些信息
    typedef struct _tag_LinkList
    {
    	LinkListNode header;//包含指针域节点
    	int		length;//头结点自身的信息
    }TLinkList;
    
    
    
    LinkList* LinkList_Create()
    {
    	//1 申请动态内存空间
    	TLinkList *tmp = (TLinkList *)malloc(sizeof(TLinkList));
    	if (NULL == tmp)
    	{
    		printf("func err malloc\n");
    		return NULL;
    	}
    
    	//2 初始化
    	memset(tmp,0,sizeof(TLinkList));
    	tmp->length = 0;
    	tmp->header.next = NULL;
    
    	return tmp;
    }
    // 链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
    void LinkList_Destroy(LinkList* list)
    {
    	TLinkList *tmp = (TLinkList *)list;
    	if (NULL == tmp)
    	{
    		printf("func err LinkList_Destroy()\n");
    	}
    	free(tmp);//释放头结点空间 
    }
    //链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0  
    void LinkList_Clear(LinkList* list)
    {
    	TLinkList *tmp = (TLinkList *)list;
    	if (NULL == tmp)
    	{
    		printf("func err LinkList_Clear()\n");
    	}
    	tmp->header.next = NULL;
    	tmp->length = 0;
    }
    //链表的长度返回头结点中的length 
    int LinkList_Length(LinkList* list)
    {
    	int ret = 0;
    	TLinkList *tmp = (TLinkList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkList_Length():%d\n",ret);
    		return ret;
    	}
    	ret = tmp->length;
    	return ret;
    }
    
    //链表的插入操作
    int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
    {
    	int ret = 0;
    	TLinkList *tmp = (TLinkList *)list;
    	LinkListNode *pCur = NULL;//辅助指针 用来遍历当前指针位置
    	if (NULL == tmp||NULL == node || pos < 0)
    	{
    		ret = -1;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    
    	pCur = &(tmp->header);//1 当前指针 初始化 指向 头结点
    
    	for (int i = 0; i < pos; i++)//2 进行遍历 找到插入位置
    	{
    		pCur = pCur->next;
    	}
    
    	//进行插入操作
    	node->next = pCur->next;//小心两步一定不能弄反 否则 会掉链子
    	pCur->next = node;
    
    	tmp->length++;//最后链表的元素个数加1
    
    	return ret;
    }
    
    LinkListNode* LinkList_Get(LinkList* list, int pos)
    {
    
    	int           ret = 0;
    	TLinkList    *tmp = (TLinkList *)list;
    	LinkListNode *pCur = NULL;//辅助指针 用来遍历当前指针位置
    	if (NULL == tmp||pos < 0)
    	{
    		ret = -1;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return NULL;
    	}
    	pCur = &(tmp->header);//1 当前指针 初始化 指向 头结点
    
    	for (int i = 0; i < pos; i++)//2 进行遍历 找到插入位置
    	{
    		pCur = pCur->next;
    	}
    
    	return pCur->next;
    }
    
    LinkListNode* LinkList_Delete(LinkList* list, int pos)
    {
    	int           ret = 0;
    	TLinkList    *tmp = (TLinkList *)list;
    	LinkListNode *pCur = NULL;//辅助指针 用来遍历当前指针位置
    	LinkListNode *Delete = NULL;
    
    	if (NULL == tmp ||pos < 0 || pos >tmp->length)
    	{
    		ret = -1;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return NULL;
    	}
    
    	pCur = &(tmp->header);//1 当前指针 初始化 指向 头结点
    
    	for (int i = 0; i < pos; i++)//2 进行遍历 找到删除位置
    	{
    		pCur = pCur->next;
    	}
    
    	Delete = pCur->next;//缓存删除的结点
    
    	pCur->next = Delete->next;//删除操作
    
    	tmp->length--;
    	return Delete;
    }

链表的测试框架：

#define  _CRT_SECURE_NO_WARNINGS   
    #include <stdlib.h>  
    #include <string.h>  
    #include <stdio.h>  
    #include "linklist.h"
    
    
    
    typedef struct _Teacher
    {
    	LinkListNode node;//包含指针域节点
    	//下面是业务域
    	char		name[32];
    	int			age;
    }Teacher;
    
    
    
    void main()
    {
    	LinkList *list = NULL;
    	Teacher t1, t2, t3, t4;//节点生命周期在这里由main函数管理
    	t1.age = 31; t2.age = 32; t3.age = 33; t4.age = 34;
    
    	//创建链表
    	list = LinkList_Create();
    	if (NULL == list)
    	{
    		printf("func err LinkList_Create()\n");
    	}
    
    	//业务节点 和链表算法是如何分离
    
    	//插入元素  头插法 插入链表的元素
    	LinkList_Insert(list, (LinkListNode *)&t1, 0);
    	LinkList_Insert(list, (LinkListNode *)&t2, 0);
    	LinkList_Insert(list, (LinkListNode *)&t3, 0);
    	LinkList_Insert(list, (LinkListNode *)&t4, 0);
    
    	//遍历链表
    	for (int i = 0; i < LinkList_Length(list); i++)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Get(list,i);
    		if (NULL == tmp)
    		{
    			printf("func err LinkList_Get()\n");
    		}
    		printf("tmp->age:%d\n",tmp->age);
    	}
    
    	//删除链表结点 从头部删除  链表节点的生命周期由调用者负责，也就是main()函数负责 调用LinkList_Delete删除每个节点
    	while (LinkList_Length(list) > 0)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Delete(list,0);
    		if (NULL == tmp)
    		{
    			printf("func err LinkList_Delete()\n");
    		}
    		printf("tmp->age:%d\n", tmp->age);
    	}
    	//最后销毁 链表 只需要释放头结点的内存空间
    	LinkList_Destroy(list);
    	system("pause");
    }

[Image 1]: