数据结构1

C 二叉树的课程设计

《数据结构》实验三——二叉树排序算法*试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。*/Exchange(pBiNode BiTree){ pBiNode p; if(BiTree) { p = BiTree->lChild; BiTree->lChild = BiTree->rChild; BiTree->rChild = p; Exchange(BiTree->lChild); Exchange(BiTree->rChild); }}/*这个算法要求同学必须...全部

  《数据结构》实验三——二叉树排序算法*试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。*/Exchange(pBiNode BiTree){ pBiNode p; if(BiTree) { p = BiTree->lChild; BiTree->lChild = BiTree->rChild; BiTree->rChild = p; Exchange(BiTree->lChild); Exchange(BiTree->rChild); }}/*这个算法要求同学必须掌握*/《数据结构》实验三——动态查找*1。
  试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序，将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树，请设计算法2。在已构建的二叉排序树中插入元素40，使之依然为二叉排序树*/#include typedef struct node{ int data; struct node * lChild,*rChild;}node,*BTNode;BTNode Create(BTNode BiTree){ int n; BTNode p,q; scanf("%d",&n); for(;n != 0;) { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = NULL; p->rChild = NULL; if(!BiTree) BiTree = p; else { q = BiTree; while(q->data != n) { if(q->data > n) if(q->lChild != NULL) q = q->lChild; else q->lChild = p; else if(q->rChild != NULL) q = q->rChild; else q->rChild = p; } } scanf("%d",&n); } return BiTree;}InOrderTraverse(BTNode BiTree){ if(BiTree) { InOrderTraverse(BiTree->lChild); printf("M",BiTree->data); InOrderTraverse(BiTree->rChild); }}Insert(BTNode BiTree,int n){ BTNode p,q = BiTree; while(q->data != n) { if(q->data > n) if(q->lChild != NULL) q = q->lChild; else { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = p->rChild = NULL; q->lChild = p; } else if(q->rChild != NULL) q = q->rChild; else { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = p->rChild = NULL; q->rChild = p; } }}main(){ BTNode BTRoot; BTRoot = NULL; BTRoot = Create(BTRoot); printf(" Sorted numbers are: "); InOrderTraverse(BTRoot); Insert(BTRoot,40); printf(" After instert numbers are: "); InOrderTraverse(BTRoot); printf(" ");}*将序列（13,15,22,8,34,19,21）插入到一个初始时是空的哈希表中，哈希函数采用hash(x)=1 (x MOD 7)。
  使用线性探测法解决冲突*/#define N 8struct number{ int data; int flag; /*冲突与否标志*/}hx[N] = {0};Create_hxTable(struct number a[]){ int i,j,n; for(i = 1;i typedef struct s{ int no,password; struct s *next;}*node;node create_cycle(int n){ node head,end,p; int i; head = NULL; end = NULL; printf("Please input %d passwords(password > 0) ",n); for(i = 1;i password); p->no = i; if(!head) { head = p; end = p; } else { end->next = p; end = p; } } end->next = head; head = end; return head;}void out_link(node head,int n,int m){ int i,j,k = m; node p = head,q; for(i = 1;i next; q = p->next; k = q->password; p->next = q->next; printf("=",q->no); free(q); } printf("=",p->no); free(p);}void main(){ node head; int n,m; printf("Please input numbers of people and init_password "); scanf("%d%d",&n,&m); head = create_cycle(n); printf("Out link sequence is: "); out_link(head,n,m); printf(" ");}串操作：判断子串int find(char *c1,char *c2){ int flag = -1,i,j; for(i = 0;*(c1 i);i ) { j = 0; if(*(c1 i) == *(c2 j)) { flag = i; for(;*(c1 i) && *(c2 j) && *(c1 i) == *(c2 j);i ,j ) ; /*空循环，继续判断是否匹配*/ if(*(c2 j) == '') /*找到匹配的串*/ break; else flag = -1; } } return flag;}void main(){ char c1[30],c2[30]; int f; scanf("%s%s",c1,c2); f = find(c1,c2); if(f == -1) printf("No "); else printf("Yes! Position is %d ",f 1);}/*找二叉树的叶节点及统计叶节点个数*/int ShowLeaves(pBiNode BiTree){ static int i = 0; if(BiTree) { ShowLeaves(BiTree->lChild); ShowLeaves(BiTree->rChild); if((BiTree->lChild==NULL)&&(BiTree->rChild==NULL)) { printf("%c",BiTree->data); i ; } } return i;}/*求二叉树的深度*/int Depth(pBiNode BiTree){ int dep1,dep2; if(BiTree==NULL)return 0; else { dep1=Depth(BiTree->lChild); dep2=Depth(BiTree->rChild); return dep1>dep2? dep1 1: dep2 1; }}二叉树的创建和遍历(递归)#include typedef struct BiNode{ char data; struct BiNode *lChild,*rChild;}BiNode,*pTree;CreateTree(pTree *BTRoot){ char ch; scanf("%c",&ch); if(ch == '#') (*BTRoot) = NULL; else { (*BTRoot) = (pTree)malloc(sizeof(BiNode)); (*BTRoot)->data = ch; CreateTree(&((*BTRoot)->lChild)); CreateTree(&((*BTRoot)->rChild)); }}PreOrderTraverse(pTree pRoot){ if(pRoot) { printf("%c ",pRoot->data); PreOrderTraverse(pRoot->lChild); PreOrderTraverse(pRoot->rChild); }}InOrderTraverse(pTree pRoot){ if(pRoot) { InOrderTraverse(pRoot->lChild); printf("%c ",pRoot->data); InOrderTraverse(pRoot->rChild); }}PostOrderTraverse(pTree pRoot){ if(pRoot) { PostOrderTraverse(pRoot->lChild); PostOrderTraverse(pRoot->rChild); printf("%c ",pRoot->data); }}main(){ pTree root = NULL; CreateTree(&root); printf(" PreOrder is : "); PreOrderTraverse(root); printf(" InOrder is : "); InOrderTraverse(root); printf(" PostOrder is : "); PostOrderTraverse(root); printf(" ");}循环链表的建立及两循环链表的链接 #include typedef struct s{ int num; struct s *next;}*ls;ls creat(){ ls head,p,end; int i; static int n = 501; head = (ls)malloc(sizeof(struct s)); head->next = NULL; end = head; for(i = 1;i num = n ; end->next = p; end = p; } p->next = head; return head;}ls link_two(ls h1,ls h2){ ls end1,end2,p; for(p = h1->next;p->next != h1;p = p->next) end1 = p; for(p = h2->next;p->next != h2;p = p->next) end2 = p; end1->next = h2->next; end2->next = h1; free(h2); return h1;}main(){ ls head1,head2,head,p; head1 = creat(); head2 = creat(); head = link_two(head1,head2); for(p = head->next;p != head;p = p->next) printf("]",p->num);}与课堂上讲的稍修改了下，把n改为了静态变量static int n = 501;creat()函数不带参数 单链表的建立、节点查找、插入、删除等操作实现 #include typedef struct s{ int num; struct s *next;}*ls;ls creat(){ ls head,p,end; int i,n = 501; head = (ls)malloc(sizeof(struct s)); head->next = NULL; end = head; for(i = 1;i num = n ; end->next = p; end = p; } p->next = NULL; return head;}ls find_front(ls head,ls e){ ls p; p = head->next; for(;p->next && p->next->num != e->num;p = p->next) if(p->next->num == e->num) return p; else return NULL;}void insert_front(ls head,ls e,ls f){ ls p; p = find_front(head,e); f->next = p->next; p->next = f;}main(){ ls head,p,e,f; head = creat(); for(p = head->next;p;p = p->next) printf("]",p->num); printf(" "); e = (ls)malloc(sizeof(struct s)); f = (ls)malloc(sizeof(struct s)); scanf("%d%d",&e->num,&f->num); e->next = NULL; f->next = NULL; /*p = find_front(head,e);*/ insert_front(head,e,f); printf("Inerted! "); for(p = head->next;p;p = p->next) printf("]",p->num);} 节点删除void delete(ls head,ls e){ ls p,q; p = find_front(head,e); q = p->next; p->next = p->next->next; free(q);}堆栈操作（检验符号匹配实例）#include #include typedef struct stack{ char c; struct stack *next;}*node;node push(node top,node new) /*入栈*/{ if(top == NULL) top = new; else { new->next = top; top = new; } return top;}node pop(node top) /*出栈*/{ node p; if(!top) { printf("NULL stack "); return NULL; } else { p = top; top = top->next; free(p); return top; }}char top_data(node top) /*取栈顶数据*/{ char ch = 0; if(!top) return 0; else ch = top->c; return ch;}void main(){ char ch; node top = NULL,p; for(;(ch = getchar()) != ' ';) /*输入表达式*/ { if(ch == '(' ||ch == '[' ||ch == '{') { p = (node)malloc(sizeof(struct stack)); p->c = ch; p->next = NULL; top =push(top,p); } else if(ch == ')') { if(top_data(top) != '(') { printf("No "); exit(); } else top = pop(top); } else if(ch == ']') { if(top_data(top) != '[') { printf("No "); exit(); } else top = pop(top); } else if(ch == '}') { if(top_data(top) != '{') { printf("No "); exit(); } else top = pop(top); } } if(top) printf("No "); else printf("Yes ");}。
  收起