（单）链表的一些较为复杂的操作：

默认前置：

#include
using namespace std;
#include//存放exit  
#include//OVERFLOW,exit#define MAXlength 100  //初始大小为100，可按需修改typedef int Status;         //函数调用状态struct K
{float a;int b;string c;
};
typedef K Elemtype;         //函数调用状态struct Lnode//node:结; 结点;
{Elemtype data;Lnode* next;
};
typedef Lnode* LinkList;

取第i个元素

project 1：（自己写的，凑合着也能用）

Status 取第i个元素(LinkList L, int i,Elemtype e)
{
if (链表是否为空(L))cerr << "链表为空" << endl;
if (i < 1)cerr << "i不对" << endl;LinkList p = L->next;int j = 0;while (p){if (i == j){e = p->data;break;}p = p->next;j++;}return true;
}

project 2：根据课程上写的（算法复杂度低一些，比较好用）

Status GetElem“i”(LinkList L, int i, Elemtype e)
{LinkList p;p = L->next;int j = 1;while (p && i > j){p = p->next;j++;}if (i<0 || idata;return true;
}

按值查找（查找其地址，以及是表中第几个元素（位置序号））

project 1:

Status 按值查找地址和位置序号(LinkList L,Elemtype e)
{LinkList p; int i=1;p = L->next;while (p){i++;if (e == p->data){cout << "地址为：  " << p << ";" << endl;cout << "位置序号为：  " << i <<";" << endl;}p = p->next;}//如果最后运行失败查找不到最后怎么返回ERROR?if (p = NULL)return NULL;return true; 
}

 但是要注意，如果要这么写的话，在类型K的声明里，还需要加上手撸判断表达式的定义：

struct K
{float a;int b;string c;bool operator==(K& t){return t.a == a && t.b == b;//&& t.c = c;}
};
typedef K Elemtype;         //函数调用状态

 project 2：根据课程上写的（算法复杂度低一些，比较好用）

Status LocateELem(LinkList L, Elemtype e)
{//在线性表L中查找值为e的数据元素//找到，则返回L中值为e的数据元素的地址，查找失败返回NULLauto p = L->next; int i=1;while (p && p->data != e){i++;if (e == p->data){cout << "地址为：  " << p << ";" << endl;cout << "位置序号为：  " << i << ";" << endl;}p = p->next;}if (p = NULL)return NULL;return true;
}

同理：

struct K
{float a;int b;string c;bool operator==(K& t){return t.a == a && t.b == b;//&& t.c = c;}bool operator!=(K& t){return t.a != a || t.b != b;//|| t.c = c;}
};
typedef K Elemtype;         //函数调用状态

插入（把元素e插到第i个位置结点上）

 project 1：

Status 插入(LinkList L,int i,Elemtype e)
{LinkList p,s; int j = 1;p = L->next;s->data = e;while (p)//&& j < i){ if (j == i-1){s->next = p->next;p->next = s;return true;}p = p->next;j++;}if (!p || j > i - 1)return false;//别忘了写插入非法时的情况
}

 project 2：根据课程上写的

Status Listlnsert(LinkList& L, int i, Elemtype e) 
{auto p = L; int j = 0;while (p && j < i - 1){ p = p->next; ++j; } if (!p ||j > i - 1)return false;auto s = new Lnode; s->data = e; s->next=p->next;p->next = s; return true;
}//Listlnsert_L

问题：（其实我觉得应该是一样的，只是把这个还没有确定的问题暂时先放在这里mark一下希望来日可以顺利解答）在这个算法里：

int j = 1；p = L->next;

auto p = L; int j = 0;

等价吗

删除（链表中第i个元素结点）

project 1：

Status 删除(LinkList& L, int i)
{LinkList p,s,q; int j=1;while (p&&jnext;j++;}s = p->next;q = s->next;delete s;p = q;return true;
}

project 2：

Status 删除(LinkList& L, int i)
{LinkList p, s; int j = 1;while (p && j < i - 1){p->next;j++;}s = (p->next)->next;delete p->next;p->next = s;return true;
}

project 3：根据视频（逻辑更严谨）

Status 删除(LinkList& L, int i)
{LinkList p,s; int j=1;while (p&&jnext;j++;}if (!p || j > i - 1)return false;s = p->next;s->next = p->next;//auto e = s->data;//何必保留这第i个结点的数据？？delete s;return true;
}

计算各操作的时间复杂度：