数据结构课程设计——综合查找算法的实现.

目录

目录 (2)

一、问题描述 (3)

二、问题分析 (4)

三、数据结构描述 (4)

四、算法设计 (5)

1、流程图 (5)

2、具体算法 (5)

五、详细程序清单 (8)

六、程序运行结果 (19)

一、问题描述

1、顺序表查找的问题描述

顺序查找又称为线性查找，它是一种最简单、最基本的查找方法。从顺序表的一端开始，依次将每一个数据元素的关键字值与给定Key进行比较，若某个数据元素的关键字值等于给定值Key，则表明查找成功；若直到所有的数据元素都比较完毕，仍找不到关键字值为Key 的数据元素，则表明查找失败。

2、有序表的查找问题描述

折半查找也称为二分查找，作为二分查找对象的数据必须是顺序存储的有序表，通常假定有序表是按关键字值从小到大排列有序，即若关键字值为数值，则按数值有序；若关键字值是字符数据，则按对应的Unicode码有序。二分查找的基本思想：首先取整个有序表的中间记录的关键字值与给定值相比较，若相等，则查找成功；否则以位于中间位置的数据元素为分界点，将查找表分为左右两个子表，并判断待查找的关键字值Key是在左子表还是在右子表，再在子表中重复上述步骤，直到待查找的关键字值Key的记录或子表长度为0。

3、哈希表查找的问题描述

在哈希表上进行查找的过程是要给定要查找的关键字的值，根据构造哈希表时设定的哈希函数求得哈希地址，若此哈希地址上为空，即没有数据元素，则查找不成功；否则比较关键字，若相等，则查找成功；若不相等，则根据构造哈希表时设置的处理冲突的方法找下一个地址，知道某个位置上为空或者关键字比较相等为止。

哈希表是在关键字和存储位置之间直接建立了映像，但由于冲突的产生，哈希表的查找过程仍然是一个和关键字比较的过程。因此，仍需用平均查找长度来衡量哈希表的查找效率。查找过程中与关键字比较的次数取决于构造哈希表是选择的哈希函数和处理冲突的方法。哈希函数的“好坏”首先影响出现冲突的频率，假设哈希函数是均匀的，即它对同样一组随机的关键字出现冲突的可能性是相同的。因此哈希表的查找效率主要取决于构造哈希表时处理冲突的方法。

4、二叉排序树的查找问题描述

在顺序表的3种查找方法中，二分查找具有最高的效率，但是由于二分查找要求表中记录按关键字有序，且不能用链表做存储结构，因此当表的插入、删除操作非常频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。这里讨论的不仅是二叉排序树具有二分查找的效率，同时又便于在查找表中进行记录的增加和删除操作。

5、界面设计模块问题描述

设计一个菜单模式界面，让用户可以选择要查找的方式，界面上还有退出按钮，可以退出程序。界面要求简洁明了，便于使用。

6、按钮动作命令模块问题描述

在设计好图形界面后，就必须对相应的按钮进行事件驱动程序设计。运行Java图形用户界面程序时，程序与用户交互，比如说，在框架中显示多个按钮，当点击按钮时，就会从按钮触发一个事件。同时，查找的操作必须要有输入和输出，则需要使用对话框和命令窗口进行输入关键字和输出结果。

二、问题分析

按钮时事件的源。图形界面中一共有5个按钮，先注册按钮，再创建监听器对象，当按钮上有行为要发生时，按钮通过监听器的actionPerformed方法通知监听器。点击按钮会使监听器中actionPerformed方法被调用。

首先，点击一个按钮，从e.getActionCommand()方法从按钮返回行为命令，按钮的行为命令就是按钮的文本。调用各查找方法，之后输出查找结果。

拿“顺序表的查找”按钮来说，点击之后，如果按钮的行为命令是"顺序表的查找"，则按顺序表的特点先建立一个存储结构为20的顺序表，利用JOptionPane.showInputDialog 弹出输入对话框，让用户输入表长，定义一个整形变量强制转化获取到字符串型的输入。

然后利用java.util.Scanner类从控制台读关键字的序列，存放在记录顺序表中。

利用对话框输入待查找的关键字，强制转化成KeyType型。

最后，调用顺序查找的seqSearch方法，利用JOptionPane.showMessageDialog输出运行查找结果。

三、数据结构描述

public void actionPerformed(ActionEvent e) {

String command = e.getActionCommand();

........

//顺序表的查找

if (command.equals("顺序表的查找")) {

.........

}

//有序表的动作实现

if (command.equals("有序表的查找")) {

.............

}

//二叉排序树的动作实现

if (command.equals("二叉排序树的查找")) {

..........

}

//哈希表开放地址法的查找

if (command.equals("哈希表开放地址法的查找")) {

...........

}

//退出

if (command.equals("退出"))

System.exit(0);

}

四、算法设计

我负责的是按钮动作的实现。

1、流程图

2、具体算法

