1. Toy模板网首页
  2. > Toy博客

编程题实训-链表应用

10月前 作者：JAVA郑 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了编程题实训-链表应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第1关：基于链表的两个一元多项式的基本运算

任务描述

本关任务：给定两个一元多项式A(x)与B(x)，利用链表表示A(x)与B(x)，实现A(x)与B(x)的加法、减法、乘法和求导运算。

编程要求

输入

输入多组数据，总计n*( a+b+2)+1行。其中，第一行整数n代表总计有n组数据，之后依次输入n组数据。每组数据包括a+b+2行，其中第一行是两个整数a和b，分别代表A(x)与B(x)的项数。之后紧跟a行，每行两个整数a1和a2，分别代表A(x)每项的系数和指数，再之后紧跟b行，每行两个整数b1和b2，分别代表B(x)每项的系数和指数，每组数据最后一行为一个字符（+、-、*、'），分别代表多项式的加法、减法、乘法和求导运算。所有数据的绝对值小于100，指数大于等于0。

输出

对于每组数据输出一行，按照多项式次数从大到小排列，参考格式：5x^17+22x^7+11x^1+7。

#include <iostream>
#include <string>
using namespace std;
typedef struct  LNode{
	int coe;
	int exp;
	struct LNode *next;
}LNode,*LinkList;
void CreatePolynomial(LinkList &L,int n){
	L = new LNode;
	L->next = NULL;
	for(int i=0;i<n;i++){
		LinkList p = new LNode;
		cin>>p->coe>>p->exp;
		LinkList pre =L,cur = L->next;
		while(cur&&p->exp<cur->exp){
			pre = cur;
			cur = cur->next;
		}
		p->next = cur;
		pre->next=p;
	}
}
void OutputPolynomial(LinkList L)
{//输出多项式
	if(!L||!L->next) cout<<0;
	LinkList p=L->next;     //p是多项式链表的工作指针,初始化为首元结点
	while(p)
	{
		if(p==L->next)     //p指向首元结点时，根据指数的情况输出多项式
        {
			if (p->exp!=0)
				cout<<p->coe<<"x^"<<p->exp;
			else
				cout<<p->coe;
		}
		else      //p指向其他结点时，根据系数的正负和指数的情况输出多项式
        {
			if(p->coe>0) cout<<"+";
			if(p->exp!=0)
				cout<<p->coe<<"x^"<<p->exp;
			else
				cout<<p->coe;
		}
		p=p->next;
	}
	cout<<endl;
}


