数据结构练习题解答

第二章线性表1.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La-next;pb=Lb-next;Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb){if(pa-datapb-data){pc-next=pa;pc=pa;pa=pa-next;}elseif(pa-datapb-data){pc-next=pb;pc=pb;pb=pb-next;}else{//相等时取La的元素，删除Lb的元素pc-next=pa;pc=pa;pa=pa-next;q=pb-next;deletepb;pb=q;}}pc-next=pa?pa:pb;//插入剩余段deleteLb;//释放Lb的头结点}2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。voidunion(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=La-next;pb=Lb-next;//初始化Lc=pc=La;//用La的头结点作为Lc的头结点Lc-next=NULL;while(pa||pb){if(!pa){q=pb;pb=pb-next;}elseif(!pb){q=pa;pa=pa-next;}elseif(pa-data=pb-data){q=pa;pa=pa-next;}else{q=pb;pb=pb-next;}q-next=Lc-next;Lc-next=q;//插入}deleteLb;//释放Lb的头结点}3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。voidMix(LinkList&La,LinkList&Lb,LinkList&Lc,){pa=la-next;pb=lb-next;∥设工作指针pa和pb；Lc=pc=La;//用La的头结点作为Lc的头结点while(pa&&pb)if(pa-data==pb-data)∥交集并入结果表中。{pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;deleteu;}elseif(pa-datapb-data){u=pa;pa=pa-next;deleteu;}else{u=pb;pb=pb-next;deleteu;}while(pa){u=pa;pa=pa-next;deleteu;}∥释放结点空间while(pb){u=pb;pb=pb-next;deleteu;}∥释放结点空间pc-next=null;∥置链表尾标记。deleteLb;∥注：本算法中也可对B表不作释放空间的处理3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。voidDifference（LinkedListA，B，*n）∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0{p=A-next；∥p和q分别是链表A和B的工作指针。q=B-next；pre=A；∥pre为A中p所指结点的前驱结点的指针。while（p!=null&&q!=null）if（p-dataq-data）{pre=p；p=p-next；*n++；}∥A链表中当前结点指针后移。elseif（p-dataq-data）q=q-next；∥B链表中当前结点指针后移。else{pre-next=p-next；∥处理A，B中元素值相同的结点，应删除。u=p；p=p-next；deleteu；}∥删除结点4.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。5.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L-next==NULL)returnNULL;pmax=L-next;//假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL){//如果下一个结点存在if(p-datapmax-data)pmax=p;p=p-next;}returnpmax-data;6.设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L-next;L-next=NULL;while(p){q=p-next;//q指向*p的后继p-next=L-next;L-next=p;//*p插入在头结点之后p=q;}}7.设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。voiddelete(LinkList&L,intmink,intmaxk){p=L-next;//首元结点while(p&&p-data=mink){pre=p;p=p-next;}//查找第一个值mink的结点if(p){while(p&&p-datamaxk)p=p-next;//查找第一个值≥maxk的结点q=pre-next;pre-next=p;//修改指针while(q!=p){s=q-next;deleteq;q=s;}//释放结点空间}//if}9.已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。voidExchange（LinkedListp）∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。{q=p-llink；q-llink-rlink=p；∥p的前驱的前驱之后继为pp-llink=q-llink；∥p的前驱指向其前驱的前驱。q-rlink=p-rlink；∥p的前驱的后继为p的后继。q-llink=p；∥p与其前驱交换p-rlink-llink=q；∥p的后继的前驱指向原p的前驱p-rlink=q；∥p的后继指向其原来的前驱}∥算法exchange结束。10.删除线性表a中第i个元素起的k个元素intDeleteK(SqList&a,inti,intk){if(i1||k0||i+k-1a.length)return-1;for(intcount=1;i+count-1=a.length-k;count++)//注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return1}11.把x插入递增有序表va中intInsert_SqList(SqList&va,intx){if(va.length+1va.listsize)return-1;va.length++;for(i=va.length-1;va.elem[i]x&&i=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;return1;}12．在链表上查找元素x,返回指针LNode*Locate(LinkListL,intx){for(p=L-next;p&&p-data!=x;p=p-next);returnp;}13．在无头结点链表L的第i个元素之前插入元素bintInsert(LinkList&L,inti,intb){p=L;q=newLNode;q.data=b;if(i==1){q.next=p;L=q;//插入在链表头部}else{while(--i1)p=p-next;q-next=p-next;p-next=q;//插入在第i个元素的位置}}14．在无头结点链表L中删除第i个元素intDelete(LinkList&L,inti){if(i==1)L=L-next;//删除第一个元素else{p=L;while(--i1)p=p-next;p-next=p-next-next;//删除第i个元素}}第三章栈与队列1.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。算法如下：//先定义链队结构:typedefstructqueuenode{Datatypedata;structqueuenode*next;}QueueNode;//以上是结点类型的定义typedefstruct{queuenode*rear;}LinkQueue;//只设一个指向队尾元素的指针(1)置空队voidInitQueue(LinkQueue*Q){//置空队：就是使头结点成为队尾元素QueueNode*s;Q-rear=Q-rear-next;//将队尾指针指向头结点while(Q-rear!=Q-rear-next)//当队列非空，将队中元素逐个出队{s=Q-rear-next;Q-rear-next=s-next;free(s);}//回收结点空间}(2)判队空intEmptyQueue(LinkQueue*Q){//判队空//当头结点的next指针指向自己时为空队returnQ-rear-next-next==Q-rear-next;}(3)入队voidEnQueue(LinkQueue*Q,Datatypex){//入队//也就是在尾结点处插入元素QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点p-data=x;p-next=Q-rear-next;//初始化新结点并链入Q-rear-next=p;Q-rear=p;//将尾指针移至新结点}(4)出队DatatypeDeQueue(LinkQueue*Q){//出队,把头结点之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q))Error(Queueunderflow);p=Q-rear-next-next;//p指向将要摘下的结点x=p-data;//保存结点中数据if(p==Q-rear){//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点Q-rear=Q-rear-next;Q-rear-next=p-next;}elseQ-rear-next-next=p-next;//摘下结点pfree(p);//释放被删结点returnx;}2.假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。循环队列类定义#includeassert.htemplateclassTypeclassQueue{//循环队列的类定义public:Queue(int=10);