数据结构作业(C语言版)习题.doc

数据结构作业（C语言版）习题1.4，试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。复数：ADT TripletD=r,i|r,i为实数R=InitComplex(&C,re,im)ADT Complex有理数：ADT TripletD=c1,c2,c3 | c1,c2,c3Z,c30;R=;C3=c1/c2;ADT Triplet1.9 假设n为2的乘幂，并且n2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。int Time (int n)count=0;x=2;while(xn/2)x*=2;count+;return(count)/Time 解：count=1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。Void bubble-sort(int aX,Y,Z,int i)for (i=n-1,change=TRUE; i&change; -i)change=FALSE;for(j=0;jaj+1)aj+1ajchange=TRUE;/bubble-sort解：int max3(int x,int y,int z)if(xy)if(xz) return x;else return z;elseif(yz) return y;else return z;2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。头结点：在单链表的第一个结点之前附设一个结点，即称之为头结点头指针：链表中第一个结点的存储位置即称之为头指针首元结点：首元结点是指链表中存储线性表中第一个数据元素a1的结点2.2填空题（1） 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。（2） 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。（3） 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的性指示。（40在单链表中设置头结点的作用是插入或删除首元素不必进行特殊处理。2.4对以下单链表分别执行下列各程序段，并画出结果示意图。2573864（1） Q=P-next;（2） L=P-next;（3） R-data=P-data;（4） R-data=P-next-data;（5） P-next-next-next-data=P-data;（6） T=P;While(T!=NULL)T-data=T-data*2;T=t-next;(7)T=PWhile(T-next!=NULL)T-data=T-data*2;T=T-next; 2.5画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode);P=LFor(i=1;inext=(LinkList)malloc(sizeof(LNode);P=P-next;p-data=i*2-1;P-next=NULL;for(i=4;i=1;i-;)Ins-LinkList(L,i+1,i*2);for(i=1;inext=S;(2)P-next=P-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)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)(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(ia.length-1|ka.length-i) return INFEASIBLE;for(j=0;jdata!=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不可能先于2出栈。3.3解：stack3.4.解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e，将其从栈中清除3. 12.解：char3. 13解：队列逆置