- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
任何人都可以帮助消除此段错误。我已经在这个代码上工作了一个星期仍然无法调试它。这段代码是Btree的实现。插入部分工作正常,但删除部分出现段错误。我无法调试它,有人可以帮忙吗?
我已经根据此链接给出了输入(已将字母值转换为 ASCII 值) http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html
当我删除第一个 H
(等效 ASCII 值)时,它可以正常工作,但是当我删除 T
(等效 ASCII 值)时,我会遇到段错误。
#include<stdio.h>
#include<stdlib.h>
#define M 5
struct node{
int n; /* n < M No. of keys in node will always less than order of B
tree */
int keys[M-1]; /*array of keys*/
struct node *p[M]; /* (n+1 pointers will be in use) */
}*root=NULL;
enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);
int input_array[20]= {65,67,71,78,72,69,75,81,77,70,87,76,84,90,68,80,82,88,89,83};
int main()
{
int choice, i,key = 11;
printf("Creation of B tree for node %d\n",M);
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Search\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//printf("Enter the key : ");
//scanf("%d",&key);
//for(i=0;i<20;i++)
for(i=0;i<20;i++)
{
key = input_array[i];
insert(key);
}
//insert(key++);
//insert(key);
break;
case 2:
printf("Enter the key : ");
scanf("%d",&key);
DelNode(key);
break;
case 3:
printf("Enter the key : ");
scanf("%d",&key);
search(key);
break;
case 4:
printf("Btree is :\n");
display(root,0);
break;
case 5:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
return 0;
}/*End of main()*/
void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf("Key already available\n");
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/
enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M - 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is
last*/
if (pos == M - 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted
is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M - 1)/2;
(*upKey) = ptr->keys[splitPos];
(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/
void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(" ");
for (i=0; i < ptr->n; i++)
printf("%d ",ptr->keys[i]);
printf("\n");
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/
void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf("Search path:\n");
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(" %d",ptr->keys[i]);
printf("\n");
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf("Key %d found in position %d of last dispalyednode\n",key,i);
return;
}
ptr = ptr->p[pos];
}
printf("Key %d is not available\n",key);
}/*End of search()*/
int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/
void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf("Key %d is not available\n",key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/
enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;
if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M - 1)/2;/*Minimum number of keys*/
pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */
if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey - 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;
if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos - 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[--lptr->n];
return Success;
}/*End of if */
if (pos > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */
if(pos == n)
pivot = pos-1;
else
pivot = pos;
lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/
可能是什么问题?
最佳答案
在不确切知道这应该如何工作的情况下,我可以说你是在 p
之外编写的。 vector 上
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
// When you delete key 84, rptr->n is 4 at one point which takes you outside
// p[M]
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
Valgrind是一个很好用的工具,我通过valgrind -v --leak-check=full <your executable>
发现了这个问题
关于c - btree 实现中的段错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5662684/
我的数学需要一点帮助,这几天我的大脑很痛。 我为许多 btree 的不同大小的节点使用了一个池。如果 btrees 对于大树和小树的每个节点的键平均数量往往相同,那么效果会很好。但是,如果分布不同,我
任何人都可以帮助消除此段错误。我已经在这个代码上工作了一个星期仍然无法调试它。这段代码是Btree的实现。插入部分工作正常,但删除部分出现段错误。我无法调试它,有人可以帮忙吗? 我已经根据此链接给出了
任何人都可以帮助消除此段错误。我已经在这个代码上工作了一个星期仍然无法调试它。这段代码是Btree的实现。插入部分工作正常,但删除部分出现段错误。我无法调试它,有人可以帮忙吗? 我已经根据此链接给出了
我正在尝试按级别顺序打印一棵 b 树,但它一直在崩溃。我不确定真正的原因是什么,但我认为它崩溃是因为指针。我正在尝试使用我在网上找到的一个函数,该函数遍历每个级别并将其放入队列中并打印出来,但我遇到了
我一直在阅读@XenphYan 的回答 How does database indexing work? 但是有些事情我无法理解 Due to the fact that a number of re
我想要一个在一个字段上进行全文搜索然后在不同字段上进行排序的查询(想象一下搜索一些文本文档并按发布日期排序)。该表有大约 1700 万行,它们或多或少按日期均匀分布。这将在 webapp 请求/响应周
让我们看两个表: CREATE TABLE `orders_products` ( `ORDER_ID` int(10) unsigned NOT NULL, `PRODUCT_ID
我正在尝试创建一个为 BTree 设置动画的 Java 小程序。我有创建树的代码,但现在我正在尝试显示它。我认为最简单的方法是按级别打印,但我不知道该怎么做。下面的代码是我的节点的构造函数。另外,如果
我在维基百科上读到的: In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within s
我一直在 slady.net 玩非常酷的 btree applet| .我无法理解特定行为。看看这个起始状态: alt text http://www.freeimagehosting.net/upl
您好,这是我的 SearchTree 类中的代码。Node* 是一个 m_info 类型为 int 的结构体,m_left(smaller nodes by info) 和 m_right(bigge
想象一下,每天都会有一位作者送给您一本新书。这本书正在编写中。他没有告诉您他更改或添加了什么。 您的工作是确定更改和添加内容,然后仅将这些内容传递给出版商(出版商没有时间每天阅读整本书) 为了解决这个
所以我有一个包含大约 2000 万个键值对的列表,我将数据以不同的方式存储在几个 MapDB 中,以查看它如何影响我的程序性能,并进行实验。 问题是,将 2000 万个键值对插入(以随机顺序)到 ma
我找不到关于 Postgres 文档的足够信息,但很想知道 btree 索引对于 postgres varchar 列是怎样的。 任何链接/解释都可能有帮助。 PS:对不起,这个问题含糊不清 最佳答案
我曾尝试查找类似的问题,但没有找到任何问题,除了有关同一列的两个索引的问题(一般而言)。 假设我们有一个包含 COL 列的表。该表(以及整个数据库)对于客户端来说是只读的(让我们假设它更新一次/每隔很
我正在尝试实现 BTree。我几乎已经完成了这棵树,并且对于较小的输入效果很好,这意味着我已经在内存中实现了这棵树。现在我想玩大输入,为此我必须将树写入文件。我不知道从哪里开始。我正在使用 Java,
我有一张 OrderDish 表,其中包含: create table OrderDish( email VARCHAR(80), nOrd integer, totalPri
如何解决这个问题? 我的表结构: CREATE TABLE IF NOT EXISTS `tbl_foster_network` ( `network_id` int(11) NOT NULL C
很难说出这里要问什么。这个问题模棱两可、含糊不清、不完整、过于宽泛或夸夸其谈,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开,visit the help center . 关闭 1
我尝试使用 Java 来实现教科书《算法简介》第三版中的算法,但没有取得很大成功。几乎每次我尝试实现它们时,我都会遇到大量错误,以至于我不确定作者自己是否尝试过实现他们自己的伪代码。但具体来说,在这种
我是一名优秀的程序员,十分优秀!