#include<iostream> using namespace std; #include<string> typedef int Status; #define OK 1 #define ERROR 0 #define ElemType int typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; Status InitList_L(LinkList &L){ L=new LNode; L->next=NULL; return OK; } Status DestroyList_L(LinkList &L){ LinkList p; while(L) { p=L; L=L->next; delete p; } return OK; } Status ClearList(LinkList & L){ // 将L重置为空表 LinkList p,q; p=L->next; //p指向第一个结点 while(p) //没到表尾 { q=p->next; delete p; p=q; } L->next=NULL; //头结点指针域为空 return OK; } int ListLength_L(LinkList L){ //返回L中数据元素个数 LinkList p; p=L->next; //p指向第一个结点 int i=0; while(p){ //遍历单链表,统计结点数 i++; p=p->next; } return i; } int ListEmpty(LinkList L){ //若L为空表,则返回1,否则返回0 if(L->next) //非空 return 0; else return 1; } Status GetElem_L(LinkList L,int i,ElemType &e){ LinkList p=L; p=L->next; int j=1; //初始化 while(p&&j<i){ //向后扫描,直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p || j>i)return ERROR; //第i个元素不存在 e=p->data; //取第i个元素 return OK; } LNode *LocateElem(LinkList L,ElemType e) { LNode *p=L; while(p&&(p->data!=e)) { p=p->next; } return p; } Status ListInsert_L(LinkList &L,int i,ElemType e){ LinkList p; LNode* s; p=L; int j=0; while(p&&j<i-1){p=p->next;++j;} //寻找第i−1个结点 if(!p||j>i-1)return ERROR; //i大于表长 + 1或者小于1 s=new LNode; //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; } Status ListDelete_L(LinkList &L,int i,ElemType &e){ LinkList p; LinkList q; p=L;int j=0; while(p->next &&j<i-1){//寻找第i-1个结点,并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; } //遍历输出函数 void PrintList(LinkList L) { LinkList p=L->next;//跳过头结点 if(ListLength_L(L)) { printf("当前单链表所有元素:"); while(p) { printf("%d ",p->data); p=p->next; } printf(" "); } else { printf("当前单链表已空! "); } } int main() { int i; LinkList L;int mount; ElemType e=0; InitList_L(L); for(;;) { cout<<"遍历0,查询请输入1,查找输入2,插入输入3,删除输入4,退出输入5"<<endl; cin>>mount; switch(mount) { case 0: PrintList(L); break; case 1: cout<<"请输入你想获取第几个的数据"<<endl; cin>>i; GetElem_L(L,i,e); cout<<"其数据为:"<<e;break; case 2: cout<<"请输入你想查找的数据"<<endl; cin>>e; if(LocateElem(L,e)!=NULL) { cout<<"该数在第"<<LocateElem(L,e)<<"个"<<endl; } break; case 3: cout<<"请输入你想要插入到第几个位置"<<endl; cin>>i; cout<<"输入插入的数值为:"; cin>>e; ListInsert_L(L,i,e); break; case 4: cout<<"请输入你想删除第几个数据"<<endl; cin>>i; ListDelete_L(L,i,e); cout<<"删除的数据为"<<e<<endl; break; } if(mount==5) break; } }