数据结构习题

数据结构习题第二章、第三章1、设顺序表L是一个递增（允许有相同值）有序表，试写一个算法将x插入L中，并使L仍为一个有序表。VoidseqListInsert(SeqListL,intx){i=0;while((i<=L.length-1)&&(x>=L.elem[i]))i++;for(k=L.length-1;k>=i;k--)L.elem[k+1]=L.elem[k];L.elem[i]=x;L.length++;}删除？1、顺序表递增，写出删除值为x的元素。IntSeqListdelete(SeqListL,intx){inti;i=0;while((i<=L.length-1)&&L.elem[i]!=x))i++;if(i<=L.length-1)for(k=i+1;k<=L.length-1;k++) {L.elem[k-1]=L.elem[k];L.lengh--;Return(1);}Elsereturn(0);}2、给定一个链表，在p点之前插入一个值为x的结点

IntLinkListInsert(LinkListL,intx){q=L;While(q->next!=p)q=q->next;s=(LinkList)malloc(sizeof(Lnode));s->data=x;s->next=p;q->next=s;returnOK;}3、计算带头结点的循环链表的结点个数intnumber(LinkedNodehead){p=head->next;i=0;while(p!=head){i++;p=p->next;}returni;}4、分别用顺序表和单链表作为存储结构，实现线性表（a0,a1,a2,……，an-1）就地逆置的操作，“就地”辅助空间O(1)Voidlinkedreverse(linkedlistL){p=L->next;L->next=Null;while(p!=Null)r=p;p=p->next;r->next=L->next;L->next=r;}}5、设单链表L是一个非递减有序表，试写一个算法将x插入其中后，仍保持L的有序性。VoidLinkListInsert(LinkedListL,intx){q=L;p=q->next;while(p!=Null)&&p->data<x){q=p;p=p->next;}s=(LinkedList)malloc(sizeof(Lnode))s->data=x;s->next=p;q->next=s;}1、设计两个栈共享空间，并使用顺序存储结构时的公共操作pushi(i,x)和popi(i,x),其中i=1,2Voidpushi(Sqstackst,inti,inte){if(st.top1==st.top2-1)printf(“栈满”)；elseif(i==1){st.data[st.top1]=e;st.top1++;}elseif(i==2){st.data[st.top2]=e;st.top2--;}}Typedefstruct{inttop1,top2;dataTypedata[M];}Sqstack;Voidpopi(Sqstackst,inti){if(i==1)if(st.top1==-1)printf(“栈1空”)；else{st.top1--;x=st.data[st.top1];returnx;}elseif(i==2)if(st.top2==M)printf(“栈2空”)；else{st.top2++;x=st.data[st.top2];returnx;}}2、假设以带头结点的循环链表表是队列，并且只设一个指针指向队尾结点，但不设头指针，设计相应的入队和出队算法。typedefstructQNode{datatypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrrear;}LinkQueue;voidQueueIN(LinkQueue&Q,datatypex){s=(Queueptr)malloc(sizeof(QNode));s->data=x;s->next=Q->rear->next;Q->rear->next=s;Q->rear=s;}voidQueueOut(LinkQueue&Q){if(Q->rear->next==Q->rear)print