链表的基本操作

注意事项

不带头头插和带头头插
不带头头插插入的每一次头都会改变
带头头插由于有头节点的存在每一次插入不会改变头节点的指针

定义

//结构体定义
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
//双链表结构 
typedef struct DNode{
	int data;
	struct DNode *next,*prior;
}DNode,*DLinkList; 

代码

单链表操作

//头插法(带头结点) 
LinkList List_HeadInsert(LinkList &L){
	LNode *s;int x;
	L = (LNode*)malloc(sizeof(LNode));
	L->data = -1;
	L->next = NULL;
	while(true){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
	} 
	return L;
}

//头插法不带头结点
LinkList List_HeadInsertWithoutHNode(LinkList &L){
	LNode *s,*p;int x;
	scanf("%d",&x);
	if(x==-1)return NULL;
	L = (LNode*)malloc(sizeof(LNode));
	L->data = x;
	L->next = NULL;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
	}
	return L;
} 

//尾插法带头结点
LinkList List_TailInsert(LinkList &L){
	LNode *s,*p;int x;
	L = (LNode*)malloc(sizeof(LNode));
	L->data = -1;
	p = L;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
	    s->next = NULL;
	    s->data = x;
	    p->next = s;
	    p = s;
	}
	return L;
} 

//尾插法不带头结点
LinkList List_TailInsertWithoutHNode(LinkList &L){
	LNode *s,*p;int x;
	scanf("%d",&x);
	if(x==-1)return NULL;
	L = (LNode*)malloc(sizeof(LNode));
	L->data = x;
	p = L;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = NULL;
		p->next = s;
		p = s;
	}
	return L;
} 

//创建带头结点的循环单链表(头插) 
LinkList create_xhd(LinkList &L){
	LNode *s;int x;
	L = (LNode*)malloc(sizeof(LNode));
	L->next = L;
	L->data = -1;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
	}
	return L;
} 

//创建不带头结点的循环单链表(头插) 
LinkList create_xhdw(LinkList &L){
	LNode *s;int x;
	scanf("%d",&x);
	if(x==-1) return NULL; 
	L = (LNode*)malloc(sizeof(LNode));
	L->next = L;
	L->data = x;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L;
		L = s;
	}
	return L;
} 

//创建带头结点的循环单链表(尾插) 
LinkList create_xhde(LinkList &L){
	LNode *s,*p;int x;
	L = (LNode*)malloc(sizeof(LNode));
	L->data = -1;
	L->next = NULL;
	p = L;
	while(1){
		scanf("%d",&x);
	    if(x == -1)break;
	    s = (LNode*)malloc(sizeof(LNode));
	    s->data = x;
	    s->next = NULL;
	    p->next = s;
	    p = s;
	}
	p->next = L;
	return L;
} 

//创建不带头结点的循环单链表(尾插) 
LinkList create_xhdew(LinkList &L){
	LNode *s,*p;int x;
	scanf("%d",&x);
	if(x==-1) return NULL; 
	L = (LNode*)malloc(sizeof(LNode));
	L->next = L;
	L->data = x;
	p = L;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = NULL;
		p->next = s;
		p=s;
	} 
	p->next = L;
	return L;
}

双链表操作

//创建带头节点的双链表（头插） 
LinkList create_slbdt(DLinkList &L){
	l = (DLNode*)malloc(sizeof(DLNode));
	DNode *s,*l;int x;
	l = L;
	l->data = -1;
	l->prior = NULL;
	l->next = NULL;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (DLNode*)malloc(sizeof(DLNode));
		s->next = l->next;
		s->data = x;
		s->prior = l;
		if(l->next!=NULL){
			l->next->prior = s;
		} 
		l->next = s;
	}
	return L;
} 

//创建不带头节点的双链表（头插） 
void create_slbbdt(DLinkList &L){
	DNode *s,*l;int x;
	scanf("%d",&x);
	if(x==-1)return NULL;
	l = L;
	l = (DLNode*)malloc(sizeof(DLNode));
	l->data = -1;
	l->prior = NULL;
	l->next = NULL;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (DLNode*)malloc(sizeof(DLNode));
		s->data = x;
		s->prior = NULL;
		s->next = l;
		//这步是否多余？ 
		l->prior = s;
		l = s;
	}
} 

//创建带头节点的双链表（尾插）  
void create_slbdtw(DLinkList &l){
	l = (DLNode*)malloc(sizeof(DLNode));
	DLNode *s,*p;int x;
	l->data = -1;
	l->prior = NULL;
	l->next = NULL;
	p=l;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (DLNode*)malloc(sizeof(DLNode));
		s->next = NULL;
		s->data = x;
		s->prior = p;
		p->next = s;
		p = s;
	}
} 

//创建不带头节点的双链表（尾插）  
void create_slbbdtw(DLinkList &l){
	DNode *s,*p;int x;
	scanf("%d",&x);
	if(x==-1)return NULL;
	l = (DLNode*)malloc(sizeof(DLNode));
	l->data = -1;
	l->prior = NULL;
	l->next = NULL;
	p=L;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (DLNode*)malloc(sizeof(DLNode));
		s->next = NULL;
		s->data = x;
		s->prior = p;
		p->next = s;
		p = s;
	}
} 

//创建带头节点的循环双链表（尾插）  
void create_slbdtwx(DLinkList &l){
	l = (DLNode*)malloc(sizeof(DLNode));
	DLNode *s,*p;int x;
	l->data = -1;
	l->prior = NULL;
	l->next = NULL;
	p=l;
	while(1){
		scanf("%d",&x);
		if(x==-1)break;
		s = (DLNode*)malloc(sizeof(DLNode));
		s->next = NULL;
		s->data = x;
		s->prior = p;
		p->next = s;
		p = s;
	}
	s->next = l;
	l->prior = s;
} 

打印与插入和删除

//链表打印(单链表且不循环)
void printList(LinkList L){
	while(L){
		printf("%d ",L->data);
		L = L->next;
	}
} 

//双链表打印
void printDList(DLinkList L){
	while(L){
		printf("%d ",L->data);
		L = L->next;
	}
} 

//循环双链表打印
void printXDList(DLinkList L){
	while(L){
		printf("%d ",L->data);
		L = L->next;
		if(L->data == -1)break; 
	}
} 
 
//删除单链表中指定位置的元素(无头节点的单链表)
void deletelinklist(LinkList &L,int i){
	LNode *p=L->next,*a;int k=1;
	while(++k<i-1 && p){ 
		p = p->next;
	}
	a = p->next;
	p->next = p->next->next;
	free(a);
} 
//指定位置插入结点(无头节点的单链表)
bool InsertNode(LinkList &L,LinkList &node,int k){
	LinkList p=L;int i=1;
	while(p && i<k-1){
		p = p->next;
		i++;
	}
	//找不到前一个结点，给定K值超出链长，插入失败 
	if(i!=k-1)return false;
	node->next = p->next;
	p->next = node;
	return true;
}