计算机软件基础(二)程序题.doc

《计算机软件基础(二)程序题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.对一个已建立好的单链表(表头指针为head),编写一算法计算该链表中的结点个数。(要求给出结点的结构描述)统计结点个数Typedefstructsnode{intdata;structsnode*next;}LinkList*;intListLength(LinkListhead){inti=0;LinkListp=head->next;While(p){i++;p=p->next;}returni;}2.给定一个n项元素的线性表V,写一个过程将元素排列的次序颠倒过来，#definen100v

2、oidniain(){intV[n];inti=0J,front=0,rear=n-l;for(i=0;inext;while(p!=NU

3、LL&&p->next!=NULL){s=p;//s指向要删除结点的前趋q=p->next;while(q!=NULL){if(q->data==p->data)}〃査找值相同的结点并删除{s->next=q->next;free(q);q=s->next;else{s=q;q=q->next;}}p=p->next;}}〃求链表长度4.设计计算线性链表长度的算法intListlength(LinklistL){Linklistp;intj=0;P=L；while(p->next!=NULL){+

4、+j；p=p->next;}returnj;}5・设一线性链表，其结点值为正整数序列，且按值从小到大链接，设计算法，将此线性链表分成两个纯属链表，其中一个结点值均为奇数，而另一个均为偶数，且也是从小到大链接。把原链表中头节点和第二个节点地址传入函数void*f(structstu*head5structstu*head1){structstu*p1,*p2;p1=head;p2=head1;for(inti=1;p1->next!=NULL&&p2->next!=NULL;i++)if(i%2!=

5、0)//是奇数节点p1=p2->next;//指向下个奇数节点else//是偶数节点p2=p1->next;//指向下个偶数节点p1->next=NULL;p2->next=NULL;}6.设有一个循环单链表长度大于1,且表中既无头结点也无头指针。已知S为指向链表中某一结点的指针，写出在链表中删除S指针所指结点的前趋结点的算法link*p,*q;P=s；while(p->next->next!=s){p=p->next;}q=p->next;p->next=s;deleteq;7.已知指针ha和h

6、b分别指两个单链表的头结点，且头结点的数据域中存放链表的长度，试写一算法将两个链表连拉在一起，即令其中一个表的首元结点连在另一表最后一个结点之后，he指向连接后的链表的头结点，并要求算法以尽可能短的时间内完成运算。LinkListLink(LinkListLI,LinkListL2)〃将两个单链表连接在一起ListNode*p,*q;P=L1；q=L2;while(p->next)p=p->next;//査找终端结点p->next=q->next;〃将L2的开始结点链接在LI之后returnLI;

7、本算法的主要操作时间花费在査找L1的终端结点上，与L2的长度无关。8・假设一数组squ[m]存放循环队列的元素。若要使这个m分量都得到利用，则需另一个tag,以t幌为0或1来区分尾指针和头指针值同时队列的状态是“空”还是“满”。试编写与此结构相应的入队和出队的算法。StatusEnCyQueue(CyQueue&Q,intx)〃带tag域的循环队列入队算法{if(Q.front==Q.rear&&Q・tag==1)//tag域的值为0表示”空”,1表示”满”returnOVERFLOW;Q.bas

8、e[Q.rear]=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front==Q.rear)Q.tag=1;〃队列满}//EnCyQueue9.假设以带头结点的循环单链表表示陈列并且只设一个指针指向队尾元素结点，不设头指针，试编写相应的入队和出队算法typedefintDatatype;typedefstructqueuenode{Datatypedata;structqueuenode*next;JQueueNode;〃以上是结点类型的定义typedefst