北邮 数据结构实验报告2

数据结构实验报告实验名称:实验二一一栈和队学生姓名:申宇飞班级：班内序03号：学号：日期2013年11月18日：1- 实验要求1.1实验目的：通过选择卞面五个题目之一进行实现，掌握如卞内容：>进一步掌握指针、模板类、异常处理的使用>掌握栈的操作的实现方法>掌握队列的操作的实现方法>学习使用栈解决实际问题的能力>学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试mainO函数测试线性表的正确性。

2.程序分析2.1存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。

第］页北京邮电大学信息与通信工程学院data next栈顶栈底关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1)Node<T> * s = new Node<T>;2)p->data = x;3)p->next = top;4)top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1)if(EmptyO)throw" F溢“；2)T x = top->data;3)Node<T> * p = top;4)top = top->next;5)elete p;三、链栈的取栈顶元素算法步骤：自然语言描述：1、判断栈是否为空第3页2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(EmptyO)tlu'ow H卜溢"；2)Node<T>*p=top;3)cout«p->data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p 伪代码描述：1)Node<T>*p = top;2)while(p !=NULL)3)cout« p->data ;4)p = p->next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1)while(top)2)strnct Node <T> * p = top;3)top = top->next;4)deletep; 时间复杂的：0(1)。

北邮数据结构实验报告摘要：本报告基于北邮数据结构实验，通过实际操作和实验结果的分析，总结和讨论了各实验的目的、实验过程、实验结果以及相关的问题和解决方法。

本报告旨在帮助读者了解数据结构实验的基本原理和应用，并为今后的学习和研究提供参考。

1. 实验一：线性表的操作1.1 实验目的本实验旨在掌握线性表的基本操作以及对应的算法实现，包括插入、删除、查找、修改等。

1.2 实验过程我们使用C++语言编写了线性表的相关算法，并在实际编程环境下进行了测试。

通过插入元素、删除元素、查找元素和修改元素的操作，验证了算法的正确性和效率。

1.3 实验结果经过测试，我们发现线性表的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(n)，修改操作的时间复杂度为O(1)。

这些结果与预期相符，并反映了线性表的基本特性。

1.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如插入操作的边界条件判断、删除操作时的内存释放等。

通过仔细分析问题，我们优化了算法的实现，并解决了这些问题。

2. 实验二：栈和队列的应用2.1 实验目的本实验旨在掌握栈和队列的基本原理、操作和应用，并进行实际编程实现。

2.2 实验过程我们使用C++语言编写了栈和队列的相关算法，并在实际编程环境下进行了测试。

通过栈的应用实现表达式求值和逆波兰表达式的计算，以及队列的应用实现图的广度优先遍历，验证了算法的正确性和效率。

2.3 实验结果经过测试，我们发现栈的应用可以实现表达式的求值和逆波兰表达式的计算，队列的应用可以实现图的广度优先遍历。

这些结果证明了栈和队列在实际应用中的重要性和有效性。

2.4 问题与解决方法在实验过程中，我们遇到了一些问题，例如中缀表达式转后缀表达式的算法设计、表达式求值的优化等。

通过查阅资料和与同学的讨论，我们解决了这些问题，并完善了算法的实现。

3. 实验三：串的模式匹配3.1 实验目的本实验旨在掌握串的基本操作和模式匹配算法，并进行实际编程实现。

北邮数据结构实验-约瑟夫环数据结构实验报告实验名称：实验1——约瑟夫环学生姓名：班级：班内序号：学号：日期：1．实验要求实验目的：通过利用循环链表实现约瑟夫问题的求解进行实现，掌握如下内容：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。

从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规则重复下去，直到所有人全部出列。

请问最后一个出列的人的编号。

2. 程序分析2.1 存储结构首先构建结点的结构体，包括结点的编号number和指向后继元素的指针*next。

然后构建循环链表储存每一个结点。

2.2 关键算法分析1、关键算法：插入：用尾插法构建循环链表，建立一个尾指针r用来保存最后一个结点的地址，插入每一个节点后，r指向新插入的结点。

用for循环来给每一个结点的number赋值。

