c++ 链表_c++链表

链表每一个节点都是由数据域和指针域构成的，每一个指针域指向下一个节点，每个节点的数据域存储相应的数据，

两点除外

1）头节点，一般头节点不存储任何数据，但也可以用来存储表长等信息

2）最后一个节点的指针域指向NULL，即空，表示链表结束

特点：

1. 访问单链表中任何一个元素都必须通过头结点层层往下遍历，因此头节点是链表中最重要的节点，没有头节点就无法访问整个链表。这也是链表和顺序表最大的不同。

2. 链表则可以动态改变长度，加之指针的方式使得其遍历速度极为高效，其灵活性和可靠性使得链表成为线性表的主要实现方式，也是栈和队列等重要数据结构类型的基础。

备注： 顺序表是数组实现，访问节点以及返回表长都很容易实现，但是顺序表没有动态分配空间的功能，只能一开始初始化一个较大的空间以便以后利用，一旦填满，则顺序表不能再插入元素。

1.单链表

一个完整的单链表如下图:

单链表的数据元素插入原理：

 若要在第i个位置上插入数据，则需要遍历单链表到第i-1个位置，然后利用malloc()函数向系统请求空间开辟新节点T

        1.先使得T的指针域 指向 第i-1个数据的指针域指向的位置(即第i个元素)；

        2.再让第i-1个数据的指针域 指向 T；

        3.以上两步千万不能颠倒顺序，否则将使得整个链表丢失i位置后的所有数据元素；

                    

单链表的数据元素删除原理：

 若要删除第i个位置上的数据，也需遍历到第i-1个位置，然后利用malloc()函数向系统请求开辟新节点P

        1.P的指针域 指向 第i-1的指针域指向的位置(即第i个元素);

        2.第i-1个元素指针域 指向 第i个元素的指针域指向的位置(即第i+1个元素);

        3.释放P节点占用的空间(即删除了第i个节点);

还有一些其他的操作，比如获得某个位置上的节点，返回单链表长度，清空/销毁链表，遍历整个链表，都是简单的方法，理解了指针就不难写，原理在此不提，关于单链表的代码，就在这里放出一段简单的实例：

#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
 
typedef struct Node
{
    int data;
    struct Node *next;
}*LinkedList,LNode;
 
void CreatLinkedList(LinkedList &L,int n)   //尾插法创建单链表;
{
    L = (LinkedList)malloc(sizeof(LNode));  //初始化;
    L->next = NULL;
    L->data = 0;
    LinkedList Tail = L;    //尾指针;
    cout<<"Enter "<<n<<" number(s)"<<endl;
    for(int i = 0 ; i < n; i++)
    {
        LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
        cin>>Temp->data;
        Tail->next = Temp;
        Tail = Temp;
        Temp = NULL;
        L->data++;  //计数;
    }
    Tail->next = NULL;
}
 
bool GetElem(int &e,int i,LinkedList L) //获取结点;
{
    while(L != NULL && i > 0)
    {
        i--;
        L = L->next;
    }
    if(i == 0 && L != NULL) //i=1时也有可能同时满足退出while的条件;
    {
        e = L->data;
        return true;
    }
    else return false;
}
 
bool InsertElem(int e,int i,LinkedList L)   //插入结点;
{
    if(i > L->data+1 || i < 1)    return false;
    else
    {
        L->data++;
        while(i > 1)
        {
            i--;
            L = L -> next;
        }
        LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
        Temp->data = e;
        Temp->next = L->next;
        L->next = Temp;
        Temp = NULL;
        return true;
    }
}
 
bool DeleteElem(int i,LinkedList L) //删除结点;
{
    if