线性表的链式存储设计与实现(C语言版本)

清疚 2022-05-25 13:23 140阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct PStudent
    {
    	int sid;
    	char name[100];
    	char sex;
    }*Student,STU;//Student===> struct PStudent*   STU等价于struct PStudent 
    
    void main()
    {
    	STU s1;
    	Student ps = &s1;
    	ps->sid = 82;
    	s1.sid = 34;
    	printf("ps->sid:%d", ps->sid);
    
    	system("pause");
    }

![70][]

![70 1][]

链表的插入操作：

![70 2][]

//LinkList.h
    #ifndef _LINKLIST_H_
    #define _LINKLIST_H_
    
    //单链表的存储结构
    //结点中包含后继结点地址的指针域组成-可以理解为指向下一个结构体(结点)
    //(这里不包含数据域,是实现了 链表的api(链表的算法) 和 具体的数据分离)
    typedef struct _tag_LinkListNode
    {
    	struct _tag_LinkListNode *next;
    }LinkListNode;
    
    //为void 再重新多取一个名字，LinkList等价于void
    //typedef + 已有的数据类型+新的数据类型(自己取的新名字)
    typedef void LinkList;
    
    //创建并且返回一个空的链式的线性表 
    LinkList* LinkList_Create();
    
    //销毁一个链式的线性表list 
    void LinkList_Destroy(LinkList* list);
    
    //将一个链式线性表list中的所有元素清空, 链式线性表回到创建时的初始状态  
    void LinkList_Clear(LinkList* list);
    
    //返回一个链式线性表list中的所有元素个数
    int LinkList_Length(LinkList* list);
    
    //向一个链式线性表list的pos位置处插入新元素node 
    int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
    
    //获取一个链式线性表list的pos位置处的元素 
    LinkListNode* LinkList_Get(LinkList* list, int pos);
    
    //删除一个链式线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
    LinkListNode* LinkList_Delete(LinkList* list, int pos);
    
    #endif

//LinkList.c
    #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 = NULL;
    	tmp = (TLinkList *)malloc(sizeof(TLinkList));
    	if (NULL == tmp)
    	{
    		printf("func err malloc\n");
    		return NULL;
    	}
    	//2 让开辟的内存 完成链式线性表初始化  
    	memset(tmp,0,sizeof(TLinkList));
    
    	//3 链表的初始化
    	tmp->header.next = NULL;
    	tmp->length = 0;
    
    	return tmp;
    }
    
    //销毁一个链式的线性表list 
    //链表节点的生命周期由调用者负责，也就是main()函数负责，链表的销毁只需释放头结点空间
    void LinkList_Destroy(LinkList* list)
    {
    	//1 缓存下来 进行操作
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	if (NULL == list)
    	{
    		printf("func err LinkList_Destroy\n");
    	}
    	//2 释放头结点空间 
    	if (tmp!=NULL)
    	{
    		free(tmp);
    	}
    }
    
    //将一个链式线性表list中的所有元素清空, 链式线性表回到创建时的初始状态  
    //链表的清空只是将头结点的指针域指向NULL,以及链表的长度length赋值为0  
    void LinkList_Clear(LinkList* list)
    {
    	//1 缓存下来 进行操作
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	if (NULL == list)
    	{
    		printf("func err LinkList_Clear\n");
    	}
    	//2 清空链表
    	tmp->header.next = NULL;
    	tmp->length = 0;
    }
    
    //返回一个链式线性表list中的所有元素个数
    int LinkList_Length(LinkList* list)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err LinkList_Length:%d\n",ret);
    		return ret;
    	}
    	ret = tmp->length;
    	return ret;
    }
    
    //向一个链式线性表list的pos位置处插入新元素node 
    int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	//辅助指针 用来遍历当前指针位置
    	LinkListNode *pCur = NULL;
    	if (NULL == list || NULL == node || pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list || NULL == node || pos < 0):%d\n", ret);
    		return ret;
    	}
    	//1 当前指针 初始化 指向 头结点
    	pCur = &(tmp->header);
    	//2 进行遍历 找到插入位置
    	for (int i = 0; i < pos; i++)
    	{
    		pCur = pCur->next;
    	}
    	//3 进行插入操作
    	node->next = pCur->next;//1
    	pCur->next = node;
    
    	//4 链表长度++
    	tmp->length++;
    
    	return ret;
    }
    
    //获取一个链式线性表list的pos位置处的元素 
    LinkListNode* LinkList_Get(LinkList* list, int pos)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TLinkList *tmp = NULL;
    	tmp = (TLinkList *)list;
    	//辅助指针 用来遍历当前指针位置
    	LinkListNode *pCur = NULL;
    	if (NULL == list || pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list|| pos < 0):%d\n", ret);
    		return NULL;
    	}
    	//1 当前指针 初始化 指向 头结点
    	pCur = &(tmp->header);
    	//2 进行遍历 找到pos位置
    	for (int i = 0; i < pos; i++)
    	{
    		pCur = pCur->next;
    	}
    
    	return pCur->next;
    }
    
    //删除一个链式线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
    LinkListNode* LinkList_Delete(LinkList* list, int pos)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TLinkList     *tmp = NULL;
    	tmp = (TLinkList *)list;
    	//辅助指针 用来缓存要删除的结点
    	LinkListNode *Deletemp = NULL;
    	//辅助指针 用来遍历当前指针位置
    	LinkListNode *pCur = NULL;
    	if (NULL == list || pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list|| pos < 0):%d\n", ret);
    		return NULL;
    	}
    	//1 当前指针 初始化 指向 头结点
    	pCur = &(tmp->header);
    	//2 进行遍历 找到要删除的pos位置
    	for (int i = 0; i < pos; i++)
    	{
    		pCur = pCur->next;
    	}
    	//3 缓存要删除的元素
    	Deletemp = pCur->next;
    	//4 进行删除操作
    	pCur->next = Deletemp->next;
    	//5 链表长度--
    	tmp->length--;
    
    	return Deletemp;
    }

