数据结构之单链表的插入删除操作

1.插入操作(注意审题)

注意: 按位序插入是找到第i个位置的前一个节点的后面插入, 要看清楚是否存在头节点

1.1 按位序插入带头结点(平均时间复杂度为O(n))

ListInsert(&L, i, e) : 插入操作. 在表L中的第i个位置插入指定的元素e
即先找到第 i-1 个节点,然后在其后面插入新的节点

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, int e){
	if(i<1)
		return false;
	LNode *p;
	int j = 0;
	p = L;
	while(p!= NULL && j< i-1){
		p = p->next;
		j++;
	} 
	if(p ==NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

1.2 按位序插入不带头节点(平均时间复杂度为O(n))

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LinkList &L, int i, int e){
	if(i<1)
		return false;
	if(i ==1){
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode *p;
	int j = 1;
	p = L;
	while(p!= NULL && j< i-1){
		p = p->next;
		j++;
	} 
	if(p ==NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

1.3 指定节点的后插操作(时间复杂度 O(1))

InsertNextNode(LNode *p, ElemType e)

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LNode *p, int e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL){
		return false;
	}
	s->data =e;
	s->next =p->next;
	p->next = s;
	return true;
}

1.4 指定节点的前插操作

1.4.1 第一种方式(找前驱节点,平均时间复杂度为O(n))

InsertPriorNode(**LinkList L**, LNode *p, ElemType e):
  相比于后插操作,还需要传入头节点,然后遍历找到前驱节点,然后在这个前驱节点后面插入(平均时间复杂度为O(n))

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
// 带头结点
bool ListInsert(LinkList L,LNode *p, int e){
	if(p == NULL || L==NULL)
		return false;
	LNode *k = L; 
	do{
		k = k->next;	  //k 是 p的前驱节点 
	} while(k->next != p)
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL){
		return false;
	}	
	s->data =e;
	s->next =k->next;
	k->next = s;
	return true;
}

1.4.2 第二种方式(仍然使用后插操作,然后交换节点数据, 时间复杂度为O(1))

InsertPriorNode(LNode *p, ElemType e)

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListInsert(LNode *p, int e){
	if(p == NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL){
		return false;
	}
	s->data =p->data;
	p->data = e;
	s->next =p->next;
	p->next = s;
	return true;
}

2.删除操作

2.1 位序删除(带头节点)(平均时间复杂度O(n))

ListDelete(&L, i, &e): 删除L中的第i个位置的节点,并且用e返回删除节点元素的值

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListDelete(LinkList &L,int i, int &e){
	if(i<1)
		return false;
	int j = 0; //表示当前指向的是 第几个节点
	LNode *p = L;  //找到删除节点的前驱节点 
	while(p!=NULL && j< i-1) {
		p = p->next;
		j++;
	}
	if(p==NULL)
		return false;
	if(p->next == NULL)
		return false; 
	LNode *q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

2.2 指定节点的删除

同指定节点的前插操作类似,有两种实现方式,但是要注意: 当使用交换数据的方式时,若删除的是最后一个节点元素,则会出错.

2.2.1 第一种时间复杂度为O(n)

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool ListDelete(LinkList &L,LNode *q, int &e){
	if(L == NULL)
		return false;
	if(q == NULL)
		return false;
	LNode *p = L; 
	do{
		p = p->next;
	}while(p->next != q);
	
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

2.2.2 第二种时间复杂度为O(1)

若删除的是最后一个节点元素,则会出错, 因为是最后一个节点的时候, p->next 是NULL, 下面第 12 行出错

#include<stdio.h>
#include<stdlib.h>

typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;

bool DeleteNode(LNode *p, int &e){
	if(p ==NULL)
		return false;
	LNode *q = p->next; 
	e = p->data;
	p->data = p->next->data;
	p->next = q->next;

	free(q);
	return true;
}