هافمن

در زمینه ی فشرده سازی در علوم رایانه روش های زیادی از جمله (( Lempel Ziv Welch)) و ((هافمن)) وجود دارد. اولی در 7zip به کار رفته که نرم افزار فشرده سازی تحت لیسانس ((LGPL)) است. در روش هافمن ابتدا (مثلا برای فشرده سازی در یک متن ) نسبت تعداد حروف الفبا به کل حروف متن بدست آمده سپس به هر حرف یک کد اختصاص می یابد. شیوه ی اختصاص این کد به این شکل است که هر حرفی تعداد وقوع بیشتری در کل متن را دارد کد کوچکتری به آن داده می شود.

در برنامه ی زیر که به زبان جاوا نوشته شده است از سه پکیج و 5 فایل جاوا که شامل پکیجی برای مواقع وفوع خطا و  پکیج binarytree که شامل 3 کلاس binarynode و tree و queue   است. و در پکیج کد که شامل کلاس form  می باشد که تعداد تکرار حروف را بررسی کرده و شروع به ساخت درحت هافمن از طریق بررسی احتمال وقوع حروف و سپس merg کردن درخت ها و گره های ایجاد شده تا در نهایت درخت هافمن اصلی ساخته شده و آن را در جدولی مه بر حسب حروف آمده در متن داده شده است؛ قرار می دهد .

برای دادن نشانی فایل متنی به برنامه ابتدا دکمه ی<<نمایش کد هافمن>> فشارد داده و سپس در پیغام ظاهر شده در صفحه آدرس فایل به صورت کامل نوشته شود. در نهایت جدولی آماده!

در لینک زیر فایل zip که با اجرای آن خود به خود از حالت zip خارج می شود (متشکرم 7zip) و شما می توانید در یک محیط مانند netbeans آن را تغییر دهید و با استفاده از امکان build فایل jar قابل اجرا را بسازید.

http://www.adrive.com/public/6ddb730fd1bcd3fccf2ad525d850678c2f951556af92c918fcc033363f5173a3.html

منابع :آب! ، ویکی پدیا و خودم برای نوشتن کد .

BST

در قسمت زیر کد یکی از مهمترین قسمت های ساختمان داده نوشته شده به زبان جاوا (چندان فرقی با سی++ ندارد به جز کلاس BinaryNode که باید لینک های چپ و راست در سی++ از نوع اشاره گر باشند)

این کلاس شامل متدهایی برای حذف /اضافه و جستجو و می توان با اضافه کردن متدی که درخت را به صورت میان ترتیب(inorder) طی می کند یک جستجو و مرتب سازی بسیار سریع را داست چراکه در حالت متوسط و در بدترین حالت تنها دارای هزینه ی nlogn است و تنها بدی آن مقدار حافظه ی مصرفی یعنی n،تعداد گره ها، می باشد .

 

