数据结构实验报告_数据结构课程设计实例

转载请注明出处，代码可以直接用，实验截图未上传成功，在编译器里运行一下就有！！！！

 南通大学计算机科学与技术学院

数据结构

实验报告书

实 验 名__数据结构实验报告    

班    级___网络工程***________

姓    名_____**______________

学    号_____*******_______

指导教师       ******            

日    期      2018/01/16        

目 录

1 实验一：约瑟夫环——————————————2

2 实验二：学生信息管理—————————————5 

3 实验三：二叉树的建立与遍历———————————-8 

4实验四：最短路径问题  —————————————12

5实验五：H ASH查找技术—————————————29

4实验六：排序  ———————————————-34

实验一     约瑟夫环问题 

1 实验目的：

          为了更好的巩固有关链表的知识点，在实际操作中掌握循环单链表的相关应用，夯实基础，掌握学习内容中的重要点，将理论与实践更好的结合，将用循环单链表来解决经典问题——约瑟夫环问题。

2 算法思想：

         约瑟夫环问题的存储结构，由于约瑟夫环问题本身具有循环性，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点，将循环链表的结点定义为如下结构：

        Struct {

                 Int data;

                 Node *next;

                };

3 程序设计：

 下面给出伪代码描述：

  ①工作指针pre和p初始化，计数器初始化；

Pre=head;p=head->next;   

②循环直到p=pre ;

    如果count=m,则输出结点p的编号；

删除结点p,即p=pre->next;

否则执行工作指针pre 和p后移；

③退出循环，链表中仅剩下一个结点p,输出结点后删除结点；

  4程序试调及结果 ：

附源程序：

#include<iostream>

using namespace std;

struct Node

{

       int data;

       int number;

       Node *next;

};

int main()

{

       struct Node *Head, *pre, *p;

       int n,m;

       cout<<“请输入总人数n:”;

       cin>>n;

       cout<<“请输入要删除编号m:”;

       cin>>m;

       Head=pre=new Node;

       Head->number=1;

       cout<<“请输入第一个数:”;

       cin>>Head->data;

       cout<<“请输入最后一个数:”;

       for(int i=2;i<n;i++)

        pre->next=new Node;

        pre=pre->next;

        cin>>pre->data;

        pre->number=i;

       pre->next=Head;

       cout<<“将退出循环的数是:”<<endl;

       while(n)

       {

              for(int j=1;j<m;j++)

              pre=pre->next;

              p=pre->next;

              pre->next=p->next;

              cout<<p->data;

              delete p;

              n–;

       }

       return 0;}

5总结 :

       对链表的操作仍需要进一步深入了解，在上机过程中，对于要退出循环的编号所对应的结点的操作仍存在问题，考虑到时循环链表，两个指针的分工也及其重要，要多加练习！

实验二         学生信息管理

1实验目的：

         为进一步巩固所学知识并将其应用在实际生活中，已达到学以致用的目的，我这次做的学生信息管理的实验是用大一时VC++中的文件输入输出流来做的，本来打算将文件输入输出流与数据结构中的链表相结合操作，能力有限，仅用大一所学知识在此实验报告中！

2问题描述：

       将学生的学号 姓名 成绩分别输入，并根据成绩分数进行输出依次为学号 姓名 成绩。（排序部分的功能未写出）

3知识回顾：

         ①文件流的使用方法：

         Ofstream outfile;

         Fstream iofile;

         ②使用文件流对象的成员函数close()/open()关闭文件/打开文件

4 程序试调及结果：

#include<fstream.h>

#include<iostream.h>

#include<iomanip.h>

class Std

{

         int no;

         char name[10];

         int degree;

public:

         void gdata()

         {

                  cout<<“(学号 姓名 成绩):”;

             cin>>no>>name>>degree;

         }

         void display()

         {

                  cout<<setw(6)<<no<<setw(6)<<name<<setw(6)<<degree<<endl;

         }

};

void func1()

{

         ofstream out;

         out.open(“std.dat”);

         Std s;

         int n;

         cout<<“输入数据”<<endl;

         cout<<“学生人数:”;

         cin>>n;

         for(int i=0;i<n;i++)

         {

                  cout<<” 第”<<i+1<<“个学生”;

                  s.gdata();

                  out.write((char*)&s,sizeof(s));

         };

         out.close();

}

void func2()

{

         ifstream in;

         in.open(“std.dat”);

         Std s;

         cout<<“输入数据”<<endl;

         cout<<“学号 姓名 成绩”<<endl;

         in.read((char*)&s,sizeof(s));

         while(in)

         {

                  s.display();

                  in.read((char*)&s,sizeof(s));

         }

         in.close();

}

void main()

{

         int n;

         do

         {

                  cout<<“选择(1:输入数据 2:输出数据 其他:退出):”;

                  cin>>n;

                  switch(n)

                  {

                  case 1:func1();break;

                  case 2:func2();break;

                  }

         }while(n==1||n==2);

}

5 实验总结：

          写本次实验报告与数据结构中涉及的算法并无太多关联，但知识之间是相互融会贯通VC++是数据结构算法能够熟练运用的基石，它是实践代码的重要工具语言，因此不可学新忘旧，所学知识一定要经常反复练习，才会获得更多收获和成长！

实验三        二叉树的建立与遍历

1 实验目的：

编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc###de###，则建立二叉树。显示其先序序列为：abcde，中序序列为:cbaed, 后序序列为：cbeda。将二叉树的实际应用融汇在实践学习中，切勿纸上谈兵，此题仅仅是对二叉树的建立和遍历，没有进行具体的应用，意在掌握二叉树的的基本思想及遍历过程。

2 算法思想： 

          二叉树的遍历思想，即沿着某条搜索路线，依次对树中每个结点均做一次访问，由二叉树的定义可知，一棵非空二叉树由根结点及左右子树这三个部分组成，因此，在任一给定的结点上可以按照某种次序执行以下操作：

1. 访问根节点D；
2. 访问左子树L；
3. 访问右子树R；

先序序列：DLR 中序序列：LDR 后序序列：LRD

3 程序设计：

char data;

     Btnode *lchild;

今天的文章数据结构实验报告_数据结构课程设计实例分享到此就结束了，感谢您的阅读。