Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit3dc2ecc

Browse files
author
Christian Bender
authored
Merge pull requestTheAlgorithms#123 from agnimish/master
3 very useful codes added
2 parents7efed28 +fade142 commit3dc2ecc

File tree

3 files changed

+242
-0
lines changed

3 files changed

+242
-0
lines changed
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
#include<stdio.h>
2+
#include<stdlib.h>
3+
structnode{
4+
intdata;
5+
structnode*next;
6+
};
7+
8+
structnode*head1=NULL;
9+
structnode*head2=NULL;
10+
11+
///// MAIN ALGORITHMIC FUNCTION to MERGE the two input linked lists ///////
12+
13+
voidmerge()
14+
{
15+
structnode*temp1=head1;
16+
structnode*temp2=head2;
17+
18+
structnode*holder1=NULL;
19+
structnode*holder2=NULL;
20+
//Temporary pointer variables to store the address of next node of the two input linked list
21+
22+
while(temp1!=NULL&&temp2!=NULL)
23+
{
24+
holder1=temp1->next;
25+
//Storing the address of next node of first linked list
26+
temp1->next=temp2;
27+
//Making the first node of first linked list point to first node of second linked list
28+
29+
if(holder1!=NULL){
30+
//Making the first node of second linked list point to second node of first linked list
31+
holder2=temp2->next;
32+
temp2->next=holder1;
33+
}
34+
temp1=holder1;
35+
temp2=holder2;
36+
//Updating the address location of two pointer variables temp1 and temp2
37+
}
38+
}
39+
40+
voidprintlist(structnode*temp){
41+
printf("%d",temp->data);
42+
temp=temp->next;
43+
while(temp!=NULL){
44+
printf("->%d",temp->data);
45+
temp=temp->next;
46+
}
47+
printf("\n");
48+
}
49+
50+
intmain()
51+
{
52+
// Linked List 1: 1->3->5->7 : Linked List 2: 2->4->6
53+
// making lists
54+
structnode*one= (structnode*)malloc(sizeof(structnode));
55+
structnode*two= (structnode*)malloc(sizeof(structnode));
56+
structnode*three= (structnode*)malloc(sizeof(structnode));
57+
structnode*four= (structnode*)malloc(sizeof(structnode));
58+
structnode*five= (structnode*)malloc(sizeof(structnode));
59+
structnode*six= (structnode*)malloc(sizeof(structnode));
60+
structnode*seven= (structnode*)malloc(sizeof(structnode));
61+
//Seven nodes are created
62+
63+
head1=one;
64+
head2=two;
65+
//head1 points to first node of first linked list
66+
//head2 points to first node of second linked list
67+
68+
one->data=1;
69+
one->next=three;
70+
71+
two->data=2;
72+
two->next=four;
73+
74+
three->data=3;
75+
three->next=five;
76+
77+
four->data=4;
78+
four->next=six;
79+
80+
five->data=5;
81+
five->next=seven;
82+
83+
six->data=6;
84+
six->next=NULL;
85+
//Last node of second input linked list
86+
87+
seven->data=7;
88+
seven->next=NULL;
89+
//Last node of first input linked list
90+
91+
printf("Linked List 1: ");
92+
printlist(head1);
93+
printf("\nLinked List 2: ");
94+
printlist(head2);
95+
96+
//Merging the two linked list into single linked list
97+
merge();
98+
99+
printf("\nMerged Linked List: ");
100+
printlist(head1);//list one has been modified
101+
102+
return0;
103+
}

