好学IT学院:IT信息技术分享交流平台
来源:互联网  作者:本站整理  发布时间:2009-11-02  ★★★加入收藏〗〖手机版
摘要:十字链表的定义十字链表(Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧都有一个结点,对应于每个定顶点也有一个结点。十字链表之于有……

十字链表的定义

十字链表(Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧都有一个结点,对应于每个定顶点也有一个结点。

十字链表之于有向图,类似于邻接表之于无向图。

十字链表的构成

用链表模拟矩阵的行(或者列,这可以根据个人喜好来定),然后,再构造代表列的链表,将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘(没见过,你就想一下苍蝇拍,这个总见过吧),而非零元就好像是在棋盘上放的棋子,总共占的空间就是,确定那些线的表头节点和那些棋子代表的非零元节点。最后,我们用一个指针指向这个棋盘,这个指针就代表了这个稀疏矩阵。

C语言应用举例

#include <malloc.h>
  #include <stdio.h>
  /*十字链表的结构类型定义如下:*/
  typedef struct OLNode
  {
  int row,col; /*非零元素的行和列下标*/
  ElementType value;
  struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
  struct OLNode *down;
  }OLNode; *OLink;
  typedef struct
  {
  OLink *row_head; /*行、列链表的头指针向量*/
  OLink *col_head;
  int m,n,len; /*稀疏矩阵的行数、列数、非零元素的个数*/
  }CrossList;
  /*建立稀疏矩阵的十字链表的算法*/
  void CreateCrossList(CrossList *M)
  {
  /*采用十字链表存储结构,创建稀疏矩阵M*/
  scanf(&m,&n,&t); /*输入M的行数,列数和非零元素的个数*/
  M->m=m;
  M->n=n;
  M->len=t;
  if(!(M->row_head=(OLink *)malloc((m+1)sizeof(OLink))))
  exit(OVERFLOW);
  if(!(M->col_head=(OLink * )malloc((n+1)sizeof(OLink))))
  exit(OVERFLOW);
  M->row_head[ ]=M->col_head[ ]=NULL; /*初始化行、列头指针向量,各行、列链表为空的链表*/
  for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e))
  {
  if(!(p=(OLNode *)malloc(sizeof(OLNode))))
  exit(OVERFLOW);
  p->row=i;
  p->col=j;
  p->value=e; /*生成结点*/
  if(M->row_head==NULL)
  M->row_head=p;
  else
  {
  /*寻找行表中的插入位置*/
  for(q=M->row_head;q->right&&q->right->col<j;q=q->right); /*空循环体*/
  p->right=q->right;
  q->right=p; /*完成插入*/
  }
  if(M->col_head[j]==NULL)
  M->col_head[j]=p;
  else
  {
  /*寻找列表中的插入位置*/
  for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down); /*空循环体*/
  p->down=q->down;
  q->down=p; /*完成插入*/
  }
  }
  }

利用SVN log命令查看提交日志信息详解
  内容提示:本文将详细介绍通过SVN log命令查看提交日志信息的方法。log: 显示一组版本与/或文件的提交日志信息。用法: 1、…
  • 好学考试H5触屏版开放内测
  • 好学触屏公众号虎力全开、杨帆起航!