南邮数据结构实验算法分析
- 格式:doc
- 大小:20.00 KB
- 文档页数:5
实验报告
( 2016 / 2017 学年第一学期)
课程名称数据结构A
实验名称二叉树的基本操作
及哈夫曼编码译码系统的实现
实验时间2017 年 5 月 1 日指导单位计算机学院计算机科学与技术系
指导教师邹志强
学生姓名吴爱天班级学号B15040916 学院(系) 计算机学院专业信息安全
实验报告
之后三步输出,对应的是三种遍历方式,应该输出的测试结果是:
先序:68 69 72 70 74 71 67 75 65 66
中序:72 69 74 70 71 75 67 68 65 66
后序:72 74 75 67 71 70 69 66 65 68
实验结果符合预期。
对于哈夫曼建树操作我自己又按照自己的想法重写了,里面也去学习了C++的字典类MAP,这个类非常好用,可以简单粗暴地提供一些方法和迭代器,让你将关键字和值绑定,这样我每新加入一个字母的数据块,我就可以记录下这对组合,不用之后搜索和解码的时
之后进行编码,其实也是一个搜索的过程,主要是调用了一个
测试:。
实验报告(2014 / 2015 学年第二学期)课程名称数据结构实验名称线性表的基本运算及多项式的算术运算实验时间2015 年9 月28 日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q学院(系) 贝尔英才专业信息科技强化班实验报告~SeqList() { delete[] elements; }bool IsEmpty() const;int Length() const;bool Find(int i, T& x) const;int Search(T x) const;bool Insert(int i, T x);bool Delete(int i);bool Update(int i, T x);void Output(ostream& out)const;private:int maxLength;T *elements;};template<class T>SeqList<T>::SeqList(int mSize){maxLength = mSize;elements = new T[maxLength];n = 0;}template<class T>bool SeqList<T>::IsEmpty() const{return n == 0;}template<class T>int SeqList<T>::Length()const{return n;}template<class T>bool SeqList<T>::Find(int i, T& x)const{if (i<0 || i>n - 1){cout <<"out of bounds"<< endl; return false;}x = elements[i];return true;}template<class T>int SeqList<T>::Search(T x)const{for (int j = 0; j < n; j++)if (elements[j] == x)return j;return -1;}template<class T>bool SeqList<T>::Insert(int i, T x){if (i<-1 || i>n - 1){cout <<"out of bounds"<< endl;return false;}if (n == maxLength){cout <<"over flow"<< endl;return false;}for (int j = n - 1; j > i; j--)elements[j + 1] = elements[j];elements[i + 1] = x;n++;return true;}template<class T>bool SeqList<T>::Delete(int i){if (i<0 || i>n - 1){cout <<"out of bounds"<< endl;return false;}if (!n){cout <<"over flow"<< endl;return false;}for (int j = i+1; j <n; j--)elements[j -1] = elements[j];n--;return true;}template<class T>bool SeqList<T>::Update(int i, T x){if (i<0 || i>n - 1){cout <<"out of bounds"<< endl;return false;}elements[i] = x;return true;}template<class T>void SeqList<T>::Output(ostream& out)const{for (int i = 0; i < n; i++)out << elements[i] << " ";out<< endl;}源.cpp:#include"seqlist.h"const int SIZE = 20;void main(){SeqList<int> LA(SIZE);int i = 0;for (i = 0; i<5; i++) LA.Insert(i - 1, i);LA.Insert(-1, 10);LA.Output(cout);}实现在线性表LA中插入0-4然后在一开始插入10 运行截图如下:多项式实验:定义类如下重构函数如下:源码:#include<iostream>using namespace std;class Term{public:Term(int c, int e);Term(int c, int e, Term* nxt);Term* InsertAfter(int c, int e);private:int coef;int exp;Term* link;friend ostream& operator<<(ostream &, const Term &);friend class Polynominal;};Term::Term(int c, int e) :coef(c), exp(e){link = 0;}Term::Term(int c, int e, Term *nxt) : coef(c), exp(e) {link = nxt;}Term* Term::InsertAfter(int c, int e){link = new Term(c, e, link);return link;}ostream& operator<<(ostream& out, const Term& val){if (0 == val.coef)return out;if (1!= val.coef)out<<val.coef;switch (val.exp){case 0:break;case 1:out<<"X"; break;default:out<<"X^"<<val.exp; break;}return out;}class Polynominal{public:Polynominal();~Polynominal();void AddTerms(istream& in);void Output(ostream& out)const;void PolyAdd(Polynominal& r);void PolyMul(Polynominal& r);private:Term* theList;friend ostream& operator<<(ostream &, const Polynominal &);friend istream& operator>>(istream&, Polynominal &);friend Polynominal& operator+(Polynominal &, Polynominal &);friend Polynominal& operator*(Polynominal &, Polynominal &); };Polynominal::Polynominal(){theList = new Term(0, -1); //头结点theList->link = NULL; //单链表尾结点指针域为空}Polynominal::~Polynominal(){Term* p = theList->link;while (p != NULL){theList->link = p->link;delete p;p = theList->link;}delete theList;}void Polynominal::AddTerms(istream & in){Term* q = theList;int c, e;for (;;){cout <<"Input a term(coef,exp):\n"<< endl;cin >> c >> e;q = q->InsertAfter(c, e);if (0 >= e) break;}}void Polynominal::Output(ostream& out)const{int first = 1;Term *p = theList->link;for (; p != NULL && p->exp >= 0; p = p->link){if (!first && (p->coef>0)) out<<"+";first = 0;out<< *p;}cout << endl;}void Polynominal::PolyAdd(Polynominal& r){Term *q, *q1 = theList, *p; //q1指向表头结点p = r.theList->link; //p指向第一个要处理的结点q = q1->link; //q1是q的前驱,p和q就指向两个当前进行比较的项while (p != NULL && p->exp >= 0)//对r的单循环链表遍历,知道全部结点都处理完{while (p->exp < q->exp) //跳过q->exp大的项{q1 = q;q = q->link;}if (p->exp == q->exp) //当指数相等时,系数相加{q->coef = q->coef + p->coef;if (q->coef == 0) //若相加后系数为0,则删除q{q1->link = q->link;delete(q);q = q1->link; //重置q指针}else{q1 = q; //若相加后系数不为0,则移动q1和qq = q->link;}}else//p>exp>q->exp的情况q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点,插入q1后 p = p->link;}}void Polynominal::PolyMul(Polynominal& r){Polynominal result; //定义相乘后的数据Term *n = result.theList; //n指向result的头结点n = n->InsertAfter(0, 0); //在result的头结点后插入新结点,系数指数均为0 Term *p = r.theList->link; //p指向第一个要处理的结点while(p->exp >= 0) //对r的单循环链表遍历{Polynominal tmp; //存储某段相乘后的数据Term *m = tmp.theList; //m指向tmp的头结点Term *q = theList->link; //q指向表头结点的后继结点while(q->exp >= 0) //对当前对象的单循环环链表遍历{m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后 q = q->link;}result.PolyAdd(tmp); //将temp加到result上p = p->link;}Term *q = theList->link; //q指向表头结点的后继结点while(q != NULL) //删除原对象的所有数据{theList->link = q->link;delete q;q = theList->link;}q = theList;q = q->InsertAfter(0, 0);PolyAdd(result); //将result加到当前对象上}ostream &operator<<(ostream& out, const Polynominal& x){x.Output(out);return out;}istream &operator>>(istream& in, Polynominal &x){x.AddTerms(in);return in;}Polynominal & operator + (Polynominal &a, Polynominal &b){a.PolyAdd(b);return a;}Polynominal & operator * (Polynominal &a, Polynominal &b){a.PolyMul(b);return a;}int main()实验报告文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.。
实验报告(2013/2014学年第一学期)课程名称算法分析与设计实验名称密码算法实验时间2014 年 5 月23 日指导单位计算机学院软件工程系指导教师张怡婷学生姓名班级学号B******** 学院(系) 软件工程专业软件工程实验报告三、实验原理及内容(包括操作过程、结果分析等)实验步骤1、RSA 算法是由麻省理工学院的Ron Rivest,Adi Shamir 和Len Adleman 于1977 年研制并于1978 年首次发表的一种算法,是第一个能同时用于加密和数字签名的算法,且易于理解和操作,因此作为一种通用公开密钥加密方式而受到推崇。
RSA 是一种分组密码,其中明文和密文都是小于某个n 的从0 到n-1 的整数,则分组的二进制值长度必须小于或等于log2n。
若以M 表示明文分组,而C 表示密文分组,则加密和解密的过程如下:C=Me mod nM=Cd mod n=(Me)d mod n=Med mod n发送方和接受方都必须知道n 的值。
发送方知道 e 的值,而只有接受方知道d 的值。
因此这是一种公开密钥为{e,n},且私有密钥为{d,n}的公开密钥加密算法。
此时算法要能够满足公开密钥加密的要求,则必须满足以下条件:(1)有可能找到e、d、n 的值,使得对所有M<n 有Med=M mod n。
(2)对于所有M<n 的值,要计算Me和Cd 相对来说是简单的。
(3)在给定e 和n 时,判断出 d 是不可行的。
2、重点考虑第一个条件:由Euler 定理的一个推论:给定两个素数p和q以及两个整数n 和m,使得n=pq 而且0<m<n,并且对于任意整数k,下列关系成立:mkΦ(n)+1=mk(p-1)(q-1)+1≡m mod n其中Φ(n)是欧拉函数,也就是不超过n 且与n 互素的整数个数。
对于素数p 和q,有Φ(pq)=(p-1)(q-1)。
因此得到需要的关系:ed=kΦ(n)+1,等价于: ed≡1 mod Φ(n)d≡e-1 mod Φ(n)也就是说:d 和 e 是以Φ(n)为模的乘法逆元。
南邮数据结构考点范围南京邮电大学数据结构课程主要涵盖以下几个方面的内容。
1.算法复杂度分析算法复杂度分析是数据结构课程的基础。
在这一部分内容中,学生需要学习如何计算算法的时间和空间复杂度。
时间复杂度是指算法所需的时间和输入数据量之间的关系,空间复杂度是指算法所需的额外空间和输入数据量之间的关系。
学生需要掌握常见算法的复杂度分析方法,如递归算法的复杂度分析、循环算法的复杂度分析等。
2.线性表线性表是数据结构中最基本的一种数据结构,也是其他数据结构的基础。
在这一部分内容中,学生需要学习线性表的概念、基本操作和实现方式。
常见的线性表包括数组、链表、栈和队列等。
学生需要学习如何操作线性表的插入、删除、查找等操作。
3.树树是一种非线性的数据结构,是由节点和边组成的。
在这一部分内容中,学生需要学习树的基本概念、遍历方式和常见的树结构。
常见的树结构包括二叉树、二叉搜索树、平衡二叉树和堆等。
学生需要学习如何操作树的插入、删除、查找等操作,以及树的遍历方式,如前序遍历、中序遍历和后序遍历等。
4.图图是一种用于描述事物之间关系的数据结构,在现实生活中有广泛的应用。
在这一部分内容中,学生需要学习图的基本概念、存储方式和常见的图算法。
常见的图算法包括深度优先搜索算法和广度优先搜索算法等。
学生需要学习如何操作图的插入、删除、查找等操作,以及图的遍历方式,如深度优先遍历和广度优先遍历等。
5.排序算法排序算法是数据结构课程的重点内容之一。
在这一部分内容中,学生需要学习常见的排序算法,如冒泡排序、插入排序、选择排序、快速排序、归并排序等。
学生需要学习如何分析排序算法的时间复杂度和空间复杂度,并能够实现各种排序算法。
6.查找算法查找算法是数据结构课程的重点内容之一。
在这一部分内容中,学生需要学习常见的查找算法,如顺序查找、二分查找、哈希查找等。
学生需要学习如何分析查找算法的时间复杂度和空间复杂度,并能够实现各种查找算法。
除了上述内容,南京邮电大学数据结构课程还可能涉及其他相关内容,如哈希表、递归算法、图的最短路径算法、动态规划等。
实验报告(2015 / 2016学年第二学期)课程名称数据结构A实验名称线性表的基本运算和多项式的基本运算实验时间2016 年 3 月10 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专业信息管理与信息系统实习题名:线性表的基本运算班级姓名学号日期2016.03.10一、问题描述深入理解线性表数据结构,熟练掌握顺序表的各种基本操作。
在顺序表类SeqList 中增加成员函数void Reverse(),实现顺序表的逆置;在顺序表类SeqList中增加成员函数bool DeleteX(const T &x),删除表中所有元素值等于x元素。
若表中存在这样的元素,则删除之,且函数返回true,否则函数返回false。
二、概要设计文件Inverse.cpp中定义了Linearlist类, SeqList类继承Linearlist类。
在顺序表类SeqList中通过函数void Reverse()实现顺序表的逆置,通过函数boolDeleteX(const T &x),删除表中所有元素值等于x元素。
三、详细设计1.类和类的层次设计程序使用了两个类, 线性表Linearlist类和顺序表SeqList类和一个主函数mian。
Linearlist类里包括常见的线性表运算,在类SeqList里面新增成员函数void Reverse()和bool DeleteX(const T &x)。
TLinearlist#int n+virtual bool IsEmpty() const = 0;+virtual int Length() const = 0;+virtual bool Find(int i,T& x) const = 0;+virtual int Search(T x) const = 0;+virtual bool Insert(int i,T x) = 0;+virtual bool Delete(int i) = 0;+virtual bool Update(int i,T x) = 0;+virtual void Output(ostream& out) const = 0;TSeqList-int maxLength;-T *elements;+IsEmpty() const;+Length() const;+Find(int i,T& x) const;+Search(T x) const;+Insert(int i,T x);+Delete(int i);+Update(int i,T x);+Output(ostream& out) const;+Reverse();+DeleteX(const T& x);2.核心算法顺序表SeqList类中,私有段封装了两个私有数据成员maxLength和elements,公有段封装了构造、析构、查找、删除、逆置等函数。
南邮数据结构实验三南京邮电大学数据结构实验三、链表的基本操作实验目的本次实验的主要目的是理解链表的概念,掌握链表的基本操作,包括链表的创建、插入、删除和遍历。
实验内容本次实验分为以下几个部分:1、链表的定义与创建1.1 链表的概念链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
链表可以分为单链表、双链表和循环链表等不同类型。
本次实验将创建一个单链表。
1.2 链表节点的定义链表节点包含两个成员变量,分别是数据域和指针域。
数据域用于存储节点的数据,指针域指向下一个节点。
1.3 链表的创建在主函数中创建一个空链表,并添加一些初始数据,用于后续的操作。
2、链表的插入操作2.1 插入节点的位置链表的插入操作需要指定节点插入的位置,可以在链表的头部、尾部或者中间插入新节点。
2.2 插入节点的操作根据所选位置,在链表中插入新节点,并更新相应的指针。
3、链表的删除操作3.1 删除节点的位置链表的删除操作需要指定节点删除的位置,可以删除头节点、尾节点或者中间节点。
3.2 删除节点的操作根据所选位置,删除链表中的节点,并更新相应的指针。
4、链表的遍历操作通过循环遍历链表的所有节点,并输出每个节点的数据。
附件说明本文档涉及以下附件:附件1:源代码附件2:实验报告法律名词及注释本文所涉及的法律名词及注释如下:1、数据结构:数据的存储方式和操作组成的集合。
在计算机科学中,数据结构是计算机中存储、组织数据的方式。
2、链表:链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。
3、节点:链表中的一个元素,包含数据域和指针域。
4、数据域:节点中存储的数据。
5、指针域:节点中指向下一个节点的指针。
6、插入操作:在链表中插入一个新节点。
7、删除操作:从链表中删除一个节点。
8、遍历操作:按照一定的顺序访问链表中的所有节点。
全文结束。
南邮数据结构实验一实验报告(2014 / 2015学年第一学期)课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间年月日指导单位指导教师学生姓名班级学号学院(系) 专业二叉树的基本运算:一、问题描述1.设计递归算法,实现二叉树的运算:删除一棵二叉树,求一棵二叉树的高度,求一棵二叉树中叶子节点数,复制一棵二叉树,交换一棵二叉树的左右子树2.设计算法,自上而下,自左向右即按层次遍历一棵二叉树3.设计main函数,测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树,然后遍历二叉树,然后交换每个结点的左右子树,接着算出输得高度和叶子节点,最后删除。
三、详细设计2. 核心算法建立二叉树的void MakeTree(const T& x,BinaryTree& left,BinaryTree& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树,求一棵二叉树的高度,求一棵二叉树中叶子节点数,复制一棵二叉树等都是用递归的方法实现。
四、程序代码流程图#includetemplatestruct BTNode{BTNode(){lChild=rChild=NULL;}BTNode(const T &x){element=x;lChild=rChild=NULL;}BTNode(const T &x,BTNode* l,BTNode* r) {element=x;lChild=l;rChild=r;}T element;BTNode* lChild,* rChild;};templateclass BinaryTree{public:BinaryTree(){root=NULL;}~BinaryTree(){Clear();}void Copy(BinaryTree&r) const;bool IsEmpty()const{return root == NULL;}void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree& left,BinaryTree& right);void BreakTree(T& x,BinaryTree& left,BinaryTree& right);void PreOrder(void (*Visit)(T &x));void LevelOrder(void (*Visit)(T& x));int Size();BinaryTree(BinaryTree&t)root=Copy(t.root);}// void InOrder(void (*Visit)(T &x));// void PostOrder(void (*Visit)(T &x));BTNode* Copy(BTNode* t);protected:BTNode * root;private:static int number;void Clear(BTNode* &t);void Exchange(BTNode* t);int GetHeight(BTNode* t);int Size(BTNode* t);void PreOrder(void (*Visit)(T &x),BTNode* t);void LevelOrder(void (*Visit)(T& x),BTNode* t); // void InOrder(void (*Visit)(T &x),BTNode* t);// void PostOrder(void (*Visit)(T &x),BTNode* t); };templatebool BinaryTree::Root(T &x)const{if(root){x=root->element;return true;}elsereturn false;}templatevoid BinaryTree::Clear(){Clear(root);}templatevoid BinaryTree::Clear(BTNode* &t){if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;}}templatevoid BinaryTree::MakeTree(const T& x,BinaryTree& left,BinaryTree& right) {if(root||&left==&right)return;root=new BTNode (x,left.root,right.root);left.root=right.root=NULL;}templatevoid BinaryTree::BreakTree(T& x,BinaryTree& left,BinaryTree& right) {if(!root||&left==&right||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;delete root;root=NULL;}templateBTNode* BinaryTree::Copy(BTNode* t){if(!t)return NULL;BTNode*q=new BTNode(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;}templatevoid Visit(T &x){cout<<x<<" ";<="" bdsfid="252" p=""></x<<">}templatevoid BinaryTree::PreOrder(void (*Visit)(T& x)){PreOrder(Visit,root);}templatevoid BinaryTree::PreOrder(void (*Visit)(T& x),BTNode* t) { if(t){Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}templatevoid BinaryTree::Exchange(){Exchange(root);}templatevoid BinaryTree::Exchange(BTNode* t){if(!t)return;BTNode* temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);}templateint BinaryTree::GetHeight(){return GetHeight(root);}int BinaryTree::GetHeight(BTNode* t) {int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ++>tempr++)return templ;elsereturn tempr;}templateint BinaryTree::number=0; templateint BinaryTree::Size(){Size(root);return number;}templateint BinaryTree::Size(BTNode* t){if(t!=NULL){Size(t->lChild);if(t->lChild ==NULL&&t->rChild ==NULL)number++;Size(t->rChild);}return number;}templatevoid BinaryTree::LevelOrder(void (*Visit)(T& x)) { PreOrder(Visit,root);}void BinaryTree::LevelOrder(void (*Visit)(T& x),BTNode* t) { BTNode *quene[50],*p;int pre=1,rear=1;quene[++pre]=t;while(pre!=0){p=quene[++rear];cout<element<<" ";if(p->lChild !=NULL)quene[++pre]=p->rChild ;if(p->rChild !=NULL)quene[++pre]=p->lChild ;}}void main(){BinaryTree a,b,x,y,z;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);cout<<"二叉树z的先序遍历:"<<endl;< bdsfid="378" p=""></endl;<>z.PreOrder(Visit);cout<<endl;< bdsfid="381" p=""></endl;<>cout<<"层次遍历二叉树:";z.LevelOrder(Visit);cout<<endl;< bdsfid="385" p=""></endl;<>BinaryTree q(z);cout<<"复制的二叉树q的先序遍历:"<<endl;< bdsfid="389" p=""></endl;<>q.PreOrder(Visit);cout<<endl;< bdsfid="392" p=""></endl;<>cout<<"树的高度:";cout<<z.getheight()<<endl;< bdsfid="395" p=""></z.getheight()<<endl;<>cout<<"叶子节点数量:";cout<<z.size()<<endl;< bdsfid="398" p=""></z.size()<<endl;<>z.Exchange();cout<<"二叉树左右子树交换后的先序遍历:"<<endl;< bdsfid="401" p=""></endl;<>z.PreOrder(Visit);cout<<endl;< bdsfid="404" p=""></endl;<>}五、测试用例和运行结果测试用例如main函数中所示,结果如下图所示。
实验报告
( 2016 / 2017 学年第一学期)
课程名称数据结构A
实验名称线性表的基本运算及多项式的算术运算实验时间2017 年 3 月22 日指导单位计算机学院计算机科学与技术系
指导教师邹志强
学生姓名吴爱天班级学号B15040916 学院(系) 计算机学院专业信息安全
实验报告
实验报告
度为O(n)级别。
2、在顺序表类SeqList 中增加成员函数bool DeleteX (const T &x), 删除表中所有元素值等于x 的元素.若表中存在这样的元素, 则删除之, 且函数返回true, 否则函数返回false.
删除所有值为X的元素
注释:主要思路为,依次查找SeqList内的元素,每次都与X的值进行依次对比,如果相同则删除,不同则继续向下扫描,知道SeqList末尾,最后用Search()来检验是否删除干净,复杂度也为O(n).
如图,原数据为 7 49 73 58 30 72,逆转过后为72 30 58 73 49 7,符合预期。
DeleteX()
如图,原数据中有3个0,输出结果中已经没有0,已经删除干净,符合预期。
实验报告
如图,分别检测6X^6+3X^5+4X^2与2X^2+3X相加和相乘运算,得到
6X^6+3X^5+4X^2+2X^2+3X+2X^2+3X和12X^8+18X^7+6X^7+9X^6+8X^4+12X^3,
符合预期。
数值计算实践I 、方程求根一、实验目的熟悉和掌握Newton 法,割线法,抛物线法的方法思路,并能够在matlab 上编程实现二、问题描述(1).给定一个三次方程,分别用Newton 法,割线法,抛物线法求解. 方程的构造方法:(a)根:方程的根为学号的后三位乘以倒数第二位加1再除以1000. 假设你的学号为B06060141,则根为141*(4+1)/1000=0.564(b)方程:以你的学号的后三位数分别作为方程的三次项,二次项,一次项的系数,根据所给的根以及三个系数确定常数项. 例如:你的学号是B06060141,则你的方程是x 3+4x 2+x+a 0=0的形式. 方程的根为0.564,因此有0.5643+4*0.5642+0.564+a0=0,于是a0=-2.015790144 你的方程为x 3+4x 2+x-2.015790144=0.(2)假设方程是sinx+4x 2+x+a0=0的形式(三个系数分别是学号中的数字),重新解决类似的问题(3)构造一个五次方程完成上面的工作.四次方程的构造:将三次多项式再乘以(x-p*)2得到对应的五次多项式(p*为已经确定的方程的根,显然,得到的五次方程有重根).(4)将(2)中的方程同样乘以(x-p*)得到一个新的方程来求解注:(1)Newton 法取0.5为初值,割线法以 0,1为初值,抛物线法以0,0.5,1为初值, (2)计算精度尽量地取高.终止准则:根据ε<--||1n n p p 来终止(3)可供研究的问题:(一)ε的取值不同对收敛速度有多大的影响(二)将注(1)中的初值该为其它的初值,对收敛性以及收敛速度有无影响 (三)能否求出方程的所有的根 (4)实验报告的撰写实验报告包含的内容:(一)实验目的(二)问题描述(三)算法介绍(包括基本原理)(四)程序(五)计算结果(六)结果分析(七)心得体会三、算法介绍在本问题中,我们用到了newton 法,割线法,抛物线法。
实验报告(2015 / 2016学年第二学期)课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间2016 年 5 月19 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专业信息管理与信息系统实习题名:图的基本运算班级姓名学号日期2016.05.19一、问题描述验证教材中关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法(见程序9.1~程序9.8),在邻接矩阵存储结构上实现图的深度和广度优先遍历算法,设计主函数,测试上述运算。
二、概要设计文件graph.cpp中在该文件中定义图数据结构的抽象模板类Graph。
邻接矩阵类MGraph是从抽象类Graph派生得来,邻接表类LGraph也是从抽象类Graph派生得来。
主函数的代码如图所示。
三、详细设计1.类和类的层次设计程序定义了Graph类,以及邻接矩阵类MGraph和邻接表类LGraph以及循环列表类SeqQueue。
邻接矩阵类MGraph继承了Graph的数据成员n和e,重载了Graph的纯虚函数。
保护数据成员T** a指向动态生成的二维数组,用以存储邻接矩阵。
邻接表类LGraph也继承了Graph的数据成员n和e及重载了Graph的纯虚函数,边结点由类ENode定义,每个结点有三个域adjVex、w和nextArc。
邻接表的表头组成为一维数组,a是指向该数组的指针。
(a)循环队列类(b)模版类Graph, MGraph和LGraph2.核心算法深度优先搜索用栈来实现:1)把根节点压入栈中2)每次从栈中弹出一个元素,搜索所有在它下一级的元素,把这些元素压入栈中。
并把这个元素记为它下一级元素的前驱3)找到所要找的元素时结束程序4)如果遍历整个树还没有找到,结束程序广度优先搜索使用队列来实现:1)把根节点放到队列的末尾2)每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。
南邮数据结构实验报告实验目的,通过本次实验,我们旨在加深对数据结构的理解,掌握数据结构的基本操作和算法设计能力,提高对数据结构的应用能力和实际问题的解决能力。
一、实验内容。
1. 实验一,线性表的基本操作。
本次实验中,我们首先学习了线性表的基本概念和操作,包括插入、删除、查找等操作,并通过实际编程操作来加深对线性表的理解。
2. 实验二,栈和队列的应用。
在实验二中,我们通过实际编程操作来学习栈和队列的应用,包括中缀表达式转换为后缀表达式、栈的应用、队列的应用等内容。
3. 实验三,树和二叉树的基本操作。
实验三中,我们学习了树和二叉树的基本概念和操作,包括树的遍历、二叉树的建立和遍历等内容,并通过实际编程操作来加深对树和二叉树的理解。
4. 实验四,图的基本操作。
最后,我们学习了图的基本概念和操作,包括图的存储结构、图的遍历等内容,并通过实际编程操作来加深对图的理解。
二、实验过程。
在实验过程中,我们首先对实验内容进行了深入的学习和理解,掌握了数据结构的基本概念和操作方法。
然后,我们通过实际编程操作来加深对数据结构的理解,并通过调试和修改程序来提高对数据结构的应用能力和实际问题的解决能力。
在实验过程中,我们遇到了一些问题,但通过不懈的努力和团队合作,最终顺利完成了实验任务。
三、实验结果与分析。
通过本次实验,我们深入理解了数据结构的基本概念和操作方法,掌握了线性表、栈、队列、树、二叉树和图的基本操作,并通过实际编程操作加深了对数据结构的理解。
同时,我们也提高了对数据结构的应用能力和实际问题的解决能力,为今后的学习和工作打下了坚实的基础。
四、实验总结。
通过本次实验,我们不仅加深了对数据结构的理解,还提高了对数据结构的应用能力和实际问题的解决能力。
在今后的学习和工作中,我们将继续努力,不断提升自己的专业能力,为将来的发展打下坚实的基础。
以上就是本次实验的报告内容,谢谢!。
南邮数据结构实验一南京邮电大学数据结构实验一一、实验目的本实验旨在通过实践操作,加深对数据结构的理解,掌握线性表的基本操作及其实现方式。
二、实验内容1. 实现线性表的顺序存储结构和链式存储结构;2. 实现线性表的基本操作,包括插入、删除、查找等;3. 对比顺序存储结构和链式存储结构的特点和优缺点。
三、实验步骤1. 线性表的顺序存储结构实现:a. 定义一个具有固定大小的数组作为存储空间;b. 实现线性表的初始化操作,包括设置表的长度和初始化元素;c. 实现线性表的插入操作,根据插入位置和元素值将元素插入到表中;d. 实现线性表的删除操作,根据删除位置将元素从表中删除;e. 实现线性表的查找操作,根据元素值查找元素在表中的位置;f. 实现线性表的遍历操作,输出表中的所有元素;g. 编写测试代码,验证线性表的基本操作是否正确。
2. 线性表的链式存储结构实现:a. 定义一个结点类,包含数据和指向下一个结点的指针;b. 实现线性表的初始化操作,创建一个头结点并初始化;c. 实现线性表的插入操作,根据插入位置和元素值创建新结点并插入到表中;d. 实现线性表的删除操作,根据删除位置找到对应结点并删除;e. 实现线性表的查找操作,根据元素值查找结点;f. 实现线性表的遍历操作,输出表中的所有元素;g. 编写测试代码,验证线性表的基本操作是否正确。
四、实验结果与分析1. 顺序存储结构的特点和优缺点:顺序存储结构使用数组作为存储空间,具有以下特点:- 插入和删除操作需要移动大量元素,效率较低;- 查找操作可以通过下标直接访问元素,效率较高;- 存储空间需要预先分配,大小固定,浪费空间的可能性较大;- 内存连续性要求较高,可能造成存储空间的碎片化。
2. 链式存储结构的特点和优缺点:链式存储结构使用结点之间的指针连接,具有以下特点:- 插入和删除操作只需要修改指针,效率较高;- 查找操作需要遍历整个链表,效率较低;- 存储空间可以动态分配,节省空间,灵活性较高;- 内存分散性较高,可能造成存储空间的碎片化。
一、实验目的本次实验旨在通过实际操作,加深对算法理论知识的理解,提高算法设计与分析能力,培养解决实际问题的能力。
通过实验,使学生掌握以下内容:1. 理解常见算法的基本原理和实现方法;2. 掌握算法设计与分析的常用方法;3. 能够运用算法解决实际问题。
二、实验内容本次实验选择了以下两个算法进行实现和分析:1. 冒泡排序算法;2. 快速排序算法。
三、实验过程1. 冒泡排序算法(1)算法原理冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。
遍历数列的工作是重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。
(2)实现步骤① 初始化一个布尔变量 swapped,用于判断是否发生交换;② 遍历数组,比较相邻的两个元素,如果前者大于后者,则交换它们的位置;③ 如果在一轮遍历中没有发生交换,则说明数组已经排序完成,退出循环;④ 重复步骤②和③,直到数组排序完成。
(3)代码实现```pythondef bubble_sort(arr):n = len(arr)for i in range(n):swapped = Falsefor j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr```2. 快速排序算法(1)算法原理快速排序是一种分而治之的排序算法。
基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
(2)实现步骤① 选择一个基准值(pivot),可以是数组的第一个元素、最后一个元素或中间元素;② 将数组分为两部分,一部分是小于基准值的元素,另一部分是大于基准值的元素;③ 对这两部分数据分别进行快速排序;④ 递归执行步骤①至③,直到数组排序完成。
实验报告(2015 / 2016 学年第一学期)课程名称数据结构实验名称图的基本运算及飞机换乘次数最少问题实验时间2015 年12 月 4 日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q14010119 学院(系)贝尔英才专业信息科技强化班实验报告实验名称图的基本运算及飞机换乘次数最少问题指导教师黄海平实验类型验证实验学时 4 实验时间12。
4一、实验目的和要求飞机最少换乘次数问题。
(1)设有n个城市,编号为0~n-1,m条航线的起点和终点由用户输入提供。
寻找一条换乘次数最少的线路方案。
(2)参考:可以使用有向图表示城市间的航线;只要两城市间有航班,则图中这两点间存在一条权值为1的边;可以使用Dijkstra算法实现。
二、实验环境(实验设备)VSUAL STUDIO2015三、实验原理及内容对象视图:源代码:Graph。
h#include<iostream>#include<string.h〉using namespace std;const int INF = 2147483647;enum ResultCode { Underflow,Duplicate,Failure,Success, NotPresent,OutOfBounds};template <class T〉class Graph//抽象类{public:virtual ResultCode Insert(int u, int v,T w) = 0;virtual ResultCode Remove(int u, int v) = 0;virtual bool Exist(int u, int v)const = 0;protected:int n, e;};template <class T>class MGraph :public Graph〈T> //邻接矩阵类{public:MGraph(int mSize, const T noedg);~MGraph();ResultCode Insert(int u,int v,T w);ResultCode Remove(int u,int v);bool Exist(int u,int v)const;int Choose(int*d, bool *s);void Dijkstra(int v,T *d, int*path);protected:T **a;T noEdge;};template〈class T〉MGraph〈T>::MGraph(int mSize, const T noedg){n = mSize;e = 0;noEdge = noedg;a = new T*[n];for(int i = 0; i〈n; i++){a[i] = new T[n];for(int j = 0; j〈n; j++)a[i][j] = noEdge;a[i][i] = 0;}}template〈class T>MGraph〈T>::~MGraph(){for (int i = 0; i〈n; i++)delete[]a[i];delete[]a;}template <class T〉ResultCode MGraph〈T>::Insert(int u, int v,T w){if (u<0 || v〈0 ||u>n — 1 || v〉n — 1 ||u == v)return Failure;if(a[u][v] != noEdge)return Duplicate;a[u][v] = w;a[v][u] = w;e++;return Success;}template〈class T〉ResultCode MGraph<T>::Remove(int u, int v){if(u<0 ||v〈0 ||u〉n — 1 ||v〉n - 1 ||u == v)return Failure;if (a[u][v] == noEdge)return NotPresent;a[u][v] = noEdge;a[v][u] = noEdge;e—-;return Success;}template〈class T〉bool MGraph〈T〉::Exist(int u,int v)const{if(u<0 || v<0 || u>n - 1 || v>n - 1 || u == v|| a[u][v] == noEdge) return false;return true;}template <class T>int MGraph<T>::Choose(int*d,bool *s) //求最小d[i]{int i, minpos;T min;min = INF;minpos = -1;for(i = 0; i<n; i++)if(d[i]〈= min&&!s[i]){min = d[i];minpos = i;}return minpos;}template <class T〉void MGraph〈T>::Dijkstra(int v,T*d,int *path)//迪杰斯特拉算法{int i, k, w;if (v〈0 ||v〉n — 1)throw OutOfBounds;bool *s = new bool[n];for(i = 0; i<n; i++){s[i] = false;d[i] = a[v][i];if(i != v&&d[i]<INF)path[i] = v;elsepath[i] = -1;}s[v] = true;d[v] = 0;for (i = 1; i〈n; i++){k = Choose(d, s);s[k] = true;for(w = 0; w<n; w++)if (!s[w]&& (d[k] + a[k][w])<d[w]){d[w] = d[k] + a[k][w];path[w] = k;}}}源.cpp#include<iostream〉#include<string。
实验报告(2015 / 2016学年第二学期)课程名称数据结构A实验名称二叉树的基本操作及哈夫曼编码译码系统的实现实验时间2016 年 4 月14 日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专业信息管理与信息系统实习题名:二叉树的基本操作班级姓名学号日期2016.04.14一、问题描述设计递归算法,实现下列二叉树运算:删除一棵二叉树、求一棵二叉树的高度、求一棵二叉树中叶子结点数、复制一棵二叉树、交换一棵二叉树的左右子树。
设计算法,按自上到下,从左到右的顺序,按层次遍历一棵二叉树。
设计main函数,测试上述每个运算。
二、概要设计文件tree.cpp中在该文件中定义二叉树的链式存储结构,用队列实现二叉树的层次遍历,并且编写实现二叉树的各种基本操作函数。
其中包括结点类BTNode,循环队列类SeqQueue,二叉树类BinaryTree。
主函数main的代码如图所示。
三、详细设计1.类和类的层次设计程序定义了循环队列SeqQueue类和二叉树BinaryTree类。
SeqQueue类主要是用队列实现,层次遍历。
运用后序遍历思想,把树分解为左右子树和跟结点再进行左右交换并计算树的高度,最后删除二叉树。
(b)二叉树类2.核心算法程序利用循环队列SeqQueue类通过不断出队并输出节点的值,将左右孩子入队直到队列为空实现二叉树的层次遍历。
并运用后序遍历思想,将二叉树树分解为左右子树和根结点,利用(p -> lChild)和(p -> rChild)计算结点数目,并通过交换结点的左右子树实现左右交换,计算树的高度,最后删除二叉树。
核心算法主要是二叉树BinaryTree类中的High,Node_num,Exchange,Level_traversal四个函数,其设计流程图如下:High()Node_num()Exchange()Level_traversal()四、程序代码template<class T>int BinaryTree<T>::Node_num(BTNode<T>*p) //叶子结点{if(p){if(p -> lChild == NULL && p -> rChild == NULL)return 1;elsereturn Node_num(p -> lChild) + Node_num(p -> rChild);}elsereturn 0;}template<class T>void BinaryTree<T>::Exchange(BTNode<T>*&t) //左右子树交换{if(t){BTNode<T>*q = t -> lChild;t -> lChild = t->rChild;t -> rChild = q;Exchange(t -> lChild);Exchange(t -> rChild);}}template<class T>void BinaryTree<T>::Level_traversal(void(*Visit)(T&x)) //层次遍历{Level_traversal(Visit, root);cout << endl;}template<class T>void BinaryTree<T>::Level_traversal(void(*Visit)(T&x),BTNode<T>*t) //层次遍历{BTNode<T> *a;Visit(t -> element);if(t -> lChild)s.EnQueue(t -> lChild);if(t -> rChild)s.EnQueue(t -> rChild);while(s.Front(a) == true){if(a -> lChild)s.EnQueue(a -> lChild);if(a -> rChild)s.EnQueue(a -> rChild);Visit(a -> element);s.DeQueue();}}五、测试和调试1.测试用例和结果测试结果如下图2.结果分析1)程序能够正确的实现二叉树的基本的建立、删除、复制、遍历以及结点计算等基本操作。
南邮数据结构实验一数据结构是计算机科学中非常重要的一门课程,它研究的是如何组织和管理数据以便于高效地访问和操作。
在南京邮电大学的数据结构课程中,实验一是我们的第一个实验,旨在帮助我们熟悉基本的数据结构和算法。
任务一:线性表的实现线性表是一种最基本的数据结构,它由一组有序的元素组成,每个元素都有一个唯一的前驱和后继。
在这个实验中,我们需要实现一个线性表,并实现一些基本的操作,比如插入、删除和查找。
首先,我们需要定义一个数据结构来表示线性表。
一种常见的实现方式是使用数组,我们可以定义一个固定大小的数组来存储线性表的元素。
另一种方式是使用链表,我们可以定义一个节点结构来存储每个元素,并使用指针将这些节点连接起来。
接下来,我们需要实现线性表的插入操作。
插入操作可以在线性表的任意位置插入一个元素。
我们可以通过移动其他元素的位置来为新元素腾出空间,并将新元素插入到指定位置。
删除操作是将线性表中的一个元素移除。
我们可以通过将被删除元素的前驱和后继连接起来,跳过被删除元素来实现删除操作。
查找操作是在线性表中查找指定元素的位置。
我们可以遍历整个线性表,逐个比较元素的值,直到找到目标元素或者遍历完整个线性表。
任务二:栈的实现栈是一种特殊的线性表,它只允许在表的一端进行插入和删除操作。
栈的特点是先进后出,即最后插入的元素最先删除。
在这个实验中,我们需要实现一个栈,并实现一些基本的操作,比如入栈、出栈和判断栈是否为空。
与线性表类似,我们可以使用数组或链表来实现栈。
如果使用数组,我们需要定义一个指针来指示栈顶的位置。
如果使用链表,我们可以使用头指针来指示栈顶的位置。
入栈操作是将一个元素插入到栈顶。
我们可以将元素插入到数组的指定位置,或者创建一个新的节点并将其连接到链表的头部。
出栈操作是将栈顶的元素移除。
我们可以将栈顶的元素从数组中删除,或者将链表的头节点移除。
判断栈是否为空可以通过检查栈顶指针或者链表头指针是否为空来实现。
数据结构实验代码南邮实验课实验十各种算法性能比较#include <iostream.h>
#include <time.h>
#include <stdlib.h>
template <class T>
void swap(T &a,T &b)
{
T temp;
temp=a;
a=b;
b=temp;
}
template <class T> //选择排序
void SelectSort(T A[],int n)
{
int small;
for(int i=0;i<n-1;i++)
{ small=i;
for(int j=i+1;j<n;j++)
if(A[j]<A[small]) small=j;
swap(A[i],A[small]);
}
}
template <class T> //直接插入排序
void InsertSort(T A[],int n)
{
for(int i=1;i<n;i++)
{ int j=i;
T temp=A[i];
while(j>0 && temp<A[j-1])
{
A[j]=A[j-1]; j--;
}
A[j]=temp;
}
}
template <class T> //冒泡排序
void BubbleSort(T A[],int n)
{
int i,j,last;
i=n-1;
while(i>0)
{
last=0;
for(j=0;j<i;j++)
if(A[j+1]<A[j])
{
swap(A[j],A[j+1]);
last=j;
}
i=last;
}
}
template <class T> //快速排序
void QuickSort(T A[],int n)
{
QSort(A,0,n-1);
}
template <class T>
void QSort(T A[],int left,int right)
{
int i,j;
if(left<right)
{ i=left; j=right+1;
do
{
do i++;while(A[i]<A[left]);
do j--;while(A[j]>A[left]);
if(i<j) swap(A[i],A[j]);
}while(i<j);
swap(A[left],A[j]);
QSort(A,left,j-1);
QSort(A,j+1,right);
}
}
template <class T> //快速排序(改编)void BQuickSort(T A[],int n)
{
BQSort(A,0,n-1);
}
template <class T>
void BQSort(T A[],int left,int right)
{
int i,j;
if(left<right)
{ i=left; j=right+1;
do
{
do i++;while(A[i]<A[left]);
do j--;while(A[j]>A[left]);
if(i<j) swap(A[i],A[j]);
}while(i<j);
swap(A[left],A[j]);
if((j-left)>=10)
BQSort(A,left,j-1);
else
{
InsertSort(A,j-left);
return;
}
if((right-j)>=10)
BQSort(A,j+1,right);
else
{
InsertSort(A,right-j);
return;
}
}
}
template <class T> //两路合并排序void Merge(T A[],int i1,int j1,int i2,int j2) {
T *Temp=new T[j2-i1+1];
int i=i1,j=i2,k=0;
while(i<j1 && j<=j2)
if(A[i]<=A[j]) Temp[k++]=A[i++];
else Temp[k++]=A[j++];
while(i<=j1) Temp[k++]=A[i++];
while(j<=j2) Temp[k++]=A[j++];
for(i=0;i<k;i++) A[i1++]=Temp[i];
delete[] Temp;
}
template <class T>
void MergeSort(T A[],int n)
{
int i1,j1,i2,j2;
int size=1;
while(size<n)
{
i1=0;
while(i1+size<n)
{
i2=i1+size;
j1=i2-1;
if(i2+size-1>n-1)
j2=n-1;
else j2=i2+size-1;
Merge(A,i1,j1,i2,j2);
i1=j2+1;
}
size*=2;
}
}
void main()
{
int i,j;
int **a;
a=new int* [5]; //生成5 个相同的随机数组
for(i=0;i<5;i++)
a[i]=new int[50000];
srand(time(NULL));
for(i=0;i<500000;i++)
a[0][i]=rand();
for(i=1;i<5;i++)
for(j=0;j<50000;j++)
a[i][j]=a[0][j];
cout<<"生成100个随机数如下: "<<endl;
for(i=0;i<50000;i++)
cout<<a[0][i]<<" ";
cout<<endl<<endl<<"5种排序算法所用的时间如下: "<<endl;
clock_t start,finish; //时间函数
start=clock();
SelectSort(a[0],50000);
finish=clock();
cout<<"选择排序: "<<start<<finish<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
start=clock();
InsertSort(a[1],50000);
finish=clock();
cout<<"直接插入排序:
"<<start<<finish<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
start=clock();
BubbleSort(a[2],50000);
finish=clock();
cout<<"冒泡排序: "<<start<<finish<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
start=clock();
QuickSort(a[3],50000);
finish=clock();
cout<<"快速排序: "<<start<<finish<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
start=clock();
MergeSort(a[4],50000);
finish=clock();
cout<<"两路合并排序: "<<start<<finish<<(double)(finish-start)/CLOCKS_PER_SEC<<endl;
cout<<endl;
}。