《数据结构》实验三——二叉树排序算法
*试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。*/
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 8
struct 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 ");
}。
答：详情>>
答：一、要有学科专业知识 二、要具备先进的培训理念 三、培训方法和技能 四、较强的组织管理能力详情>>
答：这是两个概念 两个出版社而已详情>>
答：考试院是教育厅的直属事业单位详情>>
