数据结构作业C语言版习题

1、数据结构作业（C语言版）习题1.4，试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是 其分子、分母均为自然数且分母不为零的分数）。复数：ADT TripletD=r,i|r,i 为实数R=<r,i>In itComplex(&C,re,im)ADT Complex有理数：ADT TripletD=c1,c2,c3 | c1,c2,c3 Z,c3 丰 0;R=<c1,c2>C3=c1/c2;ADT Triplet1.9假设n为2的乘幕，并且n> 2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。int Time

2、 (int n)coun t=0;x=2;while(x v n/2)x*=2;co un t+;return(co unt)/Time解：o(log 2 n)count= log2 n2X, Y和Z的值。1.16 试写一算法，自大至小依次输出顺序读入的三个整数Void bubble-sort(int aX,Y,Z,int i)for (i=n-1,cha nge=TRUE; i> &&cha nge; -i)chan ge=FALSE;» ajchange=TRUE;for(j=0;j<i;+j) if(aj>aj+1)aj+1</bubbl

3、e-sort解：int max3(i nt x,i nt y,i nt z)if(x>y)if(x>z) retur n x;else return z;elseif(y>z) retur n y; else return z;2.1描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。头结点：在单链表的第一个结点之前附设一个结点，即称之为头结点头指针：链表中第一个结点的存储位置即称之为头指针首元结点：首元结点是指链表中存储线性表中第一个数据元素al的结点2.2填空题(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素

4、在表中的位置有关。(2) 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理 位置不一定相邻。(3) 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的性指示。(40在单链表中设置头结点的作用是插入或删除首元素不必进行特殊处理。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。6-6-4(1)Q=P-> next;(2)L=P->n ext;(3)R->data=P->data;(4)R->data=P->n ext->data;(5)P->n ext->n ext- >n ext-

5、>data=P->data;(6)T=P;While(T!=NULL)T->data=T->data*2;T=t-> next;T=PL(7) LPPPPWhile(T->n ext!=NULL)T->data=T->data*2;T=T->n ext;2.5画出执行下列各行语句后各指针及链表的示意图。L=(L in kList)malloc(sizeof(LNode);P=LFor(i=1;i<=4;i+)p->n ext=(L in kList)malloc(sizeof(LNode); P=P-> next;p-&g

6、t;data=i*2-1;P-> next=NULL;for(i=4;i>=1;i-;)In s-Li nkList(L,i+1,i*2); for(i=1;i<=3;i+)Del-Lin kList(L,i);7AI7 TIPL L2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。A. 在P结点后S结点的语句序列是：(4) (1)B. 在P结点前S结点的语句序列是：(7) (11) (8)(1)C. 在表首S结点的语句序列是：(5) (12)D. 在表尾S结点的语句序列是：(9) (1) (6)(1) P-&g

7、t;next=S;(2) P->n ext=P->n ext- >n ext;(3) P-> next=S-> next;(4) S-> next=P-> next;(5) S-> next=L;(6) S-> next=NULL;Q=P(8) while(P-> next!=Q)P=P-> next;(9) while(P-> next!=NULL)P=P-> next;(10) P=Q(11) P=L;(12) L=S;(13) L=P;2.7a. (11)(3)(14)b. (10)(12)(8)(11)(3)

8、(14)c. (10)(12)(7)(3)(14)d. (12)(11)(3)(14)e(9)(11)(3)(14)2.8a. (7)(12)(6)(3)b. (8)(13)(5)(4)c. (15)(1)(11)(18)d. (16)(2)(10)(18)e. (9)(14)(17)2.10Status DeleteK(SqList &a,int i,int k)int j; if(i<0|i>a.length-1|k<0|k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j+)a.elemj+i=a.elemj

9、+i+k;a.length=a.length-k;return OK;2.13. 解：int LocateElem_L(LinkList &L,ElemType x)int i=0;LinkList p=L;while(p&&p->data!=x)p=p->next;i+;if(!p) return 0;else return i;2.14. 解：int ListLength_L(LinkList &L)int i=0;LinkList p=L;if(p) p=p-next;while(p)p=p->next;i+;return i;3.1. 解： (1)123 231 321 213 132(2) 可以得到 135426 的出站序列，但不能得到 435612 的出站序列。因为 4356 出站说明 12 已经在栈中， 1