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

Aspirer's blog

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

 
 
 

日志

 
 

按升序合并两个链表  

2009-07-13 12:50:10|  分类: 学习心得 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

按升序合并两个链表 - aspirer - Aspirers blog

按升序合并两个链表 - aspirer - Aspirers blog

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

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

Node *uniteList(Node *first, Node *second)
{
 Node *head = NULL;
 Node *curr = NULL;
 if (NULL == first || NULL == second)  //很重要,否则一个为空则出错!
 {
  return (first == NULL ? second : first);
 }

 if (first->data < second->data)
 {
  head = first;
  first = first->next;
 }
 else
 {
  head = second;
  second = second->next;
 }

 curr = head;

 while (first && second)
 {
  if (first->data < second->data)
  {
   curr->next = first;
   first = first->next;
   curr = curr->next;
  }
  else
  {
   curr->next = second;
   second = second->next;
   curr = curr->next;
  }
 }

 if (first)
 {
  curr->next = first;
 }
 else
 {
  curr->next = second;
 }

 return head;
}

Node *creat()
{
 Node *head = NULL;
 Node *curr = NULL;
 Node *tmp = NULL;
 int d;

 cout << "input data." << endl;
 cin >> d;
 fflush(stdin);

 while (d)
 {
  tmp = (Node *)malloc(sizeof(Node));
  tmp->data = d;
  if (!head)
  {
   head = tmp;
   curr = head;
  }
  else
  {
   curr->next = tmp;
   curr = curr->next;
  }
  cout << "input data." << endl;
  cin >> d;
 }
 curr->next = NULL;
 return head;
}

void Free(Node *head)
{
 Node *tmp;
 while (head != NULL)
 {
  tmp = head;
  cout << head->data << " has been released." << endl;
  head = head->next;
  free(tmp);
 }
}

int main()
{
 Node *heada = creat();
 Node *headb = creat();
 Node *newhead = uniteList(heada, headb);
 
 Free(newhead);
 return 0;
}


链表的每个节点为一个包含学生学号、分数和下一个节点的结构体;

建立两个链表,并按升序合并它们。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef struct
{
 int num;
 int score;
 struct Stu *nextStu;
}Stu;

int Add(Stu **list);
int Merge(Stu **aList, Stu *bList);
int print(Stu *list);
int freeList(Stu *aList);

int main(void)
{
 Stu *aList = NULL, *bList = NULL;
 Add(&aList);
 print(aList);

 Add(&bList);
 print(bList);

 Merge(&aList, bList);
 print(aList);

 free(aList);
 return 0;
}

int Add(Stu **list)
{  
 int num; 
 Stu *head;
 Stu *tmp, *prev;

 puts("input stu num:");
 fflush(stdin);
 scanf("%d", &num);
 //puts("input stu score:");
 //fflush(stdin);
 //scanf("%d", &score);

 while (num)
 {
  if (*list == NULL)
  {
   *list = (Stu *)malloc(sizeof(Stu));
   assert(list);
   (*list)->num = num;
   puts("input stu score:");
   fflush(stdin);
   scanf("%d", &(*list)->score);
   (*list)->nextStu = NULL;
   head = *list;
  }
  else
  {
   tmp = head;
   while (tmp && num > tmp->num)
   {
    prev = tmp;
    tmp = tmp->nextStu;
   }
   if (tmp == head)
   {
    tmp = (Stu *)malloc(sizeof(Stu));
    assert(tmp);
    //head = tmp;
    tmp->num = num;
    puts("input stu score:");
    scanf("%d", &tmp->score);
    tmp->nextStu = head;
    head = tmp;
   }
   else
   {
    tmp = (Stu *)malloc(sizeof(Stu));
    assert(tmp);
    tmp->num = num;
    puts("input stu score:");
    scanf("%d", &tmp->score);
    tmp->nextStu = prev->nextStu;
    prev->nextStu = tmp;
   }
  }
  puts("input stu num:");
  fflush(stdin);
  scanf("%d", &num);
 }
 *list = head;
 return 0;
}

int print(Stu *list)
{
 Stu *head = list;
 puts("All Students.");
 while (head)
 {
  printf("stu No. = %05d, stu score = %3d\n", head->num, head->score);
  head = head->nextStu;
 }
 return 0;
}

int Merge(Stu **aList, Stu *bList)
{
 Stu *heada = *aList;
 Stu *headb = bList;
 Stu *prev;
 while (bList)
 {
  heada = *aList;
  prev = *aList;
  headb = bList;
  while (heada && bList->num > heada->num)
  {
   prev = heada;
   heada = heada->nextStu;
   //puts("alist");
  }
  bList = bList->nextStu;
  
  if (heada == *aList)
  {
   *aList = headb;
   (*aList)->nextStu = prev;
  }
  else
  {
   headb->nextStu = prev->nextStu;
   prev->nextStu = headb;
  }
  
  //puts("blist");
 }
 return 0;
}

int freeList(Stu *aList)
{
 Stu *tmp = aList;
 while (aList)
 {
  tmp = aList;  
  aList = aList->nextStu;
  free(tmp);
 }
 return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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