Problems 1: Spiral matrix - Advanced Source of the problem: Here (not in English)
Spiral matrix is formed by filling number 1 in 1st row 1st column, after that, filling with increasing number by clockwise, example:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Write a program that inform the value of cell (x, y) of a square spiral matrix sized n x n.
Input: First row record the number of tests, not greater than 100. Each test record in one row, include tree values n x y (1 ≤ n, x, y ≤ 100)
Output: With each test, print out the value of the cell at x row y column in n x n spiral matrix.
Example:
Input: Output:
2 18
5 2 3 2
4 1 2
Solution:
Let's take the given example of the spiral matrix above to explain my idea.
I start the loop, the loop do these follow things:
First I devide the ring into 4 equally group and filling increasing number by clockwise:
1 2 3 4 | 5
--
16 .. .. .. 6
15 .. .. .. 7
14 .. .. .. 8
--
13| 12 11 10 9
After that, my ring will shrink, and repeat steps of the previous ring, look like this:
.. .. .. .. ..
.. 17 18 |19 ..
--
.. 24 .. 20 ..
--
.. 23| 22 21 ..
.. .. .. .. ..
Because I set the loop to just repeat n/2 times, so the loop will stop here, but with n is odd, there always still 1 cell left, so after stop the loop, I will have to check if n is odd, then the cell at n/2 row and n/2 column will be set to value n^2.
Implementation:
#include<stdio.h>
#define fi "d:\\program\\text\\ip_spoj_mtx.txt" //Input
#define fo "d:\\program\\text\\op_spoj_mtx.txt" //Output
#define ma 100 //maximum size of each array
int s,n[ma],x[ma],y[ma],a[ma][ma],r[ma]; //s: the number of tests; n,x,y: self-explanatory; a: contains temporay spiral matrix; r: the results
void Input(void);
void Process(void);
void Output(void);
int main(void) {
Input();
Process();
Output();
printf("Done!\n");
return 0;
}
void Input(void) {
FILE *f;
f=fopen(fi,"r");
if(!f)
printf("Cannot open file %s\n",fi);
else {
fscanf(f,"%d",&s);
int i;
for(i=0;i<s;i++)
fscanf(f,"%d%d%d",&n[i],&x[i],&y[i]);
fclose(f);
}
}
void Process(void) {
int k,i,j,xu,yu,xr,yr,xd,yd,xl,yl,v,b; //x_,y_ is the coordinates use in the matrix; _u is up group, _r: right group, _d: down, _l: left
for(k=0;k<s;k++) {
j=0; //general border of each group
b=n[k]-1; //general border of each group (each group has 2 border, one is the "|" or "--" in my explanatory above, and another is the remain
v=0; //value to filling in cells
xu=0;
yl=0;
xd=n[k]-1;
yr=n[k]-1;
for(i=0;i<n[k]/2;i++) {
for(yu=j;yu<b;yu++)
a[xu][yu]=++v;
for(xr=j;xr<b;xr++)
a[xr][yr]=++v;
for(yd=b;yd>j;yd--)
a[xd][yd]=++v;
for(xl=b;xl>j;xl--)
a[xl][yl]=++v;
b--;
j++;
xu++;
yr--;
xd--;
yl++;
}
if(n[k]%2!=0) {
v=n[k]/2;
a[v][v]=n[k]*n[k];
}
r[k]=a[x[k]-1][y[k]-1];
}
}
void Output(void) {
FILE *f;
f=fopen(fo,"w");
if(!f)
printf("Cannot open file %s\n",fo);
else {
int i;
for(i=0;i<s;i++)
fprintf(f,"%d\n",r[i]);
fclose(f);
}
}
Problem 2: Working with singly linked list
I think my code is self-explanatory, if you are beginner to coding, I really recommend you to try reading and understanding the code by yourself, if you have any question or opinion, please let me know.
Another way, you should paste it in a C compiler to see it works.
Implementation:
#include<stdio.h>
#include<stdlib.h>
#define ma 100
struct Node {
int data;
struct Node *next;
};
struct Node *head;
void Prt(void); //Print all node in the list.
void Inl(int); //Insert a node at the end of the list.
void Ins(int,int); //Insert a node of value x, at the n_th position.
void Del(int); //Delete a node at n_th option position.
void Mod(int,int); //Modify value of a node to value x, at n_th position.
void Sch(int); //Search for positions of any node that matching the key.
void Rev(void); //Reverse the list.
void Clr(void); //Clear the list.
int main(void) {
head=NULL;
int n,k,x,c;
do {
k=-1;
while(!(k==0||k==1||k==2||k==3||k==4||k==5||k==6||k==7)) {
system("cls"); //I know this not standard but I too lazy too write out a clrscr function, so if you want more standard just search on Internet for the standard one
printf("Working with a linked list (of integers)! Please know what you are doing ^_^\n");
Prt();
printf("\n\n(0) Exit program.");
printf("\n(1) Insert a node at the end of the list.");
printf("\n(2) Insert a node at any position in the list.");
printf("\n(3) Delete a node at any position in the list.");
printf("\n(4) Modify the value of a node at any position in the list.");
printf("\n(5) Searching for position of any nodes that matching the key.");
printf("\n(6) Reverse the list.");
printf("\n(7) Clear the list.");
printf("\nImport a number: ");
scanf("%d",&k);
}
switch(k) {
case 0:
return 0;
break;
case 1:
printf("\nInsert number x into the end of the list, import x: ");
scanf("%d",&x);
Inl(x);
break;
case 2:
printf("\nInsert number x into n position, import x and n: ");
scanf("%d%d",&x,&n);
Ins(x,n);
break;
case 3:
printf("\nDelete node at n position, import n: ");
scanf("%d",&n);
Del(n);
break;
case 4:
printf("\nEdit the value of node at n position to value x, import x and n: ");
scanf("%d%d",&x,&n);
Mod(x,n);
break;
case 5:
printf("\nSearching for any node that matching the key, import key: ");
scanf("%d",&x);
Sch(x);
break;
case 6:
Rev();
printf("\nDone!\n");
break;
case 7:
Clr();
printf("\nDone!\n");
break;
}
printf("\n\nContinue? (import 0 to exit, other numbers to continue): ");
scanf("%d",&c);
} while(c!=0);
return 0;
}
void Prt(void) {
struct Node *t;
t=head;
printf("\nCurrent list: ");
if(t==NULL)
printf("EMPTY");
else
while(t!=NULL) {
printf("%d ",t->data);
t=t->next;
}
}
void Inl(int x) {
struct Node *t;
t=(struct Node *)malloc(sizeof(*t));
t->data=x;
t->next=NULL;
if(head==NULL)
head=t;
else {
struct Node *u;
u=head;
while(u->next!=NULL)
u=u->next;
u->next=t;
}
}
void Ins(int x,int n) {
struct Node *t=(struct Node *)malloc(sizeof(*t));
t->data=x;
if(n==1) {
t->next=head;
head=t;
}
else {
struct Node *u=head;
int i;
for(i=0;i<n-2;i++)
u=u->next;
t->next=u->next;
u->next=t;
}
}
void Del(int n) {
struct Node *t;
t=head;
if(n==1) {
head=t->next;
free(t);
}
else {
int i;
for(i=0;i<n-2;i++)
t=t->next;
struct Node *u;
u=t->next;
t->next=u->next;
free(u);
}
}
void Mod(int x,int n) {
struct Node *t;
t=head;
int i;
for(i=0;i<n-1;i++)
t=t->next;
t->data=x;
}
void Sch(int x) {
struct Node *t;
t=head;
int i,j,r[ma];
i=0;
j=0;
while(t!=NULL) {
i++;
if(t->data==x) {
r[j]=i;
j++;
}
t=t->next;
}
if(j==0)
printf("\nNo results found!");
else {
printf("\nFound %d result(s), the positions of the result(s):\n",j);
for(i=0;i<j;i++)
printf("%d ",r[i]);
}
}
void Rev(void) {
struct Node *prev,*curr,*next;
prev=NULL;
curr=head;
while(curr!=NULL) {
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
head=prev;
}
void Clr(void) {
struct Node *prev,*curr;
prev=head;
curr=prev->next;
free(prev);
while(curr!=NULL) {
prev=curr;
curr=curr->next;
free(prev);
}
head=curr;
}
To be continue (if you have any suggest)
