第一篇：树形结构的应用 数据结构实验
树形结构应用 实验日志
实验题目：建立二叉树
实验目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。实验要求：
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的操作。
实验主要步骤：
1.编写源程序，建立二叉树。
2.连接—编译—运行该程序，并在过程中调试。3.实现各种遍历的操作。
由二叉树的定义可知，一棵树由根结点、左子树和右子树三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。先序遍历算法：（1）访问根结点；（2）先序遍历左子树；
（3）先序遍历右子树。
中序遍历算法：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。后序遍历算法：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。源程序：
#include
struct TREE_NODE *left;
//左结点指针
struct TREE_NODE *right;
//右结点指针 }TreeNode;//连接temp和tree两个节点
TreeNode* link(TreeNode *temp,TreeNode *tree,int key){
tree =(TreeNode*)malloc(sizeof(TreeNode));
if(temp!= NULL)
if(temp->value > key)
temp->left = tree;
else
temp->right = tree;
tree->value = key;
tree->left = NULL;
tree->right = NULL;
return tree;} //插入并建立二叉树
TreeNode * insert(TreeNode *tree,int key){
TreeNode *temp = NULL,*p = tree;
if(tree!= NULL)
{
while(tree!= NULL && tree->value!= key)
{
if(tree->value > key)
{
temp=tree;
tree = tree->left;
}
else
{
temp=tree;
tree = tree->right;
}
}
tree = link(temp,tree,key);
}
else//if(tree == NULL)
{
tree = link(temp,tree,key);
//将下面注释掉的代码单独写成了一个函数
/*tree =(TreeNode*)malloc(sizeof(TreeNode));
tree->value = key;
tree->left = NULL;
tree->right = NULL;*/
}
if(p!= NULL)
tree = p;
return tree;}
//先序遍历
void print1(TreeNode *tree){
if(tree)
{
printf(“%3d,”,tree->value);
print1(tree->left);
print1(tree->right);
} }
//中序遍历
void print2(TreeNode *tree){
if(tree)
{
print2(tree->left);
printf(“%3d,”,tree->value);
print2(tree->right);
} }
//后序遍历
void print3(TreeNode *tree){
if(tree!= NULL)
{
print3(tree->left);
print3(tree->right);
printf(“%3d,”,tree->value);
} } int main(){
int key,i;
TreeNode *tree;
tree = NULL;
printf(“请输入整型数：（以任意字符结束）n”);
while(1)
{
i = scanf(“%d”,&key);
if(i!= 1)
break;
tree = insert(tree,key);
}
printf(“n先序遍历：”);
print1(tree);
printf(“n中序遍历：”);
print2(tree);
printf(“n后序遍历：”);
print3(tree);
printf(“n”);
system(“pause”);
return 0;} 实验结果：
心得体会：这次实验已经比上一次要熟练一些，并且对于这类算法的大致写法也有了一个了解，那就是递归算法的大量使用。在查错的时候对C语言以前忘记或不熟练的地方也进行了复习，同时，对二叉树的遍历也有了更深的理解。
第二篇：数据结构实验教案
第一次实验 线性表
（一）实验目的和要求：
1.熟悉VC集成环境
2.会定义线性表的顺序结构和链式结构
3.熟悉对线性表的基本操作，如插入、删除等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现线性表的建立、插入、删除等功能。
写出线性表、顺序表、链表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的顺序表算法有： 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有： 1.建立链表
2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第二次实验 栈和队列
（一）实验目的和要求：
1.熟练掌握栈和队列的结构，以及这种数据结构的特点 2.会定义顺序栈、循环队列，能实现栈、队列的基本操作 3.会利用栈解决典型问题，如数制转换等
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现栈（或者队列）的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等
写出栈的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.初始化栈 2.入栈 3.出栈
4.判断栈是否为空 5.十进制转换为八进制
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第三次实验 二叉树
（一）实验目的和要求：
1.熟练掌握二叉树的结构，以及这种数据结构的特点 2.会定义二叉树的链式存储结构
3.能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现二叉树的各种基本操作，如二叉树的建立（头插法或者尾插法），遍历等 写出二叉树的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第四次实验
查找
（一）实验目的和要求：
1.熟练掌握查找算法的基本思想，以及算法的适用条件
2.会定义静态查找表的顺序结构，能实现顺序查找、二分查找
（二）实验内容和原理或涉及的知识点（综合性实验）：
自己编写程序实现顺序查找、二分查找。
写出静态查找表的定义，简单写出主要算法的思路。
（三）实验条件：安装有VC的计算机
（四）实验设计方案
设计的算法有： 1.建立静态查找表 2.顺序查找
3.建立有序的静态查找表 4.二分查找
（五）实验过程、数据和实验结果记录
程序代码（略）
实验过程中输入/输出数据、程序运行结果的记录。（一定要有！）
第三篇：数据结构实验指导书
目 录
实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表
（一）······································4 实验二 单链表
（二）······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9
实 验 规 则
为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：
1、实验前必须充分预习，完成指定的预习任务。预习要求如下：
（1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。
（3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。
2、遵守以下纪律：
（1）在实验室不得做和实验无关的事情。
（2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。
（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。
实 验 环 境
本实验在386以上的微机上进行，运行环境为VC6.0。
实验报告要求
1、实验题目 2．实验目的 3．实验环境
4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结）
实验一 单链表
（一）一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。
2、根据要求，编写程序准备上机调试。
三、实验内容
实现一个简单的学生信息管理系统，该系统的功能有：
1、利用单链表建立学生基本信息表
2、浏览每个学生的信息
3、根据学号查询某个学生的基本信息
4、添加学生信息到单链表中
5、删除一个学生的信息
四、实现提示
设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。
实验二 单链表
（二）一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。
2、根据要求，编写程序准备上机调试。
三、实验内容
1、实现单链表的就地逆置。
2、建立两个非递减有序单链表，然后合并成一个非递减链表。
3、建立两个非递减有序单链表，然后合并成一个非递增链表。
4、编写一个主函数,调试上述算法。
四、选做题、思考题
1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。
2、约毖夫环的实现。
3、如何利用文件实现学生信息的存取。
实验三 栈
一、实验目的
深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。
二、预习要求
1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。
2、根据要求，编写程序准备上机调试。
三、实验内容
利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。
四、实现提示
1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。
2、采用顺序存储实现栈的初始化、入栈、出栈操作。
五、选做题、思考题
1、两栈空间共享时，栈满的条件是什么？
2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。
3、编写程序，利用栈实现表达式求值。
实验四 二叉树
一、实验目的
通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。
二、预习要求
二叉树的三种遍历方法。
三、实验内容
1、输入字符序列，建立二叉链表。
2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。
3、求二叉树的叶子结点个数。
4、在主函数中设计一个简单的菜单，分别调试上述算法。
四、选做题、思考题
1、如何实现二叉树的后序遍历（非递归）。
2、如何求二叉树的高度。
实验五 最短路径（旅游景点导游咨询模拟）
一、实验目的
利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。
二、预习要求
学习了解图的存储结构，掌握求最短路径的两种算法。
三、实验内容
设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。
四、实现提示
咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。
五、选做题、思考题
1．如何实现对城市信息进行编辑（如：添加或删除）的功能。
2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。
实验六 内部排序
一、实验目的
直观感受算法的关键字比较次数和关键字移动次数。
二、预习要求
1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。
2、根据要求，编写程序准备上机调试。
三、实验内容
1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。
2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。
四、实现提示
测试数据可以为几组典型的数据：正序、逆序、乱序。
五、选做题、思考题
1、快速排序算法的非递归实现。
2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。
3、如何对本实验进行时间、空间的复杂度分析。
第四篇：数据结构 实验指导书
数 据 结 构 实 验 指 导 书
数据结构实验指导书
目录
数据结构实验指导书.......................................................................................................................1
目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3
实验一 C语言相关知识复习................................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3
三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5
一、实验目的...................................................................................................................5
二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6
一、实验目的...................................................................................................................6
二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8
一、实验目的...................................................................................................................8
二、实验内容...................................................................................................................8
实验指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因，使得掌握这门课程具有较大难度： 内容多，时间短，给学习带来困难；
贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点； 隐含在各部分的技术和方法丰富，也是学习的重点和难点； 先修课程中所介绍的专业性知识不多，加大了学习难度。
由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。
为了达到上述目的，本指导书安排了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。
每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。
问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；
要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；
测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；
实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。
下面带*的题目为选做题目。
上机实验题目
实验一 C语言相关知识复习
一、实验目的
复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。
二、实验内容 问题描述：编写一个函数，求一个整数数组中的最大、最小值。
要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。2 关于指针的使用：
用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。
测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。
实验二 单链表的插入、删除
一、实验目的
1、熟悉某种数据结构在计算机上实现的方法。
2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。
3、体会单链表操作、有序表插入、删除的一般方法。
二、实验内容
问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的有序性。
实验要求：
1、结点的数据均为整型。
2、若表中已经存在此元素，则不插入
三、实现提示
1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历
2.在单链表表中插入或删除，需依次实现：
a)单链表结构的定义
b)单链表的创建（头插法或尾插法建表）c)单链表的遍历
d)单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针）
//头文件
#include “stdlib.h” //预定义常量 #define NULL 0
//单链表的定义
typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建
void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
q=L;
scanf(“%d”,&data);while(data!=0){
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf(“%d”,&data);} }
//单链表的遍历
void TranverseList(LinkList L){
LinkList p;
p=L->next;
if(p==NULL)
{
printf(“niln”);
return;
}
while(p!=NULL)
{
printf(“%d ”,p->data);
p=p->next;
}
printf(“n”);}
实验三 栈及其应用
一、实验目的
1、熟悉栈的顺序表示与实现。
2、熟悉栈的应用。
3、理解并掌握递归函数的设计与实现。
二、实验内容 问题描述：利用栈实现十进制数n转化为d进制数 要求：
1)输入一个n和d，打印输出d进制数序列。
2)利用顺序栈来实现十进制数n转化为其他d进制数。此时，需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据：
（1）输入n:1348
d:8 输出：2504（2）输入n:9
d:8 输出：11（3）输入n:0
d:8 输出：0 2 问题描述：利用栈实现算术表达式求值。要求：
1)参与运算的操作数为10以内的数值。测试数据：
自拟。
实验四 二叉树的递归算法
一、实验目的
1、掌握二叉树的表示与实现。
2、掌握二叉树的定义、创建、遍历等基本操作的实现。
3、熟悉求二叉树深度等递归算法的设计与实现。
二、实验内容
问题描述：已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历。要求：
1、二叉树分别采用顺序或二叉链表存储。
2、树中的数据类型约定为整型。测试数据：
1、输入序列：-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树； 输出：深度：5
前序序列：-+a*b-cd/ef
中序序列：a+b*c-d-e/f
后序序列：abcd-*+ef/-T:d / e f
2、t=nil
输入：Ø
输出：深度：0 实验五 图的遍历
一、实验目的
熟悉图的基本操作，掌握图遍历的设计与实现。
二、实验内容
问题描述：已知的描述校园景点的图，实现对该图的深度优先和广度优先遍历。要求：
图采用邻接矩阵存储，顶点信息包括景点的名称和简单描述。
实验六 有序表的查找
一、实验目的
1、理解各种查找方法的基本思想
2、熟悉有序表查找方法的算法实现
二、实验内容 已知一有序的序列{1,3,5,7,9}，采用折半法分别查找3和6。
2已知输入一无序的序列{5,1,3,9,7}，创建一棵二叉排序树，然后对其遍历，输出递增有序的序列。
实验七 哈希表
一、实验目的
理解哈希表的概念和基本操作；熟悉哈希表的创建、查找、插入的算法实现。
二、实验内容
问题描述：已知11位好友的名字各不相同，设计并实现一个哈希表，根据好友的名字，可以取得其生日。要求：
1、好友的信息包含名字和生日两个数据项，其中好友的名字为主键，用汉语拼音形式存放；
2、哈希函数采取：好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余)；
3、采取线性探测再散列的方式处理冲突。
实验八 内部排序算法的应用
一、实验目的
理解各种内部排序方法的基本思想；熟悉各种内部排序方法的算法实现
二、实验内容
问题描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分别采取下列排序方法对其进行排序：
（1）直接插入排序；
（2）简单选择排序；
（3）起泡排序；（4）快速排序；（5）堆排序。
第五篇：实验7 数据结构
实验七
稀疏矩阵的实现基本操作
班级：1208341
4学号：1208141姓名：陈峰
一、实验内容
（1）掌握稀疏矩阵的压缩存储；（2）掌握稀疏矩阵的转置算法；
二、实验目的
（1）实现上三角阵的压缩存储；
（2）用三元组书序表存储稀疏矩阵，并实现矩阵的转置；
三、设计思想
（1）创建一个数组；（2）输入数据；
（3）给定矩阵任一元素的下标；（4）打印给定下标所对应的数据；（5）创建三元组顺序表；（6）输入矩阵中的数据；（7）输出对应的矩阵；
四、程序源代码
（1）三元组顺序表存储稀疏矩阵并实现矩阵的转置；
#include
# define MAXSIZE 100 # define MAXRC 10
struct Triple {
int i,j;
/*该非零元的行下标和列下标*/
int e;};struct TSMtrix {
struct Triple data[MAXSIZE+1];
/*非零元三元组表，data[0]未用*/
int rpos[MAXRC+1];
/*各行第一个非零元的位置表*/
int cpos[MAXRC+1];
/*各列第一个非零元的位置表*/
int num[MAXRC+1];
/*各列非零元的个数*/
int mu,nu,tu;
/*矩阵的行数、列数和非零元个数*/ };
void CreateMtrix(struct TSMtrix *M){ /*创建一个稀疏矩阵*/
int i,elem,col,row,mu,nu,tu;
printf(“please input matrix col,row,unzeroed numbers:n”);
scanf(“%d%d%d”,&mu,&nu,&tu);
M->mu=mu;
M->nu=nu;
M->tu=tu;
for(i=1;i<=tu;i++)
{
printf(“please input element col,row,value:n”);
scanf(“%d%d%d”,&col,&row,&elem);
if(mu<0 || nu<0 || mu>M->mu || nu>M->nu)
{
printf(“error!”);
i--;
}
else
{
M->data[i].i=col;
M->data[i].j=row;
M->data[i].e=elem;
}
} }
void ShowMtrix(struct TSMtrix M){ /*打印出矩阵*/
int i=1,j=1,dir=1;
printf(“The matrix is:n”);
for(i=1;i<=M.mu;i++)
{
for(j=1;j<=M.nu;j++)
{
if(M.data[dir].i==i && M.data[dir].j==j)
{
printf(“%d
”,M.data[dir].e);
/*存在非零元*/
dir++;
}
else
printf(“0
”);
}
printf(“n”);
} }
void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T){ /*矩阵的快速转置*/
int t=1,p=1,q,col=M.nu;
T->mu=M.mu;
T->nu=M.nu;
T->tu=M.tu;
if(T->tu)
{
for(col=1;col<=M.nu;col++)
M.num[col]=0;
for(t=1;t<=M.nu;t++)
++M.num[M.data[t].j];
M.cpos[1]=1;
/*找到M中cpos的位置*/
for(col=2;col<=M.nu;col++)
M.cpos[col]=M.cpos[col-1]+M.num[col-1];
for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
q=M.cpos[col];
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
++M.cpos[col];
}
} }
main(){
struct TSMtrix M;
struct TSMtrix N;
CreateMtrix(&M);
ShowMtrix(M);
printf(“n”);
FastTransposeSMtrix(M,&N);
ShowMtrix(N);
getch();}
（2）实现矩阵的经典转置算法并测试；
#include
typedef struct { int i,j;Elemtype e;}te;
typedef struct { te data[maxsize+1];//存储非0元素的数组，该数组是从1开始，所以下面的p从等于1开始// int mu,nu,tu;//mu 表示行数，nu 表示列数，tu 表示该矩阵中非0的个数// }tx;
//向矩阵中输入元素 int intput(tx &a){
int row,col,p=1;//row 表示元素的行标，col 表示元素的列标，p表示非0元素的计数器//
int temp;
printf(“请输入矩阵行数：”);
scanf(“%d”,&a.mu);
printf(“请输入矩阵列数：”);
scanf(“%d”,&a.nu);
printf(“请输入原始矩阵的每行每列元素：n”);
for(row=1;row<=a.mu;row++)//双重循环// {
for(col=1;col<=a.nu;col++)
{
scanf(“%d”,&temp);
if(temp!=0)
{
a.data[p].i=row;
a.data[p].j=col;
a.data[p].e=temp;
p++;
}
a.tu=p;
}
printf(“n”);
}
return 0;}
//输出上面的矩阵
int output(tx &a){
int row,col;
int p=1;
printf(“输出原始矩阵：n”);
for(row=1;row<=a.mu;row++)
{
for(col=1;col<=a.nu;col++)
{
if(row==a.data[p].i && col==a.data[p].j)
{
printf(“t%d”,a.data[p].e);
p++;
}
else
//剩余的输出0//
printf(“t%d”,0);
}
printf(“n”);//换行符的位置//
}
return 0;}
//定义了一个新的矩阵b// int transpose(tx a,tx &b)
{
int row,col;
//找出非0元素//
int p,q=1;
b.mu=a.nu;//矩阵b的行数等于矩阵a的列数//
b.nu=a.mu;//矩阵b的列数等于矩阵a的行数//
b.tu=a.tu;//非0元素的个数///
if(a.tu!=0)//判断是否有非0元素// {
//双重循环//
for(col=1;col<=a.nu;col++)
// 该循环是以列循环目的是：把非0元素中列标小的元素从头排列//
{
for(p=1;p<=a.tu;p++){
if(a.data[p].j==col)
//循环非0数组中的元素，并找出a.data[p].j等于当时的a矩阵在中的col// { //把矩阵a中非0元素的行标和列标等于矩阵b非0元素的列标和行标//
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].e=a.data[p].e;
q++;
} }
}
printf(“n”);
}
return 0;}
//输出转置后的矩阵
int outputtranspose(tx &b){
int q=1;
int row,col;
printf(“输出转置后的矩阵：n”);
for(row=1;row<=b.mu;row++)
{
for(col=1;col<=b.nu;col++)
{
if(row==b.data[q].i && col==b.data[q].j)//找出b矩阵非0元素//
{
printf(“t%d”,b.data[q].e);
q++;
}
else
printf(“t%d”,0);//剩余的输出0//
}
printf(“n”);
}
return 0;}
void main(){ tx a,b;intput(a);output(a);transpose(a,b);outputtranspose(b);}
五、调试及测试数据
（1）三元组顺序表存储稀疏矩阵并实现矩阵的转置；
（2）实现矩阵的经典转置算法并测试；
六、实验总结
在本实验中，老师给出了“三元组顺序表存储稀疏矩阵并实现矩阵的转置”的完整实验代码供我们参考。通过对参考例子的代码的理解，看懂之后程序代码之后就能比较轻松地写出题目的代码。在本次实验中能够清楚的知道要做什么，从哪里开始做，怎么做，思路很清晰。经过编程，学会了串的操作与实现，并且对C++也有了新的认识。
鲁公网安备37028302000876号