Timmy's Blog

Temp

6.1千字 预计阅读 17 分钟 - 次浏览

《数据结构》实验报告

学号：202531400222
姓名：方宇祺
班级：软件工程2501
课程编号：20544

实验1：顺序表的操作

1. 实验内容

本实验要求用顺序表完成几个最基本的操作：初始化、插入、删除、按位置访问、按元素值查找、清空顺序表。输入里会给出一组操作命令，程序需要按顺序执行，并在删除、访问、查找这几种操作出现时输出结果。

这次实验的核心其实很直接，就是把顺序表当成一段连续存储空间来处理。插入时要给新元素腾位置，删除时要把后面的元素往前补齐，访问和查找则分别对应按下标取值和顺序扫描。

2. 算法说明

顺序表采用题目给出的结构体定义：

C
typedef int ElemType;
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
} Sqlist;

几个主要操作的处理思路如下：

  • 初始化：为顺序表分配一段连续空间，并把长度设为 0。
  • 插入 I a b：在第 a 个位置前插入元素 b。做法是从表尾开始，把第 a 个位置及其后的元素整体向后移动一位，再把 b 放到 a-1 下标处。
  • 删除 D a：先保存第 a 个位置的元素值，再把它后面的元素依次向前移动一位，最后表长减 1，并输出被删除的值。
  • 访问 G a：直接输出第 a 个位置的元素。
  • 查找 L b：从前往后扫描顺序表，找到值为 b 的第一个元素后输出其位置。
  • 清空 C：不需要释放空间，直接把长度置为 0 就可以。

从时间复杂度来看，访问操作是 O(1)，查找是 O(n)，插入和删除在最坏情况下都需要移动一段连续元素，所以也是 O(n)。这也是顺序表比较典型的特点，读起来快，改起来如果动到中间位置就要搬数据。

3. 程序清单

C
#include <stdio.h>
#include <stdlib.h>
 
typedef int ElemType;
 
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
} Sqlist;
 
#define LIST_INIT_SIZE 110
 
void InitList(Sqlist *L) {
    L->elem = (ElemType *)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
}
 
void ClearList(Sqlist *L) {
    L->length = 0;
}
 
void ListInsert(Sqlist *L, int pos, ElemType value) {
    int i;
    for (i = L->length; i >= pos; --i) {
        L->elem[i] = L->elem[i - 1];
    }
    L->elem[pos - 1] = value;
    L->length++;
}
 
ElemType ListDelete(Sqlist *L, int pos) {
    int i;
    ElemType removed = L->elem[pos - 1];
    for (i = pos; i < L->length; ++i) {
        L->elem[i - 1] = L->elem[i];
    }
    L->length--;
    return removed;
}
 
ElemType GetElem(Sqlist *L, int pos) {
    return L->elem[pos - 1];
}
 
int LocateElem(Sqlist *L, ElemType value) {
    int i;
    for (i = 0; i < L->length; ++i) {
        if (L->elem[i] == value) {
            return i + 1;
        }
    }
    return 0;
}
 
int main(void) {
    int n, m, i;
    Sqlist L;
 
    scanf("%d%d", &n, &m);
    InitList(&L);
 
    for (i = 0; i < n; ++i) {
        scanf("%d", &L.elem[i]);
    }
    L.length = n;
 
    for (i = 0; i < m; ++i) {
        char op;
        scanf(" %c", &op);
 
        if (op == 'I') {
            int a, b;
            scanf("%d%d", &a, &b);
            ListInsert(&L, a, b);
        } else if (op == 'D') {
            int a;
            scanf("%d", &a);
            printf("%d\n", ListDelete(&L, a));
        } else if (op == 'G') {
            int a;
            scanf("%d", &a);
            printf("%d\n", GetElem(&L, a));
        } else if (op == 'L') {
            int b;
            scanf("%d", &b);
            printf("%d\n", LocateElem(&L, b));
        } else if (op == 'C') {
            ClearList(&L);
        }
    }
 
    free(L.elem);
    return 0;
}

4. 运行结果

以题目给出的样例为例：

输入：

Plain
5 6
1 2 3 4 5
D 3
D 1
G 1
G 2
G 3
L 4

输出：

Plain
3
1
2
4
5
2

运行结果和题目样例一致，说明程序能够正确完成删除、访问和查找等操作。

5. 分析与思考

