6. Z 字形变换
#define ElementType char struct MNode; typedef struct MNode* PtrToMNode; typedef PtrToMNode Vector; typedef PtrToMNode rPosition; typedef PtrToMNode bPosition; void bInsert(bPosition B); void PrintVector(Vector V); Vector CreateVector(int row); int isLast(rPosition P); void Push(ElementType X, bPosition B); struct MNode { ElementType Element; rPosition Right; bPosition Bottom; }; Vector CreateVector(int row) { if (row < 0) { printf("Invalid row!"); return NULL; } Vector V = calloc(1, sizeof(struct MNode)); if ( V == NULL ) { printf("Out of space!"); return NULL; } V->Element = 0; V->Right = NULL; V->Bottom = NULL; int i = 1; while ( i < row ) { bInsert(V); ++i; } return V; } void bInsert(bPosition B) { bPosition tmp; tmp = calloc(1, sizeof(struct MNode)); if (tmp == NULL) { printf("out of space!"); return; } tmp->Element = 0; tmp->Bottom = B->Bottom; B->Bottom = tmp; } bPosition bFind(int Index, Vector V) { if (Index < 0) { printf("Invalid Index!"); return NULL; } bPosition B; B = V; int i = 0; while ( B->Bottom != NULL && i < Index ) { B = B->Bottom; ++i; } if ( i == Index ) { return B; } while ( i < Index ) { bInsert(B); ++i; B = B->Bottom; } return B; } int isLast(rPosition P) { return P->Right == NULL; } void Push(ElementType X, bPosition B) { rPosition P; P = B; while ( !isLast(P) ) { P = P->Right; } rPosition tmp = calloc(1, sizeof(struct MNode)); if (tmp == NULL) { printf("out of space"); return; } tmp->Element = X; tmp->Right = P->Right; P->Right = tmp; } char * convert(char * s, int numRows){ Vector V = CreateVector(numRows); int goingDown = 1; int i = 0; int currRow = 0; while (s[i]) { bPosition B = bFind(currRow, V); Push(s[i], B); if (goingDown) { currRow++; } else { currRow--; } if (currRow == numRows) { goingDown = 0; currRow -= 2; } if (currRow < 0) { goingDown = 1; currRow += 2; } ++i; } char *res = calloc(i+1, sizeof(char)); rPosition R; bPosition tB; tB = V; int ii = 0; while ( tB ) { R = tB->Right; while ( R ) { res[ii++] = R->Element; R = R->Right; } tB = tB->Bottom; } return res; }
解法是看的官方解答,但是C语言没有Vector,自己写了个链表简单实现一下,但是运行速度和内存消耗都还有很大的优化空间。