10《数据结构》【005】

链接：https://pan.baidu.com/s/1jHDInT5qZOnvIZPjyVHOBQ

提取码：2r91 复制这段内容后打开百度网盘手机APP，操作更方便哦！

若资源有问题欢迎追问~

/* 二叉树应用 */#include "stdio.h"

#include "stdlib.h"typedef char ElemType /* 结点数据的类型 */

typedef struct BiTNode{

ElemType data

struct BiTNode *lchild,*rchild

}BiTNode /* 树结点类型 *//*栈的定义及基本操作*/

#define MaxSize 100

typedef BiTNode* SElemType /* 栈和队列的结点类型，用于存放树结点 */

typedef struct {

SElemType elem[MaxSize]

int top

}SqStack /* 栈 */void InitStack(SqStack *pS) /* 初始化栈,开始时栈为空 */

{

pS->top=0/* top指向栈顶的上一个元素 */

}int Push(SqStack *pS,SElemType e) /* 进栈 */

{

if (pS->top==MaxSize-1) /* 栈满 */

return 0 pS->elem[pS->top]=e

pS->top=pS->top+1

return 1

}int Pop(SqStack *pS,SElemType *pe)/* 出栈 */

{

if (pS->top==0) /* 栈空 */

return 0 pS->top = pS->top - 1

*pe = pS->elem[pS->top]

return 1

}/*队列（循环队列）的定义及基本操作*/typedef struct {

SElemType elem[MaxSize]

int front,rear

}SqQueue /* 队列 */void InitQueue(SqQueue* pQ) /* 初始化队列,开始时队列为空 */

{

pQ->front=pQ->rear=0

}int EnQueue(SqQueue* pQ,SElemType e) /* 进队 */

{

if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满 */

return 0

pQ->elem[pQ->rear] = e

pQ->rear = (pQ->rear+1)%MaxSize

return 1

}int DeQueue(SqQueue* pQ,SElemType* pe) /* 出队 */

{

if (pQ->rear == pQ->front)/* 队空 */

return 0

*pe = pQ->elem[pQ->front]

pQ->front = (pQ->front+1)%MaxSize

return 1

}

/* 先根遍历 */

void preorder(BiTNode *bt)

{ if(bt!=NULL)

{ printf("%c ",bt->data)

preorder(bt->lchild)

preorder(bt->rchild)

}

} /* 中根遍历 */

void inorder(BiTNode *bt)

{ if(bt!=NULL)

{ inorder(bt->lchild)

printf("%c ",bt->data)

inorder(bt->rchild)

}

}

/* 后根遍历 */

void postorder(BiTNode *bt)

{ if(bt!=NULL)

{ postorder(bt->lchild)

postorder(bt->rchild)

printf("%c ",bt->data)

}

}/* 非递归算法的中根遍历（后进先出，用了栈的思想） */

void inorder_fdg(BiTNode *bt)

{

BiTNode *p

SqStack s

InitStack(&s)

p=bt

do

{ while(p!=NULL)

{ Push(&s,p)

p=p->lchild

}

if(s.top!=0)

{ Pop(&s,&p)

printf("%c ",p->data)

p=p->rchild

}

}while(s.top!=0||p!=NULL)

}/* 用队列实现层次遍历 */

void lev_traverse(BiTNode* bt)

{

SqQueue q

BiTNode *p

p=bt

InitQueue(&q)

EnQueue(&q,p)

while(!(q.rear==q.front)) { /* 当队列不空 */

DeQueue(&q,&p)

printf("%c ",p->data) if(p->lchild!=NULL)

EnQueue(&q,p->lchild) if(p->rchild!=NULL)

EnQueue(&q,p->rchild)

}

}

/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过函数返回,避免使用指针的指针 */

BiTNode *crt_bt_pre()