if (command.equals("顺序表的查找")) {

System.out .println("创建顺序查找表");

ST=new SeqList(20);

Scanner sc1=new Scanner(System.in );

String tmp1 = JOptionPane.showInputDialog (this , "请输入查找表的表长:"); int n =Integer.parseInt (tmp1);

开始 选择按钮 顺序表 的查找 输入 关键字序列 输入待查关键字

输出查找结果 输入待查关键字 输入结点个数 输入 关键字序列 输入 待查 关键字 输入 关键字序列 哈希表开放地址法的查找 输入 关键字个数 输入 关键字序列 输出创建哈希表 输入待查关键字 输出查找结果 退出 退 出 程 序

输

入

表

长

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

k[i] = new KeyType(sc1.nextInt());

}

for(int i=1;i

RecordNode r = new RecordNode(k[i-1]);

try {

ST.insert(i, r);

} catch (Exception e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

}

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

key1=new KeyType(n1);

JOptionPane.showMessageDialog(null,"seqSearch(" + key1.getKey() + ")=" + ST.seqSearch(key1));

}

//有序表的动作实现

if (command.equals("有序表的查找")) {

ST=new SeqList(20);

Scanner sc1=new Scanner(System.in);

String tmp1 = JOptionPane.showInputDialog(this, "请输入查找表的表长:");

int n =Integer.parseInt(tmp1);

KeyType[] k= new KeyType[n];

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

k[i] = new KeyType(sc1.nextInt());

}

for(int i=1;i

RecordNode r = new RecordNode(k[i-1]);

try {

ST.insert(i, r);

} catch (Exception e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

}

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

JOptionPane.showMessageDialog(null,"binarySearch(" + key2.getKey() + ")=" + ST.binarySearch(key2));

}

//二叉排序树的动作实现

if (command.equals("二叉排序树的查找")) {

BSTree bstree = new BSTree();

Scanner sc1=new Scanner(System.in);

String tmp1 = JOptionPane.showInputDialog("请请输入二叉排序树的结点个数:");

int n =Integer.parseInt(tmp1);

System.out.print("请输入结点的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

bstree.insertBST(sc1.nextInt()) ;

}

System.out.println("\n创建的二叉排序树的中序遍历序列为：");

bstree.inOrderTraverse(bstree.getRoot());

System.out.println();

String tmp2 = JOptionPane.showInputDialog("请输入关键字");

int key3=Integer.parseInt(tmp2);;

BiTreeNode found = bstree.searchBST(key3);

if (found != null) {

JOptionPane.showMessageDialog(null,"查找成功!");

}

else {

JOptionPane.showMessageDialog(null,"查找失败!");

}

}

//哈希表开放地址法的查找

if (command.equals("哈希表开放地址法的查找")) {

HashTable T=null;

//建立待查找的哈希表

T=new HashTable(20);

Scanner sc1=new Scanner(System.in);

System.out.print("请输入关键字的个数:");

int n=sc1.nextInt();

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列,并插入哈希表中

T.hashInsert(sc1.nextInt());

}

System.out.println("创建的哈希表为:");

T.Hashdisplay();

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

RecordNode p=T.hashSearch(n1);

if ((p.getKey()).compareTo(n1)==0)

JOptionPane.showMessageDialog(null,"查找成功!");

else

JOptionPane.showMessageDialog(null,"查找失败!");

}

//退出

if (command.equals("退出"))

System.exit(0);

}

五、详细程序清单

package package1;

import java.util.Scanner;

import java.awt.BorderLayout;

import java.awt.GridLayout;

import java.awt.event.ActionEvent;

import java.awt.event.ActionListener;

import javax.swing.ImageIcon;

import javax.swing.JButton;

import javax.swing.JFrame;

import javax.swing.JLabel;

import javax.swing.JOptionPane;

import javax.swing.JPanel;

