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

数据结构作业2013
作业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 -2

typedef 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个元素之前插入e
Status sxbcr(SqList &L, int i, ElemType e)
{
ElemType *p,*q;
if((i<1) || (i>L.length+1))
return (ERROR);
else
{ q=&(L.elem[i-1]);
for(p=&(L.elem[L.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 ",L.elem[k]);
printf("\n");
}

//顺序表逆置
void nizhi(SqList &L)
{
int i=0,j=L.length-1;
ElemType temp;
for(;i<j;i++,j--)
{
temp=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=temp;
}
}
main()
{
SqList L;
char flag1='y',flag2='n';
int i;
ElemType k;
if(InitList_Sq(L))
{
printf("建立空顺序表成功！\n");
do{
printf("当前线性表长度为：%d\n",L.length);
printf("请输入要插入元素的位置：");
scanf("%d",&i);
printf("请输入要插入的元素值：");
scanf("%d",&k);
if(sxbcr(L,i,k))
{
printf("插入成功，插入后顺序表长度为：%d\n",L.length);
printf("插入后的顺序表为：");
xsList(L);
}
else
printf("插入失败");
printf("\n继续插入元素？(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()：单链表就地逆置；
（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 -2

typedef 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;i<=n;i++)
{
s=(LinkList)malloc(sizeof(Lnode));
scanf("%d",&s->data);
s->link=NULL;
p->link=s;
p=s; }
}

//查找是否存在结点e
LinkList dlbcz(LinkList L, ElemType e)
{
LinkList p=L->link;
while(p!=NULL && p->data!=e)
p=p->link;
return (p);
}

//在第i个元素之前插入结点e
Status 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 = (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 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&&j<i)
{ p=p->link; j++; }
if(!p||j>i) 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->data<mink)
p=p->link;
q=p;
while(q&&q->data<maxk)
q=q->link;
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->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->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->data<e)
{
pre=p;
p=p->link;
}
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("元素值为：%d\n",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阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式和存放下三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式。
参考答案：
存放上三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：
存放下三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：

4． 写出下面稀疏矩阵的三元组顺序表和十字链表表示。

参考答案：

l 编程作业
栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式： a+b/c-(d*e+f)*g
输出其后缀表达式：abc/+de*f+g*-
参考答案：

#include <stdio.h>
#include <stdlib.h>
#include <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 string[80];

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;
else
return false;
}
SElemType GetTop(SqStack S)
{ SElemType e;
if(S.top>S.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<len;i++)
if(c==Operators[i])
return true;
return false;
}
SElemType Precede(SElemType curtop,SElemType input)
{ SElemType order;
switch(input){
case '+':
case '-':
switch(curtop){
case '+':
case '-':
case '*':
case '/':
case ')': order='>'; break;
case '(':
case '#': order='<'; break;
}
break;
case '*':
case '/':
switch(curtop){
case '+':
case '-':
case '(':
case '#': order='<'; break;
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;
}
break;
case ')':
switch(curtop){
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);
else
{ switch(Precede(GetTop(S),ch))
{ case '<': Push(S,ch);
flag=0;
break;
case '=': Pop(S,e);
flag=0;
break;
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，请构造二叉树，并写出其层次遍历序列和后序遍历序列。
参考答案：
E
A
C
B
D
I
J
H
F
G
K

层次：E A F B H D G I C K J
后序---C D B A G J K I H F E

3． 将下图所示的森林转换成一棵二叉树。

参考答案：
B
A
C
D
F
G
E
H
I
J
K
L
转换成的二叉树为：

4． 将下图所示的二叉树还原成树或森林。

参考答案：
转换为森林：
A
C
H
B
F
D
M
E
G
N
J
I
K
L

5． 假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL。
参考答案：
1
0.39
0.61
0.18
0.21
0.09
0.09
0.29
0.32
0.12
0.17
0.03
0.06
A
E
G
B
D
F
哈夫曼树为：

WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56
A:101 B:001 C:100 D:0001 E:11 F:0000 G:01

l 编程作业：
二叉树采用二叉链表存储，试设计算法实现：
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) : 按树状打印二叉树。
B
C
F
A
E
D

打印得到：#C
###F
##E
A
##D
#B

提示：对于根为T，层次为level的子树：
① 打印其下一层(level+1层)右子树；
② 打印根结点；
③ 打印其下一层(level+1层)左子树；
*结点左边的’#’个数为其层次数*

参考答案：
#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

//输入先序序列，创建二叉树的二叉链表
void CreateBT(BiTree &T)
{ char ch;
scanf("%c",&ch);
if (ch == '#') T = NULL;
else
{ T = (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 < level;i++) printf("#");
printf("%c\n",T->data);
DispBiTree(T->lchild, level + 1);
}