{ char ch

BiTNode *bt

scanf("%c",&ch) if(ch==' ') bt=NULL

else

{ bt=(BiTNode *)malloc(sizeof(BiTNode))

bt->data=ch

bt->lchild=crt_bt_pre()

bt->rchild=crt_bt_pre()

}

return(bt)

}/* 利用先根序列建立二叉树，空的子树也要输入，用空格表示,建立的树通过参数返回,注意和上述方法比较，想想还有什么办法？ */

void crt_bt_pre_2(BiTNode **bt)

{ char ch

scanf("%c",&ch) if(ch==' ') (*bt)=NULL

else

{ (*bt)=(BiTNode *)malloc(sizeof(BiTNode))

(*bt)->data=ch

crt_bt_pre_2(&(*bt)->lchild)

crt_bt_pre_2(&(*bt)->rchild)

}

}

/* 求叶子数 */

int leaf(BiTNode *bt)

{

if (bt==NULL) return 0

else {

if (bt->lchild==NULL&&bt->rchild==NULL) return 1

else

return leaf(bt->lchild)+leaf(bt->rchild)

}}/* 求树的高度 */

int high(BiTNode *bt)

{

if (bt==NULL) return 0

else {

return max(high(bt->lchild),high(bt->rchild))+1

}}

/* 二叉树的释放*/

void freetree(BiTNode *bt)

{ if(bt!=NULL)

{ freetree(bt->lchild)

freetree(bt->rchild)

free(bt)

bt=NULL

}

}main()

{

BiTNode *T,*temp[20] /* 笨方法建立二叉树 */

/* temp[0]=(BiTNode*)malloc(sizeof(BiTNode))

temp[0]->data = '-' temp[1]=(BiTNode*)malloc(sizeof(BiTNode))

temp[1]->data = '+'

temp[0]->lchild = temp[1] temp[2]=(BiTNode*)malloc(sizeof(BiTNode))

temp[2]->data = '/'

temp[0]->rchild = temp[2] temp[3]=(BiTNode*)malloc(sizeof(BiTNode))

temp[3]->data = 'a'

temp[3]->lchild=NULLtemp[3]->rchild=NULL

temp[1]->lchild = temp[3] temp[4]=(BiTNode*)malloc(sizeof(BiTNode))

temp[4]->data = '*'

temp[1]->rchild = temp[4] temp[5]=(BiTNode*)malloc(sizeof(BiTNode))

temp[5]->data = 'e'

temp[5]->lchild=NULLtemp[5]->rchild=NULL

temp[2]->lchild = temp[5] temp[6]=(BiTNode*)malloc(sizeof(BiTNode))

temp[6]->data = 'f'

temp[6]->lchild=NULLtemp[6]->rchild=NULL

temp[2]->rchild = temp[6] temp[7]=(BiTNode*)malloc(sizeof(BiTNode))

temp[7]->data = 'b'

temp[7]->lchild=NULLtemp[7]->rchild=NULL

temp[4]->lchild = temp[7] temp[8]=(BiTNode*)malloc(sizeof(BiTNode))

temp[8]->data = '-'

temp[4]->rchild = temp[8] temp[9]=(BiTNode*)malloc(sizeof(BiTNode))

temp[9]->data = 'c'

temp[9]->lchild=NULLtemp[9]->rchild=NULL

temp[8]->lchild = temp[9] temp[10]=(BiTNode*)malloc(sizeof(BiTNode))

temp[10]->data = 'd'

temp[10]->lchild=NULLtemp[10]->rchild=NULL

temp[8]->rchild = temp[10] T=temp[0] */

/*输出树和各种遍历、叶子数、树的高度*/

/*printf("\ntree:\n")

printf(" -\n")

printf(" +/\n")

printf(" a *e f\n")

printf("0 0b - 0 00 0\n")

printf(" 0 0c d\n") printf("\n\nPreOrder:\n")

preorder(T) printf("\nInOrder:\n")

inorder(T) printf("\nPostOrder:\n")

postorder(T) printf("\ninorder_fdg:\n")

inorder_fdg(T) printf("\nlev_traverse:\n")

lev_traverse(T)

printf("\nleaf num:%d",leaf(T))

printf("\nTree high:%d",high(T))

freetree(T) */ /* 按先序列建树，用空格表示空子树*/ printf("\n\nplease input inorder:such as 'abc de g f '\n")

/*T = crt_bt_pre()*/

crt_bt_pre_2(&T) printf("\n\nPreOrder:\n")

preorder(T) printf("\nInOrder:\n")

inorder(T) printf("\nPostOrder:\n")

postorder(T) printf("\ninorder_fdg:\n")

inorder_fdg(T) printf("\nlev_traverse:\n")

lev_traverse(T)

printf("\nleaf num:%d",leaf(T))

printf("\nTree high:%d",high(T))

freetree(T)

getch()

}

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedef int ElemType

