首页 > 代码库 > 数据结构与算法系列研究四——数组和广义表

数据结构与算法系列研究四——数组和广义表

稀疏矩阵的十字链表实现和转置

一、数组和广义表的定义

    数组的定义1:一个 N 维数组是受 N 组线性关系约束的线性表。
           二维数组的逻辑结构可形式地描述为:
           2_ARRAY(D,R)
              其中 D={aij} | i=0,1,...,b1-1; j=0,1,...,b2-1;aij∈D0}
              R={Row,Col}
              Row={<aij,ai,j+1>|0<=i<=b1-1;0<=j<=b2-2;aij,ai,j+1∈D0}
                           ai,j+1是aij在行关系中的后继元素。
              Col={<aij,ai+1,j>|0<=i<=b1-2;0<=j<=b2-1;aij,ai+1,j∈D0}
                           ai+1,j是aij在列关系中的后继元素。
            ①每一个数组元素a[i][j]都受两个关系Row和Col的约束:
              ROW(行关系):ai,j+1 是aij在行关系中的直接后继。
              COL(列关系):ai+1,j是aij在列关系中的后继元素。
           ②每个数组元素属于同一数据类型。
           ③每个数组元素由下标(i,j)唯一确定其位置。
           ④每个下标i由bi限定其范围,0≤i≤bi-1
      n维数组的逻辑结构可描述为:    
           n_ARRAY(D,R)
                D---数组的元素  
                R---定义为数组元素间的关系
           R=(R1,R2,...,Rn)
    数组的定义2 :一维数组是定长线性表; 二维数组是一个定长线性表,它的每个元素是一个一维数组;n维数组是线性表,它的每个元素是n-1维数组。
       数组是线性结构,基于两点:
          1、一个 n维数组被定义为一个线性表,它的元素是一个 n-1维数组。
          2、一个 n维数组的数据元素受n个关系的约束,且每个关系都是线性的。

技术分享技术分享

技术分享

技术分享

技术分享

  其中: cn =L, ci-1= bi × ci,  1<i ≤ n ; ci 为常数
          上式称为n维数组的存储映象函数

 数组的基本操作:
    1、数组初始化:确定数组维数、长度,分配存储空间。
         initarray(&A,n,bound[ ]);  
             bound[ ]= b1,b2......bn
   2、撤消数组
         destroyarray (&A);
   3、求数组元素值
        value(A,&e,index[ ]);           
              index[ ]= i1,i2,......in
   4、为数组元素赋值
        assign(&A,e,index[ ]);
 数组的顺序表示及实现:
     用一遍地址连续的存储单元依次存放数据元素。
     1、数据类型描述
        #define MAX_ARRAY_DIM 8
       typedef struct {
          ElemType *base;   //数组元素空间
          int dim;          //数组维数
          int *bounds;      //数组维长
          int *constant;    //常数因子
      }ARRAY;
 矩阵的压缩存储:
    1、矩阵压缩存储的概念
        特殊矩阵:值相同元素或0元素在矩阵中分布有一定规律。
       ⒈对称矩阵:矩阵中的元素满足
                     aij=aji       1≤i,j≤n
       ⒉三角矩阵:上(下)三角矩阵指矩阵的下(上)三角(不包括对角线)中的元素均为常数c或0的n阶矩阵。
       ⒊对角矩阵(带状矩阵):矩阵中所有非0元素集中在以主对角线为中心的区域中。
      稀疏矩阵:非0元素很少( ≤ 5%)且分布无规律。
    2、矩阵的压缩存储
         为多个相同值的元分配一个存储单元;对零元不分配空间。
       对称矩阵的压缩存储
       存储分配策略: 每一对对称元只分配一个存储单元,即只存储下三角(包括对角线)的元, 所需空间数为:
                        n×(n+1)/2。
       存储分配方法: 用一维数组sa[n(n+1)/2]作为存储结构。
             sa[k]与aij之间的对应关系为:
      稀疏矩阵存储分配策略
          只存储稀疏矩阵的非0元素。
          矩阵中的一个元素可以用行列下标和其值来唯一表示,因此可以用一个三元组(i,j,aij) 唯一确定一个非0元素。
          逻辑上,用三元组表来表示稀疏矩阵的非0元                             
  广义表的定义
    广义表又称为列表(lists),是n≥0个元素a1,a2,...,an的有限序列,记为:
         A=( a1,a2,...,an)
     其中:
        A是广义表的表名,n是广义表的长度
        ai 是单个元素或广义表,
           若ai是单个元素,则称为广义表的单元素(或原子)。
           若是广义表,则称ai是广义表的子表。所以广义表又称为列表。
           即  ai ∈D0  或 ai ∈lists
        广义表的表头(Head):非空表A 的第一个元素 a1。
        广义表的头与a1具有相同的表示形式。
        广义表的表尾(Tail):除其头之外的其余元素( a2,...,an)组成的表。
        广义表的尾一定是一个广义表。
        特点:广义表的定义是一个递归的定义。

