第6章22题的完整程序

// 6_22.cpp : 已知带头节点的动态单链表L中的节点是按整数值递增排列的,

// 试设计一算法将值为X的节点插入表L中,使L依然有序。

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

 

#include "stdafx.h"

#include <stdlib.h>

#include <time.h>

 

typedef struct node

{

      int 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(void)

// 生成随机链表L的函数

// 其中srand()和rand()是用来产生随机数的函数。

{

      srand( (unsigned)time( NULL ) );

      int i = rand() % 5;

      int j = 0;

 

      node *head = NULL;

      node *s = NULL;

      node *r = NULL;

 

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

      scanf("%d", &j);

 

      if (j <= 0)

      {

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

            return NULL;

      }

 

      for (; j > 0; j–)

      {

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

 

            if(s == NULL)

            {

                  printf("内存分配出错!n");

                  return NULL;

            }

 

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

 

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

            // 这样可以保证s每次都比以前大

            // 参数可以自己设定

 

            if (head == NULL)

            {

                  head = s;

            }

            else

                  r->pNext = s;

 

            r = s;

      }

 

      if (r != NULL)

      {

            r->pNext = NULL;

      }

 

      s = head;

 

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

      if(head == NULL)

      {

            printf("内存分配出错!n");

            return NULL;

      }

 

      head->pNext = s;

 

      return head;

}

 

void printList(node* head)

// 显示链表的函数

{

      if (head == NULL && head->pNext == NULL)

      {

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

            return;

      }

 

      node* p = head->pNext;

 

      printf("当前表是:n");

 

      do

      {

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

 

            p = p->pNext;

      }

      while(p != NULL);

 

      printf("n");

}

 

void Insert(node *head, int n)

// 将节点插入链表的函数

{

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

      // insert指向的是新分配的空间

 

      if (insert == NULL)

      {

            printf("分配地址出错!n");

            return;

      }

 

      insert->data = n;

 

 

      if (head == NULL)

      {

            printf("原链表出错!n");

            return;

 

      }

 

      node *before = head->pNext;

      // 注意不是 before = head; 因为有头节点。

 

      if(n <= before->data)

      {

            head->pNext = insert;

            insert->pNext = before;

            return;

      }// 如果没有比n小的数据,则把insert作为头节点之后的第一个节点

 

      while (before->pNext != NULL && n > before->pNext->data)

      {

            before = before->pNext;

      }

      // 将before移动到要插入结点的位置的前一个

 

      if(before->pNext == NULL)

      {

            insert->pNext = NULL;

            before->pNext = insert;

      }// 如果before已经是链表尾,则把insert作为新的表尾

      else

      {

            insert->pNext = before->pNext;

            before->pNext = insert;     

      }

}

 

 

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

{

      int n = 0;

      node *head = CreateIncreaseList();

 

      printList(head);

 

      printf("请输入一个数:");

      scanf("%d", &n);

 

      Insert(head, n);

      printList(head);

 

      del(head);

      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 博主赞过: