算法与数据结构课程设计.doc

算法与数据结构课程设计一、线性表题1、建立一个单链表，显示链表中每个节点的数据，并做删除和插入处理。例：（掌握线性表在链式存储结构下的基本运算的实现。）1、 功能（1） 建立以带头结点的单链表（2） 显示链表中每个结点的数据（3） 在单链表中指定位置插入指定数据并输出单链表中所有数据（4） 删除单链表中指定的结点并输出单链表中所有数据2、 输入要求输入单链表中所有数据，插入的数据元素的位置、值，要删除的数据元素的位置。3、 测试数据单链表中所有数据：12，23，56，21，8，10，15，67，90，32插入的数据元素的位置、值：1，28要删除的数据元素的位置：10概要设计（1） 算法思想：由于在操作过程中要进行插入、删除操作，为运算方便，选用单带头结点的单链表作数据元素的存储结构。对每个数据元素，由一个数据域和一个指针域组成，数据域放输入的数据值，指针域指向下一个结点。（2） 数据结构 单链表结点类型： typedef struct Node int data; struct node *next;ListNode;带头结点的单链表类型定义： typedef ListNode *LinkList;（3） 模块划分： 建立点头结点的单链表CreatLinkList; 显示链表中每个结点的数据PrintList； 在单链表中指定位置插入指定数据并输出单链表中所有数据InsertList; 删除单链表中指定的结点并输出单链表中所有数据DeleteList; 主函数mian()，功能是给出测试数据值，建立测试数据值的带头结点的单链表，调用PrintList函数、InsertList函数、DeleteList函数实现问题要求。详细设计 见程序LinkList.c题2、约瑟夫环（Joseph）问题的一种描述是：编号1，2，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数），一开始，任选一个正整数作为报数上线值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1开始报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。二、数组、栈和队列题3、用矩阵MN表示一个迷宫，0和1分别表示通路和墙壁。试求出从入口点到达出口点的一条通路。基本思想:若当前位置可以通过,则压入栈中,否则探求下一位置,若走不通,则回朔,迷宫大小:M*N.迷宫设置自定义。求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。 为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号。 (a) 迷宫的图形表示 (b) 迷宫的二维数组表示 求迷宫中一条从入口到出口的路径的算法可简单描述如下:设定当前位置的初值为入口位置:do 若当前位置可通,则 将当前位置插入堆栈顶;若该位置是出口位置,则结束;否则切换当前位置的东邻块为新的当前位置; 否则,若堆栈不空且栈顶位置尚有其他方向未经探索;则设定新的当前位置为沿顺时针方向转到的栈顶位置的下一相邻块;若栈不空但栈顶位置的四周均不可通,则删去栈顶位置; 若栈不空,则重新测试新的栈顶位置, 直至找到一个可通的相邻或出栈至栈空;题4、停车场管理。设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场。每辆停放在车场的车在它不离开停车场时必须按它停留的时间长短交费。试为停车场编制按上述要求进行管理的模拟程序。以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离开”信息，汽车牌照号码以及到达或离去的时刻。与每一组输入数据信息相对应的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。（提示：需另设一个栈，临时停放为给要离去的汽车让路从停车场退出来的汽车，也用顺序存储结构实现。）测试数据设n，输入数据为：（，），（，），（，），（，），（，），（，），（，），（，）。其中：表示到达，表示离去，表示输入结束。其中：（，）表示1号牌照车在5这个时刻到达，而（，）表示1号牌照车在15这个时刻离去。三、树题5、请使用数组输入二叉树的结点数据，以结构体数组表示法创建二叉树，完成后将结构数组内容输出。 struct tree int data; int left; int right;typedef struct tree teeenode;treenode btree15;void main() btree root=NULL;int data10=5,6, 4,8,2,3,7,1,9;root=createbtree(data,9); /*创建二叉树*/printf(“树的结点内容n”);printfbtree(root); /*输出二叉树内容*/注：创建二叉树结点数据的策略有三个，如下：l 将第一个要创建的元素插入成为根节点。l 将元素值与结点值比较，如果元素值大于结点值，将此元素送往结点的右儿子结点，如果右儿子结点不是空的，需要重复比较，否则创建结点将元素值插入。l 如果元素值小于结点值，将此元素送往结点的左儿子结点，如果左儿子结点不是空的，需要重复比较，否则创建结点将此元素值插入。例如：二叉树结点值输入的数据顺序是5，6，4，8，2，3，7，1，9。按照上述策略创建的二叉树，如下图所示：另附：TC3常用快捷键使用f1：帮助f2：保存f3：新建f4：运行到光标处f5：watch窗口f6：窗口切换f7：进入函数体运行f8：单步