【数据结构】线性表（一）：顺序表

小鱼儿 2023-02-27 12:28 136阅读 0赞

### 线性表 ###

*   *  1.顺序表
     *   *  1.1 概念及特点
         *  1.2 顺序表图解
         *  1.3 顺序表定义的两种方式
         *   *  静态存储
             *  动态存储
     *  2.部分实现原理解析
     *  3.源代码

> 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：**顺序表**、链表、栈、队列、字符串…

## 1.顺序表 ##

### 1.1 概念及特点 ###

> 1.顺序表概念：  
> 顺序表是用一段**物理地址连续**的存储单元依次存储数据元素的线性结构，一般情况下采用**数组**存储。在数组上完成数据的增删查改。  
> 2.顺序表特点：  
> ①顺序表中的数据是**物理上连续且逻辑上连续**  
> ②可以对顺序表进行**顺序访问**，也可以对顺序表通过下表进行**随机访问**

### 1.2 顺序表图解 ###

![在这里插入图片描述][20200717185924640.png]

### 1.3 顺序表定义的两种方式 ###

> ①静态实现存储  
> ②动态实现存储

#### 静态存储 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]

#### 动态存储 ####

![在这里插入图片描述][20200717190727121.png]

## 2.部分实现原理解析 ##

> 定义表部分（动态存储）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]

--------------------

> 自动扩容部分

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 2]

--------------------

> 常量部分

![在这里插入图片描述][20200717185246242.png]

## 3.源代码 ##

> 以下代码完成了一共17个功能：  
> \[1\] 退出系统  
> \[2\] 展示数据  
> \[3\] 头部增加数据（头插法）  
> \[4\] 尾部增加数据（尾插法）  
> \[5\] 头部删除数据  
> \[6\] 尾部删除数据  
> \[7\] 获取当前最大容量  
> \[8\] 获取当前表大小  
> \[9\] 清空表中数据  
> \[10\] 升序排列表中数据  
> \[11\] 按照值插入数据  
> \[12\] 按照位置插入数据  
> \[13\] 按照值删除数据  
> \[14\] 按照位置删除数据  
> \[15\] 按照值查找位置  
> \[16\] 按照位置查找数据  
> \[17\] 反转表中数据

main函数

> 主要功能为：展示目录以及接收用户做出的选择，并调用相应的函数做出反应

