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

1、精选优质文档-倾情为你奉上数据结构作业答案(大连理工大学)专心-专注-专业作业1. 线性表l 编程作业：1 将顺序表逆置，要求用最少的附加空间。参考答案#include <stdio.h>#include <malloc.h>#include <process.h>#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 -2t

2、ypedef 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个元素

3、之前插入eStatus sxbcr(SqList &L, int i, ElemType e) ElemType *p,*q;if(i<1) | (i>L.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;k<i;k+)printf("%d

4、",L.elemk);printf("n");/顺序表逆置void nizhi(SqList &L)int i=0,j=L.length-1; ElemType temp;for(;i<j;i+,j-)temp=L.elemi;L.elemi=L.elemj;L.elemj=temp;main()SqList L;char flag1='y',flag2='n'int i;ElemType k;if(InitList_Sq(L)printf("建立空顺序表成功！n");doprintf("

5、当前线性表长度为：%dn",L.length);printf("请输入要插入元素的位置：");scanf("%d",&i);printf("请输入要插入的元素值：");scanf("%d",&k);if(sxbcr(L,i,k)printf("插入成功，插入后顺序表长度为：%dn",L.length);printf("插入后的顺序表为：");xsList(L);elseprintf("插入失败");printf("n继续

6、插入元素？(y/n) ");fflush(stdin);scanf("%c",&flag1);while(flag1='y'); nizhi(L); printf("顺序表逆置后为：n"); xsList(L);2 从键盘读入n个整数（升序），请编写算法实现：（1） CreateList()：建立带表头结点的单链表；（2） PrintList()：显示单链表，（形如：H->10->20->30->40）;（3） InsertList()：在有序单链表中插入元素x；（4） ReverseList()

7、：单链表就地逆置；（5） DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。参考答案：#include<stdio.h>#include<malloc.h>#include<process.h>#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 n

8、ode 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;

9、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;i<=n;i+) s=(LinkList)malloc(sizeof(Lnode); scanf("%d",&s->data);s->link=NULL;p->link=s;p=s; /查找是否存在结点eLinkList

10、 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 < i-1) p = p->link;+j; if (!p | j > i-1) return ERROR; s

11、 = (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 < i-1) p = p->link; +j; if (!(p->link) | j > i-1) return E

12、RROR; 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&&j<i) p=p->link; j+; if(!p|j>i) return ERROR; e=p->data; return OK;/显示单链表中元素void xsList(LinkList L)Link

13、List 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->data<mink)p=p->link;q=p;while(q&&q->data<maxk)q=q->link;p->link=q;

14、/就地升序排序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->data<q->data)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->l

15、ink->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->data<e)pre=p;p=p->link;s=(LinkList)malloc(sizeof(Lnode);s->data=e;s->link=p;pre->link=s;

16、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.删除大

17、于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"

18、,&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(&

19、quot;查找失败。"); break;case '4': printf("请输入插入位置："); scanf("%d",&i); printf("请输入要插入的元素："); scanf("%d",&e); if(ListInsert_L(L,i,e) printf("插入成功！单链表为："); else printf("插入失败。"); break;case '5': printf("请输入删除位置：&qu

20、ot;); 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,min

21、k,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 a

22、cdb 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开始存放），请分别给出存放上三角阵时任

23、一矩阵元素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 <stdio.h>#include <stdlib.h>#incl

24、ude <string.h>#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=(S

25、ElemType*)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

26、_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.top>S.base) e=*(S.top-1); return e;Status Push(SqStack &S, SElemType

27、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) /栈空r

28、eturn ERROR; e =*-S.top; return OK;Status InOP(SElemType c)char Operators='+','-','*','/','(',')','#','0'int len=strlen(Operators);for(int i=0;i<len;i+)if(c=Operatorsi)return true;return false;SElemType Precede(SElemType curtop,SElem

29、Type input)SElemType order;switch(input)case '+':case '-':switch(curtop)case '+':case '-':case '*':case '/':case ')':order='>'break;case '(':case '#':order='<'break;break;case '*':case '/':s

30、witch(curtop)case '+':case '-':case '(':case '#':order='<'break;case '*':case '/':case ')':order='>'break;break;case '(':switch(curtop)case '+':order='<'break;case '-':order='<'

31、;break;case '*':order='<'break;case '/':order='<'break;case '(':order='<'break;case '#':order='<'break;break;case ')':switch(curtop)case '+':order='>'break;case '-':order='>'brea

32、k;case '*':order='>'break;case '/':order='>'break;case '(':order='='break;case ')':order='>'break;break;case '#':switch(curtop)case '+':order='>'break;case '-':order='>'break;case &

33、#39;*':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,

34、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 '<':Push(S,ch);flag=0;break;case '=':Pop(S,e);flag=0;break;case '>':Pop

35、(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 已知二叉树的先序遍历序列是EABDCF

36、HGIKJ，中序遍历序列是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个字母设计哈夫曼编码

37、，并计算其带权路径长度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# 则建立如下图所示二叉树的二叉链表

38、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 <stdio

39、.h>#include <malloc.h>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-&

40、gt;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); PreOrder

41、Traverse(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

42、( 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 < level;i+) printf("#"); printf("%cn",T->data);