Ok here's the thing iv been reading on linked lists. Now i want to test my knowledge and see if ive grasped it fully. Can anyone give me a problem to do that deals with linked lists, appreciate your time.
Printable View
Ok here's the thing iv been reading on linked lists. Now i want to test my knowledge and see if ive grasped it fully. Can anyone give me a problem to do that deals with linked lists, appreciate your time.
Write a line-based text editor such as `ed`.
With the following "commands":
For example, (of course you'd need to print the lines when "p" is specified)Code:r [file] Read lines from a file
w [file] Write all the lines to a file
p [number, number] Print lines from number to number inclusive
q Quit
d [number, number Delete lines from number to number inclusive
a [number] Insert lines (from the user) at number
Of course use a linked-list on the back-end :pCode:r foo.txt
p 0,10
d 5,7
p 0,10
a 5
> (blank line to stop): new line
> new line 2
>
w new_foo.txt
q
Sounds lot a lot of work, lol, i was just thinking i dunno what else could be done. Im thnking of what else i could do. Last time we did like an online quiz imiator which read text files with the questions. But right now im blank as of what to do.Quote:
Originally Posted by zacs7
It's not a lot of work. Should take you about an hour...
And it deals with, traversing, inserting and deleting from linked lists.
kk, ill go read up on how that text editor works! Cuz i got no idea on it, :)Quote:
Originally Posted by zacs7
This is not "how a text editor works" - this is how something liek DOS's edlin or a simple unix text editor works - but not how a modern (text-mode) text editor works.Quote:
Originally Posted by Matus
--
Mats
Quote:
Originally Posted by matsp
Im tryin to find a visual on this thing, so i actually have an idea of how to do it.
So did you ever get anywhere on it?
I must say that either Zacs7 is a much faster programmer than me, or his/her estimates are out by at least a factor of 2. I've spent about 2 hours on it so far.
I haven't quite finished the delete operation (just as I was typing this, I realized that I needed to send "num2-num1" and not the other way around to delete the num1..num2 lines), but otherwise I've got mine done - it's currently about 350 lines of code.
It's still missing a whole heap of error checking and handling, and it should know if the file has been modified and if so ask if you want to save it when quitting, for example.
--
Mats
> I must say that either Zacs7 is a much faster programmer than me, or his/her estimates are out by at least a factor of 2. I've spent about 2 hours on it so far
Well it's not the first one :). I must admit my estimates were very out, it took me 45 minutes in Java using the built-in linked list. So I thought, hey it'd only take 15 minutes to whip up a linear linked list... guess not :p
And my use of the "about" qualifier gives me some wiggling room, of about an hour I'd say... =)
How about posting it when done? It would be interesting, for me at least, to see some code from a professional programmer. Even in spite of lacking error checking.Quote:
Originally Posted by matsp
I'd like to give Matus a chance to come up with something first - then I'll post mine.
Oh, and Zacs7: I'd be very happy to be out by a factor of 2 on an "about X" estimate. I've been known to be more like 10x out (in BOTH directions, to be honest).
--
Mats
Hey sorry took long to respond guys, actually that same day i was asking for probs, my prof dashed one at us, lol. So since i didnt really know how the editor works and was given one i havent really set any emphasis as yet. The proj i got was to tackle a lil database using circular double linked list, so currently on that right now.Quote:
Originally Posted by matsp
Sorry guys, but im gona try look it up as soon as im done with this one i have to complete.
Perhaps do this one first since it's a linear linked list (or can be anyway) :p
Quote:
Originally Posted by IceDane
Mats how about doing what IceDane said, I too would like to see the work of a Pro on here, I've gotten other stuff to do which is highly unlikely ill get to this, yet find out its working stuff in order for me to program. Im curious how this thing works, why not post it and lets see your stuff. So why not, IceDane agree's :), let us know...
This is by far not "professional level" code, but rather a quick hack to get the job done - it's about 2.5-3hrs worth of work.
Code:// ed.c
#include "list.h"
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
#define PATH_MAX 2000
typedef struct EdFile
{
List lines;
char *fname;
} EdFile;
/*
r [file] Read lines from a file
w [file] Write all the lines to a file
p [number, number] Print lines from number to number inclusive
q Quit
d [number, number Delete lines from number to number inclusive
a [number] Insert lines (from the user) at number
*/
const char *sep = " \t,";
void CleanUp(EdFile *file)
{
ListDeleteAll(&file->lines);
free(file->fname);
file->fname = 0;
}
char *GetLine(char *buffer, size_t size, FILE *f)
{
char *p;
size_t len;
p = fgets(buffer, (int)size, f);
if (p)
{
len = strlen(buffer);
if (buffer[len-1] == '\n')
{
buffer[len-1] = 0;
}
}
return p;
}
int GetFileNameOptional(char *buffer, char *fname, size_t len)
{
char *ptr = strtok(buffer+1, sep);
if (ptr != NULL && strlen(ptr) <= len)
{
strcpy(fname, ptr);
return 1;
}
return 0;
}
int GetFileName(char *buffer, char *fname, size_t len)
{
if (GetFileNameOptional(buffer, fname, len) > 0)
{
return 1;
}
printf("No filename given\n");
return 0;
}
int ArgToNum(const char *arg, int *num)
{
char *end;
if ((*num = strtol(arg, &end, 10)) == 0 || *end && !strchr(sep, *end))
{
printf("Invalid number (%s)\n", arg);
return 0;
}
return 1;
}
int GetNumArg(char *buffer, int *num1)
{
char *ptr;
ptr = strtok(buffer+1, sep);
if (ptr == NULL) return 0;
if (ArgToNum(ptr, num1))
{
return 1;
}
return 0;
}
int GetNumArgs(char *buffer, int *num1, int *num2)
{
char *ptr;
ptr = strtok(buffer+1, sep);
if (ptr == NULL || !ArgToNum(ptr, num1))
{
return 0;
}
ptr = strtok(NULL, sep);
if (ptr == NULL || !ArgToNum(ptr, num2))
{
return 1;
}
return 2;
}
void ReadFromFile(EdFile *file, const char *name)
{
FILE *f;
char buffer[BUFSIZ];
f = fopen(name, "r");
if (!f)
{
printf("Could not open %s\n", name);
return;
}
file->fname = strdup(name);
while(GetLine(buffer, sizeof buffer, f))
{
ListAppend(&file->lines, buffer);
}
fclose(f);
}
void WriteToFile(EdFile *file, const char *name)
{
FILE *f;
Node *p;
f = fopen(name, "w");
if (!f)
{
printf("Could not open %s\n", name);
return;
}
for(p = file->lines.head; p; p = p->next)
{
fputs(p->text, f);
fputs("\n", f);
}
fclose(f);
}
Node* LocateLine(EdFile *file, int lineNo)
{
Node *p;
int i;
for(p = file->lines.head, i = 0; p && i < lineNo-1; p = p->next, i++);
return p;
}
void Print(EdFile *file, int num1, int num2)
{
int i = num1;
Node *p = LocateLine(file, num1);
for(; p && i <= num2; p = p->next, i++)
{
puts(p->text);
}
}
void Append(EdFile *file, int num1)
{
char buffer[BUFSIZ];
Node *p = NULL;
if (num1 > 1)
{
p = LocateLine(file, num1-1);
}
while(GetLine(buffer, sizeof buffer, stdin) && strlen(buffer))
{
if (num1 > 1 || p)
{
p = ListInsertAfter(&file->lines, p, buffer);
}
else
{
ListInsertAtHead(&file->lines, buffer);
p = file->lines.head;
}
}
}
void Delete(EdFile *file, int num1, int num2)
{
Node *p = LocateLine(file, num1);
ListDeleteNodesFrom(&file->lines, p, num2-num1);
}
int main()
{
char buffer[BUFSIZ];
char fname[PATH_MAX];
int num1, num2;
EdFile file;
ListInit(&file.lines);
for(;;)
{
num1 = 0;
num2 = INT_MAX;
printf(">");
GetLine(buffer, sizeof(buffer), stdin);
switch(buffer[0])
{
case 'r':
if (GetFileName(buffer, fname, sizeof(fname)) > 0)
{
ReadFromFile(&file, fname);
}
break;
case 'w':
if (GetFileNameOptional(buffer, fname, sizeof(fname)) > 0)
{
WriteToFile(&file, fname);
}
else
{
WriteToFile(&file, file.fname);
}
break;
case 'p':
GetNumArgs(buffer, &num1, &num2);
Print(&file, num1, num2);
break;
case 'a':
num1 = INT_MAX;
GetNumArg(buffer, &num1);
Append(&file, num1);
break;
case 'd':
{
int n = GetNumArgs(buffer, &num1, &num2);
if (n != 2)
{
printf("Must specify first and last line to delete\n");
}
Delete(&file, num1, num2);
}
break;
case 'q':
CleanUp(&file);
return 0;
default:
printf("Invalid command\n");
break;
}
}
}
Code:// list.c
#include "list.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
void ListInit(List *l)
{
l->tail = l->head = NULL;
}
static Node *NewNode(const char *t)
{
Node *p = malloc(sizeof(Node));
if (p)
{
p->text = malloc(strlen(t) + 1);
if (p->text)
{
strcpy(p->text, t);
p->next = NULL;
return p;
}
}
printf("Error: Out of memory\n");
return NULL;
}
void ListAppend(List *l, const char *t)
{
Node *p = NewNode(t);
if (!l->tail)
{
l->head = p;
}
else
{
l->tail->next = p;
}
l->tail = p;
}
Node *ListInsertAfter(List *l, Node *p, const char *t)
{
if (p == NULL)
{
ListAppend(l, t);
return p;
}
else
{
Node *n;
n = NewNode(t);
n->next = p->next;
p->next = n;
return n;
}
}
void ListInsertAtHead(List *l, const char *t)
{
Node *n;
n = NewNode(t);
n->next = l->head;
l->head = n;
}
Node *ListDeleteOneNode(List *l, Node *p)
{
Node *next = p->next;
if (l->head == p)
{
l->head = next;
}
else
{
Node *pp;
for(pp = l->head; pp && pp->next != p; pp = pp->next);
pp->next = next;
if (l->tail == p)
l->tail = pp;
}
free(p);
return next;
}
void ListDeleteNodesFrom(List *l, Node *p, int n)
{
int i;
for(i = 0; i <= n && p; i++)
{
p = ListDeleteOneNode(l, p);
}
}
void ListDeleteAll(List *l)
{
Node *p, *q;
for(p = l->head; p; p = q)
{
q = p->next;
free(p->text);
free(p);
}
l->head = l->tail = NULL;
}
Ideas for improvements:Code:#ifndef LIST_H
#define LIST_H
typedef struct node
{
char *text;
struct node *next;
} Node;
typedef struct list
{
Node *head;
Node *tail;
} List;
void ListInit(List *l);
void ListAppend(List *l, const char *t);
Node *ListInsertAfter(List *l, Node *p, const char *t);
void ListInsertAtHead(List *l, const char *t);
void ListDeleteNodesFrom(List *l, Node *p, int n);
Node *ListDeleteOneNode(List *l, Node *p);
void ListDeleteAll(List *l);
#endif
* Identify if the file has changed and ask user for confirmation if they want to quit with modified file.
* Use double linked lists to make deleting simpler/faster.
* Search/replace.
--
Mats
Wow thanks matsp,
I do have a question
Why the cast? size was size_t.Code:p = fgets(buffer, (int)size, f);
Yea, thanks to matsp too, u know i dont think id have been able to come up with such a code. Ill be taking a look as soon as i get home. I know ill definately learn something from it :)Quote:
Originally Posted by zacs7
Right now? No idea, really - I'm pretty sure it's not needed. Probably a consequence of some change that I never fully finalized...Quote:
Originally Posted by zacs7
--
Mats