fork download
copy 
  1. #include <stdio.h>
  2. //#include <conio>
  3. //#include <alloc.h>
  4. #include<iostream>
  5. #include<stdlib.h>
  6. #define MAX1 3
  7. #define MAX2 3
  8.  
  9. /* structure for col headnode */
  10. struct cheadnode
  11. {
  12.     int colno ;
  13.     struct node *down ;
  14.     struct cheadnode *next ;
  15. } ;
  16.  
  17. /* structure for row headnode */
  18. struct rheadnode
  19. {
  20.     int rowno ;
  21.     struct node * right ;
  22.     struct rheadnode *next ;
  23. } ;
  24.  
  25. /* structure for node to store element */
  26. struct node
  27. {
  28.     int row ;
  29.     int col ;
  30.     int val ;
  31.     struct node *right ;
  32.     struct node *down ;
  33. } ;
  34.  
  35. /* structure for special headnode */
  36. struct spmat
  37. {
  38.     struct rheadnode *firstrow ;
  39.     struct cheadnode *firstcol ;
  40.     int noofrows ;
  41.     int noofcols ;
  42. } ;
  43.  
  44. struct sparse
  45. {
  46.     int *sp ;
  47.     int row  ;
  48.     struct spmat *smat ;
  49.     struct cheadnode *chead[MAX2] ;
  50.     struct rheadnode *rhead[MAX1] ;
  51.     struct node *nd ;
  52. } ;
  53.  
  54. void initsparse ( struct sparse * ) ;
  55. void create_array ( struct sparse * ) ;
  56. void display ( struct sparse ) ;
  57. int count ( struct sparse ) ;
  58. void create_triplet ( struct sparse *, struct sparse ) ;
  59. void create_llist ( struct sparse * ) ;
  60. void insert ( struct sparse *, struct spmat *, int, int, int ) ;
  61. void show_llist ( struct sparse ) ;
  62. void delsparse ( struct sparse * ) ;
  63.  
  64. int main( )
  65. {
  66.     struct sparse s1, s2 ;
  67.  
  68.     //clrscr( ) ;
  69.  
  70.     initsparse ( &s1 ) ;
  71.     initsparse ( &s2 ) ;
  72.  
  73.     create_array ( &s1 ) ;
  74.  
  75.     printf ( "\nElements in sparse matrix: " ) ;
  76.     display ( s1 ) ;
  77.  
  78.     create_triplet ( &s2, s1 ) ;
  79.  
  80.     create_llist ( &s2 ) ;
  81.     printf ( "\n\nInformation stored in linked list : " ) ;
  82.     show_llist ( s2 ) ;
  83.  
  84.     delsparse ( &s1 ) ;
  85.     delsparse ( &s2 ) ;
  86.  
  87.     getch( ) ;
  88. }
  89.  
  90. /* initializes structure elements */
  91. void initsparse ( struct sparse *p )
  92. {
  93.     int i ;
  94.     /* create row headnodes */
  95. for ( i = 0 ; i < MAX1 ; i++ )
  96.         p -> rhead[i] = ( struct rheadnode * ) malloc ( sizeof ( struct rheadnode ) ) ;
  97.  
  98.     /* initialize and link row headnodes together */
  99. for ( i = 0 ; i < MAX1 - 1 ; i++ )
  100.     {
  101.         p -> rhead[i] -> next = p -> rhead[i + 1] ;
  102.         p -> rhead[i] -> right = NULL ;
  103.         p -> rhead[i] -> rowno = i ;
  104.     }
  105.     p -> rhead[i] -> right = NULL ;
  106.     p -> rhead[i] -> next = NULL ;
  107.  
  108.     /* create col headnodes */
  109. for ( i = 0 ; i < MAX1 ; i++ )
  110.         p -> chead[i] = ( struct cheadnode * ) malloc ( sizeof ( struct cheadnode ) ) ;
  111.  
  112.     /* initialize and link col headnodes together */
  113. for ( i = 0 ; i < MAX2 - 1 ; i++ )
  114.     {
  115.         p -> chead[i] -> next = p -> chead[i + 1] ;
  116.         p -> chead[i] -> down = NULL ;
  117.         p -> chead[i] -> colno = i ;
  118.     }
  119.     p -> chead[i] -> down = NULL ;
  120.     p -> chead[i] -> next = NULL ;
  121.  
  122.     /* create and initialize special headnode */
  123.  
  124.     p -> smat = ( struct spmat * ) malloc ( sizeof ( struct spmat ) ) ;
  125.     p -> smat -> firstcol = p -> chead[0] ;
  126.     p -> smat -> firstrow = p -> rhead[0] ;
  127.     p -> smat -> noofcols = MAX2 ;
  128.     p -> smat -> noofrows = MAX1 ;
  129. }
  130.  
  131. /* creates, dynamically the matrix of size MAX1 x MAX2 */
  132. void create_array ( struct sparse *p )
  133. {
  134.     int n, i ;
  135.  
  136.     p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;
  137.  
  138.     /* get the element and store it */
  139. for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
  140.     {
  141.         printf ( "Enter element no. %d:", i ) ;
  142.         scanf ( "%d", &n ) ;
  143.         * ( p -> sp + i ) = n ;
  144.     }
  145. }
  146.  
  147. /* displays the contents of the matrix */
  148. void display ( struct sparse s )
  149. {
  150.     int i ;
  151.  
  152.     /* traverses the entire matrix */
  153. for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
  154.     {
  155.         /* positions the cursor to the new line for every new row */
  156. if ( i % MAX2 == 0 )
  157.             printf ( "\n" ) ;
  158.         printf ( "%d\t", * ( s.sp + i ) ) ;
  159.     }
  160. }
  161.  
  162. /* counts the number of non-zero elements */
  163. int count ( struct sparse s )
  164. {
  165.     int cnt = 0, i ;
  166.  
  167.     for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
  168.     {
  169.         if ( * ( s.sp + i ) != 0 )
  170.             cnt++ ;
  171.     }
  172.     return cnt ;
  173. }
  174.  
  175. /* creates an array of triplet containing info. about non-zero elements */
  176. void create_triplet ( struct sparse *p, struct sparse s )
  177. {
  178.     int r = 0 , c = -1, l = -1, i ;
  179.  
  180.     p -> row = count ( s ) ;
  181.     p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;
  182.  
  183.     for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
  184.     {
  185.         c++ ;
  186.         /* sets the row and column values */
  187. if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
  188.         {
  189.             r++ ;
  190.             c = 0 ;
  191.         }
  192.  
  193.         /* checks for non-zero element. Row, column and
  194.            non-zero element value is assigned to the matrix */
  195. if ( * ( s.sp + i ) != 0 )
  196.         {
  197.             l++ ;
  198.             * ( p -> sp + l ) = r ;
  199.             l++ ;
  200.             * ( p -> sp + l ) = c ;
  201.             l++ ;
  202.             * ( p -> sp + l ) = * ( s.sp + i ) ;
  203.         }
  204.     }
  205. }
  206.  
  207. /* stores information of triplet in a linked list form */
  208. void create_llist ( struct sparse *p )
  209. {
  210.     int j = 0, i ;
  211.     for ( i = 0 ; i < p -> row ; i++, j+= 3 )
  212.         insert ( p, p -> smat, * ( p -> sp + j ), * ( p -> sp + j + 1 ),
  213.                                                 * ( p -> sp + j + 2) ) ;
  214. }
  215.  
  216. /* inserts element to the list */
  217. void insert ( struct sparse *p, struct spmat *smat , int r, int c, int v )
  218. {
  219.     struct node *temp1, *temp2 ;
  220.     struct rheadnode *rh ;
  221.     struct cheadnode *ch ;
  222.     int i, j ;
  223.  
  224.     /*  allocate and initialize memory for the node */
  225.  
  226.     p -> nd = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
  227.     p -> nd -> col = c ;
  228.     p -> nd -> row = r ;
  229.     p -> nd -> val = v ;
  230.  
  231.     /* get the first row headnode */
  232.  
  233.     rh = smat -> firstrow ;
  234.  
  235.     /* get the proper row headnode */
  236. for ( i = 0 ; i < r ; i++ )
  237.         rh = rh -> next ;
  238.     temp1 = rh -> right ;
  239.  
  240.     /* if no element added in a row */
  241. if ( temp1 == NULL )
  242.     {
  243.         rh -> right = p -> nd ;
  244.         p -> nd -> right = NULL ;
  245.     }
  246.     else
  247.     {
  248.         /* add element at proper position */
  249. while ( ( temp1 != NULL  ) && ( temp1 -> col < c ) )
  250.         {
  251.             temp2 = temp1 ;
  252.             temp1 = temp1 -> right ;
  253.         }
  254.         temp2 -> right = p -> nd ;
  255.         p -> nd -> right = NULL ;
  256.     }
  257.  
  258.     /* link proper col headnode with the node */
  259.  
  260.     ch = p -> smat -> firstcol ;
  261.     for ( j = 0 ; j < c ; j++ )
  262.         ch = ch -> next ;
  263.     temp1 = ch -> down ;
  264.  
  265.     /* if col not pointing to any node */
  266. if ( temp1 == NULL )
  267.     {
  268.         ch -> down = p -> nd ;
  269.         p -> nd -> down = NULL ;
  270.     }
  271.     else
  272.     {
  273.         /* link previous node in column with next node in same column */
  274. while ( ( temp1 != NULL ) && ( temp1 -> row < r ) )
  275.         {
  276.             temp2 = temp1 ;
  277.             temp1 = temp1 -> down ;
  278.         }
  279.         temp2 -> down = p -> nd ;
  280.         p -> nd -> down = NULL ;
  281.     }
  282. }
  283.  
  284. void show_llist ( struct sparse s )
  285. {
  286.     struct node *temp ;
  287.     /* get the first row headnode */
  288. int r = s.smat -> noofrows ;
  289.     int i ;
  290.  
  291.     printf ( "\n" ) ;
  292.  
  293.     for ( i = 0 ; i < r ; i++ )
  294.     {
  295.         temp = s.rhead[i] -> right ;
  296.         if ( temp != NULL )
  297.         {
  298.             while ( temp -> right != NULL )
  299.             {
  300.                 printf ( "Row: %d Col: %d Val: %d\n", temp -> row, temp -> col,
  301.                                                         temp -> val ) ;
  302.                 temp = temp -> right ;
  303.             }
  304.             if ( temp -> row == i )
  305.                 printf ( "Row: %d Col: %d Val: %d\n", temp -> row, temp -> col,
  306.                                                     temp -> val ) ;
  307.         }
  308.     }
  309. }
  310.  
  311. /* deallocates memory */
  312. void delsparse ( struct sparse *p )
  313. {
  314.     int r = p -> smat -> noofrows ;
  315.        struct rheadnode *rh ;
  316.     struct node *temp1, *temp2 ;
  317.     int i, c ;
  318.  
  319.     /* deallocate memeory of nodes by traversing rowwise */
  320. for ( i = r - 1 ; i >= 0 ; i-- )
  321.     {
  322.         rh = p -> rhead[i] ;
  323.         temp1 = rh -> right ;
  324.  
  325.         while ( temp1 != NULL )
  326.         {
  327.             temp2 = temp1 -> right ;
  328.             free ( temp1 ) ;
  329.             temp1 = temp2 ;
  330.         }
  331.     }
  332.  
  333.     /* deallocate memory of row headnodes */
  334. for ( i = r - 1 ; i >= 0 ; i-- )
  335.         free ( p -> rhead[i] ) ;
  336.  
  337.     /* deallocate memory of col headnodes */
  338.  
  339.     c = p -> smat -> noofcols ;
  340.     for ( i = c - 1 ; i >= 0 ; i-- )
  341.         free ( p -> chead[i] ) ;
  342. }
  343.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
0
0
2
5
0
0
0
9
0
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:87:12: error: 'getch' was not declared in this scope
     getch( ) ;
            ^
stdout
copy 
Standard output is empty
https://ideone.com/trd3Ml
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!