插入的步骤：1.建立新指针s；2.在for循环中给s赋值；3.将r指针指向s；4.修改尾指针r=s5.在全部结点插入后，将终端结点指向第一个指针，r->next=front->next。

约瑟夫环算法实现：1.因为每次循环都有一个人出列，最后只剩一个人，因此要进行n-1次循环，用for循环实现。

2.同时定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

并输出出列的人的number，即p->number。

3.让front->next=p->next，删除p。

4.继续进行循环2、代码详细分析：约瑟夫环算法步骤：①定义一个指针p=front->next，每次循环front和p均后移m-1个，使p指向每次循环的第m个人，front指向第m-1个人。

数据结构实验报告实验名称：实验2——二叉树的构造学生姓名：XXXXNB班级：XXXXXX班内序号：学号：XXXXXXX日期：XXXXXXXX1．实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。

二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2.程序分析2.1 存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包含三个元素，分别是一个T 类型的数据域data，一个指向T 类型的指针左孩子，一个指向T 类型的指针右孩子，示意图如图所示：2.2 关键算法分析代码描述：1.构造函数template < class T >void BiTree<T>::Creat(BiNode<T>*&R, T data[], int i,int n)//i表示位置，从1开始，n表示数组长度{if (i <= n&&data[i - 1]){R = new BiNode < T > ;//创建根节点R->data = data[i - 1];Creat(R->LChild, data, 2 * i, n);//创建左子树Creat(R->RChild, data, 2 * i + 1, n);//创建右子树}else R = NULL;}template<class T>BiTree<T>::BiTree(T data[], int n){Creat(Root, data, 1, n);//利用递归循环构造}2.前序遍历//前序遍历，递归template<class T>void BiTree<T>::PreOrder(BiNode<T>*R)//前序遍历,递归//R都是源自于一开始构造所产生的根节点//根->左->右{if (R != NULL){cout << R->data<<" ";//访问结点PreOrder(R->LChild);//遍历左子树PreOrder(R->RChild);//遍历右子树}}//前序遍历，非递归template<class T>void BiTree<T>::PreOrderNormal(BiNode<T>*R)//用栈模板进行非递归操作{stack<BiNode<T>*> s;//结构栈BiNode<T>* p = R;//从根结点开始循环while (p != NULL || !s.empty()){while (p != NULL){cout << p->data << " ";s.push(p);p = p->LChild;//先压栈，再更改指针域}if (!s.empty())//检验栈是否为空,栈为空后，遍历结束{p = s.top();s.pop();p = p->RChild;}}}3.中序遍历//中序遍历，递归template<class T>void BiTree<T>::InOrder(BiNode<T>*R)//左->根->右//递归，中序遍历{if (R != NULL){InOrder(R->LChild);//遍历左子树cout << R->data<<" ";//访问节点InOrder(R->RChild);//遍历右子树}}4.后序遍历//后序遍历，递归template<class T>void BiTree<T>::PostOrder(BiNode<T>*R)//递归,后序遍历//左->右->根{if (R != NULL){PostOrder(R->LChild);//遍历左子树PostOrder(R->RChild);//遍历右子树cout << R->data<<" ";//访问节点}}时间复杂度：O（n)5.层序遍历template<class T>void BiTree<T>::LevelOrder(BiNode<T>*R)//层序遍历{queue<BiNode<T>*> q;BiNode<T>* p = R;//从根结点开始循环if(p!=NULL) q.push(p);while (!q.empty()){p = q.front();cout << p->data<<" ";q.pop();if (p->LChild != NULL) q.push(p->LChild);if (p->RChild != NULL) q.push(p->RChild);}}6.析构函数//析构函数template<class T>void BiTree<T>::Release(BiNode<T>*R){if (R != NULL){Release(R->LChild);//释放左子树Release(R->RChild);//释放右子树delete R;//释放根节点}}template<class T>BiTree<T>::~BiTree(){Release(Root);//释放二叉树}7.求二叉树深度template<class T>int BiTree<T>::Depth(BiNode<T>*R)//输出二叉树的深度{if (R == NULL) return 0;else{int m = Depth(R->LChild);int n = Depth(R->RChild);return m >= n ? m + 1:n + 1;}}时间复杂度：O（n)8.求路径template<class T>bool BiTree<T>::Findpath(BiNode<T>*R, T s)//找出指定元素到根节点的路径{if (R == NULL){return false;}else{if (R->data == s)//当前元素等于e，输出该节点{cout << R->data<<" ";return true;}else if (Findpath(R->LChild, s))//经过该结点的左孩子能到达e，输出该结点{cout << R->data<<" ";return true;}else if (Findpath(R->RChild, s))//经过该结点的右孩子能到达e,输出该结点{cout << R->data << " ";return true;}elsereturn false;}}template<class T>void BiTree<T>::Detect(BiNode<T>*R, T s){if (!(Findpath(R, s))){throw"输入元素有误！";}}3. 程序运行结果主函数流程图：测试截图：初始化二叉树，菜单创建执行功能：4. 总结.调试时出现了一些问题如：异常抛出的处理，书中并未很好的提及异常处理，通过查阅资料，选择用try catch 函数对解决。

