C語言數據結構實現鏈表逆序並輸出。本站提示廣大學習愛好者:(C語言數據結構實現鏈表逆序並輸出)文章只能為提供參考,不一定能成為您想要的結果。以下是C語言數據結構實現鏈表逆序並輸出正文
C語言數據結構實現鏈表逆序並輸出
將一個鏈表逆序並輸出。我用了兩種方法來實現,第一種是借助了一個新的空鏈表;第二種是在原來鏈表的基礎上直接實現逆序。
實例代碼:
頭文件:
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; typedef struct Node {//結點結構 ElemType value; //值域 struct Node *next;//指針域 }Node,*ptr_Node; typedef struct LinkList {//鏈表結構 ptr_Node head; //鏈表頭結點指針 ptr_Node tail;//鏈表尾結點指針 int length; //鏈表長度 }LinkList,*ptr_LinkList; ptr_LinkList CreateList(void) {//創建一個空鏈表 ptr_LinkList linklist; linklist=(LinkList *)malloc(sizeof(LinkList)); if(!linklist) { printf("allocation failed.\n"); } linklist->head=NULL; linklist->tail=NULL; linklist->length=0; return linklist; } bool IsListEmpty(ptr_LinkList linklist) {//判斷鏈表是否為空 if(linklist->length==0) { return true; } return false; } void InsertListHead(ptr_LinkList linklist,ElemType element) {//在表頭插入值為element的結點作為新的表頭 ptr_Node ptr_node; ptr_node=(Node *)malloc(sizeof(Node)); //生成插入結點 if(!ptr_node) { printf("allocation failed.\n"); } else { ptr_node->value=element; if(linklist->length==0) { linklist->head=ptr_node; linklist->tail=linklist->head; linklist->tail->next=NULL; } else { ptr_node->next=linklist->head; linklist->head=ptr_node; //鏈表頭 } linklist->length++; //鏈表長度加1 } } void InsertListTail(ptr_LinkList linklist,ElemType element) { ptr_Node ptr_node; ptr_node=(Node *)malloc(sizeof(Node)); //生成插入結點 if(!ptr_node) { printf("allocation failed.\n"); } else { ptr_node->value=element; if(linklist->length==0) { linklist->head=ptr_node; linklist->tail=linklist->head; linklist->tail->next=NULL; } else { linklist->tail->next=ptr_node; linklist->tail=ptr_node; //鏈表尾 } linklist->length++; //鏈表長度加1 } } void InsertListPosition(ptr_LinkList linklist,int pos,ElemType element) { int i; ptr_Node ptr_node; ptr_Node temp_ptr_node; if(pos<1 || pos>linklist->length) { printf("The insert position is invalidate.\n"); } else { ptr_node=(Node *)malloc(sizeof(Node)); //生成插入結點 if(!ptr_node) { printf("allocation failed.\n"); } ptr_node->value=element; if(pos==1) { InsertListHead(linklist,element); } else if(pos==linklist->length) { InsertListTail(linklist,element); } else { temp_ptr_node=linklist->head; for(i=1;i<pos-1;i++) {//找到第pos-1個結點 temp_ptr_node=temp_ptr_node->next; } ptr_node->next=temp_ptr_node->next; temp_ptr_node->next=ptr_node; linklist->length++; } } } void Destroy(ptr_LinkList linklist) {//銷毀鏈表 ptr_Node p=linklist->head; ptr_Node q; while(p) {//釋放每個結點空間 q=p->next; free(p); p=NULL; p=q; } } void Traverse(ptr_LinkList linklist) {//輸出整個鏈表 ptr_Node p; p=linklist->head; while(p) { printf("%4d",p->value); p=p->next; } }
頭文件中實現了鏈表的幾個基本的操作,有的是必須的,有些是非必須的。
實現代碼:
#include "stdafx.h" #include "LinkList.h" #include <conio.h> ptr_LinkList InvertList(ptr_LinkList list) {//該方法借助一個新的空鏈表來實現鏈表逆序 ptr_LinkList inverted_linklist; ptr_Node p; p=list->head; inverted_linklist=CreateList();//創建一個空鏈表 while(p) {//將list鏈表中的結點值逆序輸入新創建的鏈表中,實現鏈表反轉 InsertListHead(inverted_linklist,p->value); p=p->next; } return inverted_linklist; } void InvertLinkList(ptr_LinkList linklist) {//該方法直接對原有鏈表實現逆序,不借助其他鏈表 ptr_Node p,q,r,m; m=p=linklist->head; q=p->next; r=q->next; while(r) {//依次對鏈表中的結點進行反轉 q->next=p; p=q; q=r; r=r->next; } q->next=p; //最後一個結點反轉 linklist->head=q; linklist->tail=m; linklist->tail->next=NULL; } int _tmain(int argc, _TCHAR* argv[]) { ptr_LinkList linklist; ptr_LinkList list; linklist=CreateList(); if(linklist) { printf("We have created a new linklist.\n"); } InsertListHead(linklist,12); InsertListHead(linklist,35); InsertListHead(linklist,66); InsertListHead(linklist,06); InsertListHead(linklist,11); InsertListHead(linklist,54); InsertListHead(linklist,79); Traverse(linklist); printf("\n"); printf("The first method:\n"); list=InvertList(linklist); Traverse(list); printf("\n"); printf("The second method:\n"); InvertLinkList(linklist); Traverse(linklist); printf("\n"); getch(); return 0; }
感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!