【数据结构】实验二 单链表的基本操作

一、实验目的

1. 掌握线性表的链式存储结构的表示和实现方法。

2. 掌握链表基本操作的算法实现，以及对相应算法的性能分析。

二、实验内容

• 1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。
• 2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。
• 3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。
• 4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。

三、实验思路

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;
LinkList InitList(LinkList &l){l=new LNode;l->next=NULL;return l;
}
LinkList ListInsert(LinkList l,int i,int e){LNode *p;p=l;int j=0;while(p&&(j<i-1)){p=p->next;++j;}if(!p||j>i-1){printf("ERROR");return l;}LNode *s=new LNode ;s->data=e;s->next=p->next;p->next=s;return l;
}
LinkList ListDelete(LinkList l,int i){LNode *p=l;int j=0;while((p->next)&&(j<i-1)){p=p->next;++j;}if(!(p->next)||(j>i-1)){cout<<"ERROR"<<endl;}LNode *q=p->next;p->next=q->next;delete q;return l;
}
int LocateElem(LinkList l,int i){LNode *p=l->next;int j=0;while(p){j++;if(j==i){return p->data;}else{p=p->next;}}return 0;
}
void Print(LinkList l){LNode *p=l->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;
}
int main(){LinkList l;l=InitList(l);int e,i=0;cout<<"请输入一系列整数，以0标志结束"<<endl;while(scanf("%d",&e)&&e!=0){i++;l= ListInsert(l,i,e);}Print(l);cout<<"请在第i个元素之前插入一个值为x的元素"<<endl;int j,x;cin>>j>>x;l= ListInsert(l,j,x);Print(l);cout<<"请输入要删除的第i个元素"<<endl;cin>>j;l= ListDelete(l,j);Print(l);cout<<"请输入想要查找的第i个元素"<<endl;cin>>j;int h= LocateElem(l,j);if(h!=0){cout<<h;}else{cout<<"该元素不存在";}return 0;
}

运行结果：