2．20 已知线性表中的元素以值递增有序排列，并以单链表（今后若不特别指明，则凡以链表做存储结构时，均带头结点）作存储结构。试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不同），同时释放被删结点空间，并分析你的算法的时间复杂度。2.20 （算法）
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
{
p=L->next;q=p->next; //p,q指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
}
else
{
while(q->data==p->data)
{
free(q);
q=q->next;
}
p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
3．34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入段有n节车厢：硬座、硬卧和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输入段铁道上的排列次序为：硬座在前，软卧在中，硬座在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入列和出列的操作；以字符A表示对双端队列的尾端进行入队列的操作。
3.34 （算法）
void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列
{
r=train;
InitDQueue(Q);
while(*r)
{
if(*r=='P')
{
printf("E");
printf("D"); //实际上等于不入队列,直接输出P车厢
}
else if(*r=='S')
{
printf("E");
EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列
}
else
{
printf("A");
EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列
}
}//while
while(!DQueueEmpty(Q))
{
printf("D");
DeDQueue(Q);
}//while //从头端出队列的车厢必然是先S后H的顺序
}//Train_Rearrange
4．26试写一算法，实现堆存储结构的串的插入操作StrInsert（&S，pos,T）。
4.26 （算法）
Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前
{
if(pos<1) return ERROR;
if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾
S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));
for(i=S.length-1;i>=pos-1;i--)
S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置
for(i=0;i<T.length;i++)
S.ch[pos+i-1]=T.ch[pos]; //插入串T
S.length+=T.length;
return OK;
}//HString_Insert6．54 已知一棵完全二叉树存于顺序表sa中，sa.elem[1..sa.last]含结点值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。
6.54 （算法）
Status CreateBitree_SqList(Bitree &T,SqList sa)//根据顺序存储结构建立二叉链表
{
Bitree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针
if(!sa.last)
{
T=NULL; //空树
return;
}
ptr[1]=(BTNode*)malloc(sizeof(BTNode));
ptr[1]->data=sa.elem[1]; //建立树根
T=ptr[1];
for(i=2;i<=sa.last;i++)
{
if(!sa.elem[i]) return ERROR; //顺序错误
ptr[i]=(BTNode*)malloc(sizeof(BTNode));
ptr[i]->data=sa.elem[i];
j=i/2; //找到结点i的双亲j
if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子
else ptr[j]->lchild=ptr[i]; //i是j的左孩子
}
return OK;
}//CreateBitree_SqList
7．32 试修改普里姆算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子——兄弟链表）。
7.32 （算法）
void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储
{
for(j=0;j<G.vexnum;j++) //以下在Prim算法基础上稍作改动
if(j!=k)
{
closedge[j]={k,Max_int};
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost;
}//if
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k); //把这条边加入生成森林中
closedge[k].lowcost=0;
for(p=G.vertices[k].firstarc;p;p=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost};
}//if
else Forest_Prim(G,k); //对另外一个连通分量执行算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i); //找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p) //起始顶点不属于森林中已有的任何一棵树
{
p=(CSTNode*)malloc(sizeof(CSTNode));
p->data=i;
for(r=T;r->nextsib;r=r->nextsib);
r->nextsib=p;
p->firstchild=q;
} //作为新树插入到最右侧
else if(!p->firstchild) //双亲还没有孩子
p->firstchild=q; //作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作为双亲最后一个孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode)); //建立树根
T->data=1;
Forest_Prim(G,1,T);
...
}//main
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).
9．32 已知一棵二叉排序树上所有关链字中的最小值为-max，最大值为max，又-max<x<max。编写递归算法，求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。
9.32 （算法）
int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
if(last<x&&T->data>=x) //找到了小于x的最大元素
printf("a=%d\n",last);
if(last<=x&&T->data>x) //找到了大于x的最小元素
printf("b=%d\n",T->data);
last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT 10．46 序列b的每个元素是一个记录，每个记录占的存储量比其关键字占的存储量大得多，因而记录的移动操作是极为费时的。试写一算法，将序列b的排列结果放入序列a中，且每个记录只拷贝一次而无其他移动。你的算法可以调用第十章中给出的任何排序算法。思考：当记录存于链表中时，若希望利用快速排序算法对关键字排序，从而最后实现链表的排序，如何模仿上述方法实现？
10.46 （算法）
typedef struct {
int key;
int pos;
} Shadow; //影子序列的记录类型
void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素
{
Shadow d[MAXSIZE];
for(i=0;i<n;i++) //生成影子序列
{
d[i].key=b[i].key;
d[i].pos=i;
}
for(i=n-1,change=1;i>1&&change;i--) //对影子序列执行冒泡排序
{
change=0;
for(j=0;j<i;j++)
if(d[j].key>d[j+1].key)
{
d[j]<->d[j+1];
change=1;
}
}//for
for(i=0;i<n;i++) //按照影子序列里记录的原来位置复制原序列
a[i]=b[d[i].pos];
}//Shadow_Sort
download.kaoyan.com/upload/answerc.zip是这些题的算法的网址，可供参
考。我题前打的题号都跟网上算法的题号一致。每道题既要写算法，也要写程序。
编完程序后，麻烦调试一下，看看能不能运行。（我不会查错）
谢谢啊
我的oicq是31749837
Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
{
p=L->next;q=p->next; //p,q指向相邻两元素
while(p->next)
{
if(p->data!=q->data)
{
p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
}
else
{
while(q->data==p->data)
{
free(q);
q=q->next;
}
p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
}//else
}//while
}//Delete_Equal
3．34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入段有n节车厢：硬座、硬卧和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输入段铁道上的排列次序为：硬座在前，软卧在中，硬座在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入列和出列的操作；以字符A表示对双端队列的尾端进行入队列的操作。
3.34 （算法）
void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列
{
r=train;
InitDQueue(Q);
while(*r)
{
if(*r=='P')
{
printf("E");
printf("D"); //实际上等于不入队列,直接输出P车厢
}
else if(*r=='S')
{
printf("E");
EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列
}
else
{
printf("A");
EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列
}
}//while
while(!DQueueEmpty(Q))
{
printf("D");
DeDQueue(Q);
}//while //从头端出队列的车厢必然是先S后H的顺序
}//Train_Rearrange
4．26试写一算法，实现堆存储结构的串的插入操作StrInsert（&S，pos,T）。
4.26 （算法）
Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前
{
if(pos<1) return ERROR;
if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾
S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));
for(i=S.length-1;i>=pos-1;i--)
S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置
for(i=0;i<T.length;i++)
S.ch[pos+i-1]=T.ch[pos]; //插入串T
S.length+=T.length;
return OK;
}//HString_Insert6．54 已知一棵完全二叉树存于顺序表sa中，sa.elem[1..sa.last]含结点值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。
6.54 （算法）
Status CreateBitree_SqList(Bitree &T,SqList sa)//根据顺序存储结构建立二叉链表
{
Bitree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针
if(!sa.last)
{
T=NULL; //空树
return;
}
ptr[1]=(BTNode*)malloc(sizeof(BTNode));
ptr[1]->data=sa.elem[1]; //建立树根
T=ptr[1];
for(i=2;i<=sa.last;i++)
{
if(!sa.elem[i]) return ERROR; //顺序错误
ptr[i]=(BTNode*)malloc(sizeof(BTNode));
ptr[i]->data=sa.elem[i];
j=i/2; //找到结点i的双亲j
if(i-j*2) ptr[j]->rchild=ptr[i]; //i是j的右孩子
else ptr[j]->lchild=ptr[i]; //i是j的左孩子
}
return OK;
}//CreateBitree_SqList
7．32 试修改普里姆算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子——兄弟链表）。
7.32 （算法）
void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储
{
for(j=0;j<G.vexnum;j++) //以下在Prim算法基础上稍作改动
if(j!=k)
{
closedge[j]={k,Max_int};
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost;
}//if
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k); //把这条边加入生成森林中
closedge[k].lowcost=0;
for(p=G.vertices[k].firstarc;p;p=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost};
}//if
else Forest_Prim(G,k); //对另外一个连通分量执行算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i); //找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p) //起始顶点不属于森林中已有的任何一棵树
{
p=(CSTNode*)malloc(sizeof(CSTNode));
p->data=i;
for(r=T;r->nextsib;r=r->nextsib);
r->nextsib=p;
p->firstchild=q;
} //作为新树插入到最右侧
else if(!p->firstchild) //双亲还没有孩子
p->firstchild=q; //作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作为双亲最后一个孩子的兄弟
}
}//Addto_Forest
main()
{
...
T=(CSTNode*)malloc(sizeof(CSTNode)); //建立树根
T->data=1;
Forest_Prim(G,1,T);
...
}//main
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).
9．32 已知一棵二叉排序树上所有关链字中的最小值为-max，最大值为max，又-max<x<max。编写递归算法，求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。
9.32 （算法）
int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
if(last<x&&T->data>=x) //找到了小于x的最大元素
printf("a=%d\n",last);
if(last<=x&&T->data>x) //找到了大于x的最小元素
printf("b=%d\n",T->data);
last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT 10．46 序列b的每个元素是一个记录，每个记录占的存储量比其关键字占的存储量大得多，因而记录的移动操作是极为费时的。试写一算法，将序列b的排列结果放入序列a中，且每个记录只拷贝一次而无其他移动。你的算法可以调用第十章中给出的任何排序算法。思考：当记录存于链表中时，若希望利用快速排序算法对关键字排序，从而最后实现链表的排序，如何模仿上述方法实现？
10.46 （算法）
typedef struct {
int key;
int pos;
} Shadow; //影子序列的记录类型
void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素
{
Shadow d[MAXSIZE];
for(i=0;i<n;i++) //生成影子序列
{
d[i].key=b[i].key;
d[i].pos=i;
}
for(i=n-1,change=1;i>1&&change;i--) //对影子序列执行冒泡排序
{
change=0;
for(j=0;j<i;j++)
if(d[j].key>d[j+1].key)
{
d[j]<->d[j+1];
change=1;
}
}//for
for(i=0;i<n;i++) //按照影子序列里记录的原来位置复制原序列
a[i]=b[d[i].pos];
}//Shadow_Sort
download.kaoyan.com/upload/answerc.zip是这些题的算法的网址，可供参
考。我题前打的题号都跟网上算法的题号一致。每道题既要写算法，也要写程序。
编完程序后，麻烦调试一下，看看能不能运行。（我不会查错）
谢谢啊
我的oicq是31749837
bool StrInsert(&s,pos,T)
{
int i;
//for example the element is char
char *buffer;
i=s.top-s.base;
if(pos<1||pos>i+1)
{
return false;
}
if(buffer=new char[i+1-pos]==NULL)
exit(OVERFOLLOW);
for(int j=0;j<=i+1-pos;j++)
buffer[j]=s.pop();
for(j=0;j<T.Length()-1;j++)
s.push(T.GetChar(j));
for(j=0;j<=i-pos;j++)
s.push(buffer[j]);
return true;
}