C++數據結構之鏈表的創建
前言
1.鏈表在C/C++里使用非常頻繁, 因為它非常使用, 可作為天然的可變數組. push到末尾時對前面的鏈表項不影響. 反觀C數組和std::vector, 一個是靜態大小, 一個是增加多了會對之前的元素進行復制改寫(線程非常不安全).
2.通常創建鏈表都是有next這樣的成員變量指向下一個項, 通過定義一個head,last來進行鏈表創建. 參考函數 TestLinkCreateStupid().
說明
1.其實很早就知道另一種創建方式, 但是一直沒總結. 沒見過的童鞋看看以下創建鏈表的方式你用了哪一種. linus說了不會第一種的TestLinkCreateClever()根本不會用指針(看來我真不會用指針). 這種方式在循環里根本不用判斷, 可見效率有多高.
// test_shared.cpp : 定義控制臺應用程序的入口點。//#include "stdafx.h"#include <memory>#include <string>#include <iostream>typedef struct stage_tag { int data_ready; /* Data present */ long data; /* Data to process */ struct stage_tag *next; /* Next stage */} stage_t;// 高效率的鏈表創建方式stage_t* TestLinkCreateClever(int stages){ stage_t *head = NULL,*new_stage = NULL,*tail = NULL; stage_t **link = &head; // 區別在這個指針地址變量上,它起到綁定新的stage的作用. for(int i =0; i<stages;++i) { new_stage = (stage_t*)malloc(sizeof(stage_t)); new_stage->data_ready = 0; new_stage->data = i; *link = new_stage; // 把新的stage賦值給link指向的指針地址 link = &new_stage->next; // 綁定下一個的指針地址 } tail = new_stage; *link = NULL; return head;}// 低效率的鏈表創建方式stage_t* TestLinkCreateStupid(int stages){ stage_t *head = NULL,*new_stage = NULL,*tail = NULL; for(int i =0; i<stages;++i) { new_stage = (stage_t*)malloc(sizeof(stage_t)); new_stage->data_ready = 0; new_stage->data = i; new_stage->next = NULL; if(tail) tail->next = new_stage; else head = new_stage; tail = new_stage; } return head;}int _tmain(int argc, _TCHAR* argv[]){ std::cout << "=== TestLinkCreateClever ===" << std::endl; auto first = TestLinkCreateClever(10); while(first) { std::cout << "data: " << first->data << std::endl; first = first->next; } std::cout << "=== TestLinkCreateStupid ===" << std::endl; auto second = TestLinkCreateStupid(10); while(second) { std::cout << "data: " << second->data << std::endl; second = second->next; } return 0;}
如有疑問請留言或者到本站社區交流討論,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!
新聞熱點
疑難解答