public class Search extends JFrame implements ActionListener{

private ImageIcon usIcon = new ImageIcon("src/usIcon.jpg");

private JButton btnSeq = new JButton("顺序表的查找");

private JButton btnBinary = new JButton("有序表的查找");

private JButton btnHash1 = new JButton("哈希表开放地址法的查找");

private JButton btnBST = new JButton("二叉排序树的查找");

private JButton btnQuit = new JButton("退出");

public Search() {

load();

}

public void load() {

JPanel jp1 =new JPanel();

JPanel jp2 =new JPanel(new BorderLayout());

GridLayout grid = new GridLayout(2,2);

jp1.add(btnSeq);

jp1.add(btnBinary);

jp1.add(btnHash1);

jp1.add(btnBST);

jp2.add(jp1,BorderLayout.NORTH);

jp2.add(btnQuit);

jp1.setLayout(grid);

this.add(new JLabel(usIcon),BorderLayout.NORTH);

this.add(jp2,BorderLayout.SOUTH);

this.setTitle("查找");

this.setSize(550,500);

this.setVisible(true);

this.setResizable(false);

this.setDefaultCloseOperation(EXIT_ON_CLOSE);

this.btnSeq.setActionCommand("顺序表的查找");

this.btnBinary.setActionCommand("有序表的查找");

this.btnHash1.setActionCommand("哈希表开放地址法的查找");

this.btnBST.setActionCommand("二叉排序树的查找");

this.btnQuit.setActionCommand("退出");

btnSeq.addActionListener(this);

btnBinary.addActionListener(this);

btnHash1.addActionListener(this);

btnBST.addActionListener(this);

btnQuit.addActionListener(this);

}

class RecordNode {//记录结点类

private Comparable key; //关键字

private Object element; //数据元素

public Object getElement() {

return element;

}

public void setElement(Object element) {

this.element = element;

}

public Comparable getKey() {

return key;

}

public void setKey(Comparable key) {

this.key = key;

}

public RecordNode(Comparable key) { //构造方法1

this.key = key;

}

public RecordNode(Comparable key, Object element) { //构造方法2

this.key = key;

this.element = element;

}

public String toString() { //覆盖toString()方法

return "[" + key + "," + element + "]";

}

}

class KeyType implements Comparable { //记录关键字类

private int key; //关键字

public KeyType() {

}

public KeyType(int key) {

this.key = key;

}

public int getKey() {

return key;

}

public void setKey(int key) {

this.key = key;

}

public int compareTo(KeyType another) { //覆盖Comparable接口中比较关键字大小的方法

int thisVal = this.key;

int anotherVal = another.key;

return (thisVal < anotherVal ? -1 : (thisVal == anotherVal ? 0 : 1));

}

}

class SeqList {//顺序查找表类

private RecordNode[] r; //顺序表记录结点数组

private int curlen; //顺序表长度,即记录个数

// 顺序表的构造方法：构造一个存储空间容量为maxSize的顺序表

public SeqList(int maxSize) {

this.r = new RecordNode[maxSize]; // 为顺序表分配maxSize个存储单元

this.curlen = 0; // 置顺序表的当前长度为0

}

// 求顺序表中的数据元素个数并由函数返回其值

public int length() {

return curlen; // 返回顺序表的当前长度

}

public int getCurlen() {

return curlen;

}

public void setCurlen(int curlen) {

this.curlen = curlen;

}

/* 在当前顺序表的第i个结点之前插入一个RecordNode类型的结点x，其中i取值范围为：0≤i≤curlen。如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x, 当i=curlen时表示在表尾插入一个数据元素x */

public void insert(int i, RecordNode x) throws Exception {

if (curlen == r.length-1) { // 判断顺序表是否已满,0号存储单元不存放元素throw new Exception("顺序表已满");

}

if (i < 0 || i > curlen+1) { // i小于0或者大于表长

throw new Exception("插入位置不合理");

}

for (int j = curlen; j > i; j--) {

r[j+1] = r[j ]; // 插入位置及之后的元素后移

}

r[i] = x; // 插入x

this.curlen++; // 表长度增1

}

/*顺序查找：从顺序表r[1]到r[n]的n个元素中顺序查找出关键字为key的记录，若查找成功返回其下标，否则返回-1*/

public int seqSearch(Comparable key) {

int i = 1, n = length();

while (i < n+1 && r[i].getKey().compareTo(key) != 0) {

i++;

}

if (i < n+1) { //查找成功则返回该元素的下标i，否则返回-1

return i;

} else {

return -1;

}

}

/*二分查找：数组元素已按升序排列，从顺序表r[1]到r[n]的n个元素中查找出关键字为key的元素，若查找成功返回元素下标，否则返回-1 */

public int binarySearch(Comparable key) {

if (length() > 0) {

int low = 1, high = length() ; //查找范围的下界和上界

while (low <= high) {

int mid = (low + high) / 2; //中间位置，当前比较元素位置

// System.out.print(r[mid].getKey() + "? ");

if (r[mid].getKey().compareTo(key) == 0) {

return mid; //查找成功

} else if (r[mid].getKey().compareTo(key) > 0) { //给定值更小

high = mid - 1; //查找范围缩小到前半段

} else {

low = mid + 1; //查找范围缩小到后半段

}

}

}

return -1; //查找不成功

}

}

//二叉树的二叉链表的结点类

class BiTreeNode {

private int key;// 结点的关键字

private BiTreeNode lchild, rchild; // 左右孩子

public BiTreeNode(int key) {// 构造一棵左右孩子为空的结点

this(key, null, null);

}

public BiTreeNode(int key, BiTreeNode lchild, BiTreeNode rchild) {// 构造一棵数据元素和左右孩子都不为空的结点

this.key = key;

this.lchild = lchild;

this.rchild = rchild;

}

public int getKey() {

return key;

}

public BiTreeNode getLchild() {

return lchild;

}

public BiTreeNode getRchild() {

return rchild;

}

public void setKey(int key) {

this.key = key;

}

public void setLchild(BiTreeNode lchild) {

this.lchild = lchild;

}

public void setRchild(BiTreeNode rchild) {

this.rchild = rchild;

}

}

class BSTree { //二叉排序树类

protected BiTreeNode root; //根结点

public BSTree() { //构造空二叉排序树

root = null;

}

public BSTree(BiTreeNode root) { //构造根结点为root的二叉排序树

this.root = root;

}

public BiTreeNode getRoot() {

return root;

}

public void setRoot(BiTreeNode root) {

this.root = root;

}

public void inOrderTraverse(BiTreeNode T) { //中根次序遍历以T结点为根的二叉树if (T!= null) {

inOrderTraverse(T.getLchild());

System.out.print(T.getKey() + " ");

inOrderTraverse(T.getRchild());

}

}

//查找关键字值为key的结点,若查找成功返回该结点，否则返回null

public BiTreeNode searchBST(int key) {

return searchBST(root, key);

}

//二叉排序树查找的递归算法

private BiTreeNode searchBST(BiTreeNode p, int key) {

if (p != null) {

if (key==p.getKey()) //查找成功

{

return p;

}

// System.out.print(((RecordNode) p.getData()).getKey() + "? ");

if (key< p.getKey()) {

return searchBST(p.getLchild(), key); //在左子树中查找

} else {

return searchBST(p.getRchild(), key); //在右子树中查找

}

}

return null;

}

//在二叉排序树中插入关键字为Keyt的结点,若插入成功返回true,否则返回false public boolean insertBST(int key) {

if (root == null) {

root = new BiTreeNode(key); //建立根结点

return true;

}

return insertBST(root, key);

}

