数据结构学期实验报告
数据结构
实验报告
2015/01/10
武汉大学信息管理学院
邹文平2013302330028
第2章线性表
一、实验问题：
编写一个单链表类的成员函数，实现删除带头结点的单链表中数据域值等于x的所有结点的操作。要求函数返回被删除结点的个数。
二、解决思路：
遍历整个单链表，将每一个结点的数据域与x进行比较，如果相等则删除该结点，若不相等则指针移向下一个结点。
成员函数的规格说明：
public int removeAll(Object x)
删除数据域值等于x的所有结点，并计算链表中被删除结点的个数。
参数：x —一个object对象
前置条件：参数x不能为null
返回：被删除结点的个数
后置条件：链表中数据域为x的所有结点已经从链表中删除
抛出：IllegalArgumentException表明传入的x不合法
注意：删除结点后的链表的长度也要相应地缩短
三、实验过程及关键代码
1.设计并实现一个单链表类和结点类。
2.编写成员函数。
// 实现删除单链表中数据域值等于x的所有结点的操作，并返回被删除结点的个数public int removeAll(Object x) {
Node p = head.getNext();// 初始化,p指向首结点,j为计数器
Node q = head; // 用来记录p的前驱结点
int j = 0;// 用来记录被删除结点的个数
while (p != null) { // 从单链表中的首结点开始对整个链表遍历一次
if (p.getData().equals(x)) {
q.setNext(p.getNext());
++j;// 计数器的值增1
} else
q = p;
p = p.getNext();// 指向下一个元素
}
return j;// 返回被删除结点的个数
}
3.编写一个测试函数。建立一个单链表并调用该测试函数对该成员函数进行测试。import java.util.Scanner;
public class TestRemoveAll {
public static void main(String[] args) throws Exception { System.out.println("请创建一个单链表L");
System.out.println("请输入L中结点的个数：");
Scanner input = new Scanner(System.in);
int n = input.nextInt();
LinkList L = new LinkList(n,true);
System.out.println("请输入要删除的值x：");
Object x = input.next();
L.removeAll(x);
System.out.println("删除后还剩下"+L.length()+"个元素");
System.out.println("删除后的结果为：");
L.display();
input.close();
}
}
4.调试运行
四、典型实验数据、处理结果截屏
1.头结点的数据域为x
2.尾结点的数据域为x
3.多个结点的数据域为x（在1、2中已经同时测试了）
4.单链表中没有该结点
5.单链表中所有的元素均为x
五、心得体会：
这个算法是对整个链表进行遍历。当链表的规模增大时，操作次数也会随之增多。X在链表中出现的位置以及x出现的次数会影响操作的次数。可能的改进方法是先对链表进行排序，再遍历删除，当结点的数据域大于x时，方法结束。假设已经实现了某个排序算法：public void Sort( )（如果x较大，对链表进行从大
到小排序，如果x较小，对链表进行从小到大排序）将原算法改进如下（下划线加粗表示增加的语句）：// 实现删除单链表中数据域值等于x的所有结点的操作，并返回被删除结点的个数public int removeAll(Object x) {
Sort();// 对链表进行排序
Node p = head.getNext();// 初始化,p指向首结点,j为计数器
Node q = head; // 用来记录p的前驱结点
int j = 0;// 用来记录被删除结点的个数
while (p != null) { // 从单链表中的首结点开始对整个链表遍历一次
if (p.getData().equals(x)) {
q.setNext(p.getNext());
++j;// 计数器的值增1
} else
q = p;
if (((Comparable)p.getData()).compareTo(x)>0) break;
p = p.getNext();// 指向下一个元素
}
return j;// 返回被删除结点的个数
}
同时，如果估计x在链表中出现的次数很多，排序以后可以不必进行一个结点一个结点的删除，可以找到最后一个值域为x的结点后一次删除中间所有值域为x的结点。方法改进如下：
// 实现删除单链表中数据域值等于x的所有结点的操作，并返回被删除结点的个数
public int removeAll(Object x) {
sort();
Node p = head.getNext();// 初始化,p指向首结点,j为计数器
Node q = head; // 用来记录p的前驱结点
int j = 0;// 用来记录被删除结点的个数
while (p != null) { // 从单链表中的首结点开始对整个链表遍历一次
if (p.getData().equals(x)) {
++j;// 计数器的值增1
} else
q = p;
p = p.getNext();// 指向下一个元素
if (((Comparable)p.getData()).compareTo(x)>0)
{ q.setNext(p);break;}
}
return j;// 返回被删除结点的个数
}
通过输入已经排好序的序列（没有实现排序算法）对以上的两个函数分别进行了测试，均能运行出正确的结果。
第3章栈与队列
一、实验问题：
编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例如：abba和abdba均是回文序列。要求只使用栈来实现。
二、解决思路：
建立两个栈，一个栈存储读入的字符。将字符栈中的字符出栈，并与原字符串中的字符挨个进行比较，若直至栈为空也没有发现不想等的元素则说明该字符串为回文串。
函数的规格说明
public static boolean isPalindSeq(String str) throws Exception
判断一个字符序列是否为回文序列。
参数：String —一个String类的对象
前置条件：参数String不能为null
返回：如果该字符序列是回文串，返回true，反之返回false
抛出：IllegalArgumentException表明传入的String不合法
三、实验过程及关键代码
1.设计并实现一个堆栈类
2.编写判断字符串是否为回文串的函数
//判断字符序列是否为回文序列,若是则返回true值,否则返回false。
public static boolean isPalindSeq(String str) throws Exception {
SqStack S = new SqStack(str.length()+1);
int i = 0;
for (; i < str.length(); i++)
S.push(str.charAt(i));
for (i = 0; i < str.length(); i++) {
char c = ((Character) S.pop()).charValue();
if (c != str.charAt(i))
return false;
}
return true;
}
备注：如果要忽略大小写判断回文串只需将if语句改为
if(isPalindSeq(palindString.toLowerCase()))
3.编写测试函数
import java.util.Scanner;
public class TestIsPalindSeq {
public static void main(String[] args) throws Exception {
Scanner input = new Scanner(System.in);
System.out.println("Please enter into a palind string:");
String palindString = input.next();
if(isPalindSeq(palindString))
System.out.println("String "+palindString+" is a palind string");
else
System.out.println("String "+palindString+" is not a palind string");
input.close();
}
}
4.调试运行
四、典型实验数据、处理结果截屏
1.输入回文串123grirg321
2.输入非回文串wighfhahfaku32145fjayfr
五、心得体会：
这个算法利用栈后进先出的特性判断回文串，不过还有一种比较好的实现方法是：读入文本，将它同时放入一个栈和一个队列中，然后逐个字符地比对栈和队列，看它们是否产生了相同的字符串。程序如下：//判断字符序列是否为回文序列,若是则返回true值,否则返回false。
public static boolean isPalindSeq(String str) throws Exception {
SqStack S = new SqStack(str.length()+1);
LinkQueue Q= new LinkQueue();
int i = 0;
for (; i < str.length(); i++)
{ S.push(str.charAt(i));
Q.offer(str.charAt(i));}
while(!Q.isEmpty()){
if(Q.peek()!= S.pop()) return false;
Q.poll();
}
return true;
}
第4 章串与数组
一、实验问题：
编写基于SeqString类的成员函数count（），统计当前字符串中单词的个数
二、解决思路：
一个单词开始的标志是该单词首字母的前一个字母不是英文字母。故对字符串遍历，设计两个int变量begin和end，通过这两个变量的值判断单词是否开始，若开始，将单词数目加1.
成员函数的规格说明
public int count()
统计当前字符串中单词的个数。
前置条件：SeqString不能为null
返回：该字符串中单词的个数
抛出：NullPointerException表明该字符串不合法
注意：该字符串可能不含有单词
三、实验过程及关键代码
1.设计并实现SeqString类
2.编写该成员函数count()
public int count(){
int end,begin;//begin和end用来区分字符，1表示英文字母，0表示其他字符
end = begin =0;
int numbers=0;//用numbers记录单词个数
for(int i=0;i begin = end;//将end的值赋给begin，则begin的值表示前一个字符是英文字母还是其他字符if( this.charAt(i)>=65&&this.charAt(i)<=90 || this.charAt(i)>=97&&this.charAt(i)<=122 ) end = 1;//如果当前字符是英文字母，end设为1 else end = 0; //否则end设为0 if(begin == 0 && end == 1) {numbers++;continue;}//表示一个单词开始 } return numbers; } 3.编写一个测试函数 import java.util.Scanner; public class TestSeqString { public static void main(String[] args) { System.out.println("Please enter a string:"); Scanner input = new Scanner(System.in); SeqString s = new SeqString(input.nextLine()); System.out.println("These sentence have "+s.count()+" words in all"); input.close(); } } 4.调试运行 四、典型实验数据、处理结果截屏 1.不含单词的字符串（按空格键后回车） 2.字符串以空格开头 3.字符串只有一个单词 五、心得体会： 其实我觉得如果输入的字符串是一般的英文字符串（只包含英文字符和标点符号），这个问题比较简单的实现是使用Java中的正则表达式。 import java.util.Scanner; public class AddNumbersOfWord { public static void main(String[] args) { System.out.println("Please enter a string:"); Scanner input = new Scanner(System.in); String s=input.nextLine(); s = s.replaceAll("[ ]", ";");//用，替换字符串s中的所有空格 String[] tokens = s.split("[.,:;?!'-_]");//将字符串分隔为由标点符号分隔开的字符串数组 System.out.println("These sentence have "+tokens.length+" words in all"); input.close(); } } 以下是该方法的运行结果： 第5章树与二叉树 一、实验问题： 编写算法求一棵二叉树的根节点root到一个指定结点x之间的路径并输出 二、解决思路： 用递归对树的结点进行遍历，对到达的结点进行判断，用boolean值表示路径是否正确，递归回溯阶段用栈对路径的结点进行存储。（注意栈是主函数中传入方法中的参数，利用了Java中引用变量参数传递是址传递的特性，所以每一次对结点的存储都会影响到在主函数中建立的栈，因此主函数中栈的输出结果是路径） 函数的规格说明 public static boolean seek(BiTreeNode node,Object x,LinkStack stack) 求一棵二叉树的根节点root到一个指定结点x之间的路径并输出 参数：Node ——一个BiTreeNode类的对象，表示当前结点 X ——一个Object对象，表示要跟踪的结点 Stack ——一个LinkStack类的对象，存储路径的栈 前置条件：Node不为空 返回：boolean —如果该路径可以通向目标结点返回true，否则返回false。 后置条件：返回正确的路径 三、实验过程及关键代码 1.设计并实现BiTree、BiTreeNode类，为了调试程序方便编写一个BiTreeCreator类 2.编写函数 public static boolean seek(BiTreeNode node,Object x,LinkStack stack){ if(node!=null){ //对传入的参数进行判断，如果为空则不进入下一步 if(node.getData().equals(x)){stack.push(node.getData());return true;} //如果当前结点的值等于x则表明已经找到x，返回true并将当前结点的值入栈 else//否则查找当前结点的左孩子和右孩子 if(seek(node.getLchild(),x,stack)||seek(node.getRchild(),x,stack)) {stack.push(node.getData());return true;} } return false; } 3.在主函数中进行测试 public static void main(String[] args) { BiTree tree = BiTreeCreator.createBiTree(); LinkStack track = new LinkStack(); System.out.println("The tree has these nodes:"); tree.postRootTraverse(); System.out.println(); System.out.println("Please enter a node you want to trace:"); Scanner input = new Scanner(System.in); Object x = input.next(); if(seek(tree.getRoot(),x,track))track.display(); else System.out.println("The number you just entered is not contained"); input.close(); } 四、典型实验数据、处理结果截屏 原树的形态如下: M K L F H C J A G D I B E 1.输入不在树中的结点p 2.输入在树中的结点（M、B、E、D、A） 五、心得体会： 这个程序我调试了很久，最后发现是由于一个很小的错误，在 BiTreeCreator类的createBiTree()方法中，是这样初始化一棵树的： public class BiTreeCreator { //初始化一棵树，并返回其根结点 public BiTree createBiTree() { BiTreeNode A = new BiTreeNode('A'); BiTreeNode F = new BiTreeNode('F', null, A); （其余结点类似） BiTreeNode root = new BiTreeNode('M', K, L); return new BiTree(root); } } 通过例如BiTreeNode A = new BiTreeNode('A');这样的语句，结点的数据域里存储的值是char 类型：'A'，而主函数中用户是这样读取用户输入的： Scanner input = new Scanner(System.in); Object x = input.next(); 这样x对象里面存储的是String类型：“A”， 那么执行tree.getRoot.getData.equals(x)返回的结果永远是false（将x与其他结点的数据域比较也是一样的结果）所以当我把整个程序写好以后，怎么运行都运行不出结果，但是我没有马上想到这个问题，好几个小时都用来不停地修改测试seek方法。这个教训真的很惨痛，我觉得主要是自己调试能力方面的不足，归根结底还是写的程序不够多，所以平时一定要多上机实践。这个算法是自己想的，思考到实现到最后运行，最后看到正确的输出感觉很开心，特别有成就感，编程还是挺有意思的。 不过这个程序还有一个不足之处，就是如果树中存在两个结点或者多个结点有相同的值时，查找这个值只能返回一条路径，比如我把BiTreeNode E = new BiTreeNode('E');改为BiTreeNode E = new BiTreeNode('B');再查找B结果如下： 这个问题主要来源于seek函数中的一条if语句 if(seek(node.getLchild(),x,stack)||seek(node.getRchild(),x,stack)) {stack.push(node.getData());return true;} 因为java语言的特性，当seek(node.getLchild(),x,stack)返回true时候，它就不会进入||后面的seek(node.getRchild(),x,stack)，而且主函数只传递了一个栈，所以也只能记录一条路径。 所以，如果树中有多个相同结点时，上面编写的这个方法就不能用了，需要用其他的算法，不过很遗憾我目前还没有想出来。 第6章图 一、实验问题： 编写算法求距离顶点vi的最短路径长度为K的所有结点 二、解决思路： 用迪杰斯特拉算法，只输出距离顶点vi的最短路径长度为K的所有结点 三、实验过程及关键代码 1.实现VNode类、ArcNode类、GraphKind类、IGraph类、MGraph类、GenerateGraph类、ALGraph类、ShortestPath_DIJ类 2.修改ShortestPath_DIJ类（下划线加粗为改动部分） import java.util.Scanner; public class ShortestPath_DIJ { private boolean[][] P;// v0到其余顶点的最短路径, 若P[v][w]为true，则w是从v0到v当前求得最短路径上的顶点 private int[] D;// v0到其余顶点的带权长度 public int INFINITY = Integer.MAX_VALUE; // 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其权值D[v] public void DIJ(MGraph G, int v0,int k,LinkStack stack) { // 传入参数k为目标路径的长度，传入链队列stack用来记录路径为k的结点 int vexNum = G.getVexNum(); P = new boolean[vexNum][vexNum]; D = new int[vexNum]; boolean[] finish = new boolean[vexNum]; // finish[v]为true当且仅当v属于S,即已经求得从v0到v的最短路径 for (int v = 0; v < vexNum; v++) { finish[v] = false; D[v] = G.getArcs()[v0][v]; for (int w = 0; w < vexNum; w++) P[v][w] = false;// 设空路径 if (D[v] < INFINITY) { P[v][v0] = true; P[v][v] = true; } } D[v0] = 0;// 初始化，v0顶点属于S集 finish[v0] = true; int v = -1;int record = -1; // 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 for (int i = 1; i < vexNum; i++) {// 其余G.getVexNum-1个顶点int min = INFINITY;// 当前所知离v0顶点的最近距离 for (int w = 0; w < vexNum; w++) if (!finish[w]) if (D[w] < min) { v = w; min = D[w]; record = w; //用record记录min的w } if(min == k){stack.push("v"+record+" ");} finish[v] = true;// 离v0顶点最近的v加入S集 for (int w = 0; w < vexNum; w++){ // 更新当前最短路径及距离 if(min==k)break; // 如果路径的长度已经达到k，跳出循环 if (!finish[w] && G.getArcs()[v][w] < INFINITY && (min + G.getArcs()[v][w] < D[w])) { // 修改D[w]和P[w],w属于V-S D[w] = min + G.getArcs()[v][w]; System.arraycopy(P[v], 0, P[w], 0, P[v].length); P[w][w] = true; } } } } public int[] getD() { return D; } public boolean[][] getP() { return P; }// 主函数有修改 public static void main(String[] args) throws Exception { MGraph G = GenerateGraph.generateMGraph(); ShortestPath_DIJ dij = new ShortestPath_DIJ(); Scanner input = new Scanner(System.in); System.out.println("Please input the start point vi:"); int i= input.nextInt(); System.out.println("Please input the length of path:"); int k = input.nextInt(); System.out.println("距离顶点v"+i+"的最短路径长度为K的所有结点:"); if(k==0)System.out.println("v"+i); else{ LinkStack stack=new LinkStack(); dij.DIJ(G, i,k,stack); if(!stack.isEmpty())stack.display(); else System.out.println("The path doesn't exist"); } } } 3.调试 四、典型实验数据、处理结果截屏 原ShortestPath_DIJ算法原运行结果如下 该图的结构如下图所示： V1 7 3 V4 6 V0 1 V2 7 4 7 V5 5 2 V3 修改后的算法运行结果如下： 1.以v0为开始结点：（分别测试长度为0、5、9—不存在） 1.以v0为开始结点：（分别测试长度为0、6、3—不存在） 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院：计算机与信息学院班级： 学号：姓名： 日期：程序名： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。 调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到， 则显示“找不到”。 调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）： 顺序表： 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 数据结构实验报告全集 实验一线性表基本操作和简单程序 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）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3 实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图： head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。 实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位 xxx 实验报告 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i 个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 1)程序1的主要代码(附简要注释) #include 部分的时间都用在了编程上，主要是因为C语言掌握的问题，C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练，导致在编程过程中还要不断的拿着c语言的教材查找，所以今后还要对C语言多练习，多动手，多思考。 2.数据结构有很强的逻辑性，因此我认为如果在上机之前先把逻辑搞清楚很重要，不管是对算法的设计还是对程序的调试都有很大帮助。 3.经过一次上机实践，我认为实践课很重要，上理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的。 所以我在做试验的时候特别费劲，特别吃力，这也是事出有因的。通过自我反省，总结不足之处后，我还是脚踏实地去查找资料，包括请教老师，上网搜索数据库线性表操作的优秀代码，经过不断的验证，修改和深入的研究，最终使得自己的程序得以运行，实现了实验的最终目的和要求。 也许每次实验都是有个过程的，虽然过程比较繁琐和艰难，但是我觉得只要认真的分析实验内容，积极搜索实验所需材料，再多多请教老师和同学，那么实验就不会困难重重。 自己要学习的地方太多，以后更要努力学习数据结构。 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 学期：2010-2011学年第一学期指导教师：杨华莉成绩： 实验一顺序表的基本操作 一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。 二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。 三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果 一．示例程序运行结果及说明 二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L; 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next; 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include 数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G); 南京工程学院实验报告 操作的函数程序清单，分别用顺序表和链表结构完成，并在首页上表明团队名称、成员及个人的工作（函数），未来的成绩评定时将包含这一部分的团队成绩及个人的工作成绩。 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用（main函数程序清单） 程序1的主要代码(附简要注释) #include "stdio.h" #include "malloc.h" #define SUCCESS 1 #define FAILURE 0 #define null 0 #define maxsize 100 typedef int datatype; typedef struct /*定义线性表（顺序结构）数据类型*/ { datatype data[maxsize]; int last; }sequenlist; int n; /*定义功能选择菜单函数*/ void print() { printf("----线性表（顺序结构）的基本操作----\n"); printf("----------开始----------\n"); } /*打印线性表（顺序结构）*/数据结构实验报告格式
数据结构实验一顺序表问题及实验报告模板 - Copy
(完整版)数据结构实验报告全集
数据结构实验报告
数据结构实验报告完整
数据结构实验报告-答案
《数据结构》实验报告1
数据结构实验报告模板
数据结构实验报告模板(验证型)
数据结构实验报告图实验
数据结构实验一 实验报告
数据结构实验报告七查找、
数据结构实验报告及心得体会
数据结构实验一 实验报告
数据结构实验报告--图实验
《数据结构实验》实验题目及实验报告模板
数据结构实验报告
《数据结构》实验1实验报告