C语言线性结构链式结构链表逆置及重复节点删除-创新互联

#include#includetypedef int datatype;
typedef struct node *ptrNode;
typedef struct node
{
    int data;
    ptrNode next;
}lnode, *linkList;

ptrNode create_node(datatype d);
ptrNode create_node();
void link_list_front(ptrNode l,datatype d);
void link_list_rear(ptrNode l,datatype d);
void print(ptrNode l);

linkList init_node()
{
    linkList ptr = (linkList)malloc(sizeof(lnode));
    ptr->next=NULL;
    return ptr;
}

//链表逆置
void reverse_list(linkList head)
{
    linkList p = head->next;
    linkList q;
    head->next = NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next = head->next;
        head->next = q;
    }
    return ;
}

//删除重复元素
void delect_repetition(linkList head)
{
    if(head->next==NULL)//空链表直接返回
        return ;

    linkList current = head->next;//当前节点
    linkList check   ;//审视节点
    linkList pre;//审视节点前驱

    int is;
    while(current->next)
    {
        check=current->next;
        pre = current;
        while(check)
        {
            is=0;
            if(check->data == current->data)//删除节点
            {
                pre->next = check->next;//前两步为删除节点，第三步是重新组织判断点
                free(check);
                check = pre;
                is=1;
            }
            check = check->next;
            if(!is)
            pre = pre->next;//注意前驱节点也要先下滑
        }
        if(current->next)//在上述过程后current有可能成为尾节点,所以这里要判断一下其next是否存在
        current = current->next;
    }

}

int main()
{
    printf("\n测试1\n");
    linkList head = create_node();
    link_list_rear(head,10);
    link_list_rear(head,15);
    link_list_rear(head,18);
    link_list_rear(head,15);
    link_list_rear(head,10);
    link_list_rear(head,6);
    link_list_rear(head,6);
    printf("原链表为：\n");
    print(head);

    reverse_list(head);
    printf("逆置后链表为：\n");
    print(head);

    delect_repetition(head);
    printf("逆置链表删除重复节点为：\n");
    print(head);

    printf("\n测试2\n");
    linkList head2 = create_node();
    printf("原链表为：\n");
    print(head2);
    reverse_list(head2);
    printf("逆置后链表为：\n");
    print(head2);
    delect_repetition(head2);
    printf("逆置链表删除重复节点为：\n");
    print(head2);

    printf("\n测试4\n");
    linkList head4 = create_node();
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    link_list_rear(head4,6);
    printf("原链表为：\n");
    print(head4);
    reverse_list(head4);
    printf("逆置后链表为：\n");
    print(head4);
    delect_repetition(head4);
    printf("逆置链表删除重复节点为：\n");
    print(head4);

    printf("\n测试5\n");
    linkList head5 = create_node();
    link_list_rear(head5,1);
    link_list_rear(head5,2);
    link_list_rear(head5,3);
    link_list_rear(head5,4);
    link_list_rear(head5,5);
    link_list_rear(head5,6);
    link_list_rear(head5,7);
    printf("原链表为：\n");
    print(head5);
    reverse_list(head5);
    printf("逆置后链表为：\n");
    print(head5);
    delect_repetition(head5);
    printf("逆置链表删除重复节点为：\n");
    print(head5);

    return 0;
}

//下面五个函数是前面博客写的 http://t.csdn.cn/wX7Ce
ptrNode create_node(datatype d)
{
    ptrNode ptn = (ptrNode)malloc( sizeof(lnode) );
    ptn->next = NULL;
    ptn->data = d;

    return ptn;
}
ptrNode create_node()
{
    ptrNode ptn = (ptrNode)malloc( sizeof(lnode) );
    ptn->next = NULL;

    return ptn;
}
//带头结点 头插
void link_list_front(ptrNode l,datatype d)
{
    ptrNode ptn = create_node(d);
    ptrNode temp = l->next;
    l->next   = ptn ;
    ptn->next = temp;
}

//尾插
void link_list_rear(ptrNode l,datatype d)
{
    ptrNode ptn = create_node(d);
    while(l->next)l=l->next;
    l->next = ptn;
}

void print(ptrNode l)
{
    l=l->next;
    if(l==NULL)
    {
        printf("NULL\n");
        return ;
    }
    while(l)
    {
        printf("%d ",l->data);
        l=l->next;
    }
    printf("\n");
}

main()函数后面的函数是之前的博客里写的，一些链表的基础操作，想再看一下的同学可以点这个链接：http://t.csdn.cn/wX7Ce ，同样因为有函数create_node（）重载所以自己想试着运行的话可以构建C++的项目，或者把同名函数改一下就行了，除了这点都是C的语法。

链表逆置其实就是链表头插的变形，要注意的是在p获取head->next后要把head->next改为NULL做初始化；在向下遍历p时要先把p指向p->next再修改q->next，否则就会失去原链表的节点链接。

//链表逆置
void reverse_list(linkList head)
{
linkList p = head->next;
linkList q;
head->next = NULL;
while(p)
{
q=p;
p=p->next;
q->next = head->next;
head->next = q;
}
return ;
}

删除重复元素，一是要注意空链表不用处理，直接返回，这一步必不可少，因为下面的while判断直接就是current->next ，没有这一步会出错；二是在向下移动check时pre要同步移动，但是当审视时删除了某节点（下面代码第19行）时，check要继续审视pre的下一个节点，这时pre是不用移动的，所以27行有一个判断；三是在执行了删除步骤后current有可能成为尾节点(及current->next==NULL，若这里将这个值赋值给current，则12行while判断就会出错),所以30要判断一下current->next是否存在。

//删除重复元素
void delect_repetition(linkList head)
{
    if(head->next==NULL)//空链表直接返回
        return ;

    linkList current = head->next;//当前节点
    linkList check   ;//审视节点
    linkList pre;//审视节点前驱

    int is;
    while(current->next)
    {
        check=current->next;
        pre = current;
        while(check)
        {
            is=0;
            if(check->data == current->data)//删除节点
            {
                pre->next = check->next;//前两步为删除节点，第三步是重新组织判断点
                free(check);
                check = pre;
                is=1;
            }
            check = check->next;
            if(!is)
            pre = pre->next;//注意前驱节点也要先下滑
        }
        if(current->next)//在上述过程后current有可能成为尾节点,所以这里要判断一下其next是否存在
        current = current->next;
    }

}

main函数里是五个测试点，测试数据都不同，下面是运行结果：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