//text.c
    //线性表的链式存储设计与实现
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "LinkList.h"
    
    
    //业务结点
    typedef struct Teacher
    {
    	LinkListNode node; //包含指针域节点
    	//下面是业务域
    	int age;
    	char name[64];
    }Teacher;
    
    int 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 (NULL == list)
    	{
    		ret = -1;
    		printf("func err LinkList_Create():%d\n", ret);
    		return ret;
    	}
    
    	len = LinkList_Length(list);
    	if (len < 0)
    	{
    		ret = -2;
    		printf("func err LinkList_Length():%d\n", ret);
    		return ret;
    	}
    
    	//链表的算法和具体业务节点的分离 头插法
    	ret = LinkList_Insert(list, (LinkListNode*)(&t1), 0);
    	if (ret != 0)
    	{
    		ret = -3;
    		printf("func err LinkList_Insert():%d\n", ret);
    		return ret;
    	}
    	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);
    
    	//ret = LinkList_Clear(list);
    	//if (ret != 0)
    	//{
    	//	ret = -6;
    	//	printf("func err LinkList_Insert():%d\n", ret);
    	//	return ret;
    	//}
    
    	//遍历
    	for (i = 0; i< LinkList_Length(list); i++)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Get(list, i);
    		if (NULL == tmp)
    		{
    			ret = -4;
    			printf("func err LinkList_Get():%d\n", ret);
    			return ret;
    		}
    		printf("tmp->age:%d\n", tmp->age);
    	}
    	printf("================================我是分界线===============================\n");
    	//删除链表
    	while (LinkList_Length(list) > 0)
    	{
    		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
    		if (NULL == tmp)
    		{
    			ret = -5;
    			printf("func err LinkList_Delete():%d\n", ret);
    			return ret;
    		}
    		printf("tmp->age:%d\n", tmp->age);
    	}
    
    	LinkList_Destroy(list);
    
    	system("pause");
    	return ret;
    }

[70]: /images/20220525/0f22d9563d484ac38be49d593fb1a7a8.png
[70 1]: /images/20220525/e58afdc282cd4a60b31539e5cacd3db6.png
[70 2]: /images/20220525/8dc33301e67543c49943a04793e66b63.png