（C语言）数据结构之顺序表， 附简易通讯录项目全源码

  首先说一下数据结构 ， 数据结构就是计算机存储和组织数据的方式。我们熟悉的数组就是一种简单的数据结构。 

  但是由于普通数组在创建时就要把空间固定好，之后就不能直接更改，往往不能满足需求，那么我们就想到，能否创建一种特别的数组，可以按需增删线性表中的元素 ，空间不足时，我们最好可以再进行扩容以供我们使用。所以我们就有了动态顺序表。

  到这里我们就应该知道，其实顺序表本质上还是数组，只是在数组的基础上又进行了封装。那到底该怎么去封装才可以满足我们上面的需求呢？

  既然需要扩容，那肯定少不了动态内存管理，那什么时候去扩容呢？当然是现有空间不够用的时候。所以我们最好实时知道顺序表的现有空间大小和现存数据多少。

  于是我们就有了这样的结构体：

struct SeqList
{
int* arr ; //底层数组
int size ; //目前顺序表中有效数据个数
int capaciti ; //目前顺序表总空间大小
}

  这里需要强调的是，不同数组可以存储不同类型的数据，所以我们顺序表也应该如此 。所以我们这里可以先对数组类型进行重命名。

typedef int SQLDataType ;
​
typedef struct SeqList
{
SQLDataType* arr ; //底层数组
int size ; //目前顺序表中有效数据个数
int capaciti ; //目前顺序表总空间大小
}SQL;

​

这样我们可以通过改变SQLData代表的数据类型来让顺序表储存不同类型的数据。

接下来我们就可以写对于顺序表的操作函数，来便于我们更好地使用顺序表。

首先是顺序表的初始化，最开始的顺序表可以是没有空间的。所以是

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

之后我们要在顺序表了存储数据 ，那我们该用什么函数来开辟空间呢？我们是让这个数组的空间重新开辟（扩容），所以这里我们选择使用realloc函数。我们知道顺序表里的总空间和有效数据个数，所以我们每次添加数据时，都要检查一下空间够不够用，如果够用，直接把数据存进去，否则，我们需要开辟更多空间来存储更多数据。为了不造成过多浪费和提高效率，所以我们在空间不够用时一般就让总空间大小翻一倍（可以自定义）。值得注意的是，如果顺序表空间大小为0 ，那我们应该直接给顺序表开辟一定大小的空间，那这个空间该多大呢？因为我们至少要保证这份空间足以存进去一个数据，所以这里的空间大小可以是我们要存储的一个数据的大小。所以我们就可以写出这样的检查函数：

void SQLCheckCapacity(SQL* ps)
{
if (ps->capacity == ps->size) //有效数据数量等于最大空间时需要开辟空间
{
//用三目操作符判断总空间是否为0，是0则直接开辟空间，不是0则让总空间翻倍
int newcapatroy = ps->capacity == 0 ? sizeof(SQLDataType) : 2 * ps->capacity;
//注意我们的总空间大小表示可存储数据的最大数量，而relloc需要传字节数
SQLDataType* tmp = realloc(ps->arr, newcapatroy * sizeof(SQLDataType));
if (tmp == NULL) //判断空间开辟有没有失败，失败则报错退出
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp; //让数组名指向新开辟的空间
ps->capacity = newcapatroy; //更新总空间数值
}
}

  这样我们就可以写函数来插入数据了，插入又分为头插和尾插。尾插就是在现有数据的后面紧跟着插入数据；头插就是在数组第一个位置插入数据，让原先的数据整体向后移一个位置。注意插入数据之后，原先的size要加一

//尾插
void SQLPushBack(SQL* ps, SQLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size++] = x; //size要加一
}

//头插
void SQLPushFront(SQL* ps, SQLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
int i = ps->size;
for (i = ps->size; i > 0; i–) //原有数据向后移动
{
ps->arr[i] = ps->arr[i – 1];
}
ps->arr[0] = x; //在首位插入数据
ps->size++;
}

  有插入就要有删除，我们还要写头删和尾删。很简单，值得注意的就是我们删除数据可以只更改size， 因为我们只关心有效数据。

