數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

數(shù)組

基本操作

InitArray(&A, n, bound1, ..., boundn)

DestroyArray(&A)

Value(A, &e, index1, ..., indexn)

Assign(&A, e, index1, ..., indexn)

數(shù)組的順序表示

兩種順序映象的方式:

以行序?yàn)橹餍?低下標(biāo)優(yōu)先)；
以列序?yàn)橹餍?高下標(biāo)優(yōu)先)。

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

而 $n$ 維數(shù)組：LOC(x1, x2, ..., xn) = LOC(0, 0, ..., 0) + [(x1 × b1 + x2) × b2 + x3] × b3 + ... + xn

數(shù)據(jù)類型定義

#include <stdarg.h> // 標(biāo)準(zhǔn)頭文件，提供宏 va_start、va_arg 和 va_end，用于存取變長(zhǎng)參數(shù)表

#define MAX_ARRAY_DIM 8 // 假設(shè)數(shù)組維數(shù)的最大值為 8

typedef struct {
    ElemType *base;  // 數(shù)組元素地址，由 InitArray 分配
    int dim;         // 數(shù)組維數(shù)
    int *bounds;     // 數(shù)組維界基址，由 InitArray 分配
    int *constants;  // 數(shù)組映像函數(shù)常量基址，由 InitArray 分配
} Array;

其中：

Status InitArray(Array& A, int dim, ...) {
    // 若維數(shù) dim 不合法，則返回 ERROR
    if (dim < 1 || dim > MAX_ARRAY_DIM) {
        return ERROR;
    }
    A.dim = dim;
    A.bounds = (int*)malloc(dim * sizeof(int));
    if (!A.bounds) {
        exit(OVERFLOW);
    }
    // 存儲(chǔ)各維長(zhǎng)度，并計(jì)算元素總數(shù) elemtotal
    int elemtotal = 1;
    va_list ap;  // 定義 va_list 類型變量 ap，用于存放變長(zhǎng)參數(shù)表信息的數(shù)組
    va_start(ap, dim);  // 初始化 ap 數(shù)組
    for (int i = 0; i < dim; ++i) {
        A.bounds[i] = va_arg(ap, int);
        if (A.bounds[i] < 0) {
            return UNDERFLOW;
        }
        elemtotal *= A.bounds[i];
    }
    va_end(ap);  // 結(jié)束 ap 數(shù)組

    A.base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
    if (!A.base) {
        exit(OVERFLOW);
    }
    // 求映像函數(shù)的常數(shù) ci，并存入 A.constants[i-1]，i=1,...,dim
    A.constants = (int*)malloc(dim * sizeof(int));
    if (!A.constants) {
        exit(OVERFLOW);
    }
    A.constants[dim - 1] = 1;
    // L=1，指針的增減以元素的大小為單位
    for (int i = dim - 2; i >= 0; --i) {
        A.constants[i] = A.bounds[i + 1] * A.constants[i + 1];
    }
    return OK;  // 返回 OK
}

A.bounds是每一維可以放多少元素：a[A.bounds[0]][A.bounds[1]][A.bounds[2]]……
A.constants是指向每一維開(kāi)始的元素的指針（因?yàn)槭琼樞虼娣牛詻](méi)有在計(jì)算機(jī)中沒(méi)有明顯的維數(shù)的區(qū)分，需要自己計(jì)算出指向每一維第一個(gè)元素的指針）

關(guān)于va_list的解釋

/**
 * 在數(shù)組 A 中定位指定下標(biāo)的元素，并計(jì)算出該元素的相對(duì)地址。
 * 
 * @param A     要定位的多維數(shù)組
 * @param ap    指示要定位的下標(biāo)列表的可變參數(shù)
 * @param off   返回該元素在數(shù)組 A 中的相對(duì)地址
 * @return      如果下標(biāo)合法，返回 OK；否則返回 OVREFLOW
 */
Status Locate(Array A, va_list ap, int& off) {
    // 初始化偏移量為 0
    off = 0;
    // 循環(huán)遍歷所有維度
    for (int i = 0; i < A.dim; ++i) {
        // 獲取當(dāng)前維度的下標(biāo)值
        int ind = va_arg(ap, int);  
        // 檢查下標(biāo)值是否超出邊界
        if (ind < 0 || ind >= A.bounds[i]) {
            return OVREFLOW;
        }
        // 計(jì)算該維度下標(biāo)對(duì)應(yīng)的偏移量，并累加到總偏移量中
        off += A.constants[i] * ind;
    }
    // 如果下標(biāo)合法，則返回 OK
    return OK;
}

矩陣的壓縮存儲(chǔ)

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

