不带头结点单链表的基本操作

定义结点

typedef struct LNode{
	int data;			//每个节点存放一个数据元素
	struct LNode *next; //指针指向下一个节点
}LNode,*LinkList;   //LinkList等价于LNode *,前者强调链表，后者强调结点

初始化

//初始化一个空的单链表
bool InitList(LinkList &L){
	L = NULL;  //空表
	return true;
}

判空

//判断单链表是否为空
bool Empty(LinkList L){
	return (L==NULL);
}

求表的长度

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

按位序插入

//按位序插入（不带头结点）
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;
}

按位序删除

//按位序删除（不带头结点）
bool ListDelete(LinkList &L,int i,int &e){
	if(i<1)
		return false;
	if(i==1){
		LNode *r;
		r=L;
		e=r->data;
		L=r->next;
		free(r);
		return true;
	}
	LNode *p;
	int j=1;
	p=L;
	while (p!=NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL)
		return false;
	if(p->next==NULL)	//第i-1个结点之后已无结点
		return false;
	LNode *q=p->next;
	e = q->data;
	p->next=q->next;
	free(q);
	return true;
}

指定结点后插

//指定结点后插操作
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;
}

指定节点前插

//指定节点前插操作
bool InsertPriorNode(LNode *p,int 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连到p之后
	s->data = p->data;  //将p中元素复制到s中
	p->data = e;		//将p中元素覆盖为e
	return true;
}