526互联

带头节点单链表的基本操作

发布时间 2023-04-18 18:18:33作者: stuzhang

结点结构定义

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

第3行是结构体的自引用。如果要让结构体的成员还是结构体，则需要将结构体变量变为指针变量，解决无法计算结构体大小的问题。

第4行中*LinkList强调定义的是某个单链表的头指针；LNode强调的是指向单链表中任意结点的指针变量。LinkList L和LNode *p是等价的。

初始化

bool LinkListInit(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));	//为头结点分配内存空间
	if(L==NULL) return false;	//创建头结点失败
	L->next=NULL;
	return true;
}

molloc函数的作用是分配指定长度字节的内存块。如果分配成功返回指针，指向被分配的内存的地址；否则返回空指针NULL。其返回的是不确定类型的指针，所以在返回前需要做强制类型转换。若第2行执行成功，L就是指向被分配的这块内存的指针。

注意

LinkList L相当于LNode *L，L不是一个LNode型的变量，而是一个被定义为指向LNode变量的指针，但是在这里只是定义了一个指针L而没有让其指向任何地方，所以当前L指向的是NULL。

这段程序的主要作用就是：在内存中为头结点分配一块长度为LNode.size字节的空间，使得L指向这一地址。当我们调用L的时候，实际上就是访问头结点。所以第4行L->next是访问头结点的next指针域，使其指向的下一结点的地址为空，即这个单链表中只有头指针和头结点。

创建单链表

头插法

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; 
}

每次在头结点之后插入新的结点，即先插入的结点在后面，后插入的结点在前面。

过程：为新结点输入新结点的数据域，将新节点的指针域指向头结点的下一结点，然后将头结点的指针域指向该新结点。

尾插法

LinkList List_TailInsert(LinkList &L){
 	int x;
 	L=(LinkList)malloc(sizeof(LNode));	//因为最后会指向NULL，这里不用初始化
 	LNode *s,*p=L;	//*p始终为该单链表最后一个结点
 	scanf("%d",&x);
 	while(x!=9999){
 		s=(LNode*)malloc(sizeof(LNode));
 		s->data=x;
		p->next=s;
		p=s;
		scanf("%d",&x);
	}
 	p->next=NULL;	//直接对最后一个结点操作，而省略了循环中的s->next=NULL
 	return L;
}

因为前插法始终都是在头结点后面插入新的结点，而尾插法是在链表的最后一个结点之后插入新的结点，所以需要定义一个结点来表示一次插入完成后该链表的最后一个结点，即上一次插入的结点。

注意

若传入的参数带&地址符，该函数会直接对内存中这个位置的单链表进行操作，不能直接使用L=L->next，否则会对该单链表的头指针L进行修改，使其指向另一个更短的单链表。

查找

按位查找

LNode* GetElem(LinkList L,int i){
	if(i<0) return NULL;
	LNode *p=L;
	int j=0;
	while(p!=NULL&&j<i){
		p=p->next;
		j++;
	}
	return p;
}

若i<0或i超过单链表最后一个结点的位置，返回NULL；若i=0，返回头结点；其余返回第i个位置的结点。

按值查找

LNode* LocateElem(LinkList L,int e){
	LNode *p=L->next;	//头结点没有值，从首元结点开始查找
	while(p!=NULL&&p->data!=e)
		p=p->next;
	return p;
}

若单链表中没有元素值为e，则返回NULL。

插入

定点前插

在p结点之前插入元素e。

bool InsertPriorNode(LNode *p,int e){
	if(p==NULL) return false;	//*p不能是头结点
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL) return false;
	s->next=p->next;
	p->next=s;
	s->data=p->data;	//7、8行交换数据域
	p->data=e;
	return true;
}

因为单链表无法获取一个结点之前的结点，所以我们需要将新结点插入到p结点之后，然后交换两个结点的数据域。

定点后插

在p结点之后插入元素e。

bool InsertNextNode(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;
}

定位插入

将值为e的新结点插入到第i个位置，即插入到第i-1个结点后面，即定点后插。

bool PositionInsert(LinkList &L,int i,int e){
	if(i<1) return false;		//第i-1个结点最小只能是头结点，即第0个结点
	LNode *p=GetElem(L,i-1);	//查找第i-1个结点
	return InsertNextNode(p,e);	//在第i-1个结点后插入新结点
}

如果单链表中有n个结点（不含头结点），则1<=i<=n+1，有n+1个合法的插入位置。例如，一个单链表中只有2个结点，则可以在第1、2、3个位置插入。第1个位置即在头结点之后、表头插入；第2个位置即在第一个结点之后、第2个结点之前插入；第3个位置即在第2个结点、表尾插入。所以，当i=n+1时，新结点插在链表尾部。

定位插入操作用定点后插比定点前插合适。定点前插是在第i个结点之前插入新结点，其实质是在第i个结点后面插入一个新结点，然后交换两个结点的元素值，所以其只能在最后一个结点之前插入新结点，而不能在链表的末尾插入。

上面的插入操作中i的位置只能在1到n+1之间，当我们进行插入操作时，还要先知道链表的长度，较为麻烦。我一开始的思路是：当输入i的值大于n+1时，不论i有多大，始终将新结点插入到链表尾部。实现思路如下：

bool ListInsert(LinkList &L,int i,int e){
	if(i<1) return false;
	LNode *p=L;
	int j=0;
	while(p->next!=NULL&&j<i){	//此处改变
		p=p->next;
		j++;
	}
	return InsertNextNode(p,e);
}

若i的值大于n+1，始终使p指向链表的最后一个结点，而不是像之前使p指向NULL。

删除

定位删除

删除第i个结点。

bool ListDelete(LinkList &L,int i,int &e){	//e存放删除的结点的值，可不加
	LNode *p=GetElem(L,i-1);	//获取被删结点的前一个结点 
	if(p==NULL) return false;
	if(p->next==NULL) return false;	//被删结点不存在
	LNode *q=p->next;	//q指向被删除的结点 
	p->next=q->next; 	//将q从链中断开 
	e=q->data;
	free(q);	//释放该删除结点的内存
	return true;
}

求表长

int ListLength(LinkList L){
	int len=0;
	LNode *p=L;
	while(p->next!=NULL){
		p=p->next;
		len++;
	}
    return len;
}

判空

bool isEmpty(LinkList L){
	if(L->next==NULL) return true;
	return false;
}

逆置

头插法逆置

创建一个新链表复制原链表，然后将原链表初始化。之后依次获取新链表中的每个结点（不含头结点），通过头插法使得原链表逆置。

void ListReverse(LinkList &L){
	LNode *p=L->next;	//p指向原链表中第一个结点
	LNode *s;
	L->next=NULL;	//原链表初始化
	while(p!=NULL){
		s=p;	
		p=p->next;
		s->next=L->next;	//*s结点指针域改为头结点指针域
		L->next=s; 	//头结点指向*s结点
	} 
}

就地逆置

void ListReverse2(LinkList &L){
	if(L->next==NULL) return;	//链表为空直接结束
	LNode *q=L,*p=L->next,*temp;
	while(p!=NULL){
		q->data=p->data;	//将当前结点的值赋给上一结点
		temp=p->next;	//当p的next修改后，获取不到下一个结点，所以用temp提前存储p的下一结点
		p->next=q;	//p反向指向q 
		q=p;
		p=temp;
	}
	q->data=0;	//最后一个结点变为头结点
	L=q; 
}

打印

void PrintLinkList(LinkList L){
	LinkList p;
	p=L->next;
	if(p==NULL) printf("The LinkList is null!");	//判断是否为空链表
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}