山东大学数据结构课程设计报告

山东大学计算机科学与技术学院数据结构课程实验报告了Input函数和Output函数。

对问题三，仿课本所述，定义Term类作为SparseMatrix类的友元类，包含行、列、值三个要素的成员变量，用Term类的数组实现稀疏矩阵的行主映射存储。

查找行为的实现方式是，找到位于目标元素前一行的最后一个元素，再从这个元素开始向下搜索，直到找到和目标元素同一行但是列数小于目标元素的元素a[k-1]，然后决定下一步的行为————插入一个新项Term作为a[k]并将已有元素向后移位，还是修改已存在的项a[k]。

以此原理编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。

对问题四，仿照课本例子编写了有序链表类SortedChain、开放寻址的散列表类HashTable、基于有序链表链接的散列表类ChainHashTable，并对这三个类分别扩展编写了Output函数。

3.测试结果（测试输入，测试输出）问题一：问题二：上图显示了输入不符合下三角方阵约束时，抛出异常并退出程序。

上图是正常运行的结果。

问题三：普通的输入和输出操作如下：矩阵相加：矩阵转置：问题四：以上图的数据为例。

从346就应该在链表链接的散列表上看到开放寻址解决冲突的例子。

返回开放寻址的输出段，可以看到符合预期的结果：4.实现源代码（程序风格清晰易理解，有充分的注释）/** TridiagonalMatrix.h** Created on: Nov 22, 2015* Author: xudp*/#ifndef TRIDIAGONALMATRIX_H_#define TRIDIAGONALMATRIX_H_#include<iostream>using namespace std;template<class T>class TridiagonalMatrix {public:// 1、创建三对角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。

济南大学数据结构课程设计总结济南大学数据结构课程设计总结课程设计总结本次课程设计中,使用线性表的顺序存储结构、指针传递等编程思想，再次熟悉了顺序表的数据结构及存储结构，熟练使用指针传递及指针操作的。

程序设计中，基本外框实现简单一些，一次编写并调试成功，在实现集合运算的三个子程序时显得稍微费时，包括只声明但没有实际创建用于保存的顺序表Lc运行时只看到内存使用错误但不知道具体位置浪费了时间；在执行并操作时按照最初设计是直接将位于Lb的元素而不存在于La的元素复制到La中，导致在后期操作交运算时出现结果错误，后期才将其调整为含有3个参数输入的子函数；另外声明三个顺序表时使用如下：Sqlistlist1,list2,list3;Sqlist*La,*Lb,*Lc;La=&list1;Lb=&list2; Lc=&list3;的语句，相对而言有一定的不合理，但不知道具体该如何改进；在使用数据结构时，题目已经要求是整型数据元素，可以直接使用一维数组来操作，不过在控制循环时要用sizeof()库函数实现，另外在运算结果上要有值回传的实现，相对而言不如用指针方便；再分配存储空间时不合理，La 和Lb的长度可以从终端输入在分配相应的空间大小，Lc的大小可以适当的根据La和Lb的长度动态的设定；在设计时间复杂度上可以改进，但没找到更好的方法。

通过实践可以清楚的了解编程的细节及各个子函数与主函数的调用配合，熟悉并运用课本所学知识，从设定合适数据结构，设计各子函数功能及配合到时间复杂度和程序容错能力及改进都是对个人编程能力的锻炼和提高。

另外编程时看清题目的功能是最关键的，否则会混乱程序结构且得不到想要的结果。

扩展阅读：数据结构课程设计总结(模板)《数据结构》课程设计报告题目：班级：计算机系1001班姓名：王彩娟刘爽学号：4236指导教师：刘延岭日期：202*年7月3日一、课程设计目标1、问题描述以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。

数据结构课程设计报告---构件标识系统学院：软件学院专业：软件工程年级***：***学号：***一、系统开发平台1.1题目：构件标识1.2开发工具：VC++6.01.3语言：C++1.3操作系统：Windows XP 或Windows7系统二、系统规划2.1任务述：图是由非连通图和连通图构成的，非连通图又由几个独立的子连通图构成，每个子连通图称为一个构件，本系统需要将非连通图的子连通图进行标记构件，并图形化演示构件标识的过程。

2.2任务目标：（1）根据所输入数据构造图，形成直观的图形；（2）运用BFS算法将所输入数据构成的图进行标识，演示标识过程，并将不同构件的顶点标识成不同的颜色；（3）输入错误弹出对话框提示；（4）使用多组测试数据证明结果正确。

三、系统定义3.1系统边界：3.2系统描述：本系统是一个实现实际应用性很强的功能的系统。

实际生活中，有很多方面需要对一个大的系统按照其相互关联的关系进行小的分类，这需要建立一个模型，本系统抽象其为无向图的模型，实现对子连通图的标识。

其过输入图中顶点数和边数以及开始遍历的顶点进行图的构造，图形显示无向图，并显示图的构件的个数及各不同构件的元素组成。

四、需求分析4.1 数据结构需求： 输入为图中各顶点和各边（不用逗号和空格隔开，直接连接输入为一行即可），还需要输入开始进行遍历的顶点；输出为输入数据所构成的无向图（即是根据BFS 算法所输出的不同颜色标识的构件图）和构件的个数以及各构件的元素组成。

4.2 操作需求：首先输入顶点数，边数和各个顶点各个边以及开始遍历的顶点，输入完成后点击BFS 按钮将所输入的数据生成构件图在下边的图形界面显示，可以点击上一步或下一步按钮浏览生成过程。

4.3 系统需求说明:（1）可供11个顶点以及最多55条边存储的空间；（2）以秒为单位的响应速度；（3）能对数据输入的各种不同序列做出相应的响应。

