现在的位置: 首页 > 综合 > 正文

数据结构 – 单链表

2013年05月27日 ⁄ 综合 ⁄ 共 1422字 ⁄ 字号 评论关闭

1. 单链表删除节点

  • 如果删除的是头节点,则把head指针指向头节点的下一个节点。同时free p1,如下图所示:

    QQ截图20111106194959

     

 

  • 如果删除的是中间节点,则用p2的next指向p1的next同时,free p1 ,如下图所示:
    QQ截图20111106195254
  • 如果删除的是尾节点,如果为节点为P1,其前一节点为P2,则释放P1,将P2的next设为NULL
  • 代码实现
    //单链表删除节点
    node *remove(node *head ,int num)
    {
        node *p1,*p2;
        p1=head;
        while(num!=p1->data && p1->next!=NULL)//查找data为num的节点
        {
            p2=p1;
            p1=p1->next;
        }
        if(num==p1->data) //如果存在num节点,则删除
        {
            if(p1==head)
            {
                head=p1->next;
                free(p1);
            }
            else
            {
                p2->next=p1->next;
            }
        }
        else
        {
            printf("\n%d could not been found",num);
        }
        return (head);
    }
    

      

2. 单链表的插入

  • 如果插入在头结点以前,则p0的next指向p1,头节点指向p0,如下图所示:
    QQ截图20111106202019
  • 如果插入中间节点,如下图所示:
    QQ截图20111106202318
  • 如果插入尾节点,则先让p1的next指向p0,再让p0指向空,如下图所示:
    QQ截图20111106202635
  • 代码实现
    //单链表插入节点
    node *insert(node *head,int num)
    {
        node *p0,*p1,*p2;
        p1=head;
        p0=(node *)malloc(sizeof(node));
        p0->data=num;
        while(p0->data > p1->data && p1->next!=NULL)
        {
            p2==p1;
            p1=p1->next;
        }
        if(p0->data<=p1->data)
        {
            if(head==p1)
            {
                p0->next=p1;
                head=p0;
            }
            else
            {
                p2->next=p0;
                p0->next=p1;
            }
        }
        else
        {
            p1->next=p0;
            p0->next=NULL;
        }
        return (head);
    }
    

      

3. 单链表的排序

  • 代码实现

    //单链表排序
    node *sort(node *head)
    {
        node *p,*p2,*p3;
        int n;
        int temp;
        n=length(head);
        if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点
            return head;
        p=head;
        for(int j=1;j<n;++j)
        {
            p=head;
            for(int i=0;i<n-j;++i)
            {
                if(p->data > p->next->data)
                {
                    temp=p->data;
                    p->data=p->next->data;
                    p->next->data=temp;
                }
                p=p->next;
            }
        }
        return (head);
    }
    

      

4. 单链表的逆置

  • 代码实现

    //单链表逆置
    node *reverse(node *head)
    {
        node *p1,*p2,*p3;
        if(head==NULL || head->next==NULL)
            return head;
        p1=head;
        p2=p1->next;
        while(p2)
        {
            p3=p2->next;
            p2->next=p1;
            p1=p2;
            p2=p3;
        }
        head->next=NULL;
        head=p1;
        return head;
    }
    

     

 

引自:http://www.cnblogs.com/iuices/archive/2011/11/06/2238606.html

抱歉!评论已关闭.