第6章21题完整程序

// 6_21.cpp : 设有一线性表E={e1, e2, ..en-1, en},试设计一个算法,将线性表逆置,即,使元素排列次序颠倒过来,

// 成为逆线性表E’={en, en-1, … , e2, e1},要求逆线性表占用原线性表空间,并且用单链表表示。写出处理过程。

//

 

#include "stdafx.h"

#include <stdlib.h>

 

typedef int datatype;

 

typedef struct node

{

      datatype data;

      node * pNext;

 

}list;

 

void del (node* head)

// 删除链表的函数

{

      node* p = head;

 

      if(head == NULL)

      {

            return;

      }

 

      while(head != NULL)

      {

            p = head->pNext;

            delete(head);

            head = p;

      }

 

      return;

}

 

node* CreateList(void)

// 建表的函数,使用0作为结束标志

{

      datatype d;

 

      node *head = NULL, *s, *r = NULL;

 

      printf("请输入第1个节点值:");

      scanf("%d", &d);

 

      while(d != 0)

      {

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

 

            if (s == NULL)

            {

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

                  r->pNext = NULL;

                  return head;

            }

 

            s->data = d;

 

            if (head == NULL)

            {

                  head = s;

            }

            else r->pNext = s;

 

            r = s;

 

            printf("请输入下一个节点值(输入0结束):");

            scanf("%d", &d);

      }

 

      if(r != NULL)

            r->pNext = NULL;

 

      return head;

}

 

void printList(node* head)

// 显示链表的函数

{

      node* p = head;

 

      if (head == NULL)

      {

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

            return;

      }

 

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

 

      do

      {

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

 

            p = p->pNext;

      }

      while(p != NULL);

 

      printf("n");

}

 

node* invertList(node* shead)

// 逆置链表的程序,其实就是一个头插法建表的程序,只不过不用分配空间

{

      node* thead = shead;

      node* r = shead;

      node* t = shead;

 

      if (shead == NULL)

      {

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

            return NULL;

      }

 

      while (r != NULL)

      {

            thead = r;

            r = r->pNext;

            thead->pNext = t;

            t = thead;

      }

 

      shead->pNext = NULL;

 

      return thead;

}

 

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

{

      node* E = CreateList();

 

      printList(E);

 

      printList(invertList(E));

 

      del(E);

 

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