您好,登錄后才能下訂單哦!
本文實(shí)例講述了C++數(shù)據(jù)結(jié)構(gòu)與算法之反轉(zhuǎn)鏈表的方法。分享給大家供大家參考,具體如下:
算法概述:要求實(shí)現(xiàn)將一條單向鏈表反轉(zhuǎn)并考慮時(shí)間復(fù)雜度。
算法分析:
數(shù)組法(略):
將列表元素逐個(gè)保存進(jìn)數(shù)組,之后再逆向重建列表
點(diǎn)評(píng):實(shí)現(xiàn)邏輯最簡(jiǎn)單,需要額外的內(nèi)存開(kāi)銷。
移動(dòng)指針:
通過(guò)三個(gè)指針逐個(gè)從鏈表頭開(kāi)始逐一反轉(zhuǎn)鏈表元素的指針
點(diǎn)評(píng):不需要額外的內(nèi)存開(kāi)銷,會(huì)改變?cè)兼湵怼?/p>
遞歸:
以遞歸的方式首先找到鏈表尾部,再逐一反轉(zhuǎn)指針
點(diǎn)評(píng):不需要額外的內(nèi)存開(kāi)銷,不會(huì)改變?cè)兼湵怼?/p>
算法實(shí)現(xiàn):
構(gòu)建鏈表結(jié)構(gòu)
/* 節(jié)點(diǎn)結(jié)構(gòu) */ struct NODE { int data; struct NODE* next; }; /* 添加元素-壓棧 */ void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node; } /* 添加元素-添加 */ void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; } }
移動(dòng)指針
/* 反轉(zhuǎn)列表 */ void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反轉(zhuǎn)指針 nxt = cur->next; cur->next = pre; // 移動(dòng)指針 pre = cur; cur = nxt; } *head = pre; }
遞歸
/* 反轉(zhuǎn)列表-復(fù)制原表返回反轉(zhuǎn)表 */ NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反轉(zhuǎn)指針 head->next->next = head; head->next = NULL; return new_head; }
打印鏈表
/* 打印隊(duì)列 */ void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; } }
完整代碼如下:
#include <iostream> /* 節(jié)點(diǎn)結(jié)構(gòu) */ struct NODE { int data; struct NODE* next; }; /* 添加元素-壓棧 */ void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node; } /* 添加元素-添加 */ void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; } } /* 反轉(zhuǎn)列表 */ void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反轉(zhuǎn)指針 nxt = cur->next; cur->next = pre; // 移動(dòng)指針 pre = cur; cur = nxt; } *head = pre; } /* 反轉(zhuǎn)列表-復(fù)制原表返回反轉(zhuǎn)表 */ NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反轉(zhuǎn)指針 head->next->next = head; head->next = NULL; return new_head; } /* 打印隊(duì)列 */ void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; } } int main() { struct NODE* n = NULL; add(&n, 1); add(&n, 2); add(&n, 3); n = reverse(n); print(n); return 0; }
希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。