文档介绍：一、填空题
(一)链表类型题目包括:15、42、43、50、56、75、79、85、86、87
技巧解析:
1、首先看清楚题目要求和意思。看清楚链表有没有带头结点,如果带有头结点,指向数据源的指针内容是p=h—>next;如果是不带有头结点,则填写的是p=h;
2、如果所要填写的空在循环语句while的括号中的时候,里面的内容填写的是p或者是q,以最近出现的为主;如果是在循环语句的里面的时候,填写的是q=p—>next;
3、如果是排序的时候,从小到大的时候是大于号,从大到小的时候是小于号。
4、如果链表题目中考到调用函数,一般只需要填入实参head,例如:fun(head);在构造链表的时候都会有头结点,一般用head来表示,head指向了链表中的第一个数据的地址。
细化分类:
1. 将数据域中的数据进行排序,类似题目:15、42
void fun(NODE *h)
{ NODE *p, *q; int t;
/**********found**********/
p = __1__ ;指向数据源,由于h是带头结点的链表,因此需要填入h->next
while (p) {判断链表p是否已经到末尾
/**********found**********/
q = __2__ ; 比较两个数的大小,因此需要q指向p中的下一个数据需要填入p->next,也就是说p指向了第一个数据,q指向了第二个数据。
while (q) {判断q是否指向了末尾
/**********found**********/
if (p->data __3__ q->data)从小到大排序,因此填入大于符号
{ t = p->data; p->data = q->data; q->data = t; }交换数据
q = q->next; q自增,目的是比较出最小的数据
}
p = p->next; p自增
}
}
联想记忆分析1:对一维数组进行从小到大排序
void fun(int b[N])
{ int i, j, a;
for(i=0;i<N-1;i++)
for(j=i;j<N;j++){
if(b[i]>b[j]){a=b[i];b[i]=b[j];b[j]=a;}
}
}
联想记忆分析2:对结构体数组按照姓名进行从小到大排序
for(i=0;i<N-1;i++)
for(j=i;j<N;j++){
if(strcmp(a[i].name,a[j].name)>0){a=b[i];b[i]=b[j];b[j]=a;}
2. 将数据域中的元素逆置,类似的题目:43、50
链表中数据域中的元素逆置,首先将第一个数据取出来放在最后一个位置,也就是将其next置空,表示已经到了末尾。接着将第二个数据放到第一个的前面,依次类推即可将整个数据域逆置。
void fun(NODE *h)
{ NODE *p, *q, *r;
/**********found**********/
p = __1__;指向数据源,由于h是带头结点的链表,因此需要填入h->next
/**********found**********/
if (__2__) return;填入p==NULL,判断第一个数据是否为空,如果为空就无需逆置,执行return语句,结束函数的执行。
q = p->next; q指向了p的下一个数据,确保链表的完整性
p->next = NULL; 将第一个数据取出来放在最后一个位置,也就是将其next置空,表示已经到了末尾。
while (q)
{ r = q->next; 用来跟踪数据,指向了q的下一个数据
q->next = p; 将第二个数据放到第一个的前面,依次类推即可将整个数据域逆置。
/**********found**********/
p = q; q = __3__;这里需要将q指向后面的数据,因此可以填入q->next,或者是r都可以。
}
h->next = p;
}
联想记忆分析1:数组元素的逆置
int a[10]={1,2,3,4,5,6,7,8,9,10};
int i,j=0,b[10];
for(i=9;i>=0;i--){b[j]=a[i],j++;}
数组的逆置只需从数组长度减一开始往后将元素放在另外一个数组中就行。
联想记忆分析2:字符串的逆置
void fun(char *str)
{ char *p;
int len;
len=strlen(str);
while(len)
{ *p=str[len-1];
len--;