注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Aspirer's blog

停止维护,新博客地址:http://aspirer.wang/

 
 
 

日志

 
 

双向链表  

2009-08-13 19:55:49|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

双向链表 - aspirer - Aspirers blog

#include <iostream>
#include <stddef.h>
#include <iomanip>

using namespace std;

typedef struct node
{
 int data;
 struct node *prev;
 struct node *next;
}Node;

Node *creatList()
{
 Node *head = NULL;
 Node *curr, *tmp;
 int d;
 cout << "input data." << endl;
 cin >> d;
 fflush(stdin);
 while (d)
 {
  tmp = (Node *)malloc(sizeof Node);
  if (NULL == tmp)
  {
   cerr << "memory allocation error." << endl;
   exit(1);
  }
  tmp->data = d;

  if (head == NULL)
  {
   head = tmp;
   head->prev = NULL;
   curr = head;
  }
  else
  {
   curr->next = tmp;
   tmp->prev = curr;
   curr = curr->next;
  }

  cout << "input data." << endl;
  cin >> d;
  fflush(stdin);
 }
 curr->next = NULL;

 return head;
}

void printList(Node *head)
{
 cout << "double list is :" << endl;
 if (head == NULL)
 {
  cout << "NULL" << endl;
 }
 while (head != NULL)
 {
  cout << head->data;
  head = head->next;
  if (head != NULL)
  {
   cout << " <--> ";
  }
  else
  {
   cout << endl;
  }
 } 
}

void freeList(Node *head)
{
 cout << setiosflags(ios_base::left);
 Node *tmp;
 while (head != NULL)
 {
  tmp = head;
  head = head->next;
  cout << setw(5) << tmp->data << " has been released." << endl;
  free(tmp);
 }
 cout << resetiosflags(ios_base::right);
}

Node *removeList(Node *head, int d)
{
 //Node *tmp;
 Node *ret = head;
 cout << setiosflags(ios_base::left);
 while (head != NULL && head->data != d)
 {
  head = head->next;
 }
 if (head == NULL)
 {
  cout << "can not find the data you entered." << endl;
 }
 else if (head == ret)
 {
  //tmp = head;
  ret = head->next;
  ret->prev = NULL;
  cout << setw(5) << head->data << " was removed." << endl;
  //ret = head;
  free(head);
 }
 else if (NULL == head->next)
 {
  //tmp = head;
  head->prev->next = head->next;
  //head->next->prev = head->prev;
  cout << setw(5) << head->data << " was removed." << endl;
  free(head);
 }
 else
 {
  head->prev->next = head->next;
  head->next->prev = head->prev;
  cout << setw(5) << head->data << " was removed." << endl;
  free(head);
 }
 cout << resetiosflags(ios_base::right);
 return ret;
}

Node *sortList(Node *head)
{
 Node *p1 = head;
 Node *p2 = head;
 Node *tmp;
 int d;
 while (p1 != NULL)
 {
  tmp = p1;
  p2 = p1->next;
  while (p2 != NULL)
  {
   if (tmp->data > p2->data)
   {
    tmp = p2;
   }
   p2 = p2->next;
  }
  if (tmp != p1)
  {
   d = tmp->data;
   tmp->data = p1->data;
   p1->data = d;
  }
  p1 = p1->next;
 }
 return head;
}

Node *insertList(Node *head, int d)
{
 Node *ret = head;
 Node *tmp = (Node *)malloc(sizeof(Node));
 if (NULL == tmp)
 {
  cerr << "memory allocation error." << endl;
  exit(1);
 }
 tmp->data = d;

 while (head->next && head->data < d)
 {
  head = head->next;
 }
 if (head == ret)
 {
  tmp->next = head;
  head->prev = tmp;
  tmp->prev = NULL;
  ret = tmp;
 }
 else if (head->next == NULL)
 {
  if (head->data > d)
  {
   tmp->prev = head->prev;
   tmp->prev->next = tmp;
   tmp->next = head;
   head->prev = tmp;
  }
  else
  {
   head->next = tmp;
   tmp->prev = head;
   tmp->next = NULL;
  }
 }
 else
 {
  tmp->prev = head->prev;
  tmp->prev->next = tmp;
  tmp->next = head;
  head->prev = tmp;
 }
 return ret;
}

int main()
{
 Node *head = creatList();
 sortList(head);
 printList(head);
 head = removeList(head, 1);
 head = removeList(head, 5);
 head = removeList(head, 3);
 head = insertList(head, 1);
 head = insertList(head, 3);
 head = insertList(head, 5);
 printList(head);
 freeList(head);
 return 0;
}

  评论这张
 
阅读(358)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018