#define MAXSIZE 12500

typedef union {
    Triple data[MAXSIZE + 1]; // 用于存儲(chǔ)稀疏矩陣中的非零元素
    int mu, nu, tu; // 分別表示稀疏矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)
} TSMatrix; // 稀疏矩陣類型

有2類稀疏矩陣：

非零元在矩陣中的分布有一定規(guī)則
例如: 三角矩陣, 對(duì)角矩陣
隨機(jī)稀疏矩陣
非零元在矩陣中隨機(jī)出現(xiàn)

隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法:

三元組順序表

這個(gè)結(jié)構(gòu)體一般用于表示稀疏矩陣中的非零元素。對(duì)于一個(gè) m 行 n 列的稀疏矩陣，如果其非零元素個(gè)數(shù)為 k，則可以用一個(gè)長(zhǎng)度為 k 的 Triple 數(shù)組來(lái)存儲(chǔ)這些非零元素。

#define MAXSIZE 12500

typedef struct {
    int i, j; // 該非零元的行下標(biāo)和列下標(biāo)
    ElemType e; // 該非零元的值
} Triple; // 三元組類型

行邏輯聯(lián)接的順序表
十字鏈表

求轉(zhuǎn)置矩陣

三元組作轉(zhuǎn)置

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
    T.mu = M.nu;
    T.nu = M.mu;
    T.tu = M.tu;
    if (T.tu) {
        int col, t, p;
        int num[MAXSIZE + 1] = {0}; // 列計(jì)數(shù)器，用于記錄每列非零元素的個(gè)數(shù)
        int cpot[MAXSIZE + 1] = {0}; // 行指針數(shù)組，用于記錄每列第一個(gè)非零元素在轉(zhuǎn)置矩陣中的位置
        // 統(tǒng)計(jì)每列非零元素的個(gè)數(shù)
        for (col = 1; col <= M.nu; ++col) {
            num[col] = 0;
        }
        for (t = 1; t <= M.tu; ++t) {
            ++num[M.data[t].j];
        }
        // 計(jì)算每列第一個(gè)非零元素在轉(zhuǎn)置矩陣中的位置
        cpot[1] = 1;
        for (col = 2; col <= M.nu; ++col) {
            cpot[col] = cpot[col - 1] + num[col - 1];
        }
        // 執(zhí)行轉(zhuǎn)置操作
        for (p = 1; p <= M.tu; ++p) {
            col = M.data[p].j;
            int q = cpot[col]; // 該元素在轉(zhuǎn)置矩陣中的位置
            T.data[q].i = M.data[p].j;
            T.data[q].j = M.data[p].i;
            T.data[q].e = M.data[p].e;
            ++cpot[col]; // 該列的行指針加1
        }
    }
    return OK;
} // FastTransposeSMatrix

行邏輯連接的順序表

#define MAXMN 500

typedef struct {
    Triple data[MAXSIZE + 1]; // 非零元三元組表
    int rpos[MAXRC + 1]; // 各行第一個(gè)非零元的位置表
    int mu, nu, tu;  // 矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)            
} RLSMatrix; // 行邏輯鏈接順序表類型

ElemType value(RLSMatrix M, int r, int c) {
    int p = M.rpos[r];
    while (M.data[p].i == r && M.data[p].j < c) {
        p++;
    }
    if (M.data[p].i == r && M.data[p].j == c) {
        return M.data[p].e;
    } else {
        return 0;
    }
} // value

矩陣乘法：

// 稀疏矩陣相乘
Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
    // 如果兩個(gè)稀疏矩陣的列數(shù)不等，則無(wú)法相乘，返回錯(cuò)誤狀態(tài)
    if (M.nu != N.mu) {
        return ERROR;
    }
    // 計(jì)算結(jié)果矩陣Q的行數(shù)，列數(shù)以及非零元素個(gè)數(shù)
    Q.mu = M.mu;
    Q.nu = N.nu;
    Q.tu = 0;
    // 如果M、N之間存在非零元素，則進(jìn)行矩陣相乘的處理
    if (M.tu * N.tu != 0) {
        // 遍歷M的每一行
        for (int arow = 1; arow <= M.mu; ++arow) {
            // M矩陣中第arow行在三元組表中的起始位置
            int mp = M.rpos[arow];
            // 遍歷N的每一列
            for (int bcol = 1; bcol <= N.nu; ++bcol) {
                // 初始化N矩陣中第bcol列在三元組表中的起始位置
                int np = N.rpos[bcol];
                // 累加M矩陣第arow行和N矩陣第bcol列的乘積
                ElemType temp = 0;
                while (mp < M.tu && np < N.tu) {
                    // 如果M矩陣和N矩陣中的當(dāng)前位置元素在同一列，則累加乘積
                    if (M.data[mp].j == N.data[np].i) {
                        temp += M.data[mp].e * N.data[np].e;
                        mp++;
                        np++;
                    } else if (M.data[mp].j < N.data[np].i) {
                        mp++;
                    } else {
                        np++;
                    }
                } // while
                // 如果累加的乘積不為0，則添加到結(jié)果矩陣Q中
                if (temp != 0) {
                    Q.tu++;
                    // 將非零元素添加到Q三元組表的末尾
                    Q.data[Q.tu].i = arow;
                    Q.data[Q.tu].j = bcol;
                    Q.data[Q.tu].e = temp;
                }
            } // for bcol
        } // for arow
    } // if
    return OK;
} // MultSMatrix

