数据结构课程课后习题答案.-数据结构第五版课后习题答案 下载本文

typedef struct node {

ElemType data; struct node *next;

//链队结点类型

练习题及参考答案 } QNode;

//-----初始化队列-----

void InitQueue(QNode *&rear) { }

//-----进队算法-----

void EnQueue(QNode *&rear,ElemType x) { }

//-----出队算法-----

int DeQueue(QNode *&rear,ElemType &x) { }

//-----判队空算法-----

QNode *q; if (rear==NULL) { } else { }

return 1;

//原队中有两个或以上的结点

q=rear->next; x=q->data;

rear->next=q->next; free(q); return 0; x=rear->data; free(rear); rear=NULL;

//队空

QNode *s;

s=(QNode *)malloc(sizeof(QNode)); //创建新结点 s->data=x; if (rear==NULL) { } else { }

s->next=rear->next; rear->next=s; rear=s;

//让rear指向这个新插入的结点

//将*s结点插入到*rear结点之后

s->next=s; rear=s;

//原链队为空 //构成循环链表

rear=NULL;

else if (rear->next==rear) //原队中只有一个结点

21

数据结构简明教程

int QueueEmpty(QNode *rear) { }

return(rear==NULL);

上机实验题3

假设以I和O字符分别表示进栈和出栈操作,栈的初态和终栈均为空,进栈和出栈的操作序列可表示为仅由I和O组成的序列。如IOIIOIOO序列是合法的,而IOOIOIIO序列是不合法的。设计一个算法判定所给的操作序列是否合法。若合法返回1;否则返回0。(假设被判定的操作序列已存入一维数组中)。并用相关数据进行测试。

解:采用一个链栈来判断操作序列是否合法,其中str为存放操作序列的字符数组,n为该数组的元素个数(这里的ElemType类型设定为char)。对应的算法如下:

#include #include typedef struct node {

char data;

struct node *next;

//链栈结点类型 //初始化栈运算算法

} LStack; { }

ls=NULL;

void InitStack(LStack *&ls)

void DestroyStack(LStack *&ls) //销毁栈运算算法 { }

void Push(LStack *&ls,char x) //进栈运算算法 { }

int Pop(LStack *&ls,char &x) {

LStack *p;

//出栈运算算法

LStack *p;

p=(LStack *)malloc(sizeof(LStack)); p->data=x; p->next=ls; ls=p;

//创建结点*p用于存放x //插入*p结点作为栈顶结点

LStack *pre=ls,*p; if (pre==NULL) return; p=pre->next; while (p!=NULL) { }

free(pre);

//释放尾结点

free(pre);

//释放*pre结点 //pre、p同步后移

pre=p;p=p->next;

//考虑空栈的情况

}

int StackEmpty(LStack *ls) { }

int judge(char str[],int n) { }

void main() {

char str1[]=\char str2[]=\char str3[]=\char str4[]=\printf(\各序列判断结果如下:\\n\int i,tag; char x; LStack *ls; InitStack(ls); for (i=0;i

tag=StackEmpty(ls); DestroyStack(ls); return tag;

if (str[i]=='I') { } else { }

DestroyStack(ls); return 0;

//其他值无效退出

//为I时进栈

Push(ls,str[i]); if (StackEmpty(ls)) { }

else Pop(ls,x);

DestroyStack(ls); return 0;

//栈空时返回0

//链栈ls初始化

if (ls==NULL) return 1; else return 0; if (ls==NULL) { }

return 0;

else

练习题及参考答案 //栈空,下溢出返回0 //栈不空时出栈元素x并返回1 //p指向栈顶结点 //取栈顶元素x //删除结点*p //释放*p结点

p=ls;

x=p->data; ls=p->next; free(p); return 1;

//判断栈空运算算法

//判断str序列的合法性

else if (str[i]=='O') //为O时出栈

//栈为空时返回1,否则返回0

23

数据结构简明教程

}

printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\

练习题4

1. 单项选择题

(1)串是一种特殊的线性表,其特殊性体现在( )。 A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符 答:B

(2)以下( )是\abcd321ABCD\串的子串。 A. abcd B.321AB 答:D

(3)两个串相等必有串长度相等且( )。 A.串的各位置字符任意 C.两个串含有相同的字符 答:B 2. 填空题

(1)空串是指( ① ),空白串是指( ② )。

答:①不包含任何字符(长度为0)的串 ②由一个或多个空格(仅由空格符)组成的串

(2)对于带头结点的链串s,串为空的条件是( )。 答:s->next==NULL。

(3)对于一个含有n个字符的链串s,查找第i个元素的算法的时间复杂度为( )。 答:O(n) 3. 简答题

(1)设s为一个长度为n的串,其中的字符各不相同,则s中的互异的非平凡子串(非空且不同于s本身)的个数是多少?

答:由串s的特性可知,1个字符的子串有n个,2个字符的子串有n-1个,3个字符的子串有n-2个,…,n-2个字符的子串有3个,n-1个字符的子串有2个。所以,非平凡

n(n?1)子串的个数=n+(n-1)+(n-2)+…+2=?1。

2(2)若s1和s2为串,给出使s1//s2=s2//s1成立的所有可能的条件(其中,“//”表示两个串连接运算符)。

C.\

D.\

B.串中各对应位置字符均相等

D.两个所含字符任意