十字链表

十字链表相关定义如下：

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

提供代码

#include <stdio.h>#include <stdlib.h>#include "crosslist.h"int init_cross_list(PCrossList L, const ElemType *A, int m,int n){}int del_cross_list(PCrossList L, ElemType k){}

参考代码

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h>//#include "crosslist.h"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;int init_cross_list(PCrossList L, const ElemType* A, int m, int n){int i, j, sum = 0;OLNode* p, * q;L->rows = m;L->cols = n;if (!(L->rowhead = (OLink*)malloc((m + 1) * (sizeof(OLink)))))return 0;if (!(L->colhead = (OLink*)malloc((n + 1) * (sizeof(OLink)))))return 0;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) {sum++;if (!(p = (OLNode*)malloc(sizeof(OLNode))))return 0;p->row = i;p->col = j;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 {for (q = L->rowhead[i]; (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 {for (q = L->colhead[j]; (q->down) && (q->down->row < i); q = q->down);p->down = q->down;q->down = p;}}}}L->nums = sum;return sum;}void delete_crossList(PCrossList clist, int row, int col, int k){OLNode* tmp = NULL;OLNode* tmp1 = NULL;OLNode* tmp2 = NULL;OLNode* t = NULL;OLNode* t1 = NULL;OLNode* t2 = NULL;//删除一个结点需要修改行结点指针和列结点指针tmp = clist->rowhead[row];t = clist->colhead[col];if (tmp->value == k) {clist->rowhead[row] = tmp->right;}if (t->value == k) {clist->colhead[col] = t->down;}if (t->value == k) {free(t);return;}//行遍历元素while (tmp) {tmp1 = tmp;tmp = tmp->right;if (tmp && tmp->row == row && tmp->col == col) {tmp2 = tmp;tmp1->right = tmp2->right;break;}}//列遍历元素while (t) {t1 = t;t = t->down;if (t && t->row == row && t->col == col) {t2 = t;t1->down = t2->down;break;}}free(t);clist->nums--;}int del_cross_list(PCrossList L, ElemType k){OLink pt;int i, j;int sum = 0;for (i = 0; i < L->rows; i++) {pt = L->rowhead[i];for (j = 0; j < L->cols; j++) {if (pt && pt->col == j) {if (pt->value == k) {delete_crossList(L, i, j, k);sum++;}pt = pt->right;}}printf("\n");}return sum;}void test01(){CrossList L;int m = 3, n = 4;int A[21] = { 0, 0, 0, 8, 0, 0, 73, 0, 0, 0, 0, 67 };init_cross_list(&L, A, m, n);del_cross_list(&L, 8);}void main(){test01();return 0;}

十字链表实例

十字链表相关知识

/aiqq136/article/details/115303041

手写过程