算法设计：间隙缓冲区数据结构

2021年3月11日17:02:58 发表评论 1,209 次浏览

本文概述

间隙缓冲是数据结构用于编辑和存储文字以一种有效的方式目前正在编辑。它也类似于数组, 但是在数组中引入了一个空白用于处理光标处的多个更改。假设间隙为另一个包含空白的数组。

间隙缓冲区数据结构1

例子：考虑一个初始间隙大小为10的示例, 最初, 数组或间隙的大小相同, 因为我们在数组中插入元素的方式类似, 元素将插入间隙缓冲区中, 唯一的区别是每次插入时间隙大小都会减小。

间隙缓冲区数据结构2

这是在前面插入字符的基本情况。现在, 每当需要在某个位置插入字符时, 我们将使用以下命令将间隙向上移动到该位置剩下()和对()然后尝试插入字符。

需要间隙缓冲区

数组是一种数据结构, 用于将项目存储在连续的内存位置。但是, 它需要在数组末尾插入O(1), 而在前面则需要O(n)时间, 因为该数组将向右移动n个位置, n是数组的长度。

当涉及到文本编辑器时, 我们需要一种更快的数据结构来进行插入和修改, 因为光标位置存在多个更改。

在最坏的情况下, 数组将花费O(n)时间进行插入或修改, 如下例所示。

为了在前面插入" GEEKS", 通过移动数组留出了用于插入每个字符的空间。

间隙缓冲区数据结构3

Gap Buffer中的基本操作

insert()：这是一个用于在给定位置将字符插入文本的过程。它首先检查间隙是否为空, 如果发现间隙为空, 则调用过程grow()并调整间隙的大小, 现在可以插入元素了。

剩下() ：

这是用于将光标向左移动的过程, 该光标点用作更改位置。

间隙缓冲区数据结构4

对：

这是用于将光标向右移动的过程, 该光标点用作更改位置。

间隙缓冲区数据结构5

增长：

这是在间隙大小变为零时使用的过程, 因此我们需要通过在所需位置插入间隙来调整数组的大小。

间隙缓冲区数据结构6

间隙缓冲vs绳索

现在, 尽管其插入需要O(1)时间, 但是还有另一个功能增长()这大约需要O(n)时间。因此, 可能会认为这可能与绳索数据结构但是增长的成本正在由摊销其他更便宜的过程(例如left(), right()和insert())的成本。因此, 此数据结构在文本编辑器中比其他诸如绳因为它易于实现。

实现间隙缓冲区

C ++

// C++ program of implementation of gap buffer
  
#include <bits/stdc++.h> 
using namespace std; 
  
char buffer[50]; 
int gap_size = 10; 
int gap_left = 0; 
int gap_right = gap_size - gap_left-1; 
int size = 10; 
  
// Function that is used to grow the gap 
// at index position and return the array 
  
  
void grow( int k, int position) 
{ 
  
     char a[size]; 
  
     // Copy characters of buffer to a[] 
     // after position 
     for ( int i = position; i < size; i++) { 
         a[i - position] = buffer[i]; 
          
     } 
      
     // Insert a gap of k from index position 
     // gap is being represented by '-' 
     for ( int i = 0; i < k; i++) { 
         buffer[i + position] = '_' ; 
     } 
      
     // Reinsert the remaining array 
     for ( int i = 0; i < position + k; i++) { 
         buffer[position + k + i] = a[i]; 
     } 
  
     size += k;
     gap_right+=k;
} 
  
// Function that is used to move the gap 
// left in the array 
void left( int position) 
{ 
     // Move the gap left character by character 
     // and the buffers 
     while (position < gap_left) { 
         gap_left--; 
         gap_right--; 
         buffer[gap_right+1] = buffer[gap_left];
         buffer[gap_left]= '_' ;
     } 
} 
  
// Function that is used to move the gap 
// right in the array 
void right( int position) 
{ 
     // Move the gap right character by character 
     // and the buffers 
     while (position > gap_left) { 
         gap_left++; 
         gap_right++; 
         buffer[gap_left-1] = buffer[gap_right]; 
         buffer[gap_right]= '_' ;
     } 
} 
  
// Function to control the movement of gap 
// by checking its position to the point of 
// insertion 
void move_cursor( int position) 
{ 
     if (position < gap_left) { 
         left(position); 
     } 
     else { 
         right(position); 
     } 
} 
  
// Function to insert the string to the buffer 
// at point position 
void insert(string input, int position) 
{ 
     int len = input.length(); 
     int i = 0; 
  
     // If the point is not the gap check 
     // and move the cursor to that point 
     if (position != gap_left) { 
         move_cursor(position); 
     } 
  
     // Insert characters one by one 
     while (i < len) { 
         // If the gap is empty grow the size 
         if (gap_right == gap_left) { 
             int k = 10; 
             grow(k, position); 
         } 
  
         // Insert the character in the gap and 
         // move the gap 
         buffer[gap_left] = input[i]; 
         gap_left++; 
         i++; 
         position++;
     } 
} 
  
