数据结构 ——单链表【c语言版】_输出链表第i至第j个结点间的所有结点

线性表：具有相同特性的数据元素（既同类型数据）的一个有限序列.

注：同一线性表中的元素必定具有相同特性

线性表的特性：1.有穷性 2.一致性  3.序列性

线性表的最本质特征：有唯一的前驱和后继

线性表的链式存储结构称为链表

链式存储：逻辑上相邻的数据元素，物理上不一定相邻
 

在单链表中，假设每个节点的类型用SLinkList表示，它包括存储元素的数据域（data），其类型用通用类型标识符ElemType表示，还包括存储后继节点位置的指针域（next）。SLinkList类型声明如下

typedef int ElemType;
 
typedef struct Node
{
	ElemType data;//存储线性表的元素值（1个） 
	struct Node *next;//存储后继元素节点的地址 
}SLinkList;

在链表中建立了一个头节点，方便统一空表与非空表的处理过程

为了方便操作，特别地加了一个头节点进来，类型和普通节点一样
data：不用 
next：存储第1个元素节点的地址

1）初始化线性表 

          构造一个空的单链表，并建立一个头节点

SLinkList *InitList()
{
	SLinkList *h;
	h=(SLinkList *)malloc(sizeof(SLinkList));
	h->next=NULL;
	return h;
}

单链表为空条件：h ->next ==NULL

初始化链表的时间复杂度为O(1)

2）销毁单链表

        链表中，销毁元素后需要释放内存

        销毁链表时，需要判断链表是否非空，以确保操作合法性

        这里我们调用删除（ListDelete(SLinkList *h,int i,ElemType *e)）来逐一删除链表中的元素

void DestroyList(SLinkList *h)
{
	int ListDelete(SLinkList *h,int i,ElemType *e);
	ElemType v;
	
	while(h->next!=NULL)//不空
	{
		//删除第1个元素节点
		ListDelete(h,1,&v); 
	} 
	free(h);
} 

销毁链表的时间复杂度为O(n)

3）判断链表是否为空

        链表为空的条件 ：h->next == NULL

ListEmpty(SLinkList *h)
{
	if(h->next==NULL)
	{
		return 1;
	} 
	else
	{
		return 0;
	}
} 

或者也可以直接return返回，若为空返回真，否则返回假

​
ListEmpty(SLinkList *h)
{
	return (h->next == NULL)  //为空返回True，非空返回False 
} 
 
​

判断链表是否为空的时间复杂度为O(1)

4）求链表长度

        创建一个p，刚开始p指向头节点，此时链表长度len==0，只要 p->next不等于NULL，则让p指向下一个节点，len也加1，当循环结束时，len值就是链表长度

int ListLength(SLinkList *h)
{
	SLinkList *p;
	int len;
	p=h;
	len=0;
	while(p->next!=NULL)
	{
		p=p->next;
		len=len+1;
	} 
	return len;
} 

求链表长度的时间复杂度为O(n)

5）输出链表

void DispList(SLinkList *h)
{
	SLinkList *p;
	p=h; 
	printf("线性表的元素为：");
	while(p->next!=NULL)
	{
		p=p->next;
		printf("%d ",p->data); 
	} 
	printf("\n");
}

输出链表的时间复杂度也为O(n)

6）获取链表中的某一元素值

        取值时，要判断取得值是否为链表的范围内，这里可以调用ListLength(SLinkList *h)来判断参数合法性

/*
 
参数合法：i>=1 && i<=ListLength(h)
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int GetElem(SLinkList *h,int i,ElemType *e)
{
	SLinkList *p;
	int j;
	
	if(i>=1 && i<=ListLength(h))
	{
		p=h;
		for(j=1;j<=i;j++)
		{
			p=p->next;
		} 
		*e=p->data;
		return 1;
	} 
	else
	{
		printf("参数错误！\n");
		return 0;
	}	
}

链表中取某一值的时间复杂度也为O(n)

7）查找

        查找链表中是否存在某个元素e

int LocateElem(SLinkList *h,ElemType e)
{
	SLinkList *p;
	int len;
	p=h;
	len=0;
	while(p->next!=NULL)
	{
		p=p->next;
		len=len+1;
		if(p->data==e)
		{
			return len;
		}
	} 
	return 0;
} 

查找某一元素的时间复杂度也为O(n),它需要从头开始找

8）插入

        插入也就是添加元素，可以在链表头结点与首结点之间插入元素（头插法），也可以在尾结点之后插入元素（尾插法），甚至可以在链表中任意位置插入元素

此处我们会涉及到头插法与尾插法，但是我会主要讲解任意位置插入的方法

头插法的主要步骤如下：

s->next = h->next;
h->next = s;

尾插法的主要步骤如下:

r->next = s;  //r为尾指针
r =s;

单链表插入结点时，需要先找他第i-1个结点，让p指向它，再将新结点q插入,代码如下：

/*
参数合法：i>=1 && i<=ListLength(h)+1
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int ListInsert(SLinkList *h,int i,ElemType e)
{
	SLinkList *p,*q;
	int j;
	
	if(i>=1 && i<=ListLength(h)+1)
	{
		//1.构造一个节点q，存储元素e
		q=(SLinkList *)malloc(sizeof(SLinkList));
		q->data=e;
		//2.让p指向第i-1个元素节点 
		p=h;
		for(j=1;j<=i-1;j++)
		{
			p=p->next;
		} 
		//3.添加
		q->next=p->next;
		p->next=q;
		return 1;
	}
	else
	{
		printf("参数错误！\n");
		return 0;
	} 
}

在链表中插入元素的时间复杂度为O(n)

9）删除

        删除元素也需要先找到第i-1个，让p指向第i-1个，让q指向第i个，把要删除的元素值存储到*e中 ，再释放内存,代码如下：

/*
参数合法：i>=1 && i<=ListLength(h)
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int ListDelete(SLinkList *h,int i,ElemType *e)
{
	SLinkList *p,*q;
	int j;
	
	if(i>=1 && i<=ListLength(h))
	{
		//1.让p指向第i-1个
		p=h;
		for(j=1;j<=i-1;j++)
		{
			p=p->next;
		} 
		//2.让q指向第i个
		q=p->next;
		//3.把要删除的元素值存储到*e中 
		*e=q->data;
		//4.删除
		p->next=q->next;
		//5.释放存储空间
		free(q); 
		return 1;
	}
	else
	{
		printf("参数错误！\n");
		return 0;
	} 	
} 

链表中删除某一元素的时间复杂度为O(n)

因为顺序表必须占用一块事先分配好的存储空间，这样会降低存储空间的利用率。

链表的设计思路就是牺牲空间效率换取时间效率

最后再附上完整代码

#include <stdio.h>
 
typedef int ElemType;
 
typedef struct Node
{
	ElemType data;//存储线性表的元素值（1个） 
	struct Node *next;//存储后继元素节点的地址 
}SLinkList;
 
/*
为了方便操作，特别地加了一个头节点进来，类型和普通节点一样
data：不用 
next：存储第1个元素节点的地址 
执行语句p=p->next;一次，p的指向往后移动一个位置
空：h->next==NULL
最后一个节点：若p->next==NULL,说明p指向最后一个节点 
*/
 
