做网站公司需要多少钱,wordpress live2d,网站 微信开发,微信视频网站怎么做的好处1数据结构简介
学习数据结构与算法之前#xff0c;一般是先学数据结构#xff0c;方便之后学习算法#xff0c;那么数据结构拆开介绍#xff0c;就是数据 和 结构#xff0c;数据#xff0c;生活中到处都是#xff0c;结构#xff0c;就是数据存储的方式#xff0c;即…1·数据结构简介
学习数据结构与算法之前一般是先学数据结构方便之后学习算法那么数据结构拆开介绍就是数据 和 结构数据生活中到处都是结构就是数据存储的方式即数据结构可以理解为计算机存储、组织数据的方式那么我们学习数据结构无非就是学习数据在计算机里面的存储组织方式那么为什么需要数据结构数据结构存在的意义是什么
在餐厅发餐的时候人们都有自己的号码牌轮到自己的号码的时候也就是可以吃饭了这里数据就是人们点餐的号码存储的方式就是按照顺序存储取餐的时候人们按照号码开始取餐假定没有号码也就没有了顺序也就失去了秩序那么处理发餐问题上的效率就会大打折扣可以得出结论数据结构可以提高处理事件的效率。
其实我们接触C语言不久的时候就已经接触过数据结构了数据结构就是存储数据组织数据那你想存储数据的知识点我们在前面学过……
当然是数组了数组是最基本的数据结构它可以存储数据吧可以组织数据吧数组的章节我们 提到数组存储数据的时候内存空间是连续存储的所以数组存储数据的方式就是连续存储这点我们会应用到之后的顺序表里面。
既然数组已经是数据结构了为什么要学习其他的数据结构呢假定这样的场景我们定义了一个长度为10的数组可是我们只存储一个数据于是就浪费了9个数据后我们又定义了一个长度为2的数组可我们要存储10个数据这个数组我们就用不上也就是浪费空间了那么我们真正想要的是什么呢
我们真正想要的是一个能随着我们需求而改变的数据结构这个时候就会说了柔性数组呢柔性数组大小确实是可以随需求的改变而改变可是柔性数组也是存在条件的数组是最后的成员局限性是只能存储一种类型的数据我们需要的不是一种数据有时候我们需要多种数据糅合在一起比如通讯录那么现在就进入到基于数组实现的更高级的数据结构里面——线性表。
线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2·顺序表
顺序表是线性表的一种底层逻辑是数组那么它和数组的区别在哪里呢 可以理解为是苍蝇馆子和米其林餐厅的区别东西都是一样的都可以存储东西但是米其林可以提供其他的配菜可以实现更多的”功能“比如数组一次只能存一种数据顺序表一次可以存储多种数据顺序表可以通过多种接口的实现来实现更多的功能比如对数据进行增删查改。
顺序表分为两种静态顺序表动态顺序表。
#define N 7
typedef int Datatype;
struct SeqList
{Datatype arr[N];//定长数组int size;//有效数据个数
};
这就是静态顺序表的实现看似平平无奇实际就确实平平无奇让人疑惑的可能是为什么对int进行重命名假定这样一个场景在一个容器里面全都是int老板让你把int全部改成float你是一个一个改吗倘若只有几十个还好如果有几千个呢那就麻烦了所以我们不妨在int放进容器的时候就对它进行重命名之后如果更换就只需要改一个int就行了所以这里的重命名是为了之后数据类型的易转换。
typedef struct Seqlist
{Datatype* arr;int size;//有效数据个数int capacity;//开辟的空间大小
}SL;
这就是动态顺序表的实现因为是动态的所以使用指针来指向这块空间是最好的注意指针类型是我们可以自己定义的最基础的就是整型之类的比如存一些数高级一点的就是结构体指针也就是后面的通讯录会用到我们开辟了空间之后需要两个计数器一个是计算里面的有效数据个数一个是计算开辟的空间大小。 3·顺序表的初始化和销毁
我们创建的动态顺序表里面一共就三个成员一个指针两个整型那么初始化无非就是给NULL或者0
void SeqlistInit(SL s1)
{s1.arr NULL;s1.size s1.capacity 0;
}
我们创建一个函数用来初始化看似没有问题实际上当我们调试代码的时候会发现我们真正需要的结构体并没有被初始化因为这里我们使用的是传值实际上初始化的只是临时拷贝的那个结构体改进方法就是改用传址调用为了方便起见后面所有有关顺序表的操作我们都使用传址
void SeqlistInit(SL* ps)
{ps-arr NULL;ps-size ps-capacity 0;return 0;
}
同样为了之后方便实现顺序表通讯录我们可以让顺序表有关的函数和源代码放在单独的头文件和源文件里面记得要在头文件里面写上需要用到的其他的头文件。
其实销毁和初始化是大同小异区别在于销毁需要把空间还给操作系统因为在销毁之前顺序表已经实现了多种功能所以我们并不知道现在的指针是否为空即需要判断一下
void SeqlistDestroy(SL* ps)
{assert(ps);ps-arr NULL;free(ps-arr);ps-capacity ps-size 0;
}
使用assert的话别忘了引用头文件assert.h如果不想引用头文件也可以结合if语句进行判断总之就是要判断就对了,因为返回值是void所以直接返回就行了不需要加上返回值。
void SeqlistDestroy(SL* ps)
{if (ps-arr NULL){return;}//assert(ps);ps-arr NULL;free(ps-arr);ps-capacity ps-size 0;
} 4·顺序表的扩容
我们创建好顺序表之后还没有开辟空间那么在我们插入数据之前可能就会面对两种问题一是指针指向的空间还没有开辟二是指针指向的空间大小不够插入数据这两种情况我们都需要进行扩容
void SLCheckCapacity(SL* ps)
{if (ps-capacity 0){ps-arr (Datatype*)malloc(4 * sizeof(Datatype));ps-capacity 4;}if (ps-capacity ps-size){Datatype* tem (Datatype*)realloc(ps-arr, 2 * ps-capacity * sizeof(Datatype));if (tem ! NULL){ps-arr tem;ps-capacity * 2;}else {perror(realloc fail!);return;}}
}
在扩容之后顺序表里面的空间大小也会随着改变所以我们改变指针指向空间的同时还要改变一下空间计数的大小有人可能就问了为什么是两倍两倍的增加空间大小每插入一个数据的时候就增加一块空间不好吗仔细想想这样不会浪费空间但是实际上效率会低下很多假如插入数据个数多了几万个插入一个数据就调用一下这个函数岂不是浪费了很多时间至于为什么是二倍就留个读者自行探索了二倍是最不容易浪费空间的了。
有人问了为什么扩容之后原来的指针不用释放因为realloc函数会自动释放空间。 5·顺序表的尾部插入/删除
在所有插入数据操作之前我们都应该判断空间大小是否足够其次再考虑插入的事尾部插入数据的时候需要注意sizeof个数会增加
void SLPushback(SL* ps, Datatype x)
{assert(ps);SLCheckCapacity(ps);ps-arr[ps-size] x;
}
这里使用后置代码界面看起来就更简洁要是单独拎出来加加也行尾插就直接插入数据就行了没什么太多需要注意的。
那么尾部删除数据怎么操作呢
有的人可能会说删除数据我们就把删除的数据置于0size减减不就行了吗
实际上给删除的数据置于0也是给了一个数据最好的办法就是直接size减减因为删除即不再使用那个数据ps-arr[ps-size]是能访问到的最远的数据size减减之后就访问不了那个数据了这也是一种删除
void SLDeleteBack(SL* ps)
{assert(ps);ps-size--;
}
当然判断指针是否为空还是很有必要的。 6·顺序表的头部插入/删除
顺序表头部插入的时候需要注意的有空间大小是否足够size的增加移动的循环次数头部插入的时候需要将所有的数据往后移动一个单位所以用到while或者for是必不可少的
void SLPushHead(SL* ps, Datatype x)
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i 0; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[0] x;ps-size;
}
我们让数据都往后移动一个单位所以i从0开始显然不那么可行于是就从size开始了整体数据移动完之后首元素放上我们要插入的数据就行最后别忘了ps-size。
头部删除也就是除了第一个数据其他数据全部往前面移动一个单位同时size减减空间大小不变因为挪动的数据个数少一个所以循环次数少一次当然指针是否为空指针也是不能忘记的
void SLDeleteHead(SL* ps)
{assert(ps);for (int i 0; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
} 7·顺序表的指定删除/指定位置之前插入
指定删除需要注意的是删除的位置不能为负数也不能是超过size的位置删除之后后面的数据应该往前移动一个单位size减减指定位置删除的删法和头删有点像就是后面的数据依次往前覆盖了数据就行
void SLDelete(SL* ps,int pos)
{assert(ps);assert(pos 0 pos ps-size);for (int i pos; i ps-size - 1; i){ps-arr[i] ps-arr[i 1];}ps-size--;
}
多注意循环变量的控制。
指定位置之前插入类比头插和尾插先判断空间大小其次移动数据是必要的size也是要的注意这里的pos是下标哦
void SLPush(SL* ps, int pos, Datatype x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);for (int i ps-size; i pos; i--){ps-arr[i] ps-arr[i - 1];}ps-arr[pos] x;ps-size;
}8·顺序表的打印
打印是很简单的就是一个for循环的事我们先加上一下数据
#include Seqlist.h
int main()
{SL s1;SeqlistInit(s1);//初始化SLPushHead(s1, 5);SLPushHead(s1, 4);SLPushHead(s1, 3);SLPushHead(s1, 2);SLPushHead(s1, 1);SLPushBack(s1, 1);//1 2 3 4 5 1SLPrint(s1);SLPush(s1, 3, 100);//1 2 3 100 4 5 1SLPrint(s1);SLDeleteHead(s1);//2 3 100 4 5 1SLPrint(s1);SLDelete(s1, 4);//2 3 100 5 1SLPrint(s1);SeqlistDestroy(s1);//销毁return 0;
}
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i){printf(%d , ps-arr[i]);}
} 最后的结果也是没有问题的。 9·顺序表的查找
查找无非就是进行遍历最后返回我们要找的数据的下标就行了遍历就要一个for循环就行了
int SLFind(SL* ps,Datatype x)
{assert(ps);for (int i 0; i ps-size; i){if (x ps-arr[i]){return i;}}return -1;
}
然后结合实际效果看看 以上就是顺序表的基本功能实现下一篇介绍顺序表实现通讯录 感谢阅读
