专升本数据结构试题解析(4)
时间:2025-07-10
时间:2025-07-10
数据结构上机实验与习题解析 亱店↘打烊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;