{ //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0)
printf(\ else if(i= =0) { s=q; q=q->next; free(s); }
else
{ j=0; s=q;
while((j
j++; }
if (s= =NULL)
printf(\ delete\
else
{ p->next=s->next; free(s); } } }
2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：
int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;
while ( p->next!=NULL ) { p=p->next; len++; }
return (len); }
-11-
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;
} }
-12-
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));
-13-
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); }
-14-
习题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
-15-
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构习题及参考答案(3)在线全文阅读。
相关推荐：
