来看用指针实现高低位倒序！

gaosmile · 2020-05-13T11:29:19+00:00

昨晚在微信群看到一个读者发的面试题目，从网上截图出来的，我百思不得其解，题目如图。 " z$ g- T m/ g& Q6 ~0 ` & @# C( r+ V$ Q" z: h3 m幸好，我学过栈. C% a& T, i* ~/ i1 J1 ~0 V 9 ^% U( c6 `+ c( T! w( Q; a5 l9 e然后我写了个小程序) L* }3 h9 h; q! ` 第一个方法比较笨，当我写完自己的代码后，看到有同学发了自己的代码，我赶紧就发了个红包，一个是为了鼓励大家多讨论问题，一个是为了赞扬这样的行为。 4 w, B, V6 W9 B6 d% t第一个方法就是取出每一个bit，压栈，然后再出栈，你想怎么排序都没有问题。 * l/ }- w" }( [. C! E#include "stdio.h" ' C0 }9 Y6 y- B9 w5 O: B+ q5 q1 b; b#include "stdlib.h") ]$ @' \$ [9 q# P) u0 E % x; C3 S% d( U5 ^! k6 R% r) {struct List{ : s& Y9 g2 C2 Z int data;: n$ p- O6 g4 Q' n! a) @ struct List * next;" G, I9 K; I& A4 G8 ]" Z }; 7 ~5 c1 L# |7 z* U/ ] 3 e2 [# T) d9 r1 }, K: [struct Stack{ 2 R: X6 r5 q. B( H, M7 R struct List *head; : P# v$ z! t5 _( ^! N; { int size; , C( e3 P+ D* U9 s$ v9 J}; , ?1 I. C8 B3 z# G) d+ g9 C( l 2 M W# L! Y0 A7 c/ q" P0 I [ * F6 H2 e3 Y. N: L3 |3 rstruct Stack * StackInit(void)5 B3 ?& F! H( j {" M% K+ I' D0 h- E9 i struct Stack *stack = NULL; . |; ^8 G6 C+ b2 q stack = (struct Stack*)malloc(sizeof(struct Stack));$ Y8 R" ?8 V0 L! U stack->head = (struct List *)malloc(sizeof(struct List));. O3 w( P, {1 a `/ A5 i U stack->head->next = NULL; # \9 {! O6 @/ X% D; S( i stack->size = 0; ! ?8 s( R6 `: y$ I& |8 w2 h* i$ M return stack; : D: u' B# ^' Y0 }/ X% R% g}+ r0 | X# S% C N9 q6 P2 l; f / L$ E* B+ _/ U' o+ P* h8 ?4 Z int StackPush(struct Stack *stack,int data) , r" [; G1 o" e6 r{ 0 }5 b8 c/ ^" C6 S3 i. k7 ` struct List *tmp = (struct List *)malloc(sizeof(struct List));8 ]- Z# @4 O5 o) r" ]/ Y tmp->data = data;6 n" M2 X4 f, n% P tmp->next = stack->head->next;2 y7 g: ^# [( U d% C* ~5 y [ stack->head->next = tmp;" Q: Y6 N' R$ i% Y" R* A stack->size++;& w- g' L8 p# c( Y0 l6 _" m) _$ i //printf("push:%d \n",data);5 y/ o. I/ i+ w1 M$ j return 0;) \& V9 y% N" i } : E& i- d6 G. C% ^8 L! e ( u7 t3 [/ P w, G2 t, ?" C& Oint IsStackEmpty(struct Stack *stack)4 e( m. ]: `' f/ U3 p8 ^: I% W {: J+ a7 I# n) v( ?- C L8 Z( K if(stack->head->next == NULL){/ f. H% _9 B- L- n$ g //printf("stack null\n");5 Z- Q! `- y6 f& D0 L return 1; , w) K+ D Z, X0 N. x2 N2 |: ?: r }else{ 9 G6 C0 E2 q& ^) n0 M //printf("stack is not null\n"); ' q( w. j3 S1 `5 ?) L1 ^- ?7 {9 U { return 0; 9 ?3 [1 h2 Q8 }9 M B } 7 g0 g1 j3 j& l3 l* a/ {' Q5 H( y: I} 2 |# J( p! P/ Z# [: s 0 b, d; S6 U, S- jint StackPop(struct Stack *stack,int *data) 0 y; t* l' z4 Z/ \& _4 x{3 m& |8 B; f. q t5 u struct List *tmp = NULL;/ x/ d' k5 i4 P/ t if(IsStackEmpty(stack)) % p) l1 p9 w& M; Y4 u% G1 B return -1; 5 v8 C1 k- K& h" b 6 U2 M% E$ j2 P1 @" S tmp = stack->head->next; / F4 \7 y0 ~4 f& d3 r1 P *data = tmp->data; : ]; X) f. {, F stack->head->next = tmp->next;1 O" J* n; w: z9 C; ^6 o' B stack->size--;/ U2 v' H- I; q, d) X6 Y. M if(tmp!=NULL) 2 N; v# t3 n* }3 O9 V7 y) ` free(tmp);6 Z; S: l$ _5 u - u, Y1 w5 O3 s( v z1 \2 n9 Q q //printf("pop:%d \n",*data);6 B, j* ~0 ]9 f7 ?. H return 0; + a8 r! D7 w' ?}4 p- b( |3 [3 U+ D/ L, U & l9 F- r: B) _' v 4 H8 J9 { Y( q: p int main(void)4 y' s) I1 w5 O, x# l% u {0 m1 k [6 x8 {$ A0 K# z! r int i = 0;: E5 `- q, |* u( f unsigned char a = 0x71; 9 k, o9 j* y. t8 V& V* \% a unsigned char b = 0;+ J2 Y7 X. r0 b+ a ; q/ G/ b; I4 W) i6 D$ g) e struct Stack *stack = NULL;+ p- ]! q" c: r3 V5 ^6 I, F stack = StackInit();5 m3 n, d7 ^6 U9 ~ 8 `$ y, {; s, i/ ]) j5 A" x0 x/ U printf("a:0x%x\n",a);! q5 O1 I+ k* h M$ i+ E$ w for(i = 0;i<8;i++) / G1 Q/ e; r k" T2 x$ B {! p2 f( `9 z# x+ g7 T 9 w* ~. [6 Q {6 n3 |5 ] if(a&0x10) StackPush(stack,1); 6 U& z4 ~- K4 w+ v6 a: | else StackPush(stack,0); 3 t' W6 t- n+ f if(a&0x20) StackPush(stack,1); s" |9 t2 Q+ n6 X else StackPush(stack,0);% X3 s- ?) f* x& {) U7 p/ v if(a&0x40) StackPush(stack,1); " a1 t- E3 U- T8 s3 D% ~ else StackPush(stack,0); 4 H9 a% e9 [% }2 @$ x; f if(a&0x80) StackPush(stack,1); : H& J- x- }8 k( g) a else StackPush(stack,0);" R$ q& R& N/ x6 Q% K 8 F( e2 B( x2 |8 E0 z, x4 h if(a&0x01) StackPush(stack,1); 8 |" D- ]9 b; g: A ~ else StackPush(stack,0); % K v) d$ O2 H/ ]) y if(a&0x02) StackPush(stack,1); + S8 S" F& v3 j! S h1 ~' K& R- ^( R' b else StackPush(stack,0); ( [5 W) g6 u6 B }% X$ O if(a&0x04) StackPush(stack,1); ' J9 a, e7 q- y- Z; m else StackPush(stack,0); + z! c/ R) B$ h4 N1 E- [+ j if(a&0x08) StackPush(stack,1);" [0 Z9 a5 n W else StackPush(stack,0); 2 [: l3 s3 {) E) K8 R6 ^$ f } ) c ]& _2 B( s7 Z9 m5 _( E3 O for(i = 0;i<8;i++) ; Q9 O8 r- j2 R4 s {' N: S [/ n" g9 W' D int d = 0;0 F/ G# O" H7 a0 K StackPop(stack,&d); & v" M- [6 `1 g Q- I. e1 P. A if(i == 0)2 r$ Z" G8 C t, ~$ T/ \ if(d == 1) b |= 0x80;3 X6 H2 {/ K" N7 Y& W1 t& L7 k if(i == 1) ! h; A) L' Q g: ~8 R1 v if(d == 1) b |= 0x40; # h# Z! ?2 I/ w! N6 \8 F/ ?: s: H 0 _3 S3 r7 @9 n/ l/ k7 J. B if(i == 2)0 x9 W& N7 v9 Y: ? if(d == 1) b |= 0x20;# B, |3 ~5 F/ T, f" l3 e& K4 | 2 Z% r4 M4 I9 _% z a; L: A if(i == 3)3 }: ~7 [) e- T, @( b if(d == 1) b |= 0x10; ( r3 b, T( `" w( ^6 h) j' ` R7 R4 o1 ]# }& X if(i == 4)1 |) X& \$ @! h7 `" [* V% g$ p1 |8 }2 q if(d == 1) b |= 0x08;/ R q" b1 v; [( Z 3 E' ?, \$ W; F8 M if(i == 5) ! R. x% W8 D4 R/ @8 H if(d == 1) b |= 0x04;/ B0 k8 F! F" x; l$ S + v; p( u7 A: K- l if(i == 6) 7 |4 h. d& |! ~, V& ] if(d == 1) b |= 0x02; " b# z; {- o. N! Q ) V9 \# n- ]; [ if(i == 7)+ ^0 v% A7 R/ q4 j) d v5 f+ U: f if(d == 1) b |= 0x01;# E$ d7 {6 F3 I7 | 2 A V2 z" V" a% ^$ G5 `- ] } " `# i. D1 G6 E3 O2 R & L2 E# k2 O8 n printf("\nb:0x%x\n",b); ) U' l$ G: j5 c O1 e- ? return 0;1 I. q/ x" M' t, Y } 9 y7 U7 Z* L1 |( k% G! k5 N; @! I! _/ \6 L! Z2 w; ^8 o. u 执行如下：3 N0 r, N9 v7 { 0 Y0 o4 }6 b* m' X* V 除了用栈来实现，群里有位同学的答案让我眼前一亮 ; G1 }# [3 `% M#include * T6 K# U( a! a6 d1 B0 d . v6 W1 x- t( H, J( N struct charbits{8 @& H5 u' C d C' | unsigned char data1 : 4; ; @5 J" v/ w8 d5 t. _. ~& ?1 P unsigned char data2 : 4;/ N2 q0 Y( S9 L2 m1 `- ? }; ; q3 t( S) N( b k( | Q0 n6 ^ \+ n @7 M7 L5 J J6 _2 }% Funion dataChange{( f: k8 S; U% c Y+ I struct charbits charBits; , k: a1 u& n4 W4 Q2 P# ] unsigned char data; , h" a, p' K) ?7 L}datchange,*p; % v" c2 f9 e" r7 q2 G+ i 9 I3 ^+ L. K' }2 x9 w( R/ ]int main(){7 D2 R9 b5 {& Z+ y+ E 6 ~0 n0 m3 \% W unsigned char temp;9 {* z0 o, R- u' P 4 E8 v. |! Z1 Z p = &datchange;" Y |8 F) E* E s 5 ^9 h: S4 @6 X) \ datchange.data = 0x34; 3 ^, O* _/ o* ` 9 w0 U: h/ F! W# N6 a temp = p->charBits.data1;1 n8 l" q7 D1 L6 t: b) W/ ? 3 k% o/ C6 j0 i1 @ p->charBits.data1 = p->charBits.data2; 7 {: g% o+ v2 w" r % g; M0 d( w( `2 d8 | p->charBits.data2 = temp;7 d4 @ g% ]3 u9 P; E* v " ~6 H4 c7 e/ t5 _: S. G printf("data is %x", datchange.data);) U6 j& C8 \0 k( ` ( V3 j* O- B; Q, Y+ {2 n return 0;) _. V7 M; O2 i* b# S } ; |- I$ F* X& n/ x ' p i" ]" V: _ 完美演示了位域、共用体、结构体、指针的几个知识点~ ( c& L0 \5 N2 j1 i( l6 ~测试下位域的作用 7 @4 J* u3 K, p; p6 ~( K" Y#include ) E/ q: S6 B' J3 ]8 Y; m. U+ l, Q5 M: M; H* `. Z struct charbits{* L6 W6 j* g' p8 _8 _ unsigned char data1 : 1; % N. Z4 {1 |# w/ G unsigned char data2 : 3;& Z+ ?3 p) X2 M B };" a3 T4 T v/ _+ S" s+ | + N2 n5 @' X0 g1 ^* D5 R6 D ; m- G; l7 {0 U4 D4 R' @- Fstruct charbits1{. W' H% d4 T% W! T9 _, B7 }5 O+ W$ c unsigned char data1; 1 W1 G8 p1 P" e: C2 N! E unsigned char data2; * U* {% C$ M: _4 Y0 d o) g0 Y}; , j- @+ T9 P: e/ O; M7 e2 E! q6 d int main(){/ [$ u W- Y. g4 R: i! u& A* L ' e4 q4 }' P4 T. d7 { struct charbits a; " v1 Z+ T1 R& j2 A struct charbits1 b;- p o6 F' M: P8 }) J" \$ O printf("%d %d\n",sizeof(a),sizeof(b)); ( ]. |+ L2 ~; O/ Y4 N, x4 ] 2 c# K& T. L0 w# \0 }3 L /*赋值1看看*/ 2 L# n: P6 v7 u a.data1 = 1; ' T* D" {" g! I printf("%d\n",a.data1);# ?7 B6 T9 B; \* q- b /*赋值3看看*/ - ^/ Q6 U! z& f7 z a.data1 = 3; ' l% h/ U9 N) P& T+ [! @ printf("%d\n",a.data1); & I- Z* q3 N9 d K5 J4 }3 t8 }1 T /*赋值3看看*/" X7 |( l7 M7 o6 F( h a.data2 = 3;* }1 Z) v& k6 c7 \ I, f printf("%d\n",a.data2);. H' S# i3 |5 q* ~2 r2 S ) S2 j8 g1 u; X /*赋值7看看*/( x/ x6 _- o- E a.data2 = 7; . l& z: K5 q/ V; P1 ~1 o2 O printf("%d\n",a.data2);2 {6 U, b" m& J9 `9 V& K 5 h) ]) G' N9 o' f8 u " \ r8 A7 P- y9 f( U /*赋值8看看*/4 X1 z+ G" |) }/ _ a.data2 = 8;- F; U; y$ w) [) Y! \* J; Z printf("%d\n",a.data2);; o9 V0 i% E' P. z return 0; ( e! e6 c: j, ~2 k/ A# T- h}3 i9 j7 W/ N* J! D7 c3 L3 v' C 0 o& h# P4 ]* G- U# V/ a* E data1只能存 0和1，如果存其他值的话就会溢出变成0。 ; L q* n. f9 ]( zdata2是 3bits ，只能存 0~7，我们存 8 进去，就溢出变成 0。 + L' c5 }( f$ S/ J+ v* O5 I + g. d: Y) b0 g D' |' f9 p6 u( X5 ^- ^1 B6 t5 i+ G+ F; `0 i

[复制链接]

gaosmile 发布时间：2020-5-13 19:29

技术帖
文章封面:	-
文章简介:	-

昨晚在微信群看到一个读者发的面试题目，从网上截图出来的，我百思不得其解，题目如图。

幸好，我学过栈

然后我写了个小程序

第一个方法比较笨，当我写完自己的代码后，看到有同学发了自己的代码，我赶紧就发了个红包，一个是为了鼓励大家多讨论问题，一个是为了赞扬这样的行为。

第一个方法就是取出每一个bit，压栈，然后再出栈，你想怎么排序都没有问题。

#include "stdio.h"
#include "stdlib.h"

struct List{
int data;
struct List * next;
};

struct Stack{
struct List *head;
int size;
};

struct Stack * StackInit(void)
{
struct Stack *stack = NULL;
stack =  (struct Stack*)malloc(sizeof(struct Stack));
stack->head = (struct List *)malloc(sizeof(struct List));
stack->head->next = NULL;
stack->size = 0;
return stack;
}

int StackPush(struct Stack *stack,int data)
{
struct List *tmp = (struct List *)malloc(sizeof(struct List));
tmp->data = data;
tmp->next = stack->head->next;
stack->head->next = tmp;
stack->size++;
//printf("push:%d \n",data);
return 0;
}

int IsStackEmpty(struct Stack *stack)
{
if(stack->head->next == NULL){
//printf("stack null\n");
return 1;
}else{
//printf("stack is not null\n");
return 0;
}
}

int StackPop(struct Stack *stack,int *data)
{
struct List *tmp = NULL;
if(IsStackEmpty(stack))
return -1;

tmp = stack->head->next;
*data = tmp->data;
stack->head->next = tmp->next;
stack->size--;
if(tmp!=NULL)
free(tmp);

//printf("pop:%d \n",*data);
return 0;
}

int main(void)
{
int i = 0;
unsigned char a = 0x71;
unsigned char b = 0;

struct Stack *stack = NULL;
stack = StackInit();

printf("a:0x%x\n",a);
for(i = 0;i<8;i++)
{

if(a&0x10) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x20) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x40) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x80) StackPush(stack,1);
else    StackPush(stack,0);

if(a&0x01) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x02) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x04) StackPush(stack,1);
else    StackPush(stack,0);
if(a&0x08) StackPush(stack,1);
else    StackPush(stack,0);
}
for(i = 0;i<8;i++)
{
int d = 0;
StackPop(stack,&d);
if(i == 0)
if(d == 1) b |= 0x80;
if(i == 1)
if(d == 1) b |= 0x40;

if(i == 2)
if(d == 1) b |= 0x20;

if(i == 3)
if(d == 1) b |= 0x10;

if(i == 4)
if(d == 1) b |= 0x08;

if(i == 5)
if(d == 1) b |= 0x04;

if(i == 6)
if(d == 1) b |= 0x02;

if(i == 7)
if(d == 1) b |= 0x01;

}

