数据结构002-结构基础-单链表

╰+哭是因爲堅強的太久メ 2023-05-28 08:20 47阅读 0赞

# 概念 #

**链表**的引入是因为线性表的顺序存储结构，它有一个最大的缺点，就是**插入**和**删除**时需要移动大量元素，这个会需要大量时间。由此我们提出链表的概念，就是不考虑相连位置，哪里有空位，我们就去哪里，所以只要将内存地址链接起来，当我们知道第一个数据的地址，我们就会知道第二个地址，当知道第二个地址的时候，我们就会知道第三个地址。

因此，为了表示每个数据元素a\[i\]与a\[i+1\]的关系，还需要存储一个指针域，我们储存a\[n\]的地方成为数据域。这两部分信息组成数据元素a\[i\]的存储映像，称为结点（Node）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]当Node中只包含一个节点定的时候，我们称为单链表

# 单链表的操作： #

## 数据结构 ##

struct Node{
        
    	int a;
    	struct Node* next;
    };

## 初始化 和 增加 ##

void AddListTill(int a){
        
    	struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    	temp->a=a;
    	temp->next=NULL;
    	if(NULL==head){
        
    		head=temp;
    	}	
    	else{
        
    		end->next=temp;
    	}
    	end=temp;
    }

## 删 ##

void DeleteListRand(int a){
        
    	if(NULL==head){
        
    		printf("链表没有东西\n");
    		return;
    	}
    	struct Node *temp=FindNode(a);//先找到节点，返回的是struct
    	if(NULL==temp)
    	{
        
    		printf("查无此点\n");
    		return;
    	}
    	//找到了,且只有一个节点
    	if(head==end)
    	{
        
    		free(head);
    		head=NULL;
    		end=NULL;
    	}
    	else if(head->next==end) //有两个节点
    	{
        
    	//看是删除头还是删除尾
    	if(end==temp)
    		{
        	DeleteListTail(); }
    	else if(temp==head)
    		{
        	DeleteListHead(); }	
    	}
    	else//多个节点
    	{
        
    		//看是删除头还是删除尾
    		if(end==temp)
    			DeleteListTail();
    		else if(temp==head)
    			DeleteListHead();	
    		else	//删除中间某个节点
    		{
        	//找要删除temp前一个，遍历
    			struct Node *pt =head;
    			while(pt->next!=temp)
    			{
        
    				pt=pt->next;
    			}
    			//找到了
    			//让前一个直接连接后一个 跳过指定的即可
    			 pt->next=temp->next;
    			 free(temp);
    		
    		}
    	}
    }

## 查 ##

struct Node* FindNode(int a){
        
    	struct Node* temp=head;//拿到头指针
    	while(temp!=NULL){
        
    		if(a==temp->a){
        
    			return temp;
    		}
    		temp=temp->next;
    	} 
    	
    	return NULL;
    	
    }

## 插入 ##

**指定插入**

void AddListRand(int index,int a){
        
    	if(NULL==head){
        
    		printf("链表没有节点\n");
    		return;
    	}
    	struct Node* pt=FindNode(index);
    	if(NULL==pt){
        
    		printf("没有指定节点\n");
    		return;
    	}
    	struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    	temp->a=a;
    	temp->next=NULL;
    	if(pt==end){
        
    		end->next=temp;
    		end=temp;
    	}else{
        
    		temp->next=pt->next;
    		pt->next=temp;
    	}
    }

**尾插法**

void AddListTill(int a){
        
    	struct Node* temp=(struct Node*)malloc(sizeof(struct Node));//申请空间
    	temp->a=a;
    	temp->next=NULL;
    	if(NULL==head){
        //没有节点时
    		head=temp;
    	}	
    	else{
        
    		end->next=temp;//尾部插入
    		
    	}
    	end=temp;
    }

## 输出 ##

void ScanList(){
        
    	struct Node* temp=head;
    	while(temp!=NULL){
        
    		printf("%d\n",temp->a);
    		temp=temp->next;
    	} 
    }

