#include <iostream>

using namespace std;

typedef struct LinkNode

{

    int elem;//节点中的数据

    struct  LinkNode *next;//节点中的后继指针

}LinkNode,*LinkList;//LinkList为结构体LinkNode的指针

//构造空的单链表L

void InitList(LinkList &L) {

    L = new LinkNode;//生成头节点

    L->next = NULL;//头节点的后继指针初始化为NULL

}

//单链表的输入(后插法)

void ListInput(LinkList &L) {

    int n = 0;//输入数据的个数

	LinkNode *r = L;//尾指针r指向头节点

    cout << "你想要输入几个数据？" << endl;

    cin >> n;

    for (int i = 0; i < n; i++) {

        LinkNode *node = new LinkNode;

        cout << "请输入第" << i + 1 << "个数据：";

        cin >> node->elem;

        node->next = NULL; r->next = node;//将新节点*p插入尾节点*r

		r = node;//r指向新的尾节点*p

    }

}

//单链表的输出

void ListOutput(LinkList &L) {

    cout << "顺序表的值依次为：";

    LinkNode* p;

    p = L->next;

    while (p!=NULL)

    {

        cout << p->elem<<"\t";

        p = p->next;

    }

}

//单链表的取值 i为取第几位值

int GetElem(LinkList &L, int i) {

    LinkList p = L->next;//p指向首元节点

    int countNum = 1;//计数器

    while (p!=NULL&&countNum<i)

    {

        p = p->next;

        countNum++;

    }

    if (p == NULL || countNum > i)//如果p为空或者计数大于i了则返回空

        return NULL;

    else

        return p->elem;

}

//单链表的查找 e为查找的值  返回元素的内存地址

LinkNode* LocateElem(LinkList &L, int e) {

    LinkNode *p = L->next;

    while (p&&p->elem!=e)

    {

        p = p->next;

    }

    return p;

}

//单链表的插入 i为插入的位置 e为插入的值

bool ListInsert(LinkList& L, int i, int e) {

    LinkList p = L;

    int j = 0;

    while (p!=NULL&&j<i-1)//将第i位的后继指针赋值给p

    {

        p = p->next; j++;

    }

    if (p == NULL||j>i-1) return false;

    LinkNode *s = new LinkNode;//生成新节点

    s->elem = e;//将e复制给节点s

    s->next = p->next;//先将p的后继指针赋值给新节点

    p->next = s;//再把p的后继指针改为新节点

    return true;

}

//单链表的删除 i为删除的位置

bool ListDelete(LinkList& L, int i) {

    LinkList p = L;

    int j = 0;

    while (p!=NULL&&j<i-1)

    {

        p = p->next; j++;

    }

    if (p == NULL || j > i - 1) return false;

    LinkNode* s = new LinkNode;

    s = p->next;//将第i-1位元素的内存地址赋值给s

    p->next = s->next;//改变第i位元素的后继指针

    delete s;//释放第i位元素的内存空间

    return true;

}

int main()

{

    LinkList LA;

	int opearateNum = 0;//操作值

	//初始化

	InitList(LA);

	while (true)

	{

		int selectIndex = 0;//增删查所用的索引

		int selectValue = 0;//增查所用的值

		cout << "1、输入顺序表\t2、输出顺序表\t3、取值\t4、查值\t5、插入\t6、删除\t7、退出" << endl;

		cin >> opearateNum;

		if (opearateNum == 7)

			break;

		switch (opearateNum)

		{

		case 1:

			//数据输入

			ListInput(LA);

			system("pause");

			system("cls");

			break;

		case 2:

			//输出顺序表

			ListOutput(LA);

			system("pause");

			system("cls");

			break;

		case 3:

			cout << "输入要取第几位：";

			cin >> selectIndex;

			if (GetElem(LA, selectIndex) == 0)

				cout << "没有第" << selectIndex << "位的值" << endl;

			else

				cout << "第" << selectIndex << "位的值：" << GetElem(LA, selectIndex) << endl;

			system("pause");

			system("cls");

			break;

		case 4:

			cout << "输入要查找的值：";

			cin >> selectValue;

			if (LocateElem(LA, selectValue) == 0)

				cout << "没有该值！" << endl;

			else

				cout << "值为" << selectValue << "的内存地址：" << LocateElem(LA, selectValue) << endl;

			system("pause");

			system("cls");

			break;

		case 5:

			cout << "输入要插入的位置和值(如：第2位插入值为4,输入：2 4)：";

			cin >> selectIndex >> selectValue;

			if (ListInsert(LA, selectIndex, selectValue))

				cout << "插入成功！" << endl;

			else

				cout << "插入失败！" << endl;

			system("pause");

			system("cls");

			break;

		case 6:

			cout << "输入要删除第几位：";

			cin >> selectIndex;

			if (ListDelete(LA, selectIndex))

				cout << "删除成功！" << endl;

			else

				cout << "删除失败！" << endl;

			system("pause");

			system("cls");

			break;

		case 7:

			break;

		default:

			cout << "无效操作，请重新输入！" << endl;

			break;

		}

	}

}