【数据结构】之线性表（顺序存储结构）

深藏阁楼爱情的钟 2024-04-17 22:18 100阅读 0赞

> **博主声明：**
> 
> 转载请在开头附加本文链接及作者信息，并标记为转载。本文由博主 [威威喵][Link 1] 原创，请多支持与指教。
> 
> [本文首发于此][Link 2] [博主][Link 3]：[威威喵][Link 1] [|][Link 4] [博客主页][Link 5]：[https://blog.csdn.net/smile\_running][Link 5]

线性表是《数据结构》课程最开始的一章的内容，是在大学计算机专业必学的课程。我们刚接触线性表时，可能会被它的几种表的结构搞得晕头转向，它有两种基本存储结构：一种是顺序存储结构，另一种是链式存储结构。接下来，我们先来看看线性表的顺序存储结构吧。

首先，线性表的顺序存储结构用图来表示，它是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70][]

这张图很直观的说明了线性表的结构，图中元素都是一个挨着一个，表示线性表中（顺序存储结构）数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像*（sequential mapping）*。它以**“物理位置相邻”**来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

既然它的地址是相邻的，我们就可以通过地址计算公式来计算出某一个元素存在的地址。下面的计算的公式：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1][]

之前考试的时候，在线性表那一章肯定会遇到这样的题目，也是非常简单、基础的一道题，套公式就可以很快的计算出来。题目是这样的：**某线性表采用顺序存储结构，每个元素占 4 个存储单元，首地址为 100，则第 12 个元素的 存储地址为（ ）？**

**这题直接套用上面的公式： 100 + （12 - 1）\* 4 = 144，所以此题的答案是：144。**好了，其他就不做多的介绍了，我们直接看代码吧。

### 一、数组实现方式 ###

线性表的数据结构，其中 MAX 表示线性表的数组元素个数，就是线性表的最大容量，length 表示线性表当前的长度。这里有一个必要条件，就是 **length <= MAX**

#define MAX 20
    typedef int ElemType;
    typedef struct
    {
    	ElemType data[MAX];	
    	int length;
    }SqList;

初始化线性表，即使线性表的长度为 0

/** 初始化线性表 **/
    void InitList(SqList *L)
    {
    	L->length = 0;
    }

获取线性表中的元素值，传入的是线性表中元素的位置（下标）

/** 获取元素 **/
    int Get(SqList L, ElemType *e, int i)
    {
    	if(L.length ==0 || i<1 || i>L.length)
    		return -1;
    	*e = L.data[i-1];
    	return *e;
    }

向表中插入数据

/** 插入元素 **/
    int Insert(SqList *L, ElemType e, int i)
    {
    	int j;
    	if(L->length == MAX)
    		return -1;
    	if(i<1 || i>L->length+1)
    		return -1;
    
    	if(i<= L->length)
    	{	
    		for(j=L->length; j>i-1; j--)
    		{
    			L->data[j] = L->data[j-1];
    		}
    	}
    
    	L->data[i-1] = e;
    	L->length++;
    	return 1;
    }

删除线性表中指定位置的元素

/** 删除指定下标的元素 **/
    int Delete(SqList *L,int i)
    {
    	int j;
    	if(L->length == 0)
    		return -1;
    	if(i<1 || i>L->length +1)
    		return -1;
    
    	if(i<L->length)
    	{
    		for(j=i; j<L->length; j++)
    		{
    			L->data[j-1] = L->data[j];
    		}
    	}
    	L->length--;
    	return 1;
    }

获取当前表的长度

/** 线性表的长度 **/
    int Length(SqList *L)
    {
    	return L->length;
    }

清除线性表

/** 清除线性表 **/
    void Clear(SqList *L)
    {
    	L->length = 0;
    }

打印表中的元素

/** 打印线性表 **/
    void PrintList(SqList *L)
    {
    	int i;
    	for(i=0; i<L->length; i++)
    	{
    		printf("%d ",L->data[i]);
    	}
    	printf("\n");
    }

最后，写一个 main() 方法来测试一下线性表的元素获取、插入、删除等操作。以下是完整的代码：

