精华内容
下载资源
问答
  • 2022-04-10 00:24:16

    (耿《数据结构》原文)为避免大量移动元素,采用稀疏矩阵的链式存储法——十字链表。

    它的好处是能灵活地插入因运算而产生的非零元素,删除因运算而产生的新的零元素,实现矩阵的各种运算。

    1.十字链表的存储表示(五要素)

    矩阵的每一个非零元素用一个结点表示,该结点除了(row,col,value)以外,还要添加两个链域:

    right:用于链接同一行中的下一个非零元素

    down:用于链接同一列中的下一个非零元素

    在十字链表的储存结构中,可以看成是两个单链表的组合沟通。可以类比行指针,列指针。

    同一行的非零元素通过right域链接成一个单链表,

    同一列的非零元素通过down域链接成一个单链表。

    相应的,需要附设一个存放所有行链表头指针的一维数组和一个存放所有列链表的头指针的一维数组。

    2.十字链表的类型定义

    一个结点的定义;

    typedef struct OLNode
    {
    int row,col;
    ElementType value;
    struct OLNode *right,*down;//指向的下一个结点也是同样的结构
    }OLNode;*OLink;

    十字链表存储结构

    typedef struct
    {
    OLink *row_head,*col_head;//头指针
    int m,n,len;//行,列,非零元素个数
    }CrossList;

    3.十字链表的算法实现

    步骤:

    ①读入稀疏矩阵的行数,列数,非零元素个数;

    ②申请行,列链表的头指针空间;

    ③逐个读入非零元素,分别插入行链表,列链表。

    算法(建立稀疏矩阵的十字链表,实质是在两个单链表中完成插入)

    CreateCrossList(CrossList *M)
    {
    scanf("%d %d %d",&m,&n,&t);
    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[i]==NULL)//如果原先的稀疏矩阵这一行全为零,直接以这个插入的结点创建这一行行链表的头指针
    M->row_head[i]=p;
    else
    {
    //寻找插入的位置
    q=M->row_head[i];//用来指向这一行的插入点的前一个结点,一开始指向行表头
    while(q->right!=NULL&&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
    {
    //寻找插入位置
    q=M->col_head[j];
    while(q->down!=NULL&&q->down->row<i)
    q=q->down;
    p->down=q->down;
    q->down=p;
    }
    }
    }
    

    更多相关内容
  • 实现了从字符文件读入三个正整数m, n, t以及t个三元组(i, j, e)建立稀疏矩阵的十字链表存储结构(m、n分别表示矩阵行数和列数;i, j为非零元素行号和列号)和十字链表的转置并将转置后的三元组到另一字符文件中
  • 压缩包中为 十字链表法创建图的 C 文件源文件,及对应的PPT 博客《【经典算法实现 30】图的创建 --- 十字链表法》 链接:https://blog.csdn.net/Ciellee/article/details/108199838
  • 十字链表

    千次阅读 多人点赞 2019-04-26 11:26:29
    有需求才有供应,很多东西,都是为了解决实际问题才出现的,项目中出现了很多稀疏矩阵,而且需要对他们进行运算,而十字链表就是为了解决稀疏矩阵而出现的一种数据结构。 稀疏矩阵     ~~~~&...

         ~~~~     有需求才有供应,很多东西,都是为了解决实际问题才出现的,项目中出现了很多稀疏矩阵,而且需要对他们进行运算,而十字链表就是为了解决稀疏矩阵而出现的一种数据结构。

    稀疏矩阵

         ~~~~     稀疏矩阵(英语:sparse matrix),在数值分析中,是其元素大部分为零的矩阵。反之,如果大部分元素都非零,则这个矩阵是稠密的,通常这个系数被认为是5%。在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。
         ~~~~     在使用计算机存储和操作稀疏矩阵时,经常需要修改标准算法以利用矩阵的稀疏结构。由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。更为重要的是,由于过大的尺寸,标准的算法经常无法操作这些稀疏矩阵。

    三元组

         ~~~~     对于矩阵,我们第一想法就是使用二维数组来存储,但是稀疏矩阵的元素大部分都是零,而且稀疏矩阵的尺寸一般都比较大,这个时候我们如果直接使用二维数组,会浪费很多的空间,所有通常我们需要对稀疏矩阵进行压缩,三元组就是一种稀疏矩阵压缩保存的方法。
         ~~~~     三元组是指形如 ( ( x , y ) , z ) ((x,y),z) ((x,y),z)的集合(这就是说,三元组是这样的偶,其第一个射影亦是一个偶),常简记为 ( x , y , z ) (x,y,z) (x,y,z)
         ~~~~     三元组是计算机专业的一门公共基础课程——数据结构里的概念。主要是用来存储稀疏矩阵的一种压缩方式,也叫三元组表。
         ~~~~     三元组有不同的实现方法,假设以顺序表存储结构来表示三元组,称为三元组顺序表。
    结构如下

    #defube NAXSIZE 2500
    typedef struct{
        int i, j; //该非零元的行下标和列下标
        ElemType e;
    }Triple;
    typedef struct{
        Triple data[MAXSIZE + 1];//非零三元数组标,data[0]没有使用
        int mu, nu, tu;//矩阵的行数,列数,非零元个数
    }TSMatrix;
    

         ~~~~     注意,data域中表示非零元的三元组是以行序为主序顺序排列的,如果不排序,你会发现你操作和访问数据时,时间基本都花在查询数据上了。对于三元组,我们可以进行一些运算,都是很容易实现的,比如转置,相加,相减。
         ~~~~     三元组相比十字链表的缺点(暂时只能想到这些)

    • 1、增加或减少矩阵中的非零元素,都需要进行数据的移动
    • 2、大小固定,非零数据很少时,会浪费很多的空间,过多时无法保存
    • 3、查找元素比较慢(时间复杂度)
    • 4、矩阵的运算数据较慢(时间复杂度)

    十字链表

         ~~~~     十字链表(英语:Orthogonal linked list)是计算机科学中的一种高级数据结构,在Linux内核中应用广泛。具体说,一个二维十字链表是链表的元素同时链接左右水平邻结点与上下垂直邻结点。
         ~~~~     当稀疏矩阵的非零元个数和位置在操作过程中变化较大时,就不宜使用顺序表存储结构的三元组来保存稀疏矩阵;这个时候我们采用的时十字链表。
    十字链表节点结构

    typedef struct OLNode {    
         int  LineNumber, ColumneNumber;          //行号与列号     
         ElemType value;        //值     
         struct OLNode *right, *down;  //同行、同列下一个元素的指针     
    }OLNode, *OList;
    typedef struct{
        OList *rhead, *chead;    //行和列链表头指针向量基址
        int mu,nu,tu;            //稀疏矩阵的行数,列数和非零元个数
    }CrossList;
    

         ~~~~     每一个非零元可用一个含5个域的节点表示,其中i,j和e这3个域分别表示该非零元所在的行、列和非零元的值,向右域right用以链接同一行中下一个非零元,向下域down用来链接同一列下一个非零元,同一行的非零元通过right链接形成一个线性链表,同一列的非零元通过down链接形成一个线性表,每个非零元既是某个行链表中的节点,也是某一个列链表中的节点,整个矩阵构成了一个十字交叉的链表,而样的链表存储结构称为十字链表。
    在这里插入图片描述
    附上十字链表实现(百度抄的)

    #include <malloc.h>
    #include <stdio.h>
    /*十字链表的结构类型定义如下:*/
    typedef struct OLNode
    {
        int row,col; /*非零元素的行和列下标*/
        int 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)
    {
        int m, n, t, i, j, e;
        OLNode* p;
        OLNode* q;
        /*采用十字链表存储结构,创建稀疏矩阵M*/
         
    scanf("%d%d%d", &m,&n,&t); /*输入M的行数,列数和非零元素的个数*/
        M->m=m;
        M->n=n;
        M->len=t;
        if(!(M->row_head=(OLink *)malloc(m*sizeof(OLink))))
            exit(OVERFLOW);
        if(!(M->col_head=(OLink * )malloc(n*sizeof(OLink))))
            exit(OVERFLOW);
        /*初始化行、列,头指针指向量,各行、列链表为空的链表*/
        for(int h=0; h<m+1; h++)
        {
            M->row_head[h] = NULL;
        }
        for(int t=0; t<n+1; t++)
        {
            M->col_head[t] = NULL;
        }
        for(
    scanf("%d%d%d", &i,&j,&e); e!=0; scanf("%d%d%d", &i,&j,&e))
        {
            if(!(p=(OLNode *)malloc(sizeof(OLNode))))
                exit(
    OVERFLOW);
            p->row=i;
            p->col=j;
            p->value=e; /*生成结点*/
            if(M->row_head[i]==NULL)
                M->row_head[i]=p;
            p->right=NULL;
            else
            {
                /*寻找行表中的插入位置*/
                for(q=M->row_head[i]; 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;
            p->down=NULL;
            else
            {
                /*寻找列表中的插入位置*/
                for(q=M->col_head[j]; q->down&&q->down->row<i; q=q->down); /*空循环体*/
                p->down=q->down;
                q->down=p; /*完成插入*/
            }
        }
    }
    
    展开全文
  • 因此本文提出十字链表方法,将网络的拓扑结构与数值信息存于十字链表中,使其独立于计算,能保证数据的可重用性和灵活性。这种方法适用于与拓扑相关密切的电力系统计算,本文就潮流计算作简单介绍。
  • 在学习《数据结构(C语言版)》中第五章稀疏矩阵时,课本提示使用十字链表实现矩阵相加,没能运行,于是自己调试实现了下,希望对大家有帮助
  • 用C++编写的稀疏矩阵乘法运算,稀疏矩阵采用十字链表存储及计算
  • 数据结构课程设计 十字链表稀疏矩阵相加 本课程设计主要实现在十字链表存储结构下输入稀疏矩阵,并对稀疏矩阵进行相加,操作,最后输出运算后的结果。稀疏矩阵采用十字链表表示,并在不同的存储结构下,求两个具有...
  • 注意:这里是JAVA自学与了解的同步笔记与记录,如有问题欢迎指正说明 目录 前言: 一、关于十字链表 1.特殊情况下邻接表的局限 2.十字链表的结构与特点 二、十字链表的代码实现 1.基本属性 2.出边链接 3.入边链接 4....

    注意:这里是JAVA自学与了解的同步笔记与记录,如有问题欢迎指正说明

    目录

    前言:

    一、关于十字链表

    1.特殊情况下邻接表的局限

    2.十字链表的结构与特点

    二、十字链表的代码实现

    1.基本属性

    2.出边链接

    3.入边链接

    4.打印操作

    三、数据测试

    总结


    前言:

    最近到毕业季了,各种毕业需要处理的东西太多了,所以昨天时间又被耽误了没法继续更新文章,今天略得空闲,便更新下今日之内容。

    一、关于十字链表

    1.特殊情况下邻接表的局限

             下图是我们昨日提到的邻接表对于图的表示,这样的邻接表的链表部分连接的基础是以结点的出边为依据的,又名出边邻接表。在已知一个结点后我们通过邻接表的链表部分实现对于出边的访问,这个复杂度视具体的结点边的个数而定。但是在计算入边个数时,这样针对出边的邻接表似乎就显得有些笨拙了。我们需要遍历全部顺序表结构的顶点集然后逐步查看邻边,总的复杂度是确定的\(O(|V|+|E|)\)。但是由于现实问题中,大多数利用有向图时我们都讨论由出边引导的通向性问题;而无向图因为边的对偶特性,没有出边入边之分,所以往往不会担忧这种问题。

            但是如果说需要优化这种担忧,我们可以采用以入边为构造基础的入边邻接表。当然这样的方案有点因为芝麻丢了西瓜的味道,因为只考虑入边专门构造个数据结构而丢弃出边引导这种更为普遍的结构的方案有些冗余。因此,一种兼顾出边和入边的数据结构——十字链表出现了。

    2.十字链表的结构与特点

            今天描述这个数据结构关系时我改变昨日的那种存理论与代码分割的思路,今天我就直接按照今天代码会采用的结构来说明这个结构。在十字链表中,仿照邻接表,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点,但是我们代码为方便我们统一采用一种统一结构:

           这里的弧具有4个域,也是十字链表至少需要的参数域数目,其中尾域(row)和头域(column)分别表示弧的弧头与弧尾,但因为在图中其直观的指针指向具有方向性,所以这里以row / column命名从而体现一种直观性。链域nextIn指向弧头相同的下一条弧,简单来说就是指向我们的入边,并且多个入边相连构成入边链表。链域nextOut指向弧尾相同的下一条弧,简单来说就是指向我们的出边,并且多个出边相连构成出边链表。

     

            要理解十字链表这部分不能只靠文字,以图辅助,你就能恍然大悟:

     

             只要去掉链域nextIn,可以发现十字链表就变成了一个完全的出边邻接表(这个重要思想)而补上入边的指针后你就会发现:其实其实十字链表就是在出边邻接表的基础上给每个结点扩充了入边的链域,你可以在观看某个指针域的时候屏蔽其余指针域,这样全体的构造就变得清晰了。画图时,因为出边邻接表已经占据的横向的指针,所以我们在图示的时候入边指针域是纵向示意的,这就构成了指针之间纵横交错的感觉,可能这就是十字链表命名的来源。

            同时,因为边结点兼顾出边与入边的两重功能,自然的,结点自身所寄予的数值域空间也不能只是出边所代表的弧尾节点,还需要额外记录弧头以方便入边。

            通过十字链表,结点的入边和出边的访问就比较容易实现了,在特定情况采用十字链表能优化特定的问题。

    二、十字链表的代码实现

    1.基本属性

            基本属性与邻接表类似,只需要额外补充一些新的数据域即可。

        /**
    	 * An inner class for adjacent node.
    	 */
    	class OrthogonalNode {
    		/**
    		 * The row index.
    		 */
    		int row;
    
    		/**
    		 * The column index.
    		 */
    		int column;
    
    		/**
    		 * The next out node.
    		 */
    		OrthogonalNode nextOut;
    
    		/**
    		 * The next in node.
    		 */
    		OrthogonalNode nextIn;
    
    		/**
    		 *********************
    		 * The first constructor.
    		 * 
    		 * @param paraRow    The row.
    		 * @param paraColumn The column.
    		 *********************
    		 */
    		public OrthogonalNode(int paraRow, int paraColumn) {
    			row = paraRow;
    			column = paraColumn;
    			nextOut = null;
    			nextIn = null;
    		}// Of OrthogonalNode
    	}// Of class OrthogonalNode
    
    	/**
    	 * The number of nodes. This member variable may be redundant since it is always
    	 * equal to headers.length.
    	 */
    	int numNodes;
    
    	/**
    	 * The headers for each row.
    	 */
    	OrthogonalNode[] headers;

    2.出边链接

             之前在文中提到了十字链表的一个特性:去掉链域nextIn,可以发现十字链表就变成了一个完全的出边邻接表。那么我们可以在构造的前半部分完全无视nextIn域,模仿昨天的邻接表构造方法完成这部分:        

        numNodes = paraMatrix.length;
    
    	// Step 1. Initialize. The data in the headers are not meaningful.
    	OrthogonalNode tempPreviousNode, tempNode;
    	headers = new OrthogonalNode[numNodes];
    
    	// Step 2. Link to its out nodes.
    	for (int i = 0; i < numNodes; i++) {
    		headers[i] = new OrthogonalNode(i, -1);
    		tempPreviousNode = headers[i];
    		for (int j = 0; j < numNodes; j++) {
    			if (paraMatrix[i][j] == 0) {
    				continue;
    			} // Of if
    
    			// Create a new node.
    			tempNode = new OrthogonalNode(i, j);
    
    			// Link.
    			tempPreviousNode.nextOut = tempNode;
    			tempPreviousNode = tempNode;
    		} // Of for j
    	} // Of for i

            初始化不再赘述, 初始tempPreviousNode变量作为每条入边链的链表头(tempPreviousNode = headers[i];),同时,在遍历中不断迭代,持续作为尾节点的身份出现,以方便每次读取邻接矩阵而生成的新结点能插入到尾节点后以扩展链表。 注意结点创建初始化是以基础结点(也就基于哪个顶点来讨论邻边)为弧头,得到的邻边为弧尾,因此有代码:tempNode = new OrthogonalNode(i, j); 这里记录的弧尾值是后续定义入边的关键。

    3.入边链接

            入边连接是十字链表构造的一个麻烦点。因为记录入边是个连续的过程,它也是一个链表,所以我们需要有个时刻记录某类编号的上次入边的结点。简单来说,构造了编号为i顶点的入边后,下次再发现了顶点i的入边后我们需要在上次的入边结点后方进一步插入,因此需要记录对应i顶点的上一次连接的入边结点。而i是一系列值,因此可以设置一个十字链表数据项数组tempColumnNodes,初始将其按照Header赋值(最开始无任何入边连接)。

    	// Step 3. Link to its in nodes. This step is harder.
    	OrthogonalNode[] tempColumnNodes = new OrthogonalNode[numNodes];
    	for (int i = 0; i < numNodes; i++) {
    		tempColumnNodes[i] = headers[i];
    	} // Of for i
    	
    	for (int i = 0; i < numNodes; i++) {
    		tempNode = headers[i].nextOut;
    		while (tempNode != null) {
    			tempColumnNodes[tempNode.column].nextIn = tempNode;
    			tempColumnNodes[tempNode.column] = tempNode;
    
    			tempNode = tempNode.nextOut;
    		} // Of while
    	} // Of for i

            操作前,每个边结点都被一个指针所指(被兄弟边或者弧头顶点所指),并且都指出一个指针(指向兄弟边)

             但是要构成一个十字链表还差一个指向别人和别人指向自己的指针。为了同时解决这个问题,我们按照顺序对于每个边结点进行访问,并且在每次访问时,根据边的弧尾顶点值查询到需要统计入边的结点。就那上面这次针对顶点\(v_0\)的出边遍历,我们就能在访问这两个兄弟边同时通过查询column(弧尾顶点值)域的值得到1与2,这里的含义就是说明\(v_1\)顶点与\(v_2\)顶点的入边需要讨论。

            怎么讨论呢,很简单,比如设上图中出边链的最后那个边结点为\(\alpha \);通过查询\(\alpha \)的column(弧尾顶点值)值得到了2,这个2代表了这个弧的弧尾为\(v_2\),故去讨论\(v_2\)的入边。这时的操作是取出\(v_2\)的入边链表的尾节点,并在这个尾节点插入边结点为\(\alpha \),并且设置边结点为\(\alpha \)为新的尾节点。这样有什么好处呢,首先,下一次再有人发现要讨论\(v_2\)的入边时就能直接查询到\(\alpha \)这个新的尾节点并且继续尾插,从而形成一个入边链表的维护;其次,下一次再\(v_2\)讨论便需要去尾插\(\alpha \),这样就顺利补充了\(\alpha \)边结点的额外一个被指向指针和指出指针,解决了我们的担忧。

            代码中,通过tempColumnNodes[tempNode.column]查询到顶点编号为tempNode.column的最近一次链入入边链表的尾部,从而链入,链入后由尾插原则,自身变成新尾部。

    4.打印操作

    	/**
    	 *********************
    	 * Overrides the method claimed in Object, the superclass of any class.
    	 *********************
    	 */
    	public String toString() {
    		String resultString = "Out arcs: ";
    
    		OrthogonalNode tempNode;
    		for (int i = 0; i < numNodes; i++) {
    			tempNode = headers[i].nextOut;
    
    			while (tempNode != null) {
    				resultString += " (" + tempNode.row + ", " + tempNode.column + ")";
    				tempNode = tempNode.nextOut;
    			} // Of while
    			resultString += "\r\n";
    		} // Of for i
    
    		resultString += "\r\nIn arcs: ";
    
    		for (int i = 0; i < numNodes; i++) {
    			tempNode = headers[i].nextIn;
    
    			while (tempNode != null) {
    				resultString += " (" + tempNode.row + ", " + tempNode.column + ")";
    				tempNode = tempNode.nextIn;
    			} // Of while
    			resultString += "\r\n";
    		} // Of for i
    
    		return resultString;
    	}// Of toString
    

             打印操作中分别打印了每个结点的入边链和出边链。

    三、数据测试

            测试代码如下:

        /**
    	 *********************
    	 * The entrance of the program.
    	 * 
    	 * @param args Not used now.
    	 *********************
    	 */
    	public static void main(String args[]) {
    		int[][] tempMatrix = { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 1, 0 } };
    		OrthogonalList tempList = new OrthogonalList(tempMatrix);
    		System.out.println("The data are:\r\n" + tempList);
    	}// Of main

            图结构如图:

            测试结果如下:

    总结

            十字链表这种结构我接触的确实不算很多,准确来说,确乎是没有用过。第一次接触是在本科的数据结构的课程上。要问我对于这种结构的看法,就像是对于邻接表两种方案(入边/出边)的兼容版本。相比于一次分别创建个出边邻接表和入边邻接表,其灵活利用结点关系实现了数据的复用,避免了冗余。这个方案对于边信息比庞大的图同时又要同时考虑出边和入边的问题具有比较好的对策性。

            对于一个算法问题的数据结构改进不一定说选择一个最好的就好了,多结构组合才是更常见的方案。或者像今天所了解的十字链表这样,通过邻接表针对部分问题的局限为思路出发点,对结构不足进行改造而设计出更有针对性的结构。我随便举个组合,比如通过哈希表、链表、顺序表设计出一种复合的兼容\(O(1)\)的查询与\(O(1)\)插入删除线性结构等等。

            总之要认识到数据结构并不是独立的,他们就像积木,使用他们的过程就像搭积木,合理搭建出针对自己问题最好的结构才是好的数据结构。

    展开全文
  • 数据结构_十字链表(C语言)

    千次阅读 2021-03-29 20:03:29
    十字链表 1. 十字链表图文解析 十字链表是有向图的一种存储结构 在十字链表里我们称每一条有向边为:弧 十字链表的存储结构主要包括:弧结点和顶点结点,如下图: 由以上结构组成的有向图如下: 红线:与邻接表...

    数据结构总目录

    十字链表

    1. 图文解析

    在无向图中,两个顶点之间的连接我们称之为边;
    在这里插入图片描述
    而在有向图中,两个顶点之间具有方向的连接称之为英文:Arc
    如下图中弧(A->B)的权值=10,其中A为该弧的头顶点,B为该弧的尾顶点
    在这里插入图片描述
    也可以理解为在无向图中每条边都存在两条弧

    十字链表的结构和邻接表的结构较为相似,同样采用了顺序表与链表结构的结合,但在十字链表中存在两个链表,分别用于表示相同头顶点和尾顶点的弧链表。

    边结点结构图
    在这里插入图片描述
    顶点结点结构图
    在这里插入图片描述

    图与十字链表

    在这里插入图片描述

    1、在十字链表中,如果仅看相同头顶点的弧链表,其结构和邻接表相同,采用头插法插入弧结点在这里插入图片描述
    2、对于相同尾结点的弧链表,实际上就是在已插入的弧结点中,对相同尾顶点的弧结点进行链接,其操作也是链表的头插法。
    在这里插入图片描述

    2. 源代码

    #include <stdio.h>
    #include <stdlib.h>
    #define MaxVex 20
    
    typedef int ArcType;
    typedef char VertexType;
    
    // 弧结点结构
    typedef struct ArcNode
    {
        ArcType arcData;        // 弧的数据
        int headVertex, tailVertex;   // 弧的头顶点和尾顶点
        struct ArcNode *nextHeadArc, *nextTailArc;  // 指向相同头、尾顶点的弧指针 
    }ArcNode, *ArcList;
    
    // 顶点结点结构
    typedef struct VertexNode
    {
        VertexType vertexData;      // 顶点的数据
        ArcList headList, tailList; // 相同头、尾顶点的弧链表
    }VertexNode, *VertexList;
    
    // 十字链表结构
    typedef struct
    {
        VertexList vertexList;
        int numVertexs, numArcs;
    }OLGraph;
    
    // 初始化十字链表
    void InitOLGraph(OLGraph *G)
    {
        // 初始化顶点
        G->numVertexs = 0;
        G->numArcs = 0;
        G->vertexList = (VertexNode *)malloc(MaxVex * sizeof(VertexNode));
        // 初始化顶点的两个链表头结点(也可不带头结点)
        int i;
        for (i = 0; i < MaxVex; i++)
        {
            // 相同头顶点的弧链表
            G->vertexList[i].headList = (ArcNode *)malloc(sizeof(ArcNode));
            G->vertexList[i].headList->nextHeadArc = NULL;
            G->vertexList[i].headList->nextTailArc = NULL;
            // 相同尾顶点的弧链表
            G->vertexList[i].tailList = (ArcNode *)malloc(sizeof(ArcNode));
            G->vertexList[i].tailList->nextHeadArc = NULL;
            G->vertexList[i].tailList->nextTailArc = NULL;
        }
        printf("已初始化十字链表!\n");
    }
    
    // 创建十字链表
    void CreateOLGraph(OLGraph *G)
    {
        printf("请输入顶点数和弧数:");
        scanf("%d %d", &G->numVertexs, &G->numArcs);
        // 输入顶点数据
        int i, j, k;
        for (i = 0; i < G->numVertexs; i++)
        {
            fflush(stdin);
            printf("请输入第%d个顶点信息:", i + 1);
            scanf("%c", &G->vertexList[i].vertexData);
        }
        // 输入弧结点数据
        ArcType w;
        for (k = 0; k < G->numArcs; k++)
        {
            printf("请输入弧(Ai, Aj)的头、尾顶点及其权值:");
            scanf("%d %d %d", &i, &j, &w);
            
            // 创建新的弧结点,并设置该弧结点的数据和头尾顶点的下标
            ArcNode *s;
            s = (ArcNode *)malloc(sizeof(ArcNode));
            s->arcData = w;
            s->headVertex = i - 1;
            s->tailVertex = j - 1;
            
            // 头插法插入相同头顶点的弧链表
            s->nextHeadArc = G->vertexList[i - 1].headList->nextHeadArc;
            G->vertexList[i - 1].headList->nextHeadArc = s;
    
            // 头插法插入相同尾顶点的弧链表
            s->nextTailArc = G->vertexList[j - 1].tailList->nextTailArc;
            G->vertexList[j - 1].tailList->nextTailArc = s;
        }
        printf("已完成十字链表的创建!\n");
    }
    
    void DisplayOLGraph(OLGraph G)
    {
        int i;
        ArcNode *p;
        for (i = 0; i < G.numVertexs; i++)
        {
            printf("顶点:%c\n", G.vertexList[i].vertexData);
            // 相同头顶点的弧链表
            printf("\t相同头顶点的弧:");
            p = G.vertexList[i].headList;
            while (p->nextHeadArc)
            {
                p = p->nextHeadArc;
                printf("(%c)%d(%c) => ", 
                G.vertexList[p->headVertex].vertexData,
                p->arcData, 
                G.vertexList[p->tailVertex].vertexData);
            }
            printf("NULL\n");
            // 相同尾顶点的弧链表
            printf("\t相同尾顶点的弧:");
            p = G.vertexList[i].tailList;
            while (p->nextTailArc)
            {
                p = p->nextTailArc;
                printf("(%c)%d(%c) => ", 
                G.vertexList[p->headVertex].vertexData,
                p->arcData, 
                G.vertexList[p->tailVertex].vertexData);
            }
             printf("NULL\n");
        }
    }
    
    int main()
    {
        OLGraph G;
        InitOLGraph(&G);
        CreateOLGraph(&G);
        DisplayOLGraph(G);
        system("pause");
        return 0;
    }
    

    3. 测试结果

    在这里插入图片描述

    展开全文
  • 十字链表存储稀疏矩阵

    千次阅读 2021-11-23 10:29:03
    // 因为没有开辟新的空间,原来的结构不变,因此不需要对列进行操作,直接返回即可 } } // 将稀疏矩阵转换成十字链表存储 SNodePtr Matrix2List(DataType **pparr, int row, int column) { SNodePtr phead = ...
  • 对于压缩存储稀疏矩阵,无论是使用三元组顺序,还是使用行逻辑链接的顺序,归根结底是使用数组存储稀疏矩阵。介于数组 “不利于插入和删除数据” 的特点,以上两种压缩存储方式都不适合解决类似 “向矩阵中添加...
  • 图的存储之十字链表

    2022-01-23 14:43:54
    图的存储之十字链表:涉及概念详细介绍,代码实现。
  • 前面介绍了图的邻接表存储法,本节继续讲解图的另一种链式存储结构——十字链表法。 与邻接表不同,十字链表法仅适用于存储有向图和有向网。不仅如此,十字链表法还改善了邻接表计算图中顶点入度的问题。 十字链表...
  • 十字链表实现稀疏矩阵的加法
  • 十字链表实现稀疏矩阵的加法、减法、乘法、转置、求最值、插入、查看、删除等基本功能,菜单栏采用hash表存储稀疏矩阵,给每个矩阵存储一个名字,hash函数进行寻找。
  • 十字链表(icoding)

    千次阅读 2021-08-04 12:15:00
    十字链表相关定义如下: typedef int ElemType; // 非零元素结点结构 typedef struct OLNode { int row,col; ElemType value; struct OLNode *right,*down; }OLNode,*OLink; // 十字链表结构 typedef struct ...
  • 十字链表存储稀疏矩阵,可以起到节省空间的作用。 十字链表作为多重链表的一种,其结点分为两种: 类型1:数据域为另一个单链表的头指针。 类型2:数据域为待存储的数据。 其中,“十字”体现在:每一个存储...
  • 数据结构 图 十字链表 严蔚敏 数据结构 图 十字链表 严蔚敏 数据结构 图 十字链表 严蔚敏 数据结构 图 十字链表 严蔚敏 数据结构 图 十字链表 严蔚敏
  • 十字链表法表示矩阵例如,用十字链表法表示矩阵 A ,为:图2 矩阵用十字链表法表示由此可见,采用十字链表表示矩阵时,矩阵的每一行和每一个列都可以看作是一个单独的链表,而之所以能够表示矩阵,是因...
  • 十字链表、邻接多重表
  • 十字链表—— 头文件利用结构体声明元素节点利用结构体声明矩阵节点构造初始化十字链表矩阵的函数构造展示十字链表的函数—— 主函数 —— 头文件 #include <stdio.h> #include <stdlib.h> 利用结构体...
  • c++语言,用十字链表根据输入的矩阵的行数、列数、非零元数、实现矩阵的加、减、乘、转置、求逆运算,并输出矩阵。
  • 十字链表矩阵相乘代码实现--C语言

    千次阅读 2022-03-10 20:29:31
    两个稀疏矩阵的乘法算法的实现——十字链表矩阵相乘 ,附带源代码可直接运行 dev c++
  • 图存储之十字链表

    2020-10-17 15:10:51
    十字链表是有向图的一种链式存储结构,在十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点。 二 十字链表 十字链表的结构分为弧结点和顶点结点,其中弧结点中有5个域:尾域和头域分别...
  • 数据结构 图论 十字链表详解 代码 阅读之前请了解先了解邻接表邻接表基础 数据结构 上面的数组+链表可以节约一些空间和方便增删,但是我们要计算一个顶点的度还是比较麻烦,十字链表就是解决计算顶点入度(就是有...
  • 对于压缩存储稀疏矩阵,无论是使用三元组顺序,还是使用行逻辑链接的顺序,归根结底是使用数组存储稀疏矩阵。介于数组 "不利于插入和删除数据" 的特点,以上两种压缩存储方式都不适合解决类似 "...
  • 数据结构——十字链表(C语言实现)

    千次阅读 多人点赞 2020-11-09 17:22:26
    十字链表是将邻接表和逆邻接表结合在一起的一种有向图的数据结构 十字链表的节点结构体表示的是一个节点到另一个节点的边,并且此由指出节点(from)和指入节点(to)共同使用,因此大大节省了内存。 先直观感受一下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,502
精华内容 8,200
关键字:

十字链表