#include <stdlib.h>
    #include<string.h>
    #include<stdio.h>
    
    struct Node{
        
    	int a;
    	struct Node* next;
    };
    struct Node* head=NULL;
    struct Node* end=NULL;
    void AddListTill(int a){
        
    	struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    	temp->a=a;
    	temp->next=NULL;
    	if(NULL==head){
        
    		head=temp;
    	}	
    	else{
        
    		end->next=temp;
    		
    	}
    	end=temp;
    }
    void ScanList(){
        
    	struct Node *temp=head;
    	while(temp!=NULL){
        
    		printf("%d\n",temp->a);
    		temp=temp->next;
    	} 
    }
    
    struct Node* FindNode(int a){
        
    	struct Node *temp=head;//拿到头指针
    	while(temp!=NULL){
        
    		if(a==temp->a){
        
    			return temp;
    		}
    		temp=temp->next;
    	} 
    	
    	return NULL;
    	
    }
    
    void FreeList(){
        
    	struct Node *temp=head;
    	while(temp!=NULL){
        
    		struct Node* pt=temp;
    		temp=temp->next;
    		free(pt);
    	}
    	head=NULL;
    	end=NULL;
    }
    void AddListRand(int index,int a){
        
    	if(NULL==head){
        
    		printf("链表没有节点\n");
    		return;
    	}
    	struct Node* pt=FindNode(index);
    	if(NULL==pt){
        
    		printf("没有指定节点\n");
    		return;
    	}
    	struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    	temp->a=a;
    	temp->next=NULL;
    	if(pt==end){
        
    		end->next=temp;
    		end=temp;
    	}else{
        
    		temp->next=pt->next;
    		pt->next=temp;
    	}
    }
    void DeleteListTail(){
        
    	if(NULL==end){
        
    		printf("链表为空，无需删除\n");
    		return;
    		
    	}
    	if(head==end){
        
    		free(head);
    		head=NULL;
    		end=NULL;
    	}else{
        
    		struct Node* temp=head;
    		while(temp->next!=end){
        
    			temp=temp->next;
    		}
    		free(end);
    		end=temp;
    		end->next=NULL; 
    	}
    }
    
    void DeleteListHead(){
        
    	struct Node* temp=head;
    	if(NULL==head){
        
    		printf("头指针为空\n");
    		return;
    	}
    	head=head->next;
    	free(head);
    }
    
    void DeleteListRand(int a){
        
    	if(NULL==head){
        
    		printf("链表没有东西\n");
    		return;
    	}
    	struct Node*temp=FindNode(a);
    	if(NULL==temp)
    	{
        
    	printf("查无此点\n");
    	return;
    	}
    	//找到了,且只有一个节点
    	if(head==end)
    	{
        
    	free(head);
    	head=NULL;
    	end=NULL;
    	}
    	else if(head->next==end) //有两个节点
    	{
        
    	//看是删除头还是删除尾
    	if(end==temp)
    		{
        	DeleteListTail(); }
    	else if(temp==head)
    		{
        	DeleteListHead(); }	
    	}
    	else//多个节点
    	{
        
    		//看是删除头还是删除尾
    		if(end==temp)
    			DeleteListTail();
    		else if(temp==head)
    			DeleteListHead();	
    		else	//删除中间某个节点
    		{
        	//找要删除temp前一个，遍历
    			struct Node*pt =head;
    			while(pt->next!=temp)
    			{
        
    			pt=pt->next;
    			}
    			//找到了
    			//让前一个直接连接后一个 跳过指定的即可
    			 pt->next=temp->next;
    			 free(temp);
    		
    		}
    	}
    }
    
    
    
    
    
    int main ()
    {
        	
    	struct Node *pFind ;
    	//创建5个节点
    	int i=0;
    	for(i=0;i<6;i++)
    	AddListTill(i);
    	
    //	AddListRand(4,14);		//在指定位置4增加节点14
    //	DeleteListTail();		//删除一个尾结点
    	DeleteListRand(4);		//删除4节点
    	ScanList();				//便利输出链表
    	FreeList();				//删除链表
    /*	pFind = FindNode(5);	//查找5节点
    
    	if (pFind !=  NULL)
    	{
    		printf("找到%d\n",pFind->a);	//找到节点并且输出该节点数据
    	}
    	else
    	{
    		printf("No Find!\n");
    	}
    
    */
    	return 0;
    }

## demo2 ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct List
    {
        
    	char x;//结点的数据区
    	struct List * next;//结点的地址区
    }e;
    void setHead(e *l)
    {
        
    	l->next = NULL;
    }
    void newList(e *l)//尾插法建立链表
    {
        
    	//连续建立结点
    	//连续输入数据以$表示建表结束
    	int i = 1;
    	char a;//临时储存数据
    	printf("请输入数据，以$表示建表结束!\n");
    	while (i)
    	{
        	
    		scanf("\n%c",&a);
    		if (a == '$')
    		{
        
    			i = 0;
    		}
    		else
    		{
        
    			while (l->next == NULL)
    			{
        
    				e *l2 = (e *)malloc(sizeof(e));//给新的节点分配空间
    				l2->x = a;//将数据放进结点的数据区
    				l->next= l2;//上一节点的地址区指向新的结点
    				l = l2;//移动指针向后移动
    				l2->next = NULL;//新结点的地址区为空
    				break;
    			}
    		}
    	}
    }
    
    void endAdd(e *l,char a)//尾插法插入数据
    {
        
    	e * l1 = l;//移动指针初始化
    	while (1)
    	{
        
    		//通过遍历将移动指针指向最后一个结点
    		if (l1->next != 0)
    		{
        
    			l1 = l1->next;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    	e *l2 = (e *)malloc(sizeof(e));//为插入的结点分配内存
    	l2->x = a;//将数据存入结点
    	l1->next = l2;//将最后结点的指针区指向新添加的结点
    	l2->next = NULL;//将最后结点的指针区赋值为空
    }
    void headAdd(e *l,char a)
    {
        
    	e *l2 = (e *)malloc(sizeof(e));//为新的结点分配内存
    	l2->x = a;
    	//新结点的地址区指向原来头结点的地址区指向
    	l2->next = l->next;
    	//头结点地址区指向新的结点
    	l->next = l2;
    }
    void printfList(e * l)//输出链表内容
    {
        
    	while (l->next != NULL)
    	{
        
    		//遍历输出结点的数据区
    		l = l->next;
    		printf("%c ", l->x);
    	}
    	printf("\n");
    }
    void longList(e *l)//获取单链表的长度
    {
        
    	int i = 0;//统计长度
    	while(l->next)
    	{
        
    		//遍历统计单链表的长度
    		l = l->next;
    		i++;
    	}
    	printf("\n该单链表的长度为:%d\n", i);
    }
    int deleteList(e * l, int j)
    {
        
    	//将需要删除的上一个结点的地址区指向需要删除结点的指针区所指向的区域
    	e *l2 = NULL;
    	int i = 0;//标记结点位置
    	while (l->next&& j < i - 1)
    	{
        
    		i++;
    		l = l->next;
    	}
    	if (l->next)
    	{
        
    		l2 = l->next;//将要删除的结点地址储存下来
    		l->next = l->next->next;
    		free(l2);//释放空间
    		//删除成功返回0
    		return 0;
    	}
    	//删除失败返回-1
    	return -1;
    }
    int add(e *l, int j, char a)
    {
        
    	int i = 0;//标记位置
    	e *l1=l;//移动指针
    	while (l1->next!=NULL)
    	{
        
    		if (j - 1 == i)//当指针移动到插入位置的前一个结点时
    		{
        
    			e *l2 = (e *)malloc(sizeof(e));
    			l2->next = l1->next;
    			l1->next = l2;
    			l2->x = a;
    			//添加成功返回0
    			return 0;
    		}
    		i++;
    		l1 = l1->next;
    	}
    	//添加失败返回-1
    	return -1;
    }
    
    int  findList(e *l, char a)
    {
        
    	e *l1 = l;
    	int i = 0;
    	while (l1->next != NULL)
    	{
        
    		//遍历链表的结点
    		l1 = l1->next;
    		i++;
    		if (l1->x == a)
    		{
        
    			//发现需要查找的数据则返回该数据所在结点在链表中的位置
    			return i;
    		}
    	}
    	//未找到则返回-1
    	return -1;
    }
    int main()
    {
        	
    	
    	e *head = (e *)malloc(sizeof(e));
    	setHead(head);//初始化头结点
    	while(1){
        
    		printf("请输入你的选择：\n");
    		printf("0--创建列表  1--输出列表长度\n");
    		printf("2--打印链表  3--指定查找\n");
    		printf("4--头插  5--删除节点\n");
    		printf("6--指定插入 \n");
    		int dd=0;
    		scanf("%d",&dd);
    	
    		if(dd==0){
        
    			newList(head);//初始化链表
    		}else if(dd==1){
        
    			longList(head);//输出链表的长度
    		}else if(dd==2){
        
    			printfList(head);//输出链表的数据
    		}else if(dd==3){
        
    			printf("输入要查找的结点:");
    			char s;
    			scanf("\n%c",&s);
    			int q=findList(head, s);//查找结点
    			if (q > 0)
    			{
        
    				printf("该结点的位置是:%d\n", q);
    			}
    			else
    			{
        
    				printf("没有找到该结点\n");
    			}
    		}else if(dd==4){
        
    			printf("输入要插入的值:"); 
    			char ss;
    			scanf("\n%c",ss);
    			headAdd(head, ss);//头插法插入结点
    		}
    		else if(dd==5){
        
    			deleteList(head,1);//删除链表中第一个结点
    		}else{
        
    			printf("输入插入位置和插入的值:");
    			int aa=0;
    			char ss;
    			scanf("\n%d",&aa);
    			scanf("\n%c",&ss);
    			add(head, aa, ss);//在链表的第二个位置插入
    		}
    	}
    	
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230528/b8d1513a460744a39de8dea53e46fbf2.png