一、链表的基本操作

初始化

通常会用头指针来标识一个单链表，头指针为NULL时表示一个空表。但是，为了操作方便，会在单链表的名列前茅个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的名列前茅个元素结点。如下图所示：

头结点和头指针的区分：不管带不带头结点，头指针始终指向单链表的名列前茅个结点，而头结点是带头结点的单链表中的名列前茅个结点，结点内通常不存储信息。

 那么单链表的初始化操作就是申请一个头结点，将指针域置空。

void InitList(LinkList &L){

    L = (LNode *)malloc(sizeof(LinkList));

    L->next = NULL;

}

建立单链表

头插法建立单链表

所谓头插法建立单链表是说将新结点插入到当前链表的表头，即头结点之后。：

算法思想：首先初始化一个单链表，其头结点为空，然后循环插入新结点*s：将s的next指向头结点的下一个结点，然后将头结点的next指向s。

实现代码：

//头插法建立单链表

LinkList HeadInsert(LinkList &L){

    InitList(L); //初始化

    int x;

    cin>>x;

    while(x!=9999){ //输入9999表示结束

        LNode *s = (LNode *)malloc(sizeof(LNode));

        s->data = x;

        s->next = L->next;

        L->next = s;

        cin>>x;

    }

    return L;

}

需要指出的是，头插法建立的单链表中结点的次序和输入数据的顺序不一致，是相反的。若希望两者的顺序是一致的，则可采用尾插法建立单链表。

尾插法建立单链表

所谓尾插法建立单链表，就是将新结点插入到当前链表的表尾。如下图所示：

算法思想：首先初始化一个单链表，然后声明一个尾指针r，让r始终指向当前链表的尾结点，循环向单链表的尾部插入新的结点*s，将尾指针r的next域指向新结点，再修改尾指针r指向新结点，也就是当前链表的尾结点。最后别忘记将尾结点的指针域置空。

 实现代码：

//尾插法建立单链表

LinkList TailInsert(LinkList &L){

    InitList(L);

    LNode *s,*r=L;

    int x;

    cin>>x;

    while(x!=9999){

        s = (LNode *)malloc(sizeof(LNode));

        s->data = x;

        r->next = s;

        r = s;

        cin>>x;

    }

    r->next = NULL;

    return L;

}

遍历单链表

算法思想：声明一个指针p，从头结点指向的名列前茅个结点开始，如果p不为空，那么就输出当前结点的值，并将p指向下一个结点，直到遍历到最后一个结点为止。

实现代码：

//遍历操作

void PrintList(LinkList L){

    LNode *p = L->next;

    while(p){

        cout<data<<” “;

        p = p->next;

    }

    cout<

}

求单链表的长度

算法思想：声明一个指针p，p指向头结点指向的名列前茅个结点，如果p指向的结点不为空，那么长度加一，将p指向下一个结点，直到遍历到最后一个结点为止。

实现代码：

//求单链表的长度

int Length(LinkList L){

    LNode *p = L->next;

    int len = 0;

    while(p){

        len++;

        p = p->next;

    }

    return len;

}

延伸阅读：

二、线性表基本架构

对于一个线性表来说。不管它的具体实现如何，但是它们的方法函数名和实现效果应该一致(即使用方法相同、达成逻辑上效果相同，差别的是运行效率)。线性表的概念与Java的接口/抽象类有那么几分相似。非常知名的就是List的Arraylist和LinkedList，List是一种逻辑上的结构，表示这种结构为线性表，而ArrayList，LinkedList更多的是一种物理结构(数组和链表)。

所以基于面向对象的编程思维，我们可以将线性表写成一个接口，而具体实现的顺序表和链表的类可以实现这个线性表的方法，提高程序的可读性，还有一点比较重要的，记得初学数据结构与算法时候实现的线性表都是固定类型(int),随着知识的进步，我们应当采用泛型来实现更合理。至于接口的具体设计如下：

package LinerList;

public interface ListInterface {   

    void Init(int initsize);//初始化表

    int length();

    boolean isEmpty();//是否为空

    int ElemIndex(T t);//找到编号

    T getElem(int index) throws Exception;//根据index获取数据

    void add(int index,T t) throws Exception;//根据index插入数据

    void delete(int index) throws Exception;

    void add(T t) throws Exception;//尾部插入

    void set(int index,T t) throws Exception;

    String toString();//转成String输出   

}

上一篇

依次插入结点法生成二叉排序树是什么意思?

下一篇

什么是树的特殊类问题?