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;
}
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