数据结构实验报告实验名称：__ 哈夫曼树________学生姓名：______ 蔡宇豪_________________班级：________ 2 5____________________ 班内序号：__________15__________________学号：_________2012210673___________________ 日期：________2013.11.24____________________2. 程序分析2.1 存储结构哈夫曼树结点的存储结构包括双亲域parent，左子树lchild，右子树rchild，还有字符word，权重weight，编码code对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。

统计每个字符出现的次数作为叶子的权重，统计次数可以根据每个字符不同的ASCII码，根据叶子结点的权重建立一个哈夫曼树2.2 关键算法分析要实现哈夫曼解/编码器，就必须用二叉树结构建立起哈夫曼树，其中有4个关键算法，首先是初始化函数，统计每个字符的频度，并建立起哈夫曼树；然后是建立编码表，将每个字符的编码输出；再次就是编码算法，根据编码表对输入的字符串进行编码，并将编码后的字符串输出；最后是译码算法，利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。

1.初始化函数int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int i=0;i<2*n-1;i++){if(i<n){HTree[i].weight=a[i];}else{HTree[i].weight=0;}HTree[i].LChild=-1;HTree[i].RChild=-1;HTree[i].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int i=n;i<2*n-1;i++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;2.生成编码表HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}3.编码cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;【计算关键算法的时间、空间复杂度】关键算法A的时间复杂度为O(n)，关键算法B的时间复杂度为O(n),关键算法C的时间复杂度为O(n)，关键算法D的时间复杂度为O(n).2.3 其他程序完整代码：#include<iostream>using namespace std;const int MAX=1000;struct HNode{int weight;int parent;int LChild;int RChild;};struct HCode{char data;char code[200];};class Huffman{private:HNode *HTree; //哈夫曼树HCode *HCodeTable; //哈夫曼编码表char b[MAX]; //记录出现的字符int a[MAX]; //记录每个字符出现的次数，即权值static int n; //字符的种类数(静态变量)public:void init(char s[]); //初始化void init1(char s[]);void CreateCodeTable(); //创建编码表void Encoding(char *s,char *d); //编码void Decoding(char *s,char *d); //解码int count1() //算编码前长度{int q1=0;for(int i=0;i<n;i++){q1+=8*a[i];}return q1;}int count2() //算编码后长度{int q2=0;for(int i=0;i<n;i++){q2+=strlen(HCodeTable[i].code)*a[i];}return q2;}};int Huffman::n=0;void Huffman::init(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}//cout<<"共有"<<n<<"种字符，分别为:"<<endl;for(i=0;i<n;i++)cout<<b[i]<<"出现次数为:"<<a[i]<<endl;HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int q=0;q<2*n-1;q++){if(q<n){HTree[q].weight=a[q];}else{HTree[q].weight=0;}HTree[q].LChild=-1;HTree[q].RChild=-1;HTree[q].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标for(int w=n;w<2*n-1;w++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<i;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=w;HTree[w].weight=HTree[x].weight+HTree[y].weight;HTree[w].LChild=x;HTree[w].RChild=y;HTree[w].parent=-1;}}void Huffman::init1(char s[]){int i,j;for(i=0;i<MAX;i++)a[i]=0; //先将a[]数组中每个值都赋为，不然程序会运行出错？for(i=0;s[i]!='\0';i++) //'\0'字符串结束标志{for(j=0;j<n;j++){if(s[i]==b[j]) //判断该字符是否已经出现过break;}if(j<n) //该字符出现过，对应计数器加一a[j]++;else//该字符为新字符,上面的循环全部运行完毕，j=n，记录到b[j]中，对应计数器加一{b[j]=s[i];a[j]++;n++; //出现的字符种类数加一}}HTree=new HNode[2*n-1] ; //哈夫曼树初始化for(int e=0;e<2*n-1;e++){if(e<n){HTree[e].weight=a[e];}else{HTree[e].weight=0;}HTree[e].LChild=-1;HTree[e].RChild=-1;HTree[e].parent=-1;}int x,y,m1,m2; //x,y用于存放权值最小结点在数组中的下标，m1,m2用于存放两个无父结点且结点权值最小的两个结点for(int r=n;r<2*n-1;r++) //开始建哈夫曼树{//找出权值最小的结点m1=m2=MAX; //MAX=1000x=y=0;for(int j=0;j<r;j++){if(HTree[j].weight<m1&&HTree[j].parent==-1){m2=m1;//y=x;m1=HTree[j].weight;x=j;}else if(HTree[j].weight < m2 && HTree[j].parent==-1){m2=HTree[j].weight;y=j;}}HTree[x].parent=HTree[y].parent=r;HTree[r].weight=HTree[x].weight+HTree[y].weight;HTree[r].LChild=x;HTree[r].RChild=y;HTree[r].parent=-1;}}void Huffman::CreateCodeTable() //生成编码表{HCodeTable=new HCode[n];for(int i=0;i<n;i++){HCodeTable[i].data=b[i];int child=i;int parent=HTree[i].parent;int k=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';cout<<b[i]<<"的编码:";for(int j=k-1;j>=0;j--)cout<<HCodeTable[i].code[j];cout<<endl;}}void Huffman::Encoding(char *s,char *d) // 编码算法 //d为字符串{cout<<"编码后的字符串为:";while(*d!='\0'){for(int i=0;i<n;i++){if(b[i]==*d) //判断，每当出现一种时，就找到对应编码并输出{int k=strlen(HCodeTable[i].code);for(int j=k-1;j>=0;j--){*s=HCodeTable[i].code[j];cout<<*s;s++;}}}d++;}*s='\0';cout<<endl;}void Huffman::Decoding(char *s,char *d) //s为编码串{cout<<"解码后的字符串为:";while(*s!='\0'){int parent=2*n-1-1;while(HTree[parent].LChild!=-1){if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;cout<<*d;d++;}cout<<endl;void main(){int i=0;char d[MAX];char s[MAX];cout<<"请输入字符串:";while((d[i]=getchar())!='\n')i++;d[i]='\0';Huffman h;cout<<"哈夫曼功能："<<endl;cout<<"1.统计字符种类及出现次数"<<endl;cout<<"2.数据的编码解码"<<endl;cout<<"3.分析压缩效果"<<endl;int q;for(;;){cout<<"请输入（1~3）"<<endl;cin>>q;bool x=0;switch (q){case 1:h.init(d);break;case 2:h.init1(d);h.CreateCodeTable();h.Encoding(s,d);h.Decoding(s,d);break;case 3:cout<<"编码前的长度为:"<<h.count1()<<endl;cout<<"编码后的长度为:"<<h.count2()<<endl;cout<<"压缩比为:"<<(h.count2()*1.0/h.count1())<<endl;break;default:cout<<"请输入选择！！！！！"<<endl;break;}}3.}程序运行结果分析输入：I love data Structure, I love Computer。

