samroar04

Untitled

Feb 5th, 2014
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.88 KB | None | 0 0
  1. Practical File
  2.  
  3. For
  4.  
  5. Data Structures
  6.  
  7.  
  8.  
  9.  
  10. Submitted To: Submitted By:
  11. Mrs Anuradha Saini
  12.  
  13. BCA-II
  14. INDEX
  15. S.no.
  16. Programs
  17. Page no.
  18. Date
  19. Sign
  20. 1.
  21. Wap to insert an element , delete an element and traverse an element from a linear array.
  22. 3-6
  23.  
  24.  
  25.  
  26.  
  27. 2.
  28. Wap to insert a node , delete a node and traverse a linked list.
  29. 7-12
  30.  
  31.  
  32.  
  33.  
  34. 3.
  35. Wap to perform push, pop and traverse operations on a stack
  36. implemented using array.
  37. 13-15
  38.  
  39.  
  40.  
  41.  
  42. 4.
  43. Wap to implement insertion,deletion & traversal operation on linked queue
  44. 16-18
  45.  
  46.  
  47.  
  48.  
  49. 5.
  50. Wap to implement Linear search
  51. 19,20
  52.  
  53.  
  54.  
  55.  
  56. 6.
  57. Wap to implement Binary search
  58. 21,22
  59.  
  60.  
  61.  
  62.  
  63. 7.
  64. Wap to implement Bubble sort
  65. 23,24
  66.  
  67.  
  68.  
  69.  
  70. 8.
  71. Wap to implement Quick sort
  72. 25-27
  73.  
  74.  
  75.  
  76.  
  77. 9.
  78. Wap to implement Merge sort
  79. 28-30
  80.  
  81.  
  82.  
  83.  
  84. 10.
  85. Wap to implement Insertion sort
  86. 31-32
  87.  
  88.  
  89.  
  90.  
  91. 11.
  92. Wap to implement Selection sort
  93. 33-34
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134. /* Wap to insert an element , delete an element and traverse an element from a linear array */
  135.  
  136. #include<stdio.h>
  137. #include<conio.h>
  138. void traverse(int i,int a[],int len) {
  139. printf("\nTotal number of elements are : %d",len);
  140. printf("\nElements are : ");
  141. for(i=0; i<len; i++) {
  142. printf("\t%d",a[i]);
  143. }
  144. }
  145. void insert_ele(int i, int a[], int *len) {
  146. int ele,loc;
  147. printf("\nEnter element to be inserted :" );
  148. scanf("%d",&ele);
  149. printf("\nEnter loc");
  150. scanf("%d",&loc);
  151. if(i==19) {printf("\Overflow");}
  152. else {
  153. while(i>=loc) {
  154. a[i+1]=a[i];
  155. i--;
  156. }
  157. a[loc]=ele;
  158. (*len)++;
  159. printf("\nNew Array :");
  160. for(i=0 ; i<*len ; i++) {
  161. printf("\t%d",a[i]);
  162. }
  163. }
  164. }
  165. void delete_ele(int i,int a[], int *len) {
  166. int loc;
  167. printf("\nEnter location of element to be deleted");
  168. scanf("%d",&loc);
  169. if(*len==0) { printf("\nUnderflow"); }
  170. else {
  171. for(i=loc ; i<(*len-1) ; i++) {
  172. a[i]=a[i+1];
  173. }
  174. (*len)--;
  175. printf("\nNew Array :");
  176. for(i=0 ; i<*len ; i++) {
  177. printf("\t%d",a[i]);
  178. }
  179. }
  180. }
  181. void find_ele(int i,int a[], int len) {
  182. int ele, count=0;
  183. printf("\nEnter element to be searched :");
  184. scanf("%d",&ele);
  185. for(i=0 ; i<len ; i++) {
  186. if(a[i]==ele) { count++;}
  187. }
  188. if(count == 0) {
  189. printf("\nElement does not exist");
  190. }
  191. else {
  192. printf("\nElement found %d times",count);
  193. }
  194. }
  195. void main() {
  196. int a[20], i, len, ch;
  197. char choice;
  198. clrscr();
  199. printf("\nEnter number of elements you want to enter");
  200. scanf("%d",&len);
  201. printf("\nEnter the elements :");
  202. for(i=0 ; i<len; i++) {
  203. scanf("%d",&a[i]);
  204. }
  205. printf("\nElements inserted are :");
  206. for(i=0 ; i<len; i++) {
  207. printf("%d",a[i]);
  208. }
  209. i--;
  210. label:
  211. printf("\nPress 1 to insert, 2 to delete,3 to find any element");
  212. printf("\n or 4 to traverse the array");
  213. scanf("%d",&ch);
  214. switch(ch) {
  215. case 1:insert_ele(i, a, &len);
  216. break;
  217. case 2:delete_ele(i, a, &len);
  218. break;
  219. case 3:find_ele(i, a, len);
  220. break;
  221. case 4:traverse(i, a, len);
  222. break;
  223. default:printf("\nInvalid option");
  224. break;
  225. }
  226. printf("\nPress y to continue or any other key to quit :");
  227. scanf("%s",&choice);
  228. if(choice== 'y' || choice=='Y') {
  229. goto label;
  230. }
  231. getch();
  232. }
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246. //output
  247.  
  248. /* Wap to insert a node , delete a node and traverse a linked list*\
  249.  
  250. #include<stdio.h>
  251. #include<conio.h>
  252. #include<stdlib.h>
  253.  
  254. typedef struct node {
  255. int info;
  256. struct node *link;
  257. }list;
  258.  
  259. list *n,*start;
  260. void create();
  261. void search(int);
  262. void display();
  263. void insert(int);
  264. int del(int);
  265.  
  266. void main() {
  267. int n,a,i,b,choice;
  268. clrscr();
  269. start=NULL;
  270. while(1) {
  271. printf("\n---------------------------");
  272. printf("\n | Linked List Options |\n");
  273. printf("---------------------------\n");
  274. printf("\n1.Insertion");
  275. printf("\n2.Deletion");
  276. printf("\n3.Traverse");
  277. printf("\n4.Search");
  278. printf("\n5.Quit");
  279. printf("\n\nEnter your choice (1,2,3,4,5): ");
  280. scanf("%d",&choice);
  281. switch(choice) {
  282. case 1:
  283. printf("\nEnter the element:");
  284. scanf("\n%d",&a);
  285. insert(a);
  286. display();
  287. break;
  288. case 2:
  289. printf("\nEnter the element you want to delete: ");
  290. scanf("%d",&n);
  291. b=del(n);
  292. if(b==0) { printf("\nDeletion UnSucessful"); }
  293. else { printf("\nValue deleted %d",b);}
  294. display();
  295. break;
  296. case 3:
  297. display();
  298. break;
  299. case 4:
  300. printf("\nEnter the element you want to search: ");
  301. scanf("%d",&b);
  302. search(b);
  303. break;
  304. case 5:
  305. exit(0);
  306. break;
  307. default:
  308. printf("\nInvalid choice...");
  309. }
  310. printf("\n\nPress any key to continue...\n");
  311. getch();
  312. clrscr();
  313. }
  314. }
  315.  
  316. void create() {
  317. list *p;
  318. p=(list *)malloc(sizeof(list));
  319. p->link=p;
  320. start=p;
  321. }
  322. void display() {
  323. list *p;
  324. if(start->link==start) { printf("\nList is empty");return; }
  325. printf("\nElements of linked list are: ");
  326. for(p=start->link;p!=start;p=p->link)
  327. printf("%5d",p->info);
  328. }
  329.  
  330. void insert(int d) {
  331. list *p,*q;
  332. p=(list *)malloc(sizeof(list));
  333. p->info=d;
  334. p->link=start;
  335. if(start->link==start)
  336. start->link=p;
  337. else {
  338. q=start->link;
  339. while(q->link!=start)
  340. q=q->link;
  341. q->link=p;
  342. }
  343. }
  344.  
  345. void search(int d) {
  346. int position=0;
  347. list *p;
  348. if(start->link==start) {
  349. printf("\nList is empty");
  350. return;
  351. }
  352. for(p=start->link;p!=start;p=p->link) {
  353. position++;
  354. if(p->info==d) {
  355. printf("\n%d found in the list at position %d",d,position);
  356. return;
  357. }
  358. }
  359. printf("\n%d not found in the list",d);
  360. }
  361.  
  362. int del(int d) {
  363. list *p,*l;
  364. if(start->link==start)
  365. return(0);
  366.  
  367. for(p=start->link;p!=start;l=p,p=p->link) {
  368. if(p->info==d) {
  369. if(p==start->link)
  370. start->link=p->link;
  371. else {
  372. l->link=p->link;
  373. free(p);
  374. return(d);
  375. }
  376. }
  377. }
  378. printf("\n%d not found in the list",d);
  379. return(0);
  380. }
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.  
  399.  
  400.  
  401.  
  402.  
  403. //Output
  404.  
  405.  
  406. /* Wap to perform push, pop and traverse operations on a stack implemented using array */
  407. #include<stdio.h>
  408. #include<conio.h>
  409. #define max 5
  410. int top=-1;
  411. int stack[max];
  412. void push() {
  413. int item;
  414. if(top==(max-1)) { printf("\n stack is full oro verflow \n");}
  415. else {
  416. printf("\nEnter the item:");
  417. scanf("%d",&item);
  418. stack[top]=item;
  419. top=top+1;
  420. }
  421. }
  422. void pop() {
  423. int temp;
  424. if(top==-1) { printf("\n stack is empty or underflow \n"); }
  425. else {
  426. temp=stack[top];
  427. printf("item deleted is %d",temp);
  428. top=top-1;
  429. }
  430. }
  431. void display() {
  432. int i;
  433. if(top==-1) {
  434. printf("\nstack is empty\n");
  435. }
  436. else {
  437. printf("Elements of stack are:\n");
  438. for(i=-1;i<=top-1;i++) {
  439. printf("%d\n",stack[i]);
  440. }
  441. }
  442. }
  443. void main() {
  444. int choice;
  445. clrscr();
  446. while(1) {
  447. printf("1:Push\n 2:Pop\n 3:Display\n 4:Exit");
  448. printf("\nEnter your choice 1-4:");
  449. scanf("%d",&choice);
  450. switch(choice) {
  451. case 1:push();
  452. break;
  453. case 2:pop();
  454. break;
  455. case 3:display();
  456. break;
  457. case 4:exit(0);
  458. }
  459. }
  460. getch();
  461. }
  462.  
  463.  
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472.  
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481. //output
  482.  
  483.  
  484.  
  485.  
  486.  
  487.  
  488.  
  489.  
  490. /*Wap to implement insertion,deletion & traversal operation on linked queue*/
  491.  
  492. #include<stdio.h>
  493. #include<conio.h>
  494. #include<string.h>
  495. #define NULL 0
  496. struct queuenode {
  497. int info;
  498. struct queuenode *link;
  499. };
  500. typedef struct queuenode node;
  501. void enqueue(node** front,node** rear,int item) {
  502. node *new;
  503. new=(node*) malloc(sizeof(node));
  504. new->info=item;
  505. if(*front==NULL) { *front=new; *rear=new }
  506. else { (*rear)->link=new;
  507. (*rear)=new;
  508. }
  509. new->link=NULL;
  510. }
  511. void dequeue(node** front) {
  512. node *save;
  513. if(*front==NULL) { printf("undeflow: queue empty");}
  514. else {
  515. printf("element deleted=%d",(*front)->info);
  516. save=*front;
  517. *front=save->link;
  518. free(save);
  519. }
  520. }
  521. void display(node *front) {
  522. node *ptr=front;
  523. printf("\n traversing queue:");
  524. while(ptr!=NULL) {
  525. printf("%d",ptr->info);
  526. ptr=ptr->link;
  527. }
  528. }
  529. void main() {
  530. node *front=NULL;
  531. node *rear=NULL;
  532. int choice,item;
  533. char ch;
  534. clrscr();
  535. printf("1:ENQUEUE\n2.DEQUEUE\n3.Display\n4.Another to exit");
  536. do {
  537. printf("\nEnter your choice:");
  538. scanf("%d",&choice);
  539. switch(choice) {
  540. case 1:
  541. printf("Enter value to be inserted:\n");
  542. scanf("%d",&item);
  543. enqueue(&front,&rear,item);
  544. break;
  545. case 2:
  546. dequeue(&front);
  547. break;
  548. case 3:
  549. display(front);
  550. break;
  551. default:
  552. printf("\nend of operation \n");
  553. }
  554. printf("want to continue:(y or Y)=");
  555. fflush(stdin);
  556. ch=getchar();
  557. } while((ch=='y')||(ch=='n'));
  558. printf("\n end of program");
  559. getch();
  560.  
  561.  
  562.  
  563.  
  564.  
  565. //output
  566.  
  567.  
  568. /* Wap to implement linear search*/
  569.  
  570. #include<stdio.h>
  571. #include<conio.h>
  572. void main() {
  573. int a[10],i,n,m,c=0;
  574. clrscr();
  575. printf("Enter the size of an array");
  576. scanf("%d",&n);
  577. printf("\nEnter the elements of the array");
  578. for(i=0;i<=n-1;i++) {
  579. scanf("%d",&a[i]);
  580. }
  581. printf("\nThe elements of an array are");
  582. for(i=0;i<=n-1;i++) {
  583. printf(" %d",a[i]);
  584. }
  585. printf("\nEnter the number to be search");
  586. scanf("%d",&m);
  587. for(i=0;i<=n-1;i++) {
  588. if(a[i]==m) {
  589. c=1;
  590. break;
  591. }
  592. }
  593. if(c==0) { printf("\nThe number is not in the list"); }
  594. else{ printf("\nThe number is found"); }
  595. getch();
  596. }
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605. //Output
  606.  
  607.  
  608.  
  609.  
  610.  
  611.  
  612.  
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619. /* Wap to implement binary search */
  620.  
  621. #include<stdio.h>
  622. #include<conio.h>
  623. void main() {
  624. int n, a[30], item, i, j, mid, top, bottom;
  625. clrscr();
  626. printf("Enter how many elements you want:\n");
  627. scanf("%d", &n);
  628. printf("Enter the %d elements in ascending order\n", n);
  629. for (i = 0; i < n; i++) {
  630. scanf("%d", &a[i]);
  631. }
  632. printf("\nEnter the item to search\n");
  633. scanf("%d", &item);
  634. bottom = 1;
  635. top = n;
  636. do {
  637. mid = (bottom + top) / 2;
  638. if (item < a[mid])
  639. top = mid - 1;
  640. else if (item > a[mid])
  641. bottom = mid + 1;
  642. } while (item != a[mid] && bottom <= top);
  643.  
  644. if (item == a[mid]) { printf("Binary search successfull!!\n"); printf("\n %d found in position: %d\n", item, mid + 1) }
  645. else {
  646. printf("\n Search failed\n %d not found\n", item);
  647. }
  648. getch();
  649. }
  650.  
  651.  
  652.  
  653.  
  654.  
  655.  
  656. //Output
  657.  
  658.  
  659.  
  660.  
  661.  
  662.  
  663.  
  664.  
  665.  
  666.  
  667.  
  668.  
  669.  
  670.  
  671.  
  672.  
  673.  
  674. /* Wap to implement bubble sort */
  675.  
  676. #include<stdio.h>
  677. #include<conio.h>
  678. void bsort(int [], int);
  679. void main() {
  680. int a[20],n,i;
  681. clrscr();
  682. printf("Enter number of elements");
  683. scanf("%d",&n);
  684. printf("Enter the array");
  685. for(i=0;i<n;i++) {
  686. scanf("%d",&a[i]);
  687. }
  688. bsort(a,n);
  689. printf("sorted elements\n");
  690. for(i=0;i<n;i++) {
  691. printf("%d\n",a[i]);
  692. }
  693. getch();
  694. }
  695. void bsort(int a[],int n) {
  696. int temp, i=1,j,flag=0;
  697. while(i<=n-1 && flag==0) {
  698. flag=1;
  699. for(j=0;j<=n-i-1;j++) {
  700. if(a[j]>a[j+1]) {
  701. temp=a[j];
  702. a[j]=a[j+1];
  703. a[j+1]=temp;
  704. }
  705. flag=0;
  706. }
  707. i=i+1;
  708. }
  709. }
  710.  
  711.  
  712. //Output
  713.  
  714.  
  715.  
  716.  
  717.  
  718.  
  719.  
  720.  
  721.  
  722.  
  723.  
  724.  
  725.  
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733. /*Wap to implement Quick Sort */
  734.  
  735. #include<stdio.h>
  736. #include<conio.h>
  737. int i,j,n,pivot,a[20];
  738. void quick(int a[],int left,int right);
  739. void swap(int a[],int i,int j);
  740. void main() {
  741. int n,a[20];
  742. textcolor(15);
  743. clrscr();
  744. printf("\n\nQUICK SORT");
  745. printf("\n\nEnter the limit : ");
  746. scanf("%d",&n);
  747. printf("\n\nEnter the element\n\n");
  748. for(i=0;i<n;i++) {
  749. scanf("%d",&a[i])
  750. }
  751. quick(a,0,n-1);
  752. printf("\n\nThe sorted list is \n\n");
  753. for(i=0;i<n;i++) {
  754. printf("%d ",a[i]);
  755. }
  756. getch();
  757. }
  758. void quick(int a[],int first,int last) {
  759. if(first<last) {
  760. pivot=a[first];
  761. i=first;
  762. j=last;
  763. while(i<j) {
  764. while(a[i]<=pivot&&i<last)
  765. i++;
  766. while(a[j]>=pivot&&j>first)
  767. j--;
  768. if(i<j){ swap(a,i,j); }
  769. }
  770. swap(a,first,j);
  771. quick(a,first,j-1);
  772. quick(a,j+1,last);
  773. }
  774. }
  775. void swap(int a[],int i,int j) {
  776. int temp;
  777. temp=a[i];
  778. a[i]=a[j];
  779. a[j]=temp;
  780. }
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.  
  793.  
  794.  
  795.  
  796.  
  797.  
  798.  
  799.  
  800.  
  801.  
  802.  
  803.  
  804.  
  805.  
  806.  
  807.  
  808.  
  809.  
  810.  
  811. //Output
  812.  
  813.  
  814.  
  815.  
  816.  
  817.  
  818.  
  819.  
  820.  
  821.  
  822.  
  823.  
  824.  
  825.  
  826.  
  827.  
  828.  
  829. /*Wap to implement merge sort */
  830.  
  831. #include<stdio.h>
  832. #include<conio.h>
  833.  
  834. void merge_split(int a[],int first,int last);
  835. void merge(int a[],int f1,int l1,int f2,int l2);
  836. int a[25],b[25];
  837.  
  838. void main() {
  839. int i,n;
  840. clrscr();
  841. printf("\n\nMERGE SORT");
  842. printf("\n\nEnter the limit : ");
  843. scanf("%d",&n);
  844. printf("\nEnter the elements\n");
  845. for(i=0;i<n;i++) {
  846. scanf("%d",&a[i]);
  847. }
  848. merge_split(a,0,n-1);
  849. printf("\n\nSorted list : ");
  850. for(i=0;i<n;i++) {
  851. printf("\n %d",a[i]);
  852. }
  853. getch();
  854. }
  855.  
  856. void merge_split(int a[],int first,int last) {
  857. int mid;
  858. if(first<last) {
  859. mid=(first+last)/2;
  860. merge_split(a,first,mid);
  861. merge_split(a,mid+1,last);
  862. merge(a,first,mid,mid+1,last);
  863. }
  864. }
  865.  
  866. void merge(int a[],int f1,int l1,int f2,int l2) {
  867. int i,j,k=0;
  868. i=f1;
  869. j=f2;
  870. while(i<=l1 && j<=l2) {
  871. if(a[i]<a[j])
  872. b[k]=a[i++];
  873. else
  874. b[k]=a[j++];
  875. k++;
  876. }
  877. while(i<=l1)
  878. b[k++]=a[i++];
  879. while(j<=l2)
  880. b[k++]=a[j++];
  881. i=f1;
  882. j=0;
  883. while(i<=l2 && j<k)
  884. a[i++]=b[j++];
  885. }
  886.  
  887.  
  888.  
  889.  
  890.  
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898.  
  899.  
  900.  
  901.  
  902.  
  903.  
  904.  
  905.  
  906. //Output
  907.  
  908.  
  909.  
  910.  
  911.  
  912.  
  913.  
  914.  
  915.  
  916.  
  917.  
  918.  
  919.  
  920.  
  921.  
  922.  
  923.  
  924.  
  925. /*Wap to implement insertion sort */
  926.  
  927. #include<stdio.h>
  928. #include<conio.h>
  929. void insertsort(int a[], int n) {
  930. int i,j,target;
  931. for(i=1;i<n;i++) {
  932. target=a[i];
  933. j=i-1;
  934. while((j>=0) && (target<=a[j])) {
  935. a[j+1]=a[j];
  936. j=j-1;
  937. }
  938. a[j+1]=target;
  939. }
  940. }
  941. void display(int a[], int n) {
  942. int i;
  943. for(i=0;i<n;i++) {
  944. printf("%d\n",a[i]);
  945. }
  946. }
  947. void main() {
  948. int a[20],n,i;
  949. clrscr();
  950. printf("Enter the total number of elements");
  951. scanf("%d",&n);
  952. printf("Enterthe elements\n");
  953. for(i=0;i<n;i++) {
  954. scanf("%d",&a[i]);
  955. }
  956. insertsort(a,n);
  957. printf("\n Array elements after sorting\n");
  958. display(a,n);
  959. getch();
  960. }
  961.  
  962.  
  963. //Output
  964.  
  965.  
  966.  
  967.  
  968.  
  969.  
  970.  
  971.  
  972.  
  973.  
  974.  
  975.  
  976.  
  977.  
  978.  
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985. /*Wap to implement selection sort */
  986.  
  987. #include<stdio.h>
  988. int main() {
  989. int s,i,j,temp,a[20];
  990. clrscr();
  991. printf("Enter total elements: ");
  992. scanf("%d",&s);
  993. printf("Enter %d elements: ",s);
  994. for(i=0;i<s;i++) {
  995. scanf("%d",&a[i]);
  996. }
  997. for(i=0;i<s;i++) {
  998. for(j=i+1;j<s;j++) {
  999. if(a[i]>a[j]) {
  1000. temp=a[i];
  1001. a[i]=a[j];
  1002. a[j]=temp;
  1003. }
  1004. }
  1005. }
  1006. printf("After sorting is: ");
  1007. for(i=0;i<s;i++) {
  1008. printf(" %d",a[i]);
  1009. }
  1010. getch();
  1011. }
  1012.  
  1013.  
  1014.  
  1015.  
  1016.  
  1017.  
  1018.  
  1019.  
  1020.  
  1021.  
  1022. //Output
Advertisement
Add Comment
Please, Sign In to add comment