- 需要间隙缓冲区
- 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 SinghC#
// 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)
推荐阅读
- PHP Ds Vector count（）函数用法介绍
- C中的const限定符介绍和用法示例
- C ++中的函数重载介绍
- 如何使用JavaScript / jQuery将JSON数据转换为html表（）
- Java String trim()方法与示例
- 如何使用JavaScript从html输入数组获取值（）
- 文件目录中没有dev-server.js文件如何mock数据
- C语言简明教程（十九）（高级数据结构和算法详解）
- C语言简明教程（十八）（预处理指令和C函数库完整详解）