数据结构 - 单链表的基本操作 (C语言）

偏执的太偏执、 2022-06-04 05:44 161阅读 0赞

单链表：一组任意存储单元组成的线性表. 单链表这块也没有什么难点，都是一些基本操作。但是应该注意以下几点：

(1) ：单链表一般附加头结点，这样做的好处是：初始化单链表后头指针不需要再改动.

(2) ：头结点的数据域一般不存储数据 或者 存储标题，表长等信息.

而单链表的存储结构一般如下：

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

下面，我们来看看每个部分函数实现：

1 - 单链表的创建：

单链表的创建可以使用：头插法或尾插法。我一般使用尾插法，因为头插法的数据与键盘输入的顺序相反，不习惯，因人而异吧.

a) : 头插法创建单链表，代码如下：

LinkList Creat_LinkList_1()		//头插法创建单链表.
    {
    	printf("Please enter linklist datas(END OF -1): ");
    	LinkList H = (LinkList)malloc(sizeof(LNode));
    	H->next=NULL;
    	LNode *s;
    	ElemType x;
    	scanf("%d",&x);
    	while(x!=-1){
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = H->next;
    		H->next = s;
    		scanf("%d",&x);
    	}
    	
    	return H;
    }

b) : 尾插法创建单链表，代码如下：

LinkList Creat_LinkList_2()		//尾插法创建单链表.
    {
    	printf("Please enter linklist datas(END OF -1): ");
    	LinkList H = (LinkList)malloc(sizeof(LNode));
    	H->next = NULL;
    	LNode *r = H;
    	LNode *s;
    	ElemType x;
    	scanf("%d",&x);
    	while(x!=-1){
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = r->next;
    		r->next = s;
    		r = s;
    		scanf("%d",&x);
    	}
    	
    	return H;
    }

2 - 计算单链表的表长：

通过计数器来统计单链表中的结点个数，设计思路也很简单，代码如下：

int Length_LinkList(LinkList H)		//计算表长.
    {
    	int length=0;
    	LNode *p = H->next;
    	while(p){
    		p = p->next;
    		length++;
    	}
    	return length;
    }

3 - 按值查找单链表的元素：

LinkList Locate_LinkList(LinkList H,ElemType x)		//按值查找值为x的值.
    {
    	LNode *p=H->next;
    	while(p->data != x && p){
    		p=p->next;
    	}
    	if(p->data == x)  return p;
    	else return NULL; 
    }

4 - 按序号查找单链表的元素并返回结点指针值：（返回指针值，后面可以用到）

LinkList Get_LinkList(LinkList H,int k)		//按序号查找第k个元素.
    {
    	int j=0;
    	LNode *p = H->next;
    	while(p && j<k){
    		p = p->next;
    		j++;
    	}
    	if(j == k ) return p;
    	else return NULL;
    }

5 - 单链表的插入：

因为插入操作时，需要知道单链表插入位置的前一个结点的信息，所以利用上面的代码，可以快速定位：

int Insert_LinkList(LinkList H,int i,ElemType x)	//插入数据.
    {
    	LNode *p,*s;
    	p = Get_LinkList(H,i-1);		//查找第i-1个结点. 
    	if(p == NULL){
    		printf("\nInsert Location is Eroor.\n");
    		return ERROR;
    	}
    	else{
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = p->next;
    		p->next = s;
    		return TRUE;
    	}
    	 
    }

6 - 单链表的删除：

同理：单链表的删除更需要知道前一个结点的指针值，这样可以实现快速定位：

int Delete_LinkList(LinkList H,int i)	//删除单链表中第i位置的元素.
    {
    	LinkList p,q;
    	p = Get_LinkList(H,i-1);	//查找第i-1个结点.
    	if(p == NULL){
    		printf("\nDelete Location is wrong!\n");
    		return ERROR;
    	}
    	else{
    		if(p->next==NULL){
    			printf("\nDelete Location is wrong!\n");
    			return ERROR;
    		}
    		else{
    			q=p->next;
    			p->next=q->next;
    			free(q);
    			return TRUE;
    		}
    	}
    }

7 - 单链表的逆置：

逆置的中心思想：先断链，再头插。具体思路：先让H->next = NULL,然后将原来链表的数据挨个头插到头结点之后，便完成单链表的逆置，代码如下：

void Reverse_LinkList(LinkList H)		//逆置单链表.
    {
    	LinkList p,q;
    	p=H->next;
    	H->next=NULL;	 //方法：先断链，再头插. 
    	while(p){ 
    		q=p;
    		p=p->next;
    		q->next=H->next;
    		H->next=q;
    	}
    }

8 - 单链表中删除重复的值：（取重）

void Pur_LinkList(LinkList H)	//在单链表中删除重复结点. 
    {
    	LNode *p,*q,*r;
    	p=H->next;
    	if(p!=NULL)
    	while(p->next){
    		q=p;
    		while(q->next)
    		{
    			if(q->next->data == p->data)
    			{
    				r = q->next;		//找到后续结点，用r指向，删除*r. 
    				q->next = r->next;
    				free(r);
    			} 
    			else q = q->next;
    		}
    		p=p->next;
    	}
    }

