要求： 1.编程实现单链表的以下基本操作：建立单链表，查找单链表，插入单链表，删除单链表。
2.采用单链表结构编程实现：两个有序单链表的归并运算。
#include <iostream> #include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef int Status; #define OK 1 #define ERROR 0 using namespace std; //定义单链表 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkedList; //单链表的初始化 Status InitList(LinkedList &L) { L= new LNode; L->next=NULL; return OK; } //尾插创建单链表 void CreatList_R(LinkedList &L,ElemType n) { L->next=NULL; LinkedList r=L; for(int i=0;i<n;i++) { LinkedList p=new LNode; cin>>p->data; p->next=NULL; r->next=p; r=p; } } /* //查找链表 LinkedList Getelem(LinkedList L,ElemType e) { LinkedList p; p=L->next; while(p&&p->data!=e) { p=p->next; } if(!p) { cout<<"该元素不存在"<<endl; return ERROR; } cout<<"该元素的地址为："<<p<<endl; return p; } */ //查找某位置的元素内容 Status GetElem_L(LinkedList L,int i,ElemType &e){ LinkedList p; p=L->next; int j; j=1; while(p&&j<i) { p=p->next; ++j; } if(!p||j>i) { cout<<"输入位置错误"<<endl; return ERROR; } e=p->data; cout<<"该位置元素为："<<e<<endl; return OK; } //插入链表 Status ListInsert(LinkedList &L,int i,ElemType e) { LinkedList p; p=L; int j=0; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) { cout<<"输入位置错误"<<endl; return ERROR; } LinkedList s; s=new LNode; s->data=e; s->next=p->next; p->next=s; return OK; } //删除元素 Status ListDelete(LinkedList &L,int i) { LinkedList p=L; int j=0; while(p&&j<i-1) { p=p->next; ++j; } if(!p||j>i-1) { cout<<"输入位置错误"<<endl; return ERROR; } LinkedList q=p->next; p->next=q->next; delete q; return OK; } //链表的归并 void MergeList(LinkedList L1,LinkedList L2,LinkedList &L3) { LinkedList p1,p2; p1=L1->next; p2=L2->next; int i=1; while(p1&&p2) { if(p1->data<p2->data) { ListInsert(L3,i,p1->data); p1=p1->next; } else { ListInsert(L3,i,p2->data); p2=p2->next; } i++; } while(p1) { ListInsert(L3,i,p1->data); p1=p1->next; i++; } while(p2) { ListInsert(L3,i,p2->data); p2=p2->next; i++; } } //输出链表 void GetList(LinkedList &L) { LinkedList p; p=L; while(p->next) { p=p->next; cout<<p->data<<" "; } cout<<endl; } int main() { cout<<"1----创建链表"<<endl; cout<<"2----归并链表"<<endl; cout<<"3----查找"<<endl; cout<<"4----插入"<<endl; cout<<"5----删除"<<endl; cout<<"输入负数退出程序"<<endl; LinkedList L1,L2,L3; InitList(L1); InitList(L2); InitList(L3); int i; bool flg=true; while(flg) { cout<<"请输入操作码："<<endl; cin>>i; if(i==1) { cout<<"输入第一个有序链表长度："<<endl; int n1; cin>>n1; cout<<"正序输入n个元素："<<endl; CreatList_R(L1,n1); cout<<"L1链表为："; GetList(L1); cout<<endl; cout<<"输入第二个有序链表长度："<<endl; int n2; cin>>n2; cout<<"正序输入n个元素："<<endl; CreatList_R(L2,n2); cout<<"L2链表为："; GetList(L2); } else if(i==2) { L3=new LNode; L3->next=NULL; MergeList(L1,L2,L3); cout<<"L1与L2归并结果链L3为： "; GetList(L3); } else if(i==3) { int e=0; cout<<"请输入要查找的链(n)："; int n; cin>>n; cout<<"请输入要查找的位置："; int i; cin>>i; switch(n) { case 1: GetElem_L(L1,i,e); break; case 2: GetElem_L(L2,i,e); break; case 3: GetElem_L(L3,i,e); break; } } else if(i==4) { cout<<"请输入要插入的链(n)："; int n; cin>>n; cout<<"请输入要插入的位置："; int i; cin>>i; cout<<"请输入要插入的元素："; int e; cin>>e; switch(n) { case 1: ListInsert(L1,i,e); cout<<"更新后的链表为："; GetList(L1); break; case 2: ListInsert(L2,i,e); cout<<"更新后的链表为："; GetList(L2); break; case 3: ListInsert(L3,i,e); cout<<"更新后的链表为："; GetList(L3); break; } } else if(i==5) { cout<<"请输入要删除的链(n)"; int n; cin>>n; cout<<"请输入要删除的位置"; int i; cin>>i; switch(n) { case 1: ListDelete(L1,i); cout<<"更新后的链表为："; GetList(L1); break; case 2: ListDelete(L2,i); cout<<"更新后的链表为："; GetList(L2); break; case 3: ListDelete(L3,i); cout<<"更新后的链表为："; GetList(L3); break; } } else{ flg=false; } } return 0; }