Icoding平台第四次作业解析-块链串/数组

T1

1. 块链串

块链串定义如下：

#define BLOCK_SIZE 4 // 可由用户定义的块大小
#define BLS_BLANK ‘#’ // 用于空白处的补齐字符

typedef struct _block {
char ch[BLOCK_SIZE]; //块的数据域
struct _block *next; //块的指针域
} Block;

typedef struct {
Block *head; // 串的头指针
Block *tail; // 串的尾指针
int len; // 串的当前长度
} BLString;

//字符串初始化函数：
void blstr_init(BLString *T) {
T->len = 0;
T->head = NULL;
T->tail = NULL;
}

这些定义已包含在头文件 dsstring.h 中，请实现块链串的子串查找操作：

bool blstr_substr(BLString src, int pos, int len, BLString *sub);
src为要查找的字符串
pos为子串开始的下标
len为子串的长度
sub在函数调用运行前指向一个已经初始化好的空串，在函数返回时，sub指向串src从第pos个字符起长度为len的子串
函数查找成功返回true，参数不正确返回 false

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-04-19, Sun, 16:05:30
    * 最高分数：100
    */
   
   
   #include "dsstring.h" // 请不要删除，否则检查不通过
   #include <stdio.h>
   #include <stdlib.h>
   
   bool blstr_substr(BLString src, int pos, int len, BLString* sub)
   {
       if (pos < 0 || pos >= src.len || len < 1)
           return false;
       Block *p = (sub->head = (Block*)malloc(sizeof(Block))), *q = src.head;
       int i = 0, j = 0, k = 0;
       p->next = NULL;
       while (k <= pos + len - 1 && q && q->ch[i] != BLS_BLANK) {
           if (k < pos) {
               if (i < BLOCK_SIZE - 1)
                   i++;
               else {
                   q = q->next;
                   i = 0;
               }
               k++;
           } else {
               p->ch[j] = q->ch[i];
               if (i < BLOCK_SIZE - 1)
                   i++;
               else {
                   q = q->next;
                   i = 0;
               }
               if (j < BLOCK_SIZE - 1)
                   j++;
               else {
                   p->next = (Block*)malloc(sizeof(Block));
                   p = p->next;
                   p->next = NULL;
                   j = 0;
               }
               k++;
               sub->len++;
           }
       }
       if (j) {
           sub->tail = p;
           while (j < BLOCK_SIZE)
               p->ch[j++] = BLS_BLANK;
       } else {
           for (sub->tail = sub->head; sub->tail->next != p; sub->tail = sub->tail->next)
               ;
           sub->tail->next = NULL;
           free(p);
       }
       return true;
   }

---

T2

1. 矩阵加法
   实现三元组表示的两个稀疏矩阵的加法。相关定义如下：

   #define MAXSIZE 100 //假设非零元个数的最大值为100
   typedef struct {

   int i,j;   //非零元的行下标和列下标，i 和 j 从 1 开始计数，与数学中矩阵元素的编号一致
   ElemType e;    //非零元的值

   }Triple;

   typedef struct {

   Triple data[MAXSIZE];     // 非零元三元组表
   int    m, n, len;     // 矩阵的行数、列数和非零元个数

   }TSMatrix;

在三元组中，i 和 j 从 1 开始计数，与数学中矩阵元素的编号一致
矩阵加法函数的原型为：

bool add_matrix(const TSMatrix *pM, const TSMatrix *pN, TSMatrix *pQ);

