link.cpp

编写实现链表排序的一种算法。对于链表这种数据结构

// link.cpp : Defines the entry point for the console application.
//

#include <iostream.h> 
#include <stdafx.h>
#include <string.h>
#include <stdio.h>

typedef struct linka {
     int Data;
     linka* Next;
}LNode;


void L_convert(LNode **h) //链表反转（循环方法）//遍历交换
{ 
	if(h==NULL)
		return;
    LNode *s=*h; 
    LNode *p1, *p2, *p3; 
    p1=s; 
    p2=p1->Next;
	if(p2==NULL)
		return;
    p3=p2->Next;
	if(p3==NULL)
	{
		p2->Next = p1;
		p1->Next = NULL;
		*h = p2;
		return;
	}
    while(p3) 
    { 
         p2->Next =p1; 
         p1=p2; 
         p2=p3; 
         p3=p3->Next; 
    } 
    p2->Next =p1; 
	(*h)->Next = NULL;
    *h=p2; 
} 

void reverse(LNode** head)  //链表反转（循环方法）//遍历交换
{
     if(head ==NULL)
          return;
     LNode *pre, *cur, *ne;
     pre=*head;
     cur= (*head)->Next;
	 if(cur==NULL)
		 return;
     while(cur)
     {
          ne = cur->Next;
          cur->Next = pre;
          pre = cur;
          cur = ne;
     }
     (*head)->Next = NULL;
     *head = pre;
}

//链表反转（递归方法）
LNode *reverse2(LNode** Head)
{
         if((*Head)->Next!=NULL)   
          {   
                    LNode   *temp=reverse2(&(*Head)->Next);   
                    (*Head)->Next->Next=*Head;   
                    (*Head)->Next=NULL;   
                    return   temp;   
          }   
          return   *Head;   
}

//截断再连接
void ReserseInter(LNode ** head, LNode ** start)
{
     if((*head)==NULL || (*start)==NULL)
          return;

     LNode *pre, *cur, *ne;
	 LNode *ps = (*start)->Next;
	 if(ps==NULL)
		 ps = *head;
     pre=*head;
     cur=(*head)->Next;
     while(cur)
     {
          ne = cur->Next;
          cur->Next = pre;
          pre = cur;
          cur = ne;
     }
     (*head)->Next = pre;
	 *head = ps->Next;
     ps->Next = NULL;
}

//奇偶对调节点
void oddrvevenlink(LNode** head)
{
     if(head ==NULL)
          return;
     LNode *pre, *cur, *ne;
     pre = *head;
     cur = (*head)->Next;
	 if(cur==NULL)
		 return;
	 ne = cur->Next;
	 cur->Next = pre;
	 pre->Next = ne;
     *head = cur;
	 cur = ne;
	 if(ne)
	   ne = cur->Next;
	 else 
		 return;
     while(cur && ne)
     {
		  cur->Next = ne->Next;
		  ne->Next = cur;
          pre->Next = ne;
          pre = cur;
          cur = cur->Next;
   	      if(cur)
	        ne = cur->Next;
	      else 
		     break;
     }
	 if(cur)
		 cur->Next = NULL;
	 else
         pre->Next = NULL;

}
//奇偶对调数值
void oddrvevennum(LNode** head)
{
     if(head ==NULL)
          return;
     LNode *pre, *cur;
	 int temp;
     pre = *head;
     cur = (*head)->Next;
	 if(cur==NULL)
		 return;

     while(cur!=NULL)
     {
		 temp = pre->Data;
		 pre->Data = cur->Data;
		 cur->Data = temp;
         pre = cur->Next;
		 if(pre!=NULL)
			 cur = pre->Next;
   	     else
		     break;
     }
}
//排序
void order1(LNode** head)  //复杂度 O(n*n) 冒泡法
{
    if(head ==NULL)
         return;
	LNode  *p,*q;
    int   temp;
    q=*head;
    while(q->Next!=NULL)
    {
         p=*head;
         while(p->Next!=NULL)             //这个判断有冗余，待改进
         {       
            if(p->Data > p->Next->Data)       //交换数值
			{
                  temp=p->Data;
                  p->Data=p->Next->Data;
                  p->Next->Data=temp;
            }
            p=p->Next;
		 }   
         q=q->Next;
	}

}

//排序
void order2(LNode** head)  //复杂度 O(n)  插入法
{
  if(head ==NULL)
        return;
  LNode *pre, *cur, *ne;
  LNode *ppre;
  pre = (*head);
  cur = (*head)->Next;
  if(cur==NULL)
	  return;
  ne=cur->Next;     
  ppre=*head;
  while(cur!=NULL)
  {
	  if(ppre->Data>cur->Data)
	  {
		  pre->Next=ne;
          cur->Next=ppre;
		  (*head)=cur;
	  }
	  else
	  {
   	     while(ppre!=cur)
		 {
		    if(ppre->Next->Data>cur->Data)
			{
			   cur->Next=ppre->Next;
			   ppre->Next=cur;
			   pre->Next=ne;
			   break;
			}
		    ppre=ppre->Next;
		 }
	  }
	  ppre=*head;
	  if(pre->Next!=ne)
		  pre=cur;
	  cur=ne;
	  if(ne==NULL)
		  break;
	  else
	      ne=ne->Next;
  }

}

int find_circle(LNode** head)
{
    LNode* fast = *head;
    LNode* slow = *head;
    if (NULL == fast)
    {
        return -1;
    }
    while (fast && fast->Next)
    {
        fast = fast->Next->Next;
        slow = slow->Next;
        if (fast == slow)
        {
            return 1;
        }
    }
    return 0;
}


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

	 struct TMyList{ 
     int Data; 
     LNode* Next; 
     }; 
     LNode* p; 
     LNode* Head=new LNode; 
     Head->Data=1; 
     Head->Next=NULL; 
     p=Head; 
     for(int i=2;i<12;i++) 
     { 
         LNode* l=new LNode; 
         l->Data=i; 
         p->Next=l; 
         p=l; 
         p->Next=NULL; 
     } 
     p=Head;
     printf("\n原始链表序列\n "); 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n对调节点\n "); 
	 oddrvevenlink( &Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n对调数值\n "); 
	 oddrvevennum( &Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 
     
     printf("\n遍历逆序1\n "); 
	 L_convert( &Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n遍历逆序2\n "); 
     reverse(&Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n递归逆序\n "); 
	 Head = reverse2( &Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n截断逆序\n "); 
	 p=Head->Next->Next->Next;
     ReserseInter(&Head, &p);
	 p=Head->Next->Next;
     ReserseInter(&Head, &p);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     printf("\n排序链表\n "); 
	 order1( &Head);
     p=Head; 
     while(p!=NULL){ 
         printf("%2d, ",p->Data); 
         p=p->Next; 
     } 

     p=Head; 
     for(i=1;i<11;i++) 
     { 
         p=p->Next; 
     } 
	 p->Next=Head;
	 if(find_circle(&Head))
         printf("\nFind circle\n"); 

     printf("\n"); 
     return 0; 
  }