- /*
- *单链表的创建及操作
- */
- #include<iostream>
- #include "malloc.h"
- #include <stdio.h>
- #define ElemType int
- using namespace std;
- //定义线性表的单链表存储结构
- typedef struct Lnode{
- ElemType data;
- struct Lnode *next;
- }Lnode,*LinkList;
- enum Status
- {
- OK,FAILED,NULLHEAD
- };
- //单链表初始化
- LinkList LinkListInit()
- {
- LinkList head;
- head=(Lnode *)malloc(sizeof(Lnode));
- if(NULL==head)
- cout<<"申请空间失败!";
- head->next=NULL;
- head->data=0;
- return head;
- }
- //创建单链表,增加元素
- Status LinkList_Create(LinkList head,ElemType e)
- {
- LinkList q;
- q=head;
- while(q->next!=NULL)
- q=q->next;
- q->next=(Lnode *)malloc(sizeof(Lnode));
- q->next->data=e;
- q->next->next=NULL;
- head->data++;
- return OK;
- }
- //输出单链表中的元素
- Status LinkList_Cout(LinkList head)
- {
- if(NULL==head->next)
- {
- cout<<"您还没有向单链表中插入任何元素!"<<endl;
- return NULLHEAD;
- }
- LinkList p;
- p=head->next;
- while(NULL!=p->next)
- {
- cout<<p->data<<" ";
- p=p->next;
- }
- cout<<p->data<<endl;
- return OK;
- }
- //查找单链表中的第i个结点,并输出结点元素的值
- Status LinkList_Search(LinkList head,int i,ElemType *e)
- {
- if(NULL==head->next)
- {
- cout<<"您还没有向单链表中插入任何元素!"<<endl;
- return NULLHEAD;
- }
- if(i>head->data)
- {
- cout<<"请输入正确的范围!"<<endl;
- return FAILED;
- }
- LinkList p;
- p=head->next;
- while(i--!=1)
- {
- p=p->next;
- }
- *e=p->data;
- return OK;
- }
- //在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入)
- Status LinkList_Insert(LinkList head,int i,ElemType e)
- {
- if(NULL==head->next)
- {
- cout<<"您还没有向单链表中插入任何元素!"<<endl;
- return NULLHEAD;
- }
- if(i>head->data)
- {
- cout<<"请输入正确的范围!"<<endl;
- return FAILED;
- }
- LinkList p,q;
- p=head;
- while(i-->1)
- {
- p=p->next;
- }
- q=(Lnode *)malloc(sizeof(Lnode));
- q->next=p->next;
- q->data=e;
- p->next=q;
- head->data++;
- return OK;
- }
- //删除单链表中的第j个结点
- Status LinkList_Delete(LinkList head,int i,ElemType *e)
- {
- if(NULL==head->next)
- {
- cout<<"您还没有向单链表中插入任何元素!"<<endl;
- return NULLHEAD;
- }
- if(i>head->data)
- {
- cout<<"请输入正确的范围!"<<endl;
- return FAILED;
- }
- LinkList p,q;
- p=head;
- while(i-->1)
- {
- p=p->next;
- }
- q=p->next->next;
- *e=p->next->data;
- free(p->next);
- p->next=q;
- head->data--;
- return OK;
- }
- //将单链表中的各结点就地逆序(不允许另建一个链表)
- Status LinkList_Revorder(LinkList head)
- {
- if(NULL==head->next)
- {
- cout<<"您还没有向单链表中插入任何元素!"<<endl;
- return NULLHEAD;
- }
- if(1==head->data) return OK; //只有一个元素不需要逆序
- LinkList p,q,tmp;
- p=head->next;
- q=p->next;
- while(1)
- {
- if(NULL==q->next)//只剩下两个元素的时候q->next为NULL
- {
- q->next=p;
- break;
- }
- tmp=q->next;
- q->next=p;
- p=q;
- q=tmp;
- }
- head->next->next=NULL;
- head->next=q;
- return OK;
- }
- int main()
- {
- LinkList head=LinkListInit();
- int opt,n=0,m=0,i=0;
- ElemType e;
- while(1)
- {
- if(n)
- {
- while(getchar()!='\\n'&&getchar()!=' ');
- while(getchar()!='\\n'&&getchar()!=' ');
- }
- n=1;
- cout<<"************请输入您要进行的操作的编号************"<<endl<<endl;
- cout<<"1.创建一个带头结点的单链表(头指针为head),且遍历此链表(输出链表中各结点的值)"<<endl;
- cout<<"2.查找单链表中的第i个结点,并输出结点元素的值"<<endl;
- cout<<"3.在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入)"<<endl;
- cout<<"4.删除单链表中的第j个结点"<<endl;
- cout<<"5.将单链表中的各结点就地逆序(不允许另建一个链表)"<<endl;
- cout<<"6.输出单链表中的元素"<<endl;
- cout<<"7.退出"<<endl<<endl;
- cout<<"***************************************************"<<endl;
- cin>>opt;
- switch (opt)
- {
- case 1:
- cout<<"请输入您要创建的链表的节点个数"<<endl;
- cin>>m;
- for(int i=0;i<m;i++)
- {
- cin>>e;
- LinkList_Create(head,e);
- }
- cout<<"单链表创建成功!"<<endl;
- cout<<"此时的单链表为:";
- LinkList_Cout(head);
- break;
- case 2:
- cout<<"请输入要查找的元素位置i"<<endl;
- cin>>i;
- if(OK==LinkList_Search(head,i,&e))
- cout<<"您要查找的元素是: "<<e<<endl;
- break;
- case 3:
- cout<<"请输入要插入元素的位置和元素"<<endl;
- cout<<"位置:"<<endl;
- cin>>i;
- cout<<"元素"<<endl;
- cin>>e;
- if(OK==LinkList_Insert(head,i,e))
- cout<<"数据插入成功!"<<endl;
- cout<<"此时的单链表为:";
- LinkList_Cout(head);
- break;
- case 4:
- cout<<"请输入要删除的节点的位置"<<endl;
- cin>>i;
- if(OK==LinkList_Delete(head,i,&e))
- cout<<"元素"<<e<<"已经成功删除!"<<endl;
- cout<<"此时的单链表为:";
- LinkList_Cout(head);
- break;
- case 5:
- LinkList_Revorder(head);
- cout<<"逆序成功!"<<endl;
- cout<<"此时的单链表为:";
- LinkList_Cout(head);
- break;
- case 6:
- LinkList_Cout(head);
- break;
- case 7:
- return 0;
- default:
- cout<<"ERROR"<<endl;
- }
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/211020136520.html
来源: http://www.codesnippet.cn/detail/211020136520.html