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

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

本文概述

Gap Buffer中的基本操作

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

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``````