Lecture note: Linked List I

Please get it from my site:
http://sites.google.com/site/ksopheaktra/


Have a good day,

How to config Internet Connection Sharing with Windows XP-2

This is a good link:
http://www.rogershelp.com/yahoo/connection/homenetworking/winxpics.html

For further information, please googling with keyword "Internet Connection Sharing Windows XP"

Good luck,

Links for Linux Command

1. Linux Command Directory
http://onlamp.com/linux/cmd/
2. Linux Command for Practise:
http://www.pixelbeat.org/cmdline.html
3. Bash commans
http://www.ss64.com/bash/

Dynamic Linked List

# include< stdio.h>
# include< conio.h>
# include< malloc.h>
# include< stdlib.h>
struct node
{ int data;
struct node *link;
};
void append(struct node **,int);
void in_begin(struct node **,int);
void del(struct node **,int);
void in_middle(struct node **,int,int);
int count(struct node *);
void display(struct node *);

void main()
{ struct node *p; /* p can be said as the head or a start ptr */
p=NULL;
/* Printing the menu */
int num,loc;
char choice;
do
{
clrscr();
printf("PROGRAM TO IMPLEMENT SINGLY LINKED LIST ");
printf("\n=====================================");
printf("\n\n1.Create \\ Appending The List");
printf("\n2.Insert Node At Begining");
printf("\n3.Insert Node In Middle");
printf("\n4.Deleting a Node");
printf("\n5.Counting The No Of Nodes");
printf("\n6.Displaying the list");
printf("\n7.Exit");
oper:
gotoxy(1,15);printf(" ");
gotoxy(1,11);printf("\n\nEnter ur Choice : ");
choice=getch();
switch(choice)
{
case '1':
char ans;
do
{
printf("Enter any number : ");scanf("%d",&num);
append(&p,num);
printf("Enter more (y/n) :");
fflush(stdin);
ans=getchar();
}while(ans !='n');
break;
case '2':
printf("Enter The Data : ");scanf("%d",&num);
in_begin(&p,num);
break;

case '3':
printf("\nEnter The Position :");scanf("%d",&loc);
printf("\nEnter The Data : ");scanf("%d",&num);
in_middle(&p,loc,num);
break;

case '4':
printf("\nEnter The Data u Want To Delete : ");scanf("%d",&num);
del(&p,num);
break;
case '5':
printf("\nThe No Of Nodes Are %d",count(p));
getch();
break;
case '6':
display(p);
getch();
break;
case '7':
printf("\n\nQuiting.......");
getch();
exit(0);
break;
default:
gotoxy(1,15);printf("Invalid choice.Please Enter Correct Choice");
getch();
goto oper;
}

}while(choice !=7);

}

void append(struct node **q,int num)
{ struct node *temp,*r;
temp = *q;
if(*q==NULL)
{ temp = (struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->link=NULL;
*q=temp;
}
else
{ temp = *q;
while(temp->link !=NULL)
temp=temp->link;
r = (struct node *)malloc(sizeof(struct node));
r->data=num;
r->link=NULL;
temp->link=r;
}
}

void display(struct node *q)
{ if(q==NULL)
{ printf("\n\nEmpty Link List.Can't Display The Data");
getch();
goto last;
}
while(q!=NULL)
{ printf("\n%d",q->data);
q=q->link;
}
last:
}

int count(struct node *q)
{ int c=0;
if(q==NULL)
{ printf("Empty Link List.\n");
getch();
goto last;
}
while(q!=NULL)
{ c++;
q=q->link;
}
last:
return c;
}

void in_begin(struct node **q,int num)
{ struct node *temp;
if(*q==NULL)
{ printf("Link List Is Empty.Can't Insert.");
getch();
goto last;
}
else
{ temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
temp->link=*q;
*q=temp; /* pointing to the first node */
}
last:
getch();
}

void in_middle(struct node **q,int loc,int num)
{ struct node *temp,*n;
int c=1,flag=0;
temp=*q;
if(*q==NULL)
{ printf("\n\nLink List Is Empty.Can't Insert.");
getch();
goto last;
}
else
while(temp!=NULL)
{ if(c==loc)
{ n = (struct node *)malloc(sizeof(struct node));
n->data=num;
n->link=temp->link;
temp->link=n;
flag=1;
}
c++;
temp=temp->link;
}
if(flag==0)
{ printf("\n\nNode Specified Doesn't Exist.Cant Enter The Data");
getch();
}
else
{ printf("Data Inserted");
getch();
}
last:
getch();
}

void del(struct node**q,int num)
{ if(*q==NULL)
{ printf("\n\nEmpty Linked List.Cant Delete The Data.");
getch();
goto last;
}
else
{
struct node *old,*temp;
int flag=0;
temp=*q;
while(temp!=NULL)
{ if(temp->data==num)
{ if(temp==*q) /* First Node case */
*q=temp->link; /* shifted the header node */
else
old->link=temp->link;
free(temp);
flag=1;
}
else
{ old=temp;
temp=temp->link;
}
}
if(flag==0)
printf("\nData Not Found...");
else
printf("\nData Deleted...Tap a key to continue");
getch();
}
last:
getch();
}

Algorithm for Array Linked List (new)

#include< stdio.h>
#include< conio.h>
#include< stdlib.h>
#define Max_Array 50

struct array_list {

int info, next;
};

struct array_list node[Max_Array];

//Define as global variable
int avail;

/*Initially, all nodes are unused, since no lists have yet been
formed. Therefore, they must all be placed on the available list.
If the global variable avail is used to point to the available list,
we may initially organize that list as follows */
void available() {
avail=0;
for (int i=avail; i > Max_Array -1; i++)
node[i].next=i+1;
node[Max_Array-1].next=-1;
}

/*Getnode is a function that removes a node from the available list and returns
a pointer to it */
int getnode() {
int p;
if (avail==-1) {
printf("Overflow\n");
exit(1);
}
p=avail;
avail=node[avail].next;
return (p);
}/* End of getnode */

/*Freenode is function that accepts a pointer to a node and return that node to
the available list */

int freenode(int p) {
node[p].next=avail;
avail=p;
return;
} /* end of freenode */

/*Besides the primitive operations, routine insafter(insert after) is a function
that accepts a pointer p to a node and an item x as parameters. it first ensures
that p is not full and then insert x into a nodefollowing the node pointed to by p */
int insafter(int p, int x) {
int q;
if (p==-1) {
printf("Void insertion\n");
return;
}
q=getnode();
node[q].info=x;
node[q].next=node[p].next;
node[p].next=q;
return;
} /*end insafter */

/*Routine delafter(p,px), called by the statement delafter(p, &x), deletes the
node following node(p) and stores its contents in x. */
int delafter(int p, int *px) {
int q;
if ((p==-1)||(node[p].next==-1)) {
printf("Void deletion\n");
return;
}
q=node[p].next;
*px=node[q].info;
node[p].next=node[q].next;
freenode(q);
return;
} /*end of delafter */
/* Before calling insafter we must be sure that p is not null. Before calling
delafter we must be sure that neither p nor node[9].next is null */

/* For main function, you may try by getting from circular queue, try it then
see what happen */

//Have a good day

Algorithm for Array Linked List

Good links for lesson: http://en.wikipedia.org/wiki/Linked_list

Please vote for Cambodia

Please vote for the Cambodian Hero in top 10 CNN Hero
http://heroes.cnn.com/default.asp

Code for simple Dynamic Linked List

/* Program to illustrate traversing a list */
#include 
struct list {
int         value;
struct list *next;
};

main()
{
struct list n1, n2, n3, n4;
struct list *list_pointer = &n1;

n1.value = 100;
n1.next = &n2;
n2.value = 200;
n2.next = &n3;
n3.value = 300;
n3.next = &n4;
n4.value = 400;
n4.next = 0;


while( list_pointer != 0 )  {
printf("%d\n", list_pointer->value);
list_pointer = list_pointer->next;
}
}
-----------------------
Below is the more workable one, please try:)
http://www.idevelopment.info/data/Programming/data_structures/c/
LinkedList/list.c

