Question

C语言：用栈来逆置一个单链表，哪位大神能给出下面代码的详细的解释？谢谢

#include <stdio.h>
#include<stdlib.h>
#define stacksize 100
typedef int datatype;
typedef struct
{
datatype data[stacksize];
int top;
}seqstack;
typedef struct node
{
datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
linklist h;
linklist p;
int x;
linklist creatlist(int n)
{
linklist h;
listnode *p1,*p2;
int i;
h=(linklist)malloc(sizeof(listnode));
h->next=NULL; /*逆置单链表初始为空*/
p2=h;
printf("请输入链记录!:\n");
for(i=0;i<n;i++)
{
p1=(linklist)malloc(sizeof(listnode));
scanf("%d",&p1->data);
p1->next=p2->next; /*将当前处理节点p插入到逆置L的表头*/
p2->next=p1;
p2=p1; /*p指向下一个待插入的节点*/
}
return (h);
}
void print(linklist h,int n)
{
if(h==NULL)
printf("链表为空!\n");
printf("这%d个链记录是:\n",n);
p=h->next;
printf("%d",p->data);
x=1;
while(p->next!=NULL)
{
x++;
p=p->next;
printf("%4d",p->data);
if(!(x%10))
printf("\n");
}
}
datatype push(seqstack *s,int x)
{
if(s->top==stacksize-1)
printf("堆栈溢出!\n");
else
s->data[++s->top]=x;
}
datatype pop(seqstack *s)
{
if(s->top==-1)
printf("堆栈为空!\n");
else
return (s->data[s->top--]);
}
datatype deleted(linklist h)
{
datatype temp;
linklist p;
p=h->next;
temp=(p->data);
h->next=p->next;
free(p);
return (temp);
}
void invertedlist(linklist h,int n)
{
seqstack s;
int i,j,temp;
s.top=-1;
for(i=0;i<n;i++)
{
temp=deleted(h);
push(&s,temp);
}
for(i=0;i<n;i++)
{
temp=pop(&s);
printf("%5d",temp);
if(!((i+1)%10))
printf("\n");
}
printf("\n");
}
main()
{
linklist h;
int n;
printf("请输入n的值:\n");
scanf("%d",&n);
h=creatlist(n);
print(h,n);
printf("\n");
printf("经过逆置,链记录为:\n");
invertedlist(h,n);
system("pause");
return 0;
}

Answer 1

#include <stdio.h>
#include<stdlib.h>
#define stacksize 100
typedef int datatype;//这里所谓的datatype关键字是不存在的，所以这里用typedef (类型定义) 定义成int 型，意思是datatype 就是int
typedef struct
{
  datatype data[stacksize];
  int  top;
}seqstack;//这里定义了栈（其实就是结构体，里面有个int型的数组和int型的成员），在下面有栈的一些运算，

typedef struct node
{
  datatype  data;
  struct node *next;
}listnode;//这里定义了链表。int 型成员和 node * 指针

typedef listnode *linklist;//定义linklist指针，就是listnode 类型的指针
linklist h;
linklist p;
int x;

linklist creatlist(int n) //这里是创建链表
{
 linklist h;
 listnode *p1,*p2;
 int i;
 h=(linklist)malloc(sizeof(listnode));/*这里是为 h 这个结点（或者可称为结构体，它本来的面目）,申请内存空间，大小就是（sizeof(listnode)，就是结构体所占大小）*/

 h->next=NULL;    /*逆置单链表初始为空*/
 p2=h;
 printf("请输入链记录!:\n");

 for(i=0;i<n;i++)//这里就输入n个记录，比如1，2，3，4，5
 {
    p1=(linklist)malloc(sizeof(listnode));//同上
    scanf("%d",&p1->data);//输入该节点中的数据成员data的值
    p1->next=p2->next;  /*将当前处理节点p插入到逆置L的表头*/
    p2->next=p1;
    p2=p1; /*p指向下一个待插入的节点*/
 }
  return (h);
}

void print(linklist h,int n)//将该链表打印出来
{
 if(h==NULL)
          printf("链表为空!\n");
 printf("这%d个链记录是:\n",n);
 p=h->next;
 printf("%d",p->data);
 x=1;
 while(p->next!=NULL)
 {
     x++;
     p=p->next;
     printf("%4d",p->data);//这里就是P指针一直指向next, 循环打印，直到p=NULL..
     if(!(x%10))
            printf("\n");// - -这里应该是每打印10次就换行的意思。
 }
}
datatype push(seqstack *s,int x)   /*这里就是栈的操作，进栈，返回类型为datatype，实际上就是int,这里说下参数，第一个参数是指向栈的指针类型，第二个参数是你要进栈的值*/
{
 if(s->top==stacksize-1)//超出栈的大小
      printf("堆栈溢出!\n");
  else
            s->data[++s->top]=x;  
}
datatype pop(seqstack *s) //和上面相同，这个是出栈，return 栈的元素的值
{
  if(s->top==-1)
   printf("堆栈为空!\n");
  else
          return (s->data[s->top--]);
}
datatype deleted(linklist h)//删除链表结点的值，并将该结点中data值放到temp
{
   datatype temp;
   linklist p;
   p=h->next;
   temp=(p->data);
   h->next=p->next;
   free(p);//这步重要！释放结点所占的空间
   return (temp);
}
void invertedlist(linklist h,int n)//
{    
   seqstack s;
   int i,j,temp;
   s.top=-1;
   for(i=0;i<n;i++)//说白了就是将链表的值依次进栈
   {
      temp=deleted(h);
      push(&s,temp);  
   }
   for(i=0;i<n;i++)//然后将各个值依次出栈
   {
      temp=pop(&s);
      printf("%5d",temp);
      if(!((i+1)%10))
               printf("\n");
   }
   printf("\n");
}
main()
{
   linklist h;
   int n;
   printf("请输入n的值:\n");
   scanf("%d",&n);
   h=creatlist(n);
   print(h,n);
   printf("\n");
   printf("经过逆置,链记录为:\n");
   invertedlist(h,n);
   system("pause");
   return 0;
}

最后总结，原理就是利用栈的先进后出的特性来实现逆置的。有什么不懂可以再提问。