class BinaryNode<T> {
BinaryNode right;
BinaryNode left;
T value;
BinaryNode parent;

BinaryNode(T value,BinaryNode left,BinaryNode right,BinaryNode parent){
    this.right=right;
    this.left=left;
    this.value=value;
    this.parent=parent;
}
BinaryNode(){
    this(null,null,null,null);
}
}
public class BSTree {
   private BinaryNode root;
   public  BSTree(){
        root=null;
    }
   public void insert(Comparable x){
       root=insert(x,root,root);
      
   }
   private Object find(Comparable x, BinaryNode root) {
        if(root==null)
            return null;
        Object p = null;
        if(x.compareTo(root.value)>0)
            p=find(x,root.right);
        else if(x.compareTo(root.value)<0)
            p=find(x,root.left);
        else if(x.compareTo(root.value)==0)
            p=root.value;
            else
                System.out.print(“Item not founs!”);
        return p;
    }
   private BinaryNode insert(Comparable x, BinaryNode root,BinaryNode p) {
    if(root==null)
        root=new BinaryNode(x,null,null,p);
    else if(x.compareTo(root.value)>0)
        root.right=insert(x,root.right,root);
    else if(x.compareTo(root.value)<0)
        root.left=insert(x,root.left,root);
   
   
    return root;
    }
   private void remove(Comparable x){
        root=remove(x,root);
    }
   private BinaryNode remove(Comparable x, BinaryNode root) {
    if(root==null)
        return root;
    else if(x.compareTo(root.value)>0)
        root.right=remove(x,root.right);
    else  if(x.compareTo(root.value)<0)
        root.left=remove(x,root.left);
    else if(x.compareTo(root.value)==0){
        if(root.left==null)
            root=root.right;
        if(root.right==null)
            root=root.left;
        else{
        root.value=rightmost(root.left);
            root.left=removmost(root.left);
       }
    }
    return root;
   
    }
   private BinaryNode removmost(BinaryNode root) {
       if(root.right==null)
           return root.left;
       else
           root=removmost(root.right);
       return root;
    }
   private Object rightmost(BinaryNode root) {
    if(root.right==null)
        return root.value;
    else
        return rightmost(root.right);
    }
   public Object find(Comparable x){
        return find(x,root);
    }public void print(){
        print(root, 1);
    }
    private void print(BinaryNode root, int depth){
       
        for(int i=1; i<depth; i++)
            System.out.print(“  “);
        if(root == null){
            System.out.println(“null”);
            return;
        }
        if(root.parent!=null)
        System.out.println(root.value+ ” , parent”+root.parent.value);
        else
            System.out.println(root.value);
        print(root.left, depth+1);
        print(root.right, depth+1);
          }
        //System.out.println(“1111″);
  public static void  main(String []args){
        BSTree t=new BSTree();
        for(int i=0;i<10;i++)
        t.insert(Math.round(Math.random()*1000));
        t.print();
       
       
    }
   
}
 

فایل در جاوا

کار با فایل در جاوا بسیار راحت است چون تعداد زیادی کلاس کار با فایل در جاوا وجود دارد از جمله:

FileOutputStream file=new FileOutputStream(“path\\filename”,true);

در فایل بالا یک جریان به  فایل در محل path و نام filename برای نوشتن ایجاد شده و true درآخر سازنده به این موضوع اشاره دارد که اگر فایل وجود داشت در ادامه ی فایل شروع به نوشتن نماید . در این حالت شما برای نوشتن در فایل از متد write استفاده می کنید .

متد write یک آرایه از بایتها را برای نوشتن در فایل می پذیرد .برای نوشتن String در فایل می توان از روش زیر استفاده نمود :

String str=”java”;

file.write(str.getbytes());//تبدیل رشته به آرایه از بایتها

کلاس دیگری برای نوشتن وجود دارد RandomAccesFile می باشد که بری نوشتن درمحل دلخواه در فایل عالی است . مثلا نوشن در میانه ی فایل . شیوه تعریف آن به صورت :

RandomAccessFile file_=new RandomAccessFile(“path:\\filename”,”rw”);

که rw نمایانگر نوشتن و خواندن در فایل است که سایر رشته های قابل پردازش برای این قسمت عبارت است از :   r-فقط خواندن     W-فقط نوشتن  rw- خواندن و نوشتن است .

در جاوا واسط های InputStream ,OutputStream وجود دارند که FileOutput/InputStream از این واسط ها مشتق می شوند. دو نوع کلاس Writer/Reader وجود دارد که قابلیت ها زیادی دارند . که برای بعد!

 

 

انواع روش های خواندن/ نوشتن ، از/در یک فایل در سی++ و جاوا

انواع روش های خواندن/ نوشتن ، از/در یک فایل در سی++ و جاوا:

1.        در   سی++ :

ابتدا باید Header File ، fstream.h را وارد نموده و سپس می توان از موارد زیر به تناسب استفاده کرد:

ftream  <یک اسم برای جریان>)”<اسم و مسیر فایل>“,mode_open | attribute);

Mode_open :

                ios::binary         //اینکه فایل در مد باینری باز شود

            ios::in             //اینکه جریان در مد ورودی باز شود

            ios::nocreat //اگر فایل وجود دارد عمل باز کردن با شکست مواجه شود

            ios::out      //جریان در مد خروجی باز می شود

ios::trunk    //اگر فایل محتوی اطلاعات باشد (در مد نوشتن)،اطلاعات پاک شده و از ابتدا در فایل اطلاعات را می ریزد               ios::app     //در(مد نوشتن)در ادامه ی فایل شروع به نوشتن می کند

