回复 3楼 jun331207100
程序代码:
/*单链表的操作实现(这部分没有问题)*/
#include <stdio.h>
typedef struct Node
{
DataType data; //数据域
struct Node *next; //指针域
}SLNode;
//初始化()
void ListInitiate(SLNode **head)
{
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)
exit(1);
(*head)->next=NULL;
}
//插入元素
int ListInsert(SLNode *head, int i, DataType x)
{
SLNode *p, *q;
int j;
p=head;
j=-1;
while((p->next)!=NULL && j<i-1)
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("error!");
return 0;
}
if((q=(SLNode *)malloc(sizeof(SLNode)))==NULL)
exit(1);
q->data=x;
q->next=p->next;
p->next=q;
return 1;
}
//输出链表元素
void printSLNode(SLNode *head)
{
SLNode *p;
p=head;
while(p->next!=NULL)
{
p=p->next;
printf("%d ",p->data);
}
}
-------------------------------------------------------------
/*顺序堆栈的操作实现*/
#include<stdio.h>
typedef struct
{
SLNode *stack[MaxStackSize]; //stack表示存放数据的数组,这里直接定义存放SLNode类型指针
int top; //top表示当前栈顶位置
}SeqStack;
//初始化
void StackInitiate(SeqStack *S)
{
S->top =0;
}
//非空否,若为空,返回0
int StackNotEmpty(SeqStack S)
{
if(S.top<=0)
return 0;
else
return 1;
}
//入栈
int StackPush(SeqStack *S,SLNode *x)
{
if(S->top>=MaxStackSize)
{
printf ("堆栈已满!\n");
return 0;
}
else
{
S->stack[S->top]=x; //将SLNode类型的元素x放入堆栈的数组中,top自加1
S->top++;
return 1;
}
}
//出栈
int StackPop(SeqStack *S,SLNode **d) //第二个参数为SLNode **d是因为,d指向SLNode中的next,而next是SLNode指针,所以d是指向指针的指针
{
if(S->top<=0)
{
printf("堆栈已空!\n");
return 0;
}
else
{
S->top--;
*d=S->stack[S->top];
return 1;
}
}
//逆置实现函数
int reverseByStack(SLNode *head)
{
SeqStack tempStack;
SLNode *tempList,*d,*p;
ListInitiate(&tempList);
tempList=head; //使tempList指向要逆置链表的头结点
while(tempList->next!=NULL) //入栈
{
if(StackPush(&tempStack,tempList->next)==0)
{
printf("error!\n");
return 0;
}
tempList=tempList->next;
}
ListInitiate(&p);
p=head;
while(StackNotEmpty(tempStack))
if(StackPop(&tempStack,&d)==1)
{
p->next=d;
p=p->next;
}
p->next=NULL;
return 1;
}
----------------------------------------------------------------
/*测试函数*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MaxStackSize 100
typedef int DataType; //定义单链表数据类型为int型
#include "LinList.h" // 单链表头文件
#include "reverseByStack.h" //顺序堆栈头文件及实现函数
void main()
{
SLNode *head;
int i;
ListInitiate(&head); //新建链表,插入数据1到10
for(i=0;i<10;i++)
{
if(ListInsert(head, i, i+1)==0)
{
printf("error!");
return;
}
}
printf("The former list is\n");
printSLNode(head); //输出单链表元素
if(reverseByStack(head))
printf("\ncurrent list is\n");
printSLNode(head);
}
有点长,我尽量加注释,谢谢鸟!!
[
本帖最后由 xyaliner 于 2012-10-29 21:47 编辑 ]