首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


return }

OK;

【C 源程序】 #include #include <stdio.h> <string.h>

#define Ok 1 #define Maxsize typedef struct{ int i,j; int v; }TriTupleNode; typedef struct{ TriTupleNode int m; int n; int t; /*矩阵行,列及三元组表长度*/ }TriTupleTable; void InitTriTupleNode (TriTupleTable *a){ /*输入三元组表*/ /*定义三元组表*/ data[Maxsize]; 10 //用户自定义三元组最大长度 /*定义三元组表*/

int i,j,k,val,maxrow,maxcol; char contiue;

maxrow=0; maxcol=0; i=j=0; k=0; while(i!=-1&&j!=-1){ printf("input row scanf("%d",&i); printf("input col scanf("%d",&j); printf("input valuen"); n"); n"); /*rol=-1&&col=-1 结束输入*/

scanf("%d",&val); a->data[k].i=i; a->data[k].j=j; a->data[k].v=val; if if k++; } a->m=maxrow;a->n=maxcol;a->t=k-1; } void showMatrix(TriTupleTable *a){ /*输出稀疏矩阵*/ (maxrow<i) (maxcol<j) maxrow=i; maxcol=j;

int p,q; int t=0; for(p=1;p<=a->m;p++) {for(q=1;q<=a->n;q++) { if (a->data[t].i==p&&a->data[t].j==q) {printf("%d t++; } else } printf("n" } } TransposeSMatrix(TriTupleTable {int q,col,p; *a,TriTupleTable *b) ); printf("0 "); ",a->data[t].v);

b->m=a->n;b->n=a->m;b->t=a->t; if(b->t) {q=0; for(col=1;col<=a->n;++col)

for(p=0;p<a->t;++p) if(a->data[p].j==col) { b->data[q].i=a->data[p].j; b->data[q].j=a->data[p].i; b->data[q].v=a->data[p].v;++q; } } } void main( void) *a,*b;

{TriTupleTable

InitTriTupleNode(a); showMatrix(a); /*转置前*/

TransposeSMatrix(a,b); showMatrix(b); } 【测试数据】 输入: 1 4 0 2 3 0 0 0 0 7 0 8 1 2 0 4 3 0 0 【说明】 分析算法,主要的工作是在 p 和 col 的两重循环中完成,算法的时间复杂度为 O(n*t)。如果非零元素个数 t 和 m*n 同数量级时,算法的时间复杂度变为 O(m*n2)。 【实验题】 1. 稀疏矩阵按行序进行转置。 2. 两个稀疏矩阵的相加运算。 输出: 0 0 0 7 8 /*转置后*/

第三节 十字链表表示稀疏矩阵的基本操作

【问题描述】两个相同行数和列数的稀疏矩阵用十字链表实现加法运算 【数据描述】 typedef struct ele int row, col; double struct }eleNode; 【算法描述】 (1) 若 q->j>v->j,则需要在 C 矩阵的链表中插入一个值为 bij 的结点,,修改 v=v->right。 (2) 如 q->j<v->j,则需要在 C 矩阵的链表中插入一个值为 aij 的结点,修改 q=q->right。 (3) 若 q->j = = v->j 且 q->e + v->e ! = 0,则需要在 C 矩阵的链表中插入一个值为 aij+bij val; ele *right, *down; {/* 十字链表结点类型*/

的结点,修改 q=q->right,v=v->right。 重复(1)--(3)完成一行的操作。 #include #include <stdio.h> <malloc.h> {/* 十字链表结点类型*/ 修改 p=p->down,u=u->down 后,再继续下一行。【C 源程序】

typedef struct ele int row,col; int val; struct

ele *right,*down;

}eleNode; /*建立一个元素全为零的稀疏矩阵的十字链表*/ eleNode *createNullMat(int m,int n) {eleNode int k; h=(eleNode *)malloc(sizeof(eleNode)); / * /*十字链表头结点 */ */ *h,*p; / * m行n列 */

h->row=m;h->col=n;h->val=0;

行数、列数和非零元素个数

h->right=(eleNode *)malloc(sizeof(eleNode)*n); h->down=(eleNode *)malloc(sizeof(eleNode)*m);

for(p=h->down,k=0;k<m;k++,p++){ p->col=1000; / * 设矩阵不会超过 1000 列 */

p->right=p;

/

*

每个行链表是一个环 / *

*

/

p->down=k<m-1?p+1:h->down; }

使全部行链表头结点构成环*/

for(p=h->right,k=0;k<n;k++,p++){ p->row=1000; p->down / * = p; 设矩阵不会超过 1000 行 * / * / * / / *使全部列链表头结点构成环 * /

每个列链表是一个环 p+1 : h->right;

p->right = } return } // h;

k<n-1 ?

int insertNode(eleNode /*

*a ,int

row,int col,double

val){

在十字链表中插入一个结点*/

eleNode *p,*q,*r,*u,*v; if(row>=a->row||col>=a->col) return -2; r=(eleNode *)malloc(sizeof(eleNode)); / * 不合理的行列号 * /

r->row=row;r->col=col;r->val=val; p=a->down+row;q=p->right; while(q->col<col){p=q;q=q->right;} if(q->col==col) return -1; u=a->right+col;v=u->down; while(v->row<row){u=v;v=v->down;} if(v->row==row) return -1; p->right = u->down r; r->right = / * q; v; 该列已有 row 行元素 * / * / * 插入到行链中 插入到列链中 * * / / / / * 该行已有 col 列元素 * /

= r; r->down =

a->val=val; return } 0; / * 插入成功 * /

eleNode *readMat(){

/*输入数据建立十字链表*/ eleNode *h; int i,j,m,n; int v; printf("输入稀疏矩阵的行数和列数"); scanf("%d%d",&m,&n); h=createNullMat(m,n); printf("输入有非零元素的行号"); scanf("%d",&i); while(i>=0) { / * 逐行输入非零元素 * /

printf("输入非零元素的列号"); scanf("%d",&j); while(j>=0) { / * 输入一行非零元素 * /

printf("输入非零元素的值");

scanf("%d",&v); insertNode(h,i,j,v); printf("输入当前行下一个非零元素的列号(-1 表示当前行一组数据结束)"); scanf("%d",&j); } printf("输入下一行有非零元素的行号(-1 表示输入结束)"); scanf("%d",&i); } return } void {int showMat(eleNode row,col,i,j; *a) h;

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 

数据结构实验指导书 - 数据结构 实验指导书 院别 专业 班级 姓名 计算机学院编 实验一 线性表的顺序存储实验 一、实验目的及要求 1、掌握在TC环境下调试顺序表...

数据结构与算法实验指导书90969 - 数据结构与算法实验指导书 计算机与信息学院 实验一 【实验目的】 顺序表 熟练掌握线性表在顺序存储结构上的基本操作。 【实验...

数据结构实验指导书02 很好!很好!隐藏&gt;&gt; 实验二 2.1 实验目的: 线性表 (1)掌握线性表的顺序存储结构的定义及 C 语言实现。 (2)掌握线性表在顺序存储结构即...

数据结构实验说明书新版 - the principl e of simplified E IA of constr uction pr oject s in the regi on. In te...

数据结构实验指导书 - 数据结构实验指导(C语言版)... 数据结构实验指导书_IT/计算机_专业资料。数据结构实验指导(C语言版) 数据结构实验指导书 江西农业大学计算机与...

数据结构试验指导书V2[1].0 - V 2.0 数据结构与算法 实验指导书 编写: 编写:陆绍飞 校核: 校核:___ 湖南大学软件学院 2011 年 9 月 湖南大学软件学...

数据结构实验指导书(2012.9) - 1.2 实验报告(文档)书写规范 实验报告(文档)应包括以下 7 个方面的内容: 1、问题分析 根据对实验任务的理解, 以无歧义的陈述...

09级《数据结构》实验指导书 - 《数据结构实验指导书》 潘向辉/吴学毅编写 印包学院数字媒体技术专业 2011 年 3 月 实验说明 实验说明 【实验环境】 操作系统:...

空间数据结构基础实验指导书 隐藏&gt;&gt; 《空间数据结构基础》 课程实习指导书实习周数:2 周 学分数:2 一、实习目的 数据结构是一门重要的专业基础课,其特点是理论...

《数据结构(C 语言版) 》实验指导书(非计算机专业适用) 广州大学 2013.1 目 录 实验一 线性表的顺序存储及其操作... 1 实验二 线性表的链式存储及其操作......


 

热点推荐