برای مثال :

fsream  file(“help.txt” , ios::out | ios::app |ios::in);

که در آن یک جریان خروجی در یک فایل باز نموده و در ادامه ی فایل شروع به نوشتن (با استفاده از دستورات پیش رو) مینماید توجه داشته باشد که علامت | برای OR نمودن حالت  مختلف می باشد.

 برای نوشتن/خواندن می توان از عملگر های >> و << استفاده کرد و یا از دستورات write و read  استفاده نمود.

istream & read(unsigned char *buff,int num);

ofstream& write(unsigned char* buff,int num);

که در آن buff آرایه ای از کاراکترهاست که می توان با استفاده از آن خواند یا نوشت و num تعداد بایت خوانده/نوشته شده می باشد .

مثال :

char buffer[1024];تعریف یک آرایه از کاراکتر ها//

file.read(buff,1024);قرار دادن 1024بایت اول فایل در آرایه ی فوق//

استفاده از دستورات put() و get() برای نوشتن به صورت تک کاراکتری:

file.put(‘k’);

char ch= file.get();

 جاوا بعدا!

 

 

                                                                                                                                                                     

 

برنامه نمایش عکس با جاوا

درباره برنامه گرافیکی با جاوا فیلا صحبت کردم این یک نمونه از این برنامه هاست :

با استفاده از یک کلاس که با استفاده از خاصیت ارث بری در جاوا از فوق کلاس  JFrame ارث برده و ایجاد یک کلاس panel که این نیز از کلاس JPanel ارث برده و یک آرایه ی رشته ای از نام فایلهایی که می خواهیم نمایش دهیم؛ کار به آسانی انجام می شود برای آشنایی با کلاس ها نام آنها در Import ذکر شده است )

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.Timer;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JPanel;

/**
 *
 * @author eprogrammer
 */
public class NewClass extends JFrame {
    public NewClass(){
        try {
            final panel p = new panel();
            this.add(p);
            this.setSize(800, 600);
            this.setVisible(true);
            this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            for(int i=0;i<16;i++)
            {p.start(i);
            p.updateUI();
            Thread.sleep(1000 / 15);
            }
        } catch (InterruptedException ex) {
            Logger.getLogger(NewClass.class.getName()).log(Level.SEVERE, null, ex);
        }
       
    }
    public static void main(String []args) throws IOException{
       NewClass n=new NewClass();
    }
}
class panel extends JPanel{
    String str1;
    int counter=0;
    Image img;
    private Timer timer = new Timer();
    private BufferedImage i;
    panel(){
      
        this.setSize(10,10);
        this.setMaximumSize(new Dimension(100,100));
      }
  @Override
    public void paint(final Graphics g){
        g.clearRect(0,0, 800, 800);
        g.drawImage(img, 0, 0, null);
    }
   public void st(String str){
        try {
            Image image = ImageIO.read(new File(str));
            img = image;
            this.repaint();
        } catch (IOException ex) {
            Logger.getLogger(panel.class.getName()).log(Level.SEVERE, null, ex);
        }
   }
   public void start(int i) {
       String ImageArray[]={
           “001″,”002″,”003″,”004″,”005″,”006″,”007″,”008″,”009″,”010″,”011″,”012″,”013″,”014″,”015″,”016″,
           “017″,”018″,”019″,”020″,”021″,”022″,”023″,”024″,”025″,
       };
       try {
            Image image = ImageIO.read(new File(“DriveLetter:/FolderName/”+ImageArray[i]+/*extension*/”.jpg”));
            img=image;
            this.repaint();
        } catch (IOException ex) {
            Logger.getLogger(panel.class.getName()).log(Level.SEVERE, null, ex);
        }
     
    }
}

کار با فایل در سی++

برای کار با فایل در سی++ راه های زیادی وجود دارد که یادگیری همه ی مفید است . بهتر از برای کار با فایل در مراحل اول با یک یا دو نوع کلی مار کرد و بعد از مهارت پیدا کردن در این زمینه به سراغ سایر روش ها بروید .

