======Singly Linked List======
This code is available on Lab46 under the **/var/public/data/fall2012/linkedlist1/** directory in the various source files found therein.
I took the code from class and split it up to be a multi-file C project. I even included a **Makefile** so you can build the whole thing with **make**.
=====linkedlist.h=====
Set up the structure and list function prototypes.
#ifndef __LINKED_LIST_H
#define __LINKED_LIST_H
#include
struct node {
char value;
struct node *next;
};
typedef struct node Node;
char showlist(Node *);
Node * getpos(Node *, char);
Node * appendnode(Node *, Node *, Node *);
Node * insertnode(Node *, Node *, Node *);
Node * removenode(Node *, Node *, Node *);
#endif
=====append.c=====
**appendnode()** is responsible for adding a new node after a specified node. We'll see it used twice- during the initial list building, and later on in a more selective way.
#include "linkedlist.h"
Node * appendnode(Node *begin, Node *pos, Node *newnode)
{
if ((begin != NULL) && (pos != NULL) && (newnode != NULL))
{
newnode -> next = pos -> next;
pos -> next = newnode;
}
else if (begin == NULL)
{
begin = pos = newnode;
}
return(begin);
}
=====showlist.c=====
Display the list, somewhat in set/tuple notation, along with selection markers.
#include
#include
#include "linkedlist.h"
char showlist(Node *mynode)
{
Node *temp = mynode;
char i = 0;
printf("{ ");
while(temp != NULL)
{
printf("([%hhd], %hhd), ", i, temp -> value);
temp = temp -> next;
i = i + 1;
}
printf("NULL }\n");
return(i - 1);
}
=====getpos.c=====
Locate node at indicated position and return a pointer to that node.
#include "linkedlist.h"
Node * getpos(Node *begin, char pos)
{
Node *temp = begin;
char i;
for(i = 0; i < pos; i++)
temp = temp -> next;
return(temp);
}
=====main.c=====
Sample linked list application. Pulls it all together.
#include
#include "linkedlist.h"
int main()
{
Node *start, *tmp, *tmp2;
char input, i;
start = tmp = tmp2 = NULL;
printf("Phase 1: Building a list\n");
printf("------------------------\n");
printf("Enter a value (0-127) [-1 to quit]: ");
scanf("%hhd", &input);
while (input != -1)
{
tmp2 = (Node *) malloc (sizeof(Node));
tmp2 -> value = input;
tmp2 -> next = NULL;
start = appendnode(start, tmp, tmp2);
if (tmp == NULL)
tmp = start;
if (tmp -> next != NULL)
tmp = tmp -> next;
printf("Enter a value (0-127) [-1 to quit]: ");
scanf("%hhd", &input);
}
printf("\n\nPhase 2: Displaying the list\n");
printf("-----------------------------\n");
i = showlist(start);
printf("\n\nPhase 3: Selecting a Node to Append After\n");
printf("---------------------------------------------\n");
do {
printf("Select a node # to append after (0-%hhd): ", i);
scanf("%hhd", &input);
tmp = getpos(start, input);
} while (tmp == NULL);
printf("\n\nPhase 4: Append New Node After Specified Node\n");
printf("-------------------------------------------------\n");
printf("Enter a value (0-127) for new node: ");
scanf("%hhd", &input);
tmp2 = (Node *) malloc (sizeof(Node));
tmp2 -> value = input;
tmp2 -> next = NULL;
start = appendnode(start, tmp, tmp2);
printf("\n\nPhase 5: Displaying the list\n");
printf("-----------------------------\n");
showlist(start);
return(0);
}
=====Makefile=====
To assist with building. Just type **make**. **make clean** will clear out all compiled objects. **make debug** will build with debugging support.
CFLAGS = -Wall
INC =
CC = gcc $(CFLAGS) $(INC)
SRC = $(shell /bin/ls -1 *.c)
OBJ = $(SRC:.c=.o)
BIN = linkedlistprog
all: $(SRC) $(OBJ) $(BIN)
debug: CC += -DDEBUG -g
debug: DEBUG = debug
debug: $(SRC) $(OBJ) $(BIN)
linkedlistprog:
ifneq ($(MAKECMDGOALS),debug)
@printf "[B] %-20s ... " "$(BIN)"
@$(CC) -o $(BIN) $(OBJ) && echo "OK" || echo "FAIL"
else
$(CC) -o $(BIN) $(OBJ)
endif
.c.o:
ifneq ($(MAKECMDGOALS),debug)
@printf "[B] %-20s ... " "$<"
@$(CC) -c $< && echo "OK" || echo "FAIL"
else
$(CC) -c $<
endif
copy:
mkdir -p ~/src/data/linkedlist1
cp -v /var/public/data/fall2012/linkedlist1/* ~/src/data/linkedlist1/
clean:
rm -f $(OBJ) $(BIN) core
=====Sample Run=====
Following will be a demonstration of compiling and running this program.
====Obtaining a copy====
It would be worthwhile to have your own copy of this code to make changes to. Copy it into your **~/src/data/** directory as follows:
lab46:~$ ci /var/public/data/fall2012/linkedlist1
lab46:/var/public/data/fall2012/linkedlist1$ make copy
mkdir -p ~/src/data/linkedlist1
cp -v /var/public/data/fall2012/linkedlist1/* ~/src/data/linkedlist1/
`/var/public/data/fall2012/linkedlist1/Makefile' -> `/home/wedge/src/data/linkedlist1/Makefile'
`/var/public/data/fall2012/linkedlist1/append.c' -> `/home/wedge/src/data/linkedlist1/append.c'
`/var/public/data/fall2012/linkedlist1/getpos.c' -> `/home/wedge/src/data/linkedlist1/getpos.c'
`/var/public/data/fall2012/linkedlist1/insert.c' -> `/home/wedge/src/data/linkedlist1/insert.c'
`/var/public/data/fall2012/linkedlist1/linkedlist.h' -> `/home/wedge/src/data/linkedlist1/linkedlist.h'
`/var/public/data/fall2012/linkedlist1/main.c' -> `/home/wedge/src/data/linkedlist1/main.c'
`/var/public/data/fall2012/linkedlist1/remove.c' -> `/home/wedge/src/data/linkedlist1/remove.c'
`/var/public/data/fall2012/linkedlist1/showlist.c' -> `/home/wedge/src/data/linkedlist1/showlist.c'
lab46:/var/public/data/fall2012/linkedlist1$
====Change to your local copy====
lab46:/var/public/data/fall2012/linkedlist1$ cd ~/src/data/linkedlist1
lab46:~/src/data/linkedlist1$
====Compiling====
Let's build it:
lab46:~/src/data/linkedlist1$ make
[B] append.c ... OK
[B] getpos.c ... OK
[B] insert.c ... OK
[B] main.c ... OK
[B] remove.c ... OK
[B] showlist.c ... OK
[B] linkedlistprog ... OK
lab46:~/src/data/linkedlist1$
====Running====
And now, a sample execution:
lab46:~/src/data/linkedlist1$ ./linkedlistprog
Phase 1: Building a list
------------------------
Enter a value (0-127) [-1 to quit]: 2
Enter a value (0-127) [-1 to quit]: 4
Enter a value (0-127) [-1 to quit]: 6
Enter a value (0-127) [-1 to quit]: 8
Enter a value (0-127) [-1 to quit]: 10
Enter a value (0-127) [-1 to quit]: 12
Enter a value (0-127) [-1 to quit]: -1
Phase 2: Displaying the list
-----------------------------
{ ([0], 2), ([1], 4), ([2], 6), ([3], 8), ([4], 10), ([5], 12), NULL }
Phase 3: Selecting a Node to Append After
---------------------------------------------
Select a node # to append after (0-5): 2
Phase 4: Append New Node After Specified Node
-------------------------------------------------
Enter a value (0-127) for new node: 7
Phase 5: Displaying the list
-----------------------------
{ ([0], 2), ([1], 4), ([2], 6), ([3], 7), ([4], 8), ([5], 10), ([6], 12), NULL }
lab46:~/src/data/linkedlist1$