数据结构第2、3章习题讲解

1、Status Insert_Sq( SqList *La, ElemType x ) / 已知顺序表La 中元素依值非递减有序排列，本算法 / 插入新的元素 x 并保持原表的有序性,返回 OK; / 若顺序表空间已满，则不再插入并返回 OVERFLOW if (La-length = La-listsize) return OVERFLOW; i = 0; while (i length for ( j=La-length; ji; j- ) La-elemj = La-elemj-1; / 右移所有值x的元素 La-elemi = x; La-length+; return OK; /Ins

2、ert_Sq 2.2设顺序表设顺序表va中的数据元素递增有序。试写一算法，将中的数据元素递增有序。试写一算法，将x 插入到顺序表的适当位置上，以保持该表的有序性。插入到顺序表的适当位置上，以保持该表的有序性。 2.3试写一算法，在带头结点的单链表结构上实现线性表试写一算法，在带头结点的单链表结构上实现线性表 操作操作LOCATE(L, X)。 int LOCATE(LinkList L , ElemType X , Status(* compare)(ElemType , ElemType) /在带头结点的单链表L中查找第1个值与X满足compare()的元素 的位序,若找到，则返回其在L中的

3、位序，否则返回0 i = 1; p = L-next; while (p i +; if (p) return i; else return 0; 2.4已知指针已知指针ha和和hb分别指向两个单链表的头结点，并且已知分别指向两个单链表的头结点，并且已知 两个链表的长度分别为两个链表的长度分别为m和和n。试写一算法，将这两个链表。试写一算法，将这两个链表 连接在一起（即令其中一个表的首元结点连在另一个表的连接在一起（即令其中一个表的首元结点连在另一个表的 最后一个结点之后），假设指针最后一个结点之后），假设指针hc指向连接后的链表的头指向连接后的链表的头 结点，并要求算法以尽可能短的时间完成连

4、接运算。请分结点，并要求算法以尽可能短的时间完成连接运算。请分 析你的算法的时间复杂度。析你的算法的时间复杂度。 Connect ( LinkList *ha , LinkList *hb , LinkList *hc , int m , int n) /根据给定的两个链表的长度选择较短的链表并找到其尾结点。根据给定的两个链表的长度选择较短的链表并找到其尾结点。 LinkList *p , *q; if (mnext) p=p-next; p-next=q-next; free(q); /释放头结点释放头结点 ha=hb=NULL; 时间复杂度时间复杂度T(n)=O(min(m,n) 题题2.

5、5删除有序表中所有其值大于 mink 且 小于maxk的数据元素。 首先分析需要删除的结点需要删除的结点的特点： mink =maxk preqp 修改指针修改指针: pre-next = p; 释放结点释放结点: while (q!=p) s=q-next; free(q); q=s; void delete(LinkList /查找第一个值mink的结点 if (p) / if q=pre-next; pre-next=p; / 修改指针 while (q!=p) s=q-next; delete q; q=s; / 释放结点空间 p=L-next; while (p / 查找第一个值 m

6、axk 的结点 返回返回 2.6 试写一算法，对单链表实现就地逆置，即利用原表的存储 空间将线性表（a1，a2，an）逆置为 （an，an-1，a1）。 void invert(LinkList *head) LinkList *p,*q,*r; p=head; q=p-next; while(q!=NULL) /当L没用后续节点时终止 r=q-next;q-next=p;p=q;q=r; /实现指针后移 head-next=NULL; head=p;/p指向L的最后一个结点，现改为头结点 2.7 假设某个单向循环链表的长度大于假设某个单向循环链表的长度大于1，且表中既无头结点，且表中既无头结

7、点 也无头指针。已知也无头指针。已知s为指向链表中某个结点的指针，试编写为指向链表中某个结点的指针，试编写 算法在链表中删除指针算法在链表中删除指针s所指结点的前驱结点。所指结点的前驱结点。 LinkList *delnode(LinkList *s) LinkList *q,*r; q=s; while(q-next!=s) q=q-next; r=q; while(r-next!=q) r=r-next; r-next=s; free(q); 2.8 已知有一个单向循环链表，其每个结点中含三个域：已知有一个单向循环链表，其每个结点中含三个域：prior， data和和next，其中，其中d

8、ata为数据域，为数据域，next为指向后继结点的指针为指向后继结点的指针 域，域，prior也为指针域，但它的值为空（也为指针域，但它的值为空（NULL）。试编写算）。试编写算 法将此单向循环链表改为双向循环链表，即使法将此单向循环链表改为双向循环链表，即使prior成为指向成为指向 前驱结点的指针域。前驱结点的指针域。 typedef struct Lnode Elemtype data; struct Lnode *next,*prior; ; struct LinkList *trans(struct LinkList *head) struct LinkList *p,*q; p=h

9、ead-next; q=head; while(p!=head) /依次从左向右通过每个结点，对每个结点置依次从左向右通过每个结点，对每个结点置prior值。值。 p-prior=q; p=p-next; q=q-next) head-prior=q;/此时此时q指向最后一个结点，将第一个结点的指向最后一个结点，将第一个结点的 prior域指向最后一个结点。域指向最后一个结点。 return(head); 3.1 写出下列程序段的输出结果（栈的元素类型写出下列程序段的输出结果（栈的元素类型SElemType 为为char）。）。 void main() Stack S; char x, y;

10、InitStack(S); x = c; y = k; Push(S, x); Push(S, a); Push(S, y); Pop(S, x); Push(S, t); Push(S, x); Pop(S, x); Push(S, s); while(!StackEmpty(S)Pop(S, y); printf(y); printf(x); 按照四则运算加、减、乘、除和幂运算按照四则运算加、减、乘、除和幂运算 （）优先关系的惯例，并仿照教材例）优先关系的惯例，并仿照教材例3- 2的格式，画出对下列算术表达式求值时的格式，画出对下列算术表达式求值时 操作数栈和运算符栈的变化过程：操作数栈和

11、运算符栈的变化过程： ABC/D+EF 写出下列程序段的输出结果（队列中的元素类型写出下列程序段的输出结果（队列中的元素类型QElem Type为为char）。）。 void main( ) Queue Q; Init Queue (Q); Char x=e; y=c; EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q,y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ; Printf(x); 简述以下算法