五、数据结构设计5.1逻辑结构:非线性结构，无向图由顶点和边构成，分为连通图和非连通图，非连通图又由几个小的子连通图构成，进行构件时，分别对图中的子连通图进行标识。

《数据结构》课程设计报告一、课程目标《数据结构》课程旨在帮助学生掌握计算机科学中数据结构的基本概念、原理及实现方法，培养其运用数据结构解决实际问题的能力。

本课程目标如下：1. 知识目标：（1）理解数据结构的基本概念，包括线性表、栈、队列、串、数组、树、图等；（2）掌握各类数据结构的存储表示和实现方法；（3）了解常见算法的时间复杂度和空间复杂度分析；（4）掌握排序和查找算法的基本原理和实现。

2. 技能目标：（1）能够运用所学数据结构解决实际问题，如实现字符串匹配、图的遍历等；（2）具备分析算法性能的能力，能够根据实际问题选择合适的算法和数据结构；（3）具备一定的编程能力，能够用编程语言实现各类数据结构和算法。

3. 情感态度价值观目标：（1）培养学生对计算机科学的兴趣，激发其探索精神；（2）培养学生团队合作意识，提高沟通与协作能力；（3）培养学生面对问题勇于挑战、善于分析、解决问题的能力；（4）引导学生认识到数据结构在计算机科学中的重要地位，激发其学习后续课程的兴趣。

本课程针对高年级学生，课程性质为专业核心课。

结合学生特点，课程目标注重理论与实践相结合，强调培养学生的实际操作能力和解决问题的能力。

在教学过程中，教师需关注学生的个体差异，因材施教，确保课程目标的达成。

通过本课程的学习，学生将具备扎实的数据结构基础，为后续相关课程学习和职业发展奠定基础。

二、教学内容根据课程目标，教学内容主要包括以下几部分：1. 数据结构基本概念：线性表、栈、队列、串、数组、树、图等；教学大纲：第1章 数据结构概述，第2章 线性表，第3章 栈和队列，第4章 串。

2. 数据结构的存储表示和实现方法：教学大纲：第5章 数组和广义表，第6章 树和二叉树，第7章 图。

3. 常见算法的时间复杂度和空间复杂度分析：教学大纲：第8章 算法分析基础。

4. 排序和查找算法：教学大纲：第9章 排序，第10章 查找。

教学内容安排和进度如下：1. 第1-4章，共计12课时，了解基本概念，学会使用线性表、栈、队列等解决简单问题；2. 第5-7章，共计18课时，学习数据结构的存储表示和实现方法，掌握树、图等复杂结构；3. 第8章，共计6课时，学习算法分析基础，能对常见算法进行时间复杂度和空间复杂度分析；4. 第9-10章，共计12课时，学习排序和查找算法，掌握各类算法的实现和应用。

山东大学软件工程学院数据结构课程实验报告#ifndef CHAINNODE_H#define CHAINNODE_Hclass ChainNode{friend class List;friend class ListIterator; private:int data;ChainNode*link;};#endifList.h#ifndef LIST_H#define LIST_H#include<iostream>using namespace std;#include"ChainNode.h"class List{friend class ListIterator; public:List(){first=0;}~List();bool IsEmpty()const{return first==0;}int Length()const;bool Find(int k,int&x)const;int Search(const int&x)const;List&Delete(int k,int&x);List&Add(const int&x);void Output(ostream&out)const;private:ChainNode*first;};#endifList.cpp#include<iostream>using namespace std;#include"List.h"List::~List(){// 链表的析构函数，用于删除链表中的所有节点ChainNode*next;while(first){next=first->link;delete first;first=next;}}int List::Length()const{// 返回链表中的元素总数ChainNode*p=first;int length=0;while(p){length++;p=p->link;}return length;}bool List::Find(int k,int&x)const{// 寻找链表中的第k个元素，并将其传送至x//如果不存在第k个元素，则返回false，否则返回trueif(k<1||k>Length())return false;ChainNode*p=first;int index=1;while(index!=k){index++;p=p->link;}x=p->data;return true;}int List::Search(const int&x)const{// 寻找x，如果发现x，则返回x的地址//如果x不在链表中，则返回0ChainNode*p=first;int index=1;while(p&&p->data!=x){index++;p=p->link;}if(p)return index;elsereturn0;}List&List::Delete(int k,int&x){//按位置删除元素if(k<1||k>Length()){cout<<"不存在所要删除的元素"<<endl;return*this;}if(k==1)first=first->link;else{ChainNode*p=first;int index=1;while(index!=k-1){index++;p=p->link;}p->link=p->link->link;}return*this;}List&List::Add(const int&x){//在链表头进行链表的添加操作ChainNode*p=new ChainNode;p->data=x;p->link=first;first=p;return*this;}void List::Output(ostream&out)const{// 将链表元素送至输出流ChainNode*p;for(p=first;p;p=p->link){out<<p->data<<" ";}out<<endl;}listiterator.h#ifndef LISTITERATOR_H#define LISTITERATOR_H#include"ChainNode.h"class ListIterator{public:int*Initialize(const List&c);int*Next();private:ChainNode*location;};#endiflistiterator.cpp#include"ListIterator.h"#include"List.h"int*ListIterator::Initialize(const List&c){ location=c.first;if(location)return&location->data;return0;}int*ListIterator::Next(){if(!location)return0;location=location->link;if(location)return&location->data;return0;}Test.cpp#include<iostream>#include<stdlib.h>using namespace std;#include"List.h"#include"ListIterator.h"int main(){/********************************************///从键盘输入一组数存入链表并输出/********************************************/List*list1=new List();//建立链表1，输入的数存入其中int x;cout<<"请输入一系列整数作为链表节点的元素值(回车后按Ctrl + z 键后再按回车结束输出):"<<endl;while(cin>>x){list1->Add(x);}cin.clear();cout<<"链表内容为:"<<endl;list1->Output(cout);//输出链表1cout<<"请输入你想寻找的链表中的整数,将输出其在链表中的位置(不存在则为0):"<<endl;int y;cin>>y;cout<<"位置为:"<<list1->Search(y)<<endl;/*******************************************///将链表反向输出/*******************************************/cout<<"反序输出为: "<<endl;ListIterator*iterator=new ListIterator();//建立链表遍历器，遍历链表1int*n;n=iterator->Initialize(*list1);List*list2=new List();//建立反向链表while(n){//将链表1中的元素放入反向链表list2->Add(*n);n=iterator->Next();}list2->Output(cout);//输出反向链表/*******************************************///实现链表的合并/*******************************************/List*list3=new List();//建立链表aList*list4=new List();//建立链表bfor(int i=10;i>=0;i--){list3->Add(2*i+1);}for(int j=5;j>=0;j--){list4->Add(2*j);}cout<<"链表a为:"<<endl;list3->Output(cout);//输出链表acout<<"链表b为:"<<endl;list4->Output(cout);//输出链表bListIterator*iterator1=new ListIterator();//建立链表遍历器1，遍历链表aListIterator*iterator2=new ListIterator();//建立链表遍历器2，遍历链表bList*list5=new List();//建立链表5int*a=iterator1->Initialize(*list3),*b=iterator2->Initialize(*list4);while(a&&b){//将链表a、b中的元素按大小先后输入链表5，得到按从大到小排序的链表if(*a<*b){list5->Add(*a);a=iterator1->Next();}else{list5->Add(*b);b=iterator2->Next();}}while(a){list5->Add(*a);a=iterator1->Next();}while(b){list5->Add(*b);b=iterator2->Next();}n=iterator->Initialize(*list5);//遍历链表5List*list6=new List();//建立合并链表while(n){//将链表5反向，得到链表a、b的合并链表list6->Add(*n);n=iterator->Next();}cout<<"合并后链表为:"<<endl;list6->Output(cout);system("pause");return0;}实验结果：。

