数据结构Word格式文档下载.docx
《数据结构Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构Word格式文档下载.docx（125页珍藏版）》请在冰点文库上搜索。
lchild）;
//销毁左孩子子树
rchild）
//有右孩子
rchild）;
//销毁右孩子子树
free（*DT）;
//释放根结点
//空指针赋0
BiTreeSearchBST（BiTreeT,KeyTypekey）
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
if（（!
T）||key==T->
data.key）
returnT;
elseif（key<
T->
returnSearchBST（T->
lchild,key）;
else
rchild,key）;
StatusSearchBST1（BiTreeT,KeyTypekey,BiTreef,BiTree*p）
//若查找成功,则返回指针p指向该数据元素指针结点,并返回TRUE,否则指针p
//指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL
if（!
T）
*p=f;
returnfalse;
elseif（key==T->
*p=T;
returnSearchBST1（T->
lchild,key,T,p）;
rchild,key,T,p）;
intInsertBST（BiTree*T,ElemTypee）
BiTreep,s;
SearchBST1（*T,e.key,NULL,&
p））
//查找不成功
s=（BiTree）malloc（sizeof（BiTNode））;
s->
data=e;
lchild=s->
rchild=NULL;
p）
*T=s;
//被插结点*s为新的根结点
elseif（e.key<
p->
p->
lchild=s;
//被插结点*s为左孩子,值小的在左边
rchild=s;
//被插结点*s为右孩子,值小的在右边
//书中已经有关键字相同的结点,不再插入
StatusDelete（BiTree*p）
//从二叉排序树中删除结点p,并重接的左或右子树
BiTreeq,s;
（*p）->
rchild）
//右子树空则只需重接他的左子树
q=（*p）;
*p=（*p）->
lchild;
free（q）;
elseif（!
lchild）
//只需重接他的右子树
rchild;
//左右子树均不空
P230方式d
q=*p;
s=（*p）->
while（s->
rchild）{
q=s;
s=s->
data=s->
data;
//s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值）
if（q!
=*p）
//此种情况是指类似只有左右两个子结点的情况,类似情况下不需改变p->
data已经完成所需改变
q->
rchild=s->
free（s）;
StatusDeleteBST（BiTree*T,KeyTypekey）
//若二叉排序树T存在关键字等于key的数据元素的时候,则删除该数据元素结点
//并返回true,否则返回false
*T）
if（key==（*T）->
returnDelete（T）;
（*T）->
returnDeleteBST（&
（*T）->
DeleteBST（&
return1;
voidTraverseDSTable（BiTreeDT,void（*Visit）（ElemType））
if（DT）
TraverseDSTable（DT->
lchild,Visit）;
//先中序遍历左子树
Visit（DT->
data）;
//再访问根结点
rchild,Visit）;
//最后中序遍历右子树
voidprint（ElemTypec）
printf（"
（%d,%d）"
c.key,c.others）;
intmain（）
BiTreedt,p;
inti;
KeyTypej;
ElemTyper[N]={
{45,1},{12,2},{53,3},{3,4},{37,5},{24,6},
{100,7},{61,8},{90,9},{78,10}
};
//以教科书P227图9.7（a）为例
InitDSTable（&
dt）;
//构造空表
for（i=0;
i<
N;
i++）
InsertBST（&
dt,r[i]）;
//依次插入数据元素
TraverseDSTable（dt,print）;
\n请输入待查找的值:
"
）;
scanf（"
%d"
&
j）;
p=SearchBST（dt,j）;
if（p）
表中存在此值:
dt,j）;
删除此值后:
\n"
return0;
}
求幂集链式实现
stdlib.h>
#defineTRUE
1
#defineFALSE0
#defineOK
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW
-2
#defineElemTypeint
#defineStatus
int
#defineLIST_INIT_SIZE100
//线性表存储空间的初始分配量
#defineLISTINCREMENT
10
//线性表存储空间的分配增量
typedefstructLNode
ElemTypedata;
//存储的数据
structLNode*next;
//后继的结点指针
}LNode,*LinkList;
voidInitList（LinkList*L）
//InitList_L即CreateList_L
//顺序（头插法）n个元素的值,建立带表头结点的单链线性表L
LNode*p;
（*L）=（LinkList）malloc（sizeof（LNode））;
（*L）->
next=NULL;
//先建立一个带头结点的单链表
}//InitList
intListLength（LinkListL）
//计算链表长度
inti=0;
LinkListp=L->
next;
while（p）
i++;
//存在加1
p=p->
//指向下一个结点
returni;
}//ListLength
StatusGetElem（LinkListL,inti,ElemType*e）
intj;
//L为带头结点的单链表的头指针
//当第i个元素存在时，其值赋给e并返回OK,否则返回false
p=L->
j=1;
//初始化,p指向第一个结点,j为计数器
while（p&
&
j<
i）
++j;
if（!
p||j>
i）
returnERROR;
//第i个元素不存在
*e=p->
//取第i个元素
returnOK;
}//GetElem
StatusListInsert（LinkList*L,inti,ElemTypee）
LinkListp;
intj;
LinkLists=（LinkList）malloc（sizeof（LNode））;
//生成新结点
//在带头结点的单链线性表L中第i个位置之前插入元素e
p=（*L）;
j=0;
i-1）
//寻找第i-1个结点
p||j>
i-1）
//i小于1或者大于表长+1
s->
next=p->
//插入L中
next=s;
}//ListInsert
StatusListDelete（LinkList*L,inti,ElemType*e）
LinkListp,q;
//在带头结点的单链线性表L中,删除第i个元素，并由e返回其值
while（p->
next&
j<
//寻找第i个结点,并令p指向其前趋
next）||j>
//删除位置不合理
q=p->
next=q->
//删除并释放结点
*e=q->
free（q）;
}//ListDelete
voidOutput（LinkListL）{
inte,i=1;
intlength=ListLength（L）;
for（i;
=length;
++i）
GetElem（L,i,&
e）;
%d"
e）;
//输出空集
length）
Empty"
//算法6.15P150
//线性表A表示集合A，线性表B表示幂集ρ（A）的一个元素。
//局部量k为进入函数时表B的当前长度。
//第一次调用本函数时，B为空表，i＝1。
voidGetPowerSet（inti,LinkListA,LinkList*B）{
ElemTypex;
intk;
if（i>
ListLength（A））
Output（*B）;
//输出当前B值，即ρ（A）的一个元素
else{
GetElem（A,i,&
x）;
k=ListLength（*B）;
ListInsert（B,k+1,x）;
GetPowerSet（i+1,A,B）;
ListDelete（B,k+1,&
intmain（）{
intn,i;
ElemTypee;
LinkLista,b;
请输入集合A的元素个数:
n）;
InitList（&
a）;
请输入集合中的元素:
for（i=1;
=n;
i++）{
ListInsert（&
a,i,e）;
b）;
进行冥集合运算!
GetPowerSet（1,a,&
/*
请输入集合A的元素个数：
3
请输入集合A的元素：
（空格区分）
123
*/
Haffman树（最优二叉树）的线性实现
memory.h>
limits.h>
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储赫夫曼数
typedefchar**HuffmanCode;
//动态分配数组存储赫夫曼编码树
//函数voidselect（）调用
intmin1（HuffmanTreet,inti）
intj,flag;
unsignedintk=UINT_MAX;
//取k为不小于可能的值
for（j=1;
=i;
j++）
if（t[j].weight<
k&
t[j].parent==0）
k=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
//s1为最小的两个值中序号小的那个
voidSelect（HuffmanTreet,inti,int*s1,int*s2）
*s1=min1（t,i）;
*s2=min1（t,i）;
if（*s1>
*s2）
j=*s1;
*s1=*s2;
*s2=j;
voidHuffmanCoding_FromLeaf（HuffmanTree*HT,HuffmanCode*HC,int*w,intn）
//w存放n个字符的权值（均>
0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
intm,s1,s2,i,start;
unsignedintc,f;
HuffmanTreep;
char*cd;
if（n<
=1）
return;
m=2*n-1;
*HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
//0号单元未用
for（p=*HT+1,i=1;
++i,++p,++w）
（*p）.weight=*w;
（*p）.parent=0;
（*p）.lchild=0;
（*p）.rchild=0;
for（;
=m;
++i,++p）
//初始化双亲位置
for（i=n+1;
i<
{
//建赫夫曼树
//在HT[1...i-1]
Select（*HT,i-1,&
s1,&
s2）;
（*HT）[s1].parent=i;
（*HT）[s2].parent=i;
（*HT）[i].lchild=s1;
（*HT）[i].rchild=s2;
升级会员 