鏈表實現數據元素逆置是一個很常用的實例,在順序表實現輸入數據逆置那篇博客需要額外的一個逆置函數,在主函數中實現逆置還需要調用逆置函數。這一篇就全部用鏈表的知識來實現就地逆置並且輸出逆置後的數據元素。
先要構建一個帶頭結點的單鏈表,再來重新定義結點類型,在主函數中實現就地逆置的代碼為:
#include using namespace std; #include #include typedef int ElemType; typedef struct LNode//定義鏈表的結點類型 { ElemType data; struct LNode *next; }LNode,*LinkList; int main() { LinkList L,q; L=(LinkList)malloc(sizeof(LNode));//申請的頭結點 L->next=NULL; LinkList p=L; cout<<"請輸入鏈表的10個數據元素:"; for(int i=0;i<10;i++) { LinkList s=(LinkList)malloc(sizeof(LNode));//申請新的結點 cin>>s->data;//輸入結點的數據元素 p->next=s; p=s; } p->next=NULL; p=L->next; cout<<"鏈表順序輸出:"; while(p)//實現鏈表的順序輸出 { cout<data<<","; p=p->next; } cout<next; L->next=NULL; while(q)//實現鏈表就地逆置 { p=q->next; q->next=L->next; L->next=q; q=p; } p=L->next; cout<<"逆置後輸出:"; while(p)//就地逆置鏈表輸出 { cout<data<<","; p=p->next; } cout<
如果向鏈表輸入的十個數據元素為:0 1 2 3 4 5 6 7 8 9
輸出的結果為:
這樣的輸入感覺挺麻煩的,那麼就來用產生隨機數的方法來實現輸入數據元素,並且把建立的逆置單鏈表實現獨立算法與主函數區別開來。完整的代碼為:
#include using namespace std; #include #include #include typedef int ElemType; typedef struct LNode//定義鏈表的結點類型 { ElemType data; struct LNode *next; }LNode,*LinkList; int main() { srand(time(0));//實現每時每刻的隨機種子 LinkList L,q; L=(LinkList)malloc(sizeof(LNode));//申請的頭結點 L->next=NULL; LinkList p=L; for(int i=0;i<10;i++) { LinkList s=(LinkList)malloc(sizeof(LNode));//申請新的結點 s->data=rand()%100+1;//將產生的10個隨機數賦值結點的數據元素 p->next=s; p=s; } p->next=NULL; p=L->next; cout<<"鏈表順序輸出:"; while(p)//實現鏈表的順序輸出 { cout<data<<","; p=p->next; } cout<next; L->next=NULL; while(q)//實現鏈表就地逆置 { p=q->next; q->next=L->next; L->next=q; q=p; } p=L->next; cout<<"逆置後輸出:"; while(p)//就地逆置鏈表輸出 { cout<data<<","; p=p->next; } cout<
點擊程序運行的兩次結果為