中北大学算法与数据结构实验报告

更新时间：2024-05-24 22:36:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

中北大学推荐度：
相关推荐

实验类别：算法与数据结构专

业：信息与计算科学

班级：13080241 学号：1308024120 姓名：杨燕

中北大学理学院

实验一链表的应用（一）建立线性表

【实验内容】

1、画出详细规范的算法流程图 2、定义链表结点数据类型 3、定义链表数据类型 4、实现单向线性链表的建立 5、实现单向线性链表取元素 6、实现单向线性链表遍历 7、实现单向线性链表插入 8、实现单向线性链表删除【实验方法与步骤】

1、定义链表结点数据类型

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

其中int data;表示节点是整型数据，若定义浮点型的为：float data;其他类似。

2、定义链表数据类型

typedef char DateType typedef struct LNode { DateType data; struct LNode *next; }LNode,*LinkList;

3、实现单向线性链表的建立 #include

#include #include

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n)

{ //逆位序输入n个数据元素的值，建立带头结点的单链表L int i;

LNode *p;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一个带头结点的空链表

cout<<\请输入创建的单链表中的数据: <如：34,67,3,-9,45,...>\ for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode));//生成新结点 cin>>p->data; p->next=L->next;//将新结点插入到单链表的头 L->next=p;//修改单链表头结点的指针域 }//for结束

if(n) cout<<\成功创建一个单链表!\ else cout<<\创建了一个空链表!\}

void main() {

LinkList L;

int InitLNodeNum;

cout<<\ cout<>InitLNodeNum;

CreateList_L(L,InitLNodeNum); cout<<\ getch();

}//end of main() function

4、实现单向线性链表取元素

#include #include

#include #define ElemType int

#define LIST_MAX_LENGTH 100 //LIST_MAX_LENGTH是单链表L的最大长度 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n) { //创建一个带头结点的单链表L int i;

LNode *p;

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; } }

int GetElem_L(LinkList L,int i,int &e) //GetElem_L() function

{//L为带头结点的单链表的头指针，当第i个元素存在时，其值赋给e并返回OK， //否则返回Error LNode *p; int j=1;

p=L->next; //初始化，p指向链表第一个结点，j为计数器 while(p&&jnext;++j;} if(!p||j>i)

{ cout<<\这个元素 \不存在!\ getch(); exit(0); }//结束if e=p->data; return (e);

}//结束单链表的取元素

void main() //main() function {

LinkList L;

int e; //e can be Every DataType

int i,LListNodeNum; //j is a counter for cycle

cout<<\ cout<<\请输入创建的单链表的大小: \ cin>>LListNodeNum;

cout<<\请输入创建的单链表中的数据: \ CreateList_L(L,LListNodeNum);

cout<>i; //输入要提取的数据

if(i>LListNodeNum) cout<

cout<

5、实现单向线性链表遍历

#include #include #include #include

#define LIST_INIT_LENGTH 10 //LIST_INIT_LENGTH is the Init_Define_Length of LinkList typedef int ElemType; typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n) //CreatList_L() subfunction { //To Creatre a LinkList L with HeadNode

int i;

LNode *p;

int array[LIST_INIT_LENGTH]; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;

printf(\ for(i=0;i

for(i=0;idata=array[i]; //for example to a CreateList p->next=L->next; L->next=p; } //end of for

} //end of CreateList_L() function

void Contray(LinkList &head) //Contray() function

{ //Delete the NO.i element of LinkList and return by variable e LNode *p,*q; p=head;

head=NULL; while(p) { q=p; p=p->next; q->next=head; head=q; } //end of while

cout<

void main() //main() function {

LinkList L; LNode *p;

int i,LNodeNum; //j is just a counter for cycle

cout<<\ cout<<\ cin>>LNodeNum;

CreateList_L(L,LNodeNum); p=L;

cout<next; cout<data<<\ \ }

cout<

cout<<\ Contray(L); //call function Contray();

cout<data<<\ \ //output the LinkList after Contray L=L->next; }

cout<<\ getch();

}//end of main() function

6、实现单向线性链表插入

# include # include # include # include

# define INIT_LENGTH 10 # define OK 1 # define ERROR 0

typedef struct LNode //define LNode structure { int data; struct LNode *next;

}LNode,*Linklist;