山东大学数据结构实验报告四一、引言数据结构实验报告四旨在通过实践巩固和应用所学的数据结构知识，培养学生的编程能力和问题解决能力。

本次实验的主要目的是设计并实现一个基于数据结构的应用程序，通过使用合适的数据结构和算法解决实际问题。

二、实验内容本次实验要求设计一个程序，实现以下功能：1. 输入一组整数，建立一个二叉排序树；2. 实现二叉排序树的查找、插入和删除操作；3. 对建立的二叉排序树进行中序遍历，并输出排序结果。

三、实验步骤1. 设计二叉排序树的数据结构在开始编写代码之前，我们需要先设计二叉排序树的数据结构。

二叉排序树的每个节点包含一个整数值和两个指针，分别指向左子树和右子树。

2. 实现二叉排序树的建立首先，我们需要实现一个函数，用于创建二叉排序树。

该函数根据输入的一组整数，逐个插入到二叉排序树中。

具体步骤如下：- 创建一个空的二叉排序树；- 依次读取输入的整数，并将其插入到二叉排序树中的合适位置；- 返回建立好的二叉排序树。

3. 实现二叉排序树的查找在二叉排序树中查找一个特定的值，可以使用递归或迭代的方式实现。

具体步骤如下：- 如果当前节点为空，返回空指针；- 如果当前节点的值等于目标值，返回当前节点；- 如果目标值小于当前节点的值，递归地在左子树中查找；- 如果目标值大于当前节点的值，递归地在右子树中查找。

4. 实现二叉排序树的插入在二叉排序树中插入一个新的值，需要保持二叉排序树的有序性。

具体步骤如下：- 如果树为空，将新值作为根节点插入；- 如果新值小于当前节点的值，将新值插入到左子树中；- 如果新值大于当前节点的值，将新值插入到右子树中。

5. 实现二叉排序树的删除在二叉排序树中删除一个特定的值，需要保持二叉排序树的有序性。

具体步骤如下：- 如果树为空，返回空指针；- 如果目标值小于当前节点的值，递归地在左子树中删除；- 如果目标值大于当前节点的值，递归地在右子树中删除；- 如果目标值等于当前节点的值，进行删除操作。

山东大学数据结构实验报告四实验报告四：堆排序算法的设计与实现一、引言堆排序是一种基于二叉堆的排序算法，其具有时间复杂度为O(nlogn)的特点，适用于大规模数据的排序。

本实验旨在通过设计与实现堆排序算法，掌握堆排序的原理和实现过程，并分析其时间复杂度和空间复杂度。

二、实验目的1. 理解堆排序的基本原理；2. 掌握堆排序算法的实现过程；3. 分析堆排序算法的时间复杂度和空间复杂度。

三、实验内容1. 设计堆排序算法的流程；2. 根据设计的流程，编写堆排序算法的代码；3. 使用随机生成的数据进行测试，并记录排序结果；4. 分析堆排序的时间复杂度和空间复杂度。

四、实验步骤1. 设计堆排序算法的流程：1.1 创建一个最大堆（Max Heap）；1.2 将堆顶元素与最后一个元素交换；1.3 对剩余元素进行堆调整，使其满足最大堆的性质；1.4 重复步骤2和3，直到所有元素排序完成。