Code for circular queue in structure type

#include
#include
#include
#define Max_Queue 50
typedef struct Queue {
int r, f;
int data[Max_Queue];
}q;
int qempty( int count) {
return (count==0?1:0);
}

int qfull (int count) {
return (count==Max_Queue?1:0);
}

void insert_rear(int item, Queue *q, int *count) {
if (qfull(*count)) printf ("Queue is overflow\n");
else {
q->r=(q->r+1) % Max_Queue;
q->data[q->r]=item;
*count += 1;
}
}

void delete_front(Queue *q, int *count) {
if (qempty(*count)) printf ("Queue is underflow\n");
else {
printf("The delete element is %d \n", q->data[q->f]);
q->f=(q->f+1) % Max_Queue;
*count -=1;
}
}

void display (Queue *q, int count) {
int i, j;
if (qempty(count)) printf (" Queue is empty \n");
else {
printf(" Content of Queue is \n");
i=q->f;
for (j=1; j<=count; j++) {
printf ("\t%d", q->data[i]);
i= (i+1) % Max_Queue;
}
printf ("\n");
}
}

void main () {
Queue *q;
int choice, item, count;
q->f=0; q->r=-1; count=0;

for(;;) {
printf(" 1: Insert 2: Delete\n");
printf(" 3: Display 4: Exit \n");
printf(" Enter the choice: ");
scanf(" %d", &choice);
switch(choice) {
case 1:
printf (" Enter the item to be inserted: ");
scanf (" %d", &item);
insert_rear(item, q, &count);
break;
case 2:
delete_front(q, &count);
break;
case 3:
display(q,count);
break;
default:
exit(0);
}
}
}

Code for Stack and Queue

This is code for Stack:
-----------------
#include
#define Max_Stack 50


This is code for Circular Queue:
------------------
#include
#include
#include
#define Max_Queue 50

int qempty( int count) {
return (count==0?1:0);
}

int qfull (int count) {
return (count==Max_Queue?1:0);
}

void insert_rear(int item, int q[], int *r, int *count) {
if (qfull(*count)) printf ("Queue is overflow\n");
else {
*r=(*r+1) % Max_Queue;
q[*r]=item;
*count += 1;
}
}

void delete_front(int q[], int *f, int *count) {
if (qempty(*count)) printf ("Queue is underflow\n");
else {
printf("The delete element is %d \n", q[*f]);
*f=(*f+1) % Max_Queue;
*count -=1;
}
}

void display (int q[], int f, int count) {
int i, j;
if (qempty(count)) printf (" Queue is empty \n");
else {
printf(" Content of Queue is \n");
i=f;
for (j=1; j<=count; j++) {
printf ("\t%d", q[i]);
i= (i+1) % Max_Queue;
}
printf ("\n");
}
}

void main () {
int choice, item, f, r, count, q[20];
f=0; r=-1; count=0;

for(;;) {
printf(" 1: Insert 2: Delete\n");
printf(" 3: Display 4: Exit \n");
printf(" Enter the choice: ");
scanf(" %d", &choice);
switch(choice) {
case 1:
printf (" Enter the item to be inserted: ");
scanf (" %d", &item);
insert_rear(item, q, &r, &count);
break;
case 2:
delete_front(q, &f, &count);
break;
case 3:
display(q,f,count);
break;
default:
exit(0);
}
}
}