数据结构习题.ppt

数据结构与算法 主讲教师 李琼 E mail liqiong 2 22单链表的就地逆置 q LNode malloc sizeof LNode scanf d 头结点 p L next L next NULL while p NULL q p next p next L next L next p p q 作业 3 15假设以顺序存储结构实现一个双向栈 即在一维数组的存储空间中存在着两个栈 它们的栈底分别设在数组的两个端点 试编写实现这个双向栈tws的三个操作 初始化inistack tws 入栈push tws i 出栈pop tws i 的算法 其中i为0或1 用以分别指示设在数组两端的两个栈 StatusInit Stack BDStacktype typedefstruct Elemtype base 2 Elemtype top 2 BDStacktype 012345678 012210 Statuspush BDStacktype 012345678 012210 2 2 012345678 012210 2 2 Statuspop BDStacktype 3 5 21假设稀疏矩阵A和B均以三元组顺序表作为存储结构 试写出矩阵相加的算法 另设三元组C存放结果矩阵 definemaxsize10000typedefstruct inti j ElemTypev triplet tripletdata MAXSIZE 1 233 125 139 21 3 232 112 138 230 112 125 1317 21 3 4 voidTSMatrix Add TSMatrix A TSMatrix B TSMatrix C intpa pb pc intx Elemtypece pa 1 pb 1 pc 1 C data 0 i A data 0 i C data 0 j A data 0 j C data 0 v 0 for x 1 x A data 0 i x 对矩阵的每一行进行加法 while A data pa i x pa while B data pb i x pb while A data pa i x elseif A data pa j B data pb j C data pc i x C data pc j B data pb j C data pc v B data pb v pb pc else C data pc i x C data pc j A data pa j C data pc v A data pa v pa pc while A data pa i x 插入A中剩余的元素 第x行 C data pc i x C data pc j A data pa j C data pc v A data pa v pa pc while B data pb i x 插入B中剩余的元素 第x行 C data pc i x C data pc j B data pb j C data pc v B data pb v pb pc C data 0 v pc 6 42编写递归算法 计算二叉树中叶子结点的数目 按先序遍历序列建立二叉树的二叉链表 已知先序序列为 ABC DE G F typedefstructBiTNode Elemtypedata structBiTNode lchild rchild BiTNode BiTree crt bt pre BiTreeT Elemtypech printf ch scanf c 先序序列为 ABC DE G F A B C D E G F 求叶子结点的递归算法 intleafCount BiTNodebt if bt return0 空树没有叶子 elseif bt lchild 左子树的叶子数加上右子树的叶子数 voidleafCount BiTNodebt int count if bt NULL if bt lchild NULL 7 14编写算法 由依次输入的顶点数目 弧的数目 各顶点的信息和各条弧的信息建立有向图的邻接表 定义边结点的结构typedefstructe node intadjvex intweight structe node next E NODE 定义邻接表的表头类型typedefstructv node intvertex E NODE link V NODE V NODEhead MAXN voidcreat adj list V NODEhead intt intn t为有向图标识 n为顶点数目 inti w 1 v 1 v为弧起点 w为弧终点 E NODE p for i 1 i n i hea