‎Searches/modifiedBinarySearch.c

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
#include<stdio.h>
2+
3+
intn,m;//size of the matrix
4+
5+
// This function does Binary search for x in i-th row from j_low to j_high.
6+
voidbinarySearch(intmat[n][m],inti,intj_low,intj_high,intx)
7+
{
8+
while (j_low <=j_high)
9+
{
10+
intj_mid= (j_low+j_high) /2;
11+
12+
// Element found
13+
if (mat[i][j_mid]==x){
14+
printf("Found at (%d,%d)\n",i,j_mid);
15+
return ;
16+
}
17+
elseif (mat[i][j_mid]>x)
18+
j_high=j_mid-1;
19+
else
20+
j_low=j_mid+1;
21+
}
22+
// element not found
23+
printf("element not found\n");
24+
}
25+
26+
// Function to perform binary search on the mid values of row to get the desired pair of rows
27+
// where the element can be found
28+
voidmodifiedBinarySearch(intmat[n][m],intn,intm,intx)
29+
{// If Single row matrix
30+
if (n==1){
31+
binarySearch(mat,0,0,m-1,x);
32+
return;
33+
}
34+
35+
// Do binary search in middle column.
36+
// Condition to terminate the loop when the 2 desired rows are found.
37+
inti_low=0,i_high=n-1,j_mid=m/2;
38+
while ((i_low+1)<i_high)
39+
{
40+
inti_mid= (i_low+i_high) /2;
41+
// element found
42+
if (mat[i_mid][j_mid]==x){
43+
printf("Found at (%d,%d)\n",i_mid,j_mid);
44+
return;
45+
}
46+
elseif (mat[i_mid][j_mid]>x)
47+
i_high=i_mid;
48+
else
49+
i_low=i_mid;
50+
}
51+
// If element is present on the mid of the two rows
52+
if (mat[i_low][j_mid]==x)
53+
printf("Found at (%d,%d)\n",i_low,j_mid);
54+
elseif (mat[i_low+1][j_mid]==x)
55+
printf("Found at (%d,%d)\n",i_low+1,j_mid);
56+
57+
// Search element on 1st half of 1st row
58+
elseif (x <=mat[i_low][j_mid-1])
59+
binarySearch(mat,i_low,0,j_mid-1,x);
60+
61+
// Search element on 2nd half of 1st row
62+
elseif (x >=mat[i_low][j_mid+1]&&x <=mat[i_low][m-1])
63+
binarySearch(mat,i_low,j_mid+1,m-1,x);
64+
65+
// Search element on 1st half of 2nd row
66+
elseif (x <=mat[i_low+1][j_mid-1])
67+
binarySearch(mat,i_low+1,0,j_mid-1,x);
68+
69+
// search element on 2nd half of 2nd row
70+
else
71+
binarySearch(mat,i_low+1,j_mid+1,m-1,x);
72+
}
73+
74+
intmain()
75+
{
76+
intx;//element to be searched
77+
scanf("%d %d %d\n",&n,&m,&x);
78+
intmat[n][m];
79+
for(inti=0;i<n;i++){
80+
for(intj=0;j<m;j++){
81+
scanf("%d",&mat[i][j]);
82+
}
83+
}
84+
modifiedBinarySearch(mat,n,m,x);
85+
return0;
86+
}

‎misc/lexicographicPermutations.c

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#include<stdio.h>
2+
#include<string.h>
3+
#include<stdlib.h>
4+
5+
voidswap(char*left,char*right){
6+
chartemp=*left;
7+
*left=*right;
8+
*right=temp;
9+
}
10+
11+
intcompare (constvoid*a,constvoid*b){
12+
return (*(char*)a-*(char*)b );
13+
}
14+
15+
voidPrintSortedPermutations(charstr[])
16+
{
17+
intstrSize=strlen(str);
18+
qsort(str,strSize,sizeof(char),compare);
19+
20+
intlargerPermFound=1;
21+
do{
22+
// 1. Print permutation
23+
printf("%s\n",str);
24+
// 2. Find rightmost char that is smaller than char to its right
25+
inti;
26+
for (i=strSize-2;i >=0&&str[i] >=str[i+1];--i){}
27+
28+
// if we couldn't find one, we're finished, else we can swap
29+
if (i >=0){
30+
// 3. find character at index j such that str[j] = min(str[k]) && str[k] > str[i] for all k > i
31+
intj=i+1,k;
32+
for(k=j;k<strSize&&str[k];k++){
33+
if (str[k]>str[i]&&str[k]<str[j])
34+
j=k;
35+
}
36+
// 3. Swap chars at i and j
37+
swap(&str[i],&str[j]);
38+
// 4. Sort string to the right of i
39+
qsort(str+i+1,strSize-i-1,sizeof(char),compare);
40+
}
41+
elselargerPermFound=0;
42+
}
43+
while(largerPermFound);
44+
}
45+
46+
intmain() {
47+
intn;//size of string
48+
scanf("%d\n",&n);
49+
charstr[n];
50+
scanf("%s",str);
51+
PrintSortedPermutations(str);
52+
return0;
53+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp