利用顺序栈逆置单链表的程序

#include<stdio.h>

typedef int SElemType

typedef struct node

{int data

struct node *next

}linklist

linklist *head

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct {

SElemType *base

SElemType *top

int stacksize

} SeqStack

SeqStack *S

linklist *creatlist()

{linklist *p,*q

int n=0

q=p=(struct node *)malloc(sizeof(linklist))

head=p

p->next=NULL

p=(struct node *)malloc(sizeof(linklist))

scanf("%d",&p->data)

while(p->data!=-1)

{

n=n+1

q->念链next=p

q=p

p=(struct node *)malloc(sizeof(linklist))

scanf("%d",&p->data)

}

q->next=NULL

return(head)

}

void print(linklist *head)

{linklist *p

p=head->next

if(p==NULL) printf("this is an empty list.\n")

else

{

do {printf("%6d",p->data)

p=p->next

}while(p!=NULL)

printf("\n")

}

}

int InitStack (SeqStack *S ){

S->base = (SElemType*) malloc (STACK_INIT_SIZE * sizeof(SElemType))

if (! S->base) return 0

S->top =S->base

S->stacksize =STACK_INIT_SIZE

return 1

}

int push(SeqStack *S,SElemType e)

{

if(S->top -S->base >= S->stacksize)

{

S->base = (SElemType *)realloc(S->base,

(S->stacksize+STACKINCREMENT)*sizeof (SElemType))

if (! S->base ) return 0

S->top =S->base+S->stacksize

S->槐胡stacksize+= STACKINCREMENT

}

*S->top++=e

return 1

}

int Pop (SeqStack *S )

{

if(S->铅高拦top ==S->base) return 0

--S->top

return *S->top

}

int stackempty(SeqStack *S)

{

if (S->top ==S->base ) return 1

else return 0

}

linklist *backlinklist(linklist *head)

{

linklist *p

p=head->next

InitStack (S )

while(p)

{

if( push(S,p->data))

p=p->next

}

p=head->next

while(!stackempty(S))

{

p->data=Pop(S)

p=p->next

}

return(head)

}

void main()

{

linklist *head

head=creatlist()

print(head)

head=backlinklist(head)

print(head)

}

nizhi()函数改动如下：

void nizhi(LINKLIST*L) //补充此函数

{

SeqStack S

LINKLIST q

q = (*L)->next

InitStack(&S)

while(q)

{

if (Push(&S, q))

q = q->next

}

printf("开始逆序输出……\n")

while(!IsEmpty(S))

{

Pop(&S, &q)

printf("%3c", q->data)

}

printf("\n逆序输出完成\n")

}

现在可以在nizhi()函数中生成逆序节点。

但是不能保存到原链表中去，那样就会覆盖原先节点的值。

如果要得到逆置的链表，就得生成另一个新的链表，可以这样做：

void nizhi(LINKLIST*L) //补充此函数

{

SeqStack S

LINKLIST q, head, r, p

q = (*L)->next

InitStack(&S)

while(q)

{

if (Push(&S, q))

q = q->next

}

printf("开始逆置迟谈悉到新链表中……")

head=(LINKLIST )malloc(sizeof(NODE))//创侍哗建新链表的头结点

r = head

while(!IsEmpty(S))

{

Pop(&S, &q)

p = (NODE *)malloc(sizeof(NODE))

p->data = q->data

r->next = p

r = p

}

r->next=NULL

*L = head

printf("逆置完成\n")

}

现在功能完全实现了，但是原先程序和这段代码都没有考虑释放已经分配的内存，所以会造成内存泄漏，需要继续完善码乎。

---