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

1 将顺序表逆置，要求用最少的附加空间。参考答案#include#include#include#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int ElemType;typedef int Status;#define LIST_INIT_SIZE 100#define LISTTINCREMENT 10typedef structElemType *elem;int length;int listsize;SqList;/创建空顺序表Status InitList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;/创建顺序表，插入元素void ListInput_Sq(SqList &L)int n,i;printf(input the length of Sqlist:);scanf(%d,&n);L.length=n;for(i=0;in;i+)printf(input elem:);scanf(%d,&L.elemi);/输出顺序表中的元素void ListOutput_Sq(SqList L)int i,n;n=L.length;for(i=0;in;i+)printf(%2d,L.elemi);/顺序表逆置void ReverseList_Sq(SqList &L)int i,n;ElemType p;n=L.length;for(i=0;i10-20-30-40）;（3） InsertList()：在有序单链表中插入元素x；（4） ReverseList()：单链表就地逆置；（5） DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：#include#include#include#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateList(LinkList &L,int n)int i;LNode *p,*q;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=L;printf(请输入所要建立的单链表所包含的元素：);for(i=0;idata);p-next=NULL;q-next=p;q=p;void PrintList(LinkList L)LNode *p;p=L-next;while(p)printf(%d,p-data);p=p-next;printf(n);void InsertList(LinkList L,ElemType m)LNode *p,*q,*s;p=L;q=L-next;while(q&q-datanext;if(q)s=(LinkList)malloc(sizeof(LNode);s-data=m;s-next=q;p-next=s;elses=(LinkList)malloc(sizeof(LNode);s-data=m;s-next=NULL;p-next=s;void ReverseList(LinkList &L)LNode *p,*q;if(L-next&L-next-next)p=L-next;q=p-next;p-next=NULL;while(q)p=q;q=q-next;p-next=L-next;L-next=p;void DeleteList(LinkList &L,ElemType mink,ElemType maxk)LNode *p=L,*q;while(p-next&p-next-datanext;q=p;while(q&q-datanext;p-next=q;void main()LinkList L;int n,number;ElemType e,mink,maxk;doprintf(*n);printf(建立单链表请按1.n);printf(显示单链表请按2.n);printf(有序插入新元素请按3.n);printf(单链表就地逆置请按4.n);printf(删除大于mink且小于maxk的所有元素请按5.n);printf(退出请按0.n);printf(*n);printf(n请选择操作：n);scanf(%d,&number);switch(number)case 1:printf(请输入单链表中的节点个数：); scanf(%d,&n); CreateList(L,n); break;case 2:printf(要执行本操作请先建立单链表，请输入单链表中的节点个数：); scanf(%d,&n); CreateList(L,n); printf(单链表为：); PrintList(L); break; case 3:printf(要执行本操作请先建立单链表，请输入单链表中的节点个数：); scanf(%d,&n); CreateList(L,n); printf(请输入有序表中插入的值：); scanf(%d,&e); InsertList(L,e);PrintList(L); break; case 4:printf(要执行本操作请先建立单链表，请输入单链表中的节点个数：); scanf(%d,&n); CreateList(L,n); printf(单链表逆置：); ReverseList(L);PrintList(L); break; case 5:printf(要执行本操作请先建立单链表，请输入单链表中的节点个数：); scanf(%d,&n); CreateList(L,n); printf(请输入mink和maxk：); scanf(%d%d,&mink,&maxk); DeleteList(L,mink,maxk);PrintList(L); break;while(number!=0);第二次作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。例如，输入表达式： a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*- 参考答案：#include#include#include#include#define OVER -2#define OK 1#define ERROR 0#define ture 1#define false 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef char 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.stacksize) S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base) exit(OVER);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/插入int GetTop(SqStack&S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/获取栈顶元素int Pop(SqStack&S,SElemType &e)if(S.top=S.base) return ERROR;e=*-S.top;return 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)=0;return 0;/把操作数ch传进数组suffixvoid add(char exp) char *p; p = exp; while (*p != 0) +p; *p = #; *(p + 1) = 0;/在表达式结尾加结束符void del(char suffix) char *p; p = suffix; while (*p != #) p+; *p = 0; /将字符串结尾附成0int Precede(char c)if (c = * | c = /)return 2; if (c = + | c = -)return 1; if (c = ( | c = )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 (ch=a&ch= Precede(ch)Pop(S, c);Pass(suffix, c);GetTop(S, c);Push(S, ch);break;if (ch != #)ch = *+p;/后缀表达式转化int main()char suffix100;suffix0 = 0;char exp100;printf (请输入一个表达式：n);gets(exp);add(exp);transform (suffix, exp);del(suffix);printf (后缀表达式为： %sn, suffix);return 0;第三次作业二叉树采用二叉链表存储，试设计算法实现：1 CreateBT(BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；如输入：AB#D#CE#F# 则建立如下图所示二叉树的二叉链表2 ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子交换；3 CountLeaf(BiTree T, TElemType x, int &count): 统计以值为x的结点为根的子树中叶子结点的数目；4 DispBiTree(BiTree T, int level) : 按树状打印二叉树。BCFAED 打印得到：#C#F#EA#D#B提示：对于根为T，层次为level的子树： 打印其下一层(level+1层)右子树； 打印根结点； 打印其下一层(level+1层)左子树； *结点左边的#个数为其层次数*参考答案：#include#includetypedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/输入先序序列，创建二叉树的二叉链表void CreateBT(BiTree &T)char ch;scanf(%c,&ch);if(ch=#)T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);T-data=ch;CreateBT(T-lchild);CreateBT(T-rchild);/交换二叉树中结点的左右孩子void ExchangeBT(BiTree &T)BiTree temp;if(T)temp=T-lchild;T-lchild=T-rchild;T-lchild=temp;ExchangeBT(T-lchild);ExchangeBT(T-rchild);/查找值为x的结点BiTree SearchTree(BiTree T,char x)BiTree NTree;if(T)if(T-data=x)return T;NTree=SearchTree(T-lchild,x);if(NTree=NULL)NTree=SearchTree(T-rchild,x);return NTree;return NULL;/统计一x为根