这次实验比较基础，但顺序表的特点挺明显。它的优点是结构简单、存储紧凑、按位置访问很快，像 G a 这种操作几乎是直接取值；缺点也很明显，只要在中间插入或删除元素，就得把后面的数据整体挪动一遍，所以数据量一大，效率就会掉下来。

另外，这份程序是按题目“操作一定合法”这个前提写的，所以没有额外做越界判断和扩容处理。如果放到更完整一点的场景里，这两件事最好补上，不然表长超出上限或者位置非法时，程序就不够稳。说白了，这份代码适合实验题和基础练习，要做成更通用的线性表实现，还得把状态返回、容量扩展这些细节补齐。

实验2：链表及其多项式相加

1. 实验内容

这次实验要做的是输入两个一元多项式，各自建立成单链表，然后把两个多项式按指数对应相加，最后输出结果多项式。题目已经说明输入的各项是按指数从小到大给出的，这一点挺关键，因为后面做链表合并时就可以直接像归并那样往后走，不用来回找。

这个实验和顺序表那题放在一起看，其实差别一下就出来了。顺序表处理中间插入、删除时要搬动元素，链表这里就不一样，节点一接一断就能完成结构调整，所以拿它来表示多项式这种“项数不固定、还要按指数合并”的东西很合适。

2. 算法说明

单链表节点中保存两个信息，一个是系数 coef，一个是指数 exp，再加一个 next 指针指向下一项。整个多项式用带头结点的单链表表示，链表中的各项始终按指数从小到大排列。

C
typedef struct Node {
    int coef;
    int exp;
    struct Node *next;
} Node;

几个主要函数的处理思路如下：

  • 建表函数 CreatePolynomial：先创建头结点，再依次读入每一项，采用尾插法把新结点接到链表末尾。因为输入本身已经按指数递增，所以不需要额外排序。
  • 相加函数 AddPolynomial：同时用两个指针分别扫描两个多项式。若某一边指数更小，就把该结点直接接到结果链表后面；若两个指数相同，就把系数相加。相加后如果系数不为 0，就保留该项；如果等于 0，就把这一项删掉，不输出。
  • 输出函数 PrintPolynomial：从头结点后的第一个有效结点开始遍历，依次输出每一项的系数和指数。

这个过程本质上就是两个有序链表的合并。由于每个结点最多只会被访问一次，所以多项式相加的时间复杂度是 O(n + m)，空间上除了头结点和少量辅助指针，没有再开大块额外存储，整体比较直接。

3. 程序清单

C
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int coef;
    int exp;
    struct Node *next;
} Node;
 