北京邮电大学实验报告课程名称：数据库系统原理实验名称：E-R建模与关系表转换网络工程系315班姓名王倩教师吴起凡成绩_________2016年4月5日实验二 E-R建模与关系表转换●实验目的1. 理解和掌握E-R图的基本概念。

2. 培养根据实际应用领域数据对象描述，抽取数据对象特征、关联关系等信息，设计数据库概念结构的能力。

3. 选做：学习Power Designer，进行数据模型转换和关系表的自动创建，培养软件辅助设计工具的使用能力。

●实验原理对GSM网络的各种配置资源，及资源之间的相互关系，如控制，分配给，相邻等，进行抽象，设计概念数据模型（CDM），形成E-R图，然后利用Power Designer 数据库概念设计工具，将数据库概念结构转化为物理结构，然后再转化为SQL脚本，从而在数据库中直接生成表结构。

●实验平台及环境1. 软硬件环境处理器：Inter(R) Core(TM) i5-2520M CPU 2.50GHz内存：2G操作系统：Windows 8.1 专业版，32位2. 工具实验平台: Microsoft SQL Server2012数据库管理系统数据库系统概念设计工具：Sybase Power Designer 12●实验内容1．根据数据需求描述抽象出E-R图阅读《GSM移动通信网络配置数据库》课程实验背景资料-11-v4.doc，根据GSM的基本概念，分析其中的数据需求，将其描述抽象成实体和联系，并确定实体和联系的属性，特别要注意标明其主键和外键等约束关系，最终形成E-R图。

