博文
我所理解的矩阵03(2006-01-10 21:33:00)
摘要：除了用三元组顺序表来存储压缩矩阵，我们还可以用链表结构来存储，实际上后者应用更广泛，因为当非零元素的数目较大时，三元组的时间复杂度实在太高。链表结构中最常见的是十字链表，在十字链表中，稀疏矩阵每一行用一个带头结点的循环链表表示，每一列也用一个带头结点的循环链表表示。在这个结构中，除头结点外，每个结点都代表矩阵中的一个非零元素，它由5个域组成：行域（row），列域（col），数据域（data），向下域（down）
和向右域（right）。
为了使所有结点的存储结构一致，规定表头结点的结构与非零元素的结点完全一致，只是将其行域和列域设置为0，由于每一行链表的表头（行头）和每一列链表的表头（列头）的行域和列域的值均为0，故这两组表头结点可以共用，即同行号，同列号的行头和列头共同存储在一个结点中，只是将其逻辑分开（实际上行头使用该结点的向右域，而列头使用该结点的向下域），起到资源共享的效果。由此可知，稀疏矩阵的十字链表存储表示的结点总数等于非零元素的个数加上行头和列头（两者共用标号相同的结点，实际上只要提供其中的较大者的个数就可以了），再加上总表头Head[0]，其中总表头Head[0]的行域和列域分别存储矩阵的总行数和总列数，为节省空间，把矩阵非零元素的个数存储在Head[1]的行域。
//------稀疏矩阵的十字链表存储表示-------------------
#define MAXRC 100 //假设矩阵的行（列）数最多为100
typedef struct matnode
{
int row, col; //结点的行域和列域
struct matnode *right, *down;//结点的向下域（down）和向右域（right）
union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替
{
ElemType data;
struct matnode *next;
} tag;
} CrossNode, *CrossList;
//--------------------------------......
我所理解的矩阵02(2006-01-10 21:32:00)
摘要：在实际应用中，我们经常碰到这样一类矩阵，它们的非零元素很少，而且分布没有规律，我们称之为稀疏矩阵。很显然，若用二维数组存储稀疏矩阵，将浪费大量的时间和空间。因此我们对稀疏矩阵一般采取压缩存储的方法，即只存储其非零元素。常用的数据结构有三元组顺序表 和十字链表。
我们先来看三元组顺序表。
//------稀疏矩阵的三元组顺序表存储表示-------------------
#define MAXSIZE 1000 //假设非零元素的个数最多为1000个
typedef struct
{
int x, y; //该非零元素的行下标和列下标
ElemType e; //该非零元素的值
} Triple;
typedef struct
{
Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用
int mu, nu, tu; //矩阵的行数，列数和非零元素的个数
} TSMatrix;
在此，data域中表示非零元素的三元组是以行序为主序顺序排列的，这为我们的某些计算将
带来方便。
创建一个三元组
TSMatrix CreateTriple(int m, int n) //构造一个三元组顺序表存储矩阵
{
TSMatrix T;
int i=0;
puts("请按行序为主序依次输入矩阵的非零元素的行号，列号和元素值，每行输入一个元素的信息：");
printf("注意行号不能超过%d,列号不能超过%d\n", m, n);
do
{
i++; &......
我所理解的矩阵01(2006-01-10 21:30:00)
摘要：矩阵应用系列
矩阵是很多科学与工程计算问题中研究的数学对象。我这里主要是提供一些矩阵的计算方法和用不同方式存储矩阵元进行计算时算法的比较。
矩阵的存储方式很多，最为常见的是用二维数组来存储矩阵元；但是在处理稀疏矩阵时，这种存储方法会浪费大量的时间和空间，一般采用三员组和十字链表的方法来存储。我将依次讲解这三种方法的不同特点。
首先是最为常见的二维数组存储法。这种存储方法形式简单明了，进行各种计算时算法也很容易理解。矩阵的常见计算有求转置矩阵，求逆矩阵，矩阵的加法和乘法。
void CreateArray(int H[][N], int m, int n) //构造一个二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
H[i][j] = rand()%4;
}
void PrintArray(const int H[][N], int m, int n) //输出二维数组存储矩阵
{
int i, j;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
printf("%6d ", H[i][j]);
printf("\n");
}
}
1。转置矩阵
转置是一种最简单的矩阵运算，对于一个m*n的矩阵Amn，其转置矩阵是一个n*m的矩阵Bnm，
且B[j][i] = A[i][j]，0<=i<m, 0<=j<n，其函数如下；
void trsmat(const int A[][N], int B[][N], int m, int n)
{
int i, j;
for(i=0; i<m; i++)
fo......
行列式和代数余子式(2006-01-07 15:59:00)
摘要：/*创建行列式（人工输入数据），输出该行列式和代数余子式，并输出其值*/
/*2006-1-7 梁见斌*/
#include <stdio.h>
#include <stdlib.h>
#define N 3
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
int sum; //全局变量，存储行列式的值
void Create(int H[][N]); //构造一个行列式
void PrintH(const int H[][N]); //输出行列式
void PrintYH(const int YH[][N-1]);//输出代数余子式
void SolveH(const int H[][N], array S[], int i, int NiXu); //采用递归方式求行列式的值
void SolveYH(const int YH[][N-1], array S[], int i, int NiXu);//采用递归方式求代数余子式的值
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
int main(void)
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int H[N][N], YH[N-1][N-1]; //存储行列式和代数余子式
int Y[N][N];//存储代数余子式的值
int x, y, row, col;
int i, j, k;
Create(H); //构造一个行列式
PrintH(H); //输......
解线性方程组(2006-01-07 12:10:00)
摘要：/*按规则输入线性方程组的系数（每行N+1个数值，按顺序输入N个系数项，最后一项为常数项，用空格隔开）
，输出该方程组的系数行列式和它的值，最后输出方程组的解*/
/*处理整型数据*/
/*2006-1-7 梁见斌*/
#include <stdio.h>
#include <stdlib.h>
#define N 4 //行列式的行（列）数
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
int sum; //全局变量，存储行列式的值
void Create(int H[][N], int X[]); //构造一个线性方程组
void PrintH(const int H[][N], const int X[]); //输出行列式
void Solve(const int H[][N], array S[], int i, int NiXu); //采用递归方式求行列式的值
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
int main(void)
{
array SL[N]; //栈，存储行列式的每一个乘积项的元素（因子）
int H[N][N], CH[N][N]; //存储系数行列式
int B[N]; //存储常数项
int D; //存储系数行列式的值
float X[N];//存储方程组的解
int i, j, k;
Create(H,B); //构造一个行列式
PrintH(H,......
行列式和它的全排列(2006-01-07 12:06:00)
摘要：/*创建行列式（电脑随机输入数据），输出该行列式和它的全排列，并输出其值*/
#include <stdio.h>
#include <stdlib.h>
#define N 3
#define M 6
typedef struct node
{
int data; //存储元素的值
int x; //存储元素的横坐标
int y; //存储元素的纵坐标
} array;
array Stack[M][N+1]; //全局变量，存储全排列的乘积项
int sum=0, count=0; //全局变量，分别存储行列式的值和乘积项的个数
void Create(int H[][N]); //构造一个行列式
void PrintH(const int H[][N]); //输出行列式
void Solve(const int H[][N], array S[], int i, int NiXu); //采用递归方式求行列式的全排列
bool Judge(const array S[], int line, int len); //判断行列式的元素的纵坐标是否重复
void Save(const array S[]); //把每一个乘积项存储到全局变量Stack[][]
void PrintS(const array S[][N+1]); //输出行列式的全排列
int main(void)
{
array SL[N+1]; //栈，存储行列式的每一个乘积项的元素（因子）
int H[N][N]; //存储行列式
Create(H); //构造一个行列式
PrintH(H); //输出行列式
Solve(H, SL, 0, 0); //采用递归方式求行列式的全排列
&n......
万年历全集(2006-01-02 15:14:00)
摘要：程序可以实现如下三种功能：
求某个日期对应的星期
求某年某月有的天数
输出某年的日历.
例如,打印2006年日历如下:
--------------------------------------------------------------------------
2006 年
--------------------------------------------------------------------------
一 月 二 月
周日 周一 周二 周三 周四 周五 周六 周日 周一 周二 周三 周四 周五 周六
1 3 5 7 9 11 13 ......
爱因斯坦的思考题(2005-12-30 13:46:00)
摘要：/*爱因斯坦的思考题
在网上看到了个有趣的逻辑推理题，爱因斯坦声称世界上只有2%的人能解出：
有五个具有五种不同颜色的房间排成一排；
每个房间里分别住着一个不同国籍的人；
每个人都在喝一种特定品牌的饮料，抽一特定品牌的烟，养一特定的宠物；
没有任意两个人在抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物。
问题：谁在养鱼作为宠物？
爱因斯坦给出如下线索：
英国人住在红色的房子里；
瑞典人养狗作为宠物；
丹麦人喝茶；
绿房子紧挨着白房子，在白房子的左边；
绿房子的主人喝咖啡；
抽Pall Mall牌香烟的人养鸟；
黄色房子里的人抽Dunhill牌香烟；
住在中间那个房子里的人喝牛奶；
挪威人住在第一个房子里面；
抽Blends牌香烟的人和养猫的人相邻；
养马的人和抽Dunhill牌香烟的人相邻；
抽BlueMaster牌香烟的人和啤酒；
德国人抽Prince牌香烟；
挪威人和住在蓝房子的人相邻；
抽Blends牌香烟的人和喝矿泉水的人相邻。
编了一个,比较粗糙,比较复杂,敬请改进:
国家 房子 宠物 饮料 香烟
挪威 黄色&nbs......
我所理解的二杈树03(2005-12-28 11:09:00)
摘要：有序二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。
一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。
AVL树的结点声明；
typedef struct avlnode
{
int height;//比普通二杈有序树多了一个高度信息
ElemType data;
struct bnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);
//----------AVL树基本操作的算法实现--------------------
递归算法：
Position FindMin(AvlTree T)
{
if(T==NULL)
return NULL;
else if(T->lchild == NULL)
return T;
else
return FindMin(T->lchild);
}
Position FindMax(A......
我所理解的二杈树02(2005-12-28 11:09:00)
摘要： 二杈排序树
所谓二杈排序树，指的是一棵空二杈树，或者是一棵具有如下特性的非空二杈树：
1。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
2。若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
3。左，右子树本身又各是一棵二杈排序树。
二杈排序树的基本操作包括二杈排序树的查找，生成（插入）和删除。
二杈排序树的查找：
在二杈排序树b中查找x的过程为：
1。若b是空树，则搜索失败，否则
2。若x等于b的根结点的数据域之值，则查找成功；否则
3。若x小于b的根结点的数据域之值，则搜索左子树；否则
4。搜索右子树
btree* search(btree *b, ElemType x)
{
if(b == NULL)
return NULL;
if(b->data == x)
return b;
if(b->data > x)
return search(b->lchild);
&n......