《数据结构》课程设计报告
课题名称： 迷宫设计
专业班级：
学 号：
姓 名：
指导老师：
20##年12月
一、课题名称
迷宫问题(栈和队列)
求迷宫问题就是求出从入口到出口的所有路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。
二、课题设计的基本思想，原理和算法描述
1，给点一个迷宫图，求一条从指定入口到出口的路径。假设迷宫如图所示
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}。对于图中的每个方块，用0表示通道，用1表示墙。所求的路径是最短路径，即在求得的路径上不能重复出现同一个通道块。
为了表示迷宫，设置一个数组mg。为了算法方便，在一般的迷宫外围加了一条围墙，迷宫对应的迷宫数组mg，如上图所示，由于迷宫四周加了一条围墙，因此mg的行数列数均加2 （int mg[M+2][N+2]=）
2, 在算法中用到的栈采用顺序栈存储结构，即将栈定义为：
struct
{
int i;int j;int di;
} Stack[MaxSize],path[MaxSize];
int top=-1;
3，建立如下主函数调用下述算法：
void main()
{
printf("迷宫所有路径如下:\n");
mgpath();
}
三、源程序及注释
#include <stdio.h>
#define M 4 //行数
#define N 4 //列数
#define MaxSize 100 //栈最多元素个数
int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框
{1,1,1,1,1,1},
{1,0,0,0,1,1},
{1,0,1,0,0,1},
{1,0,0,0,1,1},
{1,1,0,0,0,1},
{1,1,1,1,1,1}
};
struct
{
int i;int j;int di;
} Stack[MaxSize],path[MaxSize]; //定义栈和存放最短路径的数组
int top=-1; //栈顶指针
int count=1; //路径数计数
int minlen=MaxSize; //最短路径长度
void mgpath() //路径为:(1,1)->(M,N)
{
int i,j,di,find,k;
top++;
Stack[top].i=1;
Stack[top].j=1;
Stack[top].di=-1;mg[1][1]=-1; //初始结点进栈
while(top>-1) //栈不空时循环
{
i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M && j==N) //找到了出口,输出路径
{
printf("%4d: ",count++);
for (k=0;k<=top;k++)
{
printf("(%d,%d) ",Stack[k].i,Stack[k].j);
if((k+1)%5==0) printf("\n\t"); //输出时每5个结点换一行
}
printf("\n");
if(top+1<minlen) //比较找最短路径
{
for (k=0;k<=top;k++)
path[k]=Stack[k];
minlen=top+1;
}
mg[Stack[top].i][Stack[top].j]=0; //让该位置变为其他路径可走结点
top--; i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
}
find=0;
while(di<4 && find==0) //找下一个可走结点
{ di++; //找下一个方位
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) //找到了下一个可走结点
{ Stack[top].di=di; //修改原栈顶元素的di值
top++; //下一个可走结点进栈
Stack[top].i=i;
Stack[top].j=j;
Stack[top].di=-1;
mg[i][j]=-1; //避免重复走到该结点
}
else //没有路径可走,则退栈
{
mg[Stack[top].i][Stack[top].j]=0; //让该位置变为其他路径可走结点
top--; //将该方块退栈
}
}
printf("最短路径如下:\n");
printf("长度: %d\n",minlen);
printf("路径: ");
for (k=0;k<minlen;k++)
{
printf("(%d,%d) ",path[k].i,path[k].j);
if ((k+1)%5==0) printf("\n\t"); //输出时每5个结点换一行
}
printf("\n");
}
void main()
{
printf("迷宫所有路径如下:\n");
mgpath();
}
四、运行示例及结果分析
五、调试和运行程序过程中产生的问题及采取的措施
用数组表示迷宫，用顺序栈存储数据。
程序中用到最下长度变量minlen，将最大变量maxsize赋值给minlen，比较所有最短路径，找出最下路径。
if(top+1<minlen)
{
for (k=0;k<=top;k++)
path[k]=Stack[k];
minlen=top+1;
}
六、对课题相关算法的讨论、分析，改进设想
求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。
求解迷宫(1,1)到(M-2,N-2)路径的过程是:先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中方块即为路径。否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。
为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。
七、总结
栈的主要特点是“后进先出”，因此栈也称为后进先出表。运用栈对迷宫进行编程，可以很快的找到最短路径的长度，算出最短路径。
八、参考文献
【1】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）.北京：清华大学出版社，2009.
【2】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）上机实验指导.北京：清华大学出版社，2009.
【3】 李春葆，曾慧，张植民. 数据结构程序设计题典. 北京：清华大学出版社，2002.
第二篇：总结围护结构设计
总结围护结构设计，我实在不够资格，原因有二：第一，我既不是学地下结构的，也不是学岩土的，列位大虾中有不少是“关公”级的人物，我在这儿耍大刀岂不贻笑大方；第二，我做围护结构设计不过4年，工程实践经验实在比不上很多老前辈。所以用“戏说”。
但为了让更年轻的同志少走弯路，我就恬着脸写点东西，全当科普读物。另外，我写的未必全对，有不对的地方请大家指正。
我刚才说了，我围护结构工程经验不多，记得我是从20xx年开始接触围护结构设计的，开始是南京的挡土墙，后来是北京的桩锚支护，到20xx年接触上海的板式内支撑体系，包括地下连续墙、SMW工法桩，以及20xx年接触杭州的钻孔咬合桩。从我接触围护结构这4年里，我个人认为，有四个基本问题是在设计中要搞清楚。
第一：水土问题（也就是工程水文地质情况）。
水土问题不仅是围护结构选型的因素，同时也是确定围护结构侧壁压力的依据。
土的性质和水有非常大的关系。如：含水饱和的粉砂、细砂很容易失稳；而粘性土一旦失去水份，其强度又会很高（例如上海的⑥层土，我桌子上有一块，有兴趣可以去摸摸看）。对于围护结构来说，土中有没有水，对围护结构的选形和设计起重要作用。例如，北京城铁东直门站采用桩锚式支护，桩径1m、间距1.4m，桩间采用钢筋网喷射混凝土。反之，如果地下水位较高，则应考虑采用止水能力强的围护结构形式。象地下水位较高的南京、上海、杭州、天津等地，其围护结构的选择就受到水的因素制约。
但同是地下水位较高的地区，土层条件不同，围护结构的选型范围又有较大出入。如，杭州地区基坑围护可以采用桩锚体系（类似北京）结合轻形井点降水或围护结构自止水实现。而在上海地区，锚杆就很难实施，原因是上海土层较软，能够起作用的锚杆需要打得很长，基坑变形难以控制。听吴老总讲起广州有个李限奎发明了用斜打的工法桩代替锚杆的方法，据说变形还是很大。
在整个基坑开挖过程中，基坑内外的水总是在变化的，既有有利于围护结构的变化，又可能发生不利的变化。根据杭州围护结构专家的说法，围护结构无论采用何种形式，基坑开挖后，基坑外的地下水
位均会有不同程度的降低，上海南站施工监测的结果也证实了这种说法。实际上，基坑周遍有条件的话，降低坑外土体内水位是改善围护结构受力条件的好方法。当然，水的变化也可能导致不利的情况出现，如：暴雨、洪水或坑外埋设的水管因土体变形导致的爆裂等等。因此设计中应对地下水的情况予以充分考虑，要认清水是怎么形成的？是上层滞水还是承压水？这都是设计前应该搞清楚的问题。 关于承压水的问题，我想多提两句。我参加过几次地铁基坑围护结构评审（杭州、上海），首要问题往往就是承压水问题。上海南站基坑开挖过程中发生了一次小事故，给我敲了警钟。
我们南锦区间4区局部有一个区间泵房，区间深15.6m，泵房深17.92m，开挖整区间时基底没有出现问题，再挖0.5m即出现涌砂现象。经过紧急处理，情况很快控制住了。为了搞清原因，我们进行了分析。根据地质报告，该段基底以下5.5m处⑤21灰色砂质粉土为弱承压水层，弱承压水头高度在13.2m左右，开挖基坑后，应有至少有8m厚的隔水层才能满足基坑抗承压水的要求。该段区间基底位于④1灰色淤泥质粘土层，局部泵房底距⑤21层顶仅2.3m。可能由于该段基坑均采用了注浆加固措施，因此开挖至区间底部没有发生问题，但开挖局部泵房时，由于隔水层太薄，导致涌砂现象出现。在此前，我也怀疑是此处的一个钻孔回填没有处理好，导致深层可能存在承压水的⑦层土与⑤21层土沟通造成涌砂出现，但从涌砂的点状分布看，排除了钻孔造成的涌砂的可能性。
因此，水的问题是威胁基坑安全的重要因素，应引起年轻弟兄们的足够重视。
第二、围护结构安全等级的确定。
必须深入了解基坑周边情况，包括管线、房屋、构筑物等，以确定基坑安全等级，也是确定围护结构的形式的依据之一。王总已经几次提醒我们，不要把基坑等级定的太高，应该根据周边建筑物、构筑物及管线的情况，有针对性的确定安全等级，以及围护结构的形式。而我们往往为了省事，本来局部是一级、大部可定成二级的基坑，统统定成一级。这次M7线围护结构总体院的会审期间也提到这个问题。
地铁基坑保护等级标准表（上海）
保护等级 地面最大沉降量及围护结构水平级位移控制要求
一级 1.地面最大沉降量≤0.1%H；2.围护结构最大水平位移≤0.14%H；3.Ks≥1.8
二级 1.地面最大沉降量≤0.2%H；2.围护结构最大水平位移≤0.3%H；3. Ks≥1.6
三级 1.地面最大沉降量控制在≤0.5%H2.围护结构最大水平位移≤0.7%H；3.Ks≥1.4
从表中可以看出，不同的等级变形控制值是不同的（注意不同的地区，基坑的安全等级的划分也有可能不同，上表即是《上海地铁基坑工程施工规范》（SZ-08-2000）的划分方法，而《建筑基坑支护技术规程》（JGJ 120-99）与之不同）。基坑等级定高，可能导致基坑变形对围护结构的刚度要求提高、围护结构加深、支撑增加道数，另外可能还要增加坑底加固措施等等，实际上是增加了投资。
关于围护结构的深度，我认为，一方面要满足基坑的稳定的计算要求；一方面要考虑基坑范围土体内水的渗流对基坑的影响；另一方面也要解决一个经济问题。同时，应该建立强支撑、弱围护的观念。围护可能是永久的，但支撑是临时的。
我们结构设计往往不太重视投资。实际上，地下车站的土建投资很大一部分是用在围护上，围护结构的经济与否，直接影响土建投资。因此，围护结构评审，一方面要审查围护结构的安全性，另一方面也要审查围护结构的经济性。
第三、计算模型及方法的确定。
确定围护结构的形式后，该解决计算模型问题。
以上海南站为例，车站的围护结构有两种：一种是地下连续墙，一种是SMW劲性混凝土搅拌桩。 上海采用地墙一般有两种做法：一种是有内衬的，一种是无内衬的。我目前接触的都是有内衬的那种。区别从字面上可以大致看出，但虽说同是地下墙，没有内衬的需要采用刚性连接——十字钢板接头。因此从造价上，单墙不一定比双墙便宜。地下连续墙不仅在施工期间起围护结构的作用，使用阶段地下连续墙作为主体结构的一部分参与结构受力；在地下连续墙内侧相与顶、底板及中楼板的位置预埋
接驳器与板内钢筋连为一体。这是上海的习惯做法。另，如果抗浮需要，还可以在地下连续墙内表面预留拉结筋，以确保内衬墙与地下连续墙结合为整体。
工法桩与钻孔灌注桩的区别是：工法桩在使用期间不参与内部结构受力，即按照临时结构考虑。但如果是型钢不拔除，可以考虑起抗浮作用。 施工阶段围护结构内力及变形分析计算选用能反映从基坑开挖到回筑过程中结构受力变化的计算方法，要点如下：
“结构一般按平面问题考虑，取单位长度进行结构分析，采用平面杆系有限元法计算。（端头井、换乘节点按空间结构计算）
基坑开挖阶段，把围护墙视为侧向地基上的梁；浇注底板后，分两种情况考虑：
地下墙：考虑与主体结构的共同作用。结构为弹性地基上带刚域的变截面框架，内部结构板与地下墙的连接按刚接考虑。
SMW桩：不考虑边墙的作用，顶﹑底板作为围护结构的可压缩支点，按拆撑和水平构件浇注的实际顺序计算。
为了模拟分布施工过程各阶段不同的受力状态，根据开挖、加撑、施作结构﹑拆撑及回填时的构件组成和荷载变化将结构的受力过程分为若干个相对独立的阶段。
在分阶段计算时考虑结构受力的继承性。按“先变形，后支撑”的原则进行分析。受力过程中围护墙的刚度无变化时（SMW桩在基坑开挖和回筑阶段；地下墙在基坑开挖阶段），把设置支撑前的墙体位移作为初始条件，用总和法直接求得当前阶段结构的内力和变形。地下墙与内部结构结合后，结构组成和刚度发生变化，采用增量法求得每个阶段结构的内力和变形增量。
分别用水平弹簧和竖向弹簧模拟坑底地层对墙体水平位移﹑墙趾及底板垂直位移的约束作用。竖向弹簧不能受拉。基床系数取值考虑降水加固影响。为了反映基坑开挖面附近土体受到扰动的实际情况，
假定自开挖面以下4m深度的范围内，水平基床系数从零线性增大到定值10000KN/m3。用压缩刚度等效的弹簧模拟临时支撑对墙体变形的约束作用。侧向水土压力取值：施工阶段水土合算。视基坑等级的不同，一级基坑取主动土压力与静止土压力之和的平均值，二级基坑取主动土压力，三角形分布；开挖侧的土压力由静止土压力和与墙体变形一次方呈比例的土抗力组成。
墙体的计算刚度：SMW桩——按内插焊接工字钢的刚度计算，考虑水泥土的作用后增大10%。地下墙——施作内衬后，按两者叠合的整体墙计算刚度。”
第四、土压力的计算取值问题。
土压力的计算，应按照地方规范执行。比如：上海地区施工期间是水土合算，即土的抗剪强度指标采用总应力C、Φ值和天然重度γ(或饱和容量)计算土压力，并认为水压力已包括在内；而杭州地区施工期间则采用水土分算，采用有效应力指标，即土的抗剪强度指标采用有效应力C、Φ值和浮容量γ计算土压力，另解水压力。（根据有效应力原理σ′=σ-u）总应办法应用方便，适用于不透水或弱透水的粘性土层。有效应力法应用于砂性土层。
关于土的抗剪强度指标C、Φ的取值问题，它们的大小关系道围护结构的刚度、强度、稳定性。实际工程中，我也走了弯路。做上海南站时，地勘报告仅给了一组抗剪强度指标C、Φ，我们别无选择，也没有搞清楚是什么指标。后来做杭州地铁的时侯，地勘报告给了四组C、Φ值。（1）有直剪固快试验指标C、Φ；（2）三轴试验不固结不排水指标CU、ΦU，（3）三轴试验固结不排水总应力指标CCU、ΦCU；（4）三轴试验固结不排水有效应力指标C’、Φ’。这下儿傻了，到底选择哪个指标？因为不懂这几个指标的由来，只好查杭州规范。还好规范里有。
到底如何选用指标呢？
（1）当施工速度较快，地基土的透水性和排水条件不良时，可采用三轴不排水、不固结或直剪试验结果。
（2）当地基荷载增长速率较慢，地基土的透水性较好，排水较好时，（如粘土中夹砂层），可采用固结排水或慢剪试验结果。
（3）条件介于两者之间时，可采用固结不排水或固结快剪试验结果。
关于有效应力指标，由于实验设备和实验周期的问题，大多数勘察报告是不提供的，一般只给直剪固快指标。“相对于三轴试验而言，直剪试验的设备简单，操作方便，故目前在实际工程中使用比较普遍。然而，直剪试验中只是用剪切速率的“快”与“慢”来模拟试验中的“不排水”和“排水”，对试验排水条件的控制是很不严格的，因此在有条件的情况下应尽量采用三轴试验方法。另外，
GBJ 123-88《土工试验方法标准》规定直剪试验的固结快剪和快剪试验只适用于渗透系数小于10－6 cm/s的粘土，对于其它的土类，则不宜采用直剪试验方法。”
“注意：在实际工程中，地基条件与加荷情况不一定非常明确，如加荷速度的快慢、土层的厚薄、荷载大小以及加荷过程等都没有定量的界限值，而常规的直剪试验与三轴试验是在理想化的室内试验条件下进行，与实际工程之间存在一定的差异。因此，在选用强度指标前需要认真分析实际工程的地基条件与加荷条件，并结合类似工程的经验加以判断，选用合适的试验方法与强度指标。”
关于启明星软件，我认为它的说明书中水土分算的公式是错的。其土压力按Rankine土压力理论计算，土压力为：
水土分算：（见说明书） -（1）（不会用特殊字符）
如果程序是这样算的，肯定有错，（起码量刚是错的）。请大家注意。
以上几点是我的（或是别人的）一点体会。引用了很多资料，包括王总关于围护结构计算的内容。如果各位感兴趣，我可以将我手头的资料共享给大家。另外，强烈建议让王总给大家系统地讲一讲围护结构的计算。