第一篇 data——structure把之前没写的的都总结起来顺序表首先是两种形式的顺序表c指的是所存变量的大小例如int型为4个字节则c为4物理地址就为 0X01-0X05…char为一个字节那么物理地址为0X01-0X02…。元素内置上图a就是元素内置结构数据元素本身连续存储每个元素所占存储单元大小固定相同,而元素存储的物理地址实际内存地址可以通过存储区的起始地址Loc (e0)加上逻辑地址第i个元素与存储单元大小c的乘积计算而得即Loc(ei) Loc(e0) c*i为什么表的下表都是从零开始由图中公式可以看出如果我们计算第二个元素的地址就是该元素下标c1Loc(e0)* 正好能得出地址那么以后我们想计算元素地址直接用首个元素c*下标就可以。元素外置但是如果元素的大小不一样例如int,char,字符串等一起存放那么就不能够使用元素内置表必须使用元素外置表。这种表的特点是表内存的是元素的地址再由地址指向元素x。因为地址大小相同图b中的c不再是数据元素的大小而是存储一个链接地址所需的存储量这个量通常很小。顺序表的一体式与分离式结构顺序表的结构一个顺序表的完整信息包括两部分一部分是表中的元素集合另一部分是为实现正确操作而需记录的信息即有关表的整体情况的信息这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。图a为一体式结构存储表信息的单元与元素存储区以连续的方式安排在一块存储区里两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强易于管理。但是由于数据元素存储区域是表对象的一部分顺序表创建后元素存储区就固定了。一体式结构由于顺序表信息区与数据区连续存储在一起所以若想更换数据区则只能整体搬迁即整个顺序表对象指存储顺序表的结构信息的区域改变了。图b为分离式结构表对象里只保存与整个表有关的信息即容量和元素个数第三个为首元素地址实际数据元素存放在另一个独立的元素存储区里通过链接与基本表对象关联。这样表中元素扩充时产生的新表只需要让表头第三个地址改为新表首元素地址即可。元素存储区扩充采用分离式结构的顺序表若将数据区更换为存储空间更大的区域则可以在不改变表对象的前提下对其数据存储区进行了扩充所有使用这个表的地方都不必修改。只要程序的运行环境计算机系统还有空闲存储这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表因为其容量可以在使用中动态变化。扩充的两种策略每次扩充增加固定数目的存储位置如每次扩充增加10个元素位置这种策略可称为线性增长。特点节省空间但是扩充操作频繁操作次数多。每次扩充容量加倍如每次扩充增加一倍存储空间。原来是4下次是8再下次空间变为16…特点减少了扩充操作的执行次数但可能会浪费空间资源。以空间换时间推荐的方式。