现在，我还是打算把自己写好的代码全部放上去，供大家学习交流使用：

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 0
    #define TRUE 1
    
    typedef int ElemType;
    
    typedef struct node
    {
    	ElemType data;
    	struct node *next;
    }LNode,*LinkList;
    
    LinkList Creat_LinkList_1();	//头插法创建单链表.
    
    LinkList Creat_LinkList_2();	//尾插法创建单链表.
    
    int Length_LinkList(LinkList H);	//计算表长.
    
    LinkList Get_LinkList(LinkList H,int k);	//按序号查找第k个元素.
    
    LinkList Locate_LinkList(LinkList H,ElemType x);	//按值查找值为x的值.
    
    int Insert_LinkList(LinkList H,int i,ElemType x);	//插入数据.
    
    int Delete_LinkList(LinkList H,int i);		//删除单链表中第i位置的结点.
    
    void Reverse_LinkList(LinkList H);		//逆置单链表.
    
    void Pur_LinkList(LinkList H);		//在单链表中删除重复结点. 
    
    void Print_LinkList(LinkList H);	//打印单链表. 
    
    int main()
    {
    	LinkList H = (LinkList)malloc(sizeof(LNode));
    	H = Creat_LinkList_2();
    	
    	int length=0;
    	length =  Length_LinkList(H);
    	printf("\nThe LinkList length is %d.\n",length);
    	
    	int k;
    	LNode *p;
    	printf("\nPlease enter u wanna search node's num: ");
    	scanf("%d",&k);
    	p=Get_LinkList(H,k);
    	printf("\nThe Node's point is %d.\n",p);
    	
    	ElemType x;
    	printf("\nPlease enter Insert Location and ElemType x:");
    	scanf("%d%d",&k,&x);
    	Insert_LinkList(H,k,x);
    	Print_LinkList(H);
    	
    	printf("\nPlease enter delete nodenum:");
    	scanf("%d",&k);
    	Delete_LinkList(H,k);
    	Print_LinkList(H);
    	
    	Reverse_LinkList(H);
    	Print_LinkList(H); 
    	
    	return 0;
    }
    
    LinkList Creat_LinkList_1()		//头插法创建单链表.
    {
    	printf("Please enter linklist datas(END OF -1): ");
    	LinkList H = (LinkList)malloc(sizeof(LNode));
    	H->next=NULL;
    	LNode *s;
    	ElemType x;
    	scanf("%d",&x);
    	while(x!=-1){
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = H->next;
    		H->next = s;
    		scanf("%d",&x);
    	}
    	
    	return H;
    }
    
    LinkList Creat_LinkList_2()		//尾插法创建单链表.
    {
    	printf("Please enter linklist datas(END OF -1): ");
    	LinkList H = (LinkList)malloc(sizeof(LNode));
    	H->next = NULL;
    	LNode *r = H;
    	LNode *s;
    	ElemType x;
    	scanf("%d",&x);
    	while(x!=-1){
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = r->next;
    		r->next = s;
    		r = s;
    		scanf("%d",&x);
    	}
    	
    	return H;
    }
    
    int Length_LinkList(LinkList H)		//计算表长.
    {
    	int length=0;
    	LNode *p = H->next;
    	while(p){
    		p = p->next;
    		length++;
    	}
    	return length;
    }
    
    LinkList Get_LinkList(LinkList H,int k)		//按序号查找第k个元素.
    {
    	int j=0;
    	LNode *p = H->next;
    	while(p && j<k){
    		p = p->next;
    		j++;
    	}
    	if(j == k ) return p;
    	else return NULL;
    }
    
    LinkList Locate_LinkList(LinkList H,ElemType x)		//按值查找值为x的值.
    {
    	LNode *p=H->next;
    	while(p->data != x && p){
    		p=p->next;
    	}
    	if(p->data == x)  return p;
    	else return NULL; 
    }
    
    int Insert_LinkList(LinkList H,int i,ElemType x)	//插入数据.
    {
    	LNode *p,*s;
    	p = Get_LinkList(H,i-1);		//查找第i-1个结点. 
    	if(p == NULL){
    		printf("\nInsert Location is Eroor.\n");
    		return ERROR;
    	}
    	else{
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = p->next;
    		p->next = s;
    		return TRUE;
    	}
    	 
    }
    
    void Print_LinkList(LinkList H)		//打印单链表.
    {
    	printf("\nThe LinkList NodeData as following:");
    	LinkList p = H->next;
    	while(p!=NULL){
    		printf("%d ",p->data); 
    		p = p->next;
    	}
    	printf("\n"); 
    }
    
    int Delete_LinkList(LinkList H,int i)	//删除单链表中第i位置的元素.
    {
    	LinkList p,q;
    	p = Get_LinkList(H,i-1);	//查找第i-1个结点.
    	if(p == NULL){
    		printf("\nDelete Location is wrong!\n");
    		return ERROR;
    	}
    	else{
    		if(p->next==NULL){
    			printf("\nDelete Location is wrong!\n");
    			return ERROR;
    		}
    		else{
    			q=p->next;
    			p->next=q->next;
    			free(q);
    			return TRUE;
    		}
    	}
    }
    
    void Reverse_LinkList(LinkList H)		//逆置单链表.
    {
    	LinkList p,q;
    	p=H->next;
    	H->next=NULL;	 //方法：先断链，再头插. 
    	while(p){ 
    		q=p;
    		p=p->next;
    		q->next=H->next;
    		H->next=q;
    	}
    }
    
    void Pur_LinkList(LinkList H)	//在单链表中删除重复结点. 
    {
    	LNode *p,*q,*r;
    	p=H->next;
    	if(p!=NULL)
    	while(p->next){
    		q=p;
    		while(q->next)
    		{
    			if(q->next->data == p->data)
    			{
    				r = q->next;		//找到后续结点，用r指向，删除*r. 
    				q->next = r->next;
    				free(r);
    			} 
    			else q = q->next;
    		}
    		p=p->next;
    	}
    }

小结：

单链表这边的操作也不是很难，只要C语言指针的知识学的比较扎实。然后，也需要多加练习。