C语言数据结构-数组广义表-十字链表-实现十字链表的初始化操作-实现十字链表的删除操作

深藏阁楼爱情的钟 2023-01-13 04:04 33阅读 0赞

# 十字链表 #

十字链表相关定义如下：

typedef int ElemType;
    
    // 非零元素结点结构
    typedef struct OLNode
    {
        int row,col;
        ElemType value;
        struct OLNode *right,*down;
    }OLNode,*OLink;
    
    // 十字链表结构
    typedef struct
    {
        OLink *rowhead,*colhead;
        int rows,cols,nums;
    }CrossList, *PCrossList;

1）实现十字链表的初始化操作：

int init_cross_list(PCrossList L, const ElemType *A, int m, int n);

其中 L 指向 CrossList 结构，且各成员已被初始化为0；  
A 为 ElemType 类型数组中第一个元素的地址，元素的个数为 m×n 个，按行优先存储（即A\[0\] 为十字链表第1行第1列的元素；  
A\[1\] 为第1行第2列的元素，A\[n\] 为第2行第1列的元素，A\[n+1\] 为第2行第2个元素）；  
m 表示十字链表的行数，n 表示十字链表的列数。  
init\_cross\_list 函数将 ElemType 数组中非0元素保存到十字链表中，函数返回非 0 元素的个数。

2）实现十字链表的删除操作：

int del_cross_list(PCrossList L, ElemType k);

其中 L 指向 要处理的 CrossList 结构，k 为要删除的元素；  
del\_cross\_list 函数删除十字链表中所有值为 k 的结点，并返回删除结点的个数。

**提供代码**

#include <stdio.h>
    #include <stdlib.h>
    #include "crosslist.h"
    
    int init_cross_list(PCrossList L, const ElemType *A, int m,int n){
    
    }
    
    
    int del_cross_list(PCrossList L, ElemType k){
    
    }

**参考代码**

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    //#include "crosslist.h"
    
    typedef int ElemType;
    
    // 非零元素结点结构
    typedef struct OLNode
    {
        int row, col;
        ElemType value;
        struct OLNode* right, * down;
    }OLNode, * OLink;
    
    // 十字链表结构
    typedef struct
    {
        OLink* rowhead, * colhead;
        int rows, cols, nums;
    }CrossList, * PCrossList;
    
    
    int init_cross_list(PCrossList L, const ElemType* A, int m, int n)
    {
        int i, j, sum = 0;
        OLNode* p, * q;
        L->rows = m;
        L->cols = n;
        if (!(L->rowhead = (OLink*)malloc((m + 1) * (sizeof(OLink)))))
            return 0;
        if (!(L->colhead = (OLink*)malloc((n + 1) * (sizeof(OLink)))))
            return 0;
        for (i = 0; i < m; i++) {
            L->rowhead[i] = NULL;
        }
        for (i = 0; i < n; i++) {
            L->colhead[i] = NULL;
        }
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (A[i * n + j] != 0) {
                    sum++;
                    if (!(p = (OLNode*)malloc(sizeof(OLNode))))
                        return 0;
                    p->row = i;
                    p->col = j;
                    p->value = A[i * n + j];
                    if (L->rowhead[i] == NULL || L->rowhead[i]->col > j) {
                        p->right = L->rowhead[i];
                        L->rowhead[i] = p;
                    }
                    else {
                        for (q = L->rowhead[i]; (q->right) && (q->right->col < j); q = q->right)
                            ;
                        p->right = q->right;
                        q->right = p;
                    }
                    if (L->colhead[j] == NULL || L->colhead[j]->row > i) {
                        p->down = L->colhead[j];
                        L->colhead[j] = p;
                    }
                    else {
                        for (q = L->colhead[j]; (q->down) && (q->down->row < i); q = q->down)
                            ;
                        p->down = q->down;
                        q->down = p;
                    }
                }
            }
        }
        L->nums = sum;
        return sum;
    }
    void delete_crossList(PCrossList clist, int row, int col, int k)
    {
        OLNode* tmp = NULL;
        OLNode* tmp1 = NULL;
        OLNode* tmp2 = NULL;
    
        OLNode* t = NULL;
        OLNode* t1 = NULL;
        OLNode* t2 = NULL;
    
        //删除一个结点需要修改行结点指针和列结点指针
        tmp = clist->rowhead[row];
        t = clist->colhead[col];
        if (tmp->value == k) {
            clist->rowhead[row] = tmp->right;
        }
        if (t->value == k) {
            clist->colhead[col] = t->down;
        }
        if (t->value == k) {
            free(t);
            return;
        }
        //行遍历元素
        while (tmp) {
            tmp1 = tmp;
            tmp = tmp->right;
            if (tmp && tmp->row == row && tmp->col == col) {
                tmp2 = tmp;
                tmp1->right = tmp2->right;
                break;
            }
        }
        //列遍历元素
        while (t) {
            t1 = t;
            t = t->down;
            if (t && t->row == row && t->col == col) {
                t2 = t;
                t1->down = t2->down;
                break;
            }
        }
        free(t);
        clist->nums--;
    }
    int del_cross_list(PCrossList L, ElemType k)
    {
        OLink pt;
        int i, j;
        int sum = 0;
        for (i = 0; i < L->rows; i++) {
            pt = L->rowhead[i];
            for (j = 0; j < L->cols; j++) {
                if (pt && pt->col == j) {
                    if (pt->value == k) {
                        delete_crossList(L, i, j, k);
                        sum++;
                    }
                    pt = pt->right;
                }
            }
            printf("\n");
        }
        return sum;
    }
    
    void test01()
    {
        CrossList L;
        int m = 3, n = 4;
        int A[21] = { 0, 0, 0, 8, 0, 0, 73, 0, 0, 0, 0, 67 };
        init_cross_list(&L, A, m, n);
        del_cross_list(&L, 8);
    }
    
    void main()
    {
        test01();
        return 0;
    }

**十字链表实例**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

**十字链表相关知识**

[https://blog.csdn.net/aiqq136/article/details/115303041][https_blog.csdn.net_aiqq136_article_details_115303041]

**手写过程**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/cf0b7a9b71344598adf7c03d7e67ba37.png
[https_blog.csdn.net_aiqq136_article_details_115303041]: https://blog.csdn.net/aiqq136/article/details/115303041
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221022/ce4afbe7ca854e40a549f8ae96854b72.png