王道数据结构练习

练习2.5

//试编写算法将带头结点的单链表就地逆置

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

using namespace std;

typedef struct Lnode{

    int data;

    struct Lnode *next;

}Lnode,*LinkList;

//初始化带头节点的单链表

void init_LinkList(LinkList &L){

    int x;

    L = (LinkList)malloc(sizeof(Lnode));

    Lnode *r = L,*p;

    cout<<"请输入数据（-1退出）：";

    cin>>x;

    while(x != -1){

        p = (Lnode*)malloc(sizeof(Lnode));

        p->data = x;

        p->next = NULL;

        r->next = p;

        cout<<p->data<<" "<<p<<" "<<p->next<<endl;

        r = p;

        cout<<"请输入数据（-1退出）：";

        cin>>x;

        }

}

//逆置单链表,采用头插法

void reverse_LinkList(LinkList &L){

    Lnode *r,*p;

//p指向表头下一个，即要插入位置 ,r指向原序表

    r = L->next;

    L->next = NULL;

    while(r != NULL){

        p = r;

        r = r->next;

        p->next = L->next;

        L->next = p;

    }

}

int main(){

    LinkList L;

     init_LinkList(L);

    Lnode *p;

    p = L->next;

    while(p!= NULL){

        cout<<p->data<<" ";

        p = p->next;

    }

    cout<<endl;

     p = L;

    reverse_LinkList(p);

    p = L->next;

    while(p!= NULL){

        cout<<p->data<<" ";

        p = p->next;

    }

}