⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 ds5.3.2.htm

📁 这是清华大学所用的数据结构的电子版教材
💻 HTM
📖 第 1 页 / 共 3 页
字号:
🔍
123 
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>

<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">

<!--mstheme--><font face="宋体"><p:colorscheme
 colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p ALIGN="center"><b><font size="6" color="#FFFF00">5.3.2 <font FACE="??ì?,SimSun" LANG="ZH-CN">稀疏矩阵的十字链表存储</font></font></b></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法、乘法）时，非零项数目及非零元素的位置会发生变化，这时这种表示就十分不便。在这节中，我们介绍稀疏矩阵的一种链式存储结构棗十字链表，它同样具备链式存储的特点，因此，在某些情况下，采用十字链表表示稀疏矩阵是很方便的。</b></font></p>
<p><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">图</font>5.18<font FACE="??ì?,SimSun" LANG="ZH-CN">是一个稀疏矩阵的十字链表。</font></b></font></p>
<p align="center"><img border="0" src="ds5.3.17.gif" width="164" height="95"></p>
<p align="center" style="margin-top: 0"><font SIZE="3"><img SRC="Image7.gif" width="438" height="298"></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">用十字链表表示稀疏矩阵的基本思想是：</font></b></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font face="??ì?,SimSun" lang="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp; 
</b></font><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">对每个非零元素存储为一个结点，结点由</font>5<font FACE="??ì?,SimSun" LANG="ZH-CN">个域组成，其结构如图</font>5.19<font FACE="??ì?,SimSun" LANG="ZH-CN">表示，其中：</font>row<font FACE="??ì?,SimSun" LANG="ZH-CN">域存储非零元素的行号，</font>col<font FACE="??ì?,SimSun" LANG="ZH-CN">域存储非零元素的列号，</font>v<font FACE="??ì?,SimSun" LANG="ZH-CN">域存储本元素的值，</font>right<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>down<font FACE="??ì?,SimSun" LANG="ZH-CN">是两个指针域。</font></b></font></p>
<div align="center">
  <center><!--mstheme--></font>
  <table BORDER="1" CELLSPACING="1" CELLPADDING="7" WIDTH="165" HSPACE="12" bordercolorlight="#3366CC" bordercolordark="#000000">
    <tr>
      <td WIDTH="40" VALIGN="TOP" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
        <p ALIGN="JUSTIFY">row</font><!--mstheme--></font></td>
      <td WIDTH="37" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
        <p ALIGN="JUSTIFY">col</font><!--mstheme--></font></td>
      <td WIDTH="30" VALIGN="TOP" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
        <p ALIGN="JUSTIFY">v</font><!--mstheme--></font></td>
    </tr>
    <tr>
      <td WIDTH="55" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
        <p ALIGN="JUSTIFY">down</font><!--mstheme--></font></td>
      <td WIDTH="42" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
        <p ALIGN="JUSTIFY">right</font><!--mstheme--></font></td>
    </tr>
  </table>
  <!--mstheme--><font face="宋体"></center>