技术分享

 


技术分享

 

二、稀疏矩阵的十字链表实现

  2.1.实验内容
   编程实现稀疏矩阵的十字链表实现
    1.用txt文件录入稀疏矩阵数组,格式如下:
        m  n  t //表示行号,列号和总数
        i   j  value
        ..................
   2.读文件建立十字链表
   3.输出建立后的链表,格式为;
     行号1  列号11 值** 列号12 值***  。。。。。
     行号2  列号21 值** 列号22 值***  。。。。。
    。。。。。。。。。
   4.实现矩阵的转置
   5.输出转置后的矩阵,格式为矩阵形式。
 
 2.2.输入和输出
   输入:本程序采取文件读写形式,文件中数值格式详见实验内容
   输出:本程序有两种输出形式分别为按行输出和按矩阵形式输出

 2.3.关键数据结构与算法描述
    数据结构:建立十字链表需要知道行列号i,j和链表的right,down指针,以及节点的数值,于是数据结构呼之欲出,又因过程中读文件时需要先建立一个缓冲器存储节点的信息, 则两个结构具体如下:

技术分享
/***********以下构建数据结构************/
typedef  struct OLink{
    int i,j;
    ElemType value;
    struct OLink *right,*down;
}*LinkList,OLink;
/************构建存储结构*************/
typedef struct record{
    int i;
    int j;
    int value;
}RECORD;
/**************构建完毕**************/
View Code

  算法描述:
      建立十字链表,

       1.首先要知道链表的头节点,因每行,每列都需要一个循环链表,则共需要m+n+1个头指针,m个行指针,n个列指针,1个总头指针。

       2.建立完两个指针链表之后(注意:此处链表的每一个元素都是附加头节点),就要对矩阵的元素进行插入,当插入元素时要注意和对应行,对应列都建立联系,构成网状结构,当插入完元素之后,十字链表也就建立完毕了。

       3.余下的就是输出元素了,根据头节点共有两种输出方法,一种按行输出,一种按列输出。当然也可以把非零元素放到二维数组中,通过二维数组进行输出。

       4.最后,就是矩阵的转置,只需将a[i][j]与a[j][i]交换即可,再重新建立十字链表,修改初始化和i,j指向即可。其中最核心的算法就是头节点的构建和元素的插入了,具体代码如下:

技术分享
/*************创建行,列头节点*****************/
void CreateHead(LinkList *head, int m, int n)
{
    //以下建立列头结点
    LinkList p = *head,q;
    //构建列头节点
    for(int i=0; i<n; i++)
    {
      q = (LinkList)malloc(sizeof(OLink));
      q->i = -1;   //注意在矩阵的外面,也可以不赋值
      q->j = i;    //代表矩阵的列号,从0开始

      q->down = q;  //构建循环链表的标志
      p->right = q; //链接
      p = q;        //继续向前推进
    }
    p->right = (*head);//循环链表的标志
    
    //以下建立行头结点,基本原理同上
    p = (*head);
    for(i=0; i<m; i++)
    {
      q = (LinkList)malloc(sizeof(OLink));
      q->i = i;
      q->j = -1;
    
      q->right = q;
      p->down = q;
      p = q;
    }
    p->down = (*head);
}
/************各个头节点构建完毕,共m+n+1个************/

/***************插入节点的算法************************/
bool InsertNode(LinkList *head, int i, int j, ElemType e)
{
    LinkList p = *head,q;
    if(i < 0||j < 0||i >= (*head)->i||j >= (*head)->j)
        return false;
    /********构建节点********/
    q = (LinkList)malloc(sizeof(OLink));
    q->i = i;
    q->j = j;
    q->value =http://www.mamicode.com/ e;
    /*******完毕***********/
    for(int k=0; k<=i; k++)
    {
        p = p->down;//注意此处等于i截至
    }
    //产生定位指针
    LinkList sr = p,s = p->right;
    /******若不满足s==p,或者插入元素大于后面元素,继续推进********/
    while(s!=p && q->j>s->j)
    {
        sr = s;
        s=s -> right;
    }
    /*******推进完毕,有可能有三种情况*************/
    q->right = s;
    sr->right = q;
    /**********行链接处理完毕*********************/
    /******以下链接列链表,方法同上**********************/
    p = *head;
       for( k=0; k<=j; k++)
    {
         p = p->right;
    }
     sr = p;
     s = p->down;
    while(s!=p && q->j>s->j)
    {
        sr = s;
        s = s->down;
    }
    q->down = s;
    sr->down = q;
    /**********列链接处理完毕*********************/
     return true;
}
View Code

 2.4.测试与理论
   1.在文件操作中输入如下文本:
技术分享

  2.程序运行后应产生9*5的矩阵,具体输出形式应与要求一致,如图;

技术分享

  3.转置后变成5*9的矩阵,具体显示如下

 技术分享

 2.5、所有程序

