吴桥网站,盘石做的网站,上海电商设计招聘网站,深圳建设工程信息网站文章目录
顺序表基本操作实现
知识总览
1.顺序表的初始化
1.1静态分配顺序表的初始化
1.2动态分配顺序表的初始化
2.插入操作
2.1插入操作流程
2.2插入操作时间复杂度
3.删除操作
3.1删除操作流程
3.2删除操作时间复杂度
4.查找操作
4.1按位查找
4.2按位查找时间…文章目录
顺序表基本操作实现
知识总览
1.顺序表的初始化
1.1静态分配顺序表的初始化
1.2动态分配顺序表的初始化
2.插入操作
2.1插入操作流程
2.2插入操作时间复杂度
3.删除操作
3.1删除操作流程
3.2删除操作时间复杂度
4.查找操作
4.1按位查找
4.2按位查找时间复杂度
4.3按值查找顺序查找
4.4按值查找时间复杂度
知识回顾与重要考点 顺序表基本操作实现
知识总览 注意 在各种操作的实现中包括严蔚敏老师撰写的教材)往往可以忽略边界条件判断、变量定义、内存分配不足等细节即不要求代码具有可执行性而重点在于算法的思想。 1.顺序表的初始化
静态分配和动态分配的顺序表的初始化操作是不同的。
1.1静态分配顺序表的初始化
静态分配在声明一个顺序表时就已为其分配了数组空间因此初始化时只需将顺序表的当前长度设为0。
//SqList L; //声明一个顺序表
void InitList(SqList L){L.length0; //顺序表初始长度为0}1.2动态分配顺序表的初始化
动态分配的初始化为顺序表分配一个预定义大小的数组空间,并将顺序表的当前长度设为0。MaxSize指示顺序表当前分配的存储空间大小一旦因插入元素而空间不足就进行再分配。
void InitList(SeqList L){L.data (ElemType *)malloc (MaxSize*sizeof(ElemType)); //分配存储空间L.length0; //顺序表初始长度为0L. MaxSizeInitSize; //初始存储容量
}
2.插入操作
2.1插入操作流程
在顺序表L的第i(1iL.length1个位置插入新元素e。
若i的输入不合法则返回false表示插入失败;
否则将第i个元素及其后的所有元素依次往后移动一个位置腾出一个空位置插入新元素e顺序表长度增加1插入成功返回true。
bool ListInsert(SqList L,int i,ElemType e){if(i1|iL.length1) //判断i的范围是否有效return false;if(L.lengthMaxSize) //当前存储空间已满不能插入return false;for(int jL.length;ji;j--) //将第i个元素及之后的元素后移L.data[j]L.data[j-1];L.data[i-1]e; //在位置i处放入eL.length; //线性表长度加1return true;
}注意 区别顺序表的位序和数组下标。为何判断插入位置是否合法时if语句中用length1而移动元素的for语句中只用length? 2.2插入操作时间复杂度
最好情况:在表尾插入(即in1)元素后移语句将不执行时间复杂度为O(1)。
最坏情况:在表头插入(即i 1)元素后移语句将执行n次时间复杂度为O(n)。
平均情况:假设pi (pi1/(n1))是在第i个位置上插入一个结点的概率则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为 因此顺序表插入算法的平均时间复杂度为O(n)。 3.删除操作
3.1删除操作流程
删除顺序表L中第i(1iL.length)个位置的元素用引用变量e返回。若i的输入不合法则返回false;否则将被删元素赋给引用变量e并将第i1个元素及其后的所有元素依次往前移动一个位置返回true.
bool ListDelete(SqList L,int i, ElemType e){if(i1 || iL.length) //判断i的范围是否有效return false;eL.data[i-1]; //将被删除的元素赋值给efor(int ji;jL.length;j) //将第i个位置后的元素前移L.data[j-1]L.data[j];L.length--; //线性表长度减1return true;
} 3.2删除操作时间复杂度
最好情况:删除表尾元素即in)无须移动元素时间复杂度为O(1)。
最坏情况:删除表头元素(即i1)需移动除表头元素外的所有元素时间复杂度为O(n)
平均情况:假设pi(pi 1/n)是删除第i个位置上结点的概率则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为
因此顺序表删除算法的平均时间复杂度为O(n)。
可见顺序表中插入和删除操作的时间主要耗费在移动元素上而移动元素的个数取决于插入和删除元素的位置。
4.查找操作
4.1按位查找 4.2按位查找时间复杂度 4.3按值查找顺序查找
在顺序表L中查找第一个元素值等于e的元素并返回其位序。
int LocateE lem (SqList L,ElemType e){int i;for(i0;iL.length;i)if(L.data [i]e)return i1; //下标为i的元素值等于e返回其位序i1return 0; //退出循环说明查找失败
}4.4按值查找时间复杂度
最好情况:查找的元素就在表头仅需比较一次时间复杂度为O(1)。
最坏情况:查找的元素在表尾或不存在时需要比较n次时间复杂度为O(n)。
平均情况:假设pi (pi1/n是查找的元素在第i (1iL.length)个位置上的概率则在长度为n的线性表中查找值为e的元素所需比较的平均次数为 因此顺序表按值查找算法的平均时间复杂度为O(n)。
知识回顾与重要考点
