博物馆网站制作,国际品牌的广州网页设计,东莞建站多少钱,如何选择购物网站建设文章目录 目录1. 基于动态顺序表实现通讯录项目2.顺序表经典算法2.1 [移除元素](https://leetcode.cn/problems/remove-element/description/)2.2 [合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/description/) 3. 顺序表的问题及思考 目录
基于动态顺序… 文章目录 目录1. 基于动态顺序表实现通讯录项目2.顺序表经典算法2.1 [移除元素](https://leetcode.cn/problems/remove-element/description/)2.2 [合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/description/) 3. 顺序表的问题及思考 目录
基于动态顺序表实现通讯录项目顺序表经典算法顺序表的问题及思考
1. 基于动态顺序表实现通讯录项目
我们先写一个框架
//Contact.h#include stdio.h//暂时加上//ConTest.c#include Contact.h//通讯录菜单
void menu()
{printf(******************通讯录******************\n);printf(*******1. 添加联系人 2.删除联系人********\n);printf(*******3. 修改联系人 4.查找联系人********\n);printf(*******5. 查看通讯录 0. 退 出 ********\n);printf(******************************************\n);
}int main()
{int op -1;do{menu();printf(请选择您的操作\n);scanf(%d, op);switch (op){case 1://添加联系人break;case 2://删除联系人break;case 3://修改联系人break;case 4://查找联系人break;case 5://查看通讯录break;case 0://退出通讯录printf(通讯录退出中...\n);break;default:break;}} while (op ! 0);return 0;
}接着我们就可以开始添加具体操作了
先要创建通讯录数据类型
//Contact.h#define NAME_MAX 100
#define GENDER_MAX 10
#define TEL_MAX 12
#define ADDR_MAX 100//通讯录数据类型
typedef struct PersonInfo
{char name[NAME_MAX];int age;char gender[GENDER_MAX];char tel[TEL_MAX];char addr[ADDR_MAX];
}Info;我们要把之前写的顺序表中数组的类型进行替换
//SeqList.h#include Contact.htypedef Info SLDataType;然后我们写接口
//Contact.h//通讯录提供的操作typedef struct SeqList Contact;//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表这里我们想把 SL 换成 Contact这样看上去更好理解所以就要 typedef struct SeqList Contact; 但是要使用struct SeqList 就要 #include “SeqList.h” 但是这样会出现一个问题 解决办法前置声明
//Contact.h//使用顺序表的前置声明
struct SeqList;typedef struct SeqList Contact;//通讯录提供的操作//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表
void ContactDestroy(Contact* pcon);//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon);
void ContactDel(Contact* pcon);
void ContactModify(Contact* pcon);
void ContactFind(Contact* pcon);
void ContactShow(Contact* pcon);此外以下代码不再适用直接注释掉
//SeqList.c//在顺序表中查找x
//int SLFind(SL* ps, SLDataType x)
//{
// //加上断言对代码的健壮性更好
// assert(ps);
//
// for (int i 0; i ps-size; i)
// {
// if (x ps-arr[i])
// {
// return i;
// }
// }
//
// return -1;
//}因为现在 ps-arr[i] 已经变成一个结构体了不能直接使用 来比较
接下来就是方法的具体实现
//Contact.c//#include Contact.h
#include SeqList.h//通讯录的初始化和销毁
//SL* ps
void ContactInit(Contact* pcon)
{SLInit(pcon);
}void ContactDestroy(Contact* pcon)
{SLDestroy(pcon);
}//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon)
{//创建联系人结构体变量Info info;printf(请输入联系人姓名:\n);scanf(%s, info.name);printf(请输入联系人年龄:\n);scanf(%d, info.age);printf(请输入联系人性别:\n);scanf(%s, info.gender);printf(请输入联系人电话:\n);scanf(%s, info.tel);printf(请输入联系人住址:\n);scanf(%s, info.addr);//保存数据到通讯录顺序表SLPushBack(pcon, info);
}void ContactShow(Contact* pcon)
{printf(%s %s %s %s %s\n, 姓名, 性别, 年龄, 电话, 住址);for (int i 0; i pcon-size; i){printf(%s %s %d %s %s\n,pcon-arr[i].name,pcon-arr[i].gender,pcon-arr[i].age,pcon-arr[i].tel,pcon-arr[i].addr);}
}int FindByName(Contact* pcon, char name[])
{for (int i 0; i pcon-size; i){if (0 strcmp(pcon-arr[i].name, name)){//找到了return i;}}return -1;
}void ContactDel(Contact* pcon)
{//删除之前一定要先查找//找到了可以删除//找不到不能执行删除printf(请输入要删除的联系人姓名:\n);char name[NAME_MAX];scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(要删除的联系人不存在\n);return;}//执行删除操作SLErase(pcon, findIndex);printf(联系人删除成功\n);
}void ContactModify(Contact* pcon)
{//修改之前要先查找//找到了执行修改操作//没有找到不能执行修改操作char name[NAME_MAX];printf(请输入要修改的联系人姓名\n);scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(要修改的联系人不存在\n);return;}//找到了执行修改操作printf(请输入姓名:\n);scanf(%s, pcon-arr[findIndex].name);printf(请输入年龄:\n);scanf(%d, pcon-arr[findIndex].age);printf(请输入性别:\n);scanf(%s, pcon-arr[findIndex].gender);printf(请输入电话:\n);scanf(%s, pcon-arr[findIndex].tel);printf(请输入地址:\n);scanf(%s, pcon-arr[findIndex].addr);printf(联系人修改成功\n);
}void ContactFind(Contact* pcon)
{char name[NAME_MAX];printf(请输入要查找的用户姓名:\n);scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(该联系人不存在\n);return;}//找到了打印一下查找的联系人信息printf(%s %s %s %s %s\n, 姓名, 性别, 年龄, 电话, 住址);printf(%s %s %d %s %s\n,pcon-arr[findIndex].name,pcon-arr[findIndex].gender,pcon-arr[findIndex].age,pcon-arr[findIndex].tel,pcon-arr[findIndex].addr);
}完整代码
//SeqList.h#include stdio.h
#include stdlib.h
#include assert.h
#include string.h
#include Contact.h//动态顺序表typedef Info SLDataType;typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);//顺序表的尾部插入
void SLPushBack(SL* ps, SLDataType x);//删除指定位置数据
void SLErase(SL* ps, int pos);//SeqList.c#include SeqList.h//初始化和销毁
void SLInit(SL* ps)
{assert(ps);ps-arr NULL;ps-size ps-capacity 0;
}void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity){int newCapacity 0 ps-capacity ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType));if (NULL tmp){perror(realloc fail!);exit(1);}//扩容成功ps-arr tmp;ps-capacity newCapacity;}
}//顺序表的尾部插入
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//空间不够扩容SLCheckCapacity(ps);//空间足够直接插入ps-arr[ps-size] x;
}//删除指定位置数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);//pos以后的数据往前挪动一位for (int i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}void SLDestroy(SL* ps)
{assert(ps);free(ps-arr);ps-arr NULL;ps-size ps-capacity 0;
}//Contact.h#define NAME_MAX 100
#define GENDER_MAX 10
#define TEL_MAX 12
#define ADDR_MAX 100//通讯录数据类型
typedef struct PersonInfo
{char name[NAME_MAX];int age;char gender[GENDER_MAX];char tel[TEL_MAX];char addr[ADDR_MAX];
}Info;//使用顺序表的前置声明
struct SeqList;typedef struct SeqList Contact;//通讯录提供的操作//通讯录的初始化和销毁
void ContactInit(Contact* pcon);//实际初始化的还是顺序表
void ContactDestroy(Contact* pcon);//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon);
void ContactDel(Contact* pcon);
void ContactModify(Contact* pcon);
void ContactFind(Contact* pcon);
void ContactShow(Contact* pcon);//Contact.c#include SeqList.h//通讯录的初始化和销毁
//SL* ps
void ContactInit(Contact* pcon)
{SLInit(pcon);
}void ContactDestroy(Contact* pcon)
{SLDestroy(pcon);
}//增加、删除、修改、查找、查看通讯录
void ContactAdd(Contact* pcon)
{//创建联系人结构体变量Info info;printf(请输入联系人姓名:\n);scanf(%s, info.name);printf(请输入联系人年龄:\n);scanf(%d, info.age);printf(请输入联系人性别:\n);scanf(%s, info.gender);printf(请输入联系人电话:\n);scanf(%s, info.tel);printf(请输入联系人住址:\n);scanf(%s, info.addr);//保存数据到通讯录顺序表SLPushBack(pcon, info);
}int FindByName(Contact* pcon, char name[])
{for (int i 0; i pcon-size; i){if (0 strcmp(pcon-arr[i].name, name)){//找到了return i;}}return -1;
}void ContactDel(Contact* pcon)
{//删除之前一定要先查找//找到了可以删除//找不到不能执行删除printf(请输入要删除的联系人姓名:\n);char name[NAME_MAX];scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(要删除的联系人不存在\n);return;}//执行删除操作SLErase(pcon, findIndex);printf(联系人删除成功\n);
}void ContactModify(Contact* pcon)
{//修改之前要先查找//找到了执行修改操作//没有找到不能执行修改操作char name[NAME_MAX];printf(请输入要修改的联系人姓名\n);scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(要修改的联系人不存在\n);return;}//找到了执行修改操作printf(请输入姓名:\n);scanf(%s, pcon-arr[findIndex].name);printf(请输入年龄:\n);scanf(%d, pcon-arr[findIndex].age);printf(请输入性别:\n);scanf(%s, pcon-arr[findIndex].gender);printf(请输入电话:\n);scanf(%s, pcon-arr[findIndex].tel);printf(请输入地址:\n);scanf(%s, pcon-arr[findIndex].addr);printf(联系人修改成功\n);
}void ContactFind(Contact* pcon)
{char name[NAME_MAX];printf(请输入要查找的用户姓名:\n);scanf(%s, name);int findIndex FindByName(pcon, name);if (findIndex 0){printf(该联系人不存在\n);return;}//找到了打印一下查找的联系人信息printf(%s %s %s %s %s\n, 姓名, 性别, 年龄, 电话, 住址);printf(%s %s %d %s %s\n,pcon-arr[findIndex].name,pcon-arr[findIndex].gender,pcon-arr[findIndex].age,pcon-arr[findIndex].tel,pcon-arr[findIndex].addr);
}void ContactShow(Contact* pcon)
{printf(%s %s %s %s %s\n, 姓名, 性别, 年龄, 电话, 住址);for (int i 0; i pcon-size; i){printf(%s %s %d %s %s\n,pcon-arr[i].name,pcon-arr[i].gender,pcon-arr[i].age,pcon-arr[i].tel,pcon-arr[i].addr);}
}//ConTest.c#include SeqList.h//通讯录菜单
void menu()
{printf(******************通讯录******************\n);printf(*******1. 添加联系人 2.删除联系人********\n);printf(*******3. 修改联系人 4.查找联系人********\n);printf(*******5. 查看通讯录 0. 退 出 ********\n);printf(******************************************\n);
}int main()
{int op -1;//创建通讯录结构对象Contact con;ContactInit(con);do{menu();printf(请选择您的操作\n);scanf(%d, op);switch (op){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:break;}} while (op ! 0);//销毁通讯录ContactDestroy(con);return 0;
}2.顺序表经典算法
2.1 移除元素 int removeElement(int* nums, int numsSize, int val)
{//定义两个变量int src 0, dst 0;while (src numsSize){//nums[src] val,src//否则赋值,src和dst都if (nums[src] val){src;}else{//说明src指向位置的值不等于valnums[dst] nums[src];dst;src;}}//此时dst的值刚好是数组的新长度return dst;
}2.2 合并两个有序数组 void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int l1 m - 1;int l2 n - 1;int l3 m n - 1;while (l1 0 l2 0){//从后往前比大小if (nums1[l1] nums2[l2]){nums1[l3--] nums1[l1--];}else{nums1[l3--] nums2[l2--];}}//要么是l1 0要么是l2 0while (l2 0){nums1[l3--] nums2[l2--];}
}3. 顺序表的问题及思考
中间/头部的插入删除时间复杂度为O(N)。增容需要申请新空间拷贝数据释放旧空间会有不小的消耗。增容一般是呈2倍的增长势必会有⼀定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
是否存在一种数据结构能够解决以上顺序表表现出来的问题
中间/头部的插入删除可以一步到位不需要挪动数据不需要扩容不会造成空间浪费
链表这种数据结构就可以解决这些问题我们在下一篇中就会进行介绍。
