塔防——链表的基本操作

---

---

题目：

---

---

分析：

这道题用链表来实现会比较方便，题目的几种操作都是链表的一些基本操作。和链表的对应具体如下：

• add x 新建一个节点，节点数据为x,并接在链表末尾
• del k 删除链表的第k个节点
• cge k x 把第k个节点的数据改为x
• qry k 输出第k个节点的数据

---

---

代码：

#include<iostream>
#include<stdlib.h>
#include<string>

using namespace std;

struct Game
{
    int hp;

    Game *next;
};

int main()
{
    int n,m,k,x,i,j,a;
    string str;
    Game *head,*pnew,*p,*p1;

    head=(Game*)malloc(sizeof(Game));
    head->next=NULL;
    p=head;

    cin>>n>>m;
    for(i=0;i<n;i++)                     //创建初始链表
    {
	    cin>>a;
	    pnew=(Game*)malloc(sizeof(Game));
	    pnew->hp=a;
	    p->next=pnew;
	    pnew->next=NULL;
	    p=p->next;
    }

    for(i=0;i<m;i++)
    {
	    cin>>str;
	    if(str=="add")             
	    {
		    cin>>x;
		    p=head;
		    while(p->next!=NULL)                   //定位到链表末尾
			    p=p->next;
		    pnew=(Game*)malloc(sizeof(Game));    //新建结点
		    pnew->hp=x;                          //节点数据为x
		    p->next=pnew;                       //插入链表末尾
		    pnew->next=NULL;
		    p=p->next;
	    }
	
	    if(str=="del")
	    {
		    cin>>k;
		    p=head;
		    for(j=0;j<k;j++)                 //定位到第k个节点
			    p=p->next;
		    p1=p->next;                      //删除节点
		    p->next=p1->next;
		    delete p1;
	    }
	
	    if(str=="cge")
	    {
		    cin>>k>>x;
		    p=head;
		    for(j=0;j<=k;j++)              //定位到第k个节点
			    p=p->next;
		    p->hp=x;                       //节点数据改为x
	    }
	
	    if(str=="qry")
	    {
		    cin>>k;
		    p=head;
		    for(j=0;j<=k;j++)             //定位到第k个节点
			    p=p->next;
		    cout<<p->hp<<endl;           //输出节点数据
	    }
    }
    return 0;
 } 

---

---