下载汽车网站制作网站,wordpress多用户注册,阿里巴巴网站建设初衷,国外社交网站设计欣赏知识回顾 通过前文#xff0c;我们了解到线性表是具有相同数据类型的有限个数据元素序列#xff1b;并且#xff0c;线性表只是一种逻辑结构#xff0c;其不同存储形式所展现出的也略有不同#xff0c;那么今天我们来了解一下线性表的顺序存储——顺序表。
顺序表的定义 …知识回顾 通过前文我们了解到线性表是具有相同数据类型的有限个数据元素序列并且线性表只是一种逻辑结构其不同存储形式所展现出的也略有不同那么今天我们来了解一下线性表的顺序存储——顺序表。
顺序表的定义 顺序表指的是将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。所以顺序表的特点就是其逻辑顺序与其物理顺序相同。 我们不妨将设线性表L存储的起始位置为LOCA那么其顺序表L相对应的顺序存储如图所示这里sizeof是计算括号内数据元素所占用存储空间的大小 通过图我们也不难观察出其顺序表的特点。这里每个数据元素的存储位置都与线性表的起始位置相差该数据元素的位序个n个数据元素内存大小。所以我们的顺序存储结构是随机存取的存储结构。在接下来高级程序设计语言的实现中我们决定使用数组来实现该内容(不过需要注意的是线性表中元素的位序是从1开始的而数组中的元素下标是从0开始的)。
元素类型初始化
静态分配 既然我们了解了顺序表那么接下来我们就要尝试着去实现顺序表。首先我们需要思考的是 我们应该怎么定义出顺序表中每个元素的类型呢这并不是一个困难的问题由于顺序表的特点我们这里可以使用一个数组去存放顺序表中元素不过仅仅使用数组是不行的因为我们很难去判断我们顺序表存储了多少个元素顺序表的长度那么这时我们就需要一个附加的值length去记录我们顺序表的当前长度由于我们需要两个值同时存在这里就需要用到我们之前C语言学习时的一个关键字struct了。通过我们的思考我们就可以尝试写出顺序表中的顺序存储类型了。
#define MaxSize 50 typedef struct {int data[MaxSize]; // 定义元素 int length; //表示当前长度
}SqList; 于是我们不难写出上述的代码需要注意的是此时data[]为int类型这里的int可以根据我们存储元素的类型去进行更改这里我们使用数组去存储顺序表中的元素使用length去记录当前的长度。 可以使用该方法静态分配去分配时会出现一种问题由于我们数组的大小和空间是固定的我们在分配数组时若数组的空间开的过大会导致其内存的浪费若空间开的过小又有可能导致空间占满进而导致存入新数据时产生溢出、程序崩溃这也就是我们进行静态分配的缺点。 思考第三步的Length设为0可不可以省略 这当然是不可以的如果我们没有对Length的值进行初始化那么这个值在分配的时候将是随机的这样就会导致长度计算的错误当然写过一些代码的小伙伴可能会疑惑我们平时也是没有初始化他的值一直是0呀这里主要是由于编译器的原因我们使用的编译器自动的将其设为0了但在考试中为了严谨性还是建议将Length值进行初始化的。 既然静态分配有那么多缺点那么我们能不能使用一个更好些的办法去尽可能的避免这些问题呢答案当然是可以的这里我们可以采用动态分配。 动态分配 在动态分配中存储数组的空间实在程序执行的过程中通过动态存储分配语句分配的一旦该数组的空间占满就另外开辟出一块更大的存储空间用来替换掉之前的存储空间这样可以有效的解决上面的问题。
#define InitSize 50 //顺序表初始长度typedef struct {int *data; // 指向动态分配数组的指针 int MaxSizelength; //分别表示最大容量和当前长度
}SqList; 在进行动态的申请和释放空间时我们可以利用下面这些关键字 C —— malloc、free 函数 L.data (ElemType *) malloc (sizeof(ElemType) *InitSize) ; C —— new、delete 函数 L.data new ElemType (InitSize) ; 顺序表特点
随机存储我们可以通过首地址和元素序号在时间复杂度为O(1)内找到指定的元素。其存储密度高每个节点只需存储数据元素。顺序表逻辑上相邻的元素物理上也相邻所以插入和删除就需要移动大量的元素。 顺序表的基本操作实现
顺序表的插入
顺序表的插入操作 ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e。 我们的实现思路主要就是首先判断输入的第i个位置是否合法若不合法则插入失败若合法则将第i个元素及其后面的元素依次向后移动一个位置然后腾出一个空位置插入新元素e顺序表的长度增加1及插入成功。
//插入
bool ListInsert(SqList L, int i, int e){ //传入顺序表 以及从第i个位置插入一个值e if(i1 || iL.length1) //注这里的i是表中的第几个元素并非其数组下标return false ;if(L.length MaxSize) //表满 无法插入return false ;//后移for(int jL.length; ji; j--){ //此时j表示的是位数 L.data[j] L.data[j-1];} /*for(int jL.length-1; ji-1; j--){ j表示的为数组下标 L.data[j1] L.data[j];}*/ L.data[i-1] e ;L.length;return true ;
}
思考为什么代码中if语句中用length1而for语句中只用length呢通过对代码的观察我们不难发现这里if语句和for语句中的元素代表的含义并不相同if语句中代表的是顺序表元素的位序而for语句中代表的是数组下标。
时间复杂度分析 最好情况直接在表尾插入元素 in1 元素直接后移即可时间复杂度为O(1)。 最坏情况在表头插入元素 i1 ,元素需要后移n次时间复杂度为O(n)。 平均情况假设为在第 i 个位置上插入一个结点的概率则在一个长度为n的线性表中插入一个结点时需要移动节点的平均次数为 因此顺序表插入算法的时间复杂度为O(n)。
顺序表的删除 顺序表的删除操作 ListDelete(L,i,e)删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。 删除元素我们主要的实现思路就是我们在删除第i个位置之后需要将其后面的位置全部向前移动一位这样就可以完成删除操作了。
//删除
bool ListDelete(SqList L, int i, int e){if(i1 || iL.length1)return false ;e L.data[i-1] ; //第i个元素 在数组的i-1for(int ji; jL.length; j){L.data[j-1] L.data[j] ;} L.length L.length-1 ;return true ;}
时间复杂度分析 最好情况直接在表尾删除元素 in1 元素删除即可时间复杂度为O(1)。 最坏情况在表头删除元素 i1 ,元素需要前移n次时间复杂度为O(n)。 平均情况假设为在第 i 个位置上删除一个结点的概率则在一个长度为n的线性表中删除一个结点时需要移动节点的平均次数为 因此顺序表插入算法的时间复杂度为O(n)。 由此可见插入操作删除操作的时间主要消耗在移动元素上而移动元素的个数与我们插入或者删除元素的位置有关不同的插入删除位置所移动的元素个数是不同的。
顺序表的查找
按位查找 GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值。 对于按位查找由于我们的数组下标可以很好的表示出元素的顺序这里我们就可以直接利用数组下标与元素位序的映射关系去完成返回第i个元素的值操作。
//查找第i个位置的元素值
int GetElem(SqList L, int i) {return L.data[i-1]; //数组下标从0开始
}
时间复杂度分析 由于是直接返回数组值的所以不需要什么中间的计算其时间复杂度是稳定的 O(1) 。
按值查找 LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。 对于按值查找我们可以使用循坏去遍历一遍我们的顺序表这样就可以找到需要返回的值了如果遍历一遍之后仍没有发现需要查找的值那么就返回false证明查找失败。
//查找
//查找第一个是e的元素 返回其位序
int LocateElem(SqList L, int e){for(int i0; iL.length; i){ //i为数组下标 if(L.data[i] e)return i1 ;}return 0;
}
时间复杂度分析 最好情况查找的元素在表头只需要查找一次即可时间复杂度为O(1)。 最坏情况查找的元素不存在或者在表尾需要查找n次时间复杂度为O(n)。 平均情况假设为查找元素在第 i 个位置上结点的概率则在一个长度为n的线性表中查找一个结点时需要比较节点的平均次数为 因此顺序表按值查找算法的时间复杂度为O(n)。 到这里顺序表的功能也基本完成了当然对于这些操作我们动态分配和静态分配的操作代码相差并不大只是动态分配时需要多出一个增加数组长度的函数这里在下面的完整代码展示中会体现出来本文就不做过多描述。
顺序表完整代码
静态分配代码
//2.2 顺序表
#includebits/stdc.h
#define MaxSize 50 using namespace std;typedef struct {int data[MaxSize]; // 定义元素 int length; //表示当前长度
}SqList;int ex -1 ;//插入
bool ListInsert(SqList L, int i, int e){ //传入顺序表 以及从第i个位置插入一个值e if(i1 || iL.length1) //注这里的i是表中的第几个元素并非其数组下标return false ;if(L.length MaxSize) //表满 无法插入return false ;//后移for(int jL.length; ji; j--){ //此时j表示的是位数 L.data[j] L.data[j-1];} /*for(int jL.length-1; ji-1; j--){ j表示的为数组下标 L.data[j1] L.data[j];}*/ L.data[i-1] e ;L.length;return true ;
}//删除
bool ListDelete(SqList L, int i, int e){if(i1 || iL.length1)return false ;e L.data[i-1] ; //第i个元素 在数组的i-1for(int ji; jL.length; j){ L.data[j-1] L.data[j] ;} L.length L.length-1 ;return true ;} //查找
//查找第一个是e的元素 返回其位序
int LocateElem(SqList L, int e){for(int i0; iL.length; i){ //i为数组下标 if(L.data[i] e)return i1 ;}return 0;
}//查找第i个位置的元素值
int GetElem(SqList L, int i) {return L.data[i-1]; //数组下标从0开始
} int main(){SqList L ;for(int i0; i5; i){L.data[i] i1 ;}L.length 6 ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;ListInsert(L, 3, 3) ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;ListDelete(L, 3, ex) ;cout ex endl ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;cout GetElem(L, 3) endl ; cout LocateElem(L, 3) endl;return 0;
} 动态分配代码
//2.2 顺序表
#includebits/stdc.h
#define InitSize 50 //顺序表初始长度using namespace std;typedef struct {int *data; // 指向动态分配数组的指针 int MaxSize,length; //分别表示最大容量和当前长度
}SqList;int ex -1 ;//初始化
void InitList(SqList L) {L.data (int *)malloc(sizeof(int));L.length 0;L.MaxSize InitSize;
} //动态增长数组
void IncreaseSize(SqList L, int len) { //len为需要增加长度 int *p L.data; //p记录之前数组地址 方便后期释放 L.data (int *)malloc(sizeof(int) * (L.MaxSizelen)) ; //申请一片新的区域 for(int i0; iL.length; i) {L.data[i] p[i]; //将值复制到新的区域 }L.MaxSize L.MaxSizelen; //更新最大的容量 free(p); //释放之前动态申请的空间
} //插入
bool ListInsert(SqList L, int i, int e){ //传入顺序表 以及从第i个位置插入一个值e if(i1 || iL.length1) //注这里的i是表中的第几个元素并非其数组下标return false ;if(L.length L.MaxSize) //表满 无法插入return false ;//后移for(int jL.length; ji; j--){ //此时j表示的是位数 L.data[j] L.data[j-1];} /*for(int jL.length-1; ji-1; j--){ j表示的为数组下标 L.data[j1] L.data[j];}*/ L.data[i-1] e ;L.length;return true ;
}//删除
bool ListDelete(SqList L, int i, int e){if(i1 || iL.length1)return false ;e L.data[i-1] ; //第i个元素 在数组的i-1for(int ji; jL.length; j){ L.data[j-1] L.data[j] ;} L.length L.length-1 ;return true ;} //查找
//查找第一个是e的元素 返回其位序
int LocateElem(SqList L, int e){for(int i0; iL.length; i){ //i为数组下标 if(L.data[i] e)return i1 ;}return 0;
}//查找第i个位置的元素值
int GetElem(SqList L, int i) {return L.data[i-1]; //数组下标从0开始
} int main(){SqList L ;InitList(L) ;IncreaseSize(L, 10); for(int i0; i5; i){L.data[i] i1 ;}L.length 6 ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;ListInsert(L, 3, 3) ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;ListDelete(L, 3, ex) ;cout ex endl ;for(int i0; iL.length-1; i) cout L.data[i] ;cout endl;cout GetElem(L, 3) endl ; cout LocateElem(L, 3) endl;return 0;
} 两个完整代码的内容大同小异主要就是在顺序表定义初始化时会产生些许不同我们主要理解其产生逻辑即可其代码的运行结果图如下 由代码可知我们对其顺序表初始化为123456就是我们第一行所展示的数字之后我们在第三个位置插入3所以第二行展示的就是插入后的结果第三行则是输出我们在删除时需要删除的位置紧接着我们将第三个位置的数字删除所以第四行显示的是其删除后的结果最后两行就是输出的为第三个位置和查找值为3的元素在第几个位置并输出。 顺序表的内容到这里也就结束了我们在下面尽量可以独立的去实现一下代码这样可以更好的帮助我们理清其内部的逻辑。
