[易学数据结构]链表的构建C++

  初学数据结构如果直接接触链表容易摸不着头脑，什么是链表？如何使用链表？链表的作用是啥？…但是，如果你有C或C++的基础，我们可以从一个熟悉的数据结构——数组入手。

  数组是一种可以顺序存储数据、对数据进行操作的数据结构。而链表和数组的功能是相通的，不同的是链表用指针来实现。众所周知，指针的使用相对繁杂，如果操作不当还容易造成内存隐患。那么为什么还要舍近取远使用链表呢？

  原因在于数组的内存空间是不可扩展的，而链表可以在使用时按照需要进行内存增删。
  
  数组在声明的时候就指定了内存的大小，这在后续的操作中是无法改变的，如果空间开辟的过多会造成内存浪费，如果开辟的不够则造成数据丢失，所以使用起来不是很灵活。而链表则很好地解决了这个问题，链表由一个个链接的结点组成，可以在后续的操作中通过结点的增加、删除，实现链表的扩展和缩短。这样一来，使用链表就可以灵活地解决内存增删的问题了。

  链表由结点与结点连接组成，前一个结点指向后一个结点。而结点由指针结构体实现，结构体中内嵌着同类型的指针结构体，用来指向下一结点，从而实现结点的连接。

  每个结点由一个数据域和一个指针域组成，数据域存放该结点数据，指针域则存放下一结点地址。

  如上图所示，通过结点内指针的指向，建立起结点间的联系，从而实现链表的构建。

  首先声明一个结构体，作为结点使用。

struct link
{
    int ID;//数据域
    link *next;//指针域
};

  然后写一个构建函数，构建方式通过while循环实现。

link *create(int n)//n为链表的结点数量
{
    int x=n;
    link *p=NULL;//创建一个头指针
    link *temp=new link;//开辟一个临时结点容器，作为结点操作指针使用
    temp->ID=1;
    temp->next=NULL;
    p=temp;//第一个实现的结点赋值给p，作为头指针，p不参与while循环的操作
    while(--n)
    {
        link *a=new PCB;//开辟新增结点容器
        a->ID=x-n+1;//数据域初始化
        a->next=NULL;//指针域初始化
        temp->next=a;//新增结点连接到当前结点上
        temp=temp->next;//更新当前结点位置
    }
    return p;//返回头指针
}

  链表访问函数，链表的访问只需要获得头指针即可以访问整个链表。

void display(link *head)
{
    link *temp=head;//接收头指针
    while(temp)//遍历访问链表所有结点
    {
        cout << "ID: " <ID << endl << endl;
        temp=temp->next;
    }
}

  整体代码>>>>>>

#include 
#include 
using namespace std;

struct link
{
    int ID;//数据域
    link *next;//指针域
};

link *create(int n)//n为链表的结点数量
{
    int x=n;
    link *p=NULL;//创建一个头指针
    link *temp=new link;//开辟一个临时结点容器，作为结点操作指针使用
    temp->ID=1;
    temp->next=NULL;
    p=temp;//第一个实现的结点赋值给p，作为头指针，p不参与while循环的操作
    while(--n)
    {
        link *a=new PCB;//开辟新增结点容器
        a->ID=x-n+1;//数据域初始化
        a->next=NULL;//指针域初始化
        temp->next=a;//新增结点连接到当前结点上
        temp=temp->next;//更新当前结点位置
    }
    return p;//返回头指针
}

void display(link *head)
{
    link *temp=head;//接收头指针
    while(temp)//遍历访问链表所有结点
    {
        cout << "ID: " << temp->ID << endl << endl;
        temp=temp->next;
    }
}

int main()
{
    int n;
    cout << "init>>>>>>>" << endl << endl; 
    cout << "input node number: " ;
    cin >> n;
    link *p=create(n);
    cout << endl << "init done<<<<<<<" << endl << endl;
    cout << "catch informations:" << endl << "------------------------------" << endl << endl;
    display(p);

	return 0;
}

1、理解链表与数组的区别，及使用链表的根本原因；
2、理解链表的构建过程；
3、清楚结点间连接的实现；
4、清楚如何使用头指针访问链表。