邯郸网站设计在哪里,公司设计网页,wordpress标题翻译,学做网站论坛vip账号数据结构
是数据存储的方式#xff0c;对于不同的数据我们要采用不同的数据结构。就像交通运输#xff0c;选用什么交通工具取决于你要运输的是人还是货物#xff0c;以及它们的数量。
顺序存储结构
包括顺序表、链表、栈和队列等。
例如腾讯QQ中的好友列表#xff0c;…数据结构
是数据存储的方式对于不同的数据我们要采用不同的数据结构。就像交通运输选用什么交通工具取决于你要运输的是人还是货物以及它们的数量。
顺序存储结构
包括顺序表、链表、栈和队列等。
例如腾讯QQ中的好友列表在之前添加好友信息后好友信息这种类型会存储在内存中当我们翻动好友列表时会看到不同好友的ID点开ID又会看到具体的信息信息利用顺序表或链表进行存储翻动的过程也就是遍历。
增加好友、删除好友、查找好友信息、更改好友信息等对应着数据结构最主要的功能增删查改
这些功能都是在腾讯的服务器上实现的。同时好友列表或群聊有上限达到上限后可以增容但增容往往需要充值会员。
静态顺序表 在创建顺序表时就确定了要存储元素的个数为N与静态通讯录相同可能导致内存不够用或是内存浪费因此我们需要能够动态调整内存的能力。
动态顺序表 //#定义的宏和常量 全大写typedef int SLDataType;
#define INITCAPACITY 5//假设初始容量为5typedef struct SeqList
{SLDataType* a;int sz;int capacity;
}SL; 这里我们将数据类型暂时定为int类型typedef为SLDataType便于我们后续对顺序表数据类型的修改。定义属性表为SL*的指针a数据个数sz现有容量sz。
1、接口函数 //顺序表初始化
void SLInit(SL* ps);
//打印
void SLPrint(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置删除
void SLErase(SL* ps, int pos); 插入的过程都需要判断增容可将其封装为增容函数在头插、尾插中运用。
2、顺序表的初始化
SL a;Init_SeqList(a);
//顺序表初始化
void Init_SeqList(SL* pa)
{pa-capacity INITCAPACITY;pa-sz 0;SLDataType* tmp (SLDataType*)malloc((pa-capacity) * sizeof(SLDataType));if (NULL tmp){perror(malloc fail);return;}pa-a tmp;tmp NULL;
}这里必须使用传址调用对sz和capacity初始化后malloc 容量大小的空间给中间变量tmp不为NULL后赋给a这样a就指向了一块初始空间。 3、顺序表的打印int类型为例
//打印
void SLPrint(SL* pa)
{//利用现有个数sz进行遍历打印for (int i 0; i pa-sz; i){printf(%d , pa-a[i]);}printf(\n);
}
4、增容函数
//判断是否需要增容如需要则增容
void SLCapacityAdd(SL* pa)
{if (pa-capacity pa-sz){//增容倍数随意一般来说2倍比较适合SLDataType* tmp (SLDataType*)realloc(pa-a, 2 * (pa-capacity) * sizeof(SLDataType));if (NULL tmp){perror(realloc fail);return;}pa-a tmp;tmp NULL;pa-capacity * 2;}
}
增容后capacity的值变为2倍
5、尾插
//顺序表尾插
void SLPushBack(SL* pa, SLDataType x)
{SLCapacityAdd(pa);//尾插的过程即在下标为size的位置插入pa-a[pa-sz] x;}
尾插前先调用SLCapacityAdd判断是否增容。
6、尾删
//顺序表尾删
void SLPopback(SL* pa)
{assert(pa-sz 0);pa-sz--;
}由于打印等显示过程中我们用sz来遍历顺序表因此在尾删时仅需要将sz--使遍历范围不包含最后一个元素可以等效为将其删除。
在删除前可以利用assert进行断言防止顺序表中没有数据仍然进行删除操作。
换句话说如果没有数据继续删除sz会变成负数当之后再添加元素时sz为负数遍历时会产生越界现象。 7、尾删
//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps-sz 0);//删除的过程int begin 1;while (begin ps-sz){ps-a[begin - 1] ps-a[begin];begin;}ps-sz--;
}
删除时同样判断sz是否大于0删除过程为下标为1的元素起依次向前覆盖最后sz也要-1。
注意覆盖的时候从前面的元素覆盖参考memmove和memcpy内存函数对于重叠空间拷贝的不同。
8、头插 //头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);CheckCapacity(ps);int end ps-sz - 1;while (end 0){ps-a[end 1] ps-a[end];end--;}ps-a[0] x;ps-sz;
}
先检查是否需要增容然后从sz-1开始向右覆盖最后在a[0]处添加x然后sz 9、 指定位置插入
//指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-sz);//锁定插入的范围为 0-szCheckCapacity(ps);int end ps-sz - 1;while (end pos){ps-a[end 1] ps-a[end];--end;}ps-a[pos] x;ps-sz;
}
先断言pos插入的位置正确然后从sz-1开始向右覆盖直到pos位置现有的元素也覆盖过去然后将x插入到pos的位置上。 10、指定位置删除
//指定位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-sz);//锁定插入的范围为 0-sz//assert(ps-sz 0); 上面pos已经排除了sz0的可能可以不用再写int begin pos;while (begin ps-sz - 1){ps-a[begin] ps-a[begin 1];begin;}ps-sz--;}
判断pos范围的同时确定了sz0成立。从pos开始到sz-2从右向左覆盖然后sz-1。 11、升级头尾/插删
由于我们指定位置插入删除的功能已经实现可以将头删、头插、尾插、尾删升级。
在头尾/插删的函数实现中调用Insert和Erase 注意尾插位置是sz尾删是sz-1 头插头删都是0 12、注意点
增加元素时先确保是否需要增容删除时先确保是否还有元素sz是否为0。
指定位置可以代替头尾插入删除当然也可以写一些中间位置的。
同时还有查改功能
int SLFind(SL* ps, SLDataType x)
{assert(ps);for(int i 0; i ps-size; i){if (ps-a[i] x){return i;}}return -1;
}
查的过程遍历即可根据SL数据类型直接判断是否相等结构体等自定义类型也可以。
更改是先查找根据查找内容返回的下标pos或i就可以利用指针进行修改。
