单链表操作

时间：2010-08-31 来源：chengbin_liu

/* ************************************************************************
*       Filename: main.c
*    Description:
*        Version: 1.0
*        Created: 08/31/2010 05:13:53 PM
*       Revision: none
*       Compiler: gcc
*         Author: chengbin_liu,
*        Company:
* ************************************************************************/ #include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h> typedef struct node
{
int data;
    struct node *next;
}node;
//==============================================================================
node *create()
{
int i=0;
node *head,*p,*q;
int x=0;
head=(node *)malloc(sizeof(node));
while(1)
{
  printf("input the data:");
  scanf("%d",&x);
  if(x==0)
   break;
  p=(node *)malloc(sizeof(node));
  p->data=x;
  if(++i==1)
  {
   head->next=p;
  }
  else
  {
   q->next=p;
  }
  q=p;
}
q->next=NULL;
return head;
}
//=================================================================================
void print(node *head)
{
node *p;
int index=0;
if(head->next==NULL)
  return;
p=head->next;
while(p!=NULL)
{
  printf("the %d node is %d\n",++index,p->data);
  p=p->next;
}
}
//================================================================================
node *search_node(node *head,int pos)
{
node *p=head;
if(pos<0)
{
  return NULL;
}
if(pos==0)
{
  return head;
}
if(p==NULL)
{
  return NULL;
}
while(--pos)
{
  if((p=p->next)==NULL)
  {
   break;
  }
}
return p;
}
//=============================================================================
node *insert_node(node *head,int pos, int data)
{
node *item=NULL;
node *p;
item=(node *)malloc(sizeof(node));
item->data=data;
if(pos==0)
{
  head->next=item;
  return head;
}
p=search_node(head,pos);
if(p!=NULL)
{
  item->next=p->next;
  p->next=item;
}
return head;
}
//=============================================================================
node *delete_node(node *head,int pos)
{
node *item=NULL;
node *p=head->next;
if(p==NULL)
{
  printf("link is empty!\n");
  return NULL;
}
p=search_node(head,pos-1);
if(p != NULL && p->next != NULL)
{
  item = p->next;
  p->next = item->next;
// delete item;
}
return head;
}
//=============================================================================
node *reverse(node *head)
{
node *p,*q,*r;
if(head->next==NULL)
{
  return head;
}
p=head->next;
q=p->next;
p->next=NULL;
while(q!=NULL)
{
  r=q->next;
  q->next=p;
  p=q;
  q=r;
}
head->next=p;
return head;
}
//==============================================================================
node *search_mid(node *head)
{
int i=0;
int j=0;
node *current=NULL;
node *middle=NULL;
current=middle=head->next;
while(current!=NULL)
{
  if(i/2 > j)
  {
   j++;
   middle=middle->next;
  }
  i++;
  current=current->next;
}
return middle;
}
//============================================================================
bool IsLoop(node *head,node **start)
{
node *p1=*p2=head;
if(head==NULL || head->next==NULL)
{
  return false;
}
do
{
  p1=p1->next;
  p2=p2->next->next;
}while(p2 && p2->next && p1!=p2);
if(p1=p2)
{
  *start=p1;
  return true;
}
else
return false;
}
//=============================================================================
int main()
{
//int pos,data;
// int pos;
node *head=create();
printf("djkfhjkshdfj\n");
// printf("length=%d\n",Length(head));
// printf("input the delete node:");
// scanf("%d",&pos);

//head=search_node(head,pos);
//head=insert_node(head,pos,data);
//head=delete_node(head,pos);
//head=reverse(head);
//head=search_mid(head);
//=================================================================
bool bloop=false;
node *start=head->next->next->next->next;
start->next=head->next;
node *loopstart=NULL; bloop=IsLoop(head,&loopstart);
printf("bloop=%d\n",bloop); //=================================================================
print(head);
return 0;
}