Chinaunix首页 | 论坛 | 博客
  • 博客访问: 232100
  • 博文数量: 77
  • 博客积分: 80
  • 博客等级: 民兵
  • 技术积分: 420
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-06 17:15
文章分类
文章存档

2013年(4)

2012年(73)

分类:

2012-06-05 09:02:41

原文地址:双链表 作者:迷墙人

#include
#include
#include

struct single_link
{
 int data;
 struct single_link *next;
 struct single_link *prev; 
};

int main(void)
{
 struct single_link *head=NULL,*tail=NULL,*tmp=NULL,*i_d_tmp=NULL;
 int i=0,j=0;
 for(i=0;i<5;i++)
 {
  tmp=(struct single_link *)malloc(sizeof(struct single_link));
  tmp->data=i+1;
  tmp->next =NULL;
  tmp->prev=NULL;  
  if(head ==NULL)
   head = tmp;
  else
  { 
   tail->next =tmp;
   tmp->prev=tail;
  }
  tail=tmp;
 }

 for(tmp=head;tmp;tmp=tmp->next)
  printf("init data = %d\n",tmp->data);

 printf("\n\n");

 for(tmp=tail;tmp;tmp=tmp->prev)
  printf("init data = %d\n",tmp->data); 

 i_d_tmp=(struct single_link *)malloc(sizeof(struct single_link));
 i_d_tmp->data=6;
 i_d_tmp->next =NULL;
 i_d_tmp->prev=NULL;
 
 for(tmp=head;tmp;tmp=tmp->next)
 {
  if(tmp->data>3&&tmp->data<5)
  {
   i_d_tmp->next=tmp;
   i_d_tmp->prev = tmp->prev;
   tmp->prev->next=i_d_tmp;
   tmp->prev=  i_d_tmp;
   break;
  }
 }
 printf("\n\n");

 for(tmp=head;tmp;tmp=tmp->next)
  printf("after add data=%d\n",tmp->data);
 printf("\n\n");
 for(tmp=tail;tmp;tmp=tmp->prev)
  printf("after add data=%d\n",tmp->data); 

 for(tmp=head;tmp;tmp=tmp->next)
 {
  if(tmp->data==4)
  {
   tmp->prev->next=tmp->next;
   tmp->next->prev=tmp->prev;
   free(tmp);
   break;
  }
 }
 printf("\n\n");
 for(tmp=head;tmp;tmp=tmp->next)
  printf("after delect data=%d\n",tmp->data);

 tmp=head;
 tail->next = head;
 head->prev =tail;
 i=0;
 for(tmp=head;tmp;tmp=tmp->next)
 { 

  if(tmp == head)
  {
   i++;  
   if(i>=5)
    break;
   printf("\n\n");
  }
  printf("circle link data=%d\n",tmp->data); 
 }
}
/*linux 2.6下gcc duble.c,生成a.out,执行a.out*/

第一步,创建一个链表节点,同时让链表节点的前后指针指向空指针,同时让头尾指针指向这个节点,注意,是指向这个节点,而不是这个节点的上下指针。

第二步,新建一个链表节点,此时,让第一步的尾指针的next指针指向这个新节点,同时让这个新节点的prev指针指向tail节点,这样就形成了两个节点的链表了,形成链表之后,要让tail指针指向刚建的新节点,使得这个节点称为新的尾节点

第三步,循环执行第二步,就可以形成一个循环次数的双向链表。

第四步,要添加一个链表节点到已经形成的链表中,就要先找到到插入的位置(比如节点4),然后执行下面的步骤

A. 让要插入的新节点的next指针指向要插入的位置的节点(此时就是节点4)

B. 让要新插入的新节点的prev指针指向要插入的位置的节点的上一个节点(此时就是节点3)(注意,A,B两步要的要插入的新节点的next/prev指针所指的都是链表中的节点,而不是节点的next/prev指针)

C. 完成了前面两步之后,就要断开原来的链接了,而把新节点连到链表中了,首先,把要插入的链表节点的前一个节点的next指针指向要插入的新节点。

D.再把要插入的节点的prev指针指向新插入的节点,从而形成了新的链表。

第五步,要删除链表中的一个节点,首先要找到要删除的节点,然后

E. 把要删除的节点的上一个节点的next指针,指向要删除的节点的next

F. 把要删除的节点的下一个节点的prev指针,指向要删除的节点的上一个节点

第六步,要实现循环链表,则需要把尾节点的next指针指向头结点,同时把头结点的prev指针指向尾节点。

阅读(868) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~