第6章27题的完整程序

// 6_27.cpp : 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,

// 试编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C,

// 并要求利用原表(即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;

}

 

node* CreateIncreaseList(char* t)

// 生成原始数据的函数

// 其中srand()和rand()是随机数生成函数

// t是表的名字,用来统一输入的提示语句,没什么用处。

{

      srand( (unsigned)time( NULL ) );

      int i = rand() % 5;

      int j = 0;

 

      node *head = NULL;

      node *s = NULL;

      node *r = NULL;

 

      printf("请输入线性表%s的元素数:", t);

      scanf("%d", &j);

      // 提示表名,就不用再写一句printf了:-)

 

      if (j <= 0)

      {

            printf("不合法,将退出!n");

            return NULL;

      }

 

      for (; j > 0; j–)

      {

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

 

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

 

            // 产生一个1 – 4 的随机数,加到i上,再赋给s->data,可以保证每次

            // s->data的值是增加的。

            // 参数可以自己改变。

 

            if (head == NULL)

            {

                  head = s;

            }

            else

                  r->pNext = s;

 

            r = s;

      }

 

      if (r != NULL)

      {

            r->pNext = NULL;

      }

 

      return head;

}

 

void printList(node* head, const char* t)

// 显示链表的函数,t是链表的名字。

// 其实可以把char* t写到node的定义里的,懒得写了:-)

{

      node* p = head;

 

      if (head == NULL)

      {

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

            return;

      }

 

      printf("n当前表%s是:n", t);

 

      do

      {

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

            // "%8d" 比用 "%dt" 更紧凑一点

 

            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;

 

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

      {

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

            {

                  head = rb;

                  rb = rb->pNext;

            }

            else

            {

                  head = ra;

                  ra = ra->pNext;

            }

            head->pNext = t;

            t = head;

      }

      // 当a和b都非空时,从头开始逐一比较,取出小的插入表c

 

      if (ra == NULL)

      {

            ra = rb;

      }

      // 当a和b中有一个空了时,把剩下那个非空的表用ra表示。

      // 其实就是一个小技巧,省去了几行语句。

 

      while (ra != NULL)

      {

            head = ra;

            ra = ra->pNext;

            head->pNext = t;

            t = head;

      }

      // 把剩下的那个表逐一插入表c

 

      return head;

}

 

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

{

      node *a = CreateIncreaseList("a");

 

      printList(a, "a");

 

      node *b = CreateIncreaseList("b");

 

      printList(b, "b");

 

      node *c = GetCombineList(a, b);

 

      printList(c, "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 博主赞过: