orderedlist.cpp

C++&datastructure书籍源码,以前外教提供现在与大家共享

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#include "prompt.h"

// read words in a file, store in order in a linked list

struct Node
{
   string info;
   Node * next;
   Node(const string& s, Node * link)
     : info(s), next(link)
   { }
};

Node* AddInOrder(Node* list, const string& s)
// pre: list is sorted
// post: add s to list, keep list sorted, return new list with s in it
{
    Node * first = list;   // hang onto first node
    
    // if new node is first, handle this case and return    
    if (first == 0 || s < first->info)        
    {   return new Node(s,first);
    }

    // assert: s >= list->info
    while (list->next != 0 && list->next->info < s)
    {   list = list->next;
    }
    // assert: s >= list->info and s < list->next->info (conceptually)
    
    list->next = new Node(s,list->next);
    return first;
}

void Print(Node * list)
{
    for(; list != 0; list=list->next)
    {   cout << list->info << endl;
    }
}

int main()
{
    Node * list = 0;  // empty
    string word, filename = PromptString("filename: ");
    ifstream input(filename.c_str());
    while (input >> word)
    {   list = AddInOrder(list,word);
    }
    Print(list);
    return 0;
}