c - 如何在 btree 中插入结构

Question

我有一个可以插入值的 B 树，我如何修改它以插入一个结构(如图所示)而不是一个键；我必须使用卷号并且必须从结构节点访问结构名称。我该怎么做？

struct name
{
    char first_name[16];
    char last_name[16];
    int roll_number;
};

其中名称是一个结构数组。到目前为止，我已经编写了插入结构元素的代码，但我无法继续进行；请帮助我。

#define M 3;
struct node
{
    int n; /* n < M No. of keys in node will always less than order of Btree */
    struct node *p[M]; /* (n+1 pointers will be in use) */
    int key[M-1]; /*array of names*/
} *root=NULL;

enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };
void insert(int key);
void display(struct node *root,int);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);

main()
{
    int choice,key;
    printf("Creation of B tree for node %d\n",M);
    while(1) {
            printf("1.Insert\n");
            printf("2.Quit\n");
            printf("Enter your choice : ");
            scanf("%d",&choice);
            switch(choice) {
                case 1:
                    printf("Enter the value : ");
                    scanf("%d",key);
                    insert(key);
                    break;
                case 2:
                    exit(1);
                default:
                    printf("Wrong choice\n");
                    break;
            }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

void insert(struct classifier *)
{
    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;
    int check = 1;
    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 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 dispalyed node\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()*/

Answer 1

在您定义的节点中，您应该能够将struct key替换为struct name，并使用类似的东西root->name->roll_number 供您比较。可能还有一些其他清理工作要做，但这是基本的想法。