題目

??Qestion:?完成用十字鏈表存儲的稀疏矩陣的加法運算。

主要思路

1. 獲取兩個稀疏矩陣總有多少個非零元素，記作cnt。
2. 當cnt 不為零時一直循環(huán)，每循環(huán)一次i++，也就是行循環(huán)，每循環(huán)一次就轉移至下一行。
3. 先從第一行開始循環(huán)，使得兩個工作指針p、q分別指向兩個稀疏矩陣的第一行第一個非零元。對當前行p、q有無元素個數(shù)進行判斷，下面是會遇到的四種情況：
   • p當前行無元素并且q有元素：則將賦值給p，也就是q當前行的元素全部都接在了p之后
   • p、q當前行均無元素：則跳出當前循環(huán)，令i+1，進入下一行也就是下一個循環(huán)
   • p當前行有元素、q無元素：則跳出當前循環(huán)，轉移至下行
   • p、q當前行均有元素：則進行下述循環(huán)。

思路偽代碼

完整代碼

// 完成用十字鏈表存儲的稀疏矩陣的加法運算。
typedef struct OLNode
{
    int i;
    int j;
    int e;
    struct OLNode *right;
    struct OLNode *down;
} OLNode, *OLink;

typedef struct
{
    OLink *rhead;
    OLink *chead;
    int mu; // 行數(shù)
    int nu; // 列數(shù)
    int tu;
} CrossList;

void addArray(CrossList &a, CrossList b)
{
    int cnt = a.tu + b.tu; // 統(tǒng)計一共有多少個非零數(shù)
    int i = 1;
    // int j1, j2;
    while (cnt > 0) // 當還有數(shù)沒加時繼續(xù)循環(huán)
    {
        OLink p = a.rhead[i];
        OLink q = b.rhead[i];

        if (!p && q) // p當前行無元素，q有元素，則將q賦給p
            p = q;
        if (!p && !q) // p、q當前行均無元素，則跳轉下一行
            continue;
        if (p && !q) // p有元素，q無元素，則跳轉下一行
            continue;
        if (p && q) // p、q均有元素，則進行加法
        {
            do
            {
                if (p->j < q->j)
                {
                    cnt--;        // cnt減一
                    if (p->right) // p的右元素不為空
                    {
                        p = p->right; // 工作指針p向右移
                    }
                    else
                    {
                        p->right = q; // q當前行的所有元素接到p的后面
                    }
                }
                else if (p->j == q->j)
                {
                    p->e = p->e + q->e;
                    p = p->right;
                    q = q->right;  // p、q同時向右移動
                    cnt = cnt - 2; // cnt減二
                }
                else
                {
                    OLink tmp1 = p;
                    p = q;                 // a.rhead[i]指向q的節(jié)點
                    OLink tmp2 = q->right; // 將q的右節(jié)點的指針保存
                    q->right = tmp1;       // q的右指針指向p
                    cnt--;
                    if (tmp2) // 若q的右節(jié)點不為空
                    {
                        q = tmp2; // 工作指針q向右移
                    }
                }
            } while (!p->right); // 當工作指針為當前行的最后一個元素時退出循環(huán)
        }

        i++; // 轉移到下一行
    }
}

代碼圖片

結束語

??因為是算法小菜，所以提供的方法和思路可能不是很好，請多多包涵~如果有疑問歡迎大家留言討論，你如果覺得這篇文章對你有幫助可以給我一個免費的贊嗎？我們之間的交流是我最大的動力！文章來源地址http://www.zghlxwxcb.cn/news/detail-539219.html

到了這里，關于【數(shù)據(jù)結構與算法】 完成用十字鏈表存儲的稀疏矩陣的加法運算的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！