实验一 单链表实验(一) 实验目的1. 理解线性表的链式存储结构2. 熟练掌握动态链表结构及有关算法的设计3. 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法二) 实验任务编写算法实现下列问题的求解1. 求链表中第i个结点的指针（函数），若不存在，则返回NULL2. 在第i个结点前插入值为x的结点3. 删除链表中第i个元素结点4. 在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性5. 将单链表L中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果6. 求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3三) 主要仪器设备PC机，Windows操作平台，Visual C++(四) 实验分析顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法(五) 源程序头文件 文件名：linklist.h#includeusing namespace std;struct node{ int data; node *next;};class list{public: list(); int length()const { return count; //求链表长度 } ~list(); void create(); //链表构建，以0为结束标志 void output(); //链表输出 int get_element(const int i)const; //按序号取元素 node *locate(const int x) const; //搜索对应元素 int insert(const int i,const int x); //插入对应元素 int delete_element(const int i); //删除对应元素 node *get_head() { return head; //读取头指针 } void insert2(const int x); friend void SplitList(list L1, list&L2, list &L3); friend void get_public(list L1, list L2, list &L3);private: int count; node *head;};list::list(){ head=new node; head->next=NULL; count=0;}void list::create() //链表构建，以0为结束标志{ int x; cout<<"请输入当前链表，以0为结束符。
\n"; cin>>x; node *rear=head; while(x!=0) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; }}void list::output(){ node *p=head->next; cout<<"******Top of this list******"<data<<" "; p=p->next; } cout<next; j=1; while(p!=NULL && j!=i) { p=p->next; j++; } if(p==NULL) return 0; else { return x=p->data; return 1; }}node *list::locate(const int x)const{ node *p=head->next; while(p!=NULL) if(p->data==x)return p; else p=p->next; return NULL;}int list::insert(const int i,const int x) //实验2{ node *p=head; int j=0; while(j!=i-1&&p!=NULL) { p=p->next; j++; } if(i<1||i>count+1) return 0; node *s=new node; s->data=x; s->next=p->next; p->next=s; count++; return 1;}int list::delete_element(const int i) //实验3{ node *p=head; int j=0; while(j!=i-1&&p!=NULL) { p=p->next; j++; } if(i<1||i>count) return 0; node *u=p->next; p->next=u->next; delete u; count--; return 1;}void list::insert2(const int x) //实验4{ node* p,*q; p=head; while(p->next!=NULL && p->next->datanext; if (p->next==NULL || p->next->data>x) { q=new node; q->data=x; q->next=p->next; p->next=q; count++; }}list::~list(){ while(head->next!=NULL) delete_element(1);}主程序#include #include"linklist.h"using namespace std;void SplitList(list L1, list&L2, list &L3){ node *p1= L1.head->next; for(int i = 1; p1 != NULL; i++) { if(i % 2) L2.insert(L2.count+1,p1->data); else L3.insert(L3.count+1,p1->data); p1=p1->next; } L1.output(); L2.output(); L3.output();}void get_public(list L1,list L2,list &L3){ node *p1=L1.head->next, *p2=L2.head->next; while (p1!=NULL && p2!=NULL) if (p1->datadata) p1=p1->next; else if (p1->data>p2->data) p2=p2->next; else { L3.insert(L3.count+1,p1->data); p1=p1->next; p2=p2->next; }}int main(){ { list L1; int i,x; cout<<"当前为实验1、2、3"; L1.create(); cout<<"输入i求第i个结点"; cin>>i; cout<>x>>i; L1.insert(i,x); L1.output(); cout<<"输入i删除第i个结点"; cin>>i; L1.delete_element(i); L1.output(); } { list L1; int x; cout<<"实验4，输入递增有序的L"; L1.create(); cout<<"输入x插入后仍有序"; cin>>x; L1.insert2(x); L1.output(); } { list L1,L2,L3; cout<<"当前为实验5，单链表L奇数、偶数项分开"; L1.create(); SplitList(L1,L2,L3); }{ list L1,L2,L3; cout<<"当前为实验6，求L1与L2公共元素"; L1.create(); L2.create(); get_public(L1,L2,L3); L3.output(); } return 0;}(六)。