#include "seqlist.h"
    
    int main(){ 
    	SeqList list;
    	SeqListInitial(&list);	//初始化顺序表
    	
    	while (1){ 
    		printf("******************************************************\n");
    		printf("*[1]退出系统 [2]展示数据 *\n");
    		printf("*[3]头部增加数据 [4]尾部增加数据 *\n");
    		printf("*[5]头部删除数据 [6]尾部删除数据 *\n");
    		printf("*[7]获取当前最大容量 [8]获取当前表大小 *\n");
    		printf("*[9]清空表中数据 [10]升序排列表中数据 *\n");
    		printf("*[11]按照值插入数据 [12]按照位置插入数据 *\n");
    		printf("*[13]按照值删除数据 [14]按照位置删除数据 *\n");
    		printf("*[15]按照值查找位置 [16]按照位置查找数据 *\n");
    		printf("*[17]反转表中数据 *\n");
    		printf("******************************************************\n");
    
    		printf("请输入你的选择：");
    		int select = 0;
    		scanf("%d", &select);
    
    		int value = 0;
    		int pos = 0;
    
    
    		switch (select)
    		{ 
    		case 1:
    			printf("Bye!!!!!\n");
    			SeqListDestroy(&list);
    			system("pause");
    			return 0;
    		case 2:
    			SeqListShowData(&list);
    			break;
    		case 3:
    			printf("请输入你要从头部插入表中的数据<以-1结束>：");
    			while (scanf("%d", &value), value != -1){ 
    				SeqListAddDataFromFront(&list, value);
    			}
    			printf("尾插数据完成！\n");
    			break;
    		case 4:
    			printf("请输入你要从尾部插入表中的数据<以-1结束>：");
    			while (scanf("%d", &value), value != -1){ 
    				SeqListAddDataFromBack(&list, value);
    			}
    			printf("尾插数据完成！\n");
    			break;
    		case 5:
    			SeqListDeleteFromFront(&list);
    			printf("头删数据完成！\n");
    			break;
    		case 6:
    			SeqListDeleteFromBack(&list);
    			printf("尾删数据完成！\n");
    			break;
    		case 7:
    			printf("当前表最大容量为：%d\n", SeqListGetCurrentCapacity(&list));
    			break;
    		case 8:
    			printf("当前表大小为：%d\n", SeqListGetCurrentSize(&list));
    			break;
    		case 9:
    			SeqListClearData(&list);
    			printf("表已清空！\n");
    			break;
    		case 10:
    			SeqListSort(&list);
    			printf("表已升序排列！\n");
    			break;
    		case 11:
    			printf("请输入你要按值大小插入表中的数据<以-1结束>：");
    			while (scanf("%d", &value), value != -1){ 
    				SeqListInsertByValue(&list, value);
    			}
    			printf("按值大小插入完毕！\n");
    			break;
    		case 12:
    			printf("请输入你要插入的数据和位置：");
    			scanf("%d%d", &value, &pos);
    			SeqListInsertByPosition(&list, value, pos);
    			break;
    		case 13:
    			printf("你要删除的数据为：");
    			scanf("%d", &value);
    			SeqListDeleteByValue(&list, value);
    			break;
    		case 14:
    			printf("你要删除的数据的位置为：");
    			scanf("%d", &pos);
    			SeqListDeleteByPosition(&list, pos);
    			break;
    		case 15:
    			printf("你要查找的数据为：");
    			scanf("%d", &value);
    			SeqListFindByValue(&list, value);
    			break;
    		case 16:
    			printf("你要查找的位置为：");
    			scanf("%d", &pos);
    			SeqListFindByPosition(&list, pos);
    			break;
    		case 17:
    			SeqListReverse(&list);
    			printf("逆置完成！\n");
    			break;
    		default:
    			printf("输入不合法！\n");
    			break;
    		}
    		system("pause");
    		system("cls");
    	}
    
    
    	SeqListDestroy(&list);
    	system("pause");
    	return 0;
    }

seqlist头文件

> 包含17个函数的函数声明及定义

