数据结构：顺序表专题

1. 数据结构相关概念

1.1什么是数据结构

数据结构是由“数据”和“结构”两词组合⽽来。

什么是数据？

常⻅的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等 等）、⽹⻚⾥⾁眼可以看到的信息（⽂字、图⽚、视频等等），这些都是数据

什么是结构？

当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性 ⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的 ⽅式。

想要找到草原上名叫“咩咩”的⽺很难，但是从⽺圈⾥找到“咩咩”就很简单，⽺圈这样的结构有效将 ⽺群组织起来。

概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系 的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构。

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

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

为什么需要数据结构？

如图中所⽰，不借助排队的⽅式来管理客⼾，会导致客⼾就餐感受差、等餐时间⻓、餐厅营业混乱等 情况。同理，程序中如果不对数据进⾏管理，可能会导致数据丢失、操作数据困难、野指针等情况。 通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操作。  

最基础的数据结构：数组。

 【思考】有了数组，为什么还要学习其他的数据结构？

假定数组有10个空间，已经使⽤了5个，向数组中插⼊数据步骤：

求数组的⻓度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这⾥是 否要判断数组是否满了，满了还能继续插⼊吗）.....

假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率。

结论：最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。

2.顺序表

2.1顺序表的概念及结构

2.1.1线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 案例：蔬菜分为绿叶类、⽠类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合。

2.2顺序表分类

• 顺序表和数组的区别

         ◦ 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等功能。

• 顺序表分类

 2.2.1 静态顺序表

typedef struct Slist
{
	int arr[100];
	int size;       //数组中元素个数
}SL;

静态顺序表中，数组的大小是固定的。

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费

2.2.2 动态顺序表

typedef struct Slist
{
	int* arr;       //由于不知道数组多大空间，所以先定义一个指向起始位置的指针
	int size;       //数组中有效元素的个数，初始大小为0
	int OverSpaace; //数组的整个空间大小，初始大小为0
}SL;

动态顺序表的空间就比较灵活，可以用动态内存管理函数开辟空间，从而改变OverSpaace的值。

所以我们接下来主要来探究动态顺序表元素的增删查改。

3.顺序表元素的增删查改

3.1动态顺序表的初始化

定义好顺序表的结构后，我们先给结构体成员赋一个初始值。

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

注意：传参的时候应该传递结构体的地址，因为初始化我们要改变结构体成员的值，所以这里要传结构体的地址。

3.2动态顺序表的增容

我们初始化完顺序表空间大小是0，所以如果想往顺序表中添加元素，在添加元素之前就应该对顺序表增容。

void SlExpansion(SL* ps)
{
	if (ps->size == ps->OverSpaace)
	{
		int NewOverSpaace = (ps->OverSpaace == 0) ? 4 : 2 * ps->OverSpaace;
		DataType* tmp = (DataType*)realloc(ps->arr, sizeof(DataType) * NewOverSpaace);
		if (tmp == NULL)
		{
			perror("realloc");
			return ;
		}
		ps->arr = tmp;
		ps->OverSpaace = NewOverSpaace;
	}
}

这里我们先判断空间是否够用，如果空间不够用就进行增容。我们用realloc函数进行增容。增容后的空间大小在重新赋值给OverSpaace。

3.3动态顺序表的打印

动态顺序表的打印和数组的打印是一样的。

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

3.4在顺序表的尾部添加数据

void AddTail(SL* ps, DataType x)
{
	assert(ps);
	SlExpansion(ps);
	ps->arr[ps->size++] = x;
 
}

注意：在添加数据之前要判断需不需要增容。插入完成后有效数据个数+1（size++）

3.5在顺序表的头部添加数据

