第6章19题的完整程序

// 6_19.cpp : 设有两个顺序表A和B,元素的个数分别是m和n,若表中的数据都是从小到大顺序排列的,

// 且这(m+n)个数据中没有相同的。

// 试设计算法将A和B合并成一个线性表C,并存储到另一个向量中。

//

// 说明:本程序使用了随机生成的顺序表作为原始数据。

 

#include "stdafx.h"

#include <stdlib.h>

#include <time.h>

 

typedef int datatype;

 

typedef struct node

{

      datatype data;

      node* pNext;

}node;

 

void del (node* head)

// 删除链表的函数

{

      node* p = head;

 

      if(head == NULL)

      {

            return;

      }

 

      while(head != NULL)

      {

            p = head->pNext;

            delete(head);

            head = p;

      }

 

      return;

}

 

void CreateIncreaseList(int m, int n, node **a, node **b)

// 生成随机顺序表的函数,使用传出参数将a和b的头指针返回

// srand()和rand()是产生随机数的函数

{

      srand( (unsigned)time( NULL ) );

      int i = rand() % 5;

      int j = 0;

      int k = 0;

 

      node *head[2] = {NULL};

      node *s = NULL;

      node *r[2] = {NULL};

 

      for (j = m + n; j > 0; j–)

      {

            k = rand() % 2;

            // 使用一个指针数组,这样就可以通过一个随机数k(0或1)来随机选择

            // 要把s插到a或b表中。

 

            s =(node*)malloc(sizeof(node));

 

            s->data = i += rand() % 3 + 1;

 

            // 产生一个1 – 4 的随机数,增加到i上,然后赋给s->data,

            // 这样可以保证每个s的data是递增的。

            // 当然,也可以采用别的参数。

 

            if (head[k] == NULL)

            {

                  head[k] = s;

            }

            else

                  r[k]->pNext = s;

 

            r[k] = s;

      }

 

      for (k = 0; k <= 1; k++)

      {

            if (r[k] != NULL)

            {

                  r[k]->pNext = NULL;

            }

 

      }

      *a = head[0];

      *b = head[1];

 

      return;

}

 

void printList(node* head)

// 显示链表的函数

{

      node* p = head;

 

      if (head == NULL)

      {

            printf("这是一个空表!n");

            return;

      }

 

      do

      {

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

 

            p = p->pNext;

      }

      while(p != NULL);

 

      printf("n");

}

 

node* GetCombineList(node * a, node * b)

// 合并数据的函数

{

      node *ra = a;

      node *rb = b;

      node *t = NULL;

 

      node *head = NULL;

      t = head;

 

      if (ra->data > rb->data)

      {

            head = rb;

            t = rb;

            rb = rb->pNext;

      }

      else

      {

            head = ra;

            t = ra;

            ra = ra->pNext;

      }

      // 检查第一个结点,把它作为表c的头节点

 

      while (ra != NULL && rb != NULL)

      {

            if (ra->data > rb->data)

            {

                  t->pNext = rb;

                  t = rb;

                  rb = rb->pNext;

            }

            else

            {

                  t->pNext = ra;

                  t = ra;

                  ra = ra->pNext;

            }

      }

      // 当表a和表b都不为空的时候,一次比较两个表的头节点,

      // 把比较小的一个接到表c中(尾插法)

 

      if (ra == NULL)

      {

            ra = rb;

      }

 

      t->pNext = ra;

 

      // 当a和b中有一个空了以后,把剩下的那个表接到c中就行了

 

      return head;

}

 

int main(int argc, char* argv[])

{

      node *a = NULL;

      node *b = NULL;

 

      int m;

      int n;

      printf("请输入m:");

      scanf("%d", &m);

 

      printf("请输入n:");

      scanf("%d", &n);

 

      CreateIncreaseList(m, n, &a, &b);

 

      printf("表a:n");

      printList(a);

 

      printf("表b:n");

      printList(b);

 

      node *c = GetCombineList(a, b);

 

      printf("表c:n");

      printList(c);

 

      del(c);

 

      return 0;

}

 

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: