数据结构上机实验源代码
数据结构上机实验源代码
栈的应用
十进制数转换为八进制数，
逆序输出所输入的数
实验代码：
//stack.h，头文件
class stack{
public:stack();
bool empty()const;
bool full()const;
error_code gettop(elementtype &x)const;
error_code push(const elementtype x);
error_code pop();
private:
int count;
elementtype data[maxlen];
};
stack::stack(){
count=0;
}
bool stack::empty()const
{
return count==0;
}
bool stack::full()const
{
return count==maxlen;
}
error_code stack::gettop(elementtype &x)const
{
if(empty())return underflow;
else{
x=data[count-1];
return success;
}
}
error_code stack::push(const elementtype x)
{
if(full())return overflow;
data[count]=x;
count++;
return success;
}
error_code stack::pop()
{
if(empty())return underflow;
count--;
return success;
}
//主程序
#include
enum error_code{overflow,underflow,success};
typedef int elementtype;
const int maxlen=20;
#include"stack.h"
void read_write() //逆序输出所输入的数{
stack s;
int i;
int n,x;
cout<<"please input num int n:";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"please input a num:";
cin>>x;
s.push(x);
}
while(!s.empty())
{
s.gettop(x);
cout< s.pop(); } cout< } void Dec_to_Ocx(int n) //十进制转换为八进制 { stack s1; int mod,x; while(n!=0) { mod=n%8; s1.push(mod); n=n/8; } cout<<"the ocx of the dec is:"; while(!s1.empty()) { s1.gettop(x); cout< s1.pop(); } cout< } void main() {int n; // read_write(); cout<<"please input a dec:"; cin>>n; Dec_to_Ocx(n); } 队列的应用打印n行杨辉三角 实验代码： //queue.h class queue{ public:queue(){ count=0; front=rear=0;} bool empty(){ return count==0; } bool full(){ return count==maxlen-1; } error_code get_front(elementtype &x){ if(empty())return underflow; x=data[(front+1)%maxlen]; return success; } error_code append(const elementtype x) { if(full())return overflow; rear=(rear+1)%maxlen; data[rear]=x; count++; return success; } error_code serve(){ if(empty())return underflow; front=(front+1)%maxlen; count--; return success; } private:int count; int front; int rear; int data[maxlen]; }; //主程序 #include enum error_code{overflow,underflow,success}; typedef int elementtype; const int maxlen=20; #include"queue.h" void out_number(int n) //打印前n行的杨辉三角{ int s1,s2; int i; int j; int k; queue q; for(i=1;i<=(n-1)*2;i++) cout<<" "; cout<<"1 "< q.append(1); for(i=2;i<=n;i++) { s1=0; for(k=1;k<=(n-i)*2;k++) cout<<" "; for(j=1;j<=i-1;j++) { q.get_front(s2); q.serve(); cout< q.append(s1+s2); s1=s2; } cout<<"1 "< q.append(1); } } void main() {int n; cout<<"please input n:"; cin>>n; out_number(n); } 单链表实验 实验目的:实验目的 （1）理解线性表的链式存储结构。 （2）熟练掌握动态链表结构及有关算法的设计。 （3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 实验任务 说明1：本次实验中的链表结构均为带头结点的单链表。 说明2：为使实验程序简洁直观，下面的部分实验程序中将所需要的函数以调用库函数的形式给出，并假设将库函数放在程序文件“linklist.h”中，同时假设该库函数文件中定义了链表结构中的指针类型为link，结点类型为node，并定义了部分常用运算。 例如构建链表、以某种方式显示链表、从文件中读入一个链表、跟踪访问链表结点等。 各运算的名称较为直观，并有相应的注释，因而易于理解和实现。 读者在上机实验时，需要自己设计出所涉及到的库函数，或者将函数放在实验程序中，以方便实验程序的调试。如时间紧的话，也可到作者的网站下载以供参考（不完全相同）。编写算法实现下列问题的求解。 <1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。 实验测试数据基本要求： 第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2 第二组数据：链表长度n=0，i分别为0，2 <2>在第i个结点前插入值为x的结点。 实验测试数据基本要求： 第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：链表长度n=0，x=100，i=5 <3>删除链表中第i个元素结点。 实验测试数据基本要求： 第一组数据：链表长度n≥10，i分别为5,n,1,n+1,0 第二组数据：链表长度n=0，i=5 <4>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。 实验测试数据基本要求： 链表元素为（10,20,30,40,50,60,70,80,90,100）, x分别为25，85，110和8 <5>将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。 实验测试数据基本要求： 第一组数据：链表元素为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60） 第二组数据：链表元素为（10,20,30,40,50,60,70,80,90,100） <6>求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。 实验测试数据基本要求： 第一组 第一个链表元素为（1，3，6，10，15，16，17，18，19，20） 第二个链表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30） 第二组 第一个链表元素为（1，3，6，10，15，16，17，18，19，20） 第二个链表元素为（2，4，5，7，8，9，12，22） 第三组 第一个链表元素为（） 第二个链表元素为（1，2，3，4，5，6，7，8，9，10） 实验代码: //linklist.h enum error_code{arrange_error,null,success}; typedef struct node{elementtype data; struct node *next; }node; class list{ private:node *head; int count; public:list() //链表的初始化 {head=new node; head->next=NULL; count=0; } int length() //求链表的长度 { return count; } /***********取链表中第i个节点的指针**********************/ node * locate(const int i) { node *p=head; int j=0; if(i<1||i>length())return NULL; while(p!=NULL) {if(j==i)return p; p=p->next; j++;} return NULL; } /***************在第i节点之前插入数为x的节点****************/ error_code insert(const int i,const elementtype x) {node *p=head; int j=0; while(j!=i-1&&p!=NULL) {p=p->next; j++; } if(i<1||i>count+1){cout<<"该位置前不能插入元素"< return arrange_error;} node *s=new node; s->data=x; s->next=p->next; p->next=s; count++; cout<<"插入成功！"< return success; } /***************删除第i个节点*****************************/ error_code delete_element(const int i) { node *p=head; int j=0; while(j!=i-1&&p!=NULL) {p=p->next; j++; } if(i<1||i>length()){cout<<"此元素不存在"< return arrange_error;} node *u=p->next; p->next=u->next; count--; delete u; cout<<"删除成功"< return success; } /******************若原链表递增，插入一个元素保持其递增的顺序***********/ error_code insert1(const elementtype x) {node *p=head->next; if(head->next->data>x){node *u=new node; u->data=x; u->next=head->next; head->next=u; return success; } while(p->next!=NULL){ if(p->next->data>x){node *u=new node; u->data=x; u->next=p->next; p->next=u; return success; } p=p->next; } node *u=new node; u->data=x; u->next=NULL; p->next=u; return success; } //取链表头结点的地址 node *gethead() {return head;} //输出链表中的所有元素 error_code print() {node *p=head->next; while(p!=NULL) {cout< p=p->next; } cout< return success; } error_code depart( ) {list a; list b; node *pa=a.gethead(); node *pb=b.gethead(); node *p=head->next; while(p!=NULL){ if((p->data)%2==1) {node *u=new node; u->data=p->data; pa->next=u; pa=u; pa->next=NULL; } if((p->data)%2==0){ node *u=new node; u->data=p->data; pb->next=u; pb=u; pb->next=NULL; } p=p->next; } cout<<"链表所有的奇数项为："< a.print(); cout<<"链表所有的偶数项为："< b.print(); return success; } void interset(list b,list &c) { node *pa,*pb,*rc,*u; pa=head->next; pb=b.gethead()->next; rc=c.gethead(); while(pa!=NULL&&pb!=NULL) { if(pa->data else if(pa->data>pb->data)pb=pb->next; else{ u=new node; u->data=pa->data; rc->next=u; rc=u; c.count++; pa=pa->next; pb=pb->next; } } rc->next=NULL; cout<<"两链表中的公共元素为："< c.print(); } }; // 主程序 #include typedef int elementtype; #include"linklist.h" void main() { list a;list b;list c; int m; int n; int j; int i; int choice; elementtype temp; do { cout<<"0，实验结束"< cout<<"1，实验要求1"< cout<<"2，实验要求2"< cout<<"3，实验要求3"< cout<<"4，实验要求4"< cout<<"5，实验要求5"< cout<<"6，实验要去6"< cout<<"请选择所要做的实验"< cin>>choice; switch(choice) { case 0:cout<<"实验结束"< break; case 1://*****************实验要求1 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } cout<<"请输入i的值"< cin>>i; if(a.locate(i)!=NULL)cout<<"链表第"< else cout<<"NULL"< cout<<"请输入i的值"< cin>>i; if(a.locate(i)!=NULL)cout<<"链表第"< else cout<<"链表第"< cout<<"请输入n的值"< cin>>n; for(j=0;j<3;j++) { if(a.locate(n+j)!=NULL)cout<<"链表第"< else cout<<"链表第"< } break; case 2://******************实验要求2 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } cout<<"请输入x的值："< cin>>temp; for(j=1;j<=3;j++) {cout<<"请输入插入点的位置："< cin>>i; a.insert(i,temp); } cout<<"请输入n的值："< cin>>n; for(j=0;j<3;j++) { a.insert(n+j,temp); } break; case 3://******************实验要求3 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } int n1; cout<<"请输入要删除的元素的位置"< a.delete_element(i); cout<<"请输入n的值"< cin>>n; a.delete_element(n); n1=n+1; cout<<"请输入要删除的元素的位置"< a.delete_element(i); cout<<"删除"< a.delete_element(n1); cout<<"请输入要删除的元素的位置"< a.delete_element(i); break; case 4://*************实验要求4 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } cout<<"链表未插入前的，其中的只有："< a.print(); for(j=1;j<=4;j++) { cout<<"请输入要插入的元素x的值："< cin>>temp; a.insert1(temp); cout<<"插入后链表中的值为："< a.print(); } break; case 5://***********实验要求5 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } a.depart(); break; case 6://**************************************************实验要求6 cout<<"请输入a链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; a.insert(j,temp); } cout<<"请输入链表的长度："< cin>>m; for(j=1;j<=m;j++) { cout<<"请输入元素的值"< cin>>temp; b.insert(j,temp); } a.interset(b,c); cout<<"链表中的元素有："< b.print(); cout<<"链表中的元素有："< a.print(); break; default: { cout<<"请选择正确的实验要求"< break; } } }while(choice!=0); } 双链表实验实验要求,判断双链表是否对称 //dlinklist.h //双循环链表类的定义 struct Node { T data; Node *next; Node *prior; }; class DLinkList { private: Node *Head; int count; public: DLinkList() ;//构造函数，创建空双循环链表 ~DLinkList();//析构函数，删除表空间 void CreateList(int n);//创建具有n个元素的双循环链表 void ListDisplay();//输出表元素 void symmetry();//判断链表中的元素是否对称 }; //双循环链表类的实现 DLinkList::DLinkList()//构建函数，建一空双循环链表 { Head=new Node; Head->next=Head; Head->prior=Head; count=0; } DLinkList::~DLinkList()//析构函数，释放链表所占空间 { Node *p,*q; while(q->next!=Head) q=q->next; //定位q到尾结点？？？ while(Head!=Head->next) {//从头结点开始，依次释放结点 p=Head; Head=Head->next; q->next=Head; Head->prior=q; delete p; count--; } Head=NULL;//头结点指向空 } void DLinkList::CreateList(int n) {//尾插法(正序)创建具有n个元素的双循环链表 Node *p,*s;//设置工作指针。p指向尾结点 p=Head; cout<<"请依次输入"< for(int i=1;i<=n;i++) { s=new Node;//新建元素结点 cin>>s->data;//输入新建数据元素值 s->next=p->next;//新结点链入表尾 p->next=s; s->prior=p; Head->prior=s; p=s; count++; } } void DLinkList::ListDisplay() {//显示链表 Node *p; p=Head->next; int i=1; while(p!=Head) { cout< cout< p=p->next; i++; } } void DLinkList::symmetry() { Node *p,*s; int i; p=Head->next; s=Head->prior; for(i=1;i<=count/2;i++) { if(p->data!=s->data){cout<<"链表不对称"< p=p->next; s=s->prior; } if(i==count/2+1)cout<<"链表对称"< } //主程序 #include typedef int T; #include "dLinklist.h" void main() //主函数 { int i; DLinkList L;// int choice; do {//显示主菜单 cout<<"1-创建双循环链表\n"; cout<<"2-判断链表是否对称\n"; cout<<"3-显示链表\n"; cout<<"4-退出\n"; cout<<"Enter choice:"; cin>>choice; switch(choice) { case 1://创建链表 cout<<"请输入要创建的链表中元素个数:"; cin>>i;//将创建的链表中数据元素的个数 cout< L.CreateList(i); break; case 2://判断链表是否为空 L.symmetry(); break; case 3://显示表 L.ListDisplay(); cout< break; case 4://退出 cout<<"结束运行"< break; default:// cout<<"Invalid choice\n"; break; } }while(choice!=4);//结束 } 二叉树的试验 试验要求:二叉树的构建,二叉树的前序,中序,后序遍历算法,查找替换树中的节点,交换一棵树的左右子树 试验代码: #include enum error_code{success}; typedef char elementtype; typedef struct bnode{ elementtype data; struct bnode *lchild,*rchild; }bnode, *bitree; class bitre{ private:bnode *root; void create(bitree &T); int high(bnode *T); void preorder(bnode *T);//先序遍历 void inorder(bnode *T);//中序遍历 void postorder(bnode *T);//后序遍历 public: bnode * getroot(){return root;} void create(){create(root);} int high(){return high(root);} void preorder(){preorder(root);}//先序遍历 void inorder(){inorder(root);}//中序遍历 void postorder(){postorder(root);}//后序遍历 void search(bnode *T,char &num,bitree &m);//查找 void jhuan(bnode * T,char &num,char &temp);//替换 void jbitree(bnode *T,char &num);//交换一个节点的左右子树 }; void bitre::jbitree(bnode *T,char &num)//交换一个节点的左右子树 { if(T!=NULL) { if(T->data==num) { bnode *temp; temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; } jbitree(T->lchild,num); jbitree(T->rchild,num); } } void bitre::jhuan(bnode *T,char &num,char &temp)//替换树中的元素 { if(T!=NULL) { if(T->data==num){T->data=temp;cout<<"交换成功"< jhuan(T->lchild,num,temp); jhuan(T->rchild,num,temp); } } void bitre::search(bnode *T,char &num,bitree &m) //查找元素并返回该元素的地址 { if(T!=NULL) { if(T->data==num)m=T; search(T->lchild,num,m); search(T->rchild,num,m); } } int max(int m,int n) //求最大值 {return (m>=n)?m:n;} int bitre::high(bnode *T) { if(T==NULL){ return 0; } else return max(high(T->lchild),high(T->rchild))+1; } void bitre::create(bitree &T) //创建一颗二叉树{char x; cin>>x; if ( x== '.' ) T = NULL; else{T = new bnode; T -> data = x; create ( T -> lchild ); create ( T -> rchild ); } } void bitre::preorder(bnode *T) { if(T!=NULL) { cout< preorder(T->lchild); preorder(T->rchild); } } void bitre::inorder(bnode *T) { if(T!=NULL) { inorder(T->lchild); cout< inorder(T->rchild); } } void bitre::postorder(bnode *T) { if(T!=NULL) { postorder(T->lchild); postorder(T->rchild); cout< } } void main() { char ch; char dh; bitre t; bitree a; cout<<"请按先序序列输入二叉树中元素的值"< t.create(); cout<<"树的先序序列为"< t.preorder(); cout< cout<<"树的中序序列为"< t.inorder(); cout< cout<<"树的后序序列为"< t.postorder(); cout< cout<<"请输入查找的元素："; cin>>ch; t.search(t.getroot(),ch,a); cout< cout<<"请先后输入待交换的元素与交换的元素"< cin>>ch; cin>>dh; t.jhuan(t.getroot(),ch,dh); cout<<"请输入待交换节点的元素值"< cin>>ch; t.jbitree(t.getroot(),ch); t.preorder(); cout< } 图的试验 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) { 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 #include return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); } 数据结构实验报告 一．顺序表 要求：实现顺序表的初始化、在指定位置插入和删除元素。 算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。 程序代码： #include for(i=0;i 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 顺序表的基本操作 #include int j=0; while(L.data[j]!=x) j++; if(j==https://www.wendangku.net/doc/6715481727.html,st) { cout<<"所查找值不存在！"< 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四） 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 【实验题】 1．狐狸逮兔子 围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？ （提示：这实际上是一个反复查找线性表的过程。） 【数据描述】 定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。 #define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位） }SqList; 【算法描述】 status InitList_Sq(SqList &L) { //构造一个线性表L L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType)); If(!L.elem) return OVERFLOW; //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } //InitList_Sq status Rabbit(SqList &L) { //构造狐狸逮兔子函数 int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口 for(i=0;i #include数据结构课程实验指导书
数据结构上机实验报告
数据结构上机实验答案
数据结构实验报告代码
数据结构实验报告全集
数据结构课程设计题目及要求
计10--数据结构专题实验rev2
数据结构实验一的源代码
数据结构上机实验报告
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
经典数据结构上机题_答案解析
数据结构实验程序
《数据结构与算法》上机实验要求
数据结构上机实验指导
数据结构实验题参考答案
数据结构上机实验线性表单链表源代码