2．将E-R图输入相关设计工具（Power Design）形成概念模型（CDM）。

3．使用工具将E-R图转换为数据库物理结构（PDM）。

4．将物理模型转化为生成数据库中的表和视图的脚本，注意要选择数据库为SQL Server。

5．执行SQL脚本，生成表和视图。

6．成功后，查看生成的表和视图的情况。

●实验步骤1. 需求分析GSM移动通信网络配置数据库是对通信网中的各种资源及各种资源之间的关系进行描述。

数据结构实验报告实验名称：实验二——利用栈结构实现迷宫求解问题学生姓名：班级：班内序号：学号：日期：2012年11月19日一、实验目的1、进一步掌握指针、模板类、异常处理的使用2、掌握栈的操作的实现方法3、掌握队列的操作的实现方法4、学习使用栈解决实际问题的能力5、学习使用队列解决实际问题的能力二、实验要求：利用栈结构实现迷宫求解问题。

迷宫求解问题如下：心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口，测试算法的迷宫如下图所示。

提示：1、可以使用递归或非递归两种方法实现2、老鼠能够记住已经走过的路，不会反复走重复的路径3、可以自己任意设置迷宫的大小和障碍4、使用“穷举求解”的方法三、程序分析1、存储结构栈存储结构；示意图；2、关键算法分析A、绘制迷宫；伪代码：1、输出迷宫的大小及全部设置为障碍；2、根据键盘的输入绘制迷宫的路线，起始点和终点；void draw()//绘制迷宫障碍{k=getch();switch(int(k)){case 105://上if(by>5){by--;j--;}break;case 107://下if(by<M+4){by++;j++;}break;case 106://左if(bx>2){bx=bx-2;i--;}break;case 108://右if(bx<2*N){bx=bx+2;i++;}break;case 114://'R'路map[i][j]=0;cout<<".";break;case 119://'W'墙map[i][j]=-3;cout<<"■";break;case 115://'S'起点s[0].x=i;//起点入栈s[0].y=j;top=1;map[i][j]=-1;cout<<k;break;case 101://'E'终点map[i][j]=-2;cout<<k;break;}gotoxy(bx,by);}B、路径寻找伪代码；1、向某一方向查找是否有路；2、如有遍历一下栈，看是否已经进栈，一进栈就舍弃，寻求下一个；无就让其进栈。

北邮数据库实验二实验报告一、实验目的本次数据库实验二的目的在于深入理解和掌握数据库中的关系模型、SQL 语言的基本操作，以及通过实际操作来提高对数据库管理系统的应用能力。

二、实验环境本次实验使用的数据库管理系统为 MySQL，操作系统为 Windows 10。

