数据结构：数组.ppt

第五章数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1数组的定义和特点定义5.2数组的顺序存储结构次序约定以行序为主序以列序为主序5.3矩阵的压缩存储对称矩阵三角矩阵稀疏矩阵的压缩存储方法顺序存储结构三元组表带辅助行向量的二元组表求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义2)子表分析法：若子表为原子，则为空表ls=NIL非空表1指向子表1的指针tag=0data否则，依次类推。1指向子表2的指针1指向子表n的指针ls…?例如:?a(x,y)((x))LS=(a,(x,y),((x)))ls5.6广义表操作的递归函数递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1)在每一次调用自己时，必须是(在某种意义上)更接近于解;2)必须有一个终止处理或计算的准则。例如:梵塔的递归函数voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}二叉树的遍历voidPreOrderTraverse(BiTreeT,void(Visit)(BiTreeP)){if(T){Visit(T-data);(PreOrderTraverse(T-lchild,Visit);(PreOrderTraverse(T-rchild,Visit);}}//PreOrderTraverse一、分治法(DivideandConquer)(又称分割求解法)如何设计递归函数？二、后置递归法(Postponingthework)三、回溯法(Backtracking)对于一个输入规模为n的函数或问题，用某种方法把输入分割成k(1k≤n)个子集，从而产生l个子问题，分别求解这l个问题，得出l个问题的子解，再用某种方法把它们组合成原来问题的解。若子问题还相当大，则可以反复使用分治法，直至最后所分得的子问题足够小，以至可以直接求解为止。分治法的设计思想为:在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。例如:梵塔问题:Hanoi(n,x,y,z)可递归求解Hanoi(n-1,x,z,y)将n个盘分成两个子集(1至n-1和n)，从而产生下列三个子问题：1)将1至n-1号盘从x轴移动至y轴；3)将1至n-1号盘从y轴移动至z轴；2)将n号盘从x轴移动至z轴；可递归求解Hanoi(n-1,x,z,y)又如:遍历二叉树:Traverse(BT)可递归求解Traverse(LBT)将n个结点分成三个子集(根结点、左子树和右子树)，从而产生下列三个子问题：1)访问根结点；3)遍历右子树;2)遍历左子树；可递归求解Traverse(RBT)广义表从结构上可以分解成广义表=表头+表尾或者广义表=子表1+子表2+···+子表n因此常利用分治法求解之。算法设计中的关键问题是，如何将l个子问题的解组合成原问题的解。广义表的头尾链表存储表示：typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子,LIST==1:子表typedefstructGLNode{ElemTagtag;//标志域union{AtomTypeatom;//原子结点的数据域struct{structGLNode*hp,*tp;}ptr;