LinkList Add(LinkList LA,LinkList LB){
	LinkList pa = LA->next;
	LinkList pb = LB->next;
	LinkList LC;
	CreatePolynomial(LC,0);
	LinkList pc = LC;
	while(pa&&pb){
		if(pa->exp == pb->exp){
			int sum = pa->coe + pb->coe;
			if(sum){
				pa->coe = sum;
				pc->next = pa;
				pc = pa;
				pa = pa->next;
				pb = pb->next;
			}else{
				pa = pa->next;
				pb = pb->next;
			}
		}else if(pa->exp>pb->exp){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa?pa:pb;
	return LC;
}


void Minus(LinkList LA,LinkList LB){
	LinkList p = LB->next;
	while(p){
		p->coe*= -1;
		p = p->next;
	}
	OutputPolynomial(Add(LA,LB));
}

LinkList Mul(LinkList LA,LinkList LB){
	LinkList pa = LA->next;
	LinkList pb = LB->next;
	LinkList LC;
	CreatePolynomial(LC,0);
	LinkList temp;
	CreatePolynomial(temp,0);
	while(pa){
		while(pb){
			LinkList p = new LNode;
			p->next = NULL;
			p->coe = pa->coe*pb->coe;
			p->exp = pa->exp + pb->exp;
			temp->next = p;
			LC = Add(LC,temp);
			pb = pb->next;  
		}
		pb = LB->next;
		pa = pa->next;
	}
	OutputPolynomial(LC);
	
}

void Diff(LinkList L)
{//多项式的求导运算
	LinkList p=L->next;  //p是链表L的工作指针，初始化为首元结点
	LinkList r=NULL;  //r是删除操作的辅助指针
	while(p)
	{
		p->coe*=p->exp;
		p->exp--;
		if(p->exp<0)  //所有数据的指数大于等于0
        {
			r=p;
			p=p->next;
			delete r;
		}
		else
		{
			p=p->next;
		}
	}
	OutputPolynomial(L);
}

void Opt(LinkList &LA,LinkList &LB,string s)
{//依据字符选择多项式的加法、减法、乘法和求导运算
    if(s=="+") OutputPolynomial(Add(LA, LB));
    if(s=="-") Minus(LA, LB);
    if(s=="*") Mul(LA, LB);
    if(s=="'")
    {
        Diff(LA);
        Diff(LB);
    }
}


int main(){
	int n;
	cin>>n;
	while(n--){
		int a,b;
		cin>>a>>b;
		LinkList LA,LB;
		CreatePolynomial(LA,a);
		CreatePolynomial(LB,b);
		string s;
		cin>>s;
		Opt(LA,LB,s);
	}
	return 0;
}

第2关：基于链表的两个递增有序序列的合并

任务描述

本关任务：给定两个递增的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个递增的有序序列C，序列C不允许有重复的数据。要求空间复杂度为O(1)。

编程要求

输入

多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出

对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void MergeList(LinkList &LA,LinkList &LB)
{//求基于链表的两个递增有序序列的合并
/**************begin************/
    
LinkList pa,pb,pc,q;
LinkList LC;
    pa=LA->next;
    pb=LB->next;
    pc=LC=LA;
    while (pa&&pb)
    {
        if (pa->data<pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if (pa->data>pb->data)
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
        else 
        {
            pc->next=pa;  //删掉一样的
            pc=pa;
            pa=pa->next;
            q=pb->next;
            delete pb;
            pb=q;
        }
    }
    pc->next=pa?pa:pb;  //如果一个序列比完，结束循环，剩余的直接插在链表后面
    delete LB;


    /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        LinkList LA,LB;
        CreateList_R(LA,n);
        CreateList_R(LB,m);
        MergeList(LA,LB);
        PrintList(LA);
    }
    return 0;
}

第3关：基于链表的两个非递减有序序列的合并

编程要求

输入

多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出

对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

//要结合上下文,本题与上题思路相似，但注意主函数中PrintList(LC);

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void MergeList(LinkList &LA,LinkList &LB,LinkList &LC)
{//求基于链表的两个非递减有序序列的合并
/**************begin************/
LinkList pa,pb,pc,q;
pa=LA->next;
pb=LB->next;
LC=pc=LA;
LC->next=NULL;
while (pa||pb)
{
    if (!pa)//LA表为空，用q指向pb，pb指针后移
    {
        q=pb;
        pb=pb->next;
    }
    else if (!pb)//LB表为空，用q指向pa，pa指针后移
    {
        q=pa;
        pa=pa->next;
    }
    else if (pa->data<=pb->data)
    {
        q=pa;
        pa=pa->next;
    }
    else 
    {
        q=pb;
        pb=pb->next;
    }
    q->next=LC->next;
    LC->next=q;//将q指向的节点插在LC表的表头节点之后
}
delete LB;



    /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        LinkList LA,LB,LC;
        CreateList_R(LA,n);
        CreateList_R(LB,m);
        MergeList(LA,LB,LC);
        PrintList(LC);
    }
    return 0;
}

第4关：基于链表的两个集合的交集

任务描述

本关任务：给定两个递增的整数集合A和B，分别用链表表示集合A和B，求出A和B的交集，并存放在A中。要求空间复杂度为O(1)。

编程要求

输入

多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出

对于每组数据输出一行，为A和B的交集，每个数据之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void Intersection(LinkList &LA,LinkList &LB)
{//求基于链表的两个集合的交集
/**************begin************/
LinkList pa,pb,pc,u,LC;
pa=LA->next;
pb=LB->next; //pa 和 pb 分别是链表 La 和 Lb 的工作指针 , 初始化为相应链表的第一个结点
	LC=pc=LA; // 用 La 的头结点作为 Lc 的头结点
	while(pa&&pb) 
	{ 
		  if (pa->data==pb->data)//交集并入结果表中。
	 	  { pc->next=pa;
            pc=pa;pa=pa->next; 
	        u=pb;pb=pb->next; 
            delete u;
          } 
		else if(pa->data<pb->data) 
		{
        u=pa;
        pa=pa->next; 
        delete u;
        } 
		else 
		{
        u=pb; 
        pb=pb->next;
        delete u;
        } 
	}
	while(pa)
    {
    u=pa; 
    pa=pa->next; 
    delete u;
    } //释放结点空间
	 while(pb) 
     {
     u=pb; 
     pb=pb->next; 
     delete u ;
     } //释放结点空间
	pc->next=NULL;//置链表尾标记。
	delete LB; // 释放 Lb 的头结点


    /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        LinkList LA,LB;
        CreateList_R(LA,n);
        CreateList_R(LB,m);
        Intersection(LA,LB);
        PrintList(LA);
    }
    return 0;
}

