数据结构 期末考试试卷

{ 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->datanext; q->next=p; } }

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