#ifndef _SEQLIST_H_
    #define _SEQLIST_H_
    #include "common.h"
    /*****************************************************************************/
    //定义常量
    #define DEFAULT_CAPACITY 8 //默认初始化容量
    #define DEFAULT_SIZE 0 //默认初始化大小
    #define AUTO_CAPACITY_GROWTH_MULTIPLE 2 //自动容量增长倍数
    typedef int ET;								//Element Type
    /*****************************************************************************/
    //定义顺序表的结构
    typedef struct SeqList
    { 
    	ET *base;
    	size_t capacity;
    	size_t size;
    
    }SeqList;
    /*****************************************************************************/
    //函数声明
    bool IsFull(SeqList *plist);			//判断表是否满
    bool IsEmpty(SeqList *plist);			//判断表是否空
    void SeqListInitial(SeqList *plist);	//初始化顺序表
    void SeqListDestroy(SeqList *plist);	//销毁顺序表
    void SeqListShowData(SeqList *plist);	//展示数据
    void SeqListAddDataFromBack(SeqList *plist, ET value);		//尾插数据
    void SeqListAddDataFromFront(SeqList *plist, ET value);		//头插数据
    void SeqListDeleteFromFront(SeqList *plist);	//头删数据
    void SeqListDeleteFromBack(SeqList *plist);		//尾删数据
    size_t SeqListGetCurrentCapacity(SeqList *plist);	//获取当前最大容量
    size_t SeqListGetCurrentSize(SeqList *plist);		//获取当前表大小
    void SeqListClearData(SeqList *plist);			//清空表中数据
    void SeqListSort(SeqList *plist);				//升序排列数据
    void SeqListInsertByValue(SeqList *plist, ET value);				//按照数值大小插入数据
    void SeqListInsertByPosition(SeqList *plist, ET value, int pos);	//按照位置插入数据
    void SeqListDeleteByValue(SeqList *plist, ET value);		//按照数值删除数据
    void SeqListDeleteByPosition(SeqList *plist, int pos);		//按照位置删除数据
    void SeqListFindByValue(SeqList *plist, ET value);		//获取某个值第一次出现的下标
    void SeqListFindByPosition(SeqList *plist, int pos);	//获取某个位置上面的值
    void SeqListReverse(SeqList *plist);				//逆置顺序表
    /*****************************************************************************/
    //函数定义
    bool IsFull(SeqList *plist){ 
    	assert(plist != NULL);
    	if (plist->size == plist->capacity){ 
    		return true;
    	}
    	return false;
    }
    bool IsEmpty(SeqList *plist){ 
    	if (plist->size == 0){ 
    		return true;
    	}
    	return false;
    }
    bool Increment(SeqList *plist){ 
    	assert(plist != NULL);
    
    	ET* new_base = (ET*)realloc(plist->base, sizeof(ET)* AUTO_CAPACITY_GROWTH_MULTIPLE * plist->capacity);
    	if (new_base == NULL){ 
    		printf("扩容失败！\n");
    		return false;
    	}
    
    	plist->base = new_base;
    	plist->capacity *= AUTO_CAPACITY_GROWTH_MULTIPLE;
    	return true;
    }
    void SwapData(ET* a, ET* b){ 
    	ET temp = *a;
    	*a = *b;
    	*b = temp;
    }
    void SeqListInitial(SeqList *plist){ 
    	assert(plist != NULL);
    	plist->capacity = DEFAULT_CAPACITY;
    	plist->base = (ET*)malloc(sizeof(ET)*plist->capacity);
    	plist->size = DEFAULT_SIZE;
    }
    void SeqListDestroy(SeqList *plist){ 
    	assert(plist != NULL);
    	free(plist->base);
    	plist->base = NULL;
    	plist->capacity = plist->size = 0;
    }
    void SeqListShowData(SeqList *plist){ 
    	assert(plist != NULL);
    	printf("顺序表中的数据有：");
    	for (size_t i = 0; i < plist->size; i++)
    	{ 
    		printf("%d ", plist->base[i]);
    	}
    	puts("\n");
    }
    void SeqListAddDataFromBack(SeqList *plist, ET value){ 
    	assert(plist != NULL);
    	if (IsFull(plist) && !Increment(plist)){ 
    		printf("自动扩容失败导致无法加入数据！\n");
    		return;
    	}
    	plist->base[plist->size] = value;
    	plist->size++;
    
    }
    void SeqListAddDataFromFront(SeqList *plist, ET value){ 
    	assert(plist != NULL);
    	if (IsFull(plist) && !Increment(plist)){ 
    		printf("自动扩容失败导致无法加入数据！\n");
    		return;
    	}
    	for (size_t i = plist->size ; i > 0; i--)
    	{ 
    		plist->base[i] = plist->base[i - 1];
    	}
    	plist->base[0] = value;
    	plist->size++;
    	
    	
    }
    void SeqListDeleteFromFront(SeqList *plist){ 
    	assert(plist != NULL);
    	if (IsEmpty(plist)){ 
    		printf("表已空！\n");
    		return;
    	}
    	for (size_t i = 0; i < plist->size - 1; i++)
    	{ 
    		plist->base[i] = plist->base[i + 1];
    	}
    	plist->size--;
    }
    void SeqListDeleteFromBack(SeqList *plist){ 
    	assert(plist != NULL);
    	if (IsEmpty(plist)){ 
    		printf("表已空！\n");
    		return;
    	}
    	plist->size--;
    }
    size_t SeqListGetCurrentCapacity(SeqList *plist){ 
    	assert(plist != NULL);
    	return plist->capacity;
    }
    size_t SeqListGetCurrentSize(SeqList *plist){ 
    	assert(plist != NULL);
    	return plist->size;
    }
    void SeqListClearData(SeqList *plist){ 
    	assert(plist != NULL);
    	plist->size = 0;
    }
    void SeqListSort(SeqList *plist){ 
    	for (size_t i = 0; i < plist->size; i++)
    	{ 
    		for (size_t j = i; j < plist->size; j++)
    		{ 
    			if (plist->base[i]>plist->base[j]){ 
    				SwapData(&plist->base[i], &plist->base[j]);
    			}
    		}
    	}
    }
    void SeqListInsertByValue(SeqList *plist, ET value){ 
    	SeqListSort(plist);
    	if (IsFull(plist) && !Increment(plist)){ 
    		printf("自动扩容失败导致无法加入数据！\n");
    		return;
    	}
    	int index = 0;
    	while (value < plist->base[index] && index < plist->size){ 
    		index++;
    	}
    	for (size_t i = plist->size; i >index; i--)
    	{ 
    		plist->base[i] = plist->base[i - 1];
    	}
    	plist->base[index] = value;
    	plist->size++;
    
    }
    void SeqListInsertByPosition(SeqList *plist, ET value, int pos){ 
    	assert(plist != NULL);
    	if (pos <= 0 || pos >= plist->size + 2){ 
    		printf("插入位置不合法！\n");
    		return;
    	}
    	if (IsFull(plist) && !Increment(plist)){ 
    		printf("自动扩容失败导致无法加入数据！\n");
    		return;
    	}
    	for (size_t i = plist->size; i >= pos; i--)
    	{ 
    		plist->base[i] = plist->base[i - 1];
    	}
    	plist->base[pos - 1] = value;
    	plist->size++;
    	printf("插入成功！\n");
    }
    void SeqListDeleteByValue(SeqList *plist, ET value){ 
    	assert(plist != NULL);
    	if (IsEmpty(plist)){ 
    		printf("表已空！\n");
    		return;
    	}
    	size_t index = 0;
    	while (value != plist->base[index] && index < plist->size){ 
    		index++;
    	}
    	if (index == plist->size){ 
    		printf("表中没有%d这个数据！\n", value);
    		return;
    	}
    	for (size_t i = index; i < plist->size; i++)
    	{ 
    		plist->base[i] = plist->base[i + 1];
    	}
    	plist->size--;
    	printf("删除成功！\n");
    }
    void SeqListDeleteByPosition(SeqList *plist, int pos){ 
    	assert(plist != NULL);
    	if (IsEmpty(plist)){ 
    		printf("表已空！\n");
    		return;
    	}
    	pos -= 1;
    	if (pos < 0 || pos >= plist->size ){ 
    		printf("删除位置不合法！\n");
    		return;
    	}
    	for (size_t i = pos; i < plist->size; i++)
    	{ 
    		plist->base[i] = plist->base[i + 1];
    	}
    	plist->size--;
    	printf("删除成功！\n");
    }
    void SeqListFindByValue(SeqList *plist, ET value){ 
    	assert(plist != NULL);
    	int pos = -1;
    	for (size_t i = 0; i < plist->size; i++)
    	{ 
    		if (value == plist->base[i]){ 
    			pos = i;
    			break;
    		}
    	}
    	if (-1 == pos){ 
    		printf("找不到%d这个数据！\n", value);
    	}
    	else{ 
    		printf("%d这个数据第一次出现的下标为：%d\n", value, pos + 1);
    	}
    }
    void SeqListFindByPosition(SeqList *plist, int pos){ 
    	assert(plist != NULL);
    	if (pos <= 0 || pos >= plist->size + 1){ 
    		printf("查找位置不合法！\n");
    		return;
    	}
    	printf("%d位置上的数据为：%d\n", pos, plist->base[pos - 1]);
    }
    void SeqListReverse(SeqList *plist){ 
    	assert(plist != NULL);
    	size_t right = 0, left = plist->size - 1;
    	while (right < left){ 
    		SwapData(&plist->base[right], &plist->base[left]);
    		right++, left--;
    	}
    }
    
    #endif /* _SEQLIST_H_ */

common头文件

> 定义一些常用的头文件

#ifndef _COMMOM_H_
    #define _COMMOM_H_
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <stdbool.h>
    #include <Windows.h>
    #pragma warning(disable:4996)
    
    #endif /* _COMMOM_H_ */

[20200717185924640.png]: /images/20230209/d3877c1ca8a140cba86c09801fae4c2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20230209/0718ef574c474a20a0e61c3ab93102df.png
[20200717190727121.png]: /images/20230209/0f4ba059d4b143599453c8de1f4484b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]: /images/20230209/773676946dc94b7a9b9649d1ebb10a4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 2]: /images/20230209/69ca56069541409a82bf82f1d96ca3e3.png
[20200717185246242.png]: /images/20230209/c6b341baa3a14e17bd320ca9a67cd543.png