//将关键字为keyt的结点插入到以p为根的二叉排序树中的递归算法

private boolean insertBST(BiTreeNode p, int key) {

if (key==p.getKey()) {

return false; //不插入关键字重复的结点

}

if (key

if (p.getLchild() == null) { //若p的左子树为空

p.setLchild(new BiTreeNode(key)); //建立叶子结点作为p的左孩子

return true;

} else { //若p的左子树非空

return insertBST(p.getLchild(), key); //插入到p的左子树中}

} else if (p.getRchild() == null) { //若p的右子树为空

p.setRchild(new BiTreeNode(key)); //建立叶子结点作为p的右孩子

return true;

} else { //若p的右子树非空

return insertBST(p.getRchild(), key); //插入到p的右子树中}

}

}

//采用开放地址法的哈希表类

class HashTable{

private RecordNode[] table; //哈希表的对象数组

public HashTable(int size) { //构造指定大小的哈希表this.table=new RecordNode[size];

for(int i=0;i

table[i]=new RecordNode(0);

}

}

public int hash(int key) { //除留余法数哈希函数return key % 19;

}

//开放地址哈希表的查找

public RecordNode hashSearch(int key ){

int i=hash(key); //求哈希地址

int j=0;

while((table[i].getKey().compareTo(0)!=0) && (table[i].getKey().compareTo(key)!=0) && (j< table.length)){

//该位置中不为空并且关键字与key不相等

j++;

i=(i+j)%20; //用线性探测再散列法求得下一探测地址

} //i指示查找到的记录在表中的存储位置或指示插入位置

if (j>=table.length) { //如果表已经为满

System.out.println("哈希表已满");

return null;

}

else return table[i];

}

//开放地址哈希表的插入

public void hashInsert( int key){

RecordNode p=hashSearch(key);

if (p.getKey().compareTo(0)==0)

p.setKey(key); //插入

else

System.out.println(" 此关键字记录已存在或哈希表已满");

}

//哈希表的输出

void Hashdisplay() {

for(int i=0;i

System.out.print(table[i].getKey().toString()+" ");

System.out.println();

}

}

public static void main(String [] args) {

Search search= new Search();

}

public void actionPerformed(ActionEvent e) {

String command = e.getActionCommand();

SeqList ST = null;

Scanner sc=new Scanner(System.in);

KeyType key1,key2,key4;

if (command.equals("顺序表的查找")) {

System.out.println("创建顺序查找表");

ST=new SeqList(20);

Scanner sc1=new Scanner(System.in);

String tmp1 = JOptionPane.showInputDialog(this, "请输入查找表的表长:");

int n =Integer.parseInt(tmp1);

KeyType[] k= new KeyType[n];

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

k[i] = new KeyType(sc1.nextInt());

}

for(int i=1;i

RecordNode r = new RecordNode(k[i-1]);

try {

ST.insert(i, r);

} catch (Exception e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

}

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

key1=new KeyType(n1);

JOptionPane.showMessageDialog(null,"seqSearch(" + key1.getKey() + ")=" + ST.seqSearch(key1));

}

//有序表的动作实现

if (command.equals("有序表的查找")) {

ST=new SeqList(20);

Scanner sc1=new Scanner(System.in);

String tmp1 = JOptionPane.showInputDialog(this, "请输入查找表的表长:");

int n =Integer.parseInt(tmp1);

KeyType[] k= new KeyType[n];

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

k[i] = new KeyType(sc1.nextInt());

}

for(int i=1;i

RecordNode r = new RecordNode(k[i-1]);

try {

ST.insert(i, r);

} catch (Exception e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

}

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

key2=new KeyType(n1);

JOptionPane.showMessageDialog(null,"binarySearch(" + key2.getKey() + ")=" + ST.binarySearch(key2));

}

//二叉排序树的动作实现

if (command.equals("二叉排序树的查找")) {

BSTree bstree = new BSTree();

Scanner sc1=new Scanner(System.in);

String tmp1 = JOptionPane.showInputDialog("请请输入二叉排序树的结点个数:");

int n =Integer.parseInt(tmp1);

System.out.print("请输入结点的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列

bstree.insertBST(sc1.nextInt()) ;

}

System.out.println("\n创建的二叉排序树的中序遍历序列为：");

bstree.inOrderTraverse(bstree.getRoot());

System.out.println();

String tmp2 = JOptionPane.showInputDialog("请输入关键字");

int key3=Integer.parseInt(tmp2);;

BiTreeNode found = bstree.searchBST(key3);

if (found != null) {

JOptionPane.showMessageDialog(null,"查找成功!");

}

else {

JOptionPane.showMessageDialog(null,"查找失败!");

}

}

//哈希表开放地址法的查找

if (command.equals("哈希表开放地址法的查找")) {

HashTable T=null;

//建立待查找的哈希表

T=new HashTable(20);

Scanner sc1=new Scanner(System.in);

System.out.print("请输入关键字的个数:");

int n=sc1.nextInt();

System.out.print("请输入查找表中的关键字序列:");

for (int i = 0; i < n; i++) { //输入关键字序列,并插入哈希表中

T.hashInsert(sc1.nextInt());

}

System.out.println("创建的哈希表为:");

T.Hashdisplay();

String tmp2 = JOptionPane.showInputDialog(this,"请输入待查找的关键字:");

int n1 =Integer.parseInt(tmp2);

RecordNode p=T.hashSearch(n1);

if ((p.getKey()).compareTo(n1)==0)

JOptionPane.showMessageDialog(null,"查找成功!");

else

JOptionPane.showMessageDialog(null,"查找失败!");

}

//退出

if (command.equals("退出"))

System.exit(0);

}

}

六、程序运行结果

顺序表查找运行结果：

有序表查找结果：

哈希表查找的运行结果：

二叉排序树查找运行结果：

对分查找算法及程序实现

对分查找算法及程序实现 一、设计思想 对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。 二、教材分析 本课的课程标准内容： （一）计算机解决问题的基本过程（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。 （三）算法与问题解决例举 C 查找、排序与问题解决 （2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。 本课的《学科教学指导意见》内容： 基本要求：1.初步掌握对分查找算法。 2.初步掌握对分查找算法的程序实现。 教材内容：第二章算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算

法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。 从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。 三、学情分析 学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。 四、教学目标 知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。 过程与方法：通过分析多种不同的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤。 情感态度与价值观：通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。 五、重点难点 教学重点和难点：分解并理解对分查找的过程。 六、教学策略与手段 1、教学线索：游戏引领---提出对分查找原理--- 解析对分查找的算法特征---实践解决问题。

数据结构课程设计报告模板

《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月

三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。

目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6)

