დასტის დალაგება რეკურსის გამოყენებით


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Goldman Sachs IBM კულიზა Yahoo
Recursion დასტის

პრობლემის განცხადება

პრობლემა "დასტის დალაგება რეკურსის გამოყენებით" აცხადებს, რომ თქვენ გეძლევათ ა დასტის მონაცემთა სტრუქტურა. დალაგება მისი ელემენტები რეკურსის გამოყენებით. დასტის მხოლოდ ქვემოთ ჩამოთვლილი ფუნქციების გამოყენებაა შესაძლებელი -

  • ბიძგი (ელემენტი) - ელემენტის დასტის ჩასმა.
  • pop () - pop () - მოცემული დასტის ზედა ნაწილში არსებული ელემენტის ამოღება / წაშლა.
  • isEmpty () - იმის შესამოწმებლად, არის თუ არა რაიმე ელემენტი დასტაში, თუ არა.
  • top () - მოცემული სტეკის ზედა ნაწილში ელემენტის თვალიერება / დანახვა.

დასტის დალაგება რეკურსის გამოყენებით

მაგალითი

9 4 2 -1 6 20
20 9 6 4 2 -1

განმარტება: ვინაიდან დასტა დალაგებულია ზრდადი თანმიმდევრობით. მაქსიმალური ელემენტი მოდის ზედა ნაწილში. იმის გამო, რომ სტეკი არის LIFO მონაცემთა სტრუქტურა, გამოცემა, როგორც ჩანს, კლებადობით არის.

2 1 4 3 6 5
6 5 4 3 2 1

ალგორითმი

  1. ინიციალიზაცია ა დასტის და მასში არსებული ელემენტები.
  2. შექმენით ფუნქცია, რომ ელემენტები დახარისხებული თანმიმდევრობით ჩასვათ სტეკში, რომელიც პარკად იღებს ელემენტს და ელემენტს. შეამოწმეთ ცალი ცარიელია თუ მოცემული ელემენტი უფრო მეტია, ვიდრე სტეკის ზედა ნაწილში, დააჭირეთ ელემენტს სტეკში და დააბრუნეთ.
  3. შექმენით დროებითი ცვლადი და შეინახეთ მასში დასტის ზედა ნაწილი. განათავსეთ ელემენტი დასტის ზედა ნაწილში და გააკეთეთ რეკურსიული ზარი თავად ფუნქციისკენ. დროებითი ცვლადი დააჭირეთ სტეკს.
  4. ანალოგიურად, შექმენით ფუნქციის დალაგება (), რომელიც სტეკს მიიღებს როგორც პარამეტრი. შეამოწმეთ თუ დასტა ცარიელი არ არის, შექმენით x ცვლადი და შეინახეთ მასში დასტის ზედა ნაწილი. განათავსეთ ელემენტი დასტის ზედა ნაწილში. რეკურსიული ზარი თავად ფუნქციაზე. დაურეკეთ ფუნქციას, რომ ელემენტები დალაგებული თანმიმდევრობით ჩასვა სტეკში.
  5. დარეკეთ დახარისხების ფუნქციაში მთავარ () -ში.
  6. შექმენით ფუნქცია დახარისხებული სტეკის დასაბეჭდად, რომელიც პარკს მიიღებს პარამეტრად. გადაკვეთა, სანამ დასტა ცარიელი არ არის, დაბეჭდეთ დასტის მონაცემები და გადადით შემდეგ ელემენტზე.

კოდი

C ++ პროგრამა დასტის დასალაგებლად რეკურსის გამოყენებით

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

ჯავის პროგრამა დასტის დასალაგებლად რეკურსის გამოყენებით

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

სირთულის ანალიზი

დროის სირთულე

O (N ^ 2) სადაც n არის ელემენტთა რაოდენობა სტეკში. რადგან, როდესაც ელემენტს სტეკში ვაჭერთ, შეიძლება დასრულდეს ყველა ელემენტის ამოღება, რომლებიც ამჟამად არის სტეკში და შემდეგ ჩავსვამთ მას. ეს შემთხვევა წარმოიშობა, თუ შეყვანა მცირდება თანმიმდევრობით.

სივრცის სირთულე

O (N) რადგან ჩვენ ვიყენეთ დასტის სივრცე n ელემენტისთვის. ელემენტების ამოღებისას ჩვენი ამჟამინდელი ელემენტის განთავსება. ჩვენ მოგვიწია შენახული ელემენტების შენახვა, რაც სივრცის ხაზოვან სირთულეს გვაძლევს.