数组与链表等顺序表逆置
一)数组的逆置
(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).