一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

数据结构课程设计报告模板

课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日

任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明

摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计

数据结构课程设计

1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出；

实验6：至少三种排序算法的程序实现

《数据结构与算法》课程实验报告（6） 实验题目：实验6：至少三种排序算法的程序实现 一、实验目的 1．掌握简单插入排序、希尔排序、冒泡排序、快速排序、堆排序以及归并排序的算法并加以应用。 2．对各种查找、排序技术的时间、空间复杂性有进一步认识。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 编写程序实现下述六种算法至少三种，并用以下无序序列加以验证：49，38，65，97，76，13，27，49 1．简单插入排序 2．希尔排序 3. 冒泡排序 4．快速排序 5．归并排序 6．堆排序 四、源代码与结果： 1、简单插入排序： 源代码：

#include void InsertSort(int r[],int n); int main() { int r[]={49,38,65,97,76,13,27,49}; cout<<"直接插入排序:"<=0;j--) { r[j+1]=r[j]; } r[j+1]=s; } } 运行结果： 2．希尔排序： #include void ShellSort(int r[],int n); int main() { int r[]={49,38,65,97,76,13,27,49}; cout<<"希尔排序:"<

数据结构课程设计题目2010

一、数据结构课程设计要求 1.学生必须仔细阅读《数据结构》课程设计方案，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 3.课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上2小时的上机来调试C 或C++语言设计的程序，总共至少要上机调试程序20小时。属教师安排上机时间学生不得缺席。 二、数据结构课程设计题目 1. 运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分， 3) 可以按学校编号或名称、学校总分、男女团体总分排序输出； 4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 飞机订票系统（限1 人完成） 任务：通过此系统可以实现如下功能： 录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）

