链表的增删改查(主函数操作,无封装)

发布于 29 天前  51 次阅读


/*链表的创建、插入与删除*/
#include<stdio.h>
#include <stdlib.h>//引用该文件是因为malloc()函数的原型在该文件中的439行

				   //malloc()函数原型声明:  void *__cdecl malloc(size_t _Size); 
				   //__cdecl 是 C Declaration  的缩写,表示 C 语言默认的函数调用
				   //方法:所有参数从右到左依次入栈,这些参数由调用者清除,称为
				   //手动清栈。被调用函数不会要求调用者传递多少参数,调用者传递
				   //过多或者过少的参数,甚至完全不同的参数都不会产生编译阶段的错误。
				   /*上述简单理解即可*/ 
typedef struct LinkList{
	char data;
	struct LinkList *next;//注意不要丢失struct 
} List,*Link; //创建一个结构体,里面包含的是一个节点的组成内容:包括数据域和指针域
//创建一个结构体变量,该变量即为一个节点;另外创建一个结构体指针变量,用来访问所创建的节点
 
int main(){
	
	/************************************创建链表开始************************************/
	
	//创建头结点用于保存头结点的地址,方便以后直接通过头指针直接访问;
	//解释malloc强转问题:因为malloc原型中的返回值为void*,但是我们在
	//使用时需要返回的是Link类型的,因为head需要指向的内容是Link类型的
    //结点 
	Link head=(Link)malloc(sizeof(List));//申请完成后将地址返回给head头指针,
										 //此时头指针指向的是一个头结点 
	
	//另外,如图中所示还需要一个P指针用于定位当前节点
	Link p=head;//首先将P指针指向第一个结点(head指针在上一个语句已经指向了头结点) 
				//所以这里直接将head中的地址赋值给P即可
	
	//接下来是依次创建五个新的结点
	for(int i=0;i<5;i++){
		//这里依旧像创建头结点一样创建一个新的结点,只不过上面创建的头结点数据域为空
		//这里的新建结点肯定是要有数据的,不然就成了空链表了
		Link q=(Link)malloc(sizeof(List)); 
		//这里利用一个q指针指向新建结点
		
		//给q指针里面赋值------赋值操作
		q->data = 'A'+i;
		//首先解释这里的q->c,因为q是一个指针,然后我们需要用到其数据域,所以需要用到->
		//其次这里的'A'是ASCLL码,在计算机的世界里编译器见到后会自动把'A'转换为对应的ASCLL
		//也就是直接把'A'当成65来处理,所以可以进行+1操作;65+1=66,而66对应的是'B'
		
		
        //赋值完成1次后要将P指针中的next指针指向q 
        p->next=q; 
		//然后将q指针变成p指针
		p=q; 
	} 
	p->next=NULL;//当前p在尾结点上,而尾结点的next指针必须指向空,不然会 出现内存泄露等问题 
	//至此链表创建结束,其中头结点为空,其余结点中的数据分别为A B C D E 
	/************************************创建链表结束************************************/ 
	
	/************************************创建链表结束************************************/
	//链表创建完成后先遍历一次,看一下是否存在问题
	
	/************************************开始遍历链表************************************/
	p=head->next;//这里利用结点是通过指针域相联的特点遍历链表  
	while(p->data!=NULL){//只要数据域不等于NULL说明不是最后一个节点 
	    printf("%c",p->data);//打印节点中的数据域 
		p=p->next;//指针向下移动  
	}//当节点中的数据域为空,也就是到达最后一个结点时完成遍历操作
	printf("\n"); 
	/************************************结束遍历链表************************************/
	
    //	在头结点后插入元素 
    /************************************插入结点-1开始************************************/
//                       操作                                                           code 
//    ①将申请结点的next指针先指向其后结点,其后结点在head->next中已保存       q->next = head->next;
//	  ②对申请结点的数据域进行赋值操作										   q->c = 'O';	
//    ③将申请结点的地址赋给头结点的next指针域 								   head->next = q;
//   说明:上述步骤中②顺序可调整,但是①③顺序不能调整,如果调整的话会导致找不到头结点原指向的结点 
	Link q = (Link)malloc(sizeof(List));//申请一个结点的内存空间
	q->data = 'O';//新建结点数据域赋值操作                               操作② 
	q->next = head->next;//将新建结点指向源头结点指向的节点           操作①
	head->next = q;//将新建结点地址赋值给头结点中的next指针						  操作③ 
    /************************************插入结点-1结束************************************/
    
    /************************************开始遍历链表************************************/
    p = head->next;
	while(p != NULL){
		printf("%c ",p->data);
		p = p->next;
	}
	printf("\n");
	/************************************结束遍历链表************************************/
	
	
	/************************************插入结点-2开始************************************/
	//将新建结点插入到为n的位置上,为对比与插入节点-1此时n大于1
	
	int n=3;//这里直接取位置为3,后面可以修改为交互功能,让用户输入插入位置
	
	q = (Link)malloc(sizeof(List));//申请一个节点内存空间,用于保存插入的新节点
	
	q->data = 'P';//这里直接取插入的数据为'P',后面可以改为交互功能,让用户写入插入数据
	
	p = head;//创建P指针,用于后面的遍历查询n位置
	
	for(int i=1;i<n;i++){
		p=p->next;//当i小于插入n时一直遍历链表中的结点,直到找到位置为n的结点 
	} 
	q->next = p->next;//找到后的P结点就是要插入的结点,但是此时该位置存在一个结点
	
	//然后我们知道结点的一个重要使命就是保存下一个结点的地址,否则链表就断了
	//所以需要将当前节点中保存的下一个节点信息赋值给新建的q节点的next保存
	
	p->next = q;//再将p节点的next指针指向新建立的结点
	/************************************插入结点-2结束************************************/
	
    /************************************开始遍历链表************************************/
	p = head->next;
	while(p != NULL){
		printf("%c ",p->data);
		p = p->next;
	}
	printf("\n");
	/************************************结束遍历链表************************************/
	 
	/************************************查找链表中各结点的数据域开始************************************/
	char ch='E';//这里直接赋值,后面可以改成交互功能,让用户输入所要查找的数据
	 
	
	p=head->next;//指向第一个结点(从第一个结点开始查找) 
	n=1;//标记第一个节点 
	while(p!=NULL)
	{
	    if(ch==p->data){
	    	break;
		}
		n++;//相当于一个计数器,记录ch在链表中的位置
		p=p->next;//将p指针进行移动	
	}
	/************************************查找链表中各结点的数据域结束************************************/


	/************************************删除链表中第n个结点开始************************************/
	p=head;//原理和查找一样,需要从第一个节点开始进行遍历,找到第n个直接delete
	n=5;//这里直接取n等于5,后面可以改成交互功能,让用户输入要删除的结点位置
	for(int i=1;i<n;i++){//1 2 3 4
		p=p->next;//此时P指针为第四个节点的next指针,指向第5个结点  
	} 
	//开始删除操作
	q=p->next;//将所要删除的结点地址赋值给q 
	p->next = q->next;//将删除结点中的next指针给p的next 
	free(q); //释放q结点 
	/************************************删除链表中第n个结点结束************************************/
	return 0;
} 


本当の声を響かせてよ