[C语言]

双向链表操作

[复制链接]
822|1
手机看帖
扫描二维码
随时随地手机跟帖
一路向北lm|  楼主 | 2018-10-21 18:49 | 显示全部楼层 |阅读模式
/*******************************双链表**************************/
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define  FALSE    0
#define  TRUE     1
// 双链表声明
typedef struct NODE
{
   struct  NODE  *fwd;
   struct  NODE  *bwd;
   int     value;
}Node;

// 双链表的创建,返回头指针
Node *CreatList(int n)
{
    Node *head,*pNode,*sNode;
    int i;
    head=(Node *)malloc(sizeof(Node));
        head->bwd=NULL;
        head->fwd=NULL;
    pNode=head;
    for(i=1;i<=n;i++)
    {
        sNode=(Node *)malloc(sizeof(Node));
                sNode->value=i;
                sNode->bwd = NULL;
                sNode->fwd = NULL;

                pNode->fwd=sNode;
                sNode->bwd=pNode;
        pNode=sNode;
    }
    return(head);
}

// 打印双链表数据(传递双向链表头head)
void print_link(Node *head)
{
        Node *pNode=head->fwd;
    while(pNode!=NULL)
    {
                printf("%d\n",pNode->value);
                pNode=pNode->fwd;
    }
}

/*双链表的插入
** 把一个值插入到双链表,rootp是一个指向根节点的指针
** value 是欲插入的新值
** 返回值:如果欲插入的值已存在链表中,函数返回0;
** 如果内存不足导致无法插入,函数返回-1;,如果插入成功,函数返回1;
*/

int dll_insert(Node *rootp,int value)
{
    Node *thist;
        Node *next;
        Node *newnode;
        /*查看value是否存在链表中,有就返回,
        ** 否则为新值创建一个新的节点
        **  thist 指向新节点之前那个节点
        **  next  指向新节点之后那个节点
        */
        for(thist = rootp;(next = thist->fwd) != NULL;thist = next)
        {
                if (next->value == value)
                        return 0;
                if (next->value > value)
                        break;
        }
        newnode = (Node *)malloc(sizeof(Node));
        if(newnode == NULL)
                return -1;
        newnode->value = value;

        /*
        ** 把新值添加到链表中
        */

/*
**最初版,分析了四种不同情况。
*/
/*
        if(next != NULL)
        {
               // 情况1或者2:并非位于链表尾部
                   if(thist!=rootp)         //情况1:并非位于链表的起始位置
                   {
                           newnode->fwd = next;
                           thist->fwd = newnode;
                           newnode->bwd = thist;
                           next->bwd = newnode;
                   }
                   else                     //情况2:位于链表的起始位置
                   {
                           newnode->fwd = next;
                           rootp->fwd = newnode;
                           newnode->bwd = NULL;
                           next->bwd = newnode;
                   }
        }
        else    //情况3或者4:位于链表尾部
        {
             if(thist != rootp)   //情况3:并非位于链表的起始位置
                 {
                         newnode->fwd = NULL;
                         thist->fwd = newnode;
                         newnode->bwd = thist;
                         rootp->bwd = newnode;
                 }
                 else                 //情况4:位于链表的起始位置
                 {
                         newnode->fwd = NULL;
                         rootp->fwd = newnode;
                         newnode->bwd = NULL;
                         rootp->bwd = newnode;
                 }
        }
*/

/*
**简化版,对比上面可读性不强,运行速度并不比前面的快。
*/
         newnode->fwd = next;
     thist->fwd = newnode;
        if(thist!=rootp)         
            newnode->bwd = thist;
        else                     
                newnode->bwd = NULL;       
        if(next != NULL)   
            next->bwd = newnode;
        else   
            rootp->bwd = newnode;

  return 1;  
}

/*双链表的删除
** 把一个值插入到双链表,rootp是一个指向根节点的指针
** del 是指向欲移除节点的指针
** 返回值:
** 如果链表不包含移除的节点,函数就返回假,否则返回真。
*/
int dll_remove(Node *rootp, Node *del)
{
    register  Node  *thist;
        assert( del != NULL);
        for(thist=rootp->fwd; thist != NULL; thist = thist->fwd)
            if(thist == del)
                      break;
        if(thist == del)
        {
                /*
        ** Update fwd pointer of the previous node.
        */
        if( thist->bwd == NULL )
                        rootp->fwd = thist->fwd;
        else
           thist->bwd->fwd = thist->fwd;
         /*
         ** Update bwd pointer of the next node.
         */
        if( thist->fwd == NULL )
            rootp->bwd = thist->bwd;
       else
           thist->fwd->bwd = thist->bwd;
        free( thist );
        return TRUE;
        }
        else
                return FALSE;
       
}


相关帖子

airwill| | 2018-10-23 07:14 | 显示全部楼层
双向链表作为一种数据结构, 确实很常用. 比如 UCOS 也用这个来管理任务.
不过让单片机处理这个还是有点麻烦, 特别是8位机要尽量避免

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

256

主题

3639

帖子

72

粉丝