【艾琪出品】《数据结构课程设计》【参考】

太过爱你忘了你带给我的痛 2023-01-14 10:56 162阅读 0赞

中国石油大学（北京）网络与继续教育学院

期 末 考 试

**《数据结构课程设计》**

一.课程设计题目

1. 线性表，基本操作及应用

目的：会定义线性表的顺序存储结构，熟悉对顺序表的基本操作，具体函数的定义。掌握链式存储结构。掌握单链表的基本算法，时间性能分析。

要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。

**内容：已知一个线性表，把线性表逆置**

设计要求：在程序中构造三个子程序分别为：

（1）SeqList reverse(SeqList L) /\*顺序表的就地逆置\*/

（2）Void List Traverse(SeqList L) /\*遍历顺序表\*/

（3）SeqList create(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 则主串指针回溯到i=i-j+1, j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串中的位置（i-j）。否则，当i>m-n则为匹配失败,下面代码仅供参考。

int index(char s\[ \], t\[ \], int m,n)

while (… )

if (s\[i\]<= s\[j\])\{i++,j++\} /\*对应字符串相等，指针后移\*/

else \{……\}/\*对应字符串不相等，i回溯，j仍为0指针后移\*/

if (i<=m-n&&j==n)\{ 梯在22中的位置是…匹配成功。\}

## 3. 树和二叉树及其应用。 ##

目的：掌握二叉树的结构特性以及各种存储结构的特点，及使用范围。掌握指针类型描述访问和处理二叉树的运算。熟悉二叉树的各种物理表示及各种遍历方法。

要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。

**内容：设计算法按前序次序打二叉树中叶子节点**

设计要求：本算法的要求与前序遍历算法既有相同之处又有不同之处。相同之处是打印次序均为前序，不同之处是此处表示不打印每个节点的值，而是打印出其中的叶子节点。有条件打印。下面是部分代码提示。

void PreOrder(BiNode \*root)

If(……)

(if ! root->lchild&& ! root->rchild)

(……)

## 4. 查找或排序操作。 ##

目的：掌握各种查找（顺序、二分法、查找树、哈希等等方法，及适用场合并能在解决实际问题中灵活运用。巩固在散列查找时解决冲突的方法及特点。掌握各种排序，插入、希尔、冒泡、快速排序、简单选择、堆排序等方法及适用场合。并在解决实际问题中灵活运用。

要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。

**内容：建立二叉树，并二叉树上实现对给定值进行查找操作，具体内容是编写算法求给定结点在二叉排序树中所在的层数。**

设计要求：根据题目要求，采用递归方法从根节点开始查找节点p。若待查结点是根结点，则深度为1，否则到左子数或右子树上去查找，查找深度加1。以下部分内容为参考。也可以自己设计程序代码。

（1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构。

（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(! p)

return 0;

if(p==root)

return 1;

else if (p->data < root ->data）

return ……;

else

return Level(root->rchild,+1;

## 5. 栈和队列及其应用。 ##

目的：栈的特点是好先进后出。其基本操作是入栈，出栈等等，掌握栈的顺序存储结构和链式存储结构，在实际问题背景下灵活应用。队列的特点是先进先出。其基本操作，入队出队等等，队列有顺序存储结构，链式存储结构和循环队列，要在实际问题中灵活运用。

要求：撰写实验报告，提供实验结果和数据。分析算法。给出具体的算法分析结果。包括时间复杂，度空间复杂度。简要给出算法设计小结和心得。

**内容：请利用两个栈**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))

………;

Return 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)