2. 根据设计的流程，编写堆排序算法的代码：```java// 堆排序算法public class HeapSort {public static void sort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 依次将堆顶元素与最后一个元素交换，并重新调整堆 for (int i = n - 1; i >= 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}}// 调整堆public static void heapify(int[] arr, int n, int i) {int largest = i; // 最大元素的索引int left = 2 * i + 1; // 左子节点的索引int right = 2 * i + 2; // 右子节点的索引// 如果左子节点比最大元素大，则更新最大元素的索引if (left < n && arr[left] > arr[largest])largest = left;// 如果右子节点比最大元素大，则更新最大元素的索引if (right < n && arr[right] > arr[largest])largest = right;// 如果最大元素的索引不是当前节点，则交换当前节点和最大元素，并继续调整堆if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}}}```3. 使用随机生成的数据进行测试，并记录排序结果：```javapublic class Main {public static void main(String[] args) {int[] arr = generateRandomData(100); // 生成100个随机数 System.out.println("排序前：");printArray(arr);HeapSort.sort(arr); // 使用堆排序算法进行排序System.out.println("排序后：");printArray(arr);}// 生成随机数据public static int[] generateRandomData(int n) {int[] arr = new int[n];Random random = new Random();for (int i = 0; i < n; i++) {arr[i] = random.nextInt(1000);}return arr;}// 打印数组public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}}```排序前：567 245 789 123 456 789 234 567 890 123 ...排序后：1 2 3 4 5 6 7 8 9 10 ...4. 分析堆排序的时间复杂度和空间复杂度：- 时间复杂度：堆排序的建堆过程的时间复杂度为O(n)，每次调整堆的时间复杂度为O(logn)，共需要调整n-1次。

数据结构专业课程设计方案报告模板参考嘿，大家好！今天我来给大家分享一份关于数据结构专业课程的方案设计报告。

作为一名有着十年经验的大师，我可是见证了各种方案的诞生和演变。

那么，咱们废话不多说，直接进入主题吧！一、课程设计背景数据结构是计算机科学与技术领域的基础课程，对于培养同学们的逻辑思维能力、编程能力和算法设计能力具有重要意义。

随着信息技术的不断发展，数据结构的应用越来越广泛，已经成为各类软件开发、等领域的基础。

因此，本课程设计旨在帮助同学们掌握数据结构的基本原理和算法，提高同学们的实际编程能力。

二、课程设计目标1.理解数据结构的基本概念，熟悉各类数据结构的特点和应用场景。

2.学会使用常见的数据结构进行问题求解，具备分析问题和设计算法的能力。

3.掌握数据结构的基本算法，能够实现并优化相关算法。

三、课程设计内容1.线性表定义和特点常见操作（插入、删除、查找、排序等）应用场景（顺序存储、链式存储等）2.栈和队列定义和特点常见操作（入栈、出栈、入队、出队等）应用场景（递归、表达式求值、广度优先搜索等）3.树与二叉树定义和特点常见操作（创建、遍历、查找、插入、删除等）应用场景（查找排序、哈希表、优先队列等）4.图定义和特点常见操作（创建、遍历、查找、最短路径等）应用场景（社交网络、地图导航、最小树等）5.算法设计与分析常见算法（排序、查找、图算法等）时间复杂度分析空间复杂度分析四、课程设计方法1.理论教学：通过课堂讲解，使同学们了解数据结构的基本概念、原理和方法。

2.实践教学：通过上机实验，让同学们动手实现相关算法，提高编程能力。

3.课后作业：布置一些具有代表性的题目，让同学们独立思考，巩固所学知识。

五、课程设计评价1.课堂表现：考察同学们的出勤、发言、作业完成情况等。

2.上机实验：考察同学们的编程能力、算法实现情况等。

3.课后作业：考察同学们对知识点的掌握程度。

六、课程设计进度安排1.第一周：线性表2.第二周：栈和队列3.第三周：树与二叉树4.第四周：图5.第五周：算法设计与分析注意事项：1.理解深度与广度平衡每个数据结构都有其深奥的理论和复杂的实现细节，但初学者容易陷入要么只懂皮毛要么过度深入研究两极分化的困境。

实验2 ADT栈与队列的编程与实现实验目的：加深对抽象数据类型ADT栈和队列的理解；实验原理：参照课本p.64-66，及Figure3.39-3.44；课本p.82-83，及Figure3.57-3.60.实验内容：编写程序实现ADT栈的定义，及常用操作（数组或指针实现）：1)生成栈；2)Push3)Pop编写程序实现ADT队列的定义，及常用操作：1)生成队列；2)Enqueues入列；3)Isempty判断是否队列为空。

实验要求：1)实现ADT栈的结构及操作；2)实现ADT队列的结构及操作，并给出应用。

