In insertFirst() we begin by creating the new link using the data passed as arguments.
Then we change the link references as we just noted:
// insert at start of list
void insertFirst(liste*l,int x)
{ // make new link
Liste*k=l,*newel=new liste;
Newel->iData=x;iData->next=k;l=newel;}
The --> arrows in the comments in the last two statements mean that a link (or the first field)
connects to the next (downstream) link. (In doubly linked lists well see upstream connections as
well, symbolized by <-- arrows.) Compare these two statements with Figure 3.
Make sure you understand how the statements cause the links to be changed, as shown in the
figure next slide.
This kind of reference manipulation is the heart of linked-list algorithms.
The deleteFirst() function is the reverse of insertFirst(). It disconnects the first link by
rerouting first to point to the second link. This second link is found by looking at the next field in
the first link:
liste* deleteFirst(liste*l) // delete first item
{ liste*k=l; // (assumes list not empty)
if(l==NULL){cout<<List is empty;}
else {l=l->next; //create link with the second node
delete(k); // delete first element
return l;} // return deleted link
The delete() is all you need to remove the first link from the list. We choose to also return the
link, for the convenience of the user of the linked list, so we create the link before deleting it
and return the final liste l. Figure 4 shows how first is rerouted to delete the node.
Length of the list.To display the list, you start at first and follow the chain of references
from link to link. A variable current points to (or technically refers to) each link in turn. It starts
off pointing to first, which holds a reference to the first link.
The function of lengthListe() will find the number of nodes in a linked list:
int lengthList(liste*l) {
int count=0;liste*k=l;
if(l==NULL){count=0;}else{//l is empty
while(k != null)
count ++; //variable count increment
k=k->next;}
return count;} //return count which is the length of list
STACK
Stack createS(max_stack_size) ::=
#define MAX_STACK_SIZE 100 /* maximum stack size */
typedef struct {
int key;
/* other fields */
} element;
element stack[MAX_STACK_SIZE];
int top = -1;
Boolean isEmpty(Stack) ::= top< 0;
Boolean isFull(Stack) ::= top >= MAX_STACK_SIZE-1;
---PUSH
void push(int *top, element item)
{
/* add an item to the global stack */
if (*top >= MAX_STACK_SIZE-1) {
stack_full( );
return;
}
stack[++*top] = item;
}
----POP----
element pop(int *top)
{
/* return the top element from the stack */
if (*top == -1)
return stack_empty( ); /* returns and error key */
return stack[(*top)--];
}
----------------------------------------------------------------
QUEUES
Queue createQ(max_queue_size) ::=
# define MAX_QUEUE_SIZE 100/* Maximum queue size */
typedef struct {
int key;
/* other fields */
} element;
element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;
Boolean isEmpty(queue) ::= front == rear
Boolean isFullQ(queue) ::= rear == MAX_QUEUE_SIZE-1
Enqueue
void enqueue(int *rear, element item)
{
/* add an item to the queue */
if (*rear == MAX_QUEUE_SIZE_1) {
queue_full( );
return;
}
queue [++*rear] = item;
}
Dequeue
element dequeue(int *front, int rear)
{
/* remove element at the front of the queue */
if ( *front == rear)
return queue_empty( ); /* return an error key */
return queue [++ *front];
}
-----------------------------------------------------------------------------------------------------------
RECURSION
A) // return the sum of all the numbers between 1 and value (inclusive)
int sumTo(int value)
{
if (value <= 0)
return 0; // base case (termination condition)
else if (value == 1)
return 1; // base case (termination condition)
else
return sumTo(value - 1) + value; // recursive function call
B)
int fibonacci(int number)
{
if (number == 0)
return 0; // base case (termination condition)
if (number == 1)
return 1; // base case (termination condition)
return fibonacci(number-1) + fibonacci(number-2);
}
// And a main program to display the first 13 Fibonacci numbers
int main()
{
for (int count=0; count < 13; ++count)
std:: cout << fibonacci(count) << " ";
return 0;
}
1. C) float RecursiveAvg(float A[], int i, int n)
2. {
3. //Base case
4. if (i == n-1) return A[i]/n;
5.
6. return A[i]/n + RecursiveAvg(A, i + 1, n);
7. }
8.
9. //Main function
10. void main()
11. {
12. float A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
13.
14. cout << RecursiveAvg(A, 0, 10) << endl; }
15. COUNT EVEN NUMBERS
16. public static int EvenNum(int[] arr, int index)
17. {
18. if (index == arr.length) return 0; // Stop recursion
19. //return (arr[index] % 2 == 0 ? 1 : 0) + EvenNum(arr, index + 1);
20. // or....
21. int result;
22. if ((arr[index] % 2) == 0) { // Is even
23. result = 1;
24. }
25. else { // Is odd
26. result = 0;
27. }
28. return result + EvenNum(arr, index + 1);
29. }
30.
31. public static void main(final String... args)
32. {
33. // Start with index = 0
34. System.out.println(EvenNum(new int[]{1,2,3,4,5}, 0));
35. }
SORTING-BUBBLE
void bubble_sort (int arr[], int n)
for (int i = n-1; i>1; i--)
for (int j = 0; j <i ;j++)
if (arr[j] > arr[j + 1])
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
SELECTION SORTING
void selection_sort (int ar[], int n)
int min_ele_loc;
for (int i = 0; i < n-1; i++)
//Find minimum element in the unsorted array
//Assume it's the first element
min_ele_loc = i;
//Loop through the array to find it
for (int j = i + 1; j < n; j++)
if (ar[j] < ar[min_ele_loc])
//Found new minimum position, if present
min_ele_loc = j;
}
//Swap the values
swap (ar[i], ar[min_ele_loc]);
INSERTION
void insertion_sort(int arr[],int n){
int i,j,temp;
for (j = 1; j < n; j++) {//start from second element
temp=arr[j];
i=j;
while (i > 0 && arr[i - 1] > temp) {
arr[i]=arr[i-1];
i--;
arr[i]=temp;