第5关：基于链表的两个集合的差集

任务描述

本关任务：给定两个递增的整数集合，分别用链表A和B表示，求出A和B的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。要求空间复杂度为O(1)。

编程要求

输入

多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出

对于每组数据输出两行，第一行是A和B的差集，第二行为差集中的元素个数，每个数据之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//依次输出链表中的数据和该集合的元素个数
    L=L->next;
    int s=0;
    while(L)
    {
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
        s++;
    }
    cout<<endl<<s<<endl;
}
void Difference(LinkList &LA,LinkList &LB)
{//求基于链表的两个集合的差集
/**************begin************/
   LinkList pa,pb,u,pre;
pa=LA->next;
pb=LB->next;
pre=LA;//pre为LA中pa所指结点的前驱结点的指针
while (pa&&pb)
{
    if (pa->data<pb->data)
    {
        pre=pa;
        pa=pa->next;
       
    }
    else if (pa->data>pb->data)
    {
        pb=pb->next;

    }
    else 
    {
        pre->next=pa->next;//处理A，B中元素相同的结点，应删除
        u=pa;
        pa=pa->next;
        delete u;
    }
}



   
    /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        LinkList LA,LB;
        CreateList_R(LA,n);
        CreateList_R(LB,m);
        Difference(LA,LB);
        PrintList(LA);
    }
    return 0;
}

第6关：链表的分解

任务描述

本关任务：利用单链表A表示一个非零整数序列，把A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点。要求空间复杂度为O(1)，链表B和C均利用链表A的结点空间。

编程要求

输入

多组数据，每组数据有两行，第一行为链表A的长度n，第二行为链表A的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出两行，分别对应链表B和C的元素，每个数据之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void Decompose(LinkList &LA,LinkList &LB,LinkList &LC)
{//链表的分解
/**************begin************/
    LB=new LNode;
  LB->next=NULL;
  LC=new LNode;
  LC->next=NULL;
  LinkList pa=LA->next,pb=LB,pc=LC,q;//pa，pb和pc分别是LA,LB和LC的工作指针，q暂存pa的后继
  while (pa!=NULL)
  {
      q=pa->next;
      if (pa->data<0)//将小于0的结点链入LB表，尾插法
      { 
        pb->next=pa;
        pb=pa;
      }
      else
      {
        pc->next=pa;
        pc=pa;
      }
      pa=q;
  }
  pb->next=NULL;
  pc->next=NULL;
  


  
    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList LA,LB,LC;
        CreateList_R(LA,n);
        Decompose(LA,LB,LC);
        PrintList(LB);
        PrintList(LC);
    }
    return 0;
}

第7关：查找链表中的最大值 

任务描述

本关任务：利用单链表表示一个整数序列，通过一趟遍历在单链表中确定值最大的结点。

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出一行，输出每个链表的最大值。

#include <iostream>
using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void CreateList_R(LinkList &L,int n)
{
    L->next=NULL;
    LinkList r=new LNode;
    r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

int MaxData(LinkList L)
{//确定单链表中值最大的结点
/**************begin************/
  LinkList p ,MaxData;
  if (L->next==NULL)
  return NULL;
   MaxData=L->next;
   p=L->next->next;
  while (p!=NULL)
  {
      if (p->data > MaxData->data)// 如果 p 的值大于 pmax 的值，则重新赋值
      {
        MaxData=p;
      }
      p=p->next;
  } 
return MaxData->data;



  
    /**************end************/
}

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L=new LNode;
        CreateList_R(L,n);
        cout<<MaxData(L)<<endl;
    }
    return 0;
}

