2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表
的有序性。
解：
int InsList(SeqList *L,int X)
{
int i=0,k;
if(L->last>=MAXSIZE-1)
{
printf(" 表已满无法插入！") ；return(ERROR);
} while(i<=L->last&&L->elem[i]<X) i++;
for(k=L->last;k>=I;k--)
L->elem[k+1]=L->elem[k];
L->elem[i]=X;
L->last++;
return(OK);
}
2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。解：
int LDel(Seqlist *L,int i,int k)
{
if(i=1||(i+k>L->last+1))
{
printf(" 输入的i ，k 值不合法") ；return(ERROR);
}
else if(i+k==L->last+2)
{
L->last=i-2;
return OK;
}
else
{
j=i+k-1;
while(j<=L->last)
{
elem[j-k]=elem[j];
j++;
}
L->last=L->last-k+1;
return OK;
2.6 已知线性表中的元素(整数)以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于maxk 的元素(若表中存在这样的元素) ，分析你的算法的时间复杂度(注意：mink 和maxk 是给定的两个变量，他们的值为任意的整数) 。解：
int Delete(Linklist,int mink,int maxk)
{
Node *p,*q; p=L;
while(p->next!=NULL)
p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) {
printf(" 参数不合法！");
return ERROR;
}
else
{
while(p->next->data<=mink)
数据结构与算法第二版课后题答案p=p->next;
q=p->next;
while(q->data<maxk && q!=NULL)
{
p->next=q->next;
free(q); q=p->next;
}
return OK;
}
}
2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的储存空间将线性表(al , al,…，an )逆置为(an, an-1，…，al)。
( 1 )以顺序表作存储结构。
解：
int ReversePosition(SpList L)
{
int k，temp，len;
int j=0;
k=L->last;
len=L->last+1; for(j;j<len/2;j++)
{
temp=L->elem[k-j]; elem[k-j]=elem[j]; elem[j]=temp;
}
return OK;
}
(2)以单链表作存储结构。
解：
int ReversePosition(Linklist L)
{
Node *NL,q,r;
q=L;
r=L;
NL=L->next;
if(NL==NULL)
return ERROR;
while(q->next!=NULL)
{
q=q->next;
r->next=q;
r=q;
}
while(NL->next!=r&&NL->next!=NULL)
{
q=NL;
while(q->next!=r)
q=q->next;
r->next=q;
r=q;
}
r->next=NL;
NL->next=NULL:
return OK;
}
2.8假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算
法，将A表和B表归并成一个按元素值递减的有序排列的线性表C，并要求利用原表(即A
表和B表的)结点空间存放表C
解：
void merge(SepList *LA,SepList *LB,SepList *LC)
{
Node *p1,*p2,*q1,*q2;
LA->next=p1;
LB->next=q1;
while(p1!=NULL&&q1!=NULL)
if(p1->data>q1->data)
{
q2=q1->next;
q1->next=LC->next;
LC->next=q;
q1=q2;
}
else
{
p2=p1->next;
p1->next=LC->next;
LC->next=p1;
p1=p2;
}
}
2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s 为指向链表
某个结点的指针，试编写算法在链表中删除指针s 所指结点的前驱结点。
解：
ElemType DeletePreElem (Node *s)
{
ElemType temp;
Node *p,*pre;
p=s;
while(p->next!=s)
p=p->next;
pre=p;
while(p->next!=pre)
p=p->next;
p->next=s;
temp=pre->data;
free(pre);
return temp;
}
2.10 已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其他字符)，试
编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
解:
LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)
// 把单链表L 的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型.
{
s=L->next;
A=(CiList*)malloc(sizeof(CiLNode));
p=A;
B=(CiList*)malloc(sizeof(CiLNode));
q=B;
C=(CiList*)malloc(sizeof(CiLNode));
r=C; // 建立头结点
while(s!=NULL)
{
if(s->data>='a'&&s->data<='z'||s->data>='A'&&s->data<='Z')
{
p->next=s;
p=s;
}
else if(s->data>='0'&&s->data<='9')
{
q->next=s;
q=s;
}
else
{
r->next=s;
r=s;
}
}
p->next=A;
q->next=B;
r->next=C;
}
2.11设线性表A= (al, a2，…,am), B= ( bl, b2,…，bn)，试写一个按下列规则合并A、
B 为线性表
C 的算法，使得
C= (al, bl,…，an, bn, an +1,…，am)当m>n时
或者
C= (al, bl,…，am bm, bm+1,…，bn)当口<=门时
线性表A、B、C均以单链表作为储存结构，且C表利用A表和B表中的结点空间构成。
解：
Liklist merge(Linklist A Linklist B)
{
Linklist C;
Node *pa,*pb,*r;
C=A;
r=A;
pa=A->next;
pb=B->next;
while(pa!=NULL&&pb!=NULL)
{ r->next=pa; r=pa; pa=pa->next; r->next=pb; r=pb; pb=pb->next; if(pa==NULL) r->next=pb; else r->next=pa; return(C);
}
}
2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。
解：
typedef struct Polynode
{
int coef;
int exp;
struct polynode *next;
}Polynode *PolyList;
void GreateCircle LinklistC(Linklist RL,Node *e)
{
Node *p;
p=RL->next;
RL->next=e;
RL=RL->next;
RL->next=p;
}
void DescouposeList(Linklist RL Descoupose RA Descoupose RB)
{
Node *p;
p=RL->next;
if(p->next=NULL)
return;
p=p->next;
while(p!=RL->next)
{ if(p->exp%2==0)
Greate(RB,p);
else

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。