}
3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：
void invert(LinkList *head)
{ //逆置head指针所指向的单循环链表 linklist *p, *q, *s; q=head; p=head->next;
while (p!=head) //当表不为空时，逐个结点逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; }
4．定义类型LinkList如下：
typedef struct node { int data;
struct node *next,*prior; }LinkList;
此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：
insert (LinkList *head) { LinkList *p,*s,*q;
p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)
{ s=head; // s指向q结点的前趋结点
q=head->prior; //q指向由prior域构成的链表中待比较的结点
while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置
{ s=q;
q=q->prior; } s->prior=p;
p->prior=q; //结点p插入到结点s和结点q之间 p=p->next;
} }
5．算法描述如下：
delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head;
p=head->next;
while((p!=NULL) && (p->data<=min)) { q=p;
p=p->next; }
while((p!=NULL) && (p->data
} }
6．算法描述如下：
delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next; while (p!=NULL)
if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; }
else
{ q->next=p->next;
free(p); p=q->next; } }
7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：
（1）插入（即入队）算法：
insert(LinkList *rear, elemtype x)
{ //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p;
rear->next=p; //链接成循环链表 }
else //否则在队尾插入p结点 { p->next=rear->next;
rear->next=p; rear=p; } }
（2）删除（即出队）算法：
delete(LinkList *rear)
{ //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf(\
if(rear->next= =rear) //队中只有一个结点 rear=NULL; else
rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点 }
8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：
int InsertDecreaseList( SqList *L, elemtype x ) { int i;
if ( (*L).len>= maxlen) { printf(“overflow\ return(0); }
for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); }
习题3
一、单项选择题
1. 空串与空格字符组成的串的区别在于（ ）。
A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ ）是正确的。
A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ ）。
A.两串的长度相等 B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同
5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。
A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N”
6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。
A.2 B.3 C.4 D.5
7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。
A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”
8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ ）。
A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（ ）。
A.链表的长度为1
B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符
二、填空题
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。 3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。 三、算法设计题
1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m 习题3参考答案 一、单项选择题 1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D 二、填空题 1. 固定长度，设置长度指针 2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE” 4. 含n个字符的有限序列 （n≥0） 5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为： int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j; for(i=1;i<=m;i++) r[s+i]=r[i]; for(j=m+t-i;j<=s;j++) r[s-t+j]=r[j]; return (1); } //delete 2．算法思想为： （1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较； （2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。