文档介绍：该【数据结构课堂练习题刘楚雄exercise 】是由【胜利的喜悦】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【数据结构课堂练习题刘楚雄exercise 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构课堂练习题--刘楚雄--exercise
2025/4/18
数据结构课堂练习题刘楚雄exercise
类型定义：
顺序表：
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
ElemType *elem;
int length;
int listsize;
}SqList;
数据结构课堂练习题刘楚雄exercise
单链表
typedef struct Lnode {
ElemType data;
Struct Lnode *next;
}Lnode, *LinkList;
4. 设顺序表va中的数据元素递增有序，试写一算法， 将X插入到顺序表的适当位置上，以保持该表的有序性。
数据结构课堂练习题刘楚雄exercise
Status SqInsert(SqList &va, ElemType x)
{//线性表va的元素依次和数据元素x比较，
//找到第一个比它大的元素后，之后所有
//数据后移，X元素放入。
L=va;
if (>= ) {
newbase = (ElemType *)realloc(,
(+LISTINCREMENT)*
sizeof(ElemType);
if (!newbase) exit (OVERFLOW);
= newbase;
= + LISTINCREMENT;}
数据结构课堂练习题刘楚雄exercise
i=0;
while ([i]<x && i<)
i++;
if (i= = )
[i]=x; //插在最后
else { //插在中间
for (j=; j>=i; j--)
[j+1] = [j];
[i]=x; }
++; return OK; }//SqInsert
数据结构课堂练习题刘楚雄exercise
，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
m
n
数据结构课堂练习题刘楚雄exercise
Status LinkListJoin(LinkList ha, LinkLis hb,
LinkList &hc)
{ //将ha, hb链表中长的一条链在短的一条后
//面，并放入hc中
if m > n {hc = hb; p = hb; q = ha->next;}
else {hc = ha; p = ha; q = hb->next;}
while (!p->next) p=p->next;
p->next = q;
return ok; }
算法时间复杂度分析：
时间：min(m,n) , O(n)阶
数据结构课堂练习题刘楚雄exercise
8. 试写一算法，对单链表实现就地逆置
Status LinkConvert(LinkList &h)
{ //假设有头结点，h为指向头结点的指针,
//只需将头结点后结点依次加入新链，
//加入总是放在新链的首元素位置上
p = h->next; q=p->next;
while (p) {p->next = h->next; h->next = p;
p=q; q=q->next; return OK;}
1
2
3
1
2
p
q
数据结构课堂练习题刘楚雄exercise
9. 假设以两个元素递增有序排列的线性表A和B分别表示两个集合（即同一个表中元素各不相同），现要求其并集C，并保持其元素递增有序，要求使用单链表。
1
3
8
2
3
5
q
p
t
s
数据结构课堂练习题刘楚雄exercise
Status assemjoin(LinkList ha, LinkList hb,
LinkList &hc)
{//集合以ha为基础，将hb中不同的元素
//加入，并保持递增有序
hc = ha; p=ha->next; q=hc;
t =hb->next; s=t->next;
while (p&&t) {
switch{
case (t->data = = p-> data)
{free (t) ; t=s; s=s->next;
q=p; p=p->next; break;}
数据结构课堂练习题刘楚雄exercise