void InitQueue(QNode *&rear) { }
//-----进队算法-----
void EnQueue(QNode *&rear,ElemType x) { }
//-----出队算法-----
int DeQueue(QNode *&rear,ElemType &x) { }
//-----判队空算法----- int QueueEmpty(QNode *rear) { }
return(rear==NULL); QNode *q; if (rear==NULL) { } else { }
return 1;
return 0; x=rear->data; free(rear); rear=NULL;
//队空
QNode *s; rear=NULL;
练习题及参考答案 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;
//原链队为空 //构成循环链表
else if (rear->next==rear) //原队中只有一个结点
//原队中有两个或以上的结点
q=rear->next; x=q->data;
rear->next=q->next; free(q);
21
数据结构简明教程
上机实验题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; if (ls==NULL) {
return 0;
//栈不空时出栈元素x并返回1 //p指向栈顶结点 //取栈顶元素x
p=ls; else
//栈空,下溢出返回0 //出栈运算算法
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;
//考虑空栈的情况
x=p->data;
}
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; } ls=p->next; free(p); return 1; //删除结点*p //释放*p结点 练习题及参考答案 //判断栈空运算算法 //判断str序列的合法性 else if (str[i]=='O') //为O时出栈 //栈为空时返回1,否则返回0 printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\printf(\序列%s合法的\\n\是\不是\ 23 数据结构简明教程 练习题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成立的所有可能的条件（其中，“//”表示两个串连接运算符）。 答：所有可能的条件为： （1）s1和s2为空串 （2）s1或s2其中之一为空串 （3）s1和s2为相同的串 （4）若两串长度不等，则长串由整数个短串组成。 C.\ D.\ B.串中各对应位置字符均相等 D.两个所含字符任意 练习题及参考答案 4. 算法设计题 （1）设计一个算法RepChar(s,x,y)，将顺序串s中所有字符x替换成字符y。要求空间复杂度为O(1)。 解：因要求算法空间复杂度为O(1)，所以只能对串s直接替换。从头开始遍历串s，一旦找到字符x便将其替换成y。对应算法如下： void RepStr(SqString &s,char x,char y) { } int i; for (i=0;i if (s.data[i]==x) s.data[i]=y; （2）设计一个算法，判断链串s中所有元素是否为递增排列的。 解：用p和q指向链串s的两个连续结点，p先指向开始结点，当q->data≥p->data时，p和q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下： int increase(LinkString *s) { } LinkString *p=s->next,*q; if (p!=NULL) { } return 1; while (p->next!=NULL) { } q=p->next; p=q; //逆序时返回0 return 0; //q指向*p的后续结点 if (q->data>=p->data) else （3）假设以链式结构存储一个串s，设计一个算法求串s中最长等值子串。 解：假设串用带头结点的单链表存储串s。用max存放最大平台长度，扫描串s，计算一个平台的长度n，若n大于max，则置max为n。对应的算法如下： int maxlength(LinkString *s) { int n,max=0; LinkString *p=s->next,*q; while (p!=NULL) { n=1; q=p;p=p->next; while (p!=NULL && p->data==q->data) { } n++; p=p->next; 25