</div>
<p ALIGN="center" style="margin-top: 0">&nbsp;&nbsp; <img border="0" src="ds5.3.18.gif" width="176" height="23"></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp; 
稀疏矩阵中每一行的非零元素结点按其列号从小到大顺序由</font>right<font FACE="??ì?,SimSun" LANG="ZH-CN">域链成一个带表头结点的循环行链表，同样每一列中的非零元素按其行号从小到大顺序由</font>down<font FACE="??ì?,SimSun" LANG="ZH-CN">域也链成一个带表头结点的循环列链表。即每个非零元素</font>a<sub>ij</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">既是第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">行循环链表中的一个结点，又是第</font>j<font FACE="??ì?,SimSun" LANG="ZH-CN">列循环链表中的一个结点。行链表、列链表的头结点的</font>row<font FACE="??ì?,SimSun" LANG="ZH-CN">域和</font>col<font FACE="??ì?,SimSun" LANG="ZH-CN">域置</font>0<font FACE="??ì?,SimSun" LANG="ZH-CN">。每一列链表的表头结点的</font>down<font FACE="??ì?,SimSun" LANG="ZH-CN">域指向该列链表的第一个元素结点，每一行链表的表头结点的</font>right<font FACE="??ì?,SimSun" LANG="ZH-CN">域指向该行表的第一个元素结点。由于各行、列链表头结点的</font>row<font FACE="??ì?,SimSun" LANG="ZH-CN">域、</font>col<font FACE="??ì?,SimSun" LANG="ZH-CN">域和</font>v<font FACE="??ì?,SimSun" LANG="ZH-CN">域均为零，行链表头结点只用</font>right<font FACE="??ì?,SimSun" LANG="ZH-CN">指针域，列链表头结点只用</font>right<font FACE="??ì?,SimSun" LANG="ZH-CN">指针域，故这两组表头结点可以合用，也就是说对于第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">行的链表和第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">列的链表可以共用同一个头结点。为了方便地找到每一行或每一列，将每行（列）的这些头结点们链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">行（列）的头结点的值域指向第</font>i+1<font FACE="??ì?,SimSun" LANG="ZH-CN">行（列）的头结点，</font>… 
<font FACE="??ì?,SimSun" LANG="ZH-CN">，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针</font>HA<font FACE="??ì?,SimSun" LANG="ZH-CN">指向它。总头结点的</font>row<font FACE="??ì?,SimSun" LANG="ZH-CN">和</font>col<font FACE="??ì?,SimSun" LANG="ZH-CN">域存储原矩阵的行数和列数。</font></b></font></p>
<p><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp; 
因为非零元素结点的值域是</font>datatype<font FACE="??ì?,SimSun" LANG="ZH-CN">类型，在表头结点中需要一个指针类型，为了使整个结构的结点一致，我们规定表头结点和其它结点有同样的结构，因此该域用一个联合来表示；改进后的结点结构如图</font>5.20<font FACE="??ì?,SimSun" LANG="ZH-CN">所示。</font></b></font></p>
<p ALIGN="CENTER"><center><!--mstheme--></font>
<table BORDER="1" CELLSPACING="1" CELLPADDING="7" WIDTH="148" bordercolorlight="#3366CC" bordercolordark="#000000">
  <tr>
    <td WIDTH="33%" VALIGN="TOP" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
      <p ALIGN="JUSTIFY">row</font><!--mstheme--></font></td>
    <td WIDTH="33%" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
      <p ALIGN="JUSTIFY">col</font><!--mstheme--></font></td>
    <td WIDTH="33%" VALIGN="TOP" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
      <p ALIGN="JUSTIFY">v/next</font><!--mstheme--></font></td>
  </tr>
  <tr>
    <td WIDTH="50%" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
      <p ALIGN="JUSTIFY">down</font><!--mstheme--></font></td>
    <td WIDTH="50%" VALIGN="TOP" COLSPAN="2" HEIGHT="23"><!--mstheme--><font face="宋体"><font SIZE="3">
      <p ALIGN="JUSTIFY">right</font><!--mstheme--></font></td>
  </tr>
</table>
<!--mstheme--><font face="宋体"></center>
<p ALIGN="center" style="margin-top: -1"><img border="0" src="ds5.3.19.gif" width="288" height="20"></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">综上，结点的结构定义如下</font>:</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>typedef 
struct node</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>{int 
row, col;</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;struct 
node *down , *right;</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;union 
v_next</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;{datatype 
v;</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp; 
struct node *next;</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;}</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>} 
MNode<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>*MLink;</b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp; 
让我们看基于这种存储结构的稀疏矩阵的运算。这里将介绍两个算法，创建一个稀疏矩阵的十字链表和用十字链表表示的两个稀疏矩阵的相加。</b></font></p>
<p ALIGN="JUSTIFY"><font FACE="oúì?,SimHei" LANG="ZH-CN" size="5" color="#FFFFFF"><b>1．建立稀疏矩阵A的十字链表</b></font></p>
<font SIZE="3">
<p ALIGN="JUSTIFY"></font><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp; 
首先输入的信息是：</font>m<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>A<font FACE="??ì?,SimSun" LANG="ZH-CN">的行数），</font>n<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>A<font FACE="??ì?,SimSun" LANG="ZH-CN">的列数），</font>r<font FACE="??ì?,SimSun" LANG="ZH-CN">（非零项的数目），紧跟着输入的是</font>r<font FACE="??ì?,SimSun" LANG="ZH-CN">个形如（</font>i,j,a<sub>ij</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">）的三元组。</font></b></font><font SIZE="3"></p>
</font>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">算法的设计思想是：首先建立每行（每列）只有头结点的空链表，并建立起这些头结点拉成的循环链表；然后每输入一个三元组（</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>j<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>a<sub>ij</sub><font FACE="??ì?,SimSun" LANG="ZH-CN">），则将其结点按其列号的大小插入到第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">个行链表中去，同时也按其行号的大小将该结点插入到第</font>j<font FACE="??ì?,SimSun" LANG="ZH-CN">个列链表中去。在算法中将利用一个辅助数组</font>MNode 
*hd[s+1]; <font FACE="??ì?,SimSun" LANG="ZH-CN">其中</font> s=max(m , n) , hd 
[i]<font FACE="??ì?,SimSun" LANG="ZH-CN">指向第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">行</font>(<font FACE="??ì?,SimSun" LANG="ZH-CN">第</font>i<font FACE="??ì?,SimSun" LANG="ZH-CN">列</font>)<font FACE="??ì?,SimSun" LANG="ZH-CN">链表的头结点。这样做可以在建立链表时随机的访问任何一行（列），为建表带来方便。</font></b></font><font SIZE="3"></p>
</font>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>算法如下：</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>MLink 
CreatMLink( ) /* <font FACE="??ì?,SimSun" LANG="ZH-CN">返回十字链表的头指针</font>*/</b></font></p>
<p ALIGN="justify" style="margin-left: 0; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">{</font>MLink
123

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -