数据结构03 链表及其操作

单链表及其特点

链表的种类较多，这里我们主要讲解最常见的带头结点的单链表。

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

如图所示，链表中每个数据的存储都由以下两部分组成：

1.数据元素本身，其所在的区域称为数据域；

2.指向直接后继元素的指针，所在的区域称为指针域；

一个完整的链表需要由以下几部分构成

1.头结点：头节点是一个不存储任何数据的结点，是为了方便找到链表位置。

2.首元结点：它是链表中称第一个存有数据的节点为首元结点，称呼没有实际意义。

3.其他结点：链表中其他的结点。

一个存储数据{1，2，3}的完整链表如下图所示：

注意：链表中有头结点时，头指针指向头结点；反之，若链表中没有头结点，则头指针指向首元结点。

简单的来说，链表就像一环扣一环的链子一样，当你想插入删除元素的时候，只需要找到你要插入或者删除的位置，然后解开该位置两边的环，然后将新的环连接上即可。

由于链表的特殊结构，决定了它拥有一个数组所没有的优势，那就是进行插入删除操作的时候，不需要移动元素。但是缺点就是查找元素需要从头结点开始一个一个往后找。

创建单链表

单链表在创建的时候需要先声明结点，方可创建链表，即向链表中插入元素。插入元素时，又可分为头插法和尾插法。头插法和尾插法的区别后面会通过结果展示出来。

头插法：在头结点之后插入数据，其特点是读入的数据顺序与线性表的逻辑顺序正好相反，可用来实现倒序输出一个元素序列。

尾插法：将每次插入的新结点放在链表的尾部。

定义节点存储结构

struct Node
{
    int data;    //保存节点中存储的数据
    Node *next; //指向下一结点

};

尾插法插入元素

void Wcreate(Node *l,int n) //尾插法向链表中插入n个数字
{
    Node *p,*r; //p用来指向新生成的结点。r始终指向l的终端结点。
    r=l;     //r指向了头节点，此时的头节点也是终端节点
    int k;
    for(int i=0;i<n;i++) {
        cin>>k;
        p=new Node; //为结点分配空间
        p->data=k;  //将数值存入新结点
        r->next=p;   //接受新的结点
        r=p;  //r指向终端结点
    }
    r->next=NULL; //l的终端结点指针域为NULL，l建立完成
}

遍历并显示链表内容

void show(Node *l)
{
    Node *p;
    p=l->next;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

头插法插入元素

void Tcreate(Node *l,int n) //头插法向链表中插入n个数字
{
    Node *p; //p用来指向新生成的结点
    l->next=NULL;
    int k;
    for(int i=0;i<n;i++) {
        cin>>k;
        p=new Node; //为结点分配空间
        p->data=k;  //将数值存入新结点
        p->next=l->next;  //将l指向的地址赋值给p;
        l->next=p; //头指针的指针域next指向p结点，使得p成为开始结点。
    }
}

向链表中插入元素

void insert(Node *l,int k,int e)//在第k个位置后插入元素e;
{
    Node *p,*r;
    r=l;
    if(r->next==NULL) cout<<"链表为空";
    for(int i=0;i<k;i++) //找到第k个位置之前的那个位置
        r=r->next;
    p=new Node; //为新结点申请空间
    p->data=e;
    p->next=r->next;
    r->next=p;
}

删除元素

void Delete(Node *l,int x) //删除第一个值为x的数。
{
    Node *r,*pre;
    pre=l; //记录前驱结点，防止断链
    r=l->next;
    while(r->data!=x)
    {
     pre=r;  //记录该结点前一个结点
     r=r->next;
     }
    pre->next=r->next; //将其前驱next指向其后继，实现删除
}

查找元素

//查找值为X的数是否存在，在则输出第一次出现的位置。
void Search(Node *l,int x) {
    int k=1;  //记录位置
    Node *p;
    p=l->next;
    while(p->data!=x&&p->next!=NULL) {
        p=p->next;
        k++;
    }
    if(p->data!=x) cout<<"未找到"<<endl;
    else cout<<"是第"<<k<<"个数字"<<endl;
}