1.
⑴解：(79,62,34,57,26,48)
⑵解：(26,34,48,57,62,79)
⑶解：(48,56,57,62,79,34)
⑷解：(56,57,79,34)
⑸解：(26,34,39,48,57,62)
2.
解：
为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元
素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为
表头指针。
⒈(7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0))
⒉(3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0))
⒊(2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0))
⒋(8(56,4),(57,7),(79,5),(34,0))
3.对于List类型的线性表,编写出下列每个算法。
⑴ 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若
线性表为空则显示出错信息并退出运行。
解： ElemType DMValue(List&L)
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行
{
if(ListEmpty(L)){
cerr<<"List is Empty!"<<end1;
exit(1);
}
ElemType x;
x=L.list[0];
int k=0;
for(int i=1;i<L.size;i++){
ElemType y=L.list[i];
if(y<x){x=y;k=i;}
}
L.list[k]=L.list[L.size-1];
L.size--;
return x;
}
⑵ 从线性表中删除第i个元素并由函数返回。
解：int Deletel(List& L,int i)
//从线性表中删除第i个元素并由函数返回
{
if(i<1||i>L.size){
cerr<<"Index is out range!"<<end1;
exit(1);
}
ElemType x;
x=L.list[i-1];
for(int j=i-1;j<L.size-1;j++)
L.list[j]=L.list[j+1];
L.size--;
return x;
}
⑶ 向线性表中第i个元素位置插入一个元素。
解：void Inser1(List& L,int i,ElemType x)
//向线性表中第i个元素位置插入一个元素
{
if(i<1||i>L.size+1){
cerr<<"Index is out range!"<<end1;
exit(1);
}
if(L.size==MaxSize)
{
cerr<<"List overflow!"<<end1;
exit(1);
}
for(int j=L.size-1;j>i-1;j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
⑷ 从线性表中删除具有给定值x的所有元素。
解：void Delete2(List& L,ElemType x)
//从线性表中删除具有给定值x的所有元素
{
int i=0;
while(i<L.size)
if(L.list[i]==x){
for(int j=i+1;j<L.sizr;j++)
L.list[j-1]=L.list[j];
L.size--;
}
else
i++;
}
⑸ 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
解：void Delete3(List& L,ElemType s,ElemType t)
//从线性表中删除其值在给定值s和t之间的所有元素
{
int i=0;
while(i<L.size)
if((L.list[i]>=s)&&(L.list[i]<=t)){
for(int j=i+1;j<L.size;j++)
L.list[j-i]=L.list[j];
L.size--;
}
else
i++;
}
⑹ 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。
解：void Delete4(List& L,ElemType s,ElemType t)
//从有序表中删除其值在给定值s和t之间的所有元素
{
int i=0;
while(i<L.size)//从有序表L中查找出大于等于s的第一个元素
if(L.list[i]<s)i++;
else break;
if(i<L.size){
While((i+j<L.size)&&(L.list[i+j]<=t))
j++;//求出s和t之间元素的个数
for(int k=i+j;k<L.size;k++)
L.list[k-j]=L.list[k];
L.size-=j;
}
}
⑺ 将两个有序表合并成一个新的有序表并由变量返回。
解：void Merge(List& L1,List& L2,List& L3)
//将两个有序表合并成一个新的有序表并由变量返回
{
if(L1.size+L2.size>MaxSize){
cerr<<"List overflow!"<<end1;
exit(1);
}
int i=0,j=0,k=0;
while((i<L1.size)&&(j<L2.size)){
if(L1.list[i]<=L2.list[j])
{ //将L1中的元素赋给L
L.list[k]=L1.list[i];
i++;
}
else{ //将L2中的元素赋给L
L.list[k]=L2.list[j];
j++;
}
k++;
}
while(i<L1.size){ //将L1中剩余的元素赋给L
L.list[k]=L1.list[i];
i++;k++;
}
while(j<L2.size){ //将L2中剩余的元素赋给L
L.list[k]=L2.list[j];
j++;k++;
}
L.size=k;
}
⑻ 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9,
2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。
解：void Delete5(List& L)
//从线性表中删除所有其值重复的元素,使其所有元素的值均不同
{
int i=0;
while(i<L.size){
int j=i+1;
while(j<L.size)
{ //删除重复值为L.list[i]的所有元素
if(L.list[j]==L.list[i]){
for(int k=j+1;k<L.size;k++)
L.list[k-1]=L.list[k];
L.size--;
}
else
j++;
}
i++;
}
}
4.对于结点类型为LNode的单链接表,编写出下列每个算法。
⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则
逆序链接后变为an,an-1,...a1。
解：void Contrary(LNode*&HL)
//将一个单多办实事有按逆序链接
{
LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点
HL=NULL;//HL仍为逆序后的表头指针，禄始值为空
while(p!=NULL)
{ //把原单链表中的结点依次进行逆序链接
LNode*q=p; //q指向待处理的结点
p=p->next; //p指向下一个待逆序的结点
//将q结点插入到已陈序单链表的表头
q->next=HL;
HL=q;
}
}
⑵ 删除单链表中的第i个结点。
解：void Delete1(LNode*&HL,int i)
//删除单链表中的第i个结点
{
if(i<1||HL==NULL){
cerr<<"Index is out range!"<<end1;
exit(1);
}
LNode*ap,*cp;
ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点
int j=1;
while(cp!=NULL)
if(j==i)
break; //cp结点即为第i个结点
else{ //继续向后寻找
ap=cp;
cp=cp->next;
j++;
}
if(cp==NULL){
cerr<<"Index is out range!"<<end1;
exit(1);
}
if(ap==NULL)
HL=HL->next;
else
ap->next=cp->next;
delete cp;
}
⑶ 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息
并停止运行。
解：ElemType MaxValue(LNode*HL)
//从单链表中查找出所有元素的最大值，该值由函数返回
{
if(HL==NULL){
cerr<<"Linked list is empty!"<<end1;
exit(1);
}
ElemType max=HL->data;
LNode*p=HL->next;
while(p!=NULL){
if(max<p->data) max=p->data;
p=p->next;
}
return max;
}
⑷ 统计出单链表中结点的值等于给定值x的结点数。
解：int Count(LNode*HL,ElemType x)
//统计出单链表中结点的值等于给定值x的结点数
{
int n=0;
while(HL!=NULL){
if(HL->data==x) n++;
HL=HL->next;
}
return n;
}
⑸ 根据一维数组a[n]建立一个单链表，使单链表中元素的次序与a[n]中元素的次序相同，
并使该算法的时间复杂度为O(n)。
解：void Create(LNode*&HL,ElemType a[],int n)
//根据一维数组a[n]建立一个单链表
{
InitList(HL);
for(int i=n-1;i>=0;i--)
InsertFront(HL,a[i];
}
⑹ 将一个单链表重新链接成有序单链表。
解：void OrderList(LNode*&HL)
//将一个单链表重新链接成有序单链表
{
LNode* p=HL;//p指向待处理的第一个结点，初始指向原表头结点
HL=NULL; //HL仍为待建立的有序表的表头指针，禄始值为空
while(p!=NULL)
{ //把原单链表中的结点依次进行有序链接
LNode* q=p; //q指向待处理的结点
p=p->next; //p指向下一个待处理的结点
LNode* ap=NULL,*cp=HL;
//cp指向有序表中待比较的结点，ap指向其前驱结点
while(cp!=NULL)
{ //为插入q结点寻找插入位置
if(q->data<cp->data)
break;
else{
ap=cp;
cp=cp->next;
}
} //将q结点插入到ap和cpxf hko pp uj
q->next=cp;
if(ap==NULL)
HL=q;
else
ap->next=q;
}
}
⑺ 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。
解：LNode*Mergel(LNode*&p1,LNode*&p2)
//将两个有序单链表合并成一个有序单链表
{
LNode a; //a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理
//结束后返回a结点的镄针域的值
LNode*p=&a; //p指向结果的有序单链表的表尾结点
p->next=NULL;//初始指向表头附加结点
while((p1!=NULL)&&(p2!=NULL))
{//处理两个表非空的情况
if(p1->data<p2->data){
p->next=p1;p1=p1->next;
}
else{
p->next=p2;p2=p2->;
}
p=p->next;
}
if(p1!=NULL)p->next=p1;
if(p2!=NULL)p->next=p2;
p1=p2=NULL;
return a.next;
}
⑻ 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链
表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15,
16,20)。
解：LNode*Merge2(LNode*p1,LNode*p2)
//根据两个有序单链表生成一个新的有序单链表
{
LNode a; //用a作为新的有序单链表的表头附加结点
LNode*p=&a; //p指向结果有序单链表的表尾结点
p->next=NULL; //初始指向表头附加结点
while((p1!=NULL&&(p2!=NULL))
{ //处理两个表非空时的情况
LNode*newptr=new LNode;
if(p1->data<p2->data)
{ //由p1->data建立新结点，然后p1指针后移
newptr->data=p1->data;
p1=p1->next;
}
else
{ //由p2->data建立新结点，然后p2指针后移
newptr->data=p2->data;
p2=p2->next;
}
//将newptr结点插入到结果的有序表的表尾
p->next=newptr;
p=newptr;
}
while(p1!=NULL)
{ //继续处理p1单链表中剩余的结点
LNode*newptr=new LNode;
newptr->data=p1->data;
p1=p1->next;
p->next=newptr;
p=newptr;
}
while(p2!=NULL)
{ //继续处理p2单链表中剩余的结点
LNode*newptr=new LNode;
newptr->data=p2->data;
p2=p2->next;
p->next=newptr;
p=newptr;
}
p->next=NULL;
return a.next;
}
⑼ 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有
元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表
保持不变。
解：void Separate(LNode*HL,LNode*&p1,LNode*&p2)
//根据一个单链表HL按条件拆分生成两个单链表p1和p2
{
LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点
LNode*t1=&a,*t2=&b; //t1和t2分别作为指向p1和p2单链表的
//表尾结点，初始指向表头附加结点
Lnode*p=HL;
while(p!=NULL)
{ //每循环一次产生一个新结点，并把它加入到p1或p2单链表
//的未尾
LNode*newptr=new LNode;
if(p->data%2==1){
newptr->data=p->data;
t1->next=newptr;
t1=newptr;
}
else{
newptr->data=p->data;
t2->next=newptr;
t2=newptr;
}
p=p->next;
}
t1->next=t2->next=NULL;
p1=a.next;p2=b.next; //把指向两个单链表的表头结点的指针分别赋给
//p1和p2返回
}
6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是
：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位，
不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下
去直到所有人都出列为止，试求出它们的出列次序。
假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2...,n)开始报数，则得
到的出列次序为:4,8,5,2,1,3,7,6。
此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。
解：
void Josephus(int n,int m,int s)
//使用带表头附加结点的循环单链表解决约瑟夫问题
{
//生成表头附加结点，此时循环单链表为空
LNode*HL=new LNode;
HL->next=HL;
int i;
//生成含有n个结点、结点依次为1,2,...n的带表头结点的循环单链表
for(i=n;i>=1;i--){
//生成新的结点
LNode*newptr=new LNode;
newptr->data=i;
//把新的结点插入到表头
newptr->next=HL->next;
HL->next=newptr;
}
//从表头开始顺序查找出第s个结点，对应第一个开始报数的人
LNode*ap=HL,*cp=HL->next;
for(i=1;i<s;i++){
//ap和cp指针后移一个位置
ap=cp;
cp=cp->next;
//若cp指向了表头附加结点，则仍需后移ap和cp指针，使之指向表头结点
if(cp==HL){ap=HL;cp=HL->next;}
}
//依次使n-1个人出列
for(i=1;i<n;i++){
//顺序查找出待出列的人，即为循环结束后cp所指向的结点
for(int j=1;j<m;j++){
ap=cp;
cp=cp->next;
if(cp==HL){ap=HL;cp=HL->next;}
}
//输出cp结点的值，即出列的人
cout<<cp->data<<"";
//从单链表中删除cp结点
ap->next=cp->next;
delete cp;
//使cp指向被删除结点的后继结点
cp=ap->next;
//若cp指向了表头附加结点，则后移ap和cp指针
if(cp==HL){ap=HL;cp=HL->next;}
}
//使最后一个人出列
cout<<HL->next->data<<end1;
//删除表头结点和表头附加结点
delete HL->next;
delete HL;
}
7.对于在线性表抽象数据类型中定义的每一个操作，写出结点类型为LNode的带头附加结点
的循环单链表上实现的对应算法。
⑴初始化单链表
解：void InitList(LNode*HL)
{
HL->next=HL;//将单链表置空
}
⑵删除单链表中的所有结点，使之成为一个空表
void ClearList(LNode*HL)
{
LNode*cp,*np;
cp=HL->next;//将指向第一个结点的指针赋给cp
while(cp!=HL)//遍历单链表，向系统交回每一个结点。
{
np=cp->next;//保存下一个结点的指针。
delete cp;//删除当前结点。
cp=np;//使下一个结点成为当前结点。
}
HL->next=HL;//置单链表为空
}
⑶得到单链表的长度
int ListSize(LNode*HL)
{
LNode*p=HL->next;
int i=0;
while(p!=HL){i++;p=p->next;}
return i;
}
⑷检查单链表是否为空
int ListEmpty(LNode*hl)
{
return(HL->next==HL);
}
⑸得到单链表中第pos个结点中的元素
ElemType GetElem(LNode*HL,int pos)
{
if(pos<1){
cerr<<"pos is out range!"<<end1;
exit(1);
}
LNode* p=HL->next;
int i=0;
while(p!=HL){
i++;
if(i==pos)break;
p=p->next;
}
if(p!=HL)return p->data;
else{
cerr<<"pos is out range!"<<end1;
exit(1);
}
}
⑹遍历单链表
void TraverseList(LNode*HL)
{
LNode* p=HL->next;
while(p!=HL){
cout<<p->data<<"";
p=p->next;
}
cout<<end1;
}
⑺从单链表查找具有给定值的第一个元素
int Find(LNode* HL,ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)
if(p->data==item){
item=p->data;
return 1;
}
else
p=p->next;
return 0;
}
⑻更新单链表中具有给定值的第一个元素
int Updata(LNode* HL,const ElemType& item)
{
LNode* p=HL->next;
while(p!=HL)//查找元素
if(p->data==item)break;
else p=p->next;
if(p==HL)return 0;
else{//更新元素
p->data=item;
return 1;
}
}
⑼向单链表的未尾插入一个元素
void InsertRear(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;//把新元素赋给动态结点*newptr的值域。
LNode* p=HL;
while(p->next!=HL)//从表头开始遍历到最后一个结点为止。
p=p->next;
newptr->next=HL;p->next=newptr;//把新结点链接到表尾。
}
⑽向单链表的表头插入一个元素
void InsertFront(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
newptr->next=HL->next;
HL->next=newptr;
}
(11)向单链表中插入一个元素
void Insert(LNode* HL,const ElemType& item)
{
LNode* newptr;
newptr=new LNode;
newptr->data=item;
LNode *ap,*cp;
ap=HL;cp=HL->next;
while(cp!=HL)
if(item<cp->data)break;
else{ap=cp;cp=cp->next;}
newptr->next=cp;
ap->next=newptr;
}
(12)从单链表中删除表头元素
ElemType DeleteFront(LNode* HL)
{
if(HL->next==HL){
cerr<<"Deleteing from an empty list!"<<end1;
exit(1);
}
LNode* p=HL->next;
HL->next=p->next;
ElemType temp=p->data;
delete p;
return temp;
}
(13)从单链表中删除等于给定值的第一个元素
int Delete(LNode* HL,const ElemType& item)
{
LNode*ap=HL,*cp=HL->next;
while(cp!=HL)
if(cp->data==item)break;
else{ap=cp;cp=cp->next;}
if(cp==HL){
cerr<<"Deleted element is not exitst!"<<end1;
return 0;
}
else{
ap->next=cp->next;
delete cp;
return 1;
}
}
(14)利用单链表进行数据排序
void LinkSort(ElemType a[],int n)
{
LNode* head=new LNode;
InitList(head);
int i;
for(i=0;i<n;i++)
Insert(head.a[i]);
LNode* p=head->next;
i=0;
while(p!=head){
a[i++]=p->data;
p=p->next;
}
ClearList(head);
delete head;
}
*8.对于结点类型为DNode的双向链表，编写出下列每一个算法。
⑴向双向链表的未尾插入一个值为x的结点。
解：void InsertRear(DNode*&DL,ElemType x)
{
//建立值为x的结点
DNode* newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//当链表为空时完成插入
if(DL==NULL){DL=newptr;return;}
//当链表不为空时完成插入
DNode*p=DL->left;
newptr->right=p->right;
DL->left=newptr;
newptr->left=p;
p->right=newptr;
}
⑵向双向循环表的第i个结点位置插入一个值为x的结点。
解：void Insert(DNode*&DL,int i, ElemType x)
{
//i值越界，退出执行
if(i<=0){
cerr<<"i is out range!"<<end1;
exit(1);
}
//建立值为x的新结点
DNode*newptr=new DNode;
newptr->data=x;
newptr->left=newptr->right=newptr;
//当链表为空同时i等于1时进行插入，i不为1则退出
if(DL==NULL)if(i==1){DL=newptr;return;}
else{out<<"i is range!"<<end1;
exit(1);
}
//实现i等于1时的插入
if(i==1){newptr->right=DL;
newptr->left=DL->left;
DL->left->right=newptr;
DL->left=newptr;
DL=newptr;
return;
}
//查找第i个结点
int k=1;
DNode*p=DL->right;
while(p!=DL){
k++;
if(k==i)break;
p=p->right;
}
//i值越界，退出执行
if(i>k+1){
cerr<<"i is out range!"<<end1;
exit(1);
}
//把newptr结点插入到p结点之前
newptr->right=p;
newptr->left=p->left;
p->left->right=newptr;
p->left=newptr;
return;
}
⑶从双向循环链表中删除值为x的结点。
解：bool Delete(DNode*&DL,ElemType x)
{
if(DL==NULL)return 0;
//当表头结点为x时则删除之
DNode*p=DL;
if(DL->data==x){
DL=DL->right;
p->left->right=DL;
DL->left=p->left;
delete p;
return 1;
}
//查找值为x的结点
p=p->right;
while(p!=DL){
if(p->data==x)break;
else p=p->right;
}
//不存在值为x的结点则返回0
if(p==DL)return 0;
//删除值为x的结点
p->left->right=p->right;
p->right->left=p->left;
delete p;
return 1;
}
9.假定有一种带头附加结点的链表，每个结点含三个域：data、next和range，其中data
为整型值域，next和range均为指针域，现在所有结点已经由next域链接起来，试编一算法
，利用range域把所有结点按照其值从小到大的顺序链接起来，当然由此域链接得到的单链
表的表头指针保存在表头附加结点的range域中。
解：void OrderList(SLNode* SL)
//假定SLNode类型为按题目要求所定义的结点类型，SL为指向表头附加结点的指针
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{ //每循环一次把p所指向的结点按序插入到以range域链接的有序表中
SLNode*ap,*cp;
//为p结点寻找合适的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data<cp->data)
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间，把结点插入其中
p->range=cp;
ap->range=p;
}
}
10.编一程序，实现下列功能：
⒈按照9题对结点的要求生成一个具有10个整数元素结点的带表头附加结点的根据next域
链接的链表，元素值由随机函数产生；
⒉按照next域链接的次序输出链表中每个结点的值；
⒊调用按第9题要求编写的操作算法；
⒋按照range域链接的次序输出链表中每个结点的值。
解：
//lx2-7.cpp
#include<isotream.h>
#include<stdlib.h>
typedef int ElemType;//规定元素类型为整型
struct SLNode//定义单链表结点
{
ElemType data;
SLNode*next;
SLNode*range;
};
void OrderList(SLNode* SL)
{
SL->range=NULL;
for(SLNode*p=SL->next;p!=NULL;p=p->next)
{
SLNode *ap,*cp;
//为p结点寻找合适的插入位置
ap=SL;cp=ap->range;
while(cp!=NULL)
if(p->data<cp->data)
break;
else{
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间，把p结点插入其中
p->range=cp;
ap->range=p;
}
}
void main()
{
//按next域链接生成具有10个整数元素结点的链表
SLNode*a=new SLNode;
a->next=NULL;
int i;
SLNode* p;
for(i=0;i<10;i++){
p=new SLNode;
p->data=range()%30; //假定产生30以内的随机整数
p->next=a->next;
a->next=p;
}
//按next域链接的次序输出单链表
for(p=a->next;p!=NULL;p=p->next)
cout<<p->data<<"";
cout<<end1;
//调用按第9题要求编写的操作算法
orderList(a);
//按range域链接的次序输出单链表
for(p=a->range;p!=NULL;p=p->range)
cout<<p->data<<"";
cout<<end1;
}