int ListInsert_L(Linklist &L,int i,int e)

{//在带头结点的单链线性表L中第i个位置之前插入元素e LNode *p=L; int j=0;

while(p&&jnext; ++j; }

if(!p||j>i-1) //i小于1或i大于表长 { cout<<\错误!这个位置不存在!\ return (ERROR); }

LNode *s;

s=(Linklist)malloc(sizeof(LNode));//生成新结点 s->data=e;

s->next=p->next; p->next=s; return (OK); } //ListInsert_L() end

void main() //main() function { int i,j,e;

LNode node[10]; LNode *L,*p;

int array[INIT_LENGTH+1]={5,8,12,18,25,30,37,46,51,89}; L=node;

L=(Linklist)malloc(sizeof(LNode)); L->next=NULL; for (i=10;i>0;i--)

{ p=(Linklist)malloc(sizeof(LNode)); p->data=array[i-1]; p->next=L->next; L->next=p; } p=L;

cout<

cout <next; cout<data<<\ }

cout<>j;

cout<<\请输入要插入的元素: \ cin>>e;

if(ListInsert_L(L,j,e))

{ cout <next; cout<data<<\ } }

cout<

7、实现单向线性链表删除

#include #include #include

typedef struct LNode { int data; struct LNode *next; }LNode,*LinkList;

void CreateList_L(LinkList &L,int n) //CreateList_L() function { //创建一个带头结点的单链表L int i;

LNode *p;

L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=0;i

cin>>p->data; p->next=L->next; L->next=p; }//结束for

}//end of CreateList() function

int ListDelete_L(LinkList &L,int i,int &e) //ListDelete_L() function

{ //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 LNode *p,*q; int j=0; p=L;

while(p->next&&jnext;++j; }

if(!p||j>i-1) //删除位置不合理

{ cout<<\位置\的数据不存在!\ getch(); return(0); }

q=p->next; //用指针q指向被删除的结点 p->next=q->next; //删除第i个结点

e=q->data; //取出第i个结点数据域值 free(q); //释放第i个结点 return (e); }//结束删除元素

void main() //main() function {

LinkList L; LNode *p;

int e; //e can be Every DataType int i,j; //j is just a counter for cycle int LListNodeNum;

cout<<\ cout<<\请输入创建的单链表的结点个数: \ cin>>LListNodeNum;

cout<

cout<next;

while(p) //输出创建的单链表 { cout<data<<\ \ p=p->next;

}//end of for

cout<>i; //输入要删除的位置 if(i<= LListNodeNum)

{ cout<<\数据\已经被删除\ for(j=1;jnext; cout<data<<\ \输出新的单链表 }//结束for

cout<

else cout<<\ getch();

}//end of main() function

【实验结果】

1、写出实验的总结与体会，要简洁、真实、深刻；忌空话、套话

2、单向链表和双向链表在实现时的区别

3、单向链表如何修改实现循环链表

实验二链表的应用（二）栈的应用

【实验内容】

1、实现单向链栈的抽象数据类型

2、实现单向链栈的建立、销毁、取栈顶元素、压栈、弹栈的运算 3、给出包含括号和+、-、*、\\四则运算的运算符优先级表 4、创建运算符栈和运算数栈

5、实现有一定通用性的程序，实现一个四则运算表达式的求解 6、设计测试用的运算表达式，通过键盘输入进行测试【实验方法与步骤】

1、构造空链式队列算法

# include # include # include

# define MAXQSIZE 100 # define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct SqQueue//创建一个头结点 { QElemType *base; int front; int rear; }SqQueue;

int InitQueue(SqQueue &Q)

{ Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)//存储空间分配失败 { cout<

Q.front=Q.rear=0; return (OK); } //InitQueue() end

void main() //main function { SqQueue Q;

cout<

2、销毁链式队列算法

# include # include # include

# define MAXQSIZE 100 # define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct QNode //define structure QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr;