Node *CreatePolynomial(int n) {
    Node *head = (Node *)malloc(sizeof(Node));
    Node *tail = head;
    int i;
 
    head->next = NULL;
    for (i = 0; i < n; ++i) {
        int coef, exp;
        Node *node;
 
        scanf("%d%d", &coef, &exp);
        if (coef == 0) {
            continue;
        }
 
        node = (Node *)malloc(sizeof(Node));
        node->coef = coef;
        node->exp = exp;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
 
    return head;
}
 
Node *AddPolynomial(Node *La, Node *Lb) {
    Node *pa = La->next;
    Node *pb = Lb->next;
    Node *head = (Node *)malloc(sizeof(Node));
    Node *tail = head;
 
    head->next = NULL;
 
    while (pa != NULL && pb != NULL) {
        if (pa->exp < pb->exp) {
            tail->next = pa;
            tail = pa;
            pa = pa->next;
        } else if (pa->exp > pb->exp) {
            tail->next = pb;
            tail = pb;
            pb = pb->next;
        } else {
            int sum = pa->coef + pb->coef;
            Node *nexta = pa->next;
            Node *nextb = pb->next;
 
            if (sum != 0) {
                pa->coef = sum;
                tail->next = pa;
                tail = pa;
            } else {
                free(pa);
            }
 
            free(pb);
            pa = nexta;
            pb = nextb;
        }
    }
 
    if (pa != NULL) {
        tail->next = pa;
    } else {
        tail->next = pb;
    }
 
    free(La);
    free(Lb);
    return head;
}
 
void PrintPolynomial(Node *L) {
    Node *p = L->next;
    while (p != NULL) {
        printf("%d %d\n", p->coef, p->exp);
        p = p->next;
    }
}
 
void DestroyPolynomial(Node *L) {
    Node *p = L;
    while (p != NULL) {
        Node *next = p->next;
        free(p);
        p = next;
    }
}
 
int main(void) {
    int n, m;
    Node *La;
    Node *Lb;
    Node *Lc;
 
    scanf("%d", &n);
    La = CreatePolynomial(n);
 
    scanf("%d", &m);
    Lb = CreatePolynomial(m);
 
    Lc = AddPolynomial(La, Lb);
    PrintPolynomial(Lc);
    DestroyPolynomial(Lc);
 
    return 0;
}

4. 运行结果

题目样例如下：

输入：

Plain
3
1 2
2 3
3 4
3
4 3
2 5
4 6

输出：

Plain
1 2
6 3
3 4
2 5
4 6

本程序测试结果与样例一致，提交后也已经通过评测，说明链表建立、合并相加和结果输出这几个部分都能正常完成。

5. 分析与思考

这题用链表来表示多项式，确实比顺序存储更顺手。因为多项式相加时，真正麻烦的不是按位置访问，而是不同指数项之间的拼接和合并。链表在这方面比较省事，某一项该保留就接上去，该删除就断开并释放，不需要像顺序表那样整体挪数据。

当然，链表也不是没有代价。一方面它不能像数组那样直接按下标访问，查某一项时还是得顺着指针往后走；另一方面每插入一个结点都要动态申请内存，代码量和细节处理也会多一点。这份实现已经能满足题目要求，不过如果要写得更完整些，还可以继续补内存申请失败判断，或者把释放逻辑再封装得更清楚一点，这样程序会更稳。

实验3：多重括号匹配判断

1. 实验内容

这次实验要求判断一个只由圆括号和方括号组成的表达式是否匹配。所谓匹配，说白了就是两件事得同时满足，一是左括号和右括号类型要对应，二是闭合顺序也得对，不能前面开的括号让后面不相干的括号先关掉。

这类题很典型，基本就是栈的直接应用。因为括号匹配天然符合“后进先出”这个特点，最后出现的左括号，应该最先等到和它对应的右括号，所以拿栈来做会很顺。

2. 算法说明

程序里使用顺序栈来保存扫描过程中遇到的左括号，栈中元素类型为字符。遍历输入字符串时，分两种情况处理：

  • 如果当前字符是 ( 或 [，就直接入栈。
  • 如果当前字符是 ) 或 ]，先判断栈是否为空。若栈空，说明没有可以匹配的左括号，表达式一定不合法；若栈不空，就弹出栈顶元素，检查括号类型是否对应。

当整个字符串扫描结束后，还要再判断一次栈是否为空。如果栈为空，说明所有左括号都已经正确匹配；如果栈里还有剩余元素，说明存在未闭合的左括号，结果也应该判为不匹配。

程序中另外写了一个 Match 函数，用来判断一对左右括号是否属于同一类型。整个算法只需要把字符串从头扫一遍，所以时间复杂度是 O(n)，空间复杂度也是 O(n)，这里的 n 是表达式长度。

3. 程序清单

C
#include <stdio.h>
#include <string.h>
 
#define MAXN 600
 
typedef struct {
    char data[MAXN];
    int top;
} SqStack;
 
void InitStack(SqStack *S) {
    S->top = -1;
}
 
int StackEmpty(SqStack *S) {
    return S->top == -1;
}
 
void Push(SqStack *S, char ch) {
    S->data[++S->top] = ch;
}
 
char Pop(SqStack *S) {
    return S->data[S->top--];
}
 
int Match(char left, char right) {
    if (left == '(' && right == ')') {
        return 1;
    }
    if (left == '[' && right == ']') {
        return 1;
    }
    return 0;
}
 
int main(void) {
    char str[MAXN];
    int i, len;
    SqStack S;
 
    scanf("%s", str);
    len = (int)strlen(str);
    InitStack(&S);
 
    for (i = 0; i < len; ++i) {
        if (str[i] == '(' || str[i] == '[') {
            Push(&S, str[i]);
        } else {
            if (StackEmpty(&S)) {
                printf("no\n");
                return 0;
            }
            if (!Match(Pop(&S), str[i])) {
                printf("no\n");
                return 0;
            }
        }
    }
 
    if (StackEmpty(&S)) {
        printf("yes\n");
    } else {
        printf("no\n");
    }
 
    return 0;
}

4. 运行结果

题目给出了两组样例。

样例一输入：

Plain
[]()[]

输出：

Plain
yes

样例二输入：

Plain
([[]])[)

输出：

Plain
no

本程序测试结果与题目样例一致，提交后已经通过评测，说明括号入栈、出栈以及类型匹配判断都没有问题。

5. 分析与思考

这题其实不复杂，但很能说明栈这种结构到底适合干什么。只要场景里出现“最后进去的东西要先拿出来”这种顺序，栈基本就很好用。括号匹配就是这样，越靠后的左括号，越应该先等到自己的右括号。

另外，这题也能看出顺序栈的实现很直接，定义一个数组和栈顶指针就够了，写起来不重。不过它也有前提，就是要先大致知道数据规模，好提前开够空间。这里字符串长度不超过 550，所以直接开定长数组完全够用。要是数据规模再大一些，或者输入长度不固定，那就可以考虑链栈或者动态扩容的写法。

实验4：循环队列插入与删除操作

1. 实验内容

这次实验要求实现一个环形队列，支持两种基本操作，一个是 enqueue x，表示元素进队，另一个是 dequeue，表示元素出队。队列初始为空，如果执行出队时队列里没有元素，就输出 -1。

这题看起来就是普通队列题，但专门强调了“循环队列”，意思就是数组空间要循环利用。这样做的好处很直接，队头元素出队以后，前面空出来的位置不会浪费掉，后面的新元素还能继续往回放，不然顺序队列用久了很容易出现“后面满了、前面空着却不能用”的情况。

2. 算法说明

程序中用一个数组来模拟循环队列，再配两个指针 front 和 rear 分别表示队头位置和队尾的下一位置。初始化时让二者都等于 0，这时队列为空。

队列操作规则如下：

  • 入队 EnQueue：先把新元素存入 rear 所在位置，再把 rear 按照循环方式向后移动一格，即 rear = (rear + 1) % MAXQ。
  • 出队 DeQueue：先取出 front 所在位置的元素，再把 front 按照同样的方式向后移动一格。
  • 判空 QueueEmpty：当 front == rear 时，说明队列中没有元素。

因为题目给出的操作总数不超过 31000，而且出队不会导致非法访问，所以这里直接开一个足够大的数组就能满足要求。每次入队和出队都只做常数次操作，所以时间复杂度是 O(1)，整题总复杂度就是 O(q)。

3. 程序清单

C
#include <stdio.h>
#include <string.h>
 
#define MAXQ 31010
 
typedef struct {
    int data[MAXQ];
    int front;
    int rear;
} CirQueue;
 
void InitQueue(CirQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
}
 
int QueueEmpty(CirQueue *Q) {
    return Q->front == Q->rear;
}
 
void EnQueue(CirQueue *Q, int x) {
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXQ;
}
 
int DeQueue(CirQueue *Q) {
    int value = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXQ;
    return value;
}
 
int main(void) {
    int q, i;
    char op[20];
    CirQueue Q;
 
    InitQueue(&Q);
    scanf("%d", &q);
 
    for (i = 0; i < q; ++i) {
        scanf("%s", op);
        if (strcmp(op, "enqueue") == 0) {
            int x;
            scanf("%d", &x);
            EnQueue(&Q, x);
        } else if (QueueEmpty(&Q)) {
            printf("-1\n");
        } else {
            printf("%d\n", DeQueue(&Q));
        }
    }
 
    return 0;
}

4. 运行结果

题目样例如下：

输入：

Plain
4
enqueue 123
dequeue
dequeue
enqueue 1

输出：

Plain
123
-1

本程序测试结果与样例一致，提交后已经通过评测，说明循环队列的进队、出队和空队判断都实现正确。

5. 分析与思考

这题的重点其实不是队列本身，而是“循环”这两个字。普通顺序队列也能入队出队，但如果只是简单地让队头、队尾一直往后走，用久了就会浪费前面已经腾出来的空间。循环队列把数组首尾接起来之后，这个问题就解决了。

当然，循环队列写的时候也有个很容易搞混的地方，就是 front 和 rear 到底表示什么位置。如果这个约定没先想清楚，后面判空、出队和移动指针就容易写乱。这次实现里把 rear 定义成“队尾元素的下一位置”，这样整个逻辑会顺一些，判空条件也比较自然。

实验5：字符串的模式匹配（KMP）

1. 实验内容

这次实验要求给定一个源串 S，再输入若干个模式串，判断每个模式串是不是 S 的子串。题目标题已经点明了要用 KMP，所以重点不只是把结果做出来，而是要按模式匹配的思路来实现。

如果直接用朴素匹配，模式串一旦失配，就只能把模式串整体往后挪一位重新比，这样在某些情况下会有很多重复比较。KMP 的好处就在这儿，它会利用已经匹配过的信息，在失配时把模式串移动到更合适的位置，少做很多没必要的回退。

2. 算法说明

程序分成两个核心部分，一个是求模式串的 next 数组，另一个是利用 next 数组进行匹配。

  • GetNext：根据模式串本身的前缀和后缀关系，求出每个位置对应的最长相等前后缀长度。这样一来，后面一旦失配，就知道模式串应该跳到哪里继续比较。
  • KMP：用两个指针分别扫描源串和模式串。如果当前字符相同，就一起向后移动；如果失配，就根据 next 数组调整模式串指针，而不是让源串回退。

当模式串指针走到模式串末尾时，就说明找到了一个完整匹配，返回 1；如果整个源串都扫描完还没匹配成功，就返回 0。因为每个字符最多被处理常数次，所以一次匹配的时间复杂度是 O(|S| + |P|)，其中 |S| 是源串长度，|P| 是模式串长度。

3. 程序清单

C
#include <stdio.h>
#include <string.h>
 
#define MAXS 100010
#define MAXP 3510
 
void GetNext(const char *pattern, int *next) {
    int i, j;
    int m = (int)strlen(pattern);
 
    next[0] = 0;
    for (i = 1, j = 0; i < m; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        next[i] = j;
    }
}
 
int KMP(const char *text, const char *pattern) {
    int i, j;
    int n = (int)strlen(text);
    int m = (int)strlen(pattern);
    int next[MAXP];
 
    GetNext(pattern, next);
    for (i = 0, j = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            return 1;
        }
    }
 
    return 0;
}
 
