数据结构Word格式文档下载.docx

1、lchild）; / 销毁左孩子子树 rchild） / 有右孩子 rchild）; / 销毁右孩子子树 free（*DT）; / 释放根结点 / 空指针赋0 BiTree SearchBST（BiTree T,KeyType key） / 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素 / 若查找成功,则返回指向该数据元素结点的指针,否则返回空指针 if（!T） | key = T-data.key） return T;else if （key return SearchBST（T-lchild,key）;elserchild,key）;Status SearchBST1（

2、BiTree T,KeyType key,BiTree f,BiTree *p） / 若查找成功,则返回指针p指向该数据元素指针结点,并返回TRUE,否则指针p / 指向查找路径上访问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL if （!T） *p = f;return false;else if （key = T-*p = T;return SearchBST1（T-lchild,key,T,p）;rchild,key,T,p）;int InsertBST（BiTree *T,ElemType e） BiTree p,s;SearchBST1（*T,e.key

3、,NULL,&p） / 查找不成功 s = （BiTree）malloc（sizeof（BiTNode）;s-data = e;lchild = s-rchild = NULL;p） *T = s; / 被插结点*s为新的根结点 else if （e.key p-lchild = s; / 被插结点*s为左孩子,值小的在左边 rchild = s; / 被插结点*s为右孩子,值小的在右边 / 书中已经有关键字相同的结点,不再插入 Status Delete（BiTree *p） / 从二叉排序树中删除结点p,并重接的左或右子树 BiTree q,s;（*p）-rchild） / 右子树空则只需

4、重接他的左子树 q = （*p）;*p = （*p）-lchild;free（q）;else if （!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）;Status DeleteBST（BiTree *T,KeyTy

5、pe key） / 若二叉排序树T存在关键字等于key的数据元素的时候,则删除该数据元素结点 / 并返回true,否则返回false *T） if （key = （*T）-return Delete（T）; （*T）-return DeleteBST（&（*T）-DeleteBST（&return 1;void TraverseDSTable（BiTree DT,void（*Visit）（ElemType） if （DT） TraverseDSTable（DT-lchild,Visit）; / 先中序遍历左子树 Visit（DT-data）; / 再访问根结点 rchild,Visit）; /

6、 最后中序遍历右子树 void print（ElemType c） printf（%d,%d）,c.key,c.others）;int main（） BiTree dt,p;int i;KeyType j;ElemType rN= 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#define TRUE 1 #define FALSE 0 #define OK#define ERROR 0 #define INFEASIBLE -

7、1 #define OVERFLOW -2 #define ElemType int #define Status int #define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量 typedef struct LNode ElemType data; / 存储的数据 struct LNode *next; / 后继的结点指针 LNode,*LinkList;void InitList（LinkList *L） / InitList_L即CreateList_L / 顺序（头插法）n个元

8、素的值,建立带表头结点的单链线性表L LNode *p;（*L） = （LinkList）malloc（sizeof（LNode）;（*L）-next = NULL; / 先建立一个带头结点的单链表 / InitList int ListLength（LinkList L） / 计算链表长度 int i=0;LinkList p = L-next;while（p） i+; / 存在加1 p = p- / 指向下一个结点 return i; / ListLength Status GetElem（LinkList L,int i,ElemType *e） int j;/ L为带头结点的单链表的头

9、指针 / 当第i个元素存在时，其值赋给e并返回OK,否则返回false p = L- j = 1; / 初始化,p指向第一个结点,j为计数器 while（p & j i） return ERROR; / 第i个元素不存在 *e = p- / 取第i个元素 return OK; / GetElem Status ListInsert（LinkList *L,int i,ElemType e） LinkList p; int j;LinkList s = （LinkList）malloc（sizeof（LNode）; / 生成新结点 / 在带头结点的单链线性表L中第i个位置之前插入元素e p =

10、（*L）; j = 0; i-1） / 寻找第i-1个结点 p|ji-1） / i小于1或者大于表长+1 s-next = p- / 插入L中 next = s; / ListInsert Status ListDelete（LinkList *L,int i,ElemType *e） LinkList p,q;/ 在带头结点的单链线性表L中,删除第i个元素，并由e返回其值 while（p-next & j / 删除位置不合理 q = p-next = q- / 删除并释放结点 *e = q- free（q）; / ListDelete void Output（LinkList L） int

11、e,i = 1;int length = ListLength（L）;for（ i;=length;+i） GetElem（L,i,&e）;%d ,e）;/ 输出空集 length） Empty/ 算法6.15 P150 / 线性表A表示集合A，线性表B表示幂集（A）的一个元素。/ 局部量k为进入函数时表B的当前长度。/ 第一次调用本函数时，B为空表，i1。void GetPowerSet（int i, LinkList A, LinkList *B） ElemType x;int k;if （i ListLength（A） Output（*B）; / 输出当前B值，即（A）的一个元素 els

12、e GetElem（A, i, &x）;k = ListLength（*B）;ListInsert（B, k+1, x）;GetPowerSet（i+1, A, B）;ListDelete（B, k+1, &int main（） int n,i;ElemType e;LinkList a,b;请输入集合A的元素个数:n）;InitList（&a）;请输入集合中的元素:for（i=1;=n;i+） ListInsert（&a,i,e）;b）;进行冥集合运算!GetPowerSet（1, a, &/* 请输入集合A的元素个数：3 请输入集合A的元素：（空格区分） 1 2 3 */Haffman树（

13、最优二叉树）的线性实现memory.hlimits.hunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; / 动态分配数组存储赫夫曼数 typedef char* HuffmanCode; / 动态分配数组存储赫夫曼编码树 / 函数void select（）调用 int min1（HuffmanTree t,int i） int j,flag;unsigned int k=UINT_MAX; / 取k为不小于可能的值 for（j = 1;= i; j+） if（tj.weight *s2） j=*

14、s1;*s1=*s2;*s2=j;void HuffmanCoding_FromLeaf（HuffmanTree *HT,HuffmanCode *HC,int *w,int n） / w存放n个字符的权值（均0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m,s1,s2,i,start;unsigned int c,f;HuffmanTree p;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 / 建赫夫曼树 / 在HT1.i-1 Select（*HT,i-1,&s1,&s2）;（*HT）s1.parent = i; （*HT）s2.parent = i;（*HT）i.lchild = s1; （*HT）i.rchild = s2;