// Driver code 
int main() 
{ 
     // Initializing the gap buffer with size 10 
     for ( int i = 0; i < 10; i++) { 
         buffer[i] = '_' ; 
     } 
  
     cout << "Initializing the gap buffer "
          << "with size 10" << endl;
   
     for ( int i = 0; i < size; i++) { 
         cout << buffer[i]<< " " ; 
     } 
  
     cout << endl; 
  
     // Inserting a string to buffer 
     string input = "GEEKSGEEKS" ; 
     int position = 0; 
  
     insert(input, position); 
  
     cout << endl; 
     cout << "Inserting a string to buffer"
          << ": GEEKSGEEKS" << endl; 
     cout << "Output: " ; 
     for ( int i = 0; i < size; i++) { 
         cout << buffer[i]<< " " ; 
     } 
  
     input = "FOR" ; 
     position = 5; 
  
     insert(input, position); 
  
     cout << endl; 
     cout << endl; 
      
     cout << "Inserting a string to buffer"
          << ": FOR" << endl; 
     cout << "Output: " ; 
     for ( int i = 0; i < size; i++) { 
         cout << buffer[i]<< " " ; 
     } 
  
  
     return 0;
}

Java

// Java program of implementation of gap buffer 
import java.util.*;
class GFG 
{ 
static char []buffer = new char [ 50 ]; 
static int gap_size = 10 ; 
static int gap_left = 0 ; 
static int gap_right = gap_size - gap_left - 1 ; 
static int size = 10 ; 
  
// Function that is used to grow the gap 
// at index position and return the array 
static void grow( int k, int position) 
{ 
     char []a = new char [size]; 
  
     // Copy characters of buffer to a[] 
     // after position 
     for ( int i = position; i < size; i++) 
     { 
         a[i - position] = buffer[i]; 
     }
      
     // Insert a gap of k from index position 
     // gap is being represented by '-' 
     for ( int i = 0 ; i < k; i++) 
     { 
         buffer[i + position] = '_' ; 
     } 
      
     // Reinsert the remaining array 
     for ( int i = 0 ; i < k; i++) 
     { 
         buffer[position + k + i] = a[i]; 
     } 
  
     size += k; 
     gap_right += k; 
} 
  
// Function that is used to move the gap 
// left in the array 
static void left( int position) 
{ 
     // Move the gap left character by character 
     // and the buffers 
     while (position < gap_left)
     { 
         gap_left--; 
         gap_right--; 
         buffer[gap_right + 1 ] = buffer[gap_left]; 
         buffer[gap_left]= '_' ; 
     } 
} 
  
// Function that is used to move the gap 
// right in the array 
static void right( int position) 
{ 
      
     // Move the gap right character by character 
     // and the buffers 
     while (position > gap_left)
     { 
         gap_left++; 
         gap_right++; 
         buffer[gap_left - 1 ] = buffer[gap_right]; 
         buffer[gap_right]= '_' ; 
     } 
} 
  
// Function to control the movement of gap 
// by checking its position to the point of 
// insertion 
static void move_cursor( int position) 
{ 
     if (position < gap_left)
     { 
         left(position); 
     } 
     else 
     { 
         right(position); 
     } 
} 
  
// Function to insert the string to the buffer 
// at point position 
static void insert(String input, int position) 
{ 
     int len = input.length(); 
     int i = 0 ; 
  
     // If the point is not the gap check 
     // and move the cursor to that point 
     if (position != gap_left)
     { 
         move_cursor(position); 
     } 
  
     // Insert characters one by one 
     while (i < len) 
     { 
         // If the gap is empty grow the size 
         if (gap_right == gap_left) 
         { 
             int k = 10 ; 
             grow(k, position); 
         } 
  
         // Insert the character in the gap and 
         // move the gap 
         buffer[gap_left] = input.charAt(i); 
         gap_left++; 
         i++; 
         position++; 
     } 
} 
  
// Driver code 
public static void main(String[] args)
{
     // Initializing the gap buffer with size 10 
     for ( int i = 0 ; i < 10 ; i++) 
     { 
         buffer[i] = '_' ; 
     } 
  
     System.out.println( "Initializing the gap" + 
                        " buffer with size 10" ); 
  
     for ( int i = 0 ; i < size; i++) 
     { 
         System.out.print(buffer[i] + " " ); 
     } 
  
     System.out.println(); 
  
     // Inserting a string to buffer 
     String input = "GEEKSGEEKS" ; 
     int position = 0 ; 
  
     insert(input, position); 
  
     System.out.println(); 
     System.out.println( "Inserting a string " + 
                        "to buffer: GEEKSGEEKS" ); 
     System.out.print( "Output: " ); 
     for ( int i = 0 ; i < size; i++)
     { 
         System.out.print(buffer[i] + " " ); 
     } 
  
     input = "FOR" ; 
     position = 5 ; 
  
     insert(input, position); 
  
     System.out.println(); 
     System.out.println(); 
      
     System.out.println( "Inserting a string" + 
                        " to buffer: FOR" ); 
     System.out.print( "Output: " ); 
     for ( int i = 0 ; i < size; i++)
     { 
         System.out.print(buffer[i] + " " ); 
     }
     }
}
  