十字鏈表

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

結(jié)構(gòu)體定義

typedef struct OLNode {
    int i, j;       // 該非零元的行和列下標(biāo) 
    ElemType e;     // 該非零元的值 
    struct OLNode *right, *down;   // 該非零元所在行表和列表的后繼指針 
} OLNode, *OLink;

typedef struct {
    OLink *rhead, *chead;   // 行和列鏈表頭，指向 rhead 與 chead 數(shù)組
                            // 指針向量基址由 CreateSMatrix 函數(shù)分配
    int mu, nu, tu;         // 稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)      
} CrossList;

廣義表

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】
結(jié)構(gòu)特點(diǎn)：

廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；
廣義表的深度定義為所含括弧的重?cái)?shù)；
注意：“原子”的深度為 0 ；“空表”的深度為 1

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】
表頭要去掉一次括號(hào)，表尾直接拿并且包含原來(lái)的括號(hào)

廣義表的存儲(chǔ)結(jié)構(gòu)

表頭、表尾法

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】
其中，NIL表示空表

還是好好看看吧

子表表示

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

注意其中0|x后面是0|y，而不是跟著表尾，這個(gè)時(shí)候是把表后面的元素拿出來(lái)，所以它和表頭表尾表示法的區(qū)別就在這，它拿后面的子表也要去掉最外面的括號(hào)

搭配這個(gè)例子才比較好理解一些

求深度

int GlistDepth(Glist L) {
    // 返回指針L所指的廣義表的深度
    int max = 0;
    Glist pp;
    int dep;
    if(!L) return 1;
    if(L->tag==ATOM) return 0;
    for (pp = L; pp; pp = pp->ptr.tp) {
        dep = GlistDepth(pp->ptr.hp);
        if (dep > max) {
            max = dep;
        }
    }
    return max + 1;
} // GlistDepth

遇到求深度的一些填空題，可能要自己畫(huà)一下了，不是用眼睛能看出來(lái)的

比如：廣義表 {{1,2},{3,{4,5}}} 中，子表 {1,2} 和 {3,{4,5}} 位于同層，此廣義表中包含 3 層括號(hào)，因此深度為 3。

((1,2),(3,(4,5)))
((1,2),(3,(4,5)))
((1,2),(3,(4,5)))

習(xí)題

計(jì)算地址

數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】

注意按行和按列計(jì)算

（1）100 （2）776 （3）1784 （4）4416

a₃₁₂₅—— 3×3×5×8+1×5×8+2×8+5
高維的系數(shù)乘以低維所包含的元素?cái)?shù)

5.19 馬鞍點(diǎn)

若矩陣 $A$ 中的某個(gè)元素 a_i_j是第 $i$ 行中的最小值同時(shí)又是第 $j$ 列中的最大值，則稱此元素為該矩中的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣 $A_{m*n}$ ，試編寫(xiě)求出矩陣中所有馬鞍點(diǎn)的算法,并分析你的算法在最壞情況下的時(shí)間復(fù)雜度

void saddle(int a[m][n]) {
    int flag = 0, min, col;
    for (int i = 0; i < m; ++i) {
        min = a[i][0];
        for (int j = 0; j < n; ++j) {
            if (a[i][j] < min) {
                min = a[i][j];
                col = j;
            }
        }
        int flag1 = 1;
        for (int k = 0; k < m; ++k) {
            if (min < a[k][col]){
                flag1 = 0;
                break;
            }
        }
        if (flag1) {
            printf("%d行%d列是馬鞍點(diǎn)，值為%d\n", i, col, min);
            flag = 1;
        }

    }
    if (!flag) {
        printf("無(wú)馬鞍點(diǎn)\n");
    }
}

時(shí)間復(fù)雜度： $O(m^2+m*n)$ 文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-474051.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法·第5章【數(shù)組和廣義表】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！