//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点,头结点是第0个结点(不存储数据)
while(p != NULL && j <i-1){//循环找到第i-1个结点
p = p->next;
j++;
}
if(p == NULL) //i值不合法
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s -> data = e;
s -> next = p -> next;
p -> next = s; //将结点s连接到p之后
return true; //插入成功
}
通过设置尾指针减少时间复杂度
LinkList List_TailInsert(LinkList &L){//正向建立单链表
int x; //设ElemType为整型
L = (LinkList)malloc(sizeof(LNode));//建立头结点
LNode *s,*r = L; //r为表尾指针
scanf("%d",&x); //输入结点的值
while(x != 9999){
s = (LNode *)malloc(sizeof(LNode));
s -> data = x;
r -> next = s;
scanf("%d",&x);
}
r -> next = NULL; //尾结点指针置空
return L;
}
(二)头插法
重要应用:链表的逆置
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode));//创建头结点
L -> next = NULL; //初始为空链表