目录
顺序表概念
顺序表有三种写法
时间不浪费，空间无所谓：直接定义一个足够大的数组
空间不浪费，时间无所谓：采用动态数组，用一个开一个
时间空间均衡：也就是所谓的扩容
每次申请内存是之前内存的1.5倍（如果n的0.5倍小于或者等于1），那么是当前元素个数加一
不超过0.5倍数据量的空间浪费换取超过0.5倍数据量的时间节约
1.准备
包含一下用到的头文件，准备一个数据结构体
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct student
{
char name[20];
int age;
double score;
}stu;
int curSize; //记录当前元素个数
int capacity; //记录当前容量
stu* pArr; //指向当前内存段的首地址
2.初始化
把里面的值初始化为0，指针初始化为空
void initData()
{
curSize = 0;
capacity = 0;
pArr = NULL;
}
3.插入数据
插入数据就不多说了，详解代码在下面，这里主要图解一下扩容问题
void pushData(stu* inserData)
{
//需要开内存
if (capacity <= curSize)
{
//计算新开内存
//右移一位相当于除以2
capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;
stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存
assert(pNew); //防御性编程
if (pArr)
{
//把pArr中的数据拷贝到新开内存段中
memcpy(pNew, pArr, sizeof(stu) * curSize);
//释放原有内存段
free(pArr);
}
//pArr指向新开内存段
pArr = pNew;
}
//inserData放入数组中
memcpy(pArr + curSize, inserData, sizeof(stu));
//元素个数加一
curSize++;
}
4.浏览数据
遍历数据，显示出容量和当前元素的比，可轻易看出空间利用率
void watchData()
{
printf("pArr[%d][%d]:\n", curSize,capacity);
for (int i = 0; i < curSize; i++)
{
printf("%s-%d-%.2f\n",
pArr[i].name, pArr[i].age, (pArr+i)->score);
//两种写法，自由变换
}
printf("\n");
}
5.查找数据
简单的查找程序，找到了返回该位置的下标
int findData(stu* findData)
{
for (int i = 0; i < curSize; i++)
{
if (
0 == strcmp((pArr+i)->name,findData->name)
&& pArr[i].age == findData->age
&& pArr[i].score == findData->score
)
{
return i;
}
}
return -1;
}
6.删除数据
这里是牺牲了一部分空间，来获得时间效率的提高
void delData(stu* delData)
{
int index = findData(delData);
//找到了
if (index != -1)
{
if(curSize == 1) //只有一个元素时
{
free(pArr);
initData();
}
else
{
//申请新空间
stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));
assert(pNew);
if (index != 0)
{
//该元素前面有元素,把前面元素拷贝到新内存段
memcpy(pNew, pArr, sizeof(stu) * index);
}
if (index != curSize - 1)
{
//该元素后面又元素，把后面元素拷贝到新内存段
memcpy(pNew + index, pArr + index + 1,
sizeof(stu) * (curSize - 1 - index));
}
free(pArr); //释放原来的空间
pArr = pNew; //pArr指向新数据
curSize--;
capacity = curSize;
}
}
else
{
printf("没找到，删除失败!\n");
}
}
7.修改数据
这里主要是利用了查找函数的特性来完成
void modify(stu* srcData, stu* dscData)
{
int index = findData(srcData);
if (index != -1)
{
memcpy(pArr + index, dscData, sizeof(stu));
}
else
{
printf("修改失败，没找到\n");
}
}
8.综合代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct student
{
char name[20];
int age;
double score;
}stu;
int curSize; //记录当前元素个数
int capacity; //记录当前容量
stu* pArr; //指向当前内存段的首地址
//初始化
void initData();
//insertData
void pushData(stu* inserData);
//浏览数据
void watchData();
//查找数据
int findData(stu* findData);
//删除数据
void delData(stu* delData);
//修改数据
void modify(stu* srcData, stu* dscData);
int main()
{
initData();
stu d[5] =
{
{ "关羽", 18, 18.67 },
{ "张飞", 28, 28.67 },
{ "赵云", 38, 38.67 },
{ "马超", 48, 58.67 },
{ "黄忠", 58, 48.67 }
};
for (int i = 0; i < 5; i++)
{
pushData(d + i);
}
watchData();
delData(d+2);
watchData();
modify(d, d + 1);
watchData();
return 0;
}
//初始化
void initData()
{
curSize = 0;
capacity = 0;
pArr = NULL;
}
//insertData
void pushData(stu* inserData)
{
//需要开内存
if (capacity <= curSize)
{
//计算新开内存
capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;
stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存
assert(pNew); //防御性编程
if (pArr)
{
memcpy(pNew, pArr, sizeof(stu) * curSize);
//释放原有内存段
free(pArr);
}
//pArr指向新开内存段
pArr = pNew;
}
//inserData放入数组中
memcpy(pArr + curSize, inserData, sizeof(stu));
//元素个数加一
curSize++;
}
//浏览数据
void watchData()
{
printf("pArr[%d][%d]:\n", curSize,capacity);
for (int i = 0; i < curSize; i++)
{
printf("%s-%d-%.2f\n",
pArr[i].name, pArr[i].age, (pArr+i)->score);
}
printf("\n");
}
//查找数据
int findData(stu* findData)
{
for (int i = 0; i < curSize; i++)
{
if (
0 == strcmp((pArr+i)->name,findData->name)
&& pArr[i].age == findData->age
&& pArr[i].score == findData->score
)
{
return i;
}
}
return -1;
}
//删除数据
void delData(stu* delData)
{
int index = findData(delData);
//找到了
if (index != -1)
{
if(curSize == 1) //只有一个元素时
{
free(pArr);
initData();
}
else
{
//申请新空间
stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));
assert(pNew);
if (index != 0)
{
//该元素前面有元素,把前面元素拷贝到新内存段
memcpy(pNew, pArr, sizeof(stu) * index);
}
if (index != curSize - 1)
{
//该元素后面又元素，把后面元素拷贝到新内存段
memcpy(pNew + index, pArr + index + 1, sizeof(stu) * (curSize - 1 - index));
}
free(pArr); //释放原来的空间
pArr = pNew; //pArr指向新数据
curSize--;
capacity = curSize;
}
}
else
{
printf("没找到，删除失败!\n");
}
}
//修改数据
void modify(stu* srcData, stu* dscData)
{
int index = findData(srcData);
if (index != -1)
{
memcpy(pArr + index, dscData, sizeof(stu));
}
else
{
printf("修改失败，没找到\n");
}
}
9.测试案例
下面是我的测试案例的输出结果
———————————
版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_72157449/article/details/128743508
