数据结构导论作业一.doc

《数据结构导论作业一.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、章节作业第一章概论1．设计算法在整型数组A[n]中查找值为K的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。intsearch(intA[],intn,intk){inti;i=0;while(i<=n-1)if(A[i]!=k)i++;elsebreak;if(i<=n-1)returnI;elsereturn-1；}当查找成功时，A[i]与k比较次数≤n；当查找不成功时，A[i]与k比较n次，所以，算法时间复杂度T(n)=O(n)。2．写出计算方

2、阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。voidmatrixmultiply(intA[][n],intB[][n],intC[][n],intn){intI,j;for(i=0;i

3、算量为n3+n2，算法时间复杂T(n)=O(n3)第二章线性表1．设带头结点的单链表的结点结构如下：structnode{DataTypedata；structnode*next；}Node，*LinkList；试编写一个函数intcount(LinkListhead，DataTypex)统计单链表中数据域为x的结点个数。intcount(LinkListhead,DataTypex){LinkListp=head->next;Intm=0;while(p!=NULL){if(p->data==x)m

4、++;p=p->next;}returnm;}2．试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2，…，an)逆置为(an，an-1，…，a1)。顺序表逆置算法voidinverse_sqlist(SeqlistL){intm,n,k;DataTypetemp;m=0;n=L.length-1;while(m

5、temp;m++;n--;}}带头结点的单链表的逆置算法reverse_2(LinkListhead){LinkListp,q;p=head->next;head->next=NULL;while(p!=NULL){q=p->next;p->next=head->next;head->next=p;p=q;}}第三章栈、队列和数组1．有一个整数序列，其输入顺序为20，30，90，-10，45，78，试利用栈将其输出序列改变为30，-10，45，90，78，20，试给出该整数序列进栈和出栈的操作步骤。(

6、用push(x)表示x进栈，pop(x)表示x出栈)push(20),push(30),pop(30),push(90),push(-10),pop(-10),push(45),pop(45),pop(90),push(78),pop(78),pop(20)2．设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。一号列车先出站：1234,1243,1324,1342,1432;二号列车先出站：2134,2143,2314,2341,2431；三好列

7、车先出站：3214,3241,3421；四号列车先出站：4321；但是这里的4123、4132、4213、4231都不是正解,所以共有14种可能3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队列尾结点(注意不设头指针)，试编写相应的初始化队列、入队列和出队列算法。类型定义：typedefstructlinksd_queue{DataTypedata;structlinked_queue*next;}LqueueTp;队列的初始化voidInitQueue(LqueueTp*rear){Lq

8、ueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));rear=p;rear->next=rear;}入队列voidEnQueue(LqueueTp*rear;DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));p->data=x;p->next=rear->next;rear->next=p;rear=p}出队列OutQueue(LqueueTp