说明.txt

常用算法与数据结构原代码

1. 顺序存储线性表的插入：SqInsert.cpp。

2. 计算数字表达式的值：Expression.cpp。
   （乘幂运算符的优先级最高，自右向左运算。加减乘除自左向右运算。括号改     变运算符的优先级。）

3.用栈计算Ackermann函数A(n,x,y)：Ackermann.cpp。
定义如下：A(n,x,y)=x+1,n=0;
                  =x,n=1,y=0;
                  =0,n=2,y=0;
                  =1,n=3,y=0;
                  =2,n>=4,y=0;
                  =A(n-1,A(n,x,y-1),x),n!=0,y!=0。

4.用递归计算Ackermann函数A(n,x,y)：Ackermann1.cpp。

5.    某公司有一个顾客接待站，在单位时间内随机的有几位顾客到接待站来询   问。设每位顾客的接待时间是某个范围内的随机值。只有一名接待人员，要求   程序模拟统计在设定时间内，接待员的总空闲时间和顾客的平均接待时间
  ：Customer.cpp。

6.   设有n行n列两维数组，因其下三角元素全为零，不再存储其下三角的零元    素，只将其上三角的元素按行优先存储于一维数组中。编制一个函数，要求函   数在不引入工作数组情况下，将按行优先存储的上三角元素该为按列优先存储   ：Array.cpp。
7.   编制利用碾转相除法求两个多项式的最大公因式的函数：CommFactor.cpp。

8.   将稀疏矩阵a转置生成稀疏矩阵b。设稀疏矩阵的非零元素已按行号递增，同   一行按列号递增的顺序以三元组形式存于某数组中：Transpose.cpp。

9.   建立一个元素全为零的稀疏矩阵的十字链表：createNullMat();
   在十字链表中插入一个节点：insertNode();
   输入数据建立十字链表：readMat();
   两个相同行数和列数的稀疏矩阵加法运算：matAdd()。

10.  编制一个函数，实现在两个已知字符串中找出所有非空最长公共子串的长度    和最长公共子串的个数：CommStr.cpp。

11.  编制一个函数，实现将已知字符串s1中的所有与字符串str1相同的字符列替    换成字符串str2的字符列，并将替换后的结果字符串存于字符数组s2
   ：replace.cpp。

12.  编制一个字符串整理函数 ver(char *s)，实现将已知字符串s中的前导空白    类子符和尾随的空白类字符去掉，并将字符串非空白类字符之间的连续多个空    白类字符缩减为一个空白符：trim.cpp。

13.  用已知字符串s中的字符，生成由其中n个字符组成的所有字符排列。设n      小于字符串s的字符个数，其中s中的字符在每个排列中最多出现一次
   ：perm.cpp。

14.  KMP模式匹配算法：KMP_match.cpp。
   寻找模式各字符失败链接值的函数：faillink();
   KMP模式匹配函数：kmp_match();

15.  简单模式匹配算法：simple_match.cpp。

16.  树的遍历：tree.cpp。
   前序遍历（用递归实现）：re_preorder();
   前序遍历（采用栈）：st_preorder();
   层次遍历（采用队列）：lev_order();

17.  二叉树的中序遍历（采用链接栈）：midorder.cpp。

18.  二叉查找树：bintree.cpp。
   静态查找函数：static_search();
   动态查找函数：dynamic_search();
   查找树上插入新节点：insert();
   删除查找树键值为key的结点：del();

19.  穿线树：linetree.cpp。
   找出由指针t所指节点的中序遍历的前驱节点：prev();
   找出指定节点的中序遍历的后驱节点：succ();
   插入新节点，使新节点是某参考节点的中序遍历的前驱节点：left_insert();
   插入新节点，使新节点是某参考节点的中序遍历的后继节点
   ：right_insert(); 
   利用前述函数，对给定的字符串，建立一棵查找穿线树：th_sort_t();
   中序遍历：midorder();

20.  已知字符列的前n个元素，建立一棵二叉树：buildtree.cpp。
   以str[i]为根，左、右子节点分别为str[2*i+1]和str[2*i+2]：build1();
   中间为根，前半元素为左子树，右半元素为右子树：build2();

21.  编制已知二叉树的前序遍历和中序遍历序列，构造对应二叉树的函数
    ：restore.cpp。

22.  已知二叉树，将其改建为中序穿线树：thread.cpp。

23. 筛选法求质数。程序用一个无符号整数数组代表筛，它的每一位对应一个整数。依次为3,5,7,9,11,...。screen.cpp

24. 计算n阶对称矩阵A的平方B,B也是n阶对称矩阵，以下三角形式存储：matrix.cpp