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

た入场券 2022-05-29 02:39 203阅读 0赞

linklist.h头文件

#ifndef _LINKLIST_H_ 
    #define _LINKLIST_H_ 
    
    //将数据的类型分离，相当于句柄
    typedef void LinkList;//链表的句柄 
    
    //节点指针域定义
    typedef struct _tag_LinkListNode
    {
    	struct _tag_LinkListNode *next;
    }LinkListNode;
    
    LinkList* LinkList_Create();
    
    int LinkList_Destroy(LinkList* list);
    
    int 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.cpp文件：

#include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "linklist.h"
    
    //头结点定义
    typedef struct _tag_LinkList
    {
    	int length;//头结点自身信息
    	LinkListNode header;
    }TLinkList;
    
    //链表的创建
    LinkList* LinkList_Create()
    {
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)malloc(sizeof(TLinkList));//申请一个头结点的空间
    	if (NULL==tmp)
    	{
    		printf("func LinkList_Create() err\n");
    		return NULL;
    	}
    	memset(tmp, 0, sizeof(TLinkList));
    	tmp->length = 0;//将链表的长度置0
    	tmp->header.next = NULL;//链表头结点的next域指向NULL
    	return tmp;//返回头结点
    }
    
    int LinkList_Destroy(LinkList* list)
    {
    	int ret = 0;
    //链表节点的生命周期由调用者负责，也就是main()函数负责，
    //链表的销毁只需释放头结点空间  
    	if (list==NULL)
    	{
    		ret = -1;
    		printf("func err list==NULL:%d\n",ret);
    		return ret;
    	}
    	free(list);
    	return ret;
    }
    //链表的清空
    //链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0
    int LinkList_Clear(LinkList* list)
    {
    	int ret = 0;	
    	TLinkList *tlist = NULL;
    	tlist = (TLinkList *)list;//强制类型转换
    	if (tlist == NULL)
    	{
    		ret = -1;
    		printf("func err list==NULL:%d\n", ret);
    		return ret;
    	}
    	tlist->header.next = NULL;
    	tlist->length = 0;
    	return ret;
    }
    
    int LinkList_Length(LinkList* list)
    {
    	int ret = 0;
    	TLinkList *tlist = NULL;
    	tlist = (TLinkList *)list;
    	if (tlist == NULL)
    	{
    		ret = -1;
    		printf("func err list==NULL:%d\n", ret);
    		return ret;
    	}
    	return tlist->length;//链表的长度返回头结点中的length 
    }
    
    int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
    {
    	int			  ret = 0;
    	LinkListNode *current = NULL;
    	TLinkList	 *tList = NULL;
    	tList = (TLinkList *)list;
    	if (list==NULL||node==NULL||pos<0)
    	{
    		ret = -1;
    		printf("func LinkList_Insert() err:%d\n",ret);
    		return ret;
    	}
    	current = &(tList->header);//当前节点指向头结点指针域
    	for (int i = 0; i < pos&&(current->next!=NULL); i++)//current节点跳到要插入节点的头一个结点
    	{
    		current = current->next;
    	}
    	//1 新节点 连接后续链表
    	node->next = current->next;//node的节点的指针域指向current节点的下一个节点  
    	//2 前面的链表 连接 新结点  
    	current->next = node;//current节点的指针域指向node节点 
    	tList->length++;//链表的长度加一 
    	return 0;
    }
    
    LinkListNode* LinkList_Get(LinkList* list, int pos)//0(n)
    {
    	int           ret = 0;
    	LinkListNode *current = NULL;
    	TLinkList    *tList = NULL;
    	tList = (TLinkList *)list;//缓存链表 进行操作
    	if (list == NULL || pos<0)
    	{
    		ret = 0;
    		printf("func LinkList_Insert() err:%d\n", ret);
    		return NULL;
    	}
    	current = &(tList->header);//赋值指针变量初始化 
    	for (int i = 0; i < pos && (current->next != NULL); i++)
    	{
    		current = current->next;//current指针向后跳  
    	}
    	//链表是单向的，n号结点的位置贮存在n-1结点的next域
    	return current->next;//返回current指向节点的下一个节点的  
    }
    
    LinkListNode* LinkList_Delete(LinkList* list, int pos)
    {
    	LinkListNode *ret = NULL;
    	LinkListNode *current = NULL;
    	TLinkList    *tList = NULL;
    	tList = (TLinkList *)list;
    	if (list == NULL || pos<0)
    	{
    		printf("func LinkList_Delete() err\n");
    		return NULL;
    	}
    	current = &(tList->header);//让辅助指针变量指向链表的头部
    	for (int i = 0; i < pos && (current->next != NULL); i++)//跳pos次数
    	{
    		current = current->next;
    	}
    
    	//缓存被删除的结点位置
    	ret = current->next;
    
    	//连线 删除节点
    	current->next = ret->next;
    	tList->length--;
    
    	return ret;
    }

线性表链式存储集成测试.c：

#include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "linklist.h"
    #include "linklist.cpp"
    
    //数据元素定义实例
    typedef struct Teacher
    {
    	LinkListNode node; //包含指针域节点
    	//下面是业务域
    	int age;
    	char name[64];
    }Teacher;
    
    void main()
    {
    	int len = 0, ret = 0, i = 0;
    
    	LinkList* list = NULL;
    
    	Teacher  t1, t2, t3, t4, t5;
    	t1.age = 31;
    	t2.age = 32;
    	t3.age = 33;
    	t4.age = 34;
    	t5.age = 35;
    
    	list = LinkList_Create();
    	if (list == NULL)
    	{
    		return ;
    	}
    
    	len = LinkList_Length(list);
    
    	//链表的算法和具体业务节点的分离 头插法
    	ret = LinkList_Insert(list, (LinkListNode*)(&t1), 0);
    	ret = LinkList_Insert(list, (LinkListNode*)(&t2), 0);
    	ret = LinkList_Insert(list, (LinkListNode*)(&t3), 0);
    	ret = LinkList_Insert(list, (LinkListNode*)(&t4), 0);
    	ret = LinkList_Insert(list, (LinkListNode*)(&t5), 0);
    
    	//遍历
    
    	for (i=0; i< LinkList_Length(list); i++)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Get(list, i);
    		if (tmp == NULL)
    		{
    			return ;
    		}
    		printf("tmp->age:%d\n", tmp->age);
    	}
    	printf("================================我是分界线===============================\n");
    	//删除链表
    	while (LinkList_Length(list) > 0)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
    		if (tmp == NULL)
    		{
    			return ;
    		}
    		printf("tmp->age:%d\n", tmp->age);
    	}
    
    	LinkList_Destroy(list);
    
    	system("pause");
    	return ;
    }