技术分享
  1 #include "stdlib.h"
  2 #include "conio.h"
  3 #include "iostream"
  4 using namespace std;
  5 
  6 typedef  int ElemType;//设置元素类型
  7 
  8 /***********以下构建数据结构************/
  9 typedef  struct OLink{
 10     int i,j;
 11     ElemType value;
 12     struct OLink *right,*down;
 13 }*LinkList,OLink;
 14 /************构建存储结构*************/
 15 typedef struct record{
 16     int i;
 17     int j;
 18     int value;
 19 }RECORD;
 20 /**************构建完毕**************/
 21 
 22 /**************进行初始化操作********************/
 23 void InitArray(LinkList *head, int m, int n)
 24 {
 25     *head = (LinkList)malloc(sizeof(OLink));
 26     (*head)->i=m;      //行长度
 27     (*head)->j=n;      //列长度
 28 }
 29 /***************初始化完毕*********************/
 30 
 31 /*************创建行,列头节点*****************/
 32 void CreateHead(LinkList *head, int m, int n)
 33 {
 34     //以下建立列头结点
 35     LinkList p = *head,q;
 36     //构建列头节点
 37     for(int i=0; i<n; i++)
 38     {
 39       q = (LinkList)malloc(sizeof(OLink));
 40       q->i = -1;   //注意在矩阵的外面,也可以不赋值
 41       q->j = i;    //代表矩阵的列号,从0开始
 42 
 43       q->down = q;  //构建循环链表的标志
 44       p->right = q; //链接
 45       p = q;        //继续向前推进
 46     } 
 47     p->right = (*head);//循环链表的标志
 48     
 49     //以下建立行头结点,基本原理同上
 50     p = (*head);
 51     for(i=0; i<m; i++)
 52     {
 53       q = (LinkList)malloc(sizeof(OLink));
 54       q->i = i;
 55       q->j = -1;
 56      
 57       q->right = q;
 58       p->down = q;
 59       p = q;
 60     }
 61     p->down = (*head);
 62 }
 63 /************各个头指针构建完毕,共m+n+1个************/
 64 
 65 /***************插入节点的算法************************/
 66 bool InsertNode(LinkList *head, int i, int j, ElemType e)
 67 {
 68     LinkList p = *head,q;
 69     if(i < 0||j < 0||i >= (*head)->i||j >= (*head)->j)
 70         return false;
 71 
 72     /********构建节点********/
 73     q = (LinkList)malloc(sizeof(OLink));
 74     q->i = i;
 75     q->j = j;
 76     q->value =http://www.mamicode.com/ e;
 77     /*******完毕***********/
 78 
 79 
 80     for(int k=0; k<=i; k++)
 81     {
 82         p = p->down;//注意此处等于i截至
 83     }
 84     //产生定位指针
 85     LinkList sr = p,s = p->right;
 86     /******若不满足s==p,或者插入元素大于后面元素,继续推进********/
 87     while(s!=p && q->j>s->j)
 88     {
 89         sr = s;
 90         s=s -> right;
 91     }
 92     /*******推进完毕,有可能有三种情况*************/
 93     q->right = s;
 94     sr->right = q;
 95     /**********行链接处理完毕*********************/
 96 
 97 
 98     /******以下链接列链表,方法同上**********************/
 99     p = *head;
100     for( k=0; k<=j; k++)
101     {
102          p = p->right;
103     }
104      sr = p;
105      s = p->down;
106     while(s!=p && q->j>s->j)
107     {
108         sr = s;
109         s = s->down;
110     }
111     q->down = s;
112     sr->down = q;
113     /**********列链接处理完毕*********************/
114 
115    return true;
116 }
117 
118 /**********关于矩阵转置的算法,即a[i][j]<->a[j][i]******************/
119 LinkList   MatrixTransposition(LinkList head, int m, int n)
120 {
121     LinkList THead = head,p,q,h;
122     int temp;
123     //重新构造十字矩阵,列换行,行换列
124     InitArray(&h,n,m);
125     CreateHead(&h,n,m);
126     for(p = THead->down; p!=THead; p = p->down)
127     {
128      
129       for(q = p->right; q!=p; q = q->right)
130       {
131           //j变i,i变j,值不变
132         if(!InsertNode(&h, q->j, q->i, q->value))
133             return  NULL;  
134       }
135       
136     }
137     return  h;
138     
139 }
140 /*******销毁链表操作******************/
141 void  DestroyMatrix(LinkList  *head)
142 {
143     LinkList  p,q,r;
144     for(p = (*head)->down; p!=*head; p = p->down)
145     {
146      
147       for(q = p->right; q!=p;)
148       {
149            r = q->right;
150            free(q);
151            q=r;
152       }
153       
154     }
155 }
156 /*************打印矩阵算法*********************/
157 void  PrintMatrix(LinkList head,int m,int n)
158 {
159     LinkList p,q;
160 
161     cout<<"此矩阵为"<<m<<"*"<<n<<""<<endl;
162     //向下推进,按行输出
163     for(p = head->down; p!=head; p = p->down)
164     {
165       cout<<""<<p->i<<"";
166       for(q = p->right; q!=p; q = q->right)
167       {
168         
169           cout<<"  "<<"["<<q->i<<","<<q->j<<"]  "<<q->value<<"   ";
170       }
171       cout<<endl;
172     }
173 }
174 //以矩阵形式输出
175 void   MatrixPrint(LinkList head,int m,int n)
176 {
177     int  a[100][100];
178     LinkList p,q;
179     memset(a,0,sizeof(a));//置零
180     for(p = head->down; p!=head; p = p->down)
181     {
182       for(q = p->right; q!=p; q = q->right)
183       {
184         a[q->i][q->j]=q->value;//赋值
185       }
186     }
187     for(int i=0;i<m;i++)
188     {
189         for(int j=0;j<n;j++)
190         {
191             cout<<a[i][j]<<"    ";
192         }
193         cout<<endl;
194     }
195 }
196 
197 void  MainMenu()
198 {
199     LinkList head,h;
200     int m,n,total;//total为矩阵中非零数值个数
201     RECORD RecordMatrix[1000];
202     FILE *fp;
203 
204     if((fp = fopen("F:Matrix.txt","r"))==NULL)
205     {
206         cout<<"cannot open the file"<<endl;
207         exit(-1);
208     }
209     //找到矩阵的基本框架
210     fscanf(fp,"%d%d%d",&m,&n,&total);
211     //缓存器record
212     for(int i=0;i<total;i++)
213     {
214         fscanf(fp,"%d%d%d",&RecordMatrix[i].i,&RecordMatrix[i].j,&RecordMatrix[i].value);
215     }
216     //构建十字链表
217     InitArray(&head,m,n);
218     CreateHead(&head,m,n);
219     for(i=0;i<total;i++)
220     {
221         if(!InsertNode(&head,RecordMatrix[i].i,RecordMatrix[i].j,RecordMatrix[i].value))
222             return ;
223     }
224      cout<<"原矩阵元素为"<<endl;
225      PrintMatrix(head,m,n);//打印链表矩阵
226      MatrixPrint(head,m,n);//以矩阵形式打印
227 
228      //测试转制后的矩阵
229      h = MatrixTransposition(head,m,n);
230      cout<<endl<<"转置后矩阵元素为"<<endl;
231      PrintMatrix(h,n,m);
232      MatrixPrint(h,n,m);//以矩阵形式打印
233 
234      DestroyMatrix(&head);//销毁链表
235      DestroyMatrix(&h);   //销毁链表
236         fclose(fp);           //关闭文件
237 }  
238 
239 int main()
240 {
241     MainMenu();//引入主函数
242        getchar();
243     return 0;
244 }
View Code

 

 

 

 

 




数据结构与算法系列研究四——数组和广义表