void SQLPopBack(SQL* ps)
{
assert(ps);
assert(ps->size);
ps->size–;
}

  size减一后，我们就把最后一个数据看作无效数据。就相当于删除了，不影响我们其他的增删查改操作。头插则是只需让后一个数据覆盖前一个数据，就相当于删掉了第一个数据。

void SQLPopFront(SQL* ps)
{
assert(ps);
assert(ps->size);
int i = 0;
for (i = 0; i < ps->size – 1; i++)
{
ps->arr[i] = ps->arr[i + 1]; //覆盖前一个数据
}
ps->size–;
}

之后我们还要在指定位置插入/删除数据。但是我们到这里已经思路很清晰了。首先我们要判断指定的位置是否合理 ，指定位置其实就是指定数组下标，我们让后面的数据整体向后移，把指定位置空出来，就可以把新数据插进去了 。

void SQLInsert(SQL* ps, int pos, SQLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SQLCheckCapacity(ps);
int i = ps->size;
for (i = ps->size; i > pos; i–)
{
ps->arr[i] = ps->arr[i – 1]; 从后往前后移
}
ps->arr[pos] = x;
ps->size++;
}

同样的，让后面的数据依次往前覆盖，就可以删去指定位置的数据。

void SQLErase(SQL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
int i = pos;
for (i = pos; i < ps->size – 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size–;
}

之后就是查找数据了，我们给定一个数据，要得到这个数据在顺序表中的位置（默认只有一个目标数据）。

int SQLFind(SQL* ps, SQLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (x == ps->arr[i])
{
return i; //返回下标
}
}
return -1; //没找到
}

  最后我们申请的动态内存空间不要忘了释放，同时把指针置为空。如果我们要让函数完成指针置为空的操作，注意需要传二级指针。因为通过二级指针解引用才能真正对让指针置为空，如果传一级指针置为空的操作对象是形参，达不到我们想要的效果。 

void SQLDestroy(SQL** pps)
{
if (*pps->arr)
{
free(*pps->arr);
}
*pps = NULL;
}

  紧接着我们运用以上的顺序表知识做一个简易通讯录。我们要存的数据是联系人信息，联系人信息是一个复杂类型，比如他有姓名 性别 年龄 电话 住址，所以我们需要专门定义一个结构体。

typedef struct PersonInfo
{
char name[NAME_MAX];
char sex[SEX_MAX];
int age;
char tele[TELE_MAX];
char addr[ADDR_MAX];
}PerInfo;

我们要用顺序表储存联系人信息，就要让我们之前写的SQLDataType代表联系人信息这个数据类型。

typedef PerInfo SQLDataType;

同样的，我们可以给顺序表重命名为通讯录

typedef struct SeqList Contact;

接下来我们就要写一系列函数来满足通讯录功能

首先是通讯录的初始化，我们可以直接用前面的顺序表初始化函数。

void ContactInit(Contact* con)
{
SQLInit(con);
}

之后就是添加联系人，我们可以从键盘上获取联系人信息然后用之前写的尾插来完成。

void ContactAdd(Contact* con)
{
PerInfo per;
//获取联系人的姓名 性别 年龄 电话 住址
printf("请输入联系人姓名:\\n");
scanf("%s", per.name);
printf("请输入联系人性别:\\n");
scanf("%s", per.sex);
printf("请输入联系人年龄:\\n");
scanf("%d", &per.age);
printf("请输入联系人电话:\\n");
scanf("%s", per.tele);
printf("请输入联系人住址:\\n");
scanf("%s", per.addr);
SQLPushBack(con, per); //用尾插将新联系人插到通讯录
}

有添加就有删除，我们可以先从键盘获取联系人姓名（或者是电话）来找到联系人的位置，然后用之前写的在指定位置删除顺序表数据的函数来完成。

