devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构(6_2_3)——十字链表法和多重领接表

作者：IT小白 | 2024-08-22 02:46:18

赞

踩

数据结构(6_2_3)——十字链表法和多重领接表

十字链表存储有向图

橙色入度，绿色出度

 代码示例：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 定义十字链表节点结构体
  5. typedef struct OLNode {
  6.     int row;         // 行号
  7.     int col;         // 列号
  8.     int value;       // 节点值
  9.     struct OLNode* right; // 指向右边节点的指针
  10.     struct OLNode* down;  // 指向下方节点的指针
  11. } OLNode, * OLink;
  12.  
  13. // 定义十字链表的头节点结构体
  14. typedef struct {
  15.     OLink* row_head; // 行表头指针数组
  16.     OLink* col_head; // 列表头指针数组
  17.     int m, n, len;   // 矩阵的行数、列数和非零元素的个数
  18. } CrossList;
  19. // 创建十字链表
  20. CrossList CreateCrossList(int m, int n) {
  21.     CrossList M;
  22.     M.m = m;
  23.     M.n = n;
  24.     M.len = 0;
  25.  
  26.     // 初始化行和列的头指针数组
  27.     M.row_head = (OLink*)malloc((m + 1) * sizeof(OLink));
  28.     M.col_head = (OLink*)malloc((n + 1) * sizeof(OLink));
  29.     if (!M.row_head || !M.col_head) {
  30.         exit(1); // 内存分配失败
  31.     }
  32.  
  33.     for (int i = 1; i <= m; i++) {
  34.         M.row_head[i] = NULL;
  35.     }
  36.     for (int j = 1; j <= n; j++) {
  37.         M.col_head[j] = NULL;
  38.     }
  39.  
  40.     return M;
  41. }
  42. // 向十字链表插入元素
  43. void Insert(CrossList* M, int i, int j, int value) {
  44.     if (i > M->m || j > M->n || value == 0) {
  45.         return; // 插入位置不合法或值为0
  46.     }
  47.  
  48.     // 创建新节点
  49.     OLNode* newNode = (OLNode*)malloc(sizeof(OLNode));
  50.     newNode->row = i;
  51.     newNode->col = j;
  52.     newNode->value = value;
  53.     newNode->right = NULL;
  54.     newNode->down = NULL;
  55.  
  56.     // 插入行
  57.     if (M->row_head[i] == NULL) {
  58.         M->row_head[i] = newNode;
  59.     }
  60.     else {
  61.         OLNode* current = M->row_head[i];
  62.         while (current->right && current->right->col < j) {
  63.             current = current->right;
  64.         }
  65.         newNode->right = current->right;
  66.         current->right = newNode;
  67.     }
  68.  
  69.     // 插入列
  70.     if (M->col_head[j] == NULL) {
  71.         M->col_head[j] = newNode;
  72.     }
  73.     else {
  74.         OLNode* current = M->col_head[j];
  75.         while (current->down && current->down->row < i) {
  76.             current = current->down;
  77.         }
  78.         newNode->down = current->down;
  79.         current->down = newNode;
  80.     }
  81.  
  82.     M->len++; // 更新非零元素个数
  83. }
  84. // 从十字链表删除元素
  85. void Delete(CrossList* M, int i, int j) {
  86.     if (i > M->m || j > M->n) {
  87.         return; // 位置不合法
  88.     }
  89.  
  90.     // 查找要删除的节点
  91.     OLNode* p = M->row_head[i];
  92.     while (p && p->col < j) {
  93.         p = p->right;
  94.     }
  95.  
  96.     if (p && p->col == j) {
  97.         // 删除行中的节点
  98.         if (p == M->row_head[i]) {
  99.             M->row_head[i] = p->right;
  100.         }
  101.         else {
  102.             OLNode* q = M->row_head[i];
  103.             while (q->right != p) {
  104.                 q = q->right;
  105.             }
  106.             q->right = p->right;
  107.         }
  108.  
  109.         // 删除列中的节点
  110.         if (p == M->col_head[j]) {
  111.             M->col_head[j] = p->down;
  112.         }
  113.         else {
  114.             OLNode* q = M->col_head[j];
  115.             while (q->down != p) {
  116.                 q = q->down;
  117.             }
  118.             q->down = p->down;
  119.         }
  120.  
  121.         free(p); // 释放节点内存
  122.         M->len--; // 更新非零元素个数
  123.     }
  124. }
  125. // 在十字链表中查找元素
  126. OLNode* Find(CrossList M, int i, int j) {
  127.     if (i > M.m || j > M.n) {
  128.         return NULL; // 位置不合法
  129.     }
  130.  
  131.     OLNode* p = M.row_head[i];
  132.     while (p && p->col < j) {
  133.         p = p->right;
  134.     }
  135.  
  136.     if (p && p->col == j) {
  137.         return p; // 找到元素，返回节点指针
  138.     }
  139.     else {
  140.         return NULL; // 未找到元素
  141.     }
  142. }
  143. // 打印十字链表
  144. void PrintCrossList(CrossList M) {
  145.     printf("十字链表如下：\n");
  146.     for (int i = 1; i <= M.m; i++) {
  147.         OLNode* p = M.row_head[i];
  148.         while (p) {
  149.             printf("(%d, %d, %d) ", p->row, p->col, p->value);
  150.             p = p->right;
  151.         }
  152.         printf("\n");
  153.     }
  154. }
  155. // 释放十字链表
  156. void FreeCrossList(CrossList* M) {
  157.     for (int i = 1; i <= M->m; i++) {
  158.         OLNode* p = M->row_head[i];
  159.         while (p) {
  160.             OLNode* q = p;
  161.             p = p->right;
  162.             free(q);
  163.         }
  164.     }
  165.     free(M->row_head);
  166.     free(M->col_head);
  167. }
  168. int main() {
  169.     int m = 3, n = 4; // 定义一个3行4列的稀疏矩阵
  170.     CrossList M = CreateCrossList(m, n); // 创建十字链表
  171.  
  172.     // 插入元素
  173.     Insert(&M, 1, 2, 12);
  174.     Insert(&M, 1, 4, 9);
  175.     Insert(&M, 3, 1, -3);
  176.     Insert(&M, 3, 3, 14);
  177.  
  178.     // 打印十字链表
  179.     PrintCrossList(M);
  180.  
  181.     // 删除元素
  182.     Delete(&M, 1, 2);
  183.  
  184.     // 再次打印十字链表
  185.     printf("删除元素后的十字链表：\n");
  186.     PrintCrossList(M);
  187.  
  188.     // 释放十字链表
  189.     FreeCrossList(&M);
  190.  
  191.     return 0;
  192. }
  193.

 十字链表法性能分析

 

