C Primer Plus(第五版)第17章 高级数据表示(下)
5.1 main.c
5.2 stack.h
5.3 stack.c
6
7.1 main.c
7.2 tree.h
7.3 tree.c
8.1 main.c
8.2 tree.h
8.3 tree.c
#include<stdio.h> #include<string.h> #include"stack.h" int main(void) { int i,j; Stack s; char a[MAX]; puts("输入字符串"); fgets(a,49,stdin); initstack(&s); i=strlen(a); for(j=0;j<i;j++) instack(&s,a[j]); for(j=0;j<i;j++) printf("%c ",outstack(&s)); puts(""); emptystack(&s); return 0; }
5.2 stack.h
#ifndef STACK_H #define STACK_H #include<stdio.h> #include<stdlib.h> #define MAX 50 typedef char Item; typedef struct stack { Item string[MAX]; int items; } Stack; //初始化栈 _Bool initstack(Stack*); //入栈 _Bool instack(Stack*,Item); //出栈 Item outstack(Stack*); //清空栈 _Bool emptystack(Stack*); #endif
5.3 stack.c
#include<stdio.h> #include"stack.h" //初始化栈 _Bool initstack(Stack*s) { s->items=0; } //入栈 _Bool instack(Stack*s,Item i) { if(s->items==MAX) return 0; s->string[s->items]=i; s->items++; return 1; } //出栈 Item outstack(Stack*s) { if(s->items==0) { puts("发生错误,栈空!"); exit(0); } s->items--; return s->string[s->items]; } //清空栈 _Bool emptystack(Stack*s) { s->items=0; return 1; }
6
#include<stdio.h> #define max 10 _Bool bsearch(int *i,int j,int k); int main(void) { int i; int a[max]={0,1,2,3,4,5,6,7,8,9}; printf("%d",bsearch(a,10,8)); return 0; } _Bool bsearch(int *i,int j,int k) { if(j!=0) { if(i[j/2]==k) return 1; else { if(k>i[j/2]) { if(j/2==0) return bsearch(i+j/2+1,j/2-1,k); else return bsearch(i+j/2+1,j/2,k); } else return bsearch(i,j/2,k); } } return 0; }
7.1 main.c
#include<stdio.h> #include<stdlib.h> #include"tree.h" void pfun(Item item); void menu(void); int main(int num,char **file) { if (num < 2) { fprintf(stderr, "Usage: %s filename\n", file[0]); exit(1); } FILE * in; int i; Item n; Tree ptree; InitializeTree(&ptree); if ((in = fopen(file[1], "r")) == NULL) { fprintf(stderr, "I couldn't open the file \"%s\"\n",file[1]); exit(2); } while (fscanf(in,"%s",n.words) == 1) AddItem(&n,&ptree); menu(); while((i=getchar())!='q') { while(getchar()!='\n') ; switch(i) { case 'a': Traverse (&ptree, pfun); break; case 'b': scanf("%s",n.words); while(getchar()!='\n') ; printf("word %s times %d\n",n.words,InTree(&n,&ptree)); break; case 'q': break; default: puts("wrong character"); break; } menu(); } fclose(in); puts("bye"); return 0; } void pfun(Item item) { printf("words %s times %d\n",item.words,item.num); } void menu (void) { puts("a) list all"); puts("b) input a word"); puts("q) quit"); }
7.2 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 words[20]; int num; } Item; #define MAXITEMS 99999 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 */ int 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
7.3 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 */ } new_node=SeekItem(pi,ptree).child; if (new_node != NULL) { new_node->item.num++; return true; /* 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 */ } int InTree(const Item * pi, const Tree * ptree) { Pair p; p=SeekItem(pi,ptree); return (p.child == NULL) ? false : p.child->item.num; } 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->words, i2->words)) < 0) return true; return false; } static bool ToRight(const Item * i1, const Item * i2) { int comp1; if ((comp1 = strcmp(i1->words, i2->words)) > 0) return true; 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->item.num=1; 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.words); 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); } }
8.1 main.c
/* petclub.c -- use a binary search tree */ #include <stdio.h> #include <string.h> #include <ctype.h> #include "tree.h" 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); 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:"); gets(temp.petname); puts("Please enter pet kind:"); gets(temp.petkind); 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) { Item*i; i=&item; while(i!=NULL) { printf("Pet: %-19s Kind: %-19s\n", i->petname,i->petkind); i=i->next; } } void findpet(const Tree * pt) { Item temp; Node* n; Item* m; if (TreeIsEmpty(pt)) { puts("No entries!"); return; /* quit function if tree is empty */ } puts("Please enter name of pet you wish to find:"); gets(temp.petname); uppercase(temp.petname); printf("%s(s) ", temp.petname); n=InTree(&temp,pt); if (n) { printf("are in tree.\n"); m=n->item; while(m!=NULL) { printf("%s ",m->petkind); m=m->next; } } else printf("is not a member.\n"); puts(""); } 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:"); gets(temp.petname); puts("Please enter pet kind:"); gets(temp.petkind); 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++; } }
8.2 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]; struct item*next; } 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 */ Node* 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
8.3 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); static bool AddListItem(Item item, Item ** plist); static void CopyToNode(Item item, Item * pnode); static void EmptyTheList(Item ** plist); /* 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 */ } new_node=SeekItem(pi,ptree).child; if (new_node != NULL) { AddListItem(*pi,&new_node->item); return true; /* 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 */ } static bool AddListItem(Item item, Item ** plist) { Item * pnew; Item * scan = *plist; pnew = (Item *) malloc(sizeof(Item)); if (pnew == NULL) return false; /* quit function on failure */ CopyToNode(item, pnew); pnew->next = NULL; if (scan == NULL) /* empty list, so place */ *plist = pnew; /* pnew at head of list */ else { while (scan->next != NULL) scan = scan->next; /* find end of list */ scan->next = pnew; /* add pnew to end */ } return true; } static void CopyToNode(Item item, Item * pnode) { *pnode = item; /* structure copy */ } Node* InTree(const Item * pi, const Tree * ptree) { return SeekItem(pi, ptree).child; } 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); EmptyTheList(&root->item); free(root); DeleteAllNodes(pright); } } static void EmptyTheList(Item ** plist) { Item * psave; while (*plist != NULL) { psave = (*plist)->next; /* save address of next node */ free(*plist); /* free current node */ *plist = psave; /* advance to next node */ } } 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; return false; } static bool ToRight(const Item * i1, const Item * i2) { int comp1; if ((comp1 = strcmp(i1->petname, i2->petname)) > 0) return true; return false; } static Node * MakeNode(const Item * pi) { Node * new_node; Item *q; q=malloc(sizeof(Item)); *q=*pi; q->next=NULL; new_node = (Node *) malloc(sizeof(Node)); if (new_node != NULL) { new_node->item = q; 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); EmptyTheList(&((*ptr)->item)); 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); } }
相关推荐
C Primer Plus 第五版第九章答案,自己编写可以成功运行
( C Primer Plus(第五版)中文版课后编程题全解,非常全,亲测可用
C Primer Plus(第五版)中文版.txt fhnfdjjy
c primer plus 第五版课后习题答案
c++ primer plus 第五版课后习题答案
C Primer Plus(第五版)中文版,学习C语言必备,讲的特别详细
C++PrimerPlus第五版习题参考答案
C Primer Plus第6版编程练习答案.pdf
C Primer Plus第五版中文版是全球最经典的C语言教程,(包括PDF,书中源码,习题解答)。由于资格的原因,分4个RAR上传,都要下载。
c入门必看的c primer plus ,其课后练习题也是很不错的。
《C Primer Plus》第六版 第十一章编程练习答案,亲测编译通过
通过学习《C Primer Plus(第五版)中文版》,你将奠定坚实的C编程基础。 与以前的版本一样,作者的目标仍旧是为读者提供一本入门性、条理清晰、见解深刻的C语言教程。作者把编程概念和C语言的细节很好地融合在一起...
c primer plus 第六版 中文版 源代码+勘误+习题答案,从官方处获得,因为官网需注册很麻烦,所以索性上传,与大家分享。 共三部分,针对第六版,含课后习题,源代码,书中勘误。
在这里下载了C Primer Plus(第五版)中文版可惜没有书签,就用OCR获取了书签生成了用 PdgCntEditor 1.07a 可以使用的格式共大家自行添加书签。不过原书是加密的不能编辑还有借助解密工具PDF Password Remover v3.0 。...
C Primer Plus (第五版)中文版——第 8 章 编程练习参考程序
C++Primer Plus(第6版)中文版编程练习答案--第四章.pdf
本书是c++ primer plus第五版的源代码,以及好多高手的编程心路沥程,不得不看!! 听君一席话胜读十年书!
《C++ Primer Plus第6版中文版》学习笔记(第十章) 红字内容是有疑问或者没把握的。 绿字部分是比较重要,或者经过确认的
c++ primer plus 课后编程练习的完整答案 PDF文件.
C Primer Plus (第五版) 课后编程练习答案 (完整) 文字版