Chinaunix首页 | 论坛 | 博客
  • 博客访问: 765271
  • 博文数量: 370
  • 博客积分: 2334
  • 博客等级: 大尉
  • 技术积分: 3222
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-06 16:56
文章分类

全部博文(370)

文章存档

2013年(2)

2012年(368)

分类:

2012-06-09 12:23:06

原文地址:双链表算法 作者:flychenxu

双链表数据结构:

struct LinkList

{

       int data;

       struct LinkList *pre;

       struct LinkList *next;

};

(1) 后插法构造双链表

struct LinkList *CreateLinkListAfter()

{

       struct LinkList *head, *tail, *newNode;

       head = tail = NULL;

       while (1)

       {

              newNode = new struct LinkList;

              scanf("%d", &newNode->data);

              if (newNode->data < 0)

              {

                     delete newNode;

                     break;

              }

              if (head == NULL)  //空链表

              {

                     head = tail = newNode;

              }

              else

              {

                     tail->next = newNode;

                     newNode->pre = tail;

                     tail = newNode;

              }

       }

       if (head != NULL)

       {

              head->pre = NULL;

       }

       if (tail != NULL)

       {

              tail->next = NULL;

       }

       return head;

}

(2) 遍历双链表

void PrintLinkList(struct LinkList *head)

{

       struct LinkList *p = head;

       while (p != NULL)

       {

              printf("%d ", p->data);

              p = p->next;

       }

       printf("\n");

}

(3) 删除链表

void FreeLinkList(struct LinkList *head)

{

       struct LinkList *p = head;

       while (head)

       {

              p = head;

              head = p->next;

              delete p;

       }

}

(4) 双链表插入

struct LinkList *InsertLinkList(struct LinkList *head, int value)

{

       struct LinkList *newNode = new struct LinkList;

       newNode->data = value;

       if (head == NULL)   //空链表插入后就为头结点

       {

              head = newNode;

              head->next = NULL;

              head->pre = NULL;

              return head;

       }

       else

       {

              struct LinkList *p = head;

              while (newNode->data > p->data && p->next != NULL)

              {

                     p = p->next;

              }

              if (newNode->data <= p->data)  //头结点前插入

              {

                     if (p == head)

                     {

                            head->pre = newNode;

                            newNode->next = head;

                            newNode->pre = NULL;

                            head = newNode;

                     }

                     else     //中间节点插入

                     {

                            newNode->next = p;

                            p->pre->next = newNode;

                            newNode->pre = p->pre;

                            p->pre = newNode;

                     }

              }

              else   //尾节点后插入

              {

                     p->next = newNode;

                     newNode->pre = p;

                     newNode->next = NULL;

              }

       }

       return head;

}

(5) 双链表元素删除

struct LinkList *DelLinkList(struct LinkList *head, int value)

{

       if (head == NULL)

       {

              return head;

       }

       else

       {

              struct LinkList *p = head;

              while (p->data != value && p->next != NULL)

              {

                     p = p->next;

              }

              if (p->data == value)

              {

                     if (p == head)    //删除头结点

                     {

                            head = head->next;

                            head->pre = NULL;

                            delete p;

                     }

                     else if (p->next == NULL)   //删除尾节点

                     {

                            p->pre->next = NULL;

                            delete p;

                     }

                     else    //删除中间节点

                     {

                            p->pre->next = p->next;

                            p->next->pre = p->pre;

                     }

              }

              else   //没有找到要删除的节点

              {

                     printf("there is the element's value is %d\n", value);

              }

              return head;

       }

}

阅读(471) | 评论(0) | 转发(0) |
0

上一篇:常见排序算法

下一篇:单链表算法

给主人留下些什么吧!~~