int main(void) {
    char s[MAXS];
    char str[MAXP];
    int n, i;
 
    scanf("%s", s);
    scanf("%d", &n);
 
    for (i = 0; i < n; ++i) {
        scanf("%s", str);
        if (KMP(s, str)) {
            printf("yes\n");
        } else {
            printf("no\n");
        }
    }
 
    return 0;
}

4. 运行结果

题目样例如下：

输入：

Plain
acmicpczjnuduzongfei
3
icpc
du
liu

输出：

Plain
yes
yes
no

本程序测试结果与样例一致，提交后已经通过评测，说明 next 数组构造和 KMP 匹配过程都正确。

5. 分析与思考

这题最有意思的地方就在于，KMP 不是单纯“把字符串拿来比一遍”，而是先利用模式串本身的结构信息，给后面的匹配过程铺路。失配以后，模式串不用傻傻地从头再来，而是直接跳到还能继续尝试匹配的位置，这就是它比朴素算法更高效的原因。

当然，KMP 写起来也比普通暴力匹配更容易绕，尤其是 next 数组下标、失配后的跳转位置，还有指针什么时候加一，这几处都很容易写错。这次实验做完以后，对模式匹配这类问题的感觉会更清楚一些，至少再看到“子串查找”这种题，就知道不只是循环硬扫，还可以用更讲究的办法来做。

