5.<Data Structures and Program Design in C++) Robert L Kruse Alexandeer J Ryba编,高等教育出版社2002(影印版) 6.《 DATA STRUCTURES AND ALGORITHM ANALYSIS》 CLIFFORD A. SHAFFER编 PRENTICE HALL出版公司1996出版 七、编写大纲的执笔人和审定人 执笔人:韩家新 审定人:朱战立 附件一部分课程设计题目 1.排序算法比较 利用随机函数产生30000个随机罄数,利用插入排序、起泡排序、选择排序、快速排序、堆排序、 归并排序等排序方法进行排序,并统计每一种排序上机所花费的时间。 2.图的深度周游 对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用堆栈的五种基本运算 (清空堆栈、压栈、弹岀、取栈顶元素、判栈空)实现图的深度优先搜索周游 3.图的广度周游 对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用队列的五种基本运算 置空队列、进队、出队、取队头元素、判队空)实现图的广度优先搜索周游。 4.二叉树的周游 对任意给定的二叉树(顶点数自定)建立它的二叉链表存贮结构,并利用栈的五种基本运算(置空 栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种周游,输岀三种周游 的结果 5.链表操作 利用链表的插入运算建立线性链表,然后利用链表的査找、删除、计数、输岀等运算反复实现链表 的这些操作(插入、删除、查找、计数、输出单独写成函数的形式),并能在屏幕上输岀操作前后 的结果 6.设计一元稀疏多项式简单计数器 输入并建立多项式 3)8份别为第项的系数和指数。序列按指数降序排,e2..cn,en,其中n是多项式的项 (3)多项式a和b相加,建立多项式a+b,输出相加的多项式 (4)多项式a和b相减,建立多项式a-b,输出相减的多项式。 用带表头结点的单链表存储多项式 测试数据 (1)(2x+5×8-3.1×11)+(7-5×8+11×9) (2)(6×3-×+44x2-1.2x9)(-6×-3+54×2+7.8×15 (3)(x+x2+x3)+0 (4)(x+x3)-(-x-×-3) 7.实现两个链表的合并 基本功能要求 1)建立两个链表A和B,链表元素个数分别为m和n个 (2)假设元素分别为(x1X2…Xm),和(y1,y2,…!n)。把它们合并成一个线形表C,使得 当m>=n时,C=X1,y1,X2y nini 当n>m时,C=y1,X1,y2,X2…Ym,Xm…,yn 输出线形表C (5)用直接插入排序法对C进行升序排序,生成链表D,并输出链表D 测试数据 (1)A表(30,41,15,12,56,80)5．《Data Structures and Program Design in C++》Robert L. Kruse,Alexandeer J. Ryba编，高等教育出版社2002（影印版） 6．《DATA STRUCTURES AND ALGORITHM ANALYSIS》CLIFFORD A. SHAFFER编， PRENTICE HALL出版公司1996出版 七、编写大纲的执笔人和审定人 执笔人：韩家新 审定人：朱战立 附件一 部分课程设计题目 1．排序算法比较 利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、 归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 2．图的深度周游 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算 （清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索周游 3．图的广度周游 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算 （置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。 4．二叉树的周游 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空 栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游 的结果。 5．链表操作 利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表 的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后 的结果。 6．设计一元稀疏多项式简单计数器 （1） 输入并建立多项式 （2） 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项 数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。 （3） 多项式a和b相加，建立多项式a+b，输出相加的多项式。 （4） 多项式a和b相减，建立多项式a-b，输出相减的多项式。 用带表头结点的单链表存储多项式。 测试数据： （1）(2x+5x8-3.1x11)+(7-5x8+11x9) （2） (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15) （3）(x+x2+x3)+0 （4）(x+x3)-(-x-x -3) 7．实现两个链表的合并 基本功能要求： （1）建立两个链表A和B，链表元素个数分别为m和n个。 （2）假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。把它们合并成一个线形表C，使得： 当m>=n时，C=x1,y1,x2,y2,…xn,yn,…,xm 当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn 输出线形表C （5） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。 测试数据： （1） A表（30，41，15，12，56，80）