数据结构（初阶2.顺序表）

文章目录

一、线性表

二、顺序表

　2.1 概念和结构

　2.2 分类

　　　　2.2.1 静态顺序表

　　　　2.2.2 动态顺序表

　2.3动态顺序表的实现

　　1.SeqList.h

　　2.SeqList.c

　　　　打印顺序表

　　　　初始化

　　　　销毁

　　　　增容

　　　　尾插

　　　　头插

　　　　在指定位置之前插入数据

　　　　尾删

　　　　头删

　　　　在指定位置删除数据

　　3.test.c

一、线性表

线性表（ linear list ）是n个具有相同特性的数据元素的有限序列。

线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

逻辑结构（认为想象出来的数据的组织形式）：都是线性的
物理结构（数据在内存上的存储形式）：不一定是线性的

二、顺序表

2.1 概念和结构

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

那么数组和顺序表的区别是什么？

下面可以进行一个很形象的类比：

顺序表是对数组进行封装：结构体
定义已经知道数组的大小： int arr【3】= {1，2，3}；
定义未知道数组的大小： int*arr；

2.2 分类

2.2.1 静态顺序表

上图中可以发现我们重新定义了 typedef int SLDataType，为什么？

比如当我们在测试代码中有 100000行代码，1000+会定义整型变量 int，当要把这 1000+ 的代码部分改成 char 类型时，如果逐个将这些代码找出一句句修改会非常麻烦而且工作量巨大；而当 typedef int SLDataType之后，我们只需将其改成 typedef char SLDataType ，遍能一键替换为 char 或者想要修改的位置。

2.2.2 动态顺序表

2.3动态顺序表的实现

(注意：1.当我们每实现一个方法之后须测试一下，切记写完所有方法才测试，避免出现差错；

2.在调用过程中分清传值和传址的区别；

传值：形参是实参的值的拷贝，实参和形参指向的是两块不同的地址，但保存的数据是一样的

传址：形参指向的是实参指向的地址)

1.SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义动态顺序表结构
typedef int SLDatatype;

typedef struct SeqList {
	SLDatatype* arr;
	int capacity; //空间大小
	int size;     //有效数据个数
}SL;

//typedef struct SeqList SL;

//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);

//打印顺序表
void SLPrint(SL* ps);

//插入数据
void SLPushBack(SL* ps, SLDatatype x);
void SLPushFront(SL* ps, SLDatatype x);

//删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);

2.SeqList.c

打印顺序表

void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

初始化

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

销毁

void SLDestory(SL* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);

	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

增容

当size == capacity 时，说明顺序表满了，空间不足，先增容，再插入；

增容一般是成倍数的增加（增容的操作本身就有一定的程序性能的消耗，若频繁的增容会导致程序效率底下），所以 ”一次增容一个就没有空间浪费“ 这种说法是错误的。

增容分两种情况： 1.连续空间足够，直接扩容

2.连续空间不够，1）重新找一块地址，分配足够的内存

2）拷贝数据到新的地址

3）销毁就地址

void SLCheckCapacity(SL* ps)
{
	//判断空间是否充足
	if (ps->size = ps->capacity)
	{
		//增容//0*2 = 0
		//若capacity为0，给个默认值，否则×2倍
		int newCapacity = ps->arr == 0 ? 4 : 2 * ps->capacity;
		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));
		if (tmp = NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}

尾插

空间充足：将数据插入 size 指向的位置，size++；

void SLPushBack(SL* ps, SLDatatype x)
{
	assert(ps);//等价于assert(ps != NULL)


	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

头插

void SLPushFront(SL* ps, SLDatatype x)
{
	assert(ps);

	//判断空间是否足够
	SLCheckCapacity(ps);

	//整体数据往后移一位,从后往前移
	for (int i = ps->size;i >0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}

	//将数据插入下标为0的位置
	ps->arr[0] = x;
}

在指定位置之前插入数据

void SLInsert(SL* ps, SLDatatype x, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	//       头插          尾插 

	//pos及以后的数据整体向后移动一位,从后往前移，与头插的方法类似
	for (int i =ps->size ; i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}

	//将数据插入下标为pos的位置
	ps->arr[pos] = x;
	ps->size++; //不要忘记这一步
}

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//顺序表为空，不可删除

	ps->size--;
}

头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);//顺序表为空，不可删除

	//数据整体向前移动一位，从前往后移
	for (int i = 0; i < ps->size - 1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;

}

在指定位置删除数据

void SLDelete(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);//顺序表为空，不可删除
	assert(pos >= 0 && pos <= ps->size);
	//       头删          尾删 

	//pos及以后的数据整体向前移动一位,从前往后移，与SLInsert的方法类似
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

3.test.c

#include "SeqList.h"

void SLtest01()
{
	SL s;
	SLInit(&s);

	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 10);
	SLPushBack(&s, 11);
	SLPushBack(&s, 12);
	printf("尾插后的数据：");
	SLPrint(&s);

	printf("头插后的数据：");
	SLPushFront(&s, 4);
	SLPrint(&s);

	printf("在下标为2的位置插入9后的数据：");
	SLInsert(&s, 9, 2);
	SLPrint(&s);

	printf("尾删后的数据：");
	SLPopBack(&s);
	SLPrint(&s);

	printf("头插后的数据：");
	SLPopFront(&s);
	SLPrint(&s);

	printf("删除下标为3的数据：");
	SLDelete(&s, 3);
	SLPrint(&s);

	SLDestroy(&s);
}

int main()
{
	SLtest01();	
	return 0;
}