实验6：稀疏矩阵的建立与转置

1. 实验内容

这次实验要求输入稀疏矩阵的行数、列数以及所有非零元素的信息，先建立它的三元组存储结构，再完成矩阵转置，并把转置前后的矩阵都按普通二维矩阵的形式输出出来。

这题的重点其实不在“打印矩阵”，而在“稀疏矩阵怎么存”。因为矩阵里大部分位置都是 0，如果还按普通二维数组整块存，就有点浪费了。三元组的做法更合适，只记录那些真正非零的位置，也就是行号、列号和值这三样东西。

2. 算法说明

程序中定义了一个三元组结构 Triple，用来保存一个非零元素的行、列和值；再用 TSMatrix 结构保存整个稀疏矩阵的行数、列数、非零元素个数，以及所有三元组数据。

C
typedef struct {
    int row;
    int col;
    int value;
} Triple;
 
typedef struct {
    Triple data[MAXSIZE];
    int rows;
    int cols;
    int nums;
} TSMatrix;

几个主要步骤如下：

  • 建立矩阵 CreateMatrix：读入矩阵规模和非零元素个数，再把每个非零元素的行、列和值依次存入三元组数组。
  • 转置矩阵 TransposeMatrix：转置后，原来的行和列互换，所以把每个非零元素的 row 和 col 对调即可。为了保证转置后的三元组仍然按“从上到下、从左到右”的顺序存储，程序按列扫描原矩阵的三元组，并依次生成转置结果。
  • 输出矩阵 PrintMatrix：根据三元组数组中的非零元素位置，把矩阵逐行逐列还原输出；如果当前位置没有对应的三元组，就输出 0，格式统一用 %5d。

