一)數組的逆置

(1)算法

#indclude

#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

{

t????????=?array[i];

array[i]?=?array[j];

array[j]?=?t;

}

for(i=0,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

{

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语言链表实现数组逆置,数组与链表等顺序表逆置的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。