#include <stdio.h>
     
    /**
     * 数据结构 - 线性表的顺序存储
     * 博客：https://vvcat.blog.csdn.net/
     **/
    #define MAX 20
    typedef int ElemType;
    typedef struct
    {
    	ElemType data[MAX];	
    	int length;
    }SqList;
     
    /** 初始化线性表 **/
    void InitList(SqList *L)
    {
    	L->length = 0;
    }
     
    /** 获取元素 **/
    int Get(SqList L, ElemType *e, int i)
    {
    	if(L.length ==0 || i<1 || i>L.length)
    		return -1;
    	*e = L.data[i-1];
    	return *e;
    }
     
    /** 插入元素 **/
    int Insert(SqList *L, ElemType e, int i)
    {
    	int j;
    	if(L->length == MAX || i<1 || i>L->length+1)
    		return -1;
     
    	// 如果插入的位置不在末尾，要移动元素
    	if(i<= L->length)
    	{	
    		for(j=L->length; j>i-1; j--)
    		{
    			L->data[j] = L->data[j-1];
    		}
    	}
     
    	L->data[i-1] = e;
    	L->length++;
    	return 1;
    }
     
    /** 删除指定下标的元素 **/
    int Delete(SqList *L,int i)
    {
    	int j;
    	if(L->length == 0 || i<1 || i>L->length +1)
    		return -1;
     
    	// 如果删除位置不在末尾，移动元素
    	if(i<L->length)
    	{
    		for(j=i; j<L->length; j++)
    		{
    			L->data[j-1] = L->data[j];
    		}
    	}
     
    	L->length--;
    	return 1;
    }
     
    /** 清除线性表 **/
    void Clear(SqList *L)
    {
    	L->length = 0;
    }
     
    /** 线性表的长度 **/
    int Length(SqList *L)
    {
    	return L->length;
    }
     
    /** 打印线性表 **/
    void PrintList(SqList *L)
    {
    	int i;
    	for(i=0; i<L->length; i++)
    	{
    		printf("%d ",L->data[i]);
    	}
    	printf("\n");
    }
     
    /**
     * 数据结构 - 线性表的顺序存储
     * 博客：https://vvcat.blog.csdn.net/
     * 博主：威威喵
     **/
    void main()
    {
    	int i;
    	int status = 0;
    	int arr[10] = {3,7,11,6,5,14,36,9,4,19}; 
    	SqList list;
    	ElemType e;
     
    	InitList(&list);
     
    	/** 插入 10 个数据 **/
    	for(i=1; i<=10; i++)
    	{	
    		Insert(&list, arr[i-1], i);
    	}
    	printf("线性表的顺序存储，长度 = %d \n", Length(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 在位置 5 插入一个数据 **/ 
    	Insert(&list, 45, 5);
    	printf("插入元素 45，长度为 = %d \n", Length(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 获取下标为 5 的元素的值 **/
    	printf("获取的元素为 %d \n", Get(list, &e, 5));
    	printf("\n");
     
    	/** 删除位置 5 的数据 **/ 
    	Delete(&list, 5);
    	printf("删除元素 45，长度为 = %d \n", Length(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 清空数据 **/ 
    	Clear(&list);
    	printf("清除，长度为 = %d \n", Length(&list));
    }

其运行结果为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2][]

### 二、动态扩容 ###

线性表的另一种实现方法：**动态扩容的线性表**，因为上面的数组实现方式，其数组大小是固定的，如果数据添加满了话，再添加数据则会导致数组溢出，不容易进行动态扩容。以下是完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
     
    /**
     * 数据结构 - 线性表的顺序存储
     * 博客：https://vvcat.blog.csdn.net/
     **/
    #define LIST_SIZE 10
    #define CAPACITY 5
    typedef int ElemType;
    typedef struct
    {
    	ElemType *data;	
    	int length;
    	int size;
    }SqList;
     
    /** 动态的初始化线性表 **/
    int InitList(SqList *L)
    {
    	// 申请分配的内存空间大小
    	L->data = (ElemType *)malloc(sizeof(ElemType) * LIST_SIZE);
    	if(L->data == NULL)
    		return -1;
    	L->length = 0;
    	L->size = LIST_SIZE;
    	return 1;
    }
     
    /** 获取元素 **/
    int Get(SqList L, ElemType *e, int i)
    {
    	if(L.length ==0 || i<1 || i>L.size)
    		return -1;
    	*e = L.data[i-1];
    	return *e;
    }
     
    /** 插入元素 **/
    int Insert(SqList *L, ElemType e, int i)
    {
    	ElemType *p = NULL;
    	ElemType *q = NULL;
    
    	if(i<1 || i>L->size)
    		return -1;
    
    	/** 如果内存空间不足，动态的扩容，每次扩容 CAPACITY 个大小 **/
    	if(L->length == LIST_SIZE)
    	{
    		L->data = (ElemType *)realloc(L->data, sizeof(ElemType) * (CAPACITY + LIST_SIZE));
    		L->size += CAPACITY;
    		if(!L->data)
    		{
    			printf("扩容失败！");
    			return -1;
    		}
    	}
    
    	p = &L->data[i-1];//插入的位置
    	for(q=&L->data[L->length-1]; q>=p; q--)
    	{
    		*(q+1) = *q;	
    	}
    	*p = e;
     
    	L->length++;
    	return 1;
    }
     
    /** 删除指定下标的元素 **/
    int Delete(SqList *L, ElemType *e, int i)
    {
    	ElemType *p = NULL;
    	ElemType *q = NULL;
    
    	if(L->length == 0 || i<1 || i>L->size)
    		return -1;
     
    	p = &L->data[i-1];//删除的位置
    	*e = *p;
    	q = &L->data[L->length-1];
    	while(p<=q)
    	{
    		*p = *(p+1);
    		p++;
    	}
    
    	L->length--;
    	return 1;
    }
     
    /** 清除线性表 **/
    void Clear(SqList *L)
    {
    	while(!L->data)
    	{
    		free(L->data);
    	}
    	L->length = 0;
    	L->size = 0;
    }
    
    /** 判断是否为空表 **/
    int Empty(SqList *L)
    {
    	if(L->length == 0)
    		return -1;
    	else
    		return 1;
    }
     
    /** 线性表的长度 **/
    int Length(SqList *L)
    {
    	return L->length;
    }
    
    /** 线性表的大小 **/
    int Size(SqList *L)
    {
    	return L->size;
    }
     
    /** 打印线性表 **/
    void PrintList(SqList *L)
    {
    	int i;
    	for(i=0; i<L->length; i++)
    	{
    		printf("%d ",L->data[i]);
    	}
    	printf("\n");
    }
     
    /**
     * 数据结构 - 线性表的顺序存储
     * 博客：https://vvcat.blog.csdn.net/
     * 博主：威威喵
     **/
    void main()
    {
    	int i;
    	int status = 0;
    	int arr[10] = {3,7,11,6,5,14,36,9,4,19}; 
    	SqList list;
    	ElemType e;
     
    	InitList(&list);
     
    	/** 插入 10 个数据 **/
    	for(i=1; i<=10; i++)
    	{	
    		Insert(&list, arr[i-1], i);
    	}
    	printf("线性表的顺序存储，Length = %d \n", Length(&list));
    	printf("线性表的顺序存储，Size = %d \n", Size(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 在位置 5 插入一个数据 **/ 
    	Insert(&list, 45, 5);
    	Insert(&list, 95, 9);
    	printf("插入元素 45、95，长度为 = %d \n", Length(&list));
    	printf("线性表的顺序存储，Size = %d \n", Size(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 获取下标为 5 的元素的值 **/
    	printf("获取的元素为 %d \n", Get(list, &e, 5));
    	printf("\n");
     
    	/** 删除位置 5 的数据 **/ 
    	Delete(&list, &e, 5);
    	printf("删除元素 45，长度为 = %d \n", Length(&list));
    	printf("线性表的顺序存储，Size = %d \n", Size(&list));
    	PrintList(&list);
    	printf("\n");
     
    	/** 清空数据 **/ 
    	Clear(&list);
    	printf("清除，长度为 = %d \n", Length(&list));
    	printf("线性表的顺序存储，Size = %d \n", Size(&list));
    }

以上代码的运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3][]

线性表的动态扩容，就如上面的例子，刚开始添加了 10 个元素，线性表已经满了，然后每次扩容的个数是 5 个，所以再次插入数据时，会以每 5 个空间大小进行扩容操作。

### 三、学生信息表 ###

以下代码是我个人写的一个练手的线性表顺序存储结构的案例，主要是通过输入学生的用户信息（包括学号、姓名），然后使用线性表来保存起来。

学生信息数据结构与学生表的数据结构如下：

/** 学生信息的数据结构 **/
    typedef struct
    {
    	char number[20]; // 学号
    	char name[30]; // 姓名
    }Student;
    
    /** 学生表的数据结构 **/
    typedef struct
    {
    	Student student[MAXSIZE];
    	int length;
    }SqList;

这里，我使用的是数组的方式，没用动态扩容，其中定义了 MAXSIZE 为 20 个，用于保存学生信息。完整代码如下：

#include <stdio.h>
     
    #define MAXSIZE 20 // 定义存储学生信息的最大容量
    #define OK 1;
    #define ERROR -1;
    typedef int Status;
     
    /**
     * 数据结构 - 线性表的顺序存储
     * 博客：https://vvcat.blog.csdn.net/
     **/
    /** 学生信息的数据结构 **/
    typedef struct
    {
    	char number[20]; // 学号
    	char name[30]; // 姓名
    }Student;
     
    /** 学生表的数据结构 **/
    typedef struct
    {
    	Student student[MAXSIZE];
    	int length;
    }SqList;
     
    /** 初始化 **/
    void Init(SqList *L)
    {
    	L->length = 0;
    }
     
    /** 插入学生信息 **/
    Status Insert(SqList *L, Student stu, int i)
    {
    	int k;
     
    	if(L->length == MAXSIZE)
    	{
    		printf("插入失败，表溢出! \n");
    		return ERROR;
    	}
     
    	if(i<1 || i>L->length+1)// 下标从 0 开始
    	{
    		printf("插入失败，下标异常! \n");
    		return ERROR;
    	}
     
    	/** 如果插入位置不在表尾，移动表中元素 **/
    	if(i <= L->length)
    	{
    		for(k=L->length; k>=i-1; k--)
    		{
    			L->student[k] = L->student[k-1];
    		}
    	}
     
    	L->student[i-1] = stu;
    	L->length++;
     
    //	printf("插入的数据为：学号：%s 姓名：%s \n", stu.number, stu.name);
     
    	printf("插入成功! \n");
    	return OK;
    }
     
    /** 删除学生信息 **/
    Status Delete(SqList *L, int i)
    {
    	int k;
     
    	if(L->length == 0)
    	{
    		printf("表中空数据! \n");
    		return ERROR;
    	}
    	if(i<1 || i>L->length+1)
    	{
    		printf("删除失败，下标异常! \n");
    		return ERROR;
    	}
     
    	if(i <= L->length)
    	{
    		for(k=i-1; k<=L->length; k++)
    		{
    			L->student[k] = L->student[k+1];
    		}
    	}
     
    	printf("删除成功! \n");
     
    	L->length--;
    	return OK;
    }
     
    /** 获取学生信息 **/
    Student Get(SqList *L, int i)
    {
    	if(L->length == 0)
    	{
    		printf("空表! \n");
    	}
    	else if(i<1 || i>L->length)
    	{
    		printf("下标异常! \n");
    	}
    	else
    	{
    		return  L->student[i-1];
    	}
    }
     
    int Length(SqList *L)
    {
    	return L->length;
    }
     
    /** 打印表 **/
    void Print(SqList *L)
    {
    	int i;
    	for(i=0; i<L->length; i++)
    	{
    		printf("学号：%s 姓名：%s \n", L->student[i].number, L->student[i].name);
    	}
    }
     
    void main()
    {
    	int i=1;
    	int n;
     
    	SqList sqList;
    	Student stu, stu2, stu3;
     
    	printf("请输入学生的人数：");
    	scanf("%d", &n);
     
    	/** 初始化 **/
    	Init(&sqList);
     
    	while(i<=n)
    	{
    		printf("学号：");
    		scanf("%s", stu.number);
    		printf("姓名：");
    		scanf("%s", stu.name);
    		
    		Insert(&sqList, stu, i);
    		i++;
    	}
    	Print(&sqList);
    
    	/** 插入数据 **/
    	printf("插入学号：");
    	scanf("%s", stu2.number);
    	printf("插入姓名：");
    	scanf("%s", stu2.name);
    	Insert(&sqList, stu2, 2);
    	Print(&sqList);
     
    	/** 删除数据 **/
    	Delete(&sqList, 2);
    	Print(&sqList);
     
    	/** 获取数据 **/
    	stu3 = Get(&sqList, 1);
    	printf("学号：%s \n", stu3.number);
    	printf("姓名：%s \n", stu3.name);
    }

当然了，你也可以改为**动态扩容**的方式。好了，下面是案例运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4][]

[Link 1]: https://me.csdn.net/smile_Running
[Link 2]: https://blog.csdn.net/smile_Running/column/info/27169
[Link 3]: https://blog.csdn.net/smile_Running/column/info/27335
[Link 4]: https://blog.csdn.net/smile_Running/column/info/42011
[Link 5]: https://blog.csdn.net/smile_running
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/20e7234477604709985067ded8eab241.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/34241e1e4d8146409064fc94680a8605.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/622a946770a842749e0ad1761eaced43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b4ff13a829d646a2af05bb5a66800923.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly92dmNhdC5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/479f9cdff22f45f68ab2d9b6ba1ca147.png