不用辅助节点,使用_asm{}实现单链表的反转。

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

由于使用宏,还是有要引入几个int类型的临时变量及指针,没有完全发挥xor操作的速度,改用块汇编实现。

只是替换了三处,测试与用C实现的结果一样。速度及空间应该都有改良。

#include <stdio.h>

#include <stdlib.h>

#define SWAP(a,b) { a=a^0xFFFFFFFF; b=b^a; a=a^b; b=b^0xFFFFFFFF; b=b^a; }

#define SWAP_POINT(pA,pB) { int h,t; pLinkList ph,pt; h=(int)pA; t=(int)pB; ph = (pLinkList)h; pt = (pLinkList)t; SWAP(h,t); pA = (pLinkList)h; pB = (pLinkList)t; }

typedef struct tagLinkList

{

int data;

struct tagLinkList *next;

} LinkList , *pLinkList ;

int main(int argc, char* argv[])

{

/*

int a=10,b=99;

_asm {

mov eax,a

mov ebx,b

xor ebx,eax

xor eax,ebx

xor ebx,eax

mov a,eax

mov b,ebx

}

printf("a=%d , b=%d \n",a,b);

*/

int count,i;

pLinkList Head,tmpNode,Tail;

Head=NULL;

// Construct LinkList.

printf("Enter count:"); scanf("%d",&count);

if(count <= 1)

{

printf("Count error,must large than 1.\n");

exit(1);

}

for(i=1;i<=count;++i)

{

tmpNode=(LinkList *)malloc(sizeof(LinkList));

tmpNode->data=i;

printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->data);

if(!Head)

Tail=Head=tmpNode;

else{

Tail->next=tmpNode;

Tail=tmpNode;

}

}

Tail->next=NULL;

// Reverse LinkList.

if(2 == count) {

//N=2

//SWAP_POINT(Head,Tail->next);

_asm {

mov eax,DWORD PTR Head

mov edx,DWORD PTR Tail

mov esi,4

mov ebx,[edx][esi]

xor ebx,eax

xor eax,ebx

xor ebx,eax

mov Head,eax

mov [edx][esi],ebx

}

SWAP_POINT(Head,Tail);

SWAP_POINT(Head->next->next,Tail);

}else if(3 == count) {

//N=3

SWAP_POINT(Head->next,Tail->next);

SWAP_POINT(Head,Tail);

SWAP_POINT(Head->next->next,Tail);

}else{

//N>=4

SWAP_POINT(Head->next,Tail->next);

SWAP_POINT(Head,Tail);

SWAP_POINT(Head->next->next,Tail);

SWAP_POINT(Head->next,Tail->next);

SWAP_POINT(Head->next->next,Tail);

for(i=6;i<=count;++i)

{

//SWAP_POINT(Head->next,Tail);

_asm {

mov edx,DWORD PTR Head

mov ebx,DWORD PTR Tail

mov esi,4

mov eax,[edx][esi]

xor ebx,eax

xor eax,ebx

xor ebx,eax

mov Tail,ebx

mov [edx][esi],eax

}

//SWAP_POINT(Head->next->next,Tail);

_asm {

mov eax,DWORD PTR Head

mov ebx,DWORD PTR Tail

mov esi,4

mov edx,[edx][esi]

mov eax,[edx][esi]

xor ebx,eax

xor eax,ebx

xor ebx,eax

mov Tail,ebx

mov [edx][esi],eax

}

}

}

//Output reversed LinkList.

tmpNode=Head;

printf("After reverse.\n");

for(i=1;i<=count;++i)

{

printf("No.=%d\t Address:%X , Data:%d\n",i,tmpNode,tmpNode->data);

tmpNode = tmpNode->next;

}

printf("Tail->data = %d\n",Tail->data);

//Release LinkList

printf("Release LinkList.\n");

for(i=1;i<=count;++i)

{

tmpNode=Head;

Head = Head->next;

free(tmpNode);

}

return 0;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航