数据结构课程设计(附代码)-数据结构设计说明

应用技术学院课程设计报告 课程名称《数据结构课程设计》 设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级 学号指导教师日期 一.目的与要求 1. 巩固和加深对常见数据结构的理解和掌握 2. 掌握基于数据结构进行算法设计的基本方法 3. 掌握用高级语言实现算法的基本技能 4. 掌握书写程序设计说明文档的能力 5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力 二.课程设计容说明 1. 项目一 (1) 对设计任务容的概述 学生成绩管理** 任务：要现对学生资料的录入、浏览、插入和删除等功能。 输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。 (2) 详细设计 LinkList *create()：输入学生成绩记录函数； void print(LinkList *head)：显示全部记录函数 LinkList *Delete(LinkList *head)：删除记录函数 LinkList *Insert(LinkList *head)：插入记录函数 void menu_select()：菜单选择 void ScoreManage()：函数界面 (3) 程序流程图

(4) 程序模块及其接口描述 该程序可以分为以下几个模块： 1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。 2、输入功能：LinkList *create(); 通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链

数据结构课程设计

题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日

目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9)

一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个

编程实现排序算法

学号：044120108 中国地质大学长城学院 实践课程设计 题目编程实现排序算法 学院中国地质大学长城学院 专业电子信息工程 班级电子1201 姓名李月朋 指导教师李润亚 2014 年12 月31 日

一、实验目的 ⑴掌握排序的基本概念⑵熟悉排序中使用的存储结构，掌握多种排序算法，如堆排序、希尔排序、快速排序算法等。 二、实验要求 ⑴几种典型的排序算法⑵计算不同的排序算法的时间复杂性⑶判定某种排序算法是否稳定的标准。 三、实验方法内容 1. 主要内容 本课程设计一共设计到五种排序算法。这五种算法共包括：直接插入排序法，Shell希尔排序法，直接选择排序法，冒泡排序法，快速排序法等。 2. 算法设计及算法流程 （一）、直接插入排序的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一次比较前两个数，然后把第二个数按大小插入到有序表中；第二次把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，时间复杂性为O(n^2)，空间复杂度为O(1)。直接插入排序是由两层嵌套循环组成的，外层循环标识并决定待比较的数值，内层循环为待比较数值确定其最终位置。将待比较的数值与它的前一个数值进行比较，即外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束本次循环。需用一个存储空间来保存当前待比较的数值。每一步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。 （二）、Shell排序法：先取一个小于n的整数d1作为第一个增量，把全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

查找算法

实验四查找算法的设计 一、实验目的 （1）理解静态查找和动态查找； （2）掌握顺序查找和二分查找的算法； （3）掌握二叉查找树的基本运算。 二、实验内容 （1）实现顺序查找的算法； （2）实现二分查找的算法； （3）实现二叉查找树的基本运算算法。 三、算法思想与算法描述 1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while(i=n) return -1; else { printf("%d",R[i].key); return i; } } 2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下： int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\n ",++count,low,high,mid,R[mid].key); if(R[mid].key==k)

return mid; if(R[mid].key>k) high=mid-1; else low=mid+1; } return -1; } 四、实验步骤与算法实现 #include #define MAXL 100 typedef int KeyType; typedef char InforType[10]; typedef struct { KeyType key; InforType data; }NodeType; typedef NodeType SeqList[MAXL]; int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while(i=n) return -1; else { printf("%d",R[i].key); return i; } } int BinSearch(SeqList R,int n,KeyType k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\n ",++count,low,high,mid,R[mid].key);

数据结构课程设计报告范例

Guangxi University of Science and Technology 课程设计报告 课程名称：算法与编程综合实习 课题名称： 姓名： 学号： 院系：计算机学院 专业班级：通信121 指导教师： 完成日期：2012年12月15日

目录 第1部分课程设计报告 (3) 第1章课程设计目的 (3) 第2章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 设计要求 (4) 第3章课程设计总体方案及分析 (4) 3.1 问题分析 (4) 3.2 概要设计 (7) 3.3 详细设计 (7) 3.4 调试分析 (10) 3.5 测试结果 (10) 3.6 参考文献 (12) 第2部分课程设计总结 (13) 附录(源代码) (14)

第1部分课程设计报告 第1章课程设计目的 仅仅认识到队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方………………………………………………………………………………………………………………………………………………………………………………………..(省略)

第2章课程设计内容和要求 2.1问题描述： 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的结论。 图A 2.2设计要求： 要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。

十 大 经 典 排 序 算 法 总 结 超 详 细

