#include<stdio.h>
#include <stdlib.h>
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Position;
typedef struct Node
{
int Element;
Position Next;
}link,*list;
list MakeEmpty( list L )
{
L = (list)malloc( sizeof( struct Node ) );
if( L == NULL )
{printf( "Out of memory!" );
return 0;
}
L->Next = NULL;
return L;
}
Position Find( int X, list L )
{
Position P;
P = L->Next;
while( P != NULL && P->Element != X )
P = P->Next;
return P;
}
Position FindPrevious( int X, list L )
{
Position P;
P = L;
while( P->Next != NULL && P->Next->Element != X )
P = P->Next;
return P;
}
list input(list L)
{
int n;int a,capacity;list head,temp,tt;
head=L;
tt=head;
printf("输入链表容量:");
scanf("%d",&capacity);
printf("输入元素:");
for(n=0;n<capacity;n++)
{
temp=(list)malloc(sizeof(struct Node));
temp->Next=NULL;
scanf("%d",&a);
temp->Element=a;
tt->Next=temp;
tt=temp;
}
return(head);
}
list ChangePosition(int x,int y,list L)
{
list head,tempx,tempy,position_x,position_y,posotion_rx,posotion_ry;
head=L;
posotion_rx=FindPrevious( x, head );
posotion_ry=FindPrevious( y, head );
position_x=Find( x, head );
position_y=Find( y, head );
tempx= position_x->Next;
tempy= position_y->Next;
if(tempx==position_y)
{
posotion_rx->Next=position_y;
position_y->Next=position_x;
position_x->Next=tempy;
}
else
{
posotion_rx->Next=position_y;
position_y->Next=tempx;
posotion_ry->Next=position_x;
position_x->Next=tempy;
}
return(head);
}
list reverse(list L)
{
list array[1000],temp,head;
int i=0;
head=L;
temp=head->Next;
while(temp!=NULL)
{
array[i]=temp;
temp=temp->Next;
i++;
}
temp=head;
while(i>=0)
{
temp->Next=array[i-1];
temp=array[i-1];
i--;
}
array[0]->Next=NULL;
return(head);
}
void printLink(list L)
{ list temp;
temp=L->Next;
while(temp!=NULL)
{printf("%3d",temp->Element);
temp=temp->Next;
}
printf("\n");
}
void main()
{
list H,temp_H,Ha,position_it;int find_it,change_a,change_b;
H=MakeEmpty( H );
H=input(H);
printf("生成的链表:");
printLink(H);
printf("请输入要找的元素:");
scanf("%d",&find_it);
position_it=Find( find_it, H );
if(position_it==NULL)
printf("没有找到元素\n");
else
{
printf("找到元素:");
printf("%d\n",position_it->Element);
}
printf("输入要交换位置的元素:");
scanf("%d%d",&change_a,&change_b);
Ha=ChangePosition( change_a,change_b,H);
printf("\n交换元素后:");
printLink(Ha);
temp_H=MakeEmpty( temp_H );
printf("输入要倒置的链表:");
temp_H=input(temp_H);
temp_H=reverse(temp_H);
printf("倒置后的链表:");
printLink(temp_H);
}