数据结构实验考试题

数据结构实验考试题

1.已知线性表A,B,C是递增有序的线性表。要求对A表作如下运算：删去那些既在B表

中出现又在C表中出现的元素。A,B,C以顺序表存储。

2.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构。请编写程

序将A表和B表归并成一个按元素递减有序排列的线性表C,并要求利用原表结点空间存放C表。

3.求以递增序排列的两个线性表A和B的交集，将结果存于新表C中。要求C中元素仍

然以递增序排列，并且C中没有重复的元素。以顺序结构实现此算法。

4.设A=(a1, ... ,am)和B=(b1,...,bn)均为有序线性表，A' 和B' 分别为A、B中除去最大共

同前缀后的子表。若A' = B' = 空，则A=B；若A' = 空表，B'≠空表，或者两者均不空且A'首元小于B'首元，则AB。

5.单链表中的元素以递增序存放,写一算法,删除表中所有值大于mink且小于maxk的元素

(如果这样的元素存在).

6.假设以循环链表作稀疏多项式的存储结构，编写求两个稀疏多项式乘积的算法。要求：

不破坏原来的多项式链表。

7.设两个栈共享向量空间v(1:m),它们的栈底分别在向量的两端，进栈的每个元素只占用

一个分量。写出这两个栈公用的栈操作算法：push(i,x), pop(i)和top(i,x)。其中i=0或1，分别代表两个不同的栈。

8.Ackerman函数的非递归解法

akm(m,n) = n + 1 (当m = 0时)

akm(m-1,1) (当m <> 0 且n = 0时)

akm(m-1,akm(m,n-1)) (当m<>0 且n<>0时)

9.求一个广义表的深度*广义表的深度即是括号的最大层数。通过记录一个表中所出现的

配对括号的层数，就可以求出广义表的深度。

10.具有头结点的两个单链表的链接。已知：头结点的数据段中放的是链表长度。两个链表

的链接是指将一个链表的第一个元素链接到另一个链表的尾部。要求：算法必须有最小的时间代价

●以数组储存的队列，设置rear和quelen两个变量分别表示队尾元素位置和队列长度。

写出入/出队列的算法。

●以数组存储的循环队列，编写能充分利用数组中每个元素的入/出队列算法。此题需要

设立一个标志，以指示当rear = front时队列是空还是满。

●求矩阵中所有的马鞍点。若矩阵A[0:m-1,0:n-1]中的某个元素A[i,j]是第i行中的最小值，

同时右又是第j列中的最大值，则它就是马鞍点。

●用堆栈实现判断一个算术表达式中括号是否配对的算法。假设一个算术表达式中可以包

括(),[],{}三类括号，且这三种括号可以任意嵌套使用。

●试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高。假定学生成绩

的分布情况如下：

分数0-59 60-69 70-79 80-89 90-100

比例0.05 0.15 0.40 0.30 0.10

●设线性表存于数组array中，且递增有序。将一个新元素x插入到线性表中，并保持排

序状态。

●假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表

中某个结点的指针，编写在链表中删除s所指结点的前驱结点的算法。

●试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法。要求利用原结点空间

并释放多余结点。

●已知单链表表示的线性表中含有三类字符数据元素，一类为数字，一类为字母，一类为

其他符号。试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

●试设计一个算法，将数组A(0:n-1)中的元素循环右移k位，并要求只用一个元素大小的

附加存储，元素移动或交换的次数为O(n)。

●用一维数组做存储结构，就地逆置一线性表。如：(a1,a2,...an)逆置后为(an,an-1,...,a1) ●设有一个双链表，每个结点中除了有pre,data和next三个域外，还有一个访问频度域

freq，在链表起用之前，所有的freq = 0。每当在链表进行一次LOCATE(l,x) 运算时，令元素值等于x的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。

●背包问题：假设一个背包可以装入总重量为T的物品，现在有n件物品，其重量分别

为：w1,w2,...,wn。求{wx1,wx2,...,wxn}包含于{w1,w2,...,wn}使得wx1+wx2 + ... + wxn = T。（wi <> wj, i<>j; wxi <> wxj, i <>j）

●（1）若n=1,则当w1 = T时有解；（2）若n>1,则此题化为：求T' = T - wj, 物品重量为

w1,w2,... w(j-1),w(j+1),...,wn时的背包问题。j = 1,2,...,n 如此递归，可解。

●写出求递归函数f(n)的非递归算法：

f(n) = n+1 (当n=0)

f(n) =n*f((int)(n/2)) (当n>0)

●假定用两个一维数组L(0:n-1)和R(0:n-1)作为有n个结点的二叉树的存储结构，L[i]和

R[i]分别指示结点i的左孩子和右孩子，-1 表示空。

（1）判别结点u是否为结点v的子孙；

（2）先由L和R建立一维数组T(0:n-1),使T中第i个元素(i=0,2,...,n-1)

指示结点i的双亲，然后写判别结点u是否是v的子孙的算法。

●通过键盘输入的扩充二叉树的前序遍历序列, 建立二叉树，然后按中序和后序输出此

树，并求该树的叶结点个数和度数为2的结点个数。假设二叉树结点的数据为char型，其中扩充结点用'*'号表示。