第8关：链表的逆转 

任务描述

本关任务：利用单链表表示一个整数序列，通过一趟遍历，将单链表中所有结点的链接方向逆转。要求空间复杂度为O(1)。

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出一行，逆序输出链表中的元素，元素之间用空格分隔。

#include <iostream>
using namespace std;

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void CreateList_R(LinkList &L,int n)
{
    L->next=NULL;
    LinkList r=new LNode;
    r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

void Inverse(LinkList &L)
{//逆置带头结点的单链表L
/**************begin************/
LinkList p,q;
p=L->next;
L->next=NULL;
while (p)
{
    q=p->next;
    p->next=L->next;
    L->next=p;
    p=q;
}




    /**************end************/
}

void PrintList(LinkList &L)
{
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L=new LNode;
        CreateList_R(L,n);
        Inverse(L);
        PrintList(L);
    }
    return 0;
}

第9关：删除链表中满足区间值的结点 

任务描述

本关任务：利用单链表表示一个递增的整数序列，删除链表中值大于等于mink且小于等于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔），第三行为给定的mink和maxk（用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出一行，依次输出删除元素后的链表元素，元素之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void DeleteMinMax(LinkList &L,int mink,int maxk)
{//删除链表中满足区间值的结点
/**************begin************/
LinkList p,q,pre=L,s;
p=L->next;
while (p&&p->data<mink)
{
    pre=p;
    p=p->next;//查找第一个值>mink的结点
}
 
    while (p&&p->data<=maxk)
    {
        p=p->next;
    }
    
    q=pre->next;
    pre->next=p;
    while (q!=p)
    {
        s=q->next;
        delete q;
        q=s;
    }



    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        int mink,maxk;
        cin>>mink>>maxk;
        DeleteMinMax(L,mink,maxk);
        PrintList(L);
    }
    return 0;
}

第10关：双向循环链表中结点的交换 

任务描述

本关任务：利用双向循环链表表示一个整数序列，指定一个结点位置用p指向该结点，交换p所指向的结点及其前驱结点的顺序。

编程要求

输入

多组数据，每组数据有三行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔），第三行为p所指向的结点位置。当n=0时输入结束。

输出

对于每组数据分别输出一行，依次输出交换结点顺序后的链表元素，元素之间用空格分隔。

#include<iostream>
using namespace std;
typedef struct DuLNode
{
	int data;
	struct DuLNode *next;
	struct DuLNode *prior;
}DuLNode,*DuLinkList;
void CreateList(DuLinkList &L,int n)
{//建立双向循环链表

    L=new DuLNode;    //初始化链表L的头结点
	L->prior=L;
	L->next=L;
	DuLinkList r=L;     //工作指针r初始化指向头结点
	while(n--)
	{
		DuLinkList p=new DuLNode;
		cin>>p->data;
		p->next=r->next;
		r->next=p;
		p->prior=r;
		p->next->prior=p;
		r=p;
	}
}
void Exchange(DuLinkList &L,int loc)
{//双向循环链表中结点的交换
/**************begin************/
   DuLinkList p,q;
int j;
p=L->next;
j=1;
while (p&&j<loc)
{
    p=p->next;
    j++;
}
q=p->prior;//定位前一个结点
p->prior=p->prior->prior;//更改p的前驱
q->prior->next=p;//更改q的前驱的后继指向p
q->next=p->next;
p->next=q;
q->prior=p;

    /**************end************/
}
void PrintList(DuLinkList &L)
{//依次输出链表中的数据
    DuLinkList p=L->next;
	while(p->next&&p->next!=L)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<p->data<<endl;
}
int main()
{
	int n;
	while(cin>>n)
	{
	 	if(n==0) break;
	 	DuLinkList L;
	 	CreateList(L,n);
	 	int loc;
		cin>>loc;
		if(n==1)          //链表仅有一个元素时输出其自身
		{
			cout<<L->next->data<<endl;
			continue;
		}
		Exchange(L,loc);
		PrintList(L);
	}
	return 0;
}