1.栈（链表实现）实验源程序：#include "stdafx.h"#include "stdio.h"#include "stdlib.h"#include "malloc.h"#include "string.h"typedef struct node //定义一个栈的结构{int data;struct node *pNext; //pNext为指向栈中下一个空间的指针}Node,*pNode;typedef pNode Stack;Stack InitStack() ; //初始化栈void CreateStack(Stack Top); //生成栈bool Empty(Stack Top); //判断栈是否为空void Push(Stack Top,int n); //进行压栈操作void Pop(Stack Top); //进行出栈操作void TraverseStack(Stack Top); //遍历栈的函数void DeleteStack(Stack Top); //清空栈的函数int main() //主函数{int n;char str[6]; //定义数组，存储操作指令Stack Top=NULL; //初始化Top为NULLTop=InitStack(); //初始化栈CreateStack(Top); //生成栈TraverseStack(Top); //遍历栈printf("请输入下一步操作指令(push,pop or end):");while(1){scanf("%s",str); //获取操作指令if(strcmp(str,"push")==0){printf("请输入入栈的元素:");scanf("%d",&n);Push(Top,n); //进栈操作TraverseStack(Top);printf("请输入下一步操作指令(push,pop or end):");}if(strcmp(str,"pop")==0){Pop(Top); //出栈操作TraverseStack(Top);printf("请输入下一步操作指令(push,pop or end):");}if(strcmp(str,"end")==0)break; //跳出循环if(strcmp(str,"push")!=0&&strcmp(str,"pop")!=0&&strcmp(str,"end")!=0) {printf("输入指令错误，请重新输入指令:");}}DeleteStack(Top); //释放栈空间return 0;}Stack InitStack() //进行栈的初始化的函数{Stack Top = (Stack)malloc(sizeof(Node)); //分配内存空间给栈顶if(Top==NULL){printf("动态分配内存失败\n");exit(1);}printf("初始化栈成功\n");Top->pNext = NULL; //栈顶指针的指向置为NULL；return Top;}void CreateStack(Stack Top) //生成栈{int LEN,x;Stack Bottom = Top; //令Top和Bottom指向同一空间Bottom->pNext = NULL;printf("请输入想要入栈的元素个数:");scanf("%d",&LEN);for(int i = 0; i < LEN; i++){printf("请输入第%d个元素(从栈顶到栈底):",i+1);scanf("%d",&x);Stack pNew = (Stack)malloc(sizeof(Node));pNew->data = x; //将输入的数放在栈data单元中Bottom->pNext = pNew; //Bottom指向新分配空间的单元pNew->pNext = NULL; //令pNew指向NULLBottom = pNew; //让新分配空间的单元成为栈底}printf("生成栈成功\n");}bool IsEmpty(Stack Top) // 判断栈是否为空{return Top->pNext==NULL;}void Push(Stack Top,int n) //进行进栈操作的函数{Stack pNew = (Stack)malloc(sizeof(Node)); //定义一个新节点，并分配内存空间if(pNew==NULL){printf("未能动态分配内存，进栈失败\n");return ;}pNew->data = n;pNew->pNext = Top->pNext;Top->pNext = pNew;}void Pop(Stack Top) //进行出栈操作函数{Stack p=Top->pNext;if (IsEmpty(Top)==true) //判断栈是否为空，为空就不能进行出栈操作{printf("栈为空，Pop失败\n");return ;}else{printf("弹出的栈顶元素为:");printf("%d \n",p->data); //显示出栈元素Top->pNext=p->pNext;free(p);}}void TraverseStack(Stack Top) //遍历栈，获取栈中的数值{printf("现在栈中的元素从栈顶到栈底依次为:");Stack p = Top->pNext;if(p==NULL)printf("栈空");while(p!=NULL){printf("%d ",p->data);p = p->pNext;}printf("\n");}void DeleteStack(Stack Top) //释放栈空间{Stack p,q ;p=Top->pNext;while (p != NULL){q=p->pNext;free(p);p=q;}Top->pNext=NULL;}实验结果：1）生成栈①初始化栈。

《数据结构》课程设计报告课程设计报告----数据结构学院:软件学院班级:11级二班学号:54110211姓名：刘海鲸辅导老师：刘亚波老师《数据结构》课程设计报告姓名：刘海鲸学号：54110211实验室：座位号:提交日期：2013.3.13成绩：指导教师：刘亚波问题解析（对问题的分析、解题思路与解题方法）：实验目的为使我们学习完数据结构课程后，全面深入理解数据结构知识，掌握应用技巧，提高应用与分析能力，并培养学生综合运用所学理论知识求解问题的能力和协作精神。

解题思路(分析)：题目要求独立编写程序，完成对起泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序6种内排序算法的比较，并且使用至少5组不同的输入数据（记录个数不小于1000个，其中包括完全正序，完全逆序和无序情况）进行排序，比较各组记录与各种排序方法在关键字比较次数和关键字移动次数这两个指标上的差异。

因此只需对文件进行排序并计算出两项指标针对某一组特定数据在不同排序方法中的值，既可以完成题目要求。

编写正确的排序算法，使用程序读取不同文件，并定义变量，记录排序过程中两项指标的值，就是本题的解题思路。

解题方法：使用Code::blocks作为本次实验的开发工具，使用C++完成程序。

首先使用数据产生程序来产生所需的5个数据文件，使用了C++中cstdlib文件中的rand（）函数和srand（）函数共同产生3组伪随机数；在另一个工程中创建了data.h与control.h两个头文件和main.cpp源文件，其中data.h定义了数据类型（模板类），包括主要的排序函数和数据成员，control.h定义了控制类，来完成界面控制，数据文件读取和排序功能的实现，main.cpp是对控制类对象的控制函数conmian（）的调用来完成整个程序。

最后运行程序来完成对比较指标的统计并进行分析，对得出结果进行解释。

任务分工：本实验由本人独立完成。

进度安排：为第一次实验课将6个内排序算法完成并调试成功，周末之前完成界面控制并对排序结果进行分析，第二次实验之前完成课程设计报告，第二次试验对程序结果进行最后检查并提交实验报告。

山东大学计算机科学与技术学院数据结构课程实验报告了Input函数和Output函数。

对问题三，仿课本所述，定义Term类作为SparseMatrix类的友元类，包含行、列、值三个要素的成员变量，用Term类的数组实现稀疏矩阵的行主映射存储。

查找行为的实现方式是，找到位于目标元素前一行的最后一个元素，再从这个元素开始向下搜索，直到找到和目标元素同一行但是列数小于目标元素的元素a[k-1]，然后决定下一步的行为————插入一个新项Term作为a[k]并将已有元素向后移位，还是修改已存在的项a[k]。

以此原理编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。

对问题四，仿照课本例子编写了有序链表类SortedChain、开放寻址的散列表类HashTable、基于有序链表链接的散列表类ChainHashTable，并对这三个类分别扩展编写了Output函数。