//通过姓名查找
int FindByName(Contact *con , char name[])
{
int i = 0;
for (i = 0; i < con->size; i++)
{
if (strcmp(con->arr[i].name, name)== 0)
{
return i;//找到了，返回下标
}
}
return -1;//找不到
}

void ContactDel(Contact* con)
{
char name[NAME_MAX];
printf("请输入要删除联系人的姓名:\\n");
scanf("%s", name);
int ret = FindByName(con , name);
if (ret >= 0)
{
SQLErase(con, ret); //运用之前的函数
printf("删除成功!\\n");
}
else
{
printf("该联系人不存在!\\n");
}
}

  之后是写修改联系人信息的函数，同样的，我们需要通过姓名（或电话），找到联系人位置（这个函数已经给出），然后从键盘获取新的数据。

void ContactModify(Contact* con)
{
char name[NAME_MAX];
printf("请输入要修改用户姓名:\\n");
scanf("%s", name);
int ret = FindByName(con, name);
if (ret >= 0)
{
printf("请输入新的姓名:\\n");
scanf("%s", con->arr[ret].name);
printf("请输入新的性别:\\n");
scanf("%s", con->arr[ret].sex);
printf("请输入新的年龄:\\n");
scanf("%d", &con->arr[ret].age);
printf("请输入新的电话:\\n");
scanf("%s", con->arr[ret].tele);
printf("请输入新的住址:\\n");
scanf("%s", con->arr[ret].addr);
printf("修改成功!\\n");
}
else
{
printf("该联系人不存在！\\n");
}

}

然后是查找联系人，我们希望输入一个姓名就获取该联系人的所有信息。

void ContactFind(Contact* con)
{
char name[NAME_MAX];
printf("请输入要查找联系人的姓名:\\n");
scanf("%s", name);
int ret = FindByName(con , name);
if (ret >= 0)
{
printf("%-20s %-20s %-20s %-20s %-20s\\n", "姓名", "性别", "年龄", "电话", "住址");

printf("%-20s %-20s %-20d %-20s %-20s\\n",
con->arr[ret].name,
con->arr[ret].sex,
con->arr[ret].age,
con->arr[ret].tele,
con->arr[ret].addr);
}
else
{
printf("该联系人不存在！\\n");
}
}

接着是展示通讯录函数，把已经保存到通讯录的所有联系人都展示出来

void ContactShow(Contact* con)
{
//表头
printf("%-20s %-20s %-20s %-20s %-20s\\n", "姓名", "性别", "年龄", "电话", "住址");
int i = 0;
for (i = 0; i < con->size; i++)
{
printf("%-20s %-20s %-20d %-20s %-20s\\n",
con->arr[i].name,
con->arr[i].sex,
con->arr[i].age,
con->arr[i].tele,
con->arr[i].addr);
}
}

再然后就是销毁通讯录了，可以直接用我们之前销毁顺序表的方法

void ContactDestroy(Contact* con)
{
SQLDestroy(con);
}

最后我们只需要把这些函数整合一下，写一个菜单，一个简易通讯录就写好了，这里直接奉上源码。

void menu()
{
printf("******************** 通讯录 ********************\\n");
printf("***** 1.添加联系人 ***** 2.删除联系人 ******\\n");
printf("***** 3.修改联系人 ***** 4.查找联系人 ******\\n");
printf("***** 5.展示联系人 ***** 0. 退出 ******\\n");
printf("************************************************\\n");
printf("************************************************\\n");
}

int main()
{
Contact con;
ContactInit(&con);
int a = -1;
do
{
menu();
printf("请选择您的操作：\\n");
scanf("%d", &a);
switch (a)
{
case 1:
ContactAdd(&con);
break;
case 2:
ContactDel(&con);
break;
case 3:
ContactModify(&con);
break;
case 4:
ContactFind(&con);
break;
case 5:
ContactShow(&con);
break;
case 0 :
printf("退出通讯录!\\n");
break;
default:
printf("输入错误，请重新选择\\n");
break;
}
} while (a);

return 0;
}