●在一棵以二叉链表存储的二叉树中，求在前序序列中排在第k位的结点假设表达式由单

字母变量和双目运算符构成，写一个算法，判断表达式是否为正确的后缀表达式。如果是，将其转化为前缀表达式。

●假设二叉树中左分支的标号为"0",右分支的标号为"1"，并对二叉树增设一个头结点，令

根结点为其右孩子。则：从头结点到树中任意一结点所经分支的序列为一个二进制序列，将这个二进制序列的值作为该结点对应的值。

●已知一棵非空二叉树以顺序结构存储，变量i为树中某结点在顺序存储结构中的下标值，

写一个尽可能简单的算法，求出于该结点对应的值。如：

(a)

0/ \1

(b) (c)

0/ \1

(e) (g)

0/

(h) h对应的二进制序列为1110,即十进制的14。

●假设二叉树T中至多有一个结点的数据域为x,编写算法拆去以该结点为根的子树，使

原树分为两棵。例如x = 9,二叉树的变化如下：

13

/\

316

/ \ \

2 9 27

/ / \

4 6 11

拆开后：

13

/\

316

/ \

227

/

4

9

/ \

6 11

●用递归的方法复制一棵二叉树，假设二叉树以二叉链表存储。

●设计一个算法输出已知二叉树中所有叶子结点的值

●已知一棵二叉树以二叉链表为存储结构，编写如下算法：对于树中每一个元素值为x

的结点，删去以它为根的子树，并释放相应的空间。

●编写算法查找二叉树中数据域值为X的结点（假定各结点的数据域值各不相同），并打

印出X所有祖先的数据域值。

●编写判断两个二叉树是否相等的算法。若T1与T2是等价的，则要么T1与T2是空树，

要么T1和T2的值相同并且T1、T2的左右子树分别相等。

●编写判断两个二叉树是否相似的算法。若T1与T2是相似的，则要么T1与T2是空树，

要么T1和T2都不是空树并且T1、T2的左右子树分别相似。假设树是以二叉链表形式存储的。

●写一算法,判断一棵二叉树是否是完全二叉树。

●对二叉树进行层次遍历

●求一棵二叉树中每个层次的结点数

●编写一个算法，输出以二叉树表示的算术表达式。要求：在需要加括号的地方加上括号。

●假设以二叉链表存储的二叉树中，每个结点所含的数据元素均为单字母，编写算法，按

树状打印二叉树。如：

a

/ \

b c

\ /

d e

\

f 打印为：

c f e a

d b

●一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中。编写非递归算法对该树进

行前序遍历。

●以二叉链表为二叉树的存储结构，写出求某个结点的父结点的算法。

●编写算法交换二叉树中所有结点的左、右子树。

●一棵二叉树的前序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为

结点的该二叉树。

●一棵二叉树的后序序列和中序序列分别存在两个数组中，编写算法，建立以二叉链表为

结点的该二叉树。

●huffman算法

●图解最小生成树算法

●无向图邻接表生成算法

●从一个顶点到其它顶点的最短路径算法

●图的各个顶点最短路径

●图的深度遍历

●图的广度遍历

●顺序查找算法

●二分查找算法

●冒泡排序算法

●快速排序算法

●希尔排序算法

●直接插入排序

●基数、归并排序算法

数据结构实验4

（一）题目 1. 按下述原则编写快排的非递归算法： (1) 一趟排序之后，若子序列已有序(无交换)，则不参加排序，否则先对长度较短的子序列进行排序，且将另一子序列的上、下界入栈保存； (2) 若待排记录数<=3，则不再进行分割，而是直接进行比较排序。 测试实例：{49 38 65 97 76 13 27 49 88 21 105} （二）算法思路 (1) 建立存储序列上下界的栈序列。 (2) 对栈顶作如下判断： A. 若栈顶中记录的头与尾相距小于3，对对应的子序列进行排序，然后出栈，进入(3)； B. 若栈顶中记录的头与尾相距大于等于3，则进行分块，判断分块是否有序， a.若两分块都有序，则出栈，进入(3)； b.若只有一分块有序，则改变栈顶内容为无序分块内容，进入(3)； c.若两分块都无序，则改变栈顶内容为较长的无序块，然后把较短的无序块 压进栈。进入(3) (3)重复(2)的操作，直至栈空，得到最终结果。 （三）程序结构 定义的结构体及声明 （四）源码

