快动网公共基础知识视频教程配套电子教材(pdf完整版本)(4)

将新元素插入第2个元素的位置，现在顺序表的长度变成了9

现在如果要在第4个元素的位置之前再插入一个新元素还采取相同的方法

请思考一下如果要在第10个元素的位置插入一个元素还需要移动其它元素吗？

方法总结：找到插入位置后，将插入位置开始的所有元素到最后一个元素开始顺序后移。

注意：通常用编程语言中的数组实现一个顺序表，在定义数组的长度时，一定要根据实际应用情况定义一个合适大的空间，否则在插入元素时会出数越界的错误。

1.3.4顺序表的删除运算

顺序表的删除运算就是在顺序表中删除一个元素。

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

例如：

12345678910

12345678910

图1图2

上图1为一个长度为8的顺序表存储在长度为10的存储空间中，现要求删除第一个元素，删除过程如下：第一步：

从第2个元素开始到最后一个元素依次往前移动一个位置，此时顺序表的长度变成了7如上图2。如果要删除第4个元素就采集类似的方法把第3个元素到最后一个元素依次往前移动一个位置，这时顺序表的长度变成了6。

方法总结：找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在移动完成后，线性表的长度减1

总结：从顺序表的插入和删除运算来看对于长度小的顺序表或是数据元素变动不频繁顺序表比较适合，反之就不适合了，因为顺序表插入和删除元素时会移动大量的数据元素，这样效率就比较低。

1.4栈和队列1.4.1栈

栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。它的插入和删除只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。在顺序存储结构下，对栈进行插入和删除时是不需要移动元素的。

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

入栈

退栈

栈顶 top

栈底 bottom

如果上图是一个栈的示意图，在栈中，允许插入和删除操作一端称为栈顶，通常用指针top指向栈顶，不允许插入和删除操作的一端则称为栈底，用指针bottom指向栈底。向栈中插入一个元素称为入栈，从栈中删除一个元素称为退栈。

栈顶的元素总是最后被插入的元素也是最先被删除的元素，栈底的元素总是最先被插入的元素也是最后被删除的元素。

栈遵循“先进后出”或“后进先出”的原则。

大家思考一下我们日常生活中见到有栈的情况，如刷洗盘子时，依次把每个洗净的盘子放到洗好的盘子上，相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则为进栈；射击时子弹总是从顶部一个接一个地被射出，此为子弹出栈。

1.4.2栈的顺序存储及其运算

栈的顺序存储和其它线性结构一样用一维数组S（1：m）作为栈的顺序存储空间，其中m为栈的最大容量，通常栈底指针指向低地址一端，S（bottom）通常为栈底元素，S（top）为栈顶元素。

Top=0表示栈空；top=m

表示栈满。

765

7

7

top

65

bottomtop

6432

图3

to

p432

图1

432

bottom

1

bottom

图2

该教材是快动网计算机等级考试二级公共基础知识视频教程的配套课件,欢迎大家去快动网下载或在线听视频教程这样效果会更好。

上图1是容量为7的栈顺序存储，其中已有4个元素，图2是插入E和F的栈，图3是退出一个栈顶元素F后的栈

1）入栈运算

即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加1，再将元素插入至指针所指的位置。

如果当前栈已满进行入栈时会产生“栈上溢”的错误。2）退栈运算

退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给指定的变量，再将栈顶指针减1。

当栈顶指针为0时表示此时为空栈，不进行退栈操作，否则会发生“栈下溢”的错误。3）读栈顶元素

将栈顶元素赋给某一指定变量，但栈顶指针不变。这个操作不会删除元素，如果为空栈时是读不到元素的。

如果要用我们学过的编程语言去实现请大家自己思考一下如何实现？

1.4.3队列

front

rear

队列即是允许在一端进行插入，而在另一端进行删除的线性表。

允许插入的一端称为队尾，通常用一个尾指针rear指向队尾；

允许删除的一端称为队首，通常用一个队首指针front指向排队元素的前一个位置。在队列中最先插入的元素最先被删除，队列遵循“先进先出”或“后进后出”的规则。

往队尾插入一个元素称为入队，从队头删除一个元素称为退队运算。

frontfront

rear

front

rear

rear

图3

图1图2