博客作业03--栈和队列

1.学习总结(2分)

1.1 写出你认为本周学习中比较重要的知识点关键词，如逻辑结构、栈、队列、存储结构等。

1.栈

（1）栈的定义及操作，包括：建栈，初始化栈，入栈，出栈，判断栈是否为空，取栈顶元素，销毁

（2）顺序储存结构

（3）链式存储结构

（4）栈的应用：表达式求值，求解迷宫问题

2.队列

（1）队列定义：建队列，初始化队列，入队，出队，判断队是否为空，销毁

（2）顺序存储结构，环形队列

（3）链式存储结构

（4）队列的应用：求解报数问题，求解迷宫问题

1.2 使用思维导图将这些关键词组织起来。

2.PTA实验作业（4分）

题目1：jmu-字符串是否对称

设计思路（伪代码或流程图）

主函数：定义栈并初始化s定义字符数组存初始字符串ch输入初始字符串到数组中for(i=0;ch[i];i++)    if(栈为空时)入栈ch[i]    else if(栈顶元素等于ch[i])出栈    else 入栈ch[i]endif(栈为空)输出yeselse 输出no

代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

PTA提交列表说明。

这道题还是挺简单的，刚开始还不太懂栈的应用，所以写的是全部存入栈中再全部拿出，进行比较，虽然也对了，但是明显比现在的方法复杂，于是用现在的方法又写了一遍。

题目2：jmu-报数游戏

设计思路（伪代码或流程图）

主函数：定义循环变量i，队列总元素n，输出第几个元素m定义空队列输入n和mfor(i=0;i

代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

PTA提交列表说明。

这道题也是比较简单的，一开始做的时候，不知道用队列要怎么做，没有思路想了很久，后来翻了翻课本，知道了，可以将队首元素出列，再入列到队尾，模拟循环的情况，知道了思路一下子就写出来了。

题目3：银行业务队列简单模拟

设计思路（伪代码或流程图）

主函数：定义两个队列表示A，B定义数组，并输入原始人群队列for(i=0;i

代码截图（注意，截图、截图、截图。代码不要粘贴博客上。不用用···语法去渲染）

PTA提交列表说明。

第一个错误是是最大随机N的点错误，后来加大了队列可能达到的最大长度，就对了。

3.截图本周题目集的PTA最后排名（3分）

3.1 栈PTA排名

3.2 队列PTA排名

3.3 我的总分：253

4. 阅读代码（必做，1分）

题目描述：希尔排序

#include
    
     #include
     
       #define MAXNUM 10 void main(){    void shellSort(int array[],int n,int t);//t为排序趟数    int array[MAXNUM],i;    for(i=0;i
      
       =i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行            array[j+dk]=array[j];        if(j!=i-dk)            array[j+dk]=temp;//插入    }} //计算Hibbard增量int dkHibbard(int t,int k){    return (int)(pow(2,t-k+1)-1);} //希尔排序void shellSort(int array[],int n,int t){    void shellInsert(int array[],int n,int dk);    int i;    for(i=1;i<=t;i++)        shellInsert(array,n,dkHibbard(t,i));}

分析：

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法过程：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

该算法若数据基本有序且记录较少时，当文件初态基本有序时直接插入排序所需的比较和移动次数均较少，效率是非常好的，但是数据一多就有不可靠性，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。