?
Solved

text file sorting

Posted on 2003-03-04
17
Medium Priority
?
221 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Percona Live Europe 2017 | Sep 25 - 27, 2017

The Percona Live Open Source Database Conference Europe 2017 is the premier event for the diverse and active European open source database community, as well as businesses that develop and use open source database software.

 
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

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

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

Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
A short article about problems I had with the new location API and permissions in Marshmallow
Six Sigma Control Plans
Progress
Suggested Courses

800 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