typedef struct LinkQueue //define structure LinkQueue { QueuePtr front; QueuePtr rear; }LinkQueue;

int EnQueue(LinkQueue &Q,QElemType e) //构造队列 { QNode *p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)

{ cout<

p->data=e;

p->next=NULL; if(Q.front==NULL) //new QNode { Q.front=Q.rear=p; return (OK); }

Q.rear->next=p; Q.rear=p;

return (OK); } //EnQueue() end

int DestroyQueue(LinkQueue &Q)//销毁队列Q { while(Q.front)

{ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; }

return (OK);

} //DestroyQueue() end

void main() //main() function { int i,e=1;

LinkQueue Q; QNode *q;

Q.front=Q.rear=NULL;

cout<

{ cout<<\请输入队列当中的数据 (如58到0或exit):\ cin>>e; if(e) EnQueue(Q,e); //构造队列 }

cout<

for(q=Q.front;q!=NULL;q=q->next) cout<data<<\ \ DestroyQueue(Q); //开始销毁 cout<

3、将元素压入链式栈算法

# include

# include # include # define Stack_Length 6 # define OK 1 # define ERROR 0 typedef int SElemType;

typedef struct SNode //define structure LinkStack { SElemType data; struct SNode *next; }SNode,*LinkStack;

int Push_L(LinkStack &top,SElemType e)

{//将元素e插入到栈S中，成为新的栈顶元素 SNode *q;

q=(LinkStack)malloc(sizeof(SNode)); if(!q)

{ cout<

q->data=e;

q->next=top->next; top->next=q; return (OK); } //Push_L() end

void main() //main function { SElemType e,i;

SNode node[Stack_Length]; SNode *p,*top=node;

SElemType array[Stack_Length]={5,8,12,18,30,37}; top=(LinkStack)malloc(sizeof(SNode)); top->next=NULL;

for(i=0;i

{ p=(LinkStack)malloc(sizeof(SNode)); p->data=array[i]; p->next=top->next; top->next=p; }

cout<

cout <

while(p->next)

{ p=p->next; cout<data<<\ }

cout<>e;

if(Push_L(top,e)) //call GetTop_L() cout<<\成功!栈顶元素=\ cout<next) { top=top->next; cout<data<<\ }

cout<

4、将元素弹出链式栈算法

# include # include # include # define Stack_Length 6 # define OK 1 # define ERROR 0 typedef int SElemType;

typedef struct SNode //define structure LinkStack { SElemType data; struct SNode *next; }SNode,*LinkStack;

int Pop_L(LinkStack &top,SElemType &e)

{//如果栈S空，返回ERROR；如果栈S不空，删除S的栈顶元素， //用e返回其值，并返回OK SNode *q; if(!top->next)

{ cout<

e=top->next->data;

q=top->next;

top->next=q->next; free(q);

return (OK); } //Pop_L() end

void main() //main function { SElemType e,i;

SNode node[Stack_Length]; SNode *p,*top=node;

SElemType array[Stack_Length]={5,8,22,98,70,89}; top=(LinkStack)malloc(sizeof(SNode)); top->next=NULL;

cout<

{ p=(LinkStack)malloc(sizeof(SNode)); p->data=array[i]; p->next=top->next; top->next=p; }

cout <

while(p->next) { p=p->next; cout<data<<\ }

if(Pop_L(top,e)) //弹出后的栈

cout<next) { top=top->next; cout<data<<\ }

cout<

5、取链式栈顶元素算法

# include # include # include # define Stack_Length 6 # define OK 1 # define ERROR 0 typedef int SElemType;

typedef struct SNode //define structure LinkStack { SElemType data; struct SNode *next; }SNode,*LinkStack;

int GetTop_L(LinkStack top,SElemType &e)

{//如果栈S空，返回ERROR；如果栈S不空， //用e返回栈S的栈顶元素，并返回OK if(!top->next)

{ cout<

{ e=top->next->data; return (OK); }

} //GetTop_L() end

void main() //main function { SElemType e,i;

SNode node[Stack_Length]; SNode *p,*top=node;

SElemType array[Stack_Length]={15,48,23,18,34,67}; top=(LinkStack)malloc(sizeof(SNode)); top->next=NULL;

for(i=0;i

{ p=(LinkStack)malloc(sizeof(SNode)); p->data=array[i]; p->next=top->next; top->next=p; }

cout<

while(p->next)

{ p=p->next; cout<data<<\ \ }

if(GetTop_L(top,e)) //得到栈顶元素 cout<

6、在链式队列尾插入新元素

# include # include # include

# define MAXQSIZE 100 # define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct QNode //define structure QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr;

typedef struct LinkQueue //define structure LinkQueue { QueuePtr front; QueuePtr rear; }LinkQueue;

int InitQueue(LinkQueue &Q) //InitQueue() subfunction { Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)

{ cout<

Q.front->next=NULL; return (OK); } //InitQueue() end

int EnQueue(LinkQueue &Q,QElemType e)

{//插入元素e为队列Q的新的队列为元素 QNode *p;

p=(QueuePtr)malloc(sizeof(QNode)); if(!p)

{ cout<

p->data=e; //将值e放入新结点的数据域 p->next=NULL; //令新结点的指针域为空 if(Q.front==NULL) { Q.front=Q.rear=p; return (OK); }

Q.rear->next=p; //将新结点插入到队列Q的尾 Q.rear=p; //修改队列Q的队尾指针 return (OK); } //EnQueue() end

void main() //main() function { int i,e=1;

LinkQueue Q; QNode *q;

InitQueue(Q); //call InitQueue() cout<

cout<

{ cout<<\请输入队列当中的数据 (如58到0或exit):\ cin>>e; if(e)

EnQueue(Q,e); //开始插入元素 }

cout<

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \

cout<

7、在链式队列头删除旧元素算法

# include # include # include

# define OK 1 # define ERROR 0

typedef int QElemType;

typedef struct QNode //define structure QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr;

typedef struct LinkQueue //define structure LinkQueue { QueuePtr front; QueuePtr rear; }LinkQueue;

int InitQueue(LinkQueue &Q) {//构造一个队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)

{ cout<

Q.front->next=NULL; return (OK); } //InitQueue() end

int EnQueue(LinkQueue &Q,QElemType e) { QNode *p;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)

{ cout<

p->data=e;

p->next=NULL; if(Q.front==NULL) { Q.front=p; Q.rear=p; return (OK); }

Q.rear->next=p; Q.rear=p; return (OK); } //EnQueue() end

int DeQueue(LinkQueue &Q,QElemType &e) {//如果队列空，返回ERROR；如果队列不空，

//删除Q的队列头元素，用e返回其值，并返回OK if(Q.front==Q.rear)

{ cout<

QNode *p;

p=Q.front->next; //令p指向队列Q的头 e=p->data; //将队头结点的值取出并放入e Q.front->next=p->next; //修改队头指针 free(p); //释放队头元素所占空间 return (OK); } //DeQueue() end

void main() //main() function { int i,e=1;

LinkQueue Q; QNode *q; InitQueue(Q);

cout<

{ cout<<\请输入队列中的元素(如58到0或exit):\ cin>>e; if(e) EnQueue(Q,e); //构造队列 }

cout<<\原来的队列为:\

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \ if(DeQueue(Q,e)) //开始删除 { cout<

for(q=Q.front->next;q!=NULL;q=q->next) cout<data<<\ \ }

cout<

8、创建运算符栈

# include # include # include

# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define OK 1 # define ERROR 0 typedef int SElemType;

typedef struct //define structure SqStack() { SElemType *base; SElemType *top; int stacksize; }SqStack;

int InitStack(SqStack &S) //InitStack() sub-function

{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)

{ cout<

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

return (OK); } //InitStack() end

void main() //main() function { SqStack S;

cout<

9、创建运算符数栈

#include #include #include #include

#define MAXSIZE 10

#define DUSTACKSIZE MAXSIZE typedef int SElemType ; typedef struct DuSqStack

{ SElemType data[MAXSIZE-1]; //array[0..MAXSIZE-1] for the DuSqStack int top1; //top1 is the pointer of DuSqStack S1 int top2; //top2 is the pointer of DuSqStack S2 int flag; //if flag variable=1 then operate S1 }DuSqStack; //else if flag=2 then operate S2

void InitDuSqStack(DuSqStack &S) //InitDuSqStack() function { S.top1=1; S.top2=MAXSIZE-2; //Initialize the Pointers of DuSqStack }//end of InitDuSqStack() function

int DuSqStackPush(DuSqStack &S,SElemType x) //DuSqStackPush() function { //S is a shared stack this function will push x into stack S cout<<\ cin>>x; if(S.top1+1==S.top2) //if the two stack are full, then return error

{ cout<>S.flag; if ((S.flag!=1)&&(S.flag!=2)) //flag == 1 or 2 ? otherwise return 0 {cout<

int DuSqStackPop(DuSqStack &S,SElemType &x) { //S is a shared stack

//this function will pop the top element //from S.top1 or S.top2 by x

cout<>S.flag; if((S.flag!=1)&&(S.flag!=2)) //if S.flag!=1,2 then ERROR { cout<1) //if S1 is not empty then operate S1 {S.top1--; //modify stack top pointer S.top1 x=S.data[S.top1];//pop x

into DuSqStack }//end of if else {cout<<\ return(0); } break; case 2: if(S.top2

}//end of DuSqStackPop() function

void main() //main() function {

DuSqStack S; SElemType x=2000; //push x into DuSqStack S

cout<<\ InitDuSqStack(S); //To Initilaize DuSqStack

DuSqStackPush(S,x); //Test DuSqStackPush function twice

DuSqStackPush(S,x); //for example to push two element into DuSqStack DuSqStackPop(S,x); //Test DuSqStackPop function //and return by x getch(); }

10、实现由一定通用性的程序，实现一个四则运算表达式的求解

#include #include #include #include

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType ; typedef struct SqStack { SElemType *base; SElemType *top; int stacksize; }SqStack;

int InitStack(SqStack &S) //InitStack() subfunction { //constructe a empty stack

S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base) { cout<<\ return (0); } S.top =S.base ; S.stacksize =STACK_INIT_SIZE; cout<<\ return (1);

}//end of InitStack() function

int Push(SqStack &S,SElemType e) //Push() subfunction { //Push element to SqStack if(S.top-S.base >S.stacksize) //Stack == full?

{ S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT*sizeof(SElemType))); if(!S.base) { cout<<\ return(0); } S.top=S.base+S.stacksize; //To modify pointer of Stack top S.stacksize+=STACKINCREMENT; //To modify the size of stack } //end of if *S.top++=e; //S.top++ and push e into stack S return (1);

}//end of Push() subfunction

int StackEmpty(SqStack &S) //StackEmpty() function { //judge empty stack ? if(S.top==S.base) return(1); //empty return 1 else return(0); }

int Pop(SqStack &S,SElemType &e)

{ //if empty(S) then Error,otherwise Delete the S.top element //and return it by variable e if(S.top==S.base) { cout<<\ return (0); } e=*--S.top; //S.top-- and assign the values to e return(1); }

void Conversion() //Conversion() function {

SqStack S; //S is a SqStack SElemType N,e; InitStack(S); //constructe a empty stack S printf(\ scanf(\ while(N) { Push(S,N%8); N=N/8; }

printf(\ while(!StackEmpty(S)) //no empty then output { Pop(S,e);

printf(\ }

}//end of conversion() function

void main() //main() function {

cout<<\ Conversion();

cout<

}//end of main()

【实验结果】

1、写出实验的总结与体会，要简洁、真实、深刻；忌空话、套话

2、顺序栈和链栈在实现时的区别

3、在增加了中括号大括号和方幂运算后的程序如何规定运算优先级表

实验三链表的应用（三）哈夫曼树和哈夫曼编码

【实验内容】

1、实现二叉树的抽象数据类型 2、实现二叉树的遍历运算 3、实现二叉树的建立的运算 4、实现创建哈夫曼树的算法

5、给出测试字符表，并对表中字符进行哈夫曼编码 6、对字符表中的字符构成的信息源进行哈夫曼编码和译码【实验方法与步骤】

1、先序遍历二叉树的递归算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //define structure BiTree { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //创建一个二叉树 { TElemType ch;

cout<<\请输入数据(/ for NULL node!) : \ cin>>ch;

if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (0); } //if end T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 } //else end return (OK);

} //CreateBiTree() end

int PreOrderTraverse(BiTree T) {//先序遍历二叉树 if(T)

{ cout<data<<\ //visite T if (PreOrderTraverse(T->lchild)) //访问左孩子 if (PreOrderTraverse(T->rchild)) //访问右孩子 return (OK); return (ERROR); } //if end else

return (OK);

} //PreOrderTraverse() end

void main() //main() function { BiTree T;

cout<

2、中序遍历二叉树的递归算法

# include # include

# include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //define structureBiTree { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) {//创建一个二叉树 TElemType ch;

cout<<\ cin>>ch; //输入数据 if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //创建左孩子 CreateBiTree(T->rchild); //创建右孩子 }

return (OK);

} //CreateBiTree() end

int InOrderTraverse(BiTree T) {//中序遍历二叉树 if(T)

{ if (InOrderTraverse(T->lchild)) //访问左孩子 { cout<data<<\ //访问根 if(InOrderTraverse(T->rchild)) //访问右孩子 return (OK); } return (ERROR); } //if end else

return (OK);

} //InOrderTraverse() end

void main() //main() function

{ BiTree T;

cout<

3、后序遍历二叉树的递归算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //定义二叉树结点 { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //构造二叉树 { TElemType ch;

cout<<\请输入数据 (/ for NULL node!) : \ cin>>ch;

if(ch=='/') T=NULL;

else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 }

return (OK);

} //CreateBiTree() end

int PostOrderTraverse(BiTree T) {//后序遍历二叉树 if(T)

{ if (PostOrderTraverse(T->lchild)) //访问左孩子 if(PostOrderTraverse(T->rchild)) //访问右孩子 { cout<data<<\ //访问根 return (OK); } return (ERROR); } else

return (OK);

} //PostOrderTraverse() end

void main() //main() function { BiTree T;

cout<

cout<<\ getch(); } //main()

4、建立二叉树算法

# include # include # include

# define OK 1 # define ERROR 0

typedef char TElemType;

typedef struct BiTNode //定义二叉树结点 { TElemType data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

int CreateBiTree(BiTree &T) //构造二叉树 { TElemType ch;

cout<<\请输入数据(/for NULL node!):\ cin>>ch;

if(ch=='/') T=NULL; else

{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) { cout<<\//no alloction return (ERROR); }

T->data=ch;

CreateBiTree(T->lchild); //构造左孩子 CreateBiTree(T->rchild); //构造右孩子 }

return (OK);

} //CreateBiTree() end

void main() //main() function { BiTree T;

cout<

5、求哈夫曼树及哈夫曼编码算法

# include # include # include # include # include

# define MAX_LENGTH 100 typedef char **HuffmanCode;

typedef struct //定义哈夫曼树的结点 { unsigned int weight;

unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree;

void Select(HuffmanTree HT,int i,int &s1,int &s2) //Select sub-function { int j,k=1; //s1 is the least of HT[].weight while(HT[k].parent!=0) //s2 is the second least of HT[].weight k++; s1=k;

for(j=1;j<=i;++j)

if(HT[j].parent==0&&HT[j].weight

while((HT[k].parent!=0||k==s1)) k++; s2=k;

for(j=1;j<=i;++j)

if(HT[j].parent==0&&HT[j].weight

void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)

{//w存放n个字符的权值，构造哈夫曼数HT，并求出n个字符的哈夫曼编码HC int m,i,s1,s2,start,c,f; HuffmanTree p; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

//分配m+1个哈夫曼树结点的存储空间，0号单元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) //初始化HT的前n个分量 { p->weight=*w; cout<parent=0; p->lchild=0; p->rchild=0; }

for(;i<=m;++i,++p) //初始化HT的后m-n个分量 { p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; }

cout<