数据挖掘十大经典算法，你都知道哪些？ 当前时代大数据炙手可热，数据挖掘也是人人有所耳闻，但是关于数据挖掘更具体的算法，外行人了解的就少之甚少了。 数据挖掘主要分为分类算法，聚类算法和关联规则三大类，这三类基本上涵盖了目前商业市场对算法的所有需求。而这三类里又包含许多经典算法。而今天，小编就给大家介绍下数据挖掘中最经典的十大算法，希望它对你有所帮助。 一、分类决策树算法C4.5 C4.5，是机器学习算法中的一种分类决策树算法，它是决策树(决策树，就是做决策的节点间的组织方式像一棵倒栽树)核心算法ID3的改进算法，C4.5相比于ID3改进的地方有： 1、用信息增益率选择属性 ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（shang），一种不纯度度量准则，也就是熵的变化值，而 C4.5用的是信息增益率。区别就在于一个是信息增益，一个是信息增益率。 2、在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致过拟。 3、能对非离散数据和不完整数据进行处理。 该算法适用于临床决策、生产制造、文档分析、生物信息学、空间数据建模等领域。 二、K平均算法

K平均算法（k-means algorithm）是一个聚类算法，把n个分类对象根据它们的属性分为k类（kn）。它与处理混合正态分布的最大期望算法相似，因为他们都试图找到数据中的自然聚类中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。 从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。 k-Means 算法常用于图片分割、归类商品和分析客户。 三、支持向量机算法 支持向量机(Support Vector Machine)算法，简记为SVM，是一种监督式学习的方法，广泛用于统计分类以及回归分析中。 SVM的主要思想可以概括为两点： (1)它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分； (2)它基于结构风险最小化理论之上，在特征空间中建构最优分割超平面，使得学习器得到全局最优化，并且在整个样本空间的期望风险以某个概率满足一定上界。 四、The Apriori algorithm Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是基于两阶段“频繁项集”思想的递推算法。其涉及到的关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支

数据结构课程设计报告范本

数据结构课程设计 报告

