俩个基本插入方法
#include <bits/stdc .h>
using namespace std;
typedef struct LNode
{
int date; //节点的数据域
struct LNode *next; //节点的指针域
}LNode,*LinkList; // LinkList 为指向结构体LNode的指针类型
bool Initlist_L(LinkList &L) //构造一个空的单链表L
{
L = new LNode; //生成新的节点作为头结点，用头指针L指向头结点
if(!L)
return false; //生成结点失败
L->next = NULL; // 头结点指针域置空
return true;
}
void CreateList_H(LinkList &L) //前插法创造单链表 （是逆序建表）
{
//输入n个元素，建立到头结点的单链表
int n ;
LinkList s; //定义一个指针变量
L = new LNode;
L ->next = NULL; //先建立一个带头结点的空链表
while(n--)
{
s = new LNode ; //生成新结点s
cin>>s->date; //输入元素赋值给新结点的数据域
s->next = L->next;
L->next = s; //将新结点s插入头结点之后
}
}
void CreateList_R(LinkList &L) //尾插法创建单链表 （尾插法是正序建表）
{
//输入n个元素，建立到头结点的单链表
int n ;
LinkList s, r;
L = new LNode;
L->next = NULL; //先建立一个带头结点的空链表
r = L; //尾指针r指向头结点 （就他自己）
cout<<"请输入元素个数 n: "<<endl;
cin>>n;
cout<<"请依次输入n个元素："<<endl;
cout<<"前插法创建单链表..."<<endl;
while(n--)
{
s = new LNode ; //生成新结点s
cin>>s->date; //输入元素赋值给新结点的数据域
s->next = NULL;
r->next = s; //将新结点插s插入尾结点*r之后
r = s; //r指向新的尾结点s
}
}
bool GetELem_L(LinkList L,int i, int &e) //单链表的取值（按第几位查找）
{
//在头节点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j;
LinkList p;
p = L-> next; //p指向第一个结点
j = 1; //j相当于计数器
while(j < i && p) //顺链域向后扫描，直到p指向第i个元素或者p为空
{
p = p->next; //p指向下一个结点
j ;
}
if(!p || j > i)
return false; //i不合法i>n或 i <= 0;
e = p -> date; //取第i个结点的数据域
return true;
}
bool LocatELem_L(LinkList L ,int e) //按值查找
{
//在头节点的单链表l中查找值为e的元素
LinkList p ;
p = L-> next;
while(p && p->date != e)
p = p->next; //p指向下一个结点
if(!p)
return false; //查找失败p为NULL
return true;
}
bool ListInsert_L(LinkList &L,int i,int e) //单链表的插入
{
int j;
LinkList p,s;
p = L;
j = 0;
while(p && j < i - 1) //查找第i-1个结点，p指向该结点
{
p = p->next;
j ;
}
if(!p || j > i - 1) // i > n 1或者 i < 1
return false ;
s = new LNode; //生成新的节点
s->date = e; //将新的节点指针域置为e
s->next = p->next;
p->next = s;
return true;
}
bool ListDelete_L(LinkList &L,int i) //单链表的删除
{
LinkList p,q;
int j = 0;
p = L;
while((p->next) && (j< i -1)) //p的下一个结点存在才能删除
{
p = p->next;
j ;
}
if(!(p->next) || (j > i - 1)) //当i > n 或i < 1时删除位置不合理
return false;
q = p->next;;
p->next = q->next;
delete q;
return true;
}
void listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p = L->next;
while(p)
{
cout<<p->date<<"t";
p = p->next;
}
cout<<endl;
}如何用数组模拟链表呢？
代码语言：javascript复制int e[N],ne[N],idx,head;
void init() //初始化
{
head = -1;
}
void int_to_head(int x) //在头节点后插入
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx ;
}
void add(int k,int x) //在第k个结点后面操作
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx ;
}
void remove(int k) //删除第k个结点
{
ne[k]=ne[ne[k]];
}（这个来自acwing y总思路）
