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

野性酷女 2022-05-29 12:42 200阅读 0赞

1 线性表定义

线性表(list)是零个或多个数据元素的集合，线性表中的数据元素之间是有顺序的，线性表中的数据元素个数是有限的，线性表中数据元素的类型必须相同。

2 线性表数学定义

线性表（linear list）也称为有序表（ order list ）。每一个实例都是元素的一个有序集合。每一个实例的形式为（e 1 ,e 2 ,e 3 ,...,e n-1 ），其中n为又穷自然数，e i 是线性表的元素，i是元素e i 的索引，n是线性表的大小。元素可以被看做原子，它们本身的结构与线性表的结构无关。当n = 0时，线性表为空；当n>0时，e 0 是线性表的第0个元素，e n-1 是线性表的最后一个元素。

3 线性表的性质

e0为线性表的第一个元素，只有一个后继， en为线性表的最后一个元素，只有一个前驱。除e0和en外的其它元素ei，既有前驱，又有后继线性表能够逐项访问和顺序存取。

![70][]

![70 1][]

**代码实现以及测试案例**

//SeqList.h
    #ifndef  _SEQLIST_H__ 
    #define  _SEQLIST_H__
    
    typedef void SeqList;
    typedef void SeqListNode;
    
    //创建并且返回一个空的线性表
    SeqList* SeqList_Create(int capacity);
    
    //销毁一个线性表list
    void SeqList_Destroy(SeqList* list);
    
    //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
    void SeqList_Clear(SeqList* list);
    
    //返回一个线性表list中的所有元素个数
    int SeqList_Length(SeqList* list);
    
    int SeqList_Capacity(SeqList* list);
    
    //向一个线性表list的pos位置处插入新元素node
    int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);
    
    //获取一个线性表list的pos位置处的元素
    SeqListNode* SeqList_Get(SeqList* list, int pos);
    
    //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
    SeqListNode* SeqList_Delete(SeqList* list, int pos);
    
    
    #endif  //_SEQLIST_H__

//SeqList.c
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "SeqList.h"
    
    //在结构体中套1级指针
    typedef struct _tag_SeqList
    {
    	int length;
    	int capacity;
    	unsigned int *node;   //链表需要有内存空间装元素- 根据容量来分配内存空间-需要动态内存空间-则需要在结构体中定义一个指针
    }TSeqList;
    
    //创建并且返回一个空的线性表
    SeqList* SeqList_Create(int capacity)
    {
    	int ret = 0;
    	//1 链表申请动态内存空间
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)malloc(sizeof(TSeqList));
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func malloc() err:%d\n");
    		return NULL;
    	}
    	memset(tmp,0,sizeof(TSeqList));//让开辟的内存 完成链表初始化
    	//2 根据容量分配内存大小
    	tmp->node = (unsigned int *)malloc(sizeof(unsigned int *)*capacity);
    	if (NULL == tmp->node)
    	{
    		ret = -2;
    		printf("func malloc() err:%d\n");
    		return NULL;
    	}
    	tmp->capacity = capacity;
    	tmp->length = 0;
    	return tmp;
    }
    
    //销毁一个线性表list
    void SeqList_Destroy(SeqList* list)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func SeqList_Destroy() err:%d\n",ret);
    	}
    	// 先申请 后释放
    	if (tmp->node!=NULL)
    	{
    		free(tmp->node);
    	}
    	free(tmp);
    }
    
    //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
    void SeqList_Clear(SeqList* list)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func SeqList_Clear() err:%d\n", ret);
    	}
    	tmp->length = 0;
    	memset(tmp->node, 0, (tmp->capacity * sizeof(void *)));
    }
    
    //返回一个线性表list中的所有元素个数
    int SeqList_Length(SeqList* list)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func SeqList_Length() err:%d\n", ret);
    	}
    	return tmp->length;
    }
    
    int SeqList_Capacity(SeqList* list)
    {
    	int ret = 0;
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func SeqList_Capacity() err:%d\n", ret);
    	}
    	return tmp->capacity;
    }
    
    //向一个线性表list的pos位置处插入新元素node
    int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
    {
    	int ret = 0;
    	int i = 0;
    	//1 缓存下来 进行操作
    	TSeqList    *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func SeqList_Insert() err:%d\n", ret);
    	}
    	//如果满了
    	if (tmp->length >= tmp->capacity)
    	{
    		ret = -2;
    		printf("func SeqList_Insert() err:%d\n", ret);
    	}
    	//pos 位置容错处理
    	if (pos > tmp->length)
    	{
    		pos = tmp->length;
    	}
    	//元素后移
    	for (i = tmp->length; i > pos; i--)
    	{
    		tmp->node[i] = tmp->node[i-1];
    	}
    	//空出位置插入结点
    	tmp->node[i] = (int *)node;
    	tmp->length++;
    
    	return 0;
    }
    
    //获取一个线性表list的pos位置处的元素
    SeqListNode* SeqList_Get(SeqList* list, int pos)
    {
    	int ret = 0;
    	int i = 0;
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp||pos < 0|| pos >= tmp->length)
    	{
    		ret = -1;
    		printf("func SeqList_Get() err:%d\n", ret);
    	}
    	tmp = tmp->node[pos];
    	return tmp;
    }
    
    //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
    SeqListNode* SeqList_Delete(SeqList* list, int pos)
    {
    	int ret = 0;
    	int i = 0;
    	SeqListNode *temp = NULL;//缓存删除的结点
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	if (NULL == tmp || pos < 0 || pos >= tmp->length)
    	{
    		ret = -1;
    		printf("func SeqList_Delete() err:%d\n", ret);
    	}
    	temp = tmp->node[pos];
    	//元素前移
    	for (int i = pos+1; i <tmp->length ; i++)
    	{
    		tmp->node[i - 1] = tmp->node[i];
    		//t[0]=t[1];
    	}
    	tmp->length--;
    	return temp;
    }