领接矩阵、邻接表存储无向图的缺点

邻接多重表存储无向图 

优点：

每一条边只对应一个边结点，没有冗余数据，删除结点或者删除边的时候会方便很多

 

 代码示例：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // 定义邻接多重表的边节点结构体
  5. typedef struct EdgeNode {
  6.     int ivex;            // 边的起点
  7.     int jvex;            // 边的终点
  8.     struct EdgeNode* ilink; // 指向起点相同的下一条边
  9.     struct EdgeNode* jlink; // 指向终点相同的下一条边
  10.     int mark;            // 标记边是否被访问过
  11. } EdgeNode;
  12.  
  13. // 定义邻接多重表的顶点节点结构体
  14. typedef struct VertexNode {
  15.     int data;            // 顶点数据
  16.     EdgeNode* firstedge; // 指向第一条依附于该顶点的边
  17. } VertexNode;
  18.  
  19. // 定义邻接多重表结构体
  20. typedef struct {
  21.     VertexNode* vertices; // 顶点表
  22.     int vexnum, edgenum;  // 顶点数和边数
  23. }AMLGraph;
  24. // 创建邻接多重表
  25. AMLGraph CreateAMLGraph(int vexnum, int edgenum) {
  26.     AMLGraph graph;
  27.     graph.vexnum = vexnum;
  28.     graph.edgenum = edgenum;
  29.  
  30.     // 初始化顶点表
  31.     graph.vertices = (VertexNode*)malloc(vexnum * sizeof(VertexNode));
  32.     if (!graph.vertices) {
  33.         exit(1); // 内存分配失败
  34.     }
  35.  
  36.     for (int i = 0; i < vexnum; i++) {
  37.         graph.vertices[i].data = i;
  38.         graph.vertices[i].firstedge = NULL;
  39.     }
  40.  
  41.     return graph;
  42. }
  43. // 插入边
  44. void InsertEdge(AMLGraph* graph, int ivex, int jvex) {
  45.     // 创建边节点
  46.     EdgeNode* newEdge = (EdgeNode*)malloc(sizeof(EdgeNode));
  47.     newEdge->ivex = ivex;
  48.     newEdge->jvex = jvex;
  49.     newEdge->ilink = graph->vertices[ivex].firstedge;
  50.     newEdge->jlink = graph->vertices[jvex].firstedge;
  51.     newEdge->mark = 0;
  52.  
  53.     // 插入到顶点ivex的边表
  54.     graph->vertices[ivex].firstedge = newEdge;
  55.  
  56.     // 插入到顶点jvex的边表
  57.     graph->vertices[jvex].firstedge = newEdge;
  58. }
  59. // 删除边
  60. void DeleteEdge(AMLGraph* graph, int ivex, int jvex) {
  61.     EdgeNode* p = graph->vertices[ivex].firstedge;
  62.     EdgeNode* pre = NULL;
  63.  
  64.     while (p && (p->ivex != ivex || p->jvex != jvex)) {
  65.         pre = p;
  66.         if (p->ivex == ivex) {
  67.             p = p->ilink;
  68.         }
  69.         else {
  70.             p = p->jlink;
  71.         }
  72.     }
  73.  
  74.     if (p) {
  75.         if (pre) {
  76.             if (p->ivex == ivex) {
  77.                 pre->ilink = p->ilink;
  78.             }
  79.             else {
  80.                 pre->jlink = p->jlink;
  81.             }
  82.         }
  83.         else {
  84.             if (p->ivex == ivex) {
  85.                 graph->vertices[ivex].firstedge = p->ilink;
  86.             }
  87.             else {
  88.                 graph->vertices[jvex].firstedge = p->jlink;
  89.             }
  90.         }
  91.         free(p);
  92.     }
  93. }
  94. // 查找顶点
  95. VertexNode* FindVertex(AMLGraph graph, int data) {
  96.     for (int i = 0; i < graph.vexnum; i++) {
  97.         if (graph.vertices[i].data == data) {
  98.             return &graph.vertices[i];
  99.         }
  100.     }
  101.     return NULL;
  102. }
  103. // 打印邻接多重表
  104. void PrintAMLGraph(AMLGraph graph) {
  105.     printf("邻接多重表如下：\n");
  106.     for (int i = 0; i < graph.vexnum; i++) {
  107.         EdgeNode* p = graph.vertices[i].firstedge;
  108.         while (p) {
  109.             int ivex = p->ivex;
  110.             printf("(%d, %d) ", ivex, jvex);
  111.             // 根据当前顶点，决定移动到ilink还是jlink
  112.             if (ivex == i) {
  113.                 p = p->ilink;
  114.             }
  115.             else {
  116.                 p = p->jlink;
  117.             }
  118.         }
  119.         printf("\n");
  120.     }
  121. }
  122. // 释放邻接多重表
  123. void FreeAMLGraph(AMLGraph* graph) {
  124.     for (int i = 0; i < graph->vexnum; i++) {
  125.         EdgeNode* p = graph->vertices[i].firstedge;
  126.         while (p) {
  127.             EdgeNode* q = p;
  128.             p = p->ilink;
  129.             free(q);
  130.         }
  131.     }
  132.     free(graph->vertices);
  133. }
  134. int main() {
  135.     int vexnum = 4; // 定义顶点数为4
  136.     int edgenum = 5; // 定义边数为5
  137.     AMLGraph graph = CreateAMLGraph(vexnum, edgenum); // 创建邻接多重表
  138.  
  139.     // 插入边
  140.     InsertEdge(&graph, 0, 1);
  141.     InsertEdge(&graph, 0, 2);
  142.     InsertEdge(&graph, 1, 2);
  143.     InsertEdge(&graph, 1, 3);
  144.     InsertEdge(&graph, 2, 3);
  145.  
  146.     // 打印邻接多重表
  147.     PrintAMLGraph(graph);
  148.  
  149.     // 删除边
  150.     DeleteEdge(&graph, 1, 2);
  151.  
  152.     // 再次打印邻接多重表
  153.     printf("删除边后的邻接多重表：\n");
  154.     PrintAMLGraph(graph);
  155.  
  156.     // 释放邻接多重表
  157.     FreeAMLGraph(&graph);
  158.  
  159.     return 0;
  160. }
  161.


总结：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/1014444
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号