Thread: Link Lists. I need Some Problem From u Guys to do!

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":

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

For example, (of course you'd need to print the lines when "p" is specified)

Code:

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

Of course use a linked-list on the back-end

Originally Posted by zacs7

Write a line-based text editor such as `ed`.


Of course use a linked-list on the back-end

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.

It's not a lot of work. Should take you about an hour...

And it deals with, traversing, inserting and deleting from linked lists.

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,

Originally Posted by Matus

kk, ill go read up on how that text editor works! Cuz i got no idea on it,

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.

--
Mats

Originally Posted by matsp

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.

--
Mats

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

And my use of the "about" qualifier gives me some wiggling room, of about an hour I'd say... =)

Originally Posted by matsp

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

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.

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

Originally Posted by matsp

So did you ever get anywhere on it?

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.

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)

Originally Posted by IceDane

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.

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;
}

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

Ideas for improvements:
* 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