第11关：查找链表中倒数第k个结点 

任务描述

本关任务：利用单链表表示一个整数序列，请实现一个时间复杂度为O(n)、空间复杂度为O(1)的算法，通过一趟遍历在单链表中确定倒数第k个结点。

编程要求

输入

多组数据，每组数据有三行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔），第三行为k。当n=0时输入结束。

输出

对于每组数据分别输出一行，输出每个链表的倒数第k个结点对应的数值。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void Search_k(LinkList L,int k)
{
    /**************begin************/
LinkList p=L->next,q=L->next;
int n=0;
while (p!=NULL)//p先走k步，然后和q一起走，p到达尾部时，q所指的刚好就是倒数第k的结点
{
    if (n<k)
    {
    p=p->next;
    n++;
    }
    else 
    {
        p=p->next;
        q=q->next;
    }
}
cout<<q->data<<endl;





    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        int k;
        cin>>k;
        Search_k(L,k);
    }
    return 0;
}

第12关：删除链表中绝对值相等的结点 

任务描述

本关任务：利用单链表表示一个整数序列，实现一个时间复杂度为O(n)的算法，对于链表中绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

例如，若给定的单链表HEAD如下：

编程题实训-链表应用,数据结构--头歌,链表,数据结构,算法

删除后的单链表HEAD为:

编程题实训-链表应用,数据结构--头歌,链表,数据结构,算法

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

对于每组数据分别输出一行，依次输出删除结点后的链表元素，元素之间用空格分隔。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{//打印依次输出链表中的数据
    L=L->next;
    while(L){
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
int Abs(int x)
{//绝对值函数
	return x>0?x:-x;
}
void DeleteEqualNode(LinkList &L,int n)
{//删除链表中绝对值相等的结点
/**************begin************/
    LinkList p,r;
p=L;
int a[100],m;
for (int i=0;i<100;i++)
{
    a[i]=0;
}
while (p->next!=NULL)
{
    if (p->next->data>=0)
        m=p->next->data;//看结点的绝对值在数组的位序中是否是1
    else 
    m=-(p->next->data);
    if (a[m]==0)
    {
        a[m]=1;
        p=p->next;
    }
    else 
    {
        r=p->next;
        p->next=r->next;
        delete r;
    }
}





    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        DeleteEqualNode(L,n);
        PrintList(L);
    }
    return 0;
}

第13关：查找两个单词链表共同后缀的起始结点 

任务描述

本关任务：假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀空间。 例如，“loading”和“being”的存储映像如下图所示：

编程题实训-链表应用,数据结构--头歌,链表,数据结构,算法

设str1和str2分别指向两个单词所在单链表的头结点，请实现一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置的结点，输出该结点对应的字符（如图中的字符i）。

编程要求

输入

多组数据，每组数据有三行，第一行为链表str1和str2的长度n和m，第二行为链表str1的n个元素，第三行为链表str2的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出

对于每组数据输出一行，为共同后缀的起始位置结点对应的字符。

#include <iostream>
using namespace std;
typedef struct LNode
{
    char data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void FindSuffix(LinkList str1, LinkList str2,int n,int m)
{//查找两个单词链表共同后缀的起始结点

/**************begin************/
 
LinkList longstr,shortstr;
 int k;
 if (n>m)
 {
     longstr=str1->next;
     shortstr=str2->next;
     k=n-m;
 }
else 
{
    longstr=str2->next;
    shortstr=str1->next;
    k=m-n;
}
while (k--)
longstr=longstr->next;
LinkList t=longstr;
int flag=0;
while (longstr)
{
    if (longstr->data==shortstr->data)
    {
        if (flag==0)
        {
            t=longstr;
            flag=1;
        }
    }
    else 
    {
        flag=0;
    }
    longstr=longstr->next;
    shortstr=shortstr->next;
}
cout<<t->data<<endl;



 
   /**************end************/
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        LinkList str1,str2,p;
        CreateList_R(str1,n);
        CreateList_R(str2,m);
        FindSuffix(str1,str2,n,m);
    }
    return 0;
}

第14关：猴子选大王问题 

任务描述

本关任务：一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1~m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。利用单向循环链表模拟此过程，依次输出出圈的猴子编号。

编程要求

输入

多组数据，每组数据占一行，包括两个数据m和n。m代表猴子个数，n代表步数，m=0且n=0时输入结束。

输出

依次输出出圈的猴子编号，编号之间用空格隔开。

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateCirList(LinkList &L,int m)
{//后插法创建单向循环链表
    L=new LNode;
    L->next=NULL;
    L->data=1;
    LinkList r=L;
    for(int i=2;i<=m;i++)
    {
        LinkList p=new LNode;
        p->data=i;
        p->next=NULL;
        r->next=p;
        r=p;
    }
    r->next=L;                                   //尾结点的指针指向首元结点,单向循环链表建成
    L=r;                                          //L需要指向尾结点，以防n=1时第一个需要删除的是首元结点，不易得到前驱结点
}
void MonkeyKing(LinkList &L,int n)
{//猴子选大王（约瑟夫问题）
/**************begin************/
   // int answer[100];
 
LinkList tail,head,p,q;
head=L;
tail=head;
p=head->next;
q=tail;//p在最前面时，最后一个节点是他的前继结点
int i=1;
while (p!=q)
{
    if (i==n)
    {
        q->next=p->next;
        printf ("%d ",p->data);
        delete p;
        p=q->next;
        i=1;
    }
    else 
    {//p，q各自向后移动一个节点，其中q总在p的前面
    q=p;
    p=p->next;
    i++;
    }
   
}
 printf ("%d",q->data);
 printf ("\n");






   
    /**************end************/
}
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        if(n==0&&m==0) break;
        LinkList L;
        CreateCirList(L,m);
        MonkeyKing(L,n);
    }
    return 0;
}

