基于C语言的数据结构--顺序表讲解及代码函数实现展示

        本篇文章是数据结构的开篇，所以我们先来了解一下什么是数据结构。

什么是数据结构

        数据结构是由“数据”和“结构”两个词组合而来，自然要以两个词分别去阐述。

        首先，什么是数据？数据(data)是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的原始素材。 数据可以是连续的值，比如声音、图像，称为模拟数据；也可以是离散的，如符号、文字，称为数字数据。 在计算机系统中，数据以二进制信息单元0、1的形式表示。

        什么是结构？当我们想要使用大量同一类型数据的时候，通过手动定义大量的独立的变量对程序来说可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。这样的结构可以大大提高我们寻找数据的效率。

        由此我们引出数据结构的概念：数据结构是计算机储存、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反应的是数据的内部构成，即数据由哪一部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

1）能够存储数据（如顺序表、链表等结构）

2）存储的数据能够⽅便查找

为什么需要数据结构

        在如今时代化的商业餐饮总是人山人海，不借助排队的方式来管理客户，会导致客户的就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能导致数据丢失、操作数据困难、野指针等情况。通过数据结构，我们能够有效地将数据组织和管理在一起。按照我们的方式任意地对数据进行增删查改等操作。

        我们之前在C语言中讲到的数组就是最基础的数据结构，尽管有了数组，但是最基础的数据结构已经不能完全满足复杂算法的实现，因此慢慢发展出了数据结构。

        示例：假定数组有10个空间，已经使⽤了5个，向数组中插⼊数据步骤：求数组的⻓度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这⾥是否要判断数组是否满了，满了还能继续插⼊吗）.....假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率。

线性表的概念及结构

        线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

注意：本章只讲顺序表，后续会继续讲解其他线性结构。

顺序表

        顺序表的底层结构其实就是数组，是通过对数组的封装，实现了常⽤的增删改查等接⼝。

        顺序表分为静态顺序表和动态顺序表，两者的区别在于它们的空间容量是否固定。静态顺序表使用的是定长数组储存元素，动态顺序表则是通过动态内存管理的方式对空间容量进行按需申请，因为静态顺序表存在致命缺陷（空间给少了不够用，给多了又造成空间浪费），因此我们通常使用动态顺序表。

下面我将附上函数声明和函数实现代码，测试代码请各位按自己喜好自主补充：

        注意：typedef int sqDataType的意义是方便后期更换类型时快速便捷，并且不会影响到其他无关的相同类型。

sqlist.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int sqDataType;
//定义结构体
typedef struct SQlist 
{
	sqDataType* arr;
	int size;
	int capacity;
}SQL;


//初始化声明
void InitSQL(SQL* s);
//动态开辟内存声明
void Dyopen(SQL* s);
//动态扩容
void check_Dyexpand(SQL* s);
//打印函数
void SQLprint(SQL* s);
//头插函数声明
void HeadInsert(SQL* s, sqDataType num);
//尾插函数声明
void TailInsert(SQL* s, sqDataType num);
//任意位置插入的函数声明
void SQLinsert(SQL* s, int pos, sqDataType num);

//头删函数声明
void HeadDelete(SQL* s);
//尾删函数声明
void TailDelete(SQL* s);
//任意位置删除的函数声明
void SQLdelete(SQL* s, int pos, sqDataType num);

//查找函数声明
int SQLsearch(SQL* s, sqDataType num);
//修改函数声明
void SQLedit(SQL* s,int pos,sqDataType num);

//顺序表销毁函数
void SQLdestroy(SQL* s);

sqlist.c

#include "sqlist.h"


//初始化
void InitSQL(SQL* s)
{
	s->arr = NULL;
	s->capacity = s->size = 0;
	printf("初始化完成\n");
}

//动态开辟内存
void Dyopen(SQL* s)
{
	assert(s);
	sqDataType* ps = (sqDataType*)malloc(sizeof(sqDataType) * 1);
	if (ps == NULL)
	{
		perror("malloc");
		return 1;
	}
	s->arr = ps;
	s->capacity = 1;
	printf("开辟成功\n");
}

//动态扩容判断函数
void check_Dyexpand(SQL* s)
{
	assert(s);
	if (s->size == s->capacity)
	{
		int newcapacity = (s->capacity == 0) ? 1 : (2 * s->capacity);
		sqDataType* ps = (sqDataType*)realloc(s->arr, sizeof(sqDataType) * newcapacity);
		s->capacity = newcapacity;
		printf("扩容成功\n");
	}
	else
	{
		printf("本次无需扩容\n");
	}
}

//顺序表打印函数
void SQLprint(SQL* s)
{
	assert(s);
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->arr[i]);
	}
}


//头插函数
void HeadInsert(SQL *s,sqDataType num)
{
	assert(s);
	check_Dyexpand(&s);
	for (int i = s->size; i > 0; i--)
	{
		s->arr[s->size] = s->arr[s->size - 1];
	}
	s->arr[0] = num;
	++(s->size);
}

//尾插函数
void TailInsert(SQL* s,sqDataType num)
{
	assert(s);
	check_Dyexpand(&s);
	s->arr[s->size++] = num;
}

//任意位置插入的函数
void SQLinsert(SQL* s, int pos, sqDataType num)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);
	check_Dyexpand(&s);
	for (int i = s->size - 1; i >= pos; i--)
	{
		s->arr[i + 1] = s->arr[i];
	}
	s->arr[pos] = num;
	s->size++;
	printf("插入成功\n");
}

//头删函数
void HeadDelete(SQL* s)
{
	assert(s);
	assert(s->size);
	if (s->size > 0)
	{
		int i = 0;
		for (i = 1; i < s->size; i++)
		{
			s->arr[i - 1] = s->arr[i];
		}
		--(s->size);
		printf("删除成功\n");
	}
	else
	{
		printf("顺序表为空，删除失败");
		return 1;
	}
	
}

//尾删函数
void TailDelete(SQL* s)
{
	assert(s);
	assert(s->size);
	if (s->size > 0)
	{
		s->size--;
		printf("删除成功\n");
	}
	else
	{
		printf("顺序表为空，删除失败");
		return 1;
	}
}

//任意位置删除的函数
void SQLdelete(SQL* s, int pos, sqDataType num)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);//访问s->size位置是越界的
	check_Dyexpand(&s);
	for (int i = pos-1; i < s->size - 1; i++)
	{
		s->arr[i] = s->arr[i + 1];
	}
	s->size--;
	printf("删除成功\n");
}

//查找函数
int SQLsearch(SQL* s, sqDataType num)
{
	assert(s);
	for (int i = 0; i < s->size; i++)
	{
		if (s->arr[i] == num)
		{
			return i;
		}
		else
		{
			return -1;
		}
	}
}


//修改函数
void SQLedit(SQL* s, int pos, sqDataType num)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);
	s->arr[pos - 1] = num;
	printf("修改成功\n");
}

//顺序表销毁函数
void SQLdestroy(SQL* s)
{
	if (s->arr != NULL)
	{
		free(s->arr);
		s->arr = NULL;
	}
	s->capacity = s->size = 0;
	printf("销毁成功\n");
}