using namespace std; typedef struct _stack{ int left; //lowerbound int right; //upperbound struct _stack *next; }qstack; //to store the child sequence's left and right void sort(int *arr, int left, int right){ //sort child sequence less than 3 for(int i = left; i <= right; i++){ int k = i; for(int j = i+1; j <= right; j++){ if(arr[k] > arr[j]) k = j; } if(k != i){ int t; t = arr[k]; arr[k] = arr[i]; arr[i] = t; } } } bool sorted(int *arr, int left, int right){ for(int i = left; i < right; i++){ if(arr[i] > arr[i+1]) return false; } return true; } void qsort(int *arr, int left, int right){ qstack *head; head = new qstack; head->left = left; head->right = right; head->next = NULL; qstack *p; while(head != NULL){ if(head->right - head->left < 3){ //if less than 3, sort and pop sort(arr, head->left, head->right);

数据结构实验

实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include using namespace std; int main() { int arraay[10]={1,2,3,4,5,6,7,8,9,10}; int binary_search(int a[10],int t); cout<<"Enter the target:"; int target; cin>>target; binary_search(arraay,target); return 0; } int binary_search(int a[10],int t) { int bottom=0,top=9; while(bottom

cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include #include #include using namespace std; typedef int keyType; typedef struct Node { keyType key; struct Node* left; struct Node* right; struct Node* parent; }Node,*PNode; void inseart(PNode* root, keyType key) { PNode p = (PNode)malloc(sizeof(Node)); p -> key = key;

数据结构实验报告格式

《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时）

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { 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++) {

数据结构实验报告(四)

《数据结构》实验报告 班级： 学号： 姓名：

实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

一、程序源代码 #include #include #define MAXSIZE 30 typedef char ElemType; typedef struct TNode *BiTree; struct TNode { char data; BiTree lchild; BiTree rchild; }; int IsEmpty_BiTree(BiTree *T) { if(*T == NULL) return 1; else return 0;

} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;

数据结构实验一 实验报告

班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2

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;

数据结构图的遍历实验报告

实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构实验

长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.wendangku.net/doc/e215777096.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数

数据结构实验报告模板

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&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数： 主函数； 结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { 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; } }

数据结构实验4_99XXX

《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作

附源程序清单： 1. #include #define MaxSize 100 using namespace std; typedef char ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //初始化栈 { st->top=-1; } int StackEmpty(SqStack *st) //判断栈为空{ if(st->top == -1) return 0;//为空 else return -1;//不为空 } void Push(SqStack *st,ElemType x) //元素进栈{ if(st->top==MaxSize-1)

{ printf("栈上溢出!\n"); } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } } void Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { printf("栈下溢出\n"); } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} } int main() { SqStack L; SqStack *st=&L; ElemType c; int i; InitStack(st); printf("输入回车结束入栈"); while((c=getchar())!='\n') { if(c=='(') Push(st,c); if((i=StackEmpty(st))==-1) { if(c==')') Pop(st,c); } if(c==')' && (i=StackEmpty(st))==0) { printf("右括号多出,配对失败"); goto loop;

数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)

数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 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 ）

数据结构实验1

《数据结构》实验报告 实验序号：1 实验项目名称：概论

附源程序清单： 1. #include void main() { int i; int num[10]; int *p; for(i=0;i<=9;i++) num[i]=i+1; for(p=(num+9);p>=(num+0);p--) printf("%d ",*p); printf("\n"); }

2. #include void main() { void swap(int *a,int *b); int i; int a[10]; int *p,*max,*min; for(i=0;i<10;i++) scanf("%d",&a[i]); max=min=a; for(i=0;i<10;i++) { if(*maxa[i]) min=&a[i]; } p=a; swap(p,max); swap((p+9),min); for(p=a;p<=(a+9);p++) printf("%d ",*p); printf("\n"); } void swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } 3. #include #include #include #include typedef struct { char num[5]; char name[20]; float score1; float score2; float score3; float average;

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main()

数据结构实验四题目一排序实验报告

数据结构实验报告 实验名称：实验四——排序 学生：XX 班级： 班序号： 学号： 日期： 1．实验要求 实验目的： 通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 题目1： 使用简单数组实现下面各种排序算法，并进行比较。 排序算法如下： 1、插入排序； 2、希尔排序； 3、冒泡排序； 4、快速排序； 5、简单选择排序； 6、堆排序； 7、归并排序； 8、基数排序（选作）； 9、其他。 具体要求如下： 1、测试数据分成三类：正序、逆序、随机数据。 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关 键字交换记为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。 5、编写main（）函数测试各种排序算法的正确性。 2. 程序分析 2.1 存储结构

存储结构：数组 2.2 关键算法分析 一、关键算法： 1、插入排序 a、取排序的第二个数据与前一个比较 b、若比前一个小，则赋值给哨兵 c、从后向前比较，将其插入在比其小的元素后 d、循环排序 2、希尔排序 a、将数组分成两份 b、将第一份数组的元素与哨兵比较 c、若其大与哨兵，其值赋给哨兵 d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组 e、循环进行数组拆分 3、对数据进行编码 a、取数组元素与下一个元素比较 b、若比下一个元素大，则与其交换 c、后移，重复 d、改变总元素值，并重复上述代码 4、快速排序 a、选取标准值 b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后 指针前移，重新比较 c、否则后面元素赋给前面元素 d、若后指针元素小于标准值，前指针后移，重新比较 e、否则前面元素赋给后面元素 5、简单选择排序 a、从数组中选择出最小元素 b、若不为当前元素，则交换 c、后移将当前元素设为下一个元素 6、堆排序 a、生成小顶堆 b、将堆的根节点移至数组的最后 c、去掉已做过根节点的元素继续生成小顶堆

数据结构实验报告及心得体会

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;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验报告图实验

图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { 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;