数据结构算法设计题及答案.doc

《数据结构算法设计题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构算法设计题及答案1、对带表头结点的有序单链表，编写算法向单链表中插入元素x，使其保持有序。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述voidinsertOrder(node*head,datatypex)//统计{node*s;p=head;while(p->next->datanext;s=(node*)malloc(sizeof(node));s->data=x;s->next=p->next;p->next=s;}2、对带表头结点的单链表，编写算法求

2、单链表的长度。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述intLength(node*head)//求单链表的长度{intnum=0;node*p=head->next;while(p){num++;p=p->next;}returnnum;}3、试写出单链表的插入与删除算法，并用C编写相应的程序。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};单链表的插入参考算法：//在包含元素x的结点前插入新元素

3、bvoidins_linked_LList(node*head,datatypex,datatypeb){node*p,*q;p=newnode;//申请一个新结点p->d=b;//置新结点的数据域if(head==NULL)//原链表为空{head=p;p->next=NULL;return;}if(head->d==x)//在第一个结点前插入{p->next=head;head=p;return;}q=head;while((q->next!=NULL)&&(((q->next)->d)!=x))q=q->next;//寻找包含元素x的前一个结点qp->next=q->next;q->n

4、ext=p;//新结点p插入到结点q之后return;}单链表的删除参考算法：intdel_linked_LList(node*head,Tx)//删除包含元素x的结点元素{node*p,*q;if(head==NULL)return(0);//链表为空，无删除的元素if((head->d)==x)//删除第一个结点{p=head->next;deletehead;head=p;return(1);}q=head;while((q->next!=NULL)&&(((q->next)->d)!=x))q=q->next;//寻找包含元素x的前一个结点qif(q->next==NULL)retu

5、rn(0);//链表中无删除的元素p=q->next;q->next=p->next;//删除q的下一个结点pdeletep;//释放结点p的存储空间return(1);}1、对带表头结点的单链表，编写算法统计单链表中大于x的元素个数。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述intCountX(node*head,datatypex)//统计{intnum=0;p=head->next;while(p){if(p->data>x)num++;p=p->next;}returnn

6、um;}1、对带表头结点的单链表，编写算法将单链表就地逆置。答案：typedefdatatypeint;structnode//结点结构{datatypedata;node*next;};//注：也可以用自然语言描述voidReverseList(node*head)//将单链表就地逆置{node*q,*p=head->next;head->next=NULL；while(p){q=p;p=p->next;q->next=head->next;head->next=q;}}2、写出链队列的入队、出队的算法。答案：typedefdatatypeint;structnode//结点结构{data

7、typedata;node*next;};//注：也可以用自然语言描述structLinkQueue//结点结构{node*front;node*rear;};intEnterQueue(LinkQueue*q,datatypee){//带头结点的链队列入队q->rear->next=(node*)malloc(sizeof(node));q->rear->data=e;q->rear=q->rear->ne