关于单链表的逆置问题
刚开始学数据结构，做一个逆置程序，昨天搜出来一个程序，就是有好多疑问望高手解释下程序。
#include <stdio.h>
typedef struct QLink
{
int data;
struct QLink *next;
}QLink;
main()
{
QLink *head,*p,*q;
int length,i;
printf( "此程序是实现链表置逆的功能.\n ");
printf( "请输入链表的长度: ");
scanf( "%d ",&length);
printf( "现在要输入各结点的值.\n ");
for(i=1;i <=length;i++)
{
p=(QLink *)malloc(sizeof(QLink));
scanf( "%d ",&p-> data);
p-> next=NULL;
if(i==1) head=p;
else
{
q=head;
while(q-> next!=NULL) q=q-> next; // 这一部分代码什么意思，
q-> next=p; //为什么这么写啊？？
}
}
printf( "链表已建立，现在要将它输出.\n ");
p=head;
for(i=1;i <=length;i++)
{
printf( "%d ",p-> data);
p=p-> next;
}
printf( "\n ");
printf( "现在要将其置逆.\n ");
printf( "程序置逆中……\n ");
printf( "置逆成功.现在要将新的链表输出.\n ");
p=head;
while(head-> next!=NULL)
{ 这一部分是逆置的程序，看不懂什么意思
q=p; 能不能解释下啊。这个程序好象没有头
p=head-> next; 结点。
head-> next=p-> next;
p-> next=q;
}
head=p;
p=head;
for(i=1;i <=length;i++)
{
printf( "%d ",p-> data);
p=p-> next;
}
system( "pause ");
}
[解决办法]
都是一些很基本的插入，删除操作而已， 欧觉得你还是好好把数据结构
书拿来仔细看看的好，弄清楚原理才是关键!
[解决办法]
#include <stdio.h>
typedef struct QLink
{
int data;
struct QLink *next;
}QLink; // 定义一个结构体,其中包括数据和指向下个结点的指针
main()
{
QLink *head,*p,*q; //定义三个qlink的指针
int length,i;
printf( "此程序是实现链表置逆的功能.\n ");
printf( "请输入链表的长度: ");
scanf( "%d ",&length);
printf( "现在要输入各结点的值.\n ");
for(i=1;i <=length;i++)
{
p=(QLink *)malloc(sizeof(QLink)); //为其申请空间
scanf( "%d ",&p-> data); //将数据存入
p-> next=NULL; //将其next指针设为空
if(i==1) head=p; //如果p是第一个结点,将头指针指向它
else
{
q=head;
while(q-> next!=NULL) q=q-> next; //这段意思是将q结点找到链表中的最后
q-> next=p; //一个结点,然后将p结点插在尾部,这样就完成了插入
}
}
printf( "链表已建立，现在要将它输出.\n ");
p=head;
for(i=1;i <=length;i++)
{
printf( "%d ",p-> data);
p=p-> next;
}
printf( "\n ");
printf( "现在要将其置逆.\n ");
printf( "程序置逆中……\n ");
printf( "置逆成功.现在要将新的链表输出.\n ");
p=head;
while(head-> next!=NULL)
{ q=p; //楼主可以动手画画图就可以了解到底是怎么指的
p=head-> next; //举个例子,本题的意思是 现在1-> 2-> 3-> 4
head-> next=p-> next; //循环一次后 会变成 2-> 1-> 3-> 4 再循环一次后为
p-> next=q; //3-> 2-> 1-> 4大概就是这个道理,楼主自己研究下.
}
head=p;
p=head;
for(i=1;i <=length;i++)
{
printf( "%d ",p-> data);
p=p-> next;
}
system( "pause ");
}
[解决办法]
ls说的对，先看懂算法的说。。。
[解决办法]
我不习惯这种描述,我一般都这样写逆置
我用H代表head, N代表NULL
原来:H-> 1-> 2-> 3-> N
q=h; //q-> H
p=q-> next; //p-> 1,保存原来的节点顺序
h-> next=NULL;
while(p!=NULL) //p-> N? 不等于N,继续
{
q=p; //第一次:q-> 1,第二次:q-> 2, 第三次:q-> 3
p=p-> next; // 第一次:p-> 2,第二次:p-> 3, 第三次:p-> N
q-> next=h-> next; //第一次:1-> N,第二次:2-> 1, 第三次:3-> 2
h-> next=q; //第一次:H-> 1.第二次:H-> 2, 第三次:H-> 3
} //第一次之后:H-> 1-> N 和 2-> 3-> N 两段
//第二次之后:H-> 2-> 1-> N 和 3-> N 两段
//第三次之后:H-> 3-> 2-> 1-> N
//第三次结束时,p-> N,即循环条件结束,退出循环,逆置完成
[解决办法]
//利用栈来实现单链表的逆序
#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 head;
linklist p;
int count;
linklist creatlist(int n)
{
linklist head;
listnode *p1,*p2;
int i;
head=(linklist)malloc(sizeof(listnode));
head-> next=NULL;
p2=head;
printf( "Please input the records of the chain!\n ");
for(i=0;i <n;i++)
{
p1=(linklist)malloc(sizeof(listnode));
scanf( "%d ",&p1-> data);
p1-> next=p2-> next;
p2-> next=p1;
p2=p1;
}
return (head);
}
void print(linklist head,int n)
{
if(head==NULL)
printf( "list null!\n ");
printf( "Now these %d records are:\n ",n);
p=head-> next;
printf( "%4d ",p-> data);
count=1;
while(p-> next!=NULL)
{
count++;
p=p-> next;
printf( "%4d ",p-> data);
if(!(count%10))
printf( "\n ");
}
}
datatype push(seqstack *s,int x)
{
if(s-> top==stacksize-1)
printf( "The stack is overflow!\n ");
else
s-> data[++s-> top]=x;
}
datatype pop(seqstack *s)
{
if(s-> top==-1)
printf( "the stack is empty!\n ");
else
return (s-> data[s-> top--]);
}
datatype deleted(linklist head)
{
datatype temp;
linklist p;
p=head-> next;
temp=(p-> data);
head-> next=p-> next;
free(p);
return (temp);
}
void invertedlist(linklist head,int n)
{
seqstack s;
int i,j,temp;
s.top=-1;
for(i=0;i <n;i++)
{
temp=deleted(head);
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 head;
int n;
printf( "Please input the value of n:\n ");
scanf( "%d ",&n);
head=creatlist(n);
print(head,n);
printf( "\n ");
printf( "After inverting,the records of the chain are:\n ");
invertedlist(head,n);
system( "pause ");
return 0;
}
运行结果：
Please input the value of n:
10
Please input the records of the chain!
-5 8 6 -1 0 1 2 -5 6 7
Now these 10 records are:
-5 8 6 -1 0 1 2 -5 6 7
After inverting,the records of the chain are:
7 6 -5 2 1 0 -1 6 8 -5
请按任意键继续. . .
[解决办法]
jixingzhong(瞌睡虫·星辰)
是不是天天就在CSDN上阿
在那都能看到你 厉害 高手
[解决办法]
虫虫写得好详细啊～～
[解决办法]
虫虫好
[解决办法]
路过，学习。
[解决办法]
用栈更方便