// This code is contributed by Princi Singh

C#

// C# program of implementation of gap buffer
using System;
      
class GFG 
{ 
static char []buffer = new char [50]; 
static int gap_size = 10; 
static int gap_left = 0; 
static int gap_right = gap_size - gap_left - 1; 
static int size = 10; 
  
// Function that is used to grow the gap 
// at index position and return the array 
static void grow( int k, int position) 
{ 
     char []a = new char [size]; 
  
     // Copy characters of buffer to a[] 
     // after position 
     for ( int i = position; i < size; i++) 
     { 
         a[i - position] = buffer[i]; 
     }
      
     // Insert a gap of k from index position 
     // gap is being represented by '-' 
     for ( int i = 0; i < k; i++) 
     { 
         buffer[i + position] = '_' ; 
     } 
      
     // Reinsert the remaining array 
     for ( int i = 0; i < k; i++) 
     { 
         buffer[position + k + i] = a[i]; 
     } 
  
     size += k; 
     gap_right += k; 
} 
  
// Function that is used to move the gap 
// left in the array 
static void left( int position) 
{ 
     // Move the gap left character by character 
     // and the buffers 
     while (position < gap_left)
     { 
         gap_left--; 
         gap_right--; 
         buffer[gap_right + 1] = buffer[gap_left]; 
         buffer[gap_left]= '_' ; 
     } 
} 
  
// Function that is used to move the gap 
// right in the array 
static void right( int position) 
{ 
      
     // Move the gap right character by character 
     // and the buffers 
     while (position > gap_left)
     { 
         gap_left++; 
         gap_right++; 
         buffer[gap_left - 1] = buffer[gap_right]; 
         buffer[gap_right] = '_' ; 
     } 
} 
  
// Function to control the movement of gap 
// by checking its position to the point of 
// insertion 
static void move_cursor( int position) 
{ 
     if (position < gap_left)
     { 
         left(position); 
     } 
     else
     { 
         right(position); 
     } 
} 
  
// Function to insert the string to the buffer 
// at point position 
static void insert(String input, int position) 
{ 
     int len = input.Length; 
     int i = 0; 
  
     // If the point is not the gap check 
     // and move the cursor to that point 
     if (position != gap_left)
     { 
         move_cursor(position); 
     } 
  
     // Insert characters one by one 
     while (i < len) 
     { 
         // If the gap is empty grow the size 
         if (gap_right == gap_left) 
         { 
             int k = 10; 
             grow(k, position); 
         } 
  
         // Insert the character in the gap and 
         // move the gap 
         buffer[gap_left] = input[i]; 
         gap_left++; 
         i++; 
         position++; 
     } 
} 
  
// Driver code 
public static void Main(String[] args)
{
     // Initializing the gap buffer with size 10 
     for ( int i = 0; i < 10; i++) 
     { 
         buffer[i] = '_' ; 
     } 
  
     Console.WriteLine( "Initializing the gap" + 
                       " buffer with size 10" ); 
  
     for ( int i = 0; i < size; i++) 
     { 
         Console.Write(buffer[i] + " " ); 
     } 
  
     Console.WriteLine(); 
  
     // Inserting a string to buffer 
     String input = "GEEKSGEEKS" ; 
     int position = 0; 
  
     insert(input, position); 
  
     Console.WriteLine(); 
     Console.WriteLine( "Inserting a string " + 
                     "to buffer: GEEKSGEEKS" ); 
     Console.Write( "Output: " ); 
     for ( int i = 0; i < size; i++)
     { 
         Console.Write(buffer[i] + " " ); 
     } 
  
     input = "FOR" ; 
     position = 5; 
  
     insert(input, position); 
  
     Console.WriteLine(); 
     Console.WriteLine(); 
      
     Console.WriteLine( "Inserting a string" + 
                          " to buffer: FOR" ); 
     Console.Write( "Output: " ); 
     for ( int i = 0; i < size; i++)
     { 
         Console.Write(buffer[i] + " " ); 
     }
     }
}
  
// This code is contributed by 29AjayKumar

输出如下：

Initializing the gap buffer with size 10
_ _ _ _ _ _ _ _ _ _ 


Inserting a string to buffer: GEEKSGEEKS
Output: G E E K S G E E K S _ _ _ _ _ _ _ _ _ _ 

Inserting a string to buffer: FOR
Output: G E E K S F O R _ _ _ _ _ _ _ G E E K S

插入的时间复杂度：O(1)

增长的时间复杂度：O(n)

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: