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
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.两个所含字符任意