俩个基本插入方法
#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 ; //生成新结点scin>>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 ; //生成新结点scin>>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 < 1return 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;
}如何用数组模拟链表呢？
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总思路）
