?
Solved

text file sorting

Posted on 2003-03-04
17
Medium Priority
?
230 Views
Last Modified: 2012-05-04
I need some help on this,
i need to read in text from a file called test.txt sort this info alphabetically and print the result out to report.txt

The input file would look like this;

when will we go to
the aid of the party


The output file should look like this;

aid
go
of
party
to
the
we
when
will

If a word appears twice it should only be printed once.

The problem is that i cannot use vectors, therefore it must be done using either binary trees or singly linked lists.

This is very important thanks in advance!!
0
Comment
Question by:PALKTA
  • 6
  • 4
  • 3
  • +3
17 Comments
 
LVL 1

Accepted Solution

by:
SimesA earned 400 total points
ID: 8063836
You didn't specify a language, so I used Delphi. I coded it as a linked list, so it should be easy to convert to the language of your choice.


unit Unit1;

interface

uses
  Windows, SysUtils, Classes, Controls, Forms, StdCtrls;

type
  TLink = class(TObject)
    Next: TLink;
    Word: string;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    ListBox1: TListBox;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    FStart: TLink;
    procedure ProcessFile(const filename: string);
    procedure ProcessRecord(rec: string);
    procedure ProcessWord(const word: string);
    procedure ClearList;
    procedure ListWords(const strings: TStrings);
  public
  end;

var
  Form1: TForm1;

implementation


{$R *.DFM}

procedure TForm1.ProcessWord(const word: string);
var
  lnk, newlnk, endlnk: TLink;
begin
  newlnk := TLink.Create;
  newlnk.Word := word;
  newlnk.Next := nil;
  if not Assigned(FStart) then
    FStart := newlnk
  else if word < FStart.Word then begin
    newlnk.Next := FStart;
    FStart := newlnk;
  end else begin
    lnk := FStart;
    endlnk := lnk;
    while Assigned(lnk) and (lnk.Word < word) do begin
      endlnk := lnk;
      lnk := lnk.Next;
    end;
    if Assigned(lnk) then begin
      if lnk.Word <> word then begin
        endlnk.Next := newlnk;
        newlnk.Next := lnk;
      end;
    end else
      endlnk.Next := newlnk;
  end;
end;

procedure TForm1.ClearList;
var
  lnk, nextlnk: TLink;
begin
  lnk := FStart;
  FStart := nil;
  while Assigned(lnk) do begin
    nextlnk := lnk.Next;
    lnk.Free;
    lnk := nextlnk;
  end;
end;

procedure TForm1.ListWords(const strings: TStrings);
var
  lnk: TLink;
begin
  strings.Clear;
  lnk := FStart;
  while Assigned(lnk) do begin
    strings.Add(lnk.Word);
    lnk := lnk.Next;
  end;
end;

procedure TForm1.ProcessRecord(rec: string);
var
  p: integer;
  word: string;
begin
  rec := lowercase(rec);
  while rec <> '' do begin
    // find the next word
    p := Pos(' ', rec);
    if p > 0 then begin
      word := trim(copy(rec, 1, p));
      delete(rec, 1, p);
      rec := trim(rec);
    end else begin
      word := rec;
      rec := '';
    end;

    // if we have a word, then process it
    if word <> '' then
      ProcessWord(word);
  end;
end;

procedure TForm1.ProcessFile(const filename: string);
var
  f: TextFile;
  rec: string;
begin
  ClearList;

  if FileExists(filename) then begin
    AssignFile(f, filename);
    Reset(f);
    try
      while not EOF(f) do begin
        ReadLn(f, rec);
        ProcessRecord(rec);
      end;
    finally
      CloseFile(f);
    end;
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  FStart := nil;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  ProcessFile('test.txt');
  ListWords(Listbox1.Items);
  label1.Caption := IntToStr(Listbox1.Items.Count);
end;

end.
0
 
LVL 21

Expert Comment

by:ziolko
ID: 8063922
Just another homework... SimesA posted Delphi code..if You want to use Delphi use TStringList Sort method already implemented there (QuickSort)
ziolko.
0
 
LVL 1

Expert Comment

by:SimesA
ID: 8064007
Hey even homework can be fun!

I purposely didn't use TStringList.Sort, since it wouldn't be possible to convert to other languages. Also Palkta requested linked list or binary trees.
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 21

Expert Comment

by:ziolko
ID: 8064128
I'm not saying its not fun :-) I still use BSTs :-)) not only funny but usefull.
ziolko.
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 8065744
Hope you get an A.

mlmcc
0
 

Author Comment

by:PALKTA
ID: 8066922
Sorry for not saying which language but it's c++

completly slipped my mind and i hope i get an A as well cas i need it!!!
0
 
LVL 1

