专升本数据结构试题解析(4)

数据结构上机实验与习题解析 亱店↘打烊oO

该表的有序性。

【算法源代码】

void Insert_SqList(SqList va,int x)/*把x插入递增有序表va中*/

{ int i;

if(va.length> MAXSIZE) return;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

va.length++;

}/*Insert_SqList*/

2．设 A=（a1，a2，…，am） 和 B=（b1，b2，…，bn）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。

【算法分析】比较顺序表A和B，并用返回值表示结果，值为1，表示A>B；值为-1，表示A<B；值为0，表示A=B。

1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1；

2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大

【算法源代码】

int ListComp(SqList A,SqList B)

{

for(i=1;i<=A.length&&i<=B.length;i++)

if(A.elem[i]!=B.elem[i])

return A.elem[i]>B.elem[i]?1:-1;

if(A.length==B.length) return 0;

return A.length>B.length?1:-1;

/*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/

}/*ListComp */

3．已知指针 ha和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。

【算法分析】

1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha；

2）查找单链表ha的最后一个结点，由指针p指向，即p->next==NULL；

3）将单链表hb的首元结点（非头结点）连接在p之后，即p->next=hb->next；

4）回收单链表hb的头结点空间

【算法源代码】

void ListConcat(LinkList ha,LinkList hb,LinkList *hc)

/*把链表hb接在ha后面形成链表hc*/

{

*hc=ha;

p=ha;/*由指针p指向ha的尾元结点*/

p=p->next;

p->next=hb->next;

free(hb);

}/*ListConcat */

4．试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。

【算法分析】

1）生成新结点存放元素b，由指针new指向；

2）将new插入在单链表的第i个元素的位置上：若i==1，new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。

【算法源代码】

void Insert(LinkList *L,int i,int b)

{ LinkList new;