鏈表結構的反轉,基本上把基本鏈表的內容都做了一遍。
比如,基本鏈表的創建,鏈表的遍歷,然後就是反轉鏈表了。
鏈表結構如下:
a->b->c->d->e->NULL
弄三個指針head,mid,last,設置初值:
head指向a
mid指向NULL
然後開始指針運動了:
while(head != NULL)
{
last=mid;
mid=head;
head=head->next;
mid->next=last;
}
//last往mid走,mid往head走,head往head->next走,它們一直向前走,邊走邊mid->next=last,直到head==NULL為止。
完整的代碼如下:
/* ======================================== */
/* 程式實例: 3_8.c */
/* 鏈結串列的反轉 */
/* ======================================== */
#include <stdlib.h>
struct llist /* 串列結構宣告 */
{
int num; /* 郵寄編號 */
struct llist *next; /* 指向下一標簽 */
};
typedef struct llist node; /* 定義新型態 */
typedef node *llink; /* 定義新型態指標 */
/* ---------------------------------------- */
/* 鍵結串列的列印 */
/* ---------------------------------------- */
void printllist(llink ptr)
{
while ( ptr != NULL ) /* 串列走訪回路 */
{
printf("[%d]",ptr->num); /* 列印節點資料 */
ptr = ptr->next; /* 指向下一節點 */
}
printf("
"); /* 換行 */
}
/* ---------------------------------------- */
/* 鏈結串列的建立 */
/* ---------------------------------------- */
llink createllist(int *array,int len)
{
llink head; /* 串列的開始指標 */
llink ptr,ptr1;
int i;
/* 建立第一個節點 */
head = ( llink ) malloc(sizeof(node)); /* 配置記憶體 */
if ( !head ) /* 檢查指標 */
return NULL;
head->num = array[0]; /* 建立節點內容 */
head->next = NULL; /* 設定指標初值 */
ptr = head; /* 將ptr指向串列開始 */
for ( i = 1; i < len; i++ ) /* 建立其它節點回路 */
{
ptr1 = ( llink ) malloc(sizeof(node));
if ( !ptr1 )
return NULL;
ptr1->num = array[i]; /* 建立節點內容 */
ptr1->next = NULL; /* 設定指標初值 */
ptr->next = ptr1; /* 連結節點 */
ptr = ptr->next; /* 指向下一節點 */
}
return head;
}
/* ---------------------------------------- */
/* 鏈結串列的反轉 */
/* ---------------------------------------- */
llink invertllist(llink head)
{
llink mid,last;
mid = NULL; /* mid是head的前節點 */
while ( head != NULL )
{
last = mid; /* last是mid的前節點 */
mid = head;
head = head->next; /* 下一個節點 */
mid->next = last; /* mid指向前節點last */
}
return mid;
}
/* ---------------------------------------- */
/* 鏈結串列的記憶體釋回 */
/* ---------------------------------------- */
void freellist(llink head)
{
llink ptr;
while ( head != NULL ) /* 走訪串列回路 */
{
ptr = head;
head = head->next; /* 指向下一節點 */
free(ptr); /* 釋回節點記憶體 */
}
}
/* ---------------------------------------- */
/* 主程式: 反轉串列 */
/* ---------------------------------------- */
void main()
{
int llist1[6] = { 1, 2, 3, 4, 5, 6 }; /* 陣列內容 */
llink head; /* 指向串列開始 */
head = createllist(llist1,6); /* 建立串列 */
if ( !head )
{
printf("記憶體配置失敗!
");
exit(1);
}
printf("原來的鏈表: ");
printllist(head); /* 列印原來串列 */
head = invertllist(head); /* 反轉串列 */
printf("反轉後的鏈表: ");
printllist(head); /* 列印反轉後串列 */
freellist(head); /* 釋回串列記憶體 */
}