/*单项链表的声明*/

typedef struct PolynNode{

int coef// 系数

int expn// 指数

struct PolynNode *next}PolynNode,*PolynList

/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/

/*指数系数一对一对输入*/ void CreatePolyn(PolynList &L,int n)

{

int i

下载

原文档已转码为如下格式，以便移动设备查看

数据结构(c语言)用单链表存储一元多项式,并实现两个多项式的相加运算【最新】

阅读：1037次 页数：36页 2016-03-21 举报

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

typedef int ElemType

/*单项链表的声明*/

typedef struct PolynNode{

int coef// 系数

int expn// 指数

struct PolynNode *next}PolynNode,*PolynList

/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/

/*指数系数一对一对输入*/ void CreatePolyn(PolynList &L,int n)

{

int i

PolynList p,q

L=(PolynList)malloc(sizeof(PolynNode))// 生成头结点

L->next=NULL

q=L

printf("成对输入%d个数据\n",n)

for(i=1i<=ni++)

{

p=(PolynList)malloc(sizeof(PolynNode))

scanf("%d%d",&p->coef,&p->expn)//指数和系数成对输入

q->next=p

q=q->next

}

p->next=NULL

}

// 初始条件:单链表L已存在

// 操作结果: 依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败

void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType)) {

PolynList p=L->next

while(p)

{

vi(p->coef, p->expn)

if(p->next)

{

printf(" + ")//“+”号的输出,最后一项后面没有“+”

}

p=p->next

}

printf("\n")

}

/*ListTraverse()调用的函数(类型要一致)*/ void visit(ElemType c, ElemType e) {

if(c != 0)

{

printf("%dX^%d",c,e)//格式化输出多项式每一项

}

}

/* 多项式相加,原理:归并 */ /* 参数:两个已经存在的多项式 */ /* 返回值:归并后新的多项式的头结点 */

PolynList MergeList(PolynList La, PolynList Lb) {

PolynList pa, pb, pc, Lc

pa = La->next

pb = Lb->next

Lc = pc = La// 用La的头结点作为Lc的头结点

while(pa&&pb)

{

if(pa->expn <pb->expn)

{

pc->next = pa//如果指数不相等,pc指针连上指数小的结

点,

pc = pa

pa = pa->next//指向该结点的指针后移

}

else if (pa ->expn >pb->expn )

{

pc->next = pb//pc指针连上指数小的结点,

pc = pb

pb = pb->next//指向该结点的指针后移

}

else //(pa ->expn = pb->expn )

{

pa->coef = pa->coef + pb->coef//指数相等时,系数相加

pc->next = pa

pc = pa

pa = pa->next//两指针都往后移

pb = pb->next

}

}

pc->next = pa ? pa:pb// 插入剩余段

return Lc

}

void main()

{

PolynList ha,hb,hc

printf("非递减输入多项式ha, ")

CreatePolyn(ha,5)// 正位序输入n个元素的值

printf("非递减输入多项式hb, ")

CreatePolyn(hb,5)// 正位序输入n个元素的值

---