pM, pN, pQ 分别指向三个矩阵，当 pM 和 pN 两个矩阵不可加时，函数返回 false，否则函数返回 true，且 pQ 指向两个矩阵的和。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-04-19, Sun, 16:10:16
    * 最高分数：100
    */
   
   
   #include "tsmatrix.h"
   #include <stdio.h>
   #include <stdlib.h>
   
   bool add_matrix(const TSMatrix* pM, const TSMatrix* pN, TSMatrix* pQ)
   {
       TSMatrix *M = pM, *N = pN, *Q = pQ;
       if (M->m != N->m || M->n != N->n) {
           return false;
       }
       int i = 0, j = 0, k = 0;
       Q->m = M->m, Q->n = M->n, Q->len = 0;
       while (i < M->len && j < N->len) {
           if (M->data[i].i < N->data[j].i || (M->data[i].i == N->data[j].i && M->data[i].j < N->data[j].j)) {
               Q->data[k].i = M->data[i].i;
               Q->data[k].j = M->data[i].j;
               Q->data[k].e = M->data[i].e;
               Q->len++, k++, i++;
           } else if (M->data[i].i == N->data[j].i && M->data[i].j == N->data[j].j) {
               if (M->data[i].e + N->data[j].e) {
                   Q->data[k].i = M->data[i].i;
                   Q->data[k].j = M->data[i].j;
                   Q->data[k].e = M->data[i].e + N->data[j].e;
                   k++, Q->len++;
               }
               i++, j++;
           } else {
               Q->len++;
               Q->data[k].i = N->data[i].i;
               Q->data[k].j = N->data[i].j;
               Q->data[k] = N->data[j];
               k++, j++;
           }
       }
       while (i < M->len) {
           Q->len++;
           Q->data[k] = M->data[i];
           k++, i++;
       }
       while (j < N->len) {
           Q->len++;
           Q->data[k] = N->data[j];
           k++, j++;
       }
       return true;
   }

---

T3

1. 十字链表
   十字链表相关定义如下：

   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 的结点，并返回删除结点的个数。

2. 解析
   Code

   /*
    * 完成人　：岳昕峰(201909******4)
    * 完成时间：2020-04-19, Sun, 16:15:09
    * 最高分数：100
    */
   
   
   #include "crosslist.h"
   #include <stdio.h>
   #include <stdlib.h>
   
   int init_cross_list(PCrossList L, const ElemType* A, int m, int n)
   {
       OLNode *p, *q;
       int i = 0, j = 0, k = 0;
       L->rows = m;
       L->cols = n;
       L->nums = 0;
   
       L->rowhead = (OLink*)malloc((m + 1) * sizeof(OLNode));
       for (j = 0; j <= m; ++j) {
           L->rowhead[j] = NULL;
       }
       L->colhead = (OLink*)malloc((n + 1) * sizeof(OLNode));
       for (j = 0; j <= n; ++j) {
           L->colhead[j] = NULL;
       }
       for (k = 1; k <= m * n; ++k) {
           if (A[k - 1] != 0) {
               p = (OLink)malloc(sizeof(OLNode));
               p->row = ((k - 1) / n);
               p->col = k - (p->row * n) - 1;
               p->value = A[k - 1];
               p->right = NULL;
               p->down = NULL;
               L->nums++;
               i = p->row;
               if (L->rowhead[i] == NULL) {
                   L->rowhead[i] = p;
               } else {
                   for (q = L->rowhead[i]; q->right && q->right->col < p->col; q = q->right)
                       ;
                   p->right = q->right;
                   q->right = p;
               }
               i = p->col;
               if (L->colhead[i] == NULL) {
                   L->colhead[i] = p;
               } else {
                   for (q = L->colhead[i]; q->down && q->down->row < p->row; q = q->down)
                       ;
                   p->down = q->down;
                   q->down = p;
               }
           }
       }
       return L->nums;
   }
   int del_cross_list(PCrossList L, ElemType k)
   {
       int i = 0, t = 0;
       OLink temp;
       OLink p = NULL;
       OLink templeft = NULL;
       OLink tempup = NULL;
       for (i = 0; i < L->rows; i++) {
           if (L->rowhead[i] == NULL) {
               continue;
           }
           for (p = L->rowhead[i], temp = p->right; p != NULL; p = temp) {
               temp = p->right;
               if (p->value == k) {
                   for (templeft = L->rowhead[i]; templeft->right && templeft->right->col < p->col; templeft = templeft->right)
                       ;
                   for (tempup = L->colhead[p->col]; tempup->down != NULL && tempup->down->row < p->row; tempup = tempup->down)
                       ;
                   if (templeft == p) {
                       if (tempup == p) {
                           L->rowhead[i] = p->right;
                           L->colhead[p->col] = p->down;
                           free(p);
                       } else {
                           L->rowhead[i] = p->right;
                           tempup->down = p->down;
                           free(p);
                       }
                   } else {
                       if (tempup == p) {
                           templeft->right = p->right;
                           L->colhead[p->col] = p->down;
                           free(p);
                       } else {
                           templeft->right = p->right;
                           tempup->down = p->down;
                           free(p);
                       }
                   }
                   t++;
                   L->nums--;
               }
           }
       }
       return t;
   }

---