3.测试结果（测试输入，测试输出）问题一：问题二：上图显示了输入不符合下三角方阵约束时，抛出异常并退出程序。

上图是正常运行的结果。

问题三：普通的输入和输出操作如下：矩阵相加：矩阵转置：问题四：以上图的数据为例。

从346就应该在链表链接的散列表上看到开放寻址解决冲突的例子。

返回开放寻址的输出段，可以看到符合预期的结果：4.实现源代码（程序风格清晰易理解，有充分的注释）/** TridiagonalMatrix.h** Created on: Nov 22, 2015* Author: xudp*/#ifndef TRIDIAGONALMATRIX_H_#define TRIDIAGONALMATRIX_H_#include<iostream>usingnamespace std。

template<class T>class TridiagonalMatrix {public:// 1、创建三对角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。

山东大学软件工程学院数据结构课程实验报告学号：姓名：班级：软件工程2014级2班实验题目：图的操作实验学时：实验日期： 2015.12.9实验目的：掌握图的基本概念，描述方法；遍历方法。

硬件环境：实验室软件环境：Vistual Studio 2013实验步骤与内容：实验内容：1、创建图类。

二叉树的存储结构使用邻接矩阵或链表。

2、提供操作:遍历、BFS、DFS3、对建立好的图，执行上述各操作。

4、输出生成树。

5、输出最小生成树。

代码体：Adjacencywdigraph.h#ifndef ADJACENCYWDIGRAPH_H#define ADJACENCYWDIGRAPH_Hclass AdjacencyWDigraph{friend class AdjacencyWGraph;public:AdjacencyWDigraph(int Vertices = 10, int noEnge = 0);~AdjacencyWDigraph();bool Exist(int i, int j) const;int Edges() const{ return e; }int Vertices() const{ return n; }AdjacencyWDigraph& Add(int i, int j, const int& w = 1);AdjacencyWDigraph& Delete(int i, int j);int OutDegree(int i) const;int InDegree(int i) const;void InitializePos() { pos = new int[n + 1]; }void DeactivatePos() { delete[] pos; }int Begin(int i);int NextVertex(int i);void BFS(int v, int reach[], int label = 1);void DFS(int v, int reach[], int label = 1);bool Connected(int& x);int** SpanningTree();int** SpanningMinTree();void OutPut();private:int MinNum();int Min(int v, int reach[]);bool Connecting(int i);void dfs(int v, int reach[], int label);int NoEdge, n, e;int **a;int *pos;};#endifAdjacencywdigraph.cpp#include<iostream>#include<queue>using namespace std;#include"adjacencywdigraph.h"AdjacencyWDigraph::AdjacencyWDigraph(int Vertices, int noEdge){ n = Vertices;e = 0;NoEdge = noEdge;a = new int*[n + 1];for (int i = 1; i <= n; i++)a[i] = new int[n + 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)a[i][j] = NoEdge;}AdjacencyWDigraph::~AdjacencyWDigraph(){for (int i = 1; i <= n; i++)delete[] a[i];delete[] a;}bool AdjacencyWDigraph::Exist(int i, int j) const{if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)return false;return true;}AdjacencyWDigraph& AdjacencyWDigraph::Add(int i, int j, const int& w){ if (i < 1 || j < 1 || i > n || j > n)cout << "错误!点" << i << "或点" << j << "不存在,无法添加边" << endl;else if (a[i][j] != NoEdge)cout << "错误!该边已存在,无法再添加" << endl;else{a[i][j] = w;e++;}return *this;}AdjacencyWDigraph& AdjacencyWDigraph::Delete(int i, int j){if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)cout << "错误!该边不存在,无法删除" << endl;else{a[i][j] = NoEdge;e--;}return *this;}int AdjacencyWDigraph::OutDegree(int i) const{if (i < 1 || i > n){cout << "错误,该点不存在!" << endl;return 0;}else{int sum = 0;for (int j = 1; j <= n; j++)if (a[i][j] != NoEdge)sum++;return sum;}}int AdjacencyWDigraph::InDegree(int i) const{ if (i < 1 || i > n){cout << "错误,该点不存在!" << endl;return 0;}else{int sum = 0;for (int j = 1; j <= n; j++)if (a[j][i] != NoEdge)sum++;return sum;}}int AdjacencyWDigraph::Begin(int i){if (i < 1 || i > n){cout << "错误,该点不存在!" << endl;return 0;}else{for (int j = 1; j <= n; j++)if (a[i][j] != NoEdge){pos[i] = j;return j;}pos[i] = n + 1;return 0;}}int AdjacencyWDigraph::NextVertex(int i){ if (i < 1 || i > n){cout << "错误,该点不存在!" << endl;return 0;}else{for (int j = pos[i] + 1; j <= n; j++)if (a[i][j] != NoEdge){pos[i] = j;return j;}pos[i] = n + 1;return 0;}}void AdjacencyWDigraph::BFS(int v, int reach[], int label){ if (v < 1 || v > n){cout << "错误,该点不存在!" << endl;return;}queue<int> q;InitializePos();reach[v] = label;q.push(v);while (!q.empty()){int w = q.front();q.pop();int u = Begin(w);while (u){if (!reach[u]){q.push(u);reach[u] = label;}u = NextVertex(w);}}DeactivatePos();}void AdjacencyWDigraph::dfs(int v, int reach[], int label){ reach[v] = label;int u = Begin(v);while (u){if (!reach[u])dfs(u, reach, label);u = NextVertex(v);}}void AdjacencyWDigraph::DFS(int v, int reach[], int label){ if (v < 1 || v > n){cout << "错误,该点不存在!" << endl;return;}InitializePos();dfs(v, reach, label);DeactivatePos();}void AdjacencyWDigraph::OutPut(){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)cout << a[i][j] << "\t";cout << endl;}}bool AdjacencyWDigraph::Connecting(int i){ int *reach = new int[n + 1];for (int j = 1; j <= n; j++)reach[j] = 0;BFS(i, reach, 1);for (int j = 1; j <= n; j++)if (!reach[j]){delete[]reach;return false;}delete[] reach;return true;}bool AdjacencyWDigraph::Connected(int& x){ bool *flag = new bool[n + 1];for (int i = 1; i <= n; i++)flag[i] = Connecting(i);for (int i = 1; i <= n; i++)if (flag[i]){x = i;return true;}return false;}int AdjacencyWDigraph::Min(int v, int reach[]){int k = 0, min = 0;for (int i = 1; i <= n; i++){if (!reach[i] && a[v][i] != NoEdge && !min){k = i;min = a[v][i];}else if (!reach[i] && a[v][i] != NoEdge && min > a[v][i]){ k = i;min = a[v][i];}}return k;}int** AdjacencyWDigraph::SpanningTree(){int x;if (!Connected(x)){cout << "该图不是连通图,无法生成树!" << endl;return 0;}else{InitializePos();queue<int> q;int **b = new int*[n + 1];for (int i = 1; i <= n; i++)b[i] = new int[n + 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)b[i][j] = 0;int *reach = new int[n + 1];for (int i = 1; i <= n; i++)reach[i] = 0;reach[x] = 1;q.push(x);while (!q.empty()){int w = q.front();q.pop();int u = Begin(w);while (u){if (!reach[u]){q.push(u);b[w][u] = a[w][u];reach[u] = 1;}u = NextVertex(w);}}delete[] reach;DeactivatePos();return b;}}int AdjacencyWDigraph::MinNum(){int k = 0, m = 0;for (int i = 1; i <= n; i++){if (Connecting(i)){int min = 0;for (int j = 1; j <= n; j++){if (a[i][j] != NoEdge && !min){min = a[i][j];}else if (a[i][j] != NoEdge && min > a[i][j]){min = a[i][j];}}if (m && m > min){m = min;k = i;}else if (!m){m = min;k = i;}}}return k;}int** AdjacencyWDigraph::SpanningMinTree(){int x;if (!Connected(x)){cout << "该图不是连通图,无法生成树!" << endl;return 0;}else{int **b = new int*[n + 1];for (int i = 1; i <= n; i++)b[i] = new int[n + 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)b[i][j] = 0;int *reach = new int[n + 1];for (int i = 1; i <= n; i++)reach[i] = 0;x = MinNum();reach[x] = 1;int k1, k2, z, min = 1;while (min){min = 0;for (int i = 1; i <= n; i++)if (reach[i]){k2 = Min(i, reach);if (k2 && !min){min = a[i][k2];z = i;k1 = k2;}else if (k2 && min > a[i][k2]){min = a[i][k2];z = i;k1 = k2;}}reach[k1] = 1;b[z][k1] = a[z][k1];}delete[] reach;return b;}}Adjacencywgraph.h#ifndef ADJACENCYWGRAPH_H#define ADJACENCYWGRAPH_H#include"adjacencywdigraph.h"class AdjacencyWGraph :public AdjacencyWDigraph{public:AdjacencyWGraph(int Vertices = 10, int noEdge = 0): AdjacencyWDigraph(Vertices, noEdge){} AdjacencyWGraph& Add(int i, int j, const int& w = 1);AdjacencyWGraph& Delete(int i, int j);int Degree(int i){ return OutDegree(i); }bool Connected();int** SpanningTree();int** SpanningMinTree();int MinNum();};#endifAdjacencywgraph.cpp#include<iostream>#include<queue>using namespace std;#include"adjacencywgraph.h"AdjacencyWGraph& AdjacencyWGraph::Add(int i, int j, const int& w){ if (i < 1 || j < 1 || i > n || j > n)cout << "错误!点" << i << "或点" << j << "不存在,无法添加边" << endl;else if (a[i][j] != NoEdge)cout << "错误!该边已存在,无法再添加" << endl;else{a[i][j] = w;a[j][i] = w;e++;}return *this;}AdjacencyWGraph& AdjacencyWGraph::Delete(int i, int j){if (i < 1 || j < 1 || i > n || j > n || a[i][j] == NoEdge)cout << "错误!该边不存在,无法删除" << endl;else{a[i][j] = NoEdge;a[j][i] = NoEdge;e--;}return *this;}bool AdjacencyWGraph::Connected(){int *reach = new int[n + 1];for (int i = 1; i <= n; i++)reach[i] = 0;BFS(1, reach, 1);for (int i = 1; i <= n; i++)if (!reach[i])return false;return true;}int** AdjacencyWGraph::SpanningTree(){if (!Connected()){cout << "该图不是连通图,无法生成树!" << endl;return 0;}else{InitializePos();queue<int> q;int **b = new int*[n + 1];for (int i = 1; i <= n; i++)b[i] = new int[n + 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)b[i][j] = 0;int *reach = new int[n + 1];for (int i = 1; i <= n; i++)reach[i] = 0;reach[1] = 1;q.push(1);while (!q.empty()){int w = q.front();q.pop();int u = Begin(w);while (u){if (!reach[u]){q.push(u);b[w][u] = b[u][w] = a[w][u];reach[u] = 1;}u = NextVertex(w);}}DeactivatePos();delete[] reach;return b;}}int AdjacencyWGraph::MinNum(){int d = 0, e = 0, min = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (a[i][j] != NoEdge && !min){min = a[i][j];d = i;e = j;}else if (a[i][j] != NoEdge && a[i][j] < min){min = a[i][j];d = i;e = j;}}}return d;}int** AdjacencyWGraph::SpanningMinTree(){if (!Connected()){cout << "该图不是连通图,无法生成树!" << endl;return 0;}else{int **b = new int*[n + 1];for (int i = 1; i <= n; i++)b[i] = new int[n + 1];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)b[i][j] = 0;int *reach = new int[n + 1];for (int i = 1; i <= n; i++)reach[i] = 0;int x = MinNum();reach[x] = 1;int k1, k2, z, min = 1;while (min){min = 0;for (int i = 1; i <= n; i++)if (reach[i]){k2 = Min(i, reach);if (k2 && !min){min = a[i][k2];z = i;k1 = k2;}else if (k2 && min > a[i][k2]){min = a[i][k2];z = i;k1 = k2;}}reach[k1] = 1;b[z][k1] = b[k1][z] = a[z][k1];}delete[] reach;return b;}}Test.cpp#include<iostream>using namespace std;#include"adjacencywdigraph.h"#include"adjacencywgraph.h"int main(){AdjacencyWDigraph *awd = new AdjacencyWDigraph(5, 0);AdjacencyWGraph *awg = new AdjacencyWGraph(5, 0);//下面初始化一个有向图awd->Add(1, 5, 6);awd->Add(4, 3, 19);awd->Add(5, 4, 33);awd->Add(1, 2, 17);awd->Add(3, 4, 36);awd->Add(1, 3, 34);awd->OutPut();cout << "***********************************" << endl;cout << "宽度优先搜索开始" << endl;cout << "请输入起始点: "<<endl;int m;int *reach = new int[6];for (int i = 1; i <= 5; i++)reach[i] = 0;cin >> m;while (m < 1 || m>5){cout << "输入错误！ ";cin >> m;}awd->BFS(m, reach);cout << "从点" << m << "能搜索到的点有: " << endl;for (int i = 1; i <= 5; i++)if (reach[i])cout << i << "\t";cout << endl;cout << "***********************************" << endl; cout << "广度优先搜索开始" << endl;cout << "请输入起始点: " << endl;for (int i = 1; i <= 5; i++)reach[i] = 0;cin >> m;while (m < 1 || m>5){cout << "输入错误!请重新输入: ";cin >> m;}awd->DFS(m, reach);cout << "从点" << m << "能搜索到的点有: " << endl;for (int i = 1; i <= 5; i++)if (reach[i])cout << i << "\t";cout << endl;cout << "***********************************" << endl; system("pause");cout << "生成树为: " << endl;int **a = awd->SpanningTree();if (a){for (int i = 1; i <= 5; i++){for (int j = 1; j <= 5; j++)cout << a[i][j] << "\t";cout << endl;}}for (int i = 1; i <= 5; i++)delete[] a[i];delete[] a;cout << "***********************************" << endl; system("pause");cout << "最小生成树为 : " << endl;a = awd->SpanningMinTree();if (a){for (int i = 1; i <= 5; i++){for (int j = 1; j <= 5; j++)cout << a[i][j] << "\t";cout << endl;}}for (int i = 1; i <= 5; i++)delete[] a[i];delete[] a;delete awd;awd = NULL;system("pause");return 0;}实验结果：结论分析与体会：矩阵十分的形象，但是用于表示图的时候感觉有一些理解上的不容易，还是用直观的图来表示更加容易理解，但是相比于实际的代码操作来讲，用矩阵来表示图是最方便的。

附件：
山东大学计算机科学与技术学院
数据结构与算法课程实验报告
4.分析与探讨（结果分析，若存在问题，探讨解决问题的途径）
调试完成后能满足实验要求来求并输出数组的所有子集以及全排列
代码仅针对整数型数组，可已通过改变函数参数类型等操作来达到输出其他类型数组的全排列和所有子集的目的。

5.附录：实现源代码（本实验的全部源程序代码，程序风格清晰易理解，有充分的注释）
#include<iostream>
using namespace std;
void swap(int &x,int &y) //交换两数值的函数{
int t=x;
x=y;
y=t;
}
void output_subset(int *num, int *judge, int n,int len) //生成子集并输出{
if (n==len)
{
cout << "{ ";
for (int i=0;i<len;i++)
{
if (judge[i]==1)
cout<<num[i]<<" ";
}
cout<<"}"<<endl;
return;
}
//else。

数据结构实验报告——实验三实验题目：排序算法学号：日期：2014.11.26 班级：物联网工程姓名：Email：实验目的：线性表操作任务要求： 1掌握线性表的基本操作。

2、使用链表存储。

3、自表首插入元素，删除一个指定元素，查找指定元素。

软件环境：Win7 操作系统开发工具：visual C++ 6.0实验步骤：#include<iostream>#include<conio.h>#define LEN sizeof(LNode) //定义LEN为一个节点的长度using namespace std;enum BOOL{False,True}; //定义BOOL型typedef struct node{int data; //数据域struct node *next;//指向下一个节点的指针}LNode,*LinkList;void CreatList(LinkList &,int); //生成一个单链表BOOL ListInsert(LinkList &,int,int); //在单链表首中插入一个元素BOOL ListDelete(LinkList &,int,int&); //在单链表中删除一个元素BOOL ListFind_keyword(LinkList,int,int &); //按关键字查找一个元素BOOL ListFind_order(LinkList,int &,int); //按序号查找一个元素void ListPrint(LinkList); //显示单链表所有元素void main() {LinkList L; BOOL temp;int num,loc,ch,j,flag=1;//---------------------程序解说-----------------------cout<<"本程序实现链式结构的线性表的操作。