/*
1.初始化
构造一个空的线性表 
*/
SLinkList *InitList()
{
	SLinkList *h;
	h=(SLinkList *)malloc(sizeof(SLinkList));
	h->next=NULL;
	return h;
}
 
/*
2.销毁 
*/
void DestroyList(SLinkList *h)
{
	int ListDelete(SLinkList *h,int i,ElemType *e);
	ElemType v;
	
	while(h->next!=NULL)//不空
	{
		//删除第1个元素节点
		ListDelete(h,1,&v); 
	} 
	free(h);
} 
 
/*
3.判断线性表是否为空
若为空，返回1；
否则，返回0 
*/
ListEmpty(SLinkList *h)
{
	if(h->next==NULL)
	{
		return 1;
	} 
	else
	{
		return 0;
	}
} 
 
/*
4.求长度 
*/
int ListLength(SLinkList *h)
{
	SLinkList *p;
	int len;
	p=h;
	len=0;
	while(p->next!=NULL)
	{
		p=p->next;
		len=len+1;
	} 
	return len;
} 
 
/*
5.输出 
*/
void DispList(SLinkList *h)
{
	SLinkList *p;
	p=h; 
	printf("线性表的元素为：");
	while(p->next!=NULL)
	{
		p=p->next;
		printf("%d ",p->data); 
	} 
	printf("\n");
}
 
/*
6.取值
 
参数合法：i>=1 && i<=ListLength(h)
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int GetElem(SLinkList *h,int i,ElemType *e)
{
	SLinkList *p;
	int j;
	
	if(i>=1 && i<=ListLength(h))
	{
		p=h;
		for(j=1;j<=i;j++)
		{
			p=p->next;
		} 
		*e=p->data;
		return 1;
	} 
	else
	{
		printf("参数错误！\n");
		return 0;
	}	
}
 
/*
7.查找
在线性表中查找是否存在值为e的元素，
若存在，返回该元素的位序
否则，返回0 
*/
int LocateElem(SLinkList *h,ElemType e)
{
	SLinkList *p;
	int len;
	p=h;
	len=0;
	while(p->next!=NULL)
	{
		p=p->next;
		len=len+1;
		if(p->data==e)
		{
			return len;
		}
	} 
	return 0;
} 
 
/*
8.添加 
参数合法：i>=1 && i<=ListLength(h)+1
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int ListInsert(SLinkList *h,int i,ElemType e)
{
	SLinkList *p,*q;
	int j;
	
	if(i>=1 && i<=ListLength(h)+1)
	{
		//1.构造一个节点q，存储元素e
		q=(SLinkList *)malloc(sizeof(SLinkList));
		q->data=e;
		//2.让p指向第i-1个元素节点 
		p=h;
		for(j=1;j<=i-1;j++)
		{
			p=p->next;
		} 
		//3.添加
		q->next=p->next;
		p->next=q;
		return 1;
	}
	else
	{
		printf("参数错误！\n");
		return 0;
	} 
}
 
/*
9.删除
参数合法：i>=1 && i<=ListLength(h)
若参数合法，进行相关操作，返回1；
否则，提示，返回0  
*/
int ListDelete(SLinkList *h,int i,ElemType *e)
{
	SLinkList *p,*q;
	int j;
	
	if(i>=1 && i<=ListLength(h))
	{
		//1.让p指向第i-1个
		p=h;
		for(j=1;j<=i-1;j++)
		{
			p=p->next;
		} 
		//2.让q指向第i个
		q=p->next;
		//3.把要删除的元素值存储到*e中 
		*e=q->data;
		//4.删除
		p->next=q->next;
		//5.释放存储空间
		free(q); 
		return 1;
	}
	else
	{
		printf("参数错误！\n");
		return 0;
	} 	
} 
/*
变量先定义，再赋初值，才能使用 
*/
int main()
{
	
 
}