概述
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，既有前驱，又有后继线性表能够逐项访问和顺序存取。
代码实现以及测试案例
//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:%dn");
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:%dn");
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:%dn",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:%dn", 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:%dn", 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:%dn", 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:%dn", ret);
}
//如果满了
if (tmp->length >= tmp->capacity)
{
ret = -2;
printf("func SeqList_Insert() err:%dn", 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:%dn", 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:%dn", 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():%dn");
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() errn ", 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() errn ");
return ret;
}
printf("age:%d n", tmp->age);
}
//5 销毁链表
SeqList_Destroy(list);
system("pause");
return ret;
}最后
以上就是外向羊为你收集整理的数据结构之线性表——链表的顺序存储（数组描述）的全部内容，希望文章能够帮你解决数据结构之线性表——链表的顺序存储（数组描述）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复