大连理工大学数据结构(一)上机作业答案张老师文档格式.doc

1、L.elemi）;/输出顺序表中的元素void ListOutput_Sq（SqList L）int i,n;n=L.length;%2d,L.elemi）;/顺序表逆置void ReverseList_Sq（SqList &ElemType p;n/2; p=L.elemi; L.elemi=L.elemn-i-1; L.elemn-i-1=p;void main（）SqList L;InitList_Sq（L）;ListInput_Sq（L）;ListOutput_Sq（L）;ReverseList_Sq（L）;printf（n输出结果为：2 从键盘读入n个整数（升序），请编写算法实现：（

2、1） CreateList（）：建立带表头结点的单链表；（2） PrintList（）：显示单链表，（形如：H-10-20-30-40）;（3） InsertList（）：在有序单链表中插入元素x；（4） ReverseList（）：单链表就地逆置；（5） DelList（）：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateList（LinkList &L,int n）int i

3、;LNode *p,*q;L=（LinkList）malloc（sizeof（LNode）;L-next=NULL;q=L;请输入所要建立的单链表所包含的元素：i+）p=（LinkList）malloc（sizeof（LNode）;scanf（p-data）;p-q-next=p;q=p;void PrintList（LinkList L）LNode *p;p=L-next;while（p）,p-p=p-void InsertList（LinkList L,ElemType m）LNode *p,*q,*s;p=L;q=L-while（q&q-dataif（q）s=（LinkList）mall

4、oc（sizeof（LNode）;s-data=m;next=q;next=s;elsevoid ReverseList（LinkList &if（L-next&L-next-next）p=L-q=p-while（q）p=q;q=q-p-next=L-L-void DeleteList（LinkList &L,ElemType mink,ElemType maxk）LNode *p=L,*q;while（p-=mink）q=p;maxk）p-LinkList L;int n,number;ElemType e,mink,maxk;do*n建立单链表请按1.n显示单链表请按2.n有序插入新元素请

5、按3.n单链表就地逆置请按4.n删除大于mink且小于maxk的所有元素请按5.n退出请按0.nn请选择操作：number）;switch（number）case 1:printf（请输入单链表中的节点个数： scanf（ CreateList（L,n）; break;case 2:要执行本操作请先建立单链表，请输入单链表中的节点个数： printf（单链表为： PrintList（L）; case 3:请输入有序表中插入的值： scanf（e）; InsertList（L,e）;PrintList（L）; case 4: printf（单链表逆置： ReverseList（L）; case

6、5:请输入mink和maxk：%d%dmink,&maxk）; DeleteList（L,mink,maxk）;while（number!=0）;第二次作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。例如，输入表达式： a+b/c-（d*e+f）*g 输出其后缀表达式：abc/+de*f+g*- string.hmath.h#define OVER -2#define ture 1#define false 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef c

7、har ElemType;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;/定义结构int InitStack（SqStack&S） S.base=（ElemType*）malloc（STACK_INIT_SIZE*sizeof（ElemType）; if（!S.base） exit（OVER）; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/建栈int Push（SqStack&S,SElemType e）if（S.top-S.base=S.s

8、tacksize） S.base=（ElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（ElemType）;if（!S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/插入int GetTop（SqStack&S,SElemType &e）if（S.top=S.base）return ERROR;e=*（S.top-1）;/获取栈顶元素int Pop（SqStack&if（S.top=S.base） return ERROR;e=*-S.top;re

9、turn OK;/删除栈顶并用e返回值int StackEmpty（SqStack S）if（S.top=S.base）return ture;elsereturn false;int Pass（char suffix,SElemType ch） char *p;p=suffix; while（*p!=0） p+;*p=ch;*（p+1）=;return 0;/把操作数ch传进数组suffixvoid add（char exp） char *p; p = exp; while （*p != ） +p; *p = # *（p + 1） = /在表达式结尾加结束符void del（char suf

10、fix） p = suffix; p+; /将字符串结尾附成0int Precede（char c）if （c = * | c = /return 2; if （c = +-return 1;（）return -1; else return -2;/优先级比较void transform（char suffix, char exp）char *p, ch, c;p = exp;ch = *p;SqStack S;InitStack （S）;Push （S, while（!StackEmpty（S）if （chach= Precede（ch）GetTop（S, c）;Push（S, ch）;if

11、 （ch !ch = *+p;/后缀表达式转化int main（）char suffix100;suffix0 = char exp100;printf （请输入一个表达式：gets（exp）;add（exp）;transform （suffix, exp）;del（suffix）;后缀表达式为： %sn, suffix）;第三次作业二叉树采用二叉链表存储，试设计算法实现：1 CreateBT（BiTree &T）：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；如输入：AB#D#CE#F# 则建立如下图所示二叉树的二叉链表2 ExchangeBT（BiTree T

12、）: 设计递归算法实现二叉树中所有结点的左右孩子交换；3 CountLeaf（BiTree T, TElemType x, int &count）: 统计以值为x的结点为根的子树中叶子结点的数目；4 DispBiTree（BiTree T, int level） : 按树状打印二叉树。BCFAED 打印得到：#C#F#E#D#B提示：对于根为T，层次为level的子树： 打印其下一层（level+1层）右子树； 打印根结点； 打印其下一层（level+1层）左子树； *结点左边的#个数为其层次数*typedef struct BiTNodechar data;struct BiTNode *l

13、child,*rchild;BiTNode,*BiTree;/输入先序序列，创建二叉树的二叉链表void CreateBT（BiTree &T）char ch;%cch）;if（ch=T=NULL;T=（BiTNode *）malloc（sizeof（BiTNode）;T-data=ch;CreateBT（T-lchild）;rchild）;/交换二叉树中结点的左右孩子void ExchangeBT（BiTree &BiTree temp;if（T）temp=T-lchild;lchild=T-rchild;lchild=temp;ExchangeBT（T-/查找值为x的结点BiTree Se

14、archTree（BiTree T,char x）BiTree NTree;if（T-data=x）return T;NTree=SearchTree（T-lchild,x）;if（NTree=NULL）NTree=SearchTree（T-rchild,x）;return NTree;return NULL;/统计一x为根的子树中叶子结点的个数void LeafCount（BiTree T,int &count）if（T-lchild=NULL）&（T-rchild=NULL）count+;LeafCount（T-lchild,count）;rchild,count）;/按树状打印输出二叉树

15、的元素，level表示结点的层次void PrintBiTree（BiTree T,int level）PrintBiTree（T-lchild,level+1）;for（i=0;level;#%cn,T-rchild,level+1）;BiTree T,SecT;char Secch;int count=0;输入先序序列建立二叉树：CreateBT（T）;二叉树为：PrintBiTree（T,0）;交换结点的左右孩子n ExchangeBT（T）;n此时二叉树为：输入要统计叶子结点个数的子树的根：fflush（stdin）;/清理缓存Secch）;SecT=SearchTree（T,Secch）;LeafCount（SecT, count）;叶子结点数为：%dn,count）;