第15关：奇偶链表的分割 

任务描述

本关任务：给定一个单链表，把所有的奇数结点和偶数结点分别排在一起，重新链成一个新链表。请注意，这里的奇数结点和偶数结点指的是结点编号的奇偶性，而不是结点的值的奇偶性。

要求：空间复杂度应为 O(1)，时间复杂度应为 O(n)，n 为链表结点总数。

编程要求

输入

多组数据，每组数据有两行，第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔）。当n=0时输入结束。

输出

奇数结点和偶数结点分割后重新链成的新链表。文章来源地址https://www.toymoban.com/news/detail-809935.html

#include<iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void Decollate(LinkList L,LinkList L1)
{//奇偶链表的分割
/**************begin************/
  LinkList p=L->next;//初始化p指向L的首元节点
  LinkList q=L;//初始化q指向L的头节点
  LinkList p1=L1;//初始化p1指向新链表L1的头结点
  int num=1;
  while (p)
  {
      if (num%2!=0)
      {
          p1->next=p;
          p1=p1->next;
          q->next=p->next;
          p->next=NULL;
          p=q->next;
      }
      else 
      {
          q=q->next;
          p=p->next;
      }
      num++;//结点序号加1；
  }
  p1->next=L->next;//将剩余链表部分链入新链表的表尾
  delete L;//删除原链表的头结点





  
    /**************end************/
}
void PrintList(LinkList &L)
{//依次输出链表中的数据
    LinkList p=L->next;
    while(p)
    {
        if(p->next!=NULL) cout<<p->data<<" ";
        else cout<<p->data;
        p=p->next;
    }
    cout<<endl;
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		LinkList L=new LNode;
        CreateList_R(L,n);
        LinkList L1=new LNode;    //申请新链表L1
        L1->next=NULL;
        Decollate(L,L1);      //奇偶链表的分割
        PrintList(L1);
	}
	return 0;
}

