数据结构习题解答1-3

《数据结构习题解答1-3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章绪论1.5i=0；i++；i!=n&&a[i]!=xFalseTrueProduct=1；i=1；i<=nProduct*=i；i++FalseTruex

2、）第一章线性表2.1头指针是指向链表中最前面的节点的指针。若链表带头节点，则头指针恒指向头节点。若链表不带头节点，则当链表非空时，头指针指向首元节点；链表为空时，头指针也为空。头节点是为了方便链表的操作而在链表头部附设的一个节点，其数据域可以不存任何信息，也可以存储表长等信息。首元节点为链表中存储线性表第一个数据元素的节点，即线性表中第一个数据元素的存储映像。2.3需要经常根据位序对元素进行随机存取。2.9（1）若无头节点的单链表中至少有两个节点，则将首节点删去并将其插入到表尾。（题集P182）（2）已知和分别指向单循环链表中

3、的两个节点，算法将其拆成分别包含节点和节点的两个单循环链表。例pbpapapb如：2.11StatusInsertOrderList(SqList&va,ElemTypex){if(va.length>=va.listsize)//空间已满，增加分配{newbase=(ElemType*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(Elemtype));if(!newbase)exit(OVERFLOW);va.elem=newbase;va.listsize+=LIS

4、TINCREMENT;}p=va.elem+va.length-1;while(p>=va.elem&&*p>x){*(p+1)=*p;p--;}++p=x;va.length++;returnOK;}//InsertOrderList2.13positionLocatePos(LinkListL,ElemTypex){//L为带头节点的单链表的头指针，本算法在表中查找第一个值//和x相同的元素，若存在，则返回基地址，否则返回NULLp=L->next;while(p&&p->data!=x)p=p->next;returnp

5、;}typedefstructLNode{ElemTypedata;StructLNode*next;}*LinkList,*position;说明：position定义见教材P87，也可以根据《题集》P16写成Linklist2.14intListLength(LinkListL){//L为带头节点的单链表的头指针，本算法返回链表中元素的个数p=L;n=0;while(p->next){p=p->next;n++;}returnn;}2.21voidInvertSqList(SqLista){for(i=0;i<=a.len

6、gth/2-1;i++)a.elem[i]<->a.elem[a.length-1-i];}//a.length/2为顺序表前一半的元素个数，再减1为前一半的最后下标2.31voidDeletepre(LinkLists){po=s;p=s->next;while(p->next!=s){po=p;p=p->next;}po->next=s;free(p);}栈和队列3.1（1）123，132，213，231，321（2）435612不可能得到，由于4第一个出栈，所以必须先将1，2，3依次连续进栈；1在栈底，不可能先于2出栈，

7、故不能得到出栈序列435612。135426可以得到，操作序列为SXSSXSSXXXSX3.2栈和线性表的差别是操作定义不同。栈是限定仅在表尾进行插入或删除操作的线性表。3.9《题集》p1873.10《题集》p187-1883.15//双向栈顺序存储结构#defineSTACKSIZE100//双向栈容量typedefstruct{SElemTypebase[STACKSIZE];//双向栈数组SElemType*top0,*top1;}DuStack;voidinistack(DuStack&tws){tws.top0=tw

8、s.base;tws.top1=tws.base+STACKSIZE-1;}Statuspush(DuStack&tws,inti,SElemTypex){if(tws.top0==tws.top1+1)returnERROR//双向栈满(或tws.top0>tws.top1