一)数组的逆置(1)算法#indclude<stdio.h>#define N  8main(){     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).

评论