到了这里，关于编程题实训-链表应用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【 第4关：入栈和出栈的基本操作】【编程题实训-栈】【头歌】【bjfu-243】

    本关任务：输入一个整数序列a1,a2,a3…,an。当ai不等于-1时将ai进栈；当ai=-1时，输出栈顶元素并将其出栈。 输入 多组数据，每组数据有两行，第一行为序列的长度n，第二行为n个整数，整数之间用空格分隔。当n=0时输入结束。 输出 对于每一组数据输出若干行。每行为相应的出

    2024年02月06日
    浏览(42)
  • 【数据结构与算法】之8道顺序表与链表典型编程题心决！

    【数据结构与算法】之8道顺序表与链表典型编程题心决！

                                                                                    个人主页：秋风起，再归来~                                                                                             数据结构与算

    2024年04月14日
    浏览(57)

  • 【 第1关：基于栈的中缀算术表达式求值】【编程题实训-栈】【头歌】【bjfu-240】

    本关任务：输入一个中缀算术表达式，求解表达式的值。运算符包括+、-、*、/、(、)、=，参加运算的数为double类型且为正数。（要求：直接针对中缀算术表达式进行计算，不能转换为后缀或前缀表达式再进行计算，只考虑二元运算即可。） 输入 多组数据，每组数据一行，对

    2024年02月06日
    浏览(53)
  • 【023】C/C++数据结构之链表及其实战应用

    【023】C/C++数据结构之链表及其实战应用

    💡 作者简介：专注于C/C++高性能程序设计和开发，理论与代码实践结合，让世界没有难学的技术。包括C/C++、Linux、MySQL、Redis、TCP/IP、协程、网络编程等。 👉 🎖️ CSDN实力新星，社区专家博主 👉 🔔 专栏介绍：从零到c++精通的学习之路。内容包括C++基础编程、中级编程、

    2024年02月08日
    浏览(54)

  • 数据结构：链表应用：第1关：基于链表的两个一元多项式的基本运算

    任务描述 本关任务：给定两个一元多项式A(x)与B(x)，利用链表表示A(x)与B(x)，实现A(x)与B(x)的加法、减法、乘法和求导运算。 编程要求 输入 输入多组数据，总计n*( a+b+2)+1行。其中，第一行整数n代表总计有n组数据，之后依次输入n组数据。每组数据包括a+b+2行，其中第一行是两

    2024年04月12日
    浏览(57)

  • C++数据结构与算法详解：链表、栈、队列、树、二叉树和图结构的实现与应用

    链表是一种常见的数据结构由一系列节点按顺序连接而成，一般每个节点包含一个数据元素和一个指向下一个节点的引用。 链表有多种类型： 单向链表：每个节点只有一个指向下一个节点的引用 双向链表：每个节点有一个指向前一个节点和一个指向后一个节点的引用 循环链

    2024年02月04日
    浏览(48)
  • 数据库系统概论---选择题刷题实训

    数据库系统概论---选择题刷题实训

    1. 下列选项中，不属于关系模型三要素的是（  C   ） A．数据结构                   B．数据操纵     C． 数据安全                   D．数据完整性规则       关系数据模型的三个组成部分中，不包括 （  D   ）    A. 完整性规则          B. 数据结

    2024年02月07日
    浏览(42)
  • [JDK8下的HashMap类应用及源码分析] 数据结构、哈希碰撞、链表变红黑树

    [JDK8下的HashMap类应用及源码分析] 数据结构、哈希碰撞、链表变红黑树

    [Java基础] StringBuffer 和 StringBuilder 类应用及源码分析 [Java基础] 数组应用及源码分析 [Java基础] String，分析内存地址，源码 [JDK8环境下的HashMap类应用及源码分析] 第一篇 空构造函数初始化 [JDK8环境下的HashMap类应用及源码分析] 第二篇 看源码了解HashMap的扩容机制 [JDK8环境下的

    2024年02月10日
    浏览(43)

  • 【数据结构实训】哈希表设计

    [问题描述] 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过2，并完成相应的建表和查表程序。 [基本要求] 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或

    2024年02月11日
    浏览(41)

  • 构造哈夫曼树(数据结构实训)(难度系数85)

    构造哈夫曼树 题目描述： 根据给定的叶结点字符及其对应的权值创建哈夫曼树。 输入： 第一行为叶子结点的数目n(1=n=100)。第二行为一个字符串，包含n个字符，每个字符对应一个叶子结点，第三行为每个叶子结点的概率（即权值），要求根据各叶结点构造哈夫曼树。构造哈

    2024年02月03日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包