海涛老师的面试题作业5从尾到头打印链表

View Code
  1 // 从尾到头打印链表.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <stack>
  6 #include <stdlib.h>
  7 #include <iostream>
  8 using namespace std;
  9 
 10 static int arr[5];
 11 struct ListNode
 12 {
 13     int m_nkey;
 14     ListNode* m_pNext;
 15 };
 16 
 17 ListNode* NewNode(int key)
 18 {
 19     ListNode* pNode=(ListNode*)malloc(sizeof(struct ListNode));
 20     pNode->m_nkey=key;
 21     pNode->m_pNext=NULL;
 22     return pNode;
 23 }
 24 
 25 static void CreateList(ListNode* Head)
 26 {
 27     for(int i=0;i<5;i++)
 28         arr[i]=rand()%100;
 29     for(int i=0;i<5;i++)
 30         cout<<arr[i]<<" ";
 31     cout<<endl;
 32     ListNode* pPrev=Head;
 33     ListNode* pNode;
 34     for(int i=1;i<5;i++)
 35     {
 36         pNode=NewNode(arr[i]);
 37         pPrev->m_pNext=pNode;
 38         pPrev=pNode;
 39     }
 40 }
 41 
 42 
 43 static void PrintListReversingly_Iter(ListNode* Head) //以栈结构进行反转输出
 44 {
 45     stack<ListNode*> Nodes;
 46     ListNode *pNode=Head;
 47     while(pNode)
 48     {
 49         Nodes.push(pNode);
 50         pNode=pNode->m_pNext;
 51     }
 52     while(!Nodes.empty())
 53     {
 54         pNode=Nodes.top();
 55         cout<<pNode->m_nkey<<"****";
 56         Nodes.pop();
 57     }
 58 }
 59 
 60 
 61 static void PrintListRecur(ListNode* Head)          //间接以栈结构递归反转输出
 62 {
 63     if(Head)
 64     {
 65         if(Head->m_pNext)
 66             PrintListRecur(Head->m_pNext);
 67         cout<<Head->m_nkey<<"****";
 68     }
 69 }
 70 
 71 static void PrintListReverseNode(ListNode* Head)      //修改链表指向来进行反转输出
 72 {
 73     ListNode* pPrev=Head;
 74     ListNode* pNext=NULL;
 75     ListNode* pNode=Head->m_pNext;
 76     Head->m_pNext=NULL;
 77     while(pNode)
 78     {
 79         pNext=pNode->m_pNext;
 80         pNode->m_pNext=pPrev;
 81         pPrev=pNode;
 82         pNode=pNext;
 83     }
 84     while(pPrev)
 85     {
 86         cout<<pPrev->m_nkey<<"****";
 87         pPrev=pPrev->m_pNext;
 88     }
 89 }
 90 
 91 
 92 
 93 int _tmain(int argc, _TCHAR* argv[])
 94 {
 95     ListNode* Head=(ListNode* )malloc(sizeof(struct ListNode));
 96     Head->m_pNext=NULL;
 97     CreateList(Head);
 98     Head->m_nkey=arr[0];
 99     PrintListReversingly_Iter(Head);
100     cout<<endl;
101     PrintListRecur(Head);
102     cout<<endl;
103     PrintListReverseNode(Head);
104     return 0;
105 }