第二章 线性表
Status DeleteK(SqList &aint iint k)//删除线性表a中第i个元素起的k个元素
{
if(i<||k<||i+k>alength) return INFEASIBLE;
for(count=;i+count<=alengthk;count++) //注意循环结束的条件
aelem[i+count]=aelem[i+count+k];
alength=k;
return OK;
}//DeleteK
Status Insert_SqList(SqList &vaint x)//把x插入递增有序表va中
{
if(valength+>valistsize) return ERROR;
valength++;
for(i=valength;vaelem[i]>x&&i>=;i)
vaelem[i+]=vaelem[i];
vaelem[i+]=x;
return OK;
}//Insert_SqList
int ListComp(SqList ASqList B)//比较字符表A和B并用返回值表示结果值为正表示A>B;值为负表示A
{
for(i=;Aelem[i]||Belem[i];i++)
if(Aelem[i]!=Belem[i]) return Aelem[i]Belem[i];
return ;
}//ListComp
LNode* Locate(LinkList Lint x)//链表上的元素查找返回指针
{
for(p=l>next;p&&p>data!=x;p=p>next);
return p;
}//Locate
int Length(LinkList L)//求链表的长度
{
for(k=p=L;p>next;p=p>nextk++);
return k;
}//Length
void ListConcat(LinkList haLinkList hbLinkList &hc)//把链表hb接在ha后面形成链表hc
{
hc=ha;p=ha;
while(p>next) p=p>next;
p>next=hb;
}//ListConcat
见书后答案
Status Insert(LinkList &Lint iint b)//在无头结点链表L的第i个元素之前插入元素b
{
p=L;q=(LinkList*)malloc(sizeof(LNode));
qdata=b;
if(i==)
{
qnext=p;L=q; //插入在链表头部
}
else
{
while(i>) p=p>next;
q>next=p>next;p>next=q; //插入在第i个元素的位置
}
}//Insert
Status Delete(LinkList &Lint i)//在无头结点链表L中删除第i个元素
{
if(i==) L=L>next; //删除第一个元素
else
{
p=L;
while(i>) p=p>next;
p>next=p>next>next; //删除第i个元素
}
}//Delete
Status Delete_Between(Linklist &Lint minkint maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
{
p=L;
while(p>next>data<=mink) p=p>next; //p是最后一个不大于mink的元素
if(p>next) //如果还有比mink更大的元素
{
q=p>next;
while(q>datanext; //q是第一个不小于maxk的元素
p>next=q;
}
}//Delete_Between
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
{
p=L>next;q=p>next; //pq指向相邻两元素
while(p>next)
{
if(p>data!=q>data)
{
p=p>next;q=p>next; //当相邻两元素不相等时pq都向后推一步
}
else
{
while(q>data==p>data)
{
free(q);
q=q>next;
}
p>next=q;p=q;q=p>next; //当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
void reverse(SqList &A)//顺序表的就地逆置
{
for(i=j=Alength;i
Aelem[i]<>Aelem[j];
}//reverse
void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法假设表长大于
{
p=L>next;q=p>next;s=q>next;p>next=NULL;
while(s>next)
{
q>next=p;p=q;
q=s;s=s>next; //把L的元素逐个插入新表表头
}
q>next=p;s>next=q;L>next=s;
}//LinkList_reverse
分析:本算法的思想是逐个地把L的当前元素q插入新的链表头部p为新表表头
void merge(LinkList &ALinkList &BLinkList &C)//把链表A和B合并为CA和B的元素间隔排列且使用原存储空间
{
p=A>next;q=B>next;C=A;
while(p&&q)
{
s=p>next;p>next=q; //将B的元素插入
if(s)
{
t=q>next;q>next=s; //如A非空将A的元素插入
}
p=s;q=t;
}//while
}//merge
void reverse_merge(LinkList &ALinkList &BLinkList &C)//把元素递增排列的链表A和B合并为C且C中元素递减排列使用原空间
{
pa=A>next;pb=B>next;pre=NULL; //pa和pb分别指向AB的当前元素
while(pa||pb)
{
if(pa>datadata||!pb)
{
pc=pa;q=pa>next;pa>next=pre;pa=q; //将A的元素插入新表
}
else
{
pc=pb;q=pb>next;pb>next=pre;pb=q; //将B的元素插入新表
}
pre=pc;
}
C=A;A>next=pc; //构造新表头
}//reverse_merge
分析:本算法的思想是按从小到大的顺序依次把A和B的元素插入新表的头部pc处最后处理A或B的剩余元素
void SqList_Intersect(SqList ASqList BSqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
{
i=;j=;k=;
while(Aelem[i]&&Belem[j])
{
if(Aelem[i]
if(Aelem[i]>Belem[j]) j++;
if(Aelem[i]==Belem[j])
{
Celem[++k]=Aelem[i]; //当发现了一个在AB中都存在的元素
i++;j++; //就添加到C中
}
}//while
}//SqList_Intersect
void LinkList_Intersect(LinkList ALinkList BLinkList &C)//在链表结构上重做上题
{
p=A>next;q=B>next;
pc=(LNode*)malloc(sizeof(LNode));
while(p&&q)
{
if(p>datadata) p=p>next;
else if(p>data>q>data) q=q>next;
else
{
s=(LNode*)malloc(sizeof(LNode));
s>data=p>data;
pc>next=s;pc=s;
p=p>next;q=q>next;
}
}//while
C=pc;
}//LinkList_Intersect
void SqList_Intersect_True(SqList &ASqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中
{
i=;j=;k=;
while(Aelem[i]&&Belem[j])
{
if(Aelem[i]
else if(Aelem[i]>Belem[j]) j++;
else if(Aelem[i]!=Aelem[k])
{
Aelem[++k]=Aelem[i]; //当发现了一个在AB中都存在的元素
i++;j++; //且C中没有就添加到C中
}
}//while
while(Aelem[k]) Aelem[k++]=;
}//SqList_Intersect_True
void LinkList_Intersect_True(LinkList &ALinkList B)//在链表结构上重做上题
{
p=A>next;q=B>next;pc=A;
while(p&&q)
{
if(p>datadata) p=p>next;
else if(p>data>q>data) q=q>next;
else if(p>data!=pc>data)
{
pc=pc>next;
pc>data=p>data;
p=p>next;q=q>next;
}
}//while
}//LinkList_Intersect_True