در اینجا بک برنامه ی ساده که از کابر تعدادی اسم می گیرد و در یک فایل می ریزد (با ترتیبی معکوس)و دوباره از فایل می خواند(باز هم با ترتیبی معکوس) و…(بقیه اش رو خودتون بخوانید):

#include <iostream.h>
#include <conio.h>
#include <fstream.h>
#include <cstring.h>

void swap(string &r,string &t){
 string o=r;
 r=t;
 t=o;
 }
 void print(string *str){
        for(int q=0;str[q]!=NULL;q++)
    cout<<str[q]<<” “;
         cout<<endl;
 }
main(){

fstream file_1(“c:/file1.txt”,ios::in|ios::out);
string *str_1=new string[100];
string *str_2=new string[100];
string name;
int s=0;
while(true){
cin>>name;
if(name[0]==’$')
 break;
//for(int i=0;i<name.length();i++)
 str_1[s]=name;
   s++;
  // file_1<<endl;
  // cout<<endl<<name;
}//end while I
//————-revers——————–
 for(int i=0;i<s;i++)
   str_2[s-i-1]=str_1[i];
  for(int i=0;i<s;i++)
  file_1<<str_2[i]<<endl;
file_1.close();
for(int i=0;i<s;i++)
 str_1[i]=str_2[i]=’ ‘;
//——————————————
cout<<”while <I> was ended”<<endl<<endl;
//——————————————
ifstream file_3(“c:/file1.txt”);
ofstream file_2(“c:/file2.txt”);
s=0;
while(!file_3.eof()){
getline(file_3,name);
 str_1[s++]= name;
 for(int i=0;i<s;i++)
   str_2[s-i-1]=str_1[i];

   //cout<<name;
 }
 for(int i=0;i<s;i++)
  file_2<<str_2[i]<<endl;
 file_2.close();
 file_3.close();
 //—————————————–
 cout<<”end while <II>”<<endl<<endl;
 ifstream file_4(“c:/file2.txt”);
 while(!file_4.eof()){
  getline(file_4,name);
  cout<<name<<endl;
 }
 file_4.close();
 //====================sort===============
 ifstream file_5(“c:/file2.txt”);
 int size=0;
 fstream file_6(“c:/file3.txt” ,ios::in|ios::out);
 int n=100;
 string *str=new string[n];
 int i=0    ;
 while(!file_5.eof()) {
 getline(file_5,str[i++]);
 size++;
 //file_6<<str[i]<<endl ;
 //cout<<str[i++]<<endl ;
 if(i==n){
  n*=2;
  string *str_1=new string[n];
   for(int r=0;r<(n/2);r)
    str_1[r]=str[r];
   str=str_1;
 }
 }
// for(int p=0;str[p]!=NULL;p++)
  //  cout<<str[p]<<endl;
// bool b=true ;
 int u=0;
 for(int t=0;t<size-1;t++)  {
  for(int i=0;i<size-1;i++)
  if(str[i]>str[i+1])
    {
       swap(str[i],str[i+1]);
       /*string o=str[i+1];
       str[i+1]=str[i];
       str[i]=o;                                              
       */
     // for(int q=0;str[q]!=NULL;q++)
    // cout<<str[q]<<” “;
       //  cout<<endl;
        print(str);

      }
 }
  for(int i=0;i<size;i++)
   file_6<<str[i]<<endl;

 getch();

}

 

 

جاوای گرافیکی

زمان زیادی از ارایه ی جاوا گذشته و خیلی ها علاقه دارند که برنامه هاشون رو به صورت گرافیکی بنویسند . در جاوا می توانیم از دو روش برای ایجاد برنامه های گرافیکی استفاده کینیم یکی اینکه از محیطهای برنامه نویسی گرافیکی مثل NetBeans,Eclipse,Borland استفاده کنیم یا  اینکه به صورت دستی تمام کد های لازم رو بنویسیم (سخته ، نه؟!).

در روش اول شما بهد از تعیین نوع برنامه از قبیل(Application,Panel,Frame,…) فقط نماد های Component هایی  رو که می خواهید  داخل برنامه باشه رو می کشید و می اندازید توی صفحه (+یک لیوان آب از نوع خنک) و با کلیک راست روی اونها و انتخاب Event فعالیت مناسب رو برای اون در نطر می گیرید  و ویژگی های هر یک را تعیین می کنید.

در روش دوم اولا باید صفحه ی اصلی و سپس تمام Component  ها را طراحی و با استفاده از کد طرز قرار گیری آنها و اندازه و … را تعیین کنید .(اوووووووه خسته شدم ).مثلا:

public class MyFrame extens JFrame{

public MyFrame(){

setSize(300,300);
setVisible(true);

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

setTitle(“MyFrame”);

}

public static void main(String []args){

MyFrame my=new MyFrame():

}

}

یکی از محیط های مناسب برای روش آول استفاه از http://www.netbeans.org هست .امتحان کنید.

یک منبع خوب برای یادگیری زبان جاوا :

http://www.amazon.com/s?ie=UTF8&field-keywords=%26%2334%3Bcore%20java%26%2334%3B&page=1

 

Vevtor

 

سلام !
با وجود اینکه  جاوا کلاس Vector  را دارا می باشد اما خب پیاده سازی آن به روش دلخواه مفید است .
(زیاد حرف نمی زنم برنامه ببنید

/*package Matrix*/
import java.lang.Exception;
import java.lang.NullPointerException;
public class Vector<T> {
    private int size=80;
    protected T [] cont;
     protected int low=0,high=0,pos=0;
 
    //=================init with no parameter===============
   protected void init(){
       low=pos=0;
       high=size;
       high++;
       try{
                cont=(T[])new Object[high];
          }catch(NullPointerException exc){
        System.out.println(“nul pointer Exception”);
      }
        for(Integer i=low;i<high;i++)
            cont[i]=null;
   }
   
   //===================init with low par.=================
    protected void init(int l){
    low=pos=l;
   
    high=size;
    high++;
    if(low>high)
            throw new  NullPointerException();
        try{
         cont=(T[])new Object[high];
           }catch(NullPointerException exc){
        System.out.println(“nul pointer Exception”);
           }
        for(Integer i=low;i<high;i++)
            cont[i]=null;
    }
//===================int with two parameter===================
    protected void init(int l,int h){
       low=pos=l;
      
       high=h;
       high++;
        if(low>high)
            throw new  NullPointerException();
       if(high>size)
           size=high;
    try{
          cont=(T[])new Object[high];
       }catch(NullPointerException exc){
        System.out.println(“nul pointer Exception”);
       }
        for(Integer i=low;i<high;i++)
            cont[i]=null;
    }
//====================add element at pos i=====================   
    public T addelement(T e,int p)
    {
     //  if(p > pos || p < low)
    if(p<low)      
       throw new ArrayIndexOutOfBoundsException(p);
      // else
        //{ 
             cont[p]=e;
             pos++;
        //}
       return e;
       
    }
   
    public int currentsize(){
        return this.size;
    }
   
   
    /** Creates a new instance of Vector */
 
   
   
    public Vector(int l,int h) {
    try{
    init(l,h);
    }catch(NullPointerException exc){
        exc.printStackTrace();
        return ;
    }

    }
    public Vector(int l){
    
     init(l);
    }
   
    //=======================contstructor===============
    public Vector(){
    
         init();
    }
    //=====================constructor====================
   
    public  Vector(Vector<T> ob){
        this.high=ob.high;
        this.low=ob.low;
        for(int i=low;i<=high;i++)
        {
      try{
             this.cont[i]=ob.cont[i];
         }catch(NullPointerException exc){
          exc.printStackTrace();return ;  
         }
        }
       
    }
//——————low and high————————–   
   public  int hi(){
        return this.high;
   }
   public int lo(){
       return this.low;
   }
//——————return element at i pos—————————–
   public T reap(int i) throws ArrayIndexOutOfBoundsException//return element at position i;
   {
      if(i>this.high || i<this.low)
          throw new ArrayIndexOutOfBoundsException();
      return cont[i];
   }
  
    public T reap(int i,T e) throws ArrayIndexOutOfBoundsException//return element at position i;
   {
      if(i>this.high || i<this.low)
          throw new ArrayIndexOutOfBoundsException();
      return cont[i];
   }

   public int size()
   {
       return this.size;
   }

}

class Grater extends Exception{
   public  Grater(){
         System.out.println(“your Domain have Error!\n The low is Grater Than High “);
   }
 
}

4 !

سلام !
اول بگم که پست قبلی برنامه ی اصلی ایراد داشت که من درستش کردم و نوشتم .
حالا :

برنامه ی BST : با شیوه ی جالبی پیاده سازی شده  و با تکنیک Generic  نوشته شده که از کلاس Comparable ارث برده .
متد های insert , remove را اینجا می نویسم . متهد های عمومی insert , remove  برعهده ی خواننده ی متن .

 import java.io.*;
import java.util.NoSuchElementException;
class BinaryNode<T extends Comparable> {
  T data;
  protected int Visited;
   BinaryNode<T> right,left;
  BinaryNode ( ) {
    this.data =null;
    right=left=null;
    Visited=0;
    }
}

class BinaryTree<T extends Comparable> {
 
    private  BinaryNode root;
    public  BinaryTree(){
       root=null;
}
  
  private static<T extends Comparable> 
  BinaryNode<T> insert ( BinaryNode tree, T data ) throws DuplicatItem {
    if ( tree == null ) {
      tree = new BinaryNode<T> ( data,null,null );
   
    }
    else {
      int dir = data.compareTo ( tree.data ) > 0 ? 1 : 0;
     
      if(dir<0)
          tree.left=insert(tree.left,data);
      
      else if(dir>0)
          tree.right=insert(tree.right,data);
      else
          throw new DuplicatItem(“Search Tree : insert”);
    }
    return tree;
 }
 
  private<T extends Comparable>
  BinaryNode<T> remove( BinaryNode tree, T data ) {
    if ( tree == null )
            throw new NoSuchElementException(“” +
                    “remove: No element to remove”);
  if(data.compareTo(tree.data)<0)
      tree.left=remove(tree.left,data);
  else if(data.compareTo(tree.data)>0)
      tree.right=remove(tree.right,data);
  else if(data.compareTo(tree.data)==0){
      if(tree.left==null)
        tree=tree.right;
      else if(tree.right==null)
          tree=tree.left;
  }
  else{
        Comparable replacewithvalue=rightMax(tree.left);
        tree.data = (T) replacewithvalue;
        tree.left= deletetrightMax(tree.left);
  }
    return tree;
   
  }

پیمایش پیش ترتیب !

سلام

اگر ساختمان داده داشته باشيد حتما به به پيمايش هاي پيش ترتيب و پس ترتيب و ميان ترتيب بر خورد كرده ايد . براي نوشتن آنها در صورت استفاده از c/c++ يا Java از كلاس(سی ++ و جاوا) و struct  در سي براي پياده سازي استفاده مي كنيد .
به اين صورت كه يك كلاس TreeIterator (مثلا) استفاده مي كنيد و با استفاده از ارث بري  كلاسی ديگر با عنوان PostOrder یا InOrder یا 
PreOrder ساخته  که با استفاده از یک پشته و یک کلاس و یک شمارنده این عمل را انجام دهیم .
همان طور که می بینید یک پروسه ی طولانی و حتما با اشتباهات فراوان همراه است اما جند روز پیش در یک وبلاگ روشی جالب دیدیم که بدین شرح بود :

نکته : این برنامه به زبان جاواست که با اندکی تغییر برای سی++ قابل استفاده است .

 void nonrecpreorder(BinaryTree tree){
      BinaryNode currnode=tree.root;// یک گره ایجاد و مقدار آن را برابر ریشه ی درخت قرار می دهد
      while(true){                                     // یک حلقه ی بی نهایت
          if(currnode==null)                     // این شرط برای چیست؟
              break;
          //int visited=0 in the BinaryTree defined ! 
          if(currnode.left!=null && currnode.Visited!=1) //
           currnode=currnode.left;
          else if(currnode.right!=null && currnode.right.Visited!=1)
            currnode=currnode.right;
                else if(currnode.Visited==0)
                    {
                    // element defined like :      T element   //in BinaryTree
                     System.out.print(currnode.element+ ” “);
                    currnode.Visited=1;
                    }
          else
          {
                            currnode=currnode.parent;
          
           }
      }          
  }

جالب بود نه !