數組與鏈表等順序表逆置

一)數組的逆置
(1)算法

#indclude<stdio.h>

#define N  8

main()
{ 

    int array[N] = {100,90,80,70,60,50,50,40};
    int i,j,t;

    for(i=0,j=N-1;i<j; i++, j--)     
    {     
            t        = array[i];
         array[i] = array[j];
         array[j] = t;
     }

     for(i=0,i<listsize;i++)
          printf("%d",qlist.data[i])
}

(2)時間復雜度
由於只需循環N/2即可完成逆置,所以時間復雜度為O(N/2).


(二)單向鏈表的逆置

(1)算法

//定義結構體
struct  t_node
{
  int data;
  struct t_node *next;
};
//定義別名
typedef struct  t_node Node;

//定義鏈表變量
Node  * example_link = NULL;

/*
*功能：逆轉鏈表
*輸入：x = 原鏈表
*輸出：無
*返回值：逆轉後的新鏈表
*/
Node reverse( Node * x)
{
  if( NULL==x )
    return NULL;
  
  link t=NULL;
  link r=NULL, y=x;  //(0)
  while(y!=NULL)
  {
    t = y->next;   //(1)
    y->next = r;   //(2)
    r = y;         //(3) 
    y = t;         //(4)
   }

  return r;     //返回逆置後的鏈表
}

/*
*功能：初始化鏈表
*輸入：無
*輸出：無
*返回值：無
*/
void Init_Link(void)
{  
  Node *pNext = NULL; //游標
   //頭節點
   example_link = (Node *)malloc( sizeof(Node) );    
   if(NULL == example_link)
       return;
   example_link->data = 100;
   example_link->next = NULL;

  //中間節點
  pNext = example_link; //為游標賦值
  for(i=1,i<N,i++)
  { 
    pNext->next = (Node *)malloc( sizeof(Node) );    
     if(NULL == pNext->next)
       return;
    pNext->next->data = 100 - i*10;
    pNext->next->next = NULL;
    pNext = pNext->next; //移動游標
  }

}


main()
{ 
  int i,n;
  Node *pNext = NULL;
  Node *reverse_link = NULL;

  //初始化鏈表
  Init_Link();

  if(NULL == example_link)
       return;

   //顯示原鏈表
   printf("原鏈表數值:\n");
   pNext = example_link;   
   while(pNext != NULL)
   {
      printf("%d, ",pNext->data);
      pNext = pNext->next;
   }
   printf("\n");

   //逆置鏈表
   reverse_link = reverse(example_link);

   printf("逆置後的鏈表數值:\n");
   pNext = reverse_link;   
   while(pNext != NULL)
   {
      printf("%d, ",pNext->data);
      pNext = pNext->next;
   }

   getch();

}//endmain()

(2)時間復雜度
由於 reverse函數須遍歷整個鏈表,所以時間復雜度為O(N).

本文出自 “C++” 博客，請務必保留此出處http://ljqy27.blog.51cto.com/1054/40153