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

This is a discussion on Link Lists. I need Some Problem From u Guys to do! within the C Programming forums, part of the General Programming Boards category; Ok here's the thing iv been reading on linked lists. Now i want to test my knowledge and see if ...

  1. #1
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235

    Talking 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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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
    Last edited by zacs7; 11-10-2008 at 04:37 PM.

  3. #3
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by zacs7 View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  4. #4
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    It's not a lot of work. Should take you about an hour...

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

  5. #5
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by zacs7 View Post
    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,
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Matus View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by matsp View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > 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... =)

  10. #10
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by matsp View Post
    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.
    "What's up, Doc?"
    "'Up' is a relative concept. It has no intrinsic value."

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by matsp View Post
    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.
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  13. #13
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Perhaps do this one first since it's a linear linked list (or can be anyway)

  14. #14
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by IceDane View Post
    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...
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I'm confused about link lists (again)
    By JFonseka in forum C Programming
    Replies: 4
    Last Post: 06-13-2008, 09:13 PM
  2. Dbl Link Problem
    By hoangvo in forum C++ Programming
    Replies: 6
    Last Post: 07-29-2005, 11:44 PM
  3. Trouble modifing my program from templates to link lists
    By PaulTodd03 in forum C++ Programming
    Replies: 1
    Last Post: 03-26-2005, 02:15 PM
  4. Replies: 0
    Last Post: 07-22-2003, 12:29 PM
  5. linked lists problem
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 06-17-2002, 11:55 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21