线性表之链表基本操作的实现2

这里，我们来实现循环链表的基本操作，我们采用单链表转换为循环链表：

1.将单链表转换为循环链表

ChangeLinkListToCkList(LinkList head)    //这里只需要将最后的尾指针指向头结点
{
    LinkList p,p2=head,p1=head;
    while(p2){            //最后这个p就是链表指向尾结点的指针
        p=p2;
        p2=p2->next;
    }
    while(p!=head)        //最后这个head就是指向倒数第二个尾结点的指针
    {
        head=head->next;
    }
    head->next=p1;        //将尾结点指向头结点
}

2.向循环链表添加数据

void AddElemIntoCKList(LinkList head,int index,User user)
{
    LinkList p=(LinkList)malloc(sizeof(LNode));
    p->user=user;
    int i=0;
    for(;i<index-1;i++)              //这里返回的是目标位置的前一个结点
    {
        head=head->next;
    }
    p->next=head->next;              //将目标结点指向当前目标位置上的结点
    head->next=p;                    //将目标位置的前一个结点指向目标结点，至此目标结点完成插入操作
}

3.删除循环链表的某个位置的结点

void DeletElemFromCKList(LinkList head,int index)
{
    int i=0;
    for(;i<index-1;i++)              //这里返回的是目标位置的前一个结点
    {
        head=head->next;
    }
    LinkList p=head->next;
    head->next=head->next->next;
    free(p);
}

4.将两个循环链表合并成一个循环链表

void ContactCKList(LinkList tails_0,LinkList tails_1)      //这里的tails_0和tails_1分别为两个链表的尾指针
{
    LinkList p=tails_1->next->next;                //1.找到第二个循环链表的首元结点
    tails_1->next=tails_0->next;                   //2.第二个链表的尾结点指向第一个链表的头结点
    tails_0->next=p;                               //3.第一个链表的尾结点指向第二个链表的首元结点
}

难点：将两个循环链表合并为一个循环链表

初始状态：

线性表之链表基本操作的实现2

第一步：

线性表之链表基本操作的实现2

第二步：

线性表之链表基本操作的实现2

第三步：

线性表之链表基本操作的实现2

然后美化一下：

线性表之链表基本操作的实现2

至此，两个循环链表合并为一个循环链表就完成了。

最后，附上完整源码一份：

#include<bits/stdc++.h>
using namespace std;
typedef struct
{
    char username[20];
    int id;
}User;
typedef struct LNode
{
    User user;
    struct LNode *next;

}LNode,*LinkList;
//创建单链表
LinkList CreateLinkList(LinkList L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return L;
}
//后插法插入5个数据
void InsertElem_Back(LinkList head)
{
    int i=0;
    LinkList r=head;          //每次加入数据后，r都会指向尾节点
    for(;i<5;i++)
    {
    User user;
    user.id=i;
    strcpy(user.username,"gjw");
    LinkList p=(LinkList)malloc(sizeof(LNode));
    p->user=user;
    p->next=NULL;
    r->next=p;
    r=p;
    }
}
//测试输出链表
void TestList(LinkList head)
{
    while(head->next)
    {
        User user=head->next->user;
        cout<<user.username<<endl;
        head=head->next;
    }
}
//将单链表转化为循环链表
ChangeLinkListToCkList(LinkList head)    //这里只需要将最后的尾指针指向头结点
{
    LinkList p,p2=head,p1=head;
    while(p2){            //最后这个p就是链表指向尾结点的指针
        p=p2;
        p2=p2->next;
    }
    while(p!=head)        //最后这个head就是指向倒数第二个尾结点的指针
    {
        head=head->next;
    }
    head->next=p1;
}
//测试循环链表
void TestCKList(LinkList head)     //这里注意，头结点是没有数据的，所以会输出它的地址值
{
    int num=0;
    while(head&&num<10)
    {
        head=head->next;
        num++;
        cout<<head->user.username<<endl;
    }
}
//循环链表添加数据
void AddElemIntoCKList(LinkList head,int index,User user)
{
    LinkList p=(LinkList)malloc(sizeof(LNode));
    p->user=user;
    int i=0;
    for(;i<index-1;i++)              //这里返回的是目标位置的前一个结点
    {
        head=head->next;
    }
    p->next=head->next;              //将目标结点指向当前目标位置上的结点
    head->next=p;                    //将目标位置的前一个结点指向目标结点，至此目标结点完成插入操作
}
//删除第i个位置的结点
void DeletElemFromCKList(LinkList head,int index)
{
    int i=0;
    for(;i<index-1;i++)              //这里返回的是目标位置的前一个结点
    {
        head=head->next;
    }
    LinkList p=head->next;
    head->next=head->next->next;
    free(p);
}
//获取链表的尾指针
LinkList GetTails(LinkList head,int i)
{
    LinkList p;
    int index=0;
    while(head && index<i)
    {
        p=head==0?p:head;
        head=head->next;
        index++;
    }
    return p;
}
//合并两个循环链表成一个循环链表
void ContactCKList(LinkList tails_0,LinkList tails_1)
{
    LinkList p=tails_1->next->next;                //找到第二个循环链表的首元结点
    tails_1->next=tails_0->next;                   //第二个链表的尾结点指向第一个链表的头结点
    tails_0->next=p;                               //第一个链表的尾结点指向第二个链表的首元结点
}
int main()
{
    LinkList L;
    User user;
    //创建单链表
    LinkList head=CreateLinkList(L);
    //采用后插法插入一段数据
    InsertElem_Back(head);
    //测试输出链表
    //TestList(head);
    //将单链表改为循环链表
    ChangeLinkListToCkList(head);
    //测试循环链表
    //TestCKList(head);
    //循环链表添加数据到第i个位置
    //int i=3;
    //user.id=0;
    //strcpy(user.username,"px");
    //AddElemIntoCKList(head,i,user);
    //删除第i个位置的结点
    //DeletElemFromCKList(head,i);
    //将两个循环链表合并为一个循环链表
    LinkList head1=CreateLinkList(L);       //创建一个新的单链表
    InsertElem_Back(head1);                    //向链表中添加5个数据
    ChangeLinkListToCkList(head1);          //将该链表转化为循环链表
    LinkList tails_0=GetTails(head,5);        //获取第一个链表的尾指针
    LinkList tails_1=GetTails(head1,5);       //获取第二个链表的尾指针
    ContactCKList(tails_0,tails_1);           //合并两个循环链表为一个循环链表
    return 0;
}

线性表之链表基本操作的实现2

相关推荐