PTA 7-4 单链表基本操作

7-4 单链表基本操作

请编写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列,输出实施上述操作后的链表。单链表数据域值为整数。

输入格式:

输入第1行为1个正整数n,表示当前单链表长度;第2行为n个空格间隔的整数,为该链表n个元素的数据域值。第3行为1个正整数m,表示对该链表施加的操作数量;接下来m行,每行表示一个操作,为2个或3个整数,格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点,若k=0则表示表头插入。1 k表示删除链表中第k个结点,此时k不能为0。注:操作序列中若含有不合法的操作(如在长度为5的链表中删除第8个结点、删除第0个结点等),则忽略该操作。n和m不超过100000。

输出格式:

输出为一行整数,表示实施上述m个操作后的链表,每个整数后一个空格。输入数据保证结果链表不空。

输入样例:

5
1 2 3 4 5
5
0 2 8
0 9 6
0 0 7
1 0 
1 6

输出样例:

7 1 2 8 3 5 

参照课本的实现

#include<iostream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
typedef int ElemType;
typedef int Status;
#define ERROR 0
#define OK 1
#define OVERFLOW 3

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

Status ListInsert(LinkList L,int i,ElemType e)
{
    int j=0;
    LinkList p=L,s;
    while(p&&j<i-1) // 寻找第i-1个结点
    {
        p=p->next;
        j++;
    }
    if(!p||j>i-1) // i小于1或者大于表长
        return ERROR;
    s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
    s->data=e; // 插入L中
    s->next=p->next;
    p->next=s;
    return OK;
 }

 Status ListDelete(LinkList L,int i)
 {
   int j=0;
   LinkList p=L,q;
   while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
   {
     p=p->next;
     j++;
   }
   if(!p->next||j>i-1) // 删除位置不合理
     return ERROR;
   q=p->next; // 删除并释放结点
   p->next=q->next;
   free(q);
   return OK;
 }

 int main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     LinkList L;
     L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
     if(!L) // 存储分配失败
        exit(OVERFLOW);
     L->next=NULL;

     int n=0,m=0;
     LinkList db=L,da;
     cin>>n;
     for(int i=0;i<n;i++)
     {
         da=(LinkList)malloc(sizeof(LNode));
         cin>>da->data;
         da->next=NULL;
         db->next=da;
         db = da;
     }
     cin>>m;
     for(int i=0;i<m;i++)
     {
         int o,x,y;
         cin>>o;
         if(o==0)
         {
             cin>>x>>y;
             ListInsert(L,x+1,y);
         }
         else if(o==1)
         {
             cin>>x;
             ListDelete(L,x);
         }
         else
         {
             exit(ERROR);
         }
     }

     LinkList p=L->next;
     while(p!=NULL)
     {
         cout<<p->data<<" ";
         p = p->next;
     }

     return 0;
 }

上一篇:单链表数据结构代码(C语言)


下一篇:Java集合框架 :ArrayList 类,LinkedList 类 较详细