//text.c
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "SeqList.h"
    
    
    //业务结点
    typedef struct _Teacher
    {
    	char name[32];
    	int age;
    }Teacher;
    
    int main()
    {
    	int ret = 0;
    	Teacher t1, t2, t3;
    	t1.age = 31;
    	t2.age = 32;
    	t3.age = 33;
    	//1 创建空的链表的顺序结构
    	SeqList *list = NULL;
    	list = SeqList_Create(10);
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err SeqList_Create():%d\n");
    		return ret;
    	}
    	//思考1: 如何实现 链表的api(链表的算法) 和 具体的数据分离  
    	//思考2: 链表库(业务逻辑)  测试程序的业务逻辑  结点的生命周期 归谁管? 
    	//2 插入元素 链表的插入 采用头插法
    	ret = SeqList_Insert(list,(SeqListNode *)&t1,0);
    	if (ret!=0)
    	{
    		ret = -2;
    		printf("func err SeqList_Insert()\n");
    		return ret;
    	}
    	ret = SeqList_Insert(list, (SeqListNode *)&t2, 0);
    	if (ret != 0)
    	{
    		ret = -3;
    		printf("func err SeqList_Insert()\n");
    		return ret;
    	}
    	ret = SeqList_Insert(list, (SeqListNode *)&t3, 0);
    	if (ret != 0)
    	{
    		ret = -4;
    		printf("func err SeqList_Insert()\n");
    		return ret;
    	}
    
    	//3 遍历链表
    	for (int i = 0; i < SeqList_Length(list); i++)
    	{
    		Teacher *tmp = (Teacher *)SeqList_Get(list, i); //获取链表结点  
    		if (NULL == tmp)
    		{
    			ret = -5;
    			printf("func SeqList_Get() err\n ", ret);
    			return ret;
    		}
    		printf("age:%d \n", tmp->age);
    	}
    
    	// 4 删除链表结点
    	while (SeqList_Length(list) > 0)
    	{
    		Teacher *tmp = (Teacher *)SeqList_Delete(list,0);
    		if (NULL == tmp)
    		{
    			ret = -6;
    			printf("func SeqList_Delete() err\n ");
    			return ret;
    		}
    		printf("age:%d \n", tmp->age);
    	}
    
    	//5 销毁链表
    	SeqList_Destroy(list);
    
    	system("pause");
    	return ret;
    }

[70]: /images/20220529/7d5005287d074f52b0f39e39d7261589.png
[70 1]: /images/20220529/4128d495765d43beb9aee754055d9906.png