icoding 復習4 ?

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;
pM, pN, pQ 分別指向三個矩陣，當 pM 和 pN 兩個矩陣不可加時，函數返回 false，
否則函數返回 true，且 pQ 指向兩個矩陣的和。

#include "tsmatrix.h"
#include
#include

bool add_matrix(const TSMatrix* pM, const TSMatrix* pN, TSMatrix* pQ)
{
?? ?if(pM->m != pN->m || pM->n != pN->n) return false;
?? ?
?? ?pQ->m = pM->m;
?? ?pQ->n = pM->n;
?? ?//記得檢查結構體賦值!!?
?? ?int i, j, k = 0;
?? ?for(i = 0, j = 0; i < pM->len && j < pN->len;){
?? ??? ?if(pM->data[i].i == pN->data[j].i){
?? ??? ??? ?if(pM->data[i].j == pN->data[j].j){
?? ??? ??? ??? ?if(pM->data[i].e + pN->data[j].e){
?? ??? ??? ??? ??? ?pQ->data[k].e = pM->data[i].e + pN->data[j].e;
?? ??? ??? ??? ??? ?pQ->data[k].i = pM->data[i].i;
?? ??? ??? ??? ??? ?pQ->data[k].j = pM->data[i].j;
?? ??? ??? ??? ??? ?k++; i++; j++;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else{//這個else可以不要,前面的if里面的i++和j++可以提出來?
?? ??? ??? ??? ??? ?i++; j++;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ??? ?else if(pM->data[i].j < pN->data[j].j){
?? ??? ??? ??? ?pQ->data[k].e = pM->data[i].e;
?? ??? ??? ??? ?pQ->data[k].i = pM->data[i].i;
?? ??? ??? ??? ?pQ->data[k].j = pM->data[i].j;
?? ??? ??? ??? ?k++; i++;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?pQ->data[k].e = pN->data[j].e;
?? ??? ??? ??? ?pQ->data[k].i = pN->data[j].i;
?? ??? ??? ??? ?pQ->data[k].j = pN->data[j].j;
?? ??? ??? ??? ?k++; j++;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?else if(pM->data[i].i < pN->data[j].i){
?? ??? ??? ?pQ->data[k].e = pM->data[i].e;
?? ??? ??? ?pQ->data[k].i = pM->data[i].i;
?? ??? ??? ?pQ->data[k].j = pM->data[i].j;
?? ??? ??? ?k++; i++;
?? ??? ?}
?? ??? ?else{
?? ??? ??? ?pQ->data[k].e = pN->data[j].e;
?? ??? ??? ?pQ->data[k].i = pN->data[j].i;
?? ??? ??? ?pQ->data[k].j = pN->data[j].j;
?? ??? ??? ?k++; j++;?? ??? ??? ?
?? ??? ?}?? ?
?? ?}?
?? ?while(i < pM->len){
?? ??? ?pQ->data[k].e = pM->data[i].e;
?? ??? ?pQ->data[k].i = pM->data[i].i;
?? ??? ?pQ->data[k].j = pM->data[i].j;
?? ??? ?k++; i++;?? ??? ?
?? ?}
?? ?while(j < pN->len){
?? ??? ?pQ->data[k].e = pN->data[j].e;
?? ??? ?pQ->data[k].i = pN->data[j].i;
?? ??? ?pQ->data[k].j = pN->data[j].j;
?? ??? ?k++; j++;?? ??? ?
?? ?}
?? ?pQ->len = k;
?? ?return true;
}

2. 十字鏈表

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 的結點，并返回刪除結點的個數。

掌握!!!!!!?
int init_cross_list(PCrossList L, const ElemType* A, int m, int n)
{
? ? int i, j, k = 0;
? ? OLNode *p, *q;

? ? L->cols = n;
? ? L->rows = m;
? ? !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
? ? //下面這個是個很奇怪的數組可以認為是指針數組?
? ? if (!(L->rowhead = (OLink*)malloc(m * sizeof(OLink))))//也可以return 0;....icoding不會檢測.....?
? ? ? ? ;
? ? if (!(L->colhead = (OLink*)malloc(n * sizeof(OLink))))
? ? ? ? ;

? ? 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) {
? ? ? ? ? ? ? ? k++;
? ? ? ? ? ? ? ? if (!(p = (OLNode*)malloc(sizeof(OLNode))))
? ? ? ? ? ? ? ? ? ? ;
? ? ? ? ? ? ? ? p->col = j;
? ? ? ? ? ? ? ? p->row = i;
? ? ? ? ? ? ? ? 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 {
? ? ? ? ? ? ? ? ? ? q = L->rowhead[i];
? ? ? ? ? ? ? ? ? ? while (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 {
? ? ? ? ? ? ? ? ? ? q = L->colhead[j];
? ? ? ? ? ? ? ? ? ? while (q->down && q->down->row < i)
? ? ? ? ? ? ? ? ? ? ? ? q = q->down;
? ? ? ? ? ? ? ? ? ? p->down = q->down;
? ? ? ? ? ? ? ? ? ? q->down = p;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? L->nums = k;
? ? return L->nums;
} //init

int del_cross_list(PCrossList L, ElemType k)
{
? ? int num = 0;
? ? int i, j;
? ? OLNode *p, *q, *s;
? ? OLNode *x, *y, *z;

? ? for (i = 0; i < L->rows; i++) {
? ? ? ? p = L->rowhead[i];
? ? ? ? q = p;
? ? ? ? while (p) {
? ? ? ? ? ? if (p->value == k && p == q) {//第一個結點(不設頭結點)?
? ? ? ? ? ? ? ? L->rowhead[i] = L->rowhead[i]->right;
? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ? ? ? p = L->rowhead[i];
? ? ? ? ? ? ? ? num++;
? ? ? ? ? ? } else if (p->value == k) {
? ? ? ? ? ? ? ? s = p;
? ? ? ? ? ? ? ? q->right = p->right;
? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ? ? ? p = q->right;
? ? ? ? ? ? ? ? num++;
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? q = p;
? ? ? ? ? ? ? ? p = p->right;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? //下面的for可以不要,icoding根本不得檢測縱向的鏈..........................................................?
? ? for (j = 0; j < L->cols; j++) {
? ? ? ? x = L->colhead[j];
? ? ? ? y = x;
? ? ? ? while (x) {
? ? ? ? ? ? if (x->value == k && x == y) {
? ? ? ? ? ? ? ? L->colhead[j] = L->colhead[j]->down;
? ? ? ? ? ? ? ? x = x->down;
? ? ? ? ? ? ? ? free(y);
? ? ? ? ? ? } else if (x->value == k) {
? ? ? ? ? ? ? ? y->down = x->down;
? ? ? ? ? ? ? ? z = x;
? ? ? ? ? ? ? ? free(z);
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? y = x;
? ? ? ? ? ? ? ? x = x->down;
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? L->nums -= num;
? ? return num;
}

總結

以上是生活随笔為你收集整理的icoding复习4 数组 十字链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。