void AddHead(SL* ps, DataType x)
{
	assert(ps);
	SlExpansion(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

在头部添加数据之前，我们要把数组中的元素依次往后移动一个单位。然后再把数据插入到第一个节点中。移动的时候要注意是从后往前移动。插入完成后有效数据个数+1（size++）

3.6删除头部的数据

void DelHead(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

删除头部的数据只需要把数组中的元素依次往前移动一位，这样第一个元素就被挤出去了，最后size--。

3.7删除尾部数据

void DelTail(SL* ps)
{
	assert(ps);
	ps->size--;
}

删除尾部数据直接size--就可以，这样尾部的数据也被挤出去了。

3.8指定位置插入数据

void SpeLocInsert(SL* ps, int loc, int x)
{
	assert(ps);
	assert(loc >= 0 && loc <= ps->size);
	for (int i = ps->size; i > loc; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[loc] = x;
	ps->size++;
}

把要插入数据的位置之后的元素依次往后移动一个单位，然后再把想插入的数据插入到指定位置中。插入完成后有效数据个数+1（size++）。

3.9指定位置删除数据

void SpeLocDel(SL* ps, int loc)
{
	assert(ps);
	for (int i = loc; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

把要删除数据的位置之后的元素依次往前一定一个单位，最后size--。

3.10查找数据是否存在

int fund(SL* ps, int x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

遍历数组，如果要查找的数据存在就返回该元素的下标，否则返回一个小于0的数。

这样，顺序表的增删查改任务就完成了，哪学完之后有什么用呢？

我们下面实现一个手机通讯录的小项目。

4.手机通讯录的实现

手机通讯录其实就是一个顺序表，顺序表的每一个成员都是一个结构体，结构体中包含联系人的

名字、性别、年龄、电话、地址等信息，只不过我们之前建立的顺序表里存储的是整形数据，而通讯录里存储的是结构体类型而已。

所以我们还要创建一个结构体来存储联系人信息。

#define MAX_NAME 20
#define MAX_GENDER 10
#define MAX_PHONE 20
#define MAX_ADDR 30
typedef struct contacts 
{
	char name[MAX_NAME];
	char gender[MAX_GENDER];
	int age;
	char phone[MAX_PHONE];
	char addr[MAX_ADDR];
}contacts;

 既然通讯录就是顺序表，那我们可以给顺序表改类型一个名字

struct SList;
typedef struct SList CON;

4.1功能要求

1）⾄少能够存储100个⼈的通讯信息

2）能够保存⽤⼾信息：名字、性别、年龄、电话、地址等

3）增加联系⼈信息

4）删除指定联系⼈

5）查找制定联系⼈

6）修改指定联系⼈

7）显示联系⼈信息

4.2通讯录初始化

void ContactInit(CON* con)
{
	SlInit(con);
}

通讯录的初始化也就是顺序表的初始化，我们直接调用之前的顺序表初始化函数即可。

4.3添加联系人

void AddContact(CON* con)
{
	contacts f;
	printf("请输入要添加的联系人姓名：");
	scanf("%s", f.name);
	printf("请输入要添加的联系人性别：");
	scanf("%s", f.gender);
	printf("请输入要添加的联系人年龄：");
	scanf("%d", &f.age);
	printf("请输入要添加的联系人电话：");
	scanf("%s", f.phone);
	printf("请输入要添加的联系人住址：");
	scanf("%s", f.addr);
	AddTail(con, f);
}

我们先定义一个联系人结构体，再添加联系人信息，最后调用尾插函数，把联系人尾插到通讯录中。

4.4查看某联系人是否存在

int FundByContact(CON* con, char name[])
{
	assert(con);
	for (int i = 0; i < con->size; i++)
	{
		if (0 == strcmp(con->arr[i].name, name))
		{
			return i;
		}
	}
	return -1;
}

遍历数组，如果遍历到了要查找的联系人的名字，就返回数组成员下标，否则返回一个小于0的数。

4.5删除联系人

void DelContact(CON* con)
{
	assert(con);
	char name[MAX_NAME];
	printf("请输入要删除的联系人姓名：\n");
	scanf("%s", name);
	int fund = FundByContact(con, name);
	if (fund < 0)
	{
		printf("该联系人不存在");
	}
	SpeLocDel(con, fund);
}

调用FundByContact函数，如果要删除的联系人存在，那么返回数组下标，在调用SpeLocDel函数，删除改下表对应的联系人。

4.6打印通讯录

void PrintContact(CON* con)
{
	printf("姓名  性别  年龄  电话  住址\n");
	for (int i = 0; i < con->size; i++)
	{
		printf("%s %s %d %s %s\n",
			con->arr[i].name,
			con->arr[i].gender,
			con->arr[i].age,
			con->arr[i].phone,
			con->arr[i].addr);
	}
}

遍历数组，打印结构体成员信息。

4.7修改联系人

void ModifyContact(CON* con)
{
	char name[MAX_NAME];
	printf("请输入要修改的联系人姓名");
	scanf("%s", name);
	int fund = FundByContact(con, name);
	if (fund < 0)
	{
		printf("该联系人不存在");
	}
	printf("请输入新的联系人姓名:\n");
	scanf("%s", con->arr[fund].name);
 
	printf("请输入新的联系人性别:\n");
	scanf("%s", con->arr[fund].gender);
 
	printf("请输入新的联系人年龄:\n");
	scanf("%d", &con->arr[fund].age);
 
	printf("请输入新的联系人电话:\n");
	scanf("%s", con->arr[fund].phone);
 
	printf("请输入新的联系人住址:\n");
	scanf("%s", con->arr[fund].addr);
 
}

如果要修改的联系人存在，用fund接收返回的下标，再通过下标修改联系人信息。

4.7查找联系人

void FundContact(CON* con)
{
	assert(con);
	char name[MAX_NAME];
	printf("请输入要查找的联系人姓名:\n");
	scanf("%s", name);
	int fund = FundByContact(con, name);
	if (fund < 0)
	{
		printf("该联系人不存在");
	}
	printf("%s %s %d %s %s\n",
	con->arr[fund].name,
	con->arr[fund].gender,
	con->arr[fund].age,
	con->arr[fund].phone,
	con->arr[fund].addr);
}

如果要查找的联系人存在，打印该联系人的信息。

至此，通讯录的基本功能就实现了。感谢大家观看。