公共基础补充内容.docx

《公共基础补充内容.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、front—A8rear——A3front—►765432176543rear——>2876rear——►54rront32A③排头元后情况1素M退队②元素M、A先后入队后情况①初始状态为空，rear二front二8rear——>8X7F6E5D4C3B2Afront―►18X7F6E5D4C3B•♦■■11VflAL・rear——►>2A1Y④元素B、C、D、E、F、X先后入队可用上图代替教材图1.14,这样会更⑤元素Y入队jH,rear=front=l,队满容易理解循环队列的运算。8X7F6E5Dfront—►4Crear——►3B2⑥排头1Y元素A

2、退队后情况元素M入队时，应存储在9#存储单元中,即rear=9,但这超过了队列的长度8,所以在rear=9=8+l时，应置rear=l,最终元素M存储在了1#存储单元中。参见P8,循环队列的入队运算有关描述。第一章数据结构与算法循环队列入队、出队运算示意图P2：直接递归：P二P+1间接递归：P=Q+2Q=P+3减半递推:f(a)af(2)f(b)为求在（a,b）间函数f（X）与横轴的交点，可取a、b的中点坐标十，求出f（十）来，可看到f（十与f（b）同号，从而可以将［十,b］舍掉（问题规模减半，问题性质未变），接下来可在（比宁）间重复上述操作（递推），直

3、到足够逼近所求为止。P4：一般来讲，同一种逻辑结构可采用不同的存储（物理）结构；反之，同一种存储（物理）结构可用于实现不同的逻辑结构。有序表：后件不大于前件P5：线性表示意图（a】，&2，,a：,,如）a】—迦―••…—舛―•.…f务P5上半页资料原话“线性结构又称线性表”，这里的“线性表”代指了所有“线性结构”。可同一页的下半页，又提到了一个非空线性结构具备了列举出的三个特征，才能被叫做“线性表”，也就是在这里，“线性表”是指二种巒殊附线性结构。••••这样，“线性表”这个概念有了广义和狭义之分，大家今后在阅读此资料时请仔细分辨，资料中后面再提“线性表

4、”，一般是指狭义概念，是指符合列举出的三个特征的二曲特殊旳线性结构。••“一年四季”逻辑结构的“顺序存储”示意图:10241025102610271028102910301031春夏秋冬首行为“存储单元地址”，第二行为“存储内容”建议补充在P4图1.2处,该图为“一年四季”的逻辑结构示意图。P5〜P6:对顺序存储的长度为n的线性表插入与删除有:平均性态均为：n/2,即平均移动n/2个元素最坏情况复杂性均为：n,即最多移动n个元素入栈、退栈演示图top109876F54321EDCBAbottom栈中元素数n=

5、top-bottom

6、+1体会为什么要+11

7、.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈,则元素出栈的顺序是。A、12345ABCDEB、EDCBA54321C、ABCDE12345D、54321EDCBA体会栈是“后进先岀”或“先进后出”表。1.假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom二49,top二30（数组下标），则栈中具有个元素。n=

8、top-bottom

9、+1=

10、30-49

11、+1=20rearfront非循环队列入队、退队演示图8

12、7»654-321非循环队列的元素数n=rear-front循环队列入、退队操作演示frontrear>①初始状态为空，rear=front=8②元素M、A先后入队后情况元素M入队时，应存储在9#存储单元中,即rear二9,但这超过了队列的长度8,所以在rear=9=8+l时，应置rear=l,最终元素M存储在了1#存储单元中。参见P8,循环队列的入队运算有关描述。③排头元素M退队后情况①元素氏C、D、E、F、X先后入队②元素Y入队后,rear=front=l,队满③排头元素A退队后情况以上各步将在授课时逐一加以动态演示。各步的阶段效果图，请详见本资料的

13、第一页，课下可反复对照琢磨。假设某循环队列，初始状态为空（即s=0）时，front=rear=m（即队列的长度为m）,队尾指针为rear,排头指针为front,则该循环队列某时刻所包含的元素个数n为：rear>front时front=rear时rear

14、50,头指针front二5（指向队头元素的前一位置），尾指针rear=29（指向