I'm a college student and C is the only language I mastered so far,I want to lower the difficulty to learn data structure so I googled and find this extension.
But I take several hours to find and understand tutorials and still not effect.
I can't figure out where is my lack,I think it seem to need learn typescript,java,npm and other knowledge about Web front-end development to this,since I find the demonstrate gif is only show how typescript works and I can't see how to type correct command in the extension command bar.
petclub.c
/* petclub.c -- use a binary search tree */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"
#define SIZE 30
char menu(void);
void addpet(Tree * pt);
void droppet(Tree * pt);
void showpets(const Tree * pt);
void findpet(const Tree * pt);
void printitem(Item item);
void uppercase(char * str);
char* s_gets(char* st,int n) //字符输入检测函数
{
char* ret_val;
char* find;
ret_val=fgets(st,n,stdin);
if(ret_val)
{
find = strchr(st,'\n'); //查找输入的字符串在前n个字的范围内是否有换行符
if(find)
*find = '\0'; //若有将尾部的换行符替代掉
else
while(getchar()!='\n') //若无将n后面的字符全部丢弃
continue;
}
return ret_val;
}
int main(void)
{
Tree pets;
char choice;
InitializeTree(&pets);
while ((choice = menu()) != 'q')
{
switch (choice)
{
case 'a' : addpet(&pets);
break;
case 'l' : showpets(&pets);
break;
case 'f' : findpet(&pets);
break;
case 'n' : printf("%d pets in club\n",
TreeItemCount(&pets));
break;
case 'd' : droppet(&pets);
break;
default : puts("Switching error");
}
}
DeleteAll(&pets);
puts("Bye.");
return 0;
}
char menu(void)
{
int ch;
puts("Nerfville Pet Club Membership Program");
puts("Enter the letter corresponding to your choice:");
puts("a) add a pet l) show list of pets");
puts("n) number of pets f) find pets");
puts("d) delete a pet q) quit");
while ((ch = getchar()) != EOF)
{
while (getchar() != '\n') /* discard rest of line */
continue;
ch = tolower(ch);
if (strchr("alrfndq",ch) == NULL)
puts("Please enter an a, l, f, n, d, or q:");
else
break;
}
if (ch == EOF) /* make EOF cause program to quit */
ch = 'q';
return ch;
}
void addpet(Tree * pt)
{
Item temp;
if (TreeIsFull(pt))
puts("No room in the club!");
else
{
puts("Please enter name of pet:");
s_gets(temp.petname,SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind,SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
AddItem(&temp, pt);
}
}
void showpets(const Tree * pt)
{
if (TreeIsEmpty(pt))
puts("No entries!");
else
Traverse(pt, printitem);
}
void printitem(Item item)
{
printf("Pet: %-19s Kind: %-19s\n", item.petname,
item.petkind);
}
void findpet(const Tree * pt)
{
Item temp;
if (TreeIsEmpty(pt))
{
puts("No entries!");
return; /* quit function if tree is empty */
}
puts("Please enter name of pet you wish to find:");
s_gets(temp.petname,SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind,SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s ", temp.petname, temp.petkind);
if (InTree(&temp, pt))
printf("is a member.\n");
else
printf("is not a member.\n");
}
void droppet(Tree * pt)
{
Item temp;
if (TreeIsEmpty(pt))
{
puts("No entries!");
return; /* quit function if tree is empty */
}
puts("Please enter name of pet you wish to delete:");
s_gets(temp.petname,SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind,SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s ", temp.petname, temp.petkind);
if (DeleteItem(&temp, pt))
printf("is dropped from the club.\n");
else
printf("is not a member.\n");
}
void uppercase(char * str)
{
while (*str)
{
*str = toupper(*str);
str++;
}
}
`
tree.c
`/* tree.c -- tree support functions */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
/* local data type */
typedef struct pair {
Node * parent;
Node * child;
} Pair;
/* protototypes for local functions */
static Node * MakeNode(const Item * pi);
static bool ToLeft(const Item * i1, const Item * i2);
static bool ToRight(const Item * i1, const Item * i2);
static void AddNode (Node * new_node, Node * root);
static void InOrder(const Node * root, void (* pfun)(Item item));
static Pair SeekItem(const Item * pi, const Tree * ptree);
static void DeleteNode(Node **ptr);
static void DeleteAllNodes(Node * ptr);
/* function definitions */
void InitializeTree(Tree * ptree)
{
ptree->root = NULL;
ptree->size = 0;
}
bool TreeIsEmpty(const Tree * ptree)
{
if (ptree->root == NULL)
return true;
else
return false;
}
bool TreeIsFull(const Tree * ptree)
{
if (ptree->size == MAXITEMS)
return true;
else
return false;
}
int TreeItemCount(const Tree * ptree)
{
return ptree->size;
}
bool AddItem(const Item * pi, Tree * ptree)
{
Node * new_node;
if (TreeIsFull(ptree))
{
fprintf(stderr,"Tree is full\n");
return false; /* early return */
}
if (SeekItem(pi, ptree).child != NULL)
{
fprintf(stderr, "Attempted to add duplicate item\n");
return false; /* early return */
}
new_node = MakeNode(pi); /* points to new node */
if (new_node == NULL)
{
fprintf(stderr, "Couldn't create node\n");
return false; /* early return */
}
/* succeeded in creating a new node */
ptree->size++;
if (ptree->root == NULL) /* case 1: tree is empty */
ptree->root = new_node; /* new node is tree root */
else /* case 2: not empty */
AddNode(new_node,ptree->root); /* add node to tree */
return true; /* successful return */
}
bool InTree(const Item * pi, const Tree * ptree)
{
return (SeekItem(pi, ptree).child == NULL) ? false : true;
}
bool DeleteItem(const Item * pi, Tree * ptree)
{
Pair look;
look = SeekItem(pi, ptree);
if (look.child == NULL)
return false;
if (look.parent == NULL) /* delete root item */
DeleteNode(&ptree->root);
else if (look.parent->left == look.child)
DeleteNode(&look.parent->left);
else
DeleteNode(&look.parent->right);
ptree->size--;
return true;
}
void Traverse (const Tree * ptree, void (* pfun)(Item item))
{
if (ptree != NULL)
InOrder(ptree->root, pfun);
}
void DeleteAll(Tree * ptree)
{
if (ptree != NULL)
DeleteAllNodes(ptree->root);
ptree->root = NULL;
ptree->size = 0;
}
/* local functions */
static void InOrder(const Node * root, void (* pfun)(Item item))
{
if (root != NULL)
{
InOrder(root->left, pfun);
(*pfun)(root->item);
InOrder(root->right, pfun);
}
}
static void DeleteAllNodes(Node * root)
{
Node * pright;
if (root != NULL)
{
pright = root->right;
DeleteAllNodes(root->left);
free(root);
DeleteAllNodes(pright);
}
}
static void AddNode (Node * new_node, Node * root)
{
if (ToLeft(&new_node->item, &root->item))
{
if (root->left == NULL) /* empty subtree */
root->left = new_node; /* so add node here */
else
AddNode(new_node, root->left);/* else process subtree*/
}
else if (ToRight(&new_node->item, &root->item))
{
if (root->right == NULL)
root->right = new_node;
else
AddNode(new_node, root->right);
}
else /* should be no duplicates */
{
fprintf(stderr,"location error in AddNode()\n");
exit(1);
}
}
static bool ToLeft(const Item * i1, const Item * i2)
{
int comp1;
if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
return true;
else if (comp1 == 0 &&
strcmp(i1->petkind, i2->petkind) < 0 )
return true;
else
return false;
}
static bool ToRight(const Item * i1, const Item * i2)
{
int comp1;
if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
return true;
else if (comp1 == 0 &&
strcmp(i1->petkind, i2->petkind) > 0 )
return true;
else
return false;
}
static Node * MakeNode(const Item * pi)
{
Node * new_node;
new_node = (Node *) malloc(sizeof(Node));
if (new_node != NULL)
{
new_node->item = *pi;
new_node->left = NULL;
new_node->right = NULL;
}
return new_node;
}
static Pair SeekItem(const Item * pi, const Tree * ptree)
{
Pair look;
look.parent = NULL;
look.child = ptree->root;
if (look.child == NULL)
return look; /* early return */
while (look.child != NULL)
{
if (ToLeft(pi, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->left;
}
else if (ToRight(pi, &(look.child->item)))
{
look.parent = look.child;
look.child = look.child->right;
}
else /* must be same if not to left or right */
break; /* look.child is address of node with item */
}
return look; /* successful return */
}
static void DeleteNode(Node **ptr)
/* ptr is address of parent member pointing to target node */
{
Node * temp;
puts((*ptr)->item.petname);
if ( (*ptr)->left == NULL)
{
temp = *ptr;
*ptr = (*ptr)->right;
free(temp);
}
else if ( (*ptr)->right == NULL)
{
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
}
else /* deleted node has two children */
{
/* find where to reattach right subtree */
for (temp = (*ptr)->left; temp->right != NULL;
temp = temp->right)
continue;
temp->right = (*ptr)->right;
temp = *ptr;
*ptr =(*ptr)->left;
free(temp);
}
}
`
tree.h
`/* tree.h -- binary search tree */
/* no duplicate items are allowed in this tree */
#ifndef _TREE_H_
#define _TREE_H_
#include <stdbool.h>
/* redefine Item as appropriate */
typedef struct item
{
char petname[20];
char petkind[20];
} Item;
#define MAXITEMS 10
typedef struct node
{
Item item;
struct node * left; /* pointer to right branch */
struct node * right; /* pointer to left branch */
} Node;
typedef struct tree
{
Node * root; /* pointer to root of tree */
int size; /* number of items in tree */
}Tree;
/* function prototypes */
/* operation: initialize a tree to empty */
/* preconditions: ptree points to a tree */
/* postconditions: the tree is initialized to empty */
void InitializeTree(Tree * ptree);
/* operation: determine if tree is empty */
/* preconditions: ptree points to a tree */
/* postconditions: function returns true if tree is */
/* empty and returns false otherwise */
bool TreeIsEmpty(const Tree * ptree);
/* operation: determine if tree is full */
/* preconditions: ptree points to a tree */
/* postconditions: function returns true if tree is */
/* full and returns false otherwise */
bool TreeIsFull(const Tree * ptree);
/* operation: determine number of items in tree */
/* preconditions: ptree points to a tree */
/* postconditions: function returns number of items in */
/* tree */
int TreeItemCount(const Tree * ptree);
/* operation: add an item to a tree */
/* preconditions: pi is address of item to be added */
/* ptree points to an initialized tree */
/* postconditions: if possible, function adds item to */
/* tree and returns true; otherwise, */
/* the function returns false */
bool AddItem(const Item * pi, Tree * ptree);
/* operation: find an item in a tree */
/* preconditions: pi points to an item */
/* ptree points to an initialized tree */
/* postconditions: function returns true if item is in */
/* tree and returns false otherwise */
bool InTree(const Item * pi, const Tree * ptree);
/* operation: delete an item from a tree */
/* preconditions: pi is address of item to be deleted */
/* ptree points to an initialized tree */
/* postconditions: if possible, function deletes item */
/* from tree and returns true; */
/* otherwise, the function returns false*/
bool DeleteItem(const Item * pi, Tree * ptree);
/* operation: apply a function to each item in */
/* the tree */
/* preconditions: ptree points to a tree */
/* pfun points to a function that takes*/
/* an Item argument and has no return */
/* value */
/* postcondition: the function pointed to by pfun is */
/* executed once for each item in tree */
void Traverse (const Tree * ptree, void (* pfun)(Item item));
/* operation: delete everything from a tree */
/* preconditions: ptree points to an initialized tree */
/* postconditions: tree is empty */
void DeleteAll(Tree * ptree);
#endif