9.16日pta练习

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

输入格式:

输入第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个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。

这一段代码是根据书上完成的，可以通过测试

  1 #include<iostream>
  2 #include<iomanip>
  3 #include<stdlib.h>
  4 using namespace std;
  5 typedef int ElemType;
  6 typedef int Status;
  7 #define ERROR 0
  8 #define OK 1
  9 #define OVERFLOW 3
 10 
 11 typedef struct LNode
 12 {
 13     ElemType data;
 14     struct LNode *next;
 15 }LNode ,*LinkList;
 16 
 17 Status ListInsert(LinkList L,int i,ElemType e)
 18 {
 19     int j=0;
 20     LinkList p=L,s;
 21     while(p&&j<i-1) // 寻找第i-1个结点
 22     {
 23         p=p->next;
 24         j++;
 25     }
 26     if(!p||j>i-1) // i小于1或者大于表长
 27         return ERROR;
 28     s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
 29     s->data=e; // 插入L中
 30     s->next=p->next;
 31     p->next=s;
 32     return OK;
 33  }
 34 
 35  Status ListDelete(LinkList L,int i)
 36  {
 37    int j=0;
 38    LinkList p=L,q;
 39    while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
 40    {
 41      p=p->next;
 42      j++;
 43    }
 44    if(!p->next||j>i-1) // 删除位置不合理
 45      return ERROR;
 46    q=p->next; // 删除并释放结点
 47    p->next=q->next;
 48    free(q);
 49    return OK;
 50  }
 51 
 52  int main()
 53  {
 54      ios::sync_with_stdio(false);
 55      cin.tie(0);
 56      cout.tie(0);
 57      LinkList L;
 58      L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
 59      if(!L) // 存储分配失败
 60         exit(OVERFLOW);
 61      L->next=NULL;
 62 
 63      int n=0,m=0;
 64      LinkList db=L,da;
 65      cin>>n;
 66      for(int i=0;i<n;i++)
 67      {
 68          da=(LinkList)malloc(sizeof(LNode));
 69          cin>>da->data;
 70          da->next=NULL;
 71          db->next=da;
 72          db = da;
 73      }
 74      cin>>m;
 75      for(int i=0;i<m;i++)
 76      {
 77          int o,x,y;
 78          cin>>o;
 79          if(o==0)
 80          {
 81              cin>>x>>y;
 82              ListInsert(L,x+1,y);
 83          }
 84          else if(o==1)
 85          {
 86              cin>>x;
 87              ListDelete(L,x);
 88          }
 89          else
 90          {
 91              exit(ERROR);
 92          }
 93      }
 94 
 95      LinkList p=L->next;
 96      while(p!=NULL)
 97      {
 98          cout<<p->data<<" ";
 99          p = p->next;
100      }
101 
102      return 0;
103  }

不过我自己根据网上的单链表的学习，写了一下程序，发现通过不了，显示段错误和运行超时，不知道为什么，希望大神可以指出来

  1 #include <iostream>
  2 #include <stdlib.h>
  3 using namespace std;
  4 typedef struct LinkNode{
  5     int data;
  6     struct LinkNode* next;
  7 }LinkNode;
  8 struct LinkNode* InputData(){
  9     struct LinkNode* header = (struct LinkNode*)malloc(sizeof(struct LinkNode));
 10     header->data=-1;
 11     header->next=NULL;
 12     struct LinkNode* ptail=header;
 13     int n;
 14     cin>>n;
 15     for(int i=0;i<n;i++){
 16         int number;
 17         struct LinkNode* newNode=(struct LinkNode*)malloc(sizeof(struct LinkNode));
 18         cin>>number;
 19         newNode->data=number;
 20         newNode->next=NULL;
 21         ptail->next=newNode;
 22         ptail=newNode;
 23     }
 24     return header;
 25 }
 26 void Insert (struct LinkNode* header,int k,int d){
 27     if(header==NULL){
 28         return;
 29     }
 30     int count=0;
 31     struct LinkNode* ptail =header->next;
 32     while(ptail!=NULL){
 33         count++;
 34         ptail=ptail->next;
 35     }
 36     if(k>count){
 37         return;
 38     }
 39     struct LinkNode* pfrount =header;
 40     struct LinkNode* pcurrent = header->next;
 41     for(int i=0;i<k;i++){
 42         pfrount=pcurrent;
 43         pcurrent=pcurrent->next;
 44     }
 45     if(pfrount==NULL){
 46         return;
 47     }
 48     struct LinkNode* newNode = (struct LinkNode*)malloc(sizeof(struct LinkNode));
 49     newNode->data=d;
 50     newNode->next=NULL;
 51     newNode->next=pcurrent;
 52     pfrount->next=newNode;
 53 }
 54 void DeleteNode(struct LinkNode* header,int k){
 55     if(header==NULL){
 56         return;
 57     }
 58     if(k==0){
 59         return;
 60     }
 61     struct LinkNode* pfront =header;
 62     struct LinkNode* pcurrent=header->next;
 63     for(int i=0;i<k-1;i++){
 64         pfront=pcurrent;
 65         pcurrent=pcurrent->next;
 66     }
 67     pfront->next=pcurrent->next;
 68 }
 69 void  Foreach_LinkNode(struct LinkNode* Header)
 70 {
 71     if (Header == NULL)
 72         return;
 73     struct LinkNode* Pcurrent = Header->next;            //Pcurrent 现在的指针
 74     while (Pcurrent != NULL)                            //判断现在里面的值是否为空
 75     {
 76         printf("%d  ", Pcurrent->data);                   //打印现在结构体存储的值
 77         Pcurrent = Pcurrent->next;                      //将现在的指针往下一个点偏移。
 78     }
 79 }
 80 
 81 int main(){
 82     struct LinkNode* header=InputData();
 83     int n;
 84     cin>>n;
 85     int number;
 86     for(int i=0;i<n;i++){
 87         int number;
 88         cin>>number;
 89         if(number==0){
 90             int a,b;
 91             cin>>a>>b; 
 92             Insert(header,a,b);
 93         }
 94         else if(number==1){
 95             int c;
 96             cin>>c;
 97             DeleteNode(header,c);
 98         }
 99     }
100     Foreach_LinkNode(header); 
101 }