三、实验内容及步骤（一）创建数据库和表1、首先，使用以下命令创建名为“student_management”的数据库：｀CREATE DATABASE student_management;｀2、然后，在该数据库中创建“students”表，用于存储学生的基本信息，表结构如下：｀CREATE TABLE students （id INT PRIMARY KEY AUTO_INCREMENT,name VARCHAR(50)，age INT,gender VARCHAR(10)）；｀（二）插入数据使用以下 SQL 语句向“students”表中插入一些示例数据：｀INSERT INTO students （name, age, gender)VALUES （＇张三'， 20, ＇男'），（＇李四'， 21, ＇女'），（＇王五'， 19, ＇男'）；｀（三）数据查询1、查询所有学生的信息：｀SELECT FROM students;｀2、查询年龄大于 20 岁的学生：｀SELECT FROM students WHERE age ＞ 20;｀（四）数据更新将学生“张三”的年龄修改为 21 岁：｀UPDATE students SET age ＝ 21 WHERE name ＝＇张三'；｀（五）数据删除删除年龄小于 20 岁的学生：｀DELETE FROM students WHERE age ＜ 20;｀四、实验结果及分析（一）创建数据库和表成功创建了“student_management”数据库和“students”表，表结构符合预期。

北邮数据结构答案【篇一：北邮数据结构实验报告实验二含源码】验名称：实验二——栈和队列学生姓名：申宇飞班级： 2012211103班内序号： 03学号： 2012210064日期： 2013年11月18日1．实验要求1.1实验目的：通过选择下面五个题目之一进行实现，掌握如下内容：? 进一步掌握指针、模板类、异常处理的使用? 掌握栈的操作的实现方法? 掌握队列的操作的实现方法? 学习使用栈解决实际问题的能力? 学习使用队列解决实际问题的能力1.2实验内容题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试main()函数测试线性表的正确性。

2. 程序分析2.1 存储结构链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈在实现时直接采用栈顶指针指向栈顶元素。

datanexttop栈顶关键算法分析链栈：一、入栈操作算法步骤：自然语言描述：1、建立新结点2、给p结点的数据域赋值3、修改p结点的指针域，将其指向栈顶结点4、栈顶指针指向p结点伪代码描述：1）nodet * s = new nodet;2）p-data = x;3）p-next = top;4）top = p;二、出栈操作算法步骤：自然语言描述：1、判断栈是否为空2、保存栈顶结点的数据域3、定义指针p指向栈顶结点4、栈顶指针指向下一个结点5、释放p结点伪代码描述：1）if(empty())throw下溢;2）t x = top-data;3）nodet * p = top;4）top = top-next;5）elete p;三、链栈的取栈顶元素栈底算法步骤：自然语言描述:1、判断栈是否为空2、定义指针p指向栈顶结点3、返回栈顶元素的值，不删除伪代码描述1)if(empty())throw下溢;2)nodet*p=top;3)coutp-data;四、遍历链栈元素算法步骤：自然语言描述：1、定义指针p指向栈顶结点2、判断栈是否为空3、返回栈元素的值4、把下一个指针的值赋给p伪代码描述：1）nodet*p = top;2）while(p != null)3）cout p-data ;4）p = p-next;五、析构函数算法步骤：自然语言描述：1、判断栈顶指针是否为空2、定义指针p指向栈顶结点3、把下一个指针的值赋给栈顶指针4、释放要释放的指针伪代码描述：1）while(top)2）struct node t * p = top;3）top = top-next;4）delete p;时间复杂的：o(1)。

北邮数据结构实验报告北邮数据结构实验报告一、引言数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化起着至关重要的作用。

本报告旨在总结北邮数据结构实验的相关内容，包括实验目的、实验设计、实验过程和实验结果等。

二、实验目的本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。

具体目的如下：1. 掌握线性表、栈和队列等基本数据结构的实现方法；2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；3. 学会使用递归和非递归算法解决实际问题；4. 培养编程实践能力和团队合作意识。

三、实验设计本次实验包括以下几个部分：1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和查找等。

通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。

通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。

通过实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。

通过实验，掌握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索算法。

四、实验过程1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。

在实验过程中，遇到了一些问题，如边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和出队等基本操作。

在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查找等操作。

在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。