printf("\nb:0x%x\n",b);
return 0;
}

执行如下：

除了用栈来实现，群里有位同学的答案让我眼前一亮

#include <stdio.h>

struct charbits{
unsigned char data1 : 4;
unsigned char data2 : 4;
};

union dataChange{
struct charbits charBits;
unsigned char data;
}datchange,*p;

int main(){

unsigned char temp;

p = &datchange;

datchange.data = 0x34;

temp = p->charBits.data1;

p->charBits.data1 = p->charBits.data2;

p->charBits.data2 = temp;

printf("data is %x", datchange.data);

return 0;
}

完美演示了位域、共用体、结构体、指针的几个知识点~

测试下位域的作用

#include <stdio.h>

struct charbits{
unsigned char data1 : 1;
unsigned char data2 : 3;
};

struct charbits1{
unsigned char data1;
unsigned char data2;
};

int main(){

struct charbits a;
struct charbits1 b;
printf("%d %d\n",sizeof(a),sizeof(b));

/*赋值1看看*/
a.data1 = 1;
printf("%d\n",a.data1);
/*赋值3看看*/
a.data1 = 3;
printf("%d\n",a.data1);

/*赋值3看看*/
a.data2 = 3;
printf("%d\n",a.data2);

/*赋值7看看*/
a.data2 = 7;
printf("%d\n",a.data2);

/*赋值8看看*/
a.data2 = 8;
printf("%d\n",a.data2);
return 0;
}

data1只能存 0和1，如果存其他值的话就会溢出变成0。

data2是 3bits ，只能存 0~7，我们存 8 进去，就溢出变成 0。