数据结构练习题 第二章 线性表 习题及答案

{p->next=q->next; /*在表L中删除q 结点*/ q->next= B ->next; B ->next=q; /*将q结点插入B中*/ q=p->next; /*移动q指针*/ }else {p=q;q=p->next;} /*移动q指针*/ } p->next=L;R=L; /*使R为循环表*/ } 13．分析：使用一维数组，数组下标表示元素的序号，数组值为1表示元素存在，数组 值为0表示此元素不存在。若累加数组的下标大于N，再从1开始继续累加数组值，直到 所有元素都输出。 Void JSP( int n, k, a[n]) {for(I=0;Inext =null; t->prior=null; return(t); } (2)定位（设含头结点） int locate_dlklist (dlklist head, datatype x) /*求表head中第一个值等于x 的结点的序号。不存在这种结点时结果为0 */ {p=head->next;j=1; /*置初值*/ while((p!=null)&&(p->data!=x)) {p=p->next;j++;} /*未达尾结点又未找到值等于x的结点时继续扫描*/ if (p->data = = x) return (j); else return (0); } （3） 插入（设含头结点） void insert_dlklist (dlklist head, datatype x, int I) 21

/*在表head的第I 个位置上插入一个以x为值的新结点*/ {p=head->next; j=1; /*先找第I-1个结点*/ while ((p!=null) &&(jdata=x;/*否则生成新结点*/ s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } } （4） 删除（设含头结点） void deldtd_dlklist(dlklist head, int I) /*删除表head的第i个结点*/ {p=head->next;j=1; /*先找第i个结点*/ while((p!=null)&&(jnext;j++;} if(I!=j) error(“不存在第I个位置”)/*若第i个结点不存在，退出*/ if(p!=null) /*若直接前趋存在且待删结点存在*/ {p->prior->next=p->next; p->next->prior=p->prior; free(p);/*释放已摘除结点p*/ } else error(“不在存在第I 结点”) /*否则给出相关信息*/ } 15．分析：首先在链表中查找元素值为X的结点，若找到则让freq域的值增1；然后 依次和它的前趋的freq域值比较，若比前freq域值大，和前趋结点位置交换，直到比 前趋结点的freq域值小为止。 Typedef struct dfnode *dfpointer; Struct dfnode {datatype data; int freq; dfpointer prior,next; } typedef dfpointer dflklist; 设该双链表含头结点。 Int LOCATE_dflklist(dflklist L,datatype X) {/*定位值等于X的结点*/ p=L->next; I=1; while ((p!=null)&&(p->data!=X)) 22

{o=p->next; I++;} if ((p->data!=X||(p= = null)) error(“不存在值为X的结点 ”); else { p->freq++; /*令元素值为X的结点中freq域的值增1*/ q=p->prior; while((q!= L)&&(q->freqfreq)) {I=I-1; p->prior->next=p->next; /*摘除p*/ p->next->prior=p->prior; q->prior-prior=q->prior; p->next=q; q->prior=p; q=p->prior; /*q重新指向p的前趋*/ } return(i); } 23