逆置（链表表示）.cpp

数据结构实验--实现链表的插入与删除（源码

/*3．写一个线性表的转置算法（链表表示）
   （a1,a2,….,an)变为（an,an-1,….,a1)*/
/*......................................................*/
#include <stdio.h> /*标准输入、输出函数库*/
#include <stdlib.h>
#define LEN sizeof(struct list)
/*定义节点数据类型*/
struct list
{
int data; /*节点的数据类型，可以是其它类型*/
 list * next;
};
/* 创建链表，并返回表头指针 */
 list * create(void); 
/*对链表逆置的函数*/
 list * invert( list *);
/*输出链表*/
void print( list *);
int main()
{
  list *h,*t; /*定义一个链表，h为头指针*/
  printf("请输入一个结点数据(以0结束输入)：\n");
  h = create(); /*创建链表*/
  printf("创建的链表是：\n");
  print(h); /*输出所创建的链表*/
  t=invert(h); /*对链表进行逆置*/
  printf("逆置后的链表是：\n");
  print(t); /*输出逆置后的链表*/
  return 0;
}
 list * create() /* 创建链表，并返回表头指针。带一个头指针的链表 */
{
 list *head; /* 表头 */
 list *p; /* 新建结点 */
 list *tail; /*表尾节点*/
 int input; /*输入的数据*/
 head = NULL; /* 还没有任何数据，表头为空 */
 tail = head; /*尾指针首先指向表头指针*/
//printf("请输入结点数据：\n");
//scanf("%d",&input);
 while (input!=0) /* 假设data为0表示输入结束 */
 { 
	 scanf("%d",&input);
     p = (struct list *)malloc(LEN); /* 新建一个结点 */
     p->data=input;
     p->next=NULL;
  if (head==NULL)/*链表为空表*/
       head=p;
  else 
     tail->next = p; /* 在表尾链接新结点 */
      tail = p; /* 新建结点成为表尾 */
     printf("请输入一个结点数据：\n");
//scanf("%d",&input);
 }
  if (head!=NULL) /*输入了数据，已插入节点*/
      tail->next = NULL; /* 输入结束，表尾结点的下一个结点为空 */
     return head; /* 返回表头指针 */
}
void print( list *head) /*输出链表*/
{
if (head==NULL)
{
printf("链表空！\n");
return;
}
while(head!= NULL)
{
printf("%4d",head->data);
head = head->next;
}
printf("\n");
}
/*对链表逆置的函数*/
 list * invert( list * head)
{
     list *p,*q; /*用于逆置的中间变量*/
    if (head==NULL)
   {
       printf("链表空！\n");
       return head;
    }
    p=head; 
    head=NULL;
    while (p!=NULL)
    {//采用头插法插入数据
         q=p->next;
         p->next=head;
         head=p;
         p=q;
     }
    return head;
}