软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

C++数据结构之链表的创建

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 iostreamtypedef 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; istages;++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; istages;++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;}

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!