Expert Comment

by:SimesA
ID: 8067886
Delphi -> C++ shouldn't be too hard for you!
0
 
LVL 8

Expert Comment

by:Exceter
ID: 8068472
>> Hey even homework can be fun!

Completing homework problems is a violation of the EE membership agreement. :-)

Exceter
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 8069024
Palkta
When you have the program translated and almost running check back.

mlmcc
0
 

Expert Comment

by:Ed2003
ID: 8072207
Sorry if this sounds really lame compared to the above (!) but how about importing the file into an MS Access table (you could use OLE) and running a query (select distinct ... order by ... )?  I reckon it would take fewer lines of code and might work fine.  I'm just lazy - I'd always use somebody else's database engine to do this stuff, rather than trying to code it myself!

Good luck

Ed
0
 
LVL 101

Expert Comment

by:mlmcc
ID: 8075868
All that work - a full running program and you give him a C?

mlmcc
0
 
LVL 1

Expert Comment

by:SimesA
ID: 8076169
<shrug>Some kids are *so* ungrateful</shrug>

0
 

Expert Comment

by:Ed2003
ID: 8087965
I don't suppose anybody's listening now, but I coded up my MS Access solution as an exercise and it works fine.  For me it's *considerably* more comprehensible than the accepted answer above!

This VB code behind a button:

Private Sub Command1_Click()

    Dim db As Database
    Dim tb As TableDef
    Dim fd As Field
    Dim ws As Workspace
    Dim con As DAO.Connection
    Dim qry As QueryDef
    Dim qry1 As QueryDef
    Dim rs As Recordset
    Dim intFile As Integer
    Dim strText As String
    Dim varText As Variant
    Dim intCounter As Integer
    Dim intFile1 As Integer
    Dim intFile2 As Integer
    Dim x As String
   
    'create MS Access DB, table and field
    Set db = CreateDatabase("MyDB", dbLangGeneral)
    Set tb = db.CreateTableDef("tb")
    Set fd = tb.CreateField("word", dbText)
    tb.Fields.Append fd
    db.TableDefs.Append tb
   
    'create queries
    Set qry = db.CreateQueryDef("qry")
    Set qry1 = db.CreateQueryDef("qry1", "select distinct word from tb order by word")
   
    'get text data from file
    intFile1 = FreeFile
    Open txtFile For Input As #intFile1
    Input #intFile1, strText
   
    'make array of words
    varText = Split(strText, " ")
   
    'insert words into table
    For intCounter = 0 To UBound(varText)
        qry.SQL = "insert into tb (word) values('" & varText(intCounter) & "')"
        qry.Execute
    Next
   
    'sort alphabetically
    Set rs = qry1.OpenRecordset
   
    'open new text file
    intFile2 = FreeFile
    Open "c:\myfile.txt" For Append As #intFile2
   
    Do While Not rs.EOF
        Print #intFile2, rs!word
        rs.MoveNext
    Loop
   
    db.Close
    Close #intFile1
    Close #intFile2
    Set db = Nothing
    x = CurDir
    Kill x & "/MyDB.mdb"
   
End Sub

You need DAO and Access in the project references.
Place a textbox on the form to key the path/filename of the input file.  The output file is hardcoded.

Oh well, I enjoyed writing it!

ED
0
 
LVL 1

Expert Comment

by:SimesA
ID: 8088218
Ed2003, I think you missed the point.

The point isn't to get a list of the words sorted into alphabetical order. It's an execise in solving a problem programatically, withing certain constraints.

So remove the Access DB, add some data storage (linked list or binary tree if possible) and sort the result. Oh, and do it all in C++.
0
 

Expert Comment

by:Ed2003
ID: 8089063
SimesA

I can see that you took it as such and, no doubt, produced an excellent solution from an intellectual standpoint.  However, there's nothing I can see in the original question to indicate that it's a test exercise, rather than a practical one.  In the real world, as I'm sure you're aware, we need to produce a cost-effective solution using the tools available.  One would not, therefore, normally choose to write pages of code, when optimised compiled solutions already exist that can be harnessed with a little effort.  I used VB because I know it - you may well be able to generate an equivalent solution in C even more economically.

Regards

Ed
0
 
LVL 1

Expert Comment

by:SimesA
ID: 8089152
Yep, you're absolutely right. I humbly apologise.
0
 

Expert Comment

by:Ed2003
ID: 8101917
Accepted, and sorry if I was a bit OTT there!
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When you see single cell contains number and text, and you have to get any date out of it seems like cracking our heads.
When you discover the power of the R programming language, you are going to wonder how you ever lived without it! Learn why the language merits a place in your programming arsenal.
Simple Linear Regression
Six Sigma Control Plans

571 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question