由于转置部分用了两层循环，时间复杂度大致是 O(cols * nums)。在这道题的数据范围下，矩阵规模很小，这种写法已经完全够用，而且逻辑直观，不容易写乱。

3. 程序清单

C
#include <stdio.h>
 
#define MAXSIZE 410
 
typedef struct {
    int row;
    int col;
    int value;
} Triple;
 
typedef struct {
    Triple data[MAXSIZE];
    int rows;
    int cols;
    int nums;
} TSMatrix;
 
void CreateMatrix(TSMatrix *M) {
    int i;
    scanf("%d%d%d", &M->rows, &M->cols, &M->nums);
    for (i = 0; i < M->nums; ++i) {
        scanf("%d%d%d", &M->data[i].row, &M->data[i].col, &M->data[i].value);
    }
}
 
void TransposeMatrix(TSMatrix *M, TSMatrix *T) {
    int col, k, index = 0;
 
    T->rows = M->cols;
    T->cols = M->rows;
    T->nums = M->nums;
 
    for (col = 0; col < M->cols; ++col) {
        for (k = 0; k < M->nums; ++k) {
            if (M->data[k].col == col) {
                T->data[index].row = M->data[k].col;
                T->data[index].col = M->data[k].row;
                T->data[index].value = M->data[k].value;
                ++index;
            }
        }
    }
}
 
void PrintMatrix(TSMatrix *M) {
    int i, j, k = 0;
 
    for (i = 0; i < M->rows; ++i) {
        for (j = 0; j < M->cols; ++j) {
            if (k < M->nums && M->data[k].row == i && M->data[k].col == j) {
                printf("%5d", M->data[k].value);
                ++k;
            } else {
                printf("%5d", 0);
            }
        }
        printf("\n");
    }
}
 
int main(void) {
    TSMatrix M, T;
 
    CreateMatrix(&M);
    TransposeMatrix(&M, &T);
 
    PrintMatrix(&M);
    printf("\n");
    PrintMatrix(&T);
 
    return 0;
}

4. 运行结果

题目样例如下：

输入：

Plain
6 7 8
0 1 12
0 2 9
2 1 3
2 5 14
3 2 24
4 1 18
5 0 15
5 3 -7

输出：

Plain
    0   12    9    0    0    0    0
    0    0    0    0    0    0    0
    0    3    0    0    0   14    0
    0    0   24    0    0    0    0
    0   18    0    0    0    0    0
   15    0    0   -7    0    0    0

    0    0    0    0    0   15
   12    0    3    0   18    0
    9    0    0   24    0    0
    0    0    0    0    0   -7
    0    0    0    0    0    0
    0    0   14    0    0    0
    0    0    0    0    0    0

本程序测试结果与样例一致，提交后已经通过评测，说明稀疏矩阵建立、转置和按格式输出都没有问题。

5. 分析与思考

这题做完以后，能很明显感觉到三元组存储的价值。对于非零元素很少的矩阵，真正有用的信息其实就那么几项，没必要把一大堆 0 也老老实实存起来。用三元组以后，数据结构会更紧凑，处理起来也更有针对性。

不过这份实现也能看出一个点，就是现在的转置方法虽然直观，但还不算最快。它是按列去扫所有非零元素，所以规模再大一点时，效率就没那么漂亮了。后面如果继续学稀疏矩阵，通常还会碰到“快速转置”这种写法，会进一步利用每一列非零元素的个数来减少扫描次数。对实验题来说，这一版已经够用了，而且思路清楚，比较适合理解三元组和转置的基本过程。

实验7：二叉树的创建及遍历

实验8：树的建立与遍历

实验9：图的建立与遍历

实验10：最小生成树prim算法

实验11：最小生成树Kruskal算法

实验12：拓扑排序

实验13：最短路径Dijkstra算法

实验14：二叉搜索树的构建与应用

实验15：快速排序

实验16：堆排序

评论

评论加载中…