数据结构作业答案(大连理工大学).doc

精品文档作业1. 线性表l 编程作业：1 将顺序表逆置，要求用最少的附加空间。参考答案#include #include #include #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct ElemType *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;/顺序表在第i个元素之前插入eStatus sxbcr(SqList &L, int i, ElemType e) ElemType *p,*q;if(iL.length+1) return (ERROR); else q=&(L.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return (OK); /顺序表显示void xsList(SqList L)int i=L.length,k;for(k=0;ki;k+)printf(%d ,L.elemk);printf(n);/顺序表逆置void nizhi(SqList &L)int i=0,j=L.length-1; ElemType temp;for(;i10-20-30-40）;（3） InsertList()：在有序单链表中插入元素x；（4） ReverseList()：单链表就地逆置；（5） DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct node ElemType data; struct node *link;Lnode, *LinkList;/头插法建立单链表void Create_L1(LinkList &L, int n) LinkList p; int i; L=(LinkList)malloc(sizeof(Lnode); L-link = NULL; for (i = n; i 0; -i) p=(LinkList)malloc(sizeof(Lnode); scanf(%d,&p-data); p- link = L- link; L- link = p; /尾插法建立单链表void Create_L2(LinkList &L,int n) LinkList s, p; int i; L=(LinkList)malloc(sizeof(Lnode); L-data=0; L-link=NULL; p=L; for(i=1;idata);s-link=NULL;p-link=s;p=s; /查找是否存在结点eLinkList dlbcz(LinkList L, ElemType e) LinkList p=L-link; while(p!=NULL & p-data!=e) p=p-link; return (p);/在第i个元素之前插入结点eStatus ListInsert_L(LinkList L, int i, ElemType e) LinkList p = L,s; int j = 0; while (p & j link;+j; if (!p | j i-1) return ERROR; s = (LinkList) malloc ( sizeof (Lnode); s-data = e; s-link = p-link; p-link = s; return OK;/删除第i个结点Status ListDelete_L(LinkList L, int i, ElemType &e) LinkList p = L,q; int j = 0; while (p-link & j link; +j; if (!(p-link) | j i-1) return ERROR; q=p-link; p-link=q-link; e=q-data; free(q); return OK;/求第i个元素值Status GetElem_L(LinkList L, int i, ElemType &e) int j=1; LinkList p=L-link; while(p&jlink; j+; if(!p|ji) return ERROR; e=p-data; return OK;/显示单链表中元素void xsList(LinkList L)LinkList p=L-link;while(p)printf(%d ,p-data);p=p-link;/删除大于mink且小于maxk的元素void DelList(LinkList &L, ElemType mink, ElemType maxk)LinkList p=L,q;while(p-link&p-link-datalink;q=p;while(q&q-datalink;p-link=q;/就地升序排序void sh_sort(LinkList &L)LinkList p=L-link,pre=L,q=L-link-link,u;p-link=NULL;while(q)p=L-link;pre=L;while(p&p-datadata)pre=p;p=p-link;u=q-link;pre-link=q;q-link=p;q=u;/就地逆置void nizhi(LinkList &L)LinkList p=L-link,q=L-link-link,u;p-link=NULL;while(q)u=q-link;q-link=L-link;L-link=q;q=u;/有序表插入void yxcharu(LinkList &L, ElemType e)LinkList pre,p,s;pre=L;p=L-link;while(p&p-datalink;s=(LinkList)malloc(sizeof(Lnode);s-data=e;s-link=p;pre-link=s;main()LinkList L;int n,i,mink,maxk;ElemType e; char choice=0;while(choice!=q)printf(n*n);printf(1.建立单链表 );printf(2.取元素值 );printf(3.查找 n);printf(4.插入 );printf(5.删除 );printf(6.显示n);printf(7.删除大于mink且小于maxk的元素值 );printf(8.就地升序排序n);printf(9.就地逆置 );printf(a.有序表插入 );printf(q.退出n);printf(n请选择操作：);fflush(stdin);scanf(%c,&choice);switch(choice)case 1: printf(请输入单链表中结点个数：); scanf(%d,&n); Create_L2(L,n); break;case 2: printf(请输入元素位序：); scanf(%d,&i); GetElem_L(L,i,e); printf(元素值为：%dn,e); break;case 3: printf(请输入要查找的元素：); scanf(%d,&e); if(dlbcz(L,e) printf(查找成功！); else printf(查找失败。); break;case 4: printf(请输入插入位置：); scanf(%d,&i); printf(请输入要插入的元素：); scanf(%d,&e); if(ListInsert_L(L,i,e) printf(插入成功！单链表为：); else printf(插入失败。); break;case 5: printf(请输入删除位置：); scanf(%d,&i); if(ListDelete_L(L,i,e) printf(删除成功！); else printf(删除失败。n); break;case 6: printf(n单链表为：); xsList(L); break;case 7: printf(请输入mink和maxk:); scanf(%d,%d,&mink,&maxk); DelList(L,mink,maxk); break;case 8: sh_sort(L); break;case 9: nizhi(L); break;case a: printf(请输入在有序表中插入的元素值:); scanf(%d,&e); yxcharu(L,e); break;作业2. 栈、队列、数组l 非编程作业：1 若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。参考答案：可能的出栈序列：(14种) dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd 不可能的出栈序列：(10种)dbca dbac dabc dacb dcab cabd cdab bdac cadb adbc 2 简要说明循环队列如何判断队满和队空？参考答案：当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环状的下一个位置）上” 作为队列“满”状态的标志时，循环队列判断队满的条件为：(rear+1) % MaxQsize=front；判断队空的条件为：front = rear。3 设A为n阶对称矩阵，采用压缩存储存放于一维数组Fn(n+1)/2中（从F0开始存放），请分别给出存放上三角阵时任一矩阵元素aij（1i,jn）的地址计算公式和存放下三角阵时任一矩阵元素aij（1i,jn）的地址计算公式。参考答案：存放上三角阵时，任一矩阵元素aij（1i,jn）的地址计算公式为：存放下三角阵时，任一矩阵元素aij（1i,jn）的地址计算公式为：4 写出下面稀疏矩阵的三元组顺序表和十字链表表示。参考答案：l 编程作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。例如，输入表达式： a+b/c-(d*e+f)*g 输出其后缀表达式：abc/+de*f+g*- 参考答案：#include #include #include #define OVERFLOW -2#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status;typedef char SElemType; typedef char string80; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if(!S.base) exit(OVERFLOW);S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK);Status ClearStack(SqStack &S)S.base=(SElemType*)realloc(S.base,STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK);void DestroyStack(SqStack &S)S.stacksize=0;if(S.base)free(S.base);S.base=S.top=NULL;Status StackEmpty(SqStack S)if(S.top=S.base)return true;elsereturn false;SElemType GetTop(SqStack S) SElemType e;if(S.topS.base) e=*(S.top-1); return e;Status Push(SqStack &S, SElemType e) if(S.top-S.base=S.stacksize) /栈满 S.base=(SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+ S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S, SElemType &e) if(S.top = S.base) /栈空return ERROR; e =*-S.top; return OK;Status InOP(SElemType c)char Operators=+,-,*,/,(,),#,0;int len=strlen(Operators);for(int i=0;i;break;case (:case #:order=;break;break;case *:case /:switch(curtop)case +:case -:case (:case #:order=;break;break;case (:switch(curtop)case +:order=;break;case -:order=;break;case *:order=;break;case /:order=;break;case (:order=;break;case #:order=;break;case -:order=;break;case *:order=;break;case /:order=;break;case (:order=;break;case ):order=;break;break;case #:switch(curtop)case +:order=;break;case -:order=;break;case *:order=;break;case /:order=;break;case ):order=;break;case #:order=;break;break;return order;void Pass( string Suffix, SElemType ch)*Suffix=ch;void Transform(string Infix, string Suffix ) SqStack S;SElemType ch,e; int flag=0,len;InitStack(S); Push(S, #);len=strlen(Infix);*(Infix+len)=#;ch = *Infix;while (!StackEmpty(S) if (!InOP(ch) Pass( Suffix+, ch);elseswitch(Precede(GetTop(S),ch)case :Pop(S,e);Pass( Suffix+, e);flag=1;break;if(!flag)if (ch!=#) ch = *+Infix; Pass(Suffix, 0);DestroyStack(S); void main()string Infix,Suffix;gets(Infix);Transform(Infix, Suffix) ;puts(Suffix);作业3. 树l 非编程作业：1 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。参考答案：具有3个结点的树： 具有3个结点的二叉树： 2 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。参考答案：EACBDIJHFGK 层次：E A F B H D G I C K J 后序-C D B A G J K I H F E3 将下图所示的森林转换成一棵二叉树。参考答案：BACDFGEHIJKL转换成的二叉树为：4 将下图所示的二叉树还原成树或森林。参考答案：转换为森林：ACHBFDMEGNJIKL5 假设用于通信的电文由7个字母组成A,B,C,D,E,F,G，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL。参考答案： 10.390.610.180.210.090.090.290.320.120.170.030.06AEGBDF哈夫曼树为：WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56A:101 B:001 C:100 D:0001 E:11 F:0000 G:01l 编程作业：二叉树采用二叉链表存储，试设计算法实现：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 #include typedef struct BiTNodechardata;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-rchild=temp; ExchangeBT(T-lchild); ExchangeBT(T-rchild);/先序遍历二叉树void PreOrderTraverse(BiTree T) if(T) printf(%c , T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /查找值为x的结点BiTree SearchTree(BiTree T,char X) BiTree bt;if(T) if(T-data=X)return T; bt=SearchTree(T-lchild,X); if(bt=NULL) bt=SearchTree(T-rchild,X); return bt;return NULL;/统计以T为根的子树中叶子结点数int LeafCount1 (BiTree T) static int count;if ( T ) if (T-lchild=NULL)& (T-rchild=NULL) count+; else count=LeafCount1( T-lchild); count=LeafCount1( T-rchild); return count; void LeafCount2 (BiTree T, int &count) if ( T ) if (T-lchild=NULL)& (T-rchild=NULL) count+; LeafCount2( T-lchild, count); LeafCount2( T-rchild, count); /按树状打印输出二叉树的元素,level表示结点的层次void DispBiTree(BiTree T,int level)int i; if(T) DispBiTree(T-rchild, level + 1); for(i = 0; i data); DispBiTree(T-lchild, level + 1);void main()BiTree T,SubT; char Subch;int countl=0; printf(输入先序序列建立二叉树：n); CreateBT(T);printf(n二叉树的先序序列：); PreOrderTraverse(T);printf(n二叉树为：n); DispBiTree(T,0);printf(交换结点的左右孩子n); ExchangeBT(T);printf(n此时二叉树为：n); DispBiTree(T,0); printf(输入要统计叶子结点个数的子树的根：); fflush(stdin); scanf(%c,