1、中国石油大学（北京）网络与继续教育学院期 末 考 试数据结构课程设计学习中心：_ 姓名：_ 学号：_ 关于课程考试违规作弊的说明1、提交文件中涉嫌抄袭内容（包括抄袭网上、书籍、报刊杂志及其他已有论文），带有明显外校标记，不符合学院要求或学生本人情况，或存在查明出处的内容或其他可疑字样者，判为抄袭，成绩为“0”。 2、两人或两人以上答题内容或用语有50%以上相同者判为雷同，成绩为“0”。3、所提交试卷或材料没有对老师题目进行作答或提交内容与该课程要求完全不相干者，认定为“白卷”或“错卷”，成绩为“0”。一.课程设计题目选题说明：学号尾号为1、2的学生完成第1题，3、4完成第2题，学5、6完成第3
2、题， 7、8完成第4题， 9、0完成第5题，1. 线性表，基本操作及应用目的：会定义线性表的顺序存储结构，熟悉对顺序表的基本操作，具体函数的定义。掌握链式存储结构。掌握单链表的基本算法，时间性能分析。要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。内容：已知一个线性表，把线性表逆置设计要求：在程序中构造三个子程序分别为：（1）SeqList reverse(SeqList L) /*顺序表的就地逆置*/（2）Void List Traverse(SeqList L) /*遍历顺序表*/（3）SeqList cre
3、ate(int n) /*建立顺序表*/ 2. 串及其应用。目的：掌握串的运算（赋值、比较、连接，插入子串、模式匹配，等等），以便在实际问题背景下灵活应用。要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。内容：完成串的基本操作，如串的赋值、比较、链接、插入等等设计要求：判断字符串t 是否是字符串s的子串，称为串的模式匹配。其基本思想是对串s和t各设一个指针i和j，i的值域是（0，m-n），j（0，n-1），初始值i，j均为0。模式匹配，从S0，T0开始，若S0=T0则i和j指针加1，若在某个位置。Si!=Tj 则
4、主串指针回溯到i=i-j+1, j仍从0开始，进行下一轮的比较，直到匹配成功（jn-1），返回子串在主串中的位置（i-j）。否则，当im-n则为匹配失败,下面代码仅供参考。int index(char s , t , int m,n)while ( )if (si= sj)i+,j+ /*对应字符串相等，指针后移*/ else /*对应字符串不相等，i回溯，j仍为0指针后移*/if (ilchild& ! root-rchild) ()4. 查找或排序操作。目的：掌握各种查找（顺序、二分法、查找树、哈希等等方法，及适用场合并能在解决实际问题中灵活运用。巩固在散列查找时解决冲突的方法及特点。掌握
5、各种排序，插入、希尔、冒泡、快速排序、简单选择、堆排序等方法及适用场合。并在解决实际问题中灵活运用。要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。内容：建立二叉树，并二叉树上实现对给定值进行查找操作，具体内容是编写算法求给定结点在二叉排序树中所在的层数。设计要求：根据题目要求，采用递归方法从根节点开始查找节点p。若待查结点是根结点，则深度为1，否则到左子数或右子树上去查找，查找深度加1。以下部分内容为参考。也可以自己设计程序代码。（1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构
6、。（2）先输入带查找记录的关键字值key，然后在二叉排序树上查找盖记录，如果在二叉排序树中存在该记录，则显示“找到”信息，否则显示“找不到”信息。（3）二叉排序树的二叉链表存储结构描述为typedef struct Bitnode /*定义二叉排序树的节点类型*/ Keytype Key /*取放记录关键值的数据域key*/elemtype ether;/* 存储记录中的其他数据项的域*/ Struct Bitnode * lchild, *rchild /*左右孩子指针域*/ Bitnode, *Bitree;（4）int Level(Bitnode *root，Bitnode *p) if
7、(! p) return 0;if(p=root) return 1;else if (p-data data） return ;else return Level(root-rchild,+1;5. 栈和队列及其应用。目的：栈的特点是好先进后出。其基本操作是入栈，出栈等等，掌握栈的顺序存储结构和链式存储结构，在实际问题背景下灵活应用。队列的特点是先进先出。其基本操作，入队出队等等，队列有顺序存储结构，链式存储结构和循环队列，要在实际问题中灵活运用。要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。内容：请利用两个
8、栈S1和S2来模拟一个队列Q写出进队enqueue,和出队dnqueue函数。设计要求：栈的特点是后进先出，队列的特点是先进先出。所以用个S1和S2模拟一个队列q时。S1做输入栈，逐个元素压栈，模拟队列元素的入队。当需要出队时则在S1退栈并逐个元素压栈S2，结果S1最先入栈的元素在S2中处于栈顶。而S2退栈相当于队列q出队实现了先进先出。显然只有S2为空时，队列也为空。以下为参考代码，也可以自己定义变量，编写代码。（1）int enqueue(stack S1）/* S1是容量为n的栈*/* top1是栈S1栈顶指针 是全局变量*/ if (top1=n& ! Sempty(S2);Retur
9、n 0; /* S1满，S2非空，这时S1不能再入栈*/If (top1=n& Sempty(S2) /* S2非为空，先将S1退栈，元素在压到S2栈*/ While (!Sempty(S1)）POP(S1,x); POP(S2,x); Push(S1,x); retrun(1);/*x入栈，实现了队列元素的入队*/（2）void dequeue(stack S2, S1 )/* S2 是输出栈，本算法，将S2栈顶元素退栈，实现队列元素的出队*/if(！Sempty(S2)）/* S2不空，则直接出队*/ POP(S2,x) else if Sempty(S1). /* 若输入栅也为空，则判定
10、队空*/ else while(！Sempty(S1)POP(S1,x);PUSH S2,x);POP(S2,x); /* 退栈相当于队列出队*/二.课程设计要求（1）要求利用结构和程序设计语言C语言或C+完成上述题目。（2）课程设计要独立思考，独立完成。课程设计报告雷同超过60%，不论什么原因，一律0分处理。（3）算法设计及实现中，只能采用线性表、树和图结构完成，不得用数据库。（4）最后提交的内容：源程序与课程设计报告word文档。提交word文档，将源程序粘贴在课程设计报告最后面，不能提交压缩包文档。（5）请以远程教育学院课程设计报告模板为样本，完成设计报告。三.课程设计报告书写规范课程设计报告必须包含下面内容：（1）需求分析此部分叙述算法的功能、输入、输出及运行环境。（2）概要设计在此部分给出算法用到的主要数据结构、主要函数及其功能的介绍，各函数之间的调用关系示意图。（3）详细设计此部分给出主要算法的设计思想及实现。（4）程序测试在这部分给出程序运行结果的屏幕截图，以及测试分析。（5）感想与体会在这部分给出算法设计过程中的问题、程序调试过程的问题，算法存在的不足及改进思路。5
