【链表的学习】实现链表的几种方法

【链表的学习】实现链表的几种方法

1.静态链表

const int N = 10000;                   //按需要定义静态链表的空间大小
struct node{                           //单向链表
    int id;                            //这个结点的id
    int data;                          //数据
    int nextid;                        //指向下一个结点的id
}nodes[N];                             //静态分配需要定义在全局

//为链表的next指针赋初值，例如：
    nodes[0].nextid = 1;
    for(int i = 1; i <= n; i++){
        nodes[i].id = i;     //把第i个结点的id就赋值为i
        nodes[i].nextid = i + 1;   //next指针指向下一个结点
    }

//定义为循环链表：尾指向头
    nodes[n].nextid = 1;                 

//遍历链表，沿着nextid访问结点即可

//删除结点。设当前位于位置now，删除这个结点  
    nodes[prev].nextid = nodes[now].nextid;   //跳过结点now，即删除now
    now = nodes[prev].nextid;                 //更新now

2.双向静态链表

const int N = 10000;
struct node{                          //双向链表
    int id;                           //结点编号
    int data;                         //数据
    int preid;                        //前一个结点
    int nextid;                       //后一个结点
}nodes[N];

//为结点的指针赋初值，例如
    nodes[0].nextid = 1;  
    nodes[1].preid  = 0;
    for(int i = 1; i <= n; i++){       //建立链表
        nodes[i].id = i;
        nodes[i].preid  = i-1;          //前结点
        nodes[i].nextid = i+1;          //后结点
    }
//定义为循环链表
    nodes[n].nextid = 1;               //循环链表：尾指向头
    nodes[1].preid = n;                //循环链表：头指向尾

//遍历链表，沿着preid和nextid访问结点即可

//删除结点。设当前位于位置now，删除这个结点
    prev = nodes[now].preid;   
    next = nodes[now].nextid;
    nodes[prev].nextid = nodes[now].nextid;  //删除now
    nodes[next].preid  = nodes[now].preid;   
    now = next;                              //更新now

//插入结点，见后面的习题“自行车停放”

3.上述链表的手写代码已经比较简单了，如果还嫌麻烦，可以使用C++的STL list。 list 是双向链表，它的内存空间可以是不连续的，通过指针访问结点数据，它能高效率地删除和插入。

//定义一个list
    listnode;
//为链表赋值，例如定义一个包括n个结点的链表
    for(int i=1;i<=n;i++)  
        node.push_back(i); 
//遍历链表，用it遍历链表，例如从头遍历到尾：
    list::iterator it = node.begin();
    while(node.size()>1){           //list的大小由STL自己管理
         it++;
         if(it == node.end())   //循环链表，end()是list末端下一位置
                it = node.begin();                                              
    }
//删除一个结点
    list::iterator next = ++it;
    if(next==node.end())  next=node.begin();  //循环链表
    node.erase(--it);            //删除这个结点，node.size()自动减1
    it = next;                   //更新it

//插入结点，见后面的习题“自行车停放”