数据结构课程设计报告 压缩软件 一·问题描述 利用哈夫曼编码设计一个压缩软件，能对任何类型的文件进行哈夫曼编码，产生编码后的文件——压缩文件;也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。 二·基本要求 要求编码和译码的效率尽可能地高。 三·工具/准备工作 已学内容:哈夫曼树，哈夫曼树构造算法，哈夫曼编码，Huffman压缩算法。 需要的硬件设施与开发软件：一台计算机，并安装了Visual C++. 四·分析与实现 Huffman树中，叶子结点包含字符以及对应的字符频度（权值） struct HTNode{ //压缩用Huffman树结点 unsigned long weight; //字符频度（权值） unsigned int parent,lchild,rchild; };

使用哈夫曼编码能够对文件进行压缩，由于字符的哈夫曼编码以比特为单位，而当将哈夫曼编码以压缩文件进行存储时，压缩文件最少以字节为单位进行存储，因此需要定义字节缓冲器，以便自动将比特转换为字节，定义如下： struct Buffer{ //字节缓冲压缩用Huffman树 char ch; //字节 unsigned int bits; //实际比特数 }; 定义哈夫曼树的抽象基类模板，实现建树，压缩，解压等功能 class HuffmanTree{ //Huffman树 public: void Code(); //编码 void UnCode(); //译码 private: HTNode HT[m+1]; //树结点表(HT[1]到HT[m]) char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n]) char *HuffmanCode[n+1]; //叶结点对应

数据结构课程设计说明书讲解

安徽理工大学 数据结构 课程设计说明书题目: 一元多项式计算 院系：计算机科学与工程学院 专业班级：数字媒体13-1班 学号： 2013303102 学生姓名：钱福琛 指导教师：梁兴柱 2015年 1月 9 日

安徽理工大学课程设计（论文）任务书计算机科学与工程学院

2014年 11 月 10 日安徽理工大学课程设计（论文）成绩评定表

目录 1 问题描述 2 功能描述 2.1 课题要求........................................... 2.2 软件格式规定....................................... 3 设计 2 3.1 相关函数介绍说明................................... 3.2 主程序的流程基函数调用说明......................... 4 程序设计 4 4.1 多项式存储的实现................................... 4.2 加减乘除算法....................................... 4.2.1加法运算的实现............................... 4.2.2减法运算的实现............................... 4.2.3乘法运算的实现............................... 4.2.4除法运算的实现............................... 4.3 函数调用关系图..................................... 5 运行测试

数据结构课程设计内容

（一）课程设计要求 1.分组要求 每个人一个小组进行分组。 2.实训目的 （1）熟悉课程所学的内容，包括线性表、链表、串，栈，队列，树，图，查找和排序； （2）学生能够按照软件工程的规范要求，能够运用软件工程的基本概念、方法与过程来进行软件的设计与开发。 3.课程设计要求 （1）每组学生在以下项目中选择一项完成即可； （2）编写程序要严格按照程序编程规范进行代码编写; （2）必须按照个体软件的过程，真实地采集数据、填写相关的表格、编写有关的文档; （3）按照老师的要求，每个人必须独立完成; （4）按照实训的时间安排进行实训，实训结束后提交有关的表格与文档。（二）课程设计题目 1.线性表 （1）实验目的：利用顺序结构和链式结构实现线性表的基本运算。 （2）实验要求：对于顺序存储结构的线性表，验证其插入、删除操作；对以链式存储结构存储的线性表，验证其插入、删除、查找操作。 2.火车列车调度问题 （1）实验目的：利用顺序结构和链式结构实现栈和队列的基本运算 （2）实验要求：栈操作的验证火车调度；对于顺序队列、链队列的基本操作进行验证； 3.稀疏矩阵 （1）实验目的：利用三元组和十字链表实现稀疏矩阵的有关算法 （2）实验要求：以三元组作为存储结构实现稀疏矩阵的转置

4.二叉树 （1）实验目的：利用二叉链表实现二叉树的建立和遍历 （2）实验要求：以二叉链表作为存储结构建立二叉树；以二叉链表作为存储结构实现先序、中序和后序遍历二叉树 5.图的遍历和最短路径问题 （1）实验目的：在图的两种存储结构基础上实现图的遍历 （2）实验要求：采用连通无向图作为遍历对象对以邻接矩阵为存储结构的图实现深度优先搜索和广度搜索遍历；采用连通无向图作为遍历对象，建立邻接表时顶点对序号从大到小输入，对以邻接表为存储结构的图实现深度优先搜索和广度优先搜索遍历； 6.排序与查找 （1）实验目的：验证各排序与查找算法 （2）实验要求：编程实现排序与查找算法，包括直接插入排序、选择和起泡排序、折半查找 7.综合课程设计1 （1）实验目的：综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列； 8.综合课程设计2 （1）实验目的:综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：设计一个校园导游程序，为来访的客人提供各种信息查询

数据结构查找算法课程设计

存档编号： 西安******** 课程设计说明书 设计题目： 查找算法性能分析 系别：计算机学院 专业：计算机科学 班级：计科*** 姓名：王*** （共页） 2015年01月07 日

***** 计算机科学专业课程设计任务书 姓名：*** 班级：计科**** 学号：**** 指导教师：**** 发题日期：2015-01-05 完成日期：2015-01-09 一需求分析

1.1问题描述 查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对表做修改运算（插入或删除），则相应的表成为动态查找表，反之称为静态查找表。 由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（也叫平均查找长度）作为一个查找算法效率优劣的标准。 平均查找程度ASL定义为： ASL=∑PiCi（i从1到n） 其中Pi代表查找第i个元素的概率，一般认为每个元素的查找概率相等，Ci代表找到第i个元素所需要比较的次数。 查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找（又叫哈希查找），它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找则需要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。 1.2基本要求 （1）输入的形式和输入值的范围； 在设计查找算法性能分析的过程中，我们调用产生随机数函数： srand((int)time(0)); 产生N个随机数。 注：折半查找中需要对产生的随机数进行排序，需要进行排序后再进行输入，N<50; （2）输出形式； 查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找

数据结构课程设计报告

《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日

一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图

2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果）

二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList list用来存储课程信息。DrawInfo类是一个辅助画图的类，其中 包括成员变量num、name、shuxing、xuefen分别代表课程的编号、名称、属性、 学分。ArrayList是一个DrawInfo类型的数组，主要用来在ReadFile、DrawG、DrawC、SaveFile、Window这些类之间辅助参数传递，传递课程信息。 3.Class DrawInfo, 包括int num;String name;String shuxing;float xuefen;四个成员变量。 4.Class Edge包括int from;int to;double weight;三个成员变量。 5.Class Vertex包括int value一个成员变量。 主要程序的流程图： //ReadFile.java

数据结构课程设计(附代码)

上海应用技术学院课程设计报告 课程名称《数据结构课程设计》 设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级 姓名学号指导教师日期 一.目的与要求 1. 巩固和加深对常见数据结构的理解和掌握 2. 掌握基于数据结构进行算法设计的基本方法 3. 掌握用高级语言实现算法的基本技能 4. 掌握书写程序设计说明文档的能力 5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力 二.课程设计内容说明 1. 项目一 (1) 对设计任务内容的概述 学生成绩管理** 任务：要求实现对学生资料的录入、浏览、插入和删除等功能。 输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。 (2) 详细设计 LinkList *create()：输入学生成绩记录函数； void print(LinkList *head)：显示全部记录函数 LinkList *Delete(LinkList *head)：删除记录函数 LinkList *Insert(LinkList *head)：插入记录函数 void menu_select()：菜单选择 void ScoreManage()：函数界面

(3) 程序流程图 (4) 程序模块及其接口描述 该程序可以分为以下几个模块： 1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。

数据结构课程设计题目及要求

实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （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）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。