第6章31题的完整程序

// 6_31.cpp : 已知,由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符,数字字符和其他字符),

// 是编写算法构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,

// 且利用原表中的节点空间作为这三个表的结点空间,头节点可另辟空间。

//

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

 

#include "stdafx.h"

#include <stdlib.h>

#include <time.h>

 

typedef struct node

{

      char data;

      node *pNext;

}node;

 

void del (node* head)

// 删除链表的函数

{

      node* p = head;

      node* q = head;

 

      if(head == NULL)

      {

            return;

      }

 

      while(head != q)

      {

            p = head;

            head = head->pNext;

            delete(p);

      }

      // 注意这里,是head != q 。因为是循环链表,所以如果还用

      // head->pNext != NULL的话会出错。

 

      return;

}

 

node* CreateIncreaseList(void)

// 随机生成数据的函数

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

{

      srand( (unsigned)time( NULL ) );

      int i = rand() % 5 + 40;

      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));

 

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

 

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

            // 参数可以自己设定

 

            if(i >= 127)

            {

                  i -= 128;

            }

 

            // 保证值在ASCII码中,否则会溢出,显示一串问号

            // 用 i %= 128 也可以,但是可能引发效率问题。

 

            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;

      head->data = ”;

 

      // 给头节点赋零值

 

      return head;

}

 

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

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

{     

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

      {

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

            return;

      }

 

      node* p = head->pNext;

 

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

 

      do

      {

            printf("%ct", p->data);

 

            p = p->pNext;

      }

      while(p != NULL && p->data != ”);

 

      printf("n");

}

 

void Proceed(node* head, node** a, node** b, node** c)

{

      // 处理循环链表的函数,可能比较难懂

      // 使用a,b,c作为传出指针

 

      int i = 0;

 

      node* list[3] = {*a, *b, *c};

      // 将a、b、c 的表头分别存入一个指针数组,便于分类和处理

 

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

      {

            printf("原列表为空!n");

            return;

      }

 

      node* temp = head->pNext;

 

      for (i = 0; i < 3; i++)

      {

            if (list[i] == NULL)

            {

                  list[i] = (node*)malloc(sizeof(node));

 

                  if (list[i] == NULL)

                  {

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

                        return;

                  }

            }

            // 确保a、b、c均对应可用内存

 

            list[i]->data = ”;                  //置头节点标记

            list[i]->pNext = NULL;

      }

      //为a、b、c赋初值

 

      node* s[3];

 

      for (i = 0; i < 3; i++)

      {

            s[i] = list[i];

      }

      // s是三个临时指针,分别与a、b、c三个表对应

 

      while (temp != NULL)

      {

            i = 0;

            if (temp->data >= ‘0’ && temp->data <= ‘9’)

            {

                  i = 1;

            }

            else if ((temp->data >= ‘a’ && temp->data <= ‘z’) || (temp->data >= ‘A’ && temp->data <= ‘Z’))

            {

                  i = 2;

            }

            // 本来可以用tolower()函数将大小写一同处理,但发现tolower()在处理一些符号的时候出问题。

 

            // 用一个i表示要处理字符的类型,直接向list[i]中添加节点

 

            s[i]->pNext = temp;

 

            s[i] = temp;

 

            temp = temp->pNext;

      }

 

      for (i = 0; i < 3; i++)

      {

            s[i]->pNext = list[i];

      }

      // 处理循环

 

 

      *a = list[0];

      *b = list[1];

      *c = list[2];

      // 保证a、b、c与list的对应头是相同的

      // 因为开始的时候可能会分配空间

 

 

      return;

}

 

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

{

      node *head = CreateIncreaseList();

      node *a = NULL;

      node *b = NULL;

      node *c = NULL;

 

      printList(head, "初始");

 

      Proceed(head, &a, &b, &c);

      // 执行后a、b、c就有值了

      printList(a, "其它");

      printList(b, "数字");

      printList(c, "字符");

 

      del(a);

      del(b);

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