数据结构_链表基本操作的实现_代码_例题

一、基本操作实现

1.按位序插入（带头节点）

2.按位序插入（不带头节点）

3.指定结点的后插操作

4.指定结点的前插操作

5.按位序删除（带头节点）

6.指定结点的删除

7.按位查找，返回第i个元素（带头结点）

8.按值查找

9.求表的长度

10.尾插法建立单链表

11.头插法建立单链表（可用于链表的逆置） 

二、例题

1.有序链表的合并，不允许有重复数据

---

一、基本操作实现

1.按位序插入（带头节点）

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
 
//按位序插入（带头节点）
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	LNode *p;	//指针p指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;	//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;
} 

2.按位序插入（不带头节点）

//按位序插入（不带头节点）
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1) return false;
	if (i == 1){	//插入第1个结点的操作与其他结点不一样 
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	} 
	LNode *p;	//指针p指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;	//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;
} 

3.指定结点的后插操作

//指定结点的后插操作
bool InsertNextNode(LNode *p,ElemType 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;
} 

4.指定结点的前插操作

思路：先后插将位置占住，然后再交换前后两个的结点的data。

//指定结点的前插操作
bool InsertNextNode(LNode *p,ElemType e){
	if (p == NULL) return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if (s == NULL) return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e; 
	return true;
} 

5.按位序删除（带头节点）

//按位序删除（带头节点）
bool ListDelet(LinkList &L,int i,ElemType &e){
	if(i<1) return false;
	LNode *p;	//指针p指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;	//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;	//用e返回删除元素的值 
	p->next = q->next;
	free(q);
	return true;
} 

6.指定结点的删除

//指定结点的删除
bool DeletNode(LNode *p){
	if (p == NULL) return false;
	LNode *q = p->next;
	p->data = p->next->data;
	p->next = q->next;
	free(q);
	return true;
} 

7.按位查找，返回第i个元素（带头结点）

//按位查找，返回第i个元素（带头结点）
LNode * GetElem(LinkList L,int i){
	if(i<0) return NULL;
	LNode *p;
	int j = 0;
	p = L;
	while(p != NULL && j<i){
		p = p->next;
		j++;
	}
	return p;
} 

8.按值查找

//按值查找
LNode * LocateElem(LinkList L,ElemType e){
	LNode *p = L->next;
	while(p != NULL && p->data != e){
		p = p->next;
	}
	return p;
} 

9.求表的长度

//求表的长度
int Length(LinkList L){
	int len = 0;
	LNode *p = L;
	while(p->next != NULL){
		p = p->next;
		len ++;
	}
	return len;
} 

10.尾插法建立单链表

//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r = L;
	scanf("%d",&x);
	while(x != 9999){
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d",&x);
	}
	r->next = NULL;
	return L;
}

11.头插法建立单链表（可用于链表的逆置） 

//头插法建立单链表（可用于链表的逆置） 
LinkList List_HeadInsert(LinkList &L){
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;	//初始为空链表 
	scanf("%d",&x);
	while(x != 9999){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d",&x);
	}
	return L;
} 

二、例题

1.有序链表的合并，不允许有重复数据

#include<stdio.h>
#include<stdlib.h>
 
typedef struct LNode{
	int data;
	struct LNode *next;
}LNode,*LinkList;
 
//尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r = L;
	scanf("%d",&x);
	while(x != 9999){
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d",&x);
	}
	r->next = NULL;
	return L;
}
 
void ListPrint(LinkList L){
	LNode *p;
	p = L->next;
	while(p != NULL){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}
 
void MergeList_L(LinkList &LA,LinkList &LB,LinkList &LC){
	LNode *pa,*pb,*pc;
	pa = LA->next;
	pb = LB->next;
	LC = LA;
	pc = LC;
	while(pa && pb){
		if(pa->data < pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else if(pa->data > pb->data){
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
		//这里解决了不允许有重复数据的要求 
		else{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			pb = pb->next;
		}
	}
	pc->next = pa?pa:pb;
	delete LB;
}
 
int main(){
	LinkList LA,LB,LC;
	List_TailInsert(LA);
	ListPrint(LA);
	List_TailInsert(LB);
	ListPrint(LB);
	MergeList_L(LA,LB,LC);
	ListPrint(LC);
	return 0;
}