算法设计（间隙缓冲区数据结构） _算法

需要间隙缓冲区
Gap Buffer中的基本操作
间隙缓冲vs绳索
实现间隙缓冲区

目录本文概述

C ++
Java
C#

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

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

文章图片
这是在前面插入字符的基本情况。现在, 每当需要在某个位置插入字符时, 我们将使用以下命令将间隙向上移动到该位置剩下()和对()然后尝试插入字符。
需要间隙缓冲区数组是一种数据结构, 用于将项目存储在连续的内存位置。但是, 它需要在数组末尾插入O(1), 而在前面则需要O(n)时间, 因为该数组将向右移动n个位置, n是数组的长度。
当涉及到文本编辑器时, 我们需要一种更快的数据结构来进行插入和修改, 因为光标位置存在多个更改。
在最坏的情况下, 数组将花费O(n)时间进行插入或修改, 如下例所示。
为了在前面插入" GEEKS", 通过移动数组留出了用于插入每个字符的空间。

文章图片
Gap Buffer中的基本操作 insert()：这是一个用于在给定位置将字符插入文本的过程。它首先检查间隙是否为空, 如果发现间隙为空, 则调用过程grow()并调整间隙的大小, 现在可以插入元素了。
剩下() ：
这是用于将光标向左移动的过程, 该光标点用作更改位置。

文章图片
对：
这是用于将光标向右移动的过程, 该光标点用作更改位置。

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

文章图片
间隙缓冲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# 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: GEEKSGEEKSOutput: G E E K S G E E K S _ _ _ _ _ _ _ _ _ _ Inserting a string to buffer: FOROutput: G E E K S F O R _ _ _ _ _ _ _ G E E K S

插入的时间复杂度：O(1)
【算法设计（间隙缓冲区数据结构）】增长的时间复杂度：O(n)