精华内容
下载资源
问答
  • C语言链表操作详解

    万次阅读 多人点赞 2018-12-29 19:01:55
    为什么要使用链表 在未学习链表时,我们常用的存储数据的方式无非就是数组。...而链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表的操作。 链表的特点: n个节点离散分配 每一个节...

    为什么要使用链表

    在未学习链表时,我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快,但是它的弊端也很明显:

    1.  使用前需声明数组的长度,一旦声明长度就不能更改
    2. 插入和删除操作需要移动大量的数组元素,效率慢
    3. 只能存储一种类型的数据.

    而链表则可以实现以上这些数组所不具备的功能,此时引入了结构体来实现创建链表的操作。

    链表的特点:

    1.  n个节点离散分配
    2. 每一个节点之间通过指针相连
    3. 每一个节点有一个前驱节点和一个后继节点
    4. 首节点没有前驱节点,尾节点没有后继节点

    首先先定义一个简单的结构体

    struct link{
           int data;          //定义数据域
           struct link *next; //定义指针域,存储直接后继的节点信息
    };

    数据域的内容可以自己指定,指针域用来存放下一个节点的地址。

    创建链表前须知

    首节点:存放第一个有效数据的节点

    头节点:在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点,头结点的数据域可以不存储任何信息,指针域指向第一个节点(首节点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空

    头指针:指向头节点的指针

    尾节点:存放最后一个有效数据的节点

    尾指针:指向尾节点的指针

    建立一个单向链表

    方法:定义方法向链表中添加节点来建立一个单向链表

    思路:首先定义一个结构体指针变量p,使用malloc函数为新建节点申请内存空间,让p指向这个节点(指向它刚申请的内存空间),再将其添加到链表中。此时需考虑两种情况:

    1.若单链表为空表,则将新建节点置为头节点

    //若此时只在链表中插入头节点
    struct link *p = head;
    p = (struct link *)malloc(sizeof(struct link));  //让p指向新建节点创建的内存空间
    if(p == NULL){   //新建节点申请内存失败
        exit(0);
    }
    //此时head也指向头节点的地址
    p->next = NULL;     //因为没有后续节点,所以新建节点指针域置空

    2.链表非空,则将新建节点添加到表尾

    //此时已存在头节点,再插入一个节点(首节点)
    struct link *p = NULL,*pr = head;  
    p = (struct link *)malloc(sizeof(struct link));
    if(p == NULL){
        exit(0);
    }
    if(head == NULL){
        head = p;
    }else{
        while(pr->next != NULL){     //当头节点的指针域不为NULL
          pr = pr->next;             //pr指向下一个节点的地址
      }
        pr->next = p;                //使头节点的指针域存储下一个节点的地址
    }

    完整操作

    #include <stdio.h>
    #include <stdlib.h>
    struct link *AppendNode(struct link *head);
    void DisplayNode(struct link *head);
    void DeleteMemory(struct link *head);
    //定义结构体 
    struct link{
    	int data; 				//定义数据域 
    	struct link *next; 			//定义指针域 
    }; 
    int main(){
    	int i =0;         			//定义i,记录创建的节点数 
    	char c;							
    	struct link *head = NULL;		//创建头指针,初始化为NULL 
    	printf("DO you wang to append a new node(Y or N)?");
    	scanf(" %c",&c);				
    	while(c == 'Y' || c == 'y'){	//如果确定继续添加结点 
    		head = AppendNode(head);	//通过函数获得链表的地址,AppendNode函数返回的是链表的头指针
    		                            //可以根据头指针指向的地址来获取链表中保存的数据 
    		DisplayNode(head);			//根据头指针打印链表 
    		printf("DO you want to append a new node(Y or N)?");
    		scanf(" %c",&c);
    		i++; 
    	}
    	printf("%d new nodes hava been appended!\n",i);
    	DeleteMemory(head);			//释放占用的内存 
    }
    struct link *AppendNode(struct link *head){    //声明创建节点函数 
    	struct link *p = NULL,*pr = head;      //创建p指针,初始化为NULL;创建pr指针,通过pr指针来给指针域赋值 
    	int data ;
    	p = (struct link *)malloc(sizeof(struct link)) ; //为指针p申请内存空间,必须操作,因为p是新创建的节点 
    	if(p == NULL){			//如果申请内存失败,则退出程序 
    		printf("NO enough momery to allocate!\n");
    		exit(0);
    	}
    	if(head == NULL){		//如果头指针为NULL,说明现在链表是空表 
    		head = p;								//使head指针指向p的地址(p已经通过malloc申请了内存,所以有地址) 
    	}else{										//此时链表已经有头节点 ,再一次执行了AppendNode函数 
    												//注:假如这是第二次添加节点
    	                                  //因为第一次添加头节点时,pr = head,和头指针一样指向头节点的地址 
    		while(pr->next!= NULL){		//当pr指向的地址,即此时的p的指针域不为NULL(即p不是尾节点) 
    			pr = pr->next;	//使pr指向头节点的指针域
    		}
    		pr->next = p;	//使pr的指针域指向新键节点的地址,此时的next指针域是头节点的指针域 
    	}
    	printf("Input node data:");                   
    	scanf("%d",&data);
    	p->data = data; 			//给p的数据域赋值 
    	p->next = NULL;			//新添加的节点位于表尾,所以它的指针域为NULL 
    	return head;			//返回head的地址 
    }
    void DisplayNode(struct link *head){         	//输出函数,打印链表 
    	struct link *p = head;			// 定义p指针使其指向头节点 
    	int j = 1;									//定义j记录这是第几个数值 
    	while(p != NULL){		//因为p = p->next,所以直到尾节点打印结束 
    		printf("%5d%10d\n",j,p->data);			
    		p = p->next;		//因为节点已经创建成功,所以p的指向由头节点指向下一个节点(每一个节点的指针域都指向了下一个节点) 
    		j++;	
    	}
    }
    void DeleteMemory(struct link *head){			//释放资源函数 
    	struct link *p = head,*pr = NULL;	        //定义p指针指向头节点 
    	while(p != NULL){				//当p的指针域不为NULL 
    		pr = p;									//将每一个节点的地址赋值给pr指针 
    		p = p->next;			        //使p指向下一个节点 
    		free(pr);								//释放此时pr指向节点的内存 
    	}
    }

    第二种创建链表方式-优化

    #include <stdio.h> 
    #include <stdlib.h>
    struct Stu *create(int n);
    void print(struct Stu *head);
    struct Stu{
    	int id;
    	char name[50];
    	struct Stu *next;
    };
    int main(){
    	int n;
    	struct Stu *head = NULL;   //创建头指针 
    	printf("请输入你想要创建的节点个数:\n");
    	scanf("%d",&n);
    	head = create(n);
    	print(head);
    }
    struct Stu *create(int n){
    	struct Stu *head,*node,*end;   						//定义头节点,普通节点,尾节点 
    	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
    	end = head;        									//若是空表,则头尾地址一致 
    	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->id,node->name);	//给数据域赋值 
    		end->next = node;					//让上一个节点的数据域指向当前节点 
    		end = node;     						//end指向当前节点,最终end指向尾节点 
    	}
    	end->next = NULL;                                   //给end的指针域置空 
    	return head;                                        //返回头节点的地址 
    }
    void print(struct Stu *head){
    	struct Stu *p = head;
    	int j =1;
    	p = p->next;  //不打印头节点的数据域中的值 
    	while(p != NULL){
    		printf("%d\t%d\t%s\n",j,p->id,p->name);
    		p = p->next;
    		j++;
    	}
    }

    前插法创建链表 --逆序输出

    struct link *create(int n){
         struct link *headnode ,*node;
         headnode = (struct link *)malloc(sizeof(struct link));   //为头节点申请内存 
    	 headnode ->next = NULL;     //让头节点的指针域置空 
    	 for(int i=0;i<n;i++){ 
    	 	node = (struct link *)malloc(sizeof(struct link));  //给新建节点申请内存 
    	 	scanf("%d",&node->data);       //新建节点数据域传值 
    	 	node->next = headnode->next;   //新建节点的数据域指向头节点 == 创建尾节点 
    	 	headnode->next = node;         //将新建节点数据域传给头节点 
    	 }	
    	 return headnode;  
    }

     

    删除节点

    void deleteNode(struct Stu *head,int n){         //删除n处的节点 
    	struct  Stu *p = head,*pr = head;
    	int i =0;
    	while(i<n&&p!=NULL){       //到达指定节点,此时p指向指定节点,pr指向上一节点 
    		pr = p;            //将p的地址赋值给pr
    		p = p->next;       //p指向下一节点
    		i++;
    	}
    	if(p!=NULL){               //当p不为空时,即p不能指向尾节点之后的节点
    		pr->next = p->next;
    		free(p);
    	} else{
    		printf("节点不存在!\n"); 
    	}
    } 

    我在这着重解释一下p->next = NULL和p!=NULL的区别,因为我刚开始也经常弄错!!

    • while(p->next != NULL) 循环结束时,此时p的位置是尾节点的位置,但如果用于输出函数的判断条件,则尾节点的数据不会输出。
    • while(p!=NULL) 循环结束时, 此时p指向的位置为尾节点的下一个节点,因为没有申请内存空间,所以是一个未知的区域。

    插入节点

    void insertNode(struct Stu *head,int n){    //插入节点 
    	struct Stu *p = head,*pr;
    	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
    	printf("input data:\n");
    	scanf("%d %s",&pr->id,pr->name);
    	int i = 0;
        //当插入位置是尾节点时,只要在尾节点后再插入一个节点,并让尾节点的指针域指向新建节点,新建节点的指针域置空
        while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->next;
    		i++;
    	}
    	if(p!=NULL){            //如果p没越界 
    		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
    		p->next = pr;       //使插入节点指向新建节点 
    	}else{
    		printf("节点不存在!\n");
    	}
    }

    修改节点

    void change(struct Stu *head,int n){
    	struct Stu *p = head;
    	int i = 0;
    	while(i<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在!\n");
    	} 

    链表的逆序

     

    思路:假如此时链表有两个有效节点,头节点为0号,中间的节点为1号,尾节点为2号

    1.定义三个指针pf指向链表的头节点(0号),tmp,pb初始化为NULL

    2.让pb指向pf的下一个节点(1号),并将此时头节点的指针域置空(变为尾节点)

    3.第一次while循环,让tmp指向pb(1号),然后让pb指向下一个节点,再让tmp让1号节点的指针域(tmp->next = pf)指向pf(上一个节点)(0号),再将pf指向tmp(1号)(pf = tmp)

    4.第二次while循环,让tmp指向pb(2号),然后让pb指向下一个节点,此时pb==NULL,所以这是最后一次循环,再让tmp让2号节点的指针域(tmp->next = pf)指向pf(1号),再将pf指向tmp(2号)

     5.此时链表逆序完成,让头指针指向首节点(2号),返回头指针即可

                                                                              逆序后

    STU *link_reversed_order(STU *head)
    {
        STU *pf = NULL, *pb = NULL, *tmp = NULL; 
        pf = head;  //将头节点的地址赋值给pf 
        if(head == NULL) { //如果链表为空 
            printf("链表为空,不需要逆序!\n");
            return head;
        } else if(head->next == NULL) {  //如果只有一个节点 
            printf("链表只有一个节点,不需要逆序!\n");
            return head;
        } else {
            pb = pf->next;  //pb指向pf的下一个节点 
            head->next = NULL; //头节点的指针域置空(变为尾节点) 
            while(pb != NULL)	//当pb不为空时 
            {
                tmp = pb;	//将pb的地址赋值给temp 
                pb = pb->next; //pb指向下一个节点 
                tmp->next = pf;	//pb的上一个节点的指针域指向pf 
                pf = tmp;	//让pf指向tmp 
            }
            head = pf;
            return head;
        }    
    }*/

    所有操作

    #include <stdio.h> 
    #include <stdlib.h>
    struct Stu *create(int n);
    void print(struct Stu *head);
    void deleteNode(struct Stu *head,int n);
    void insertNode(struct Stu *head,int n);
    void change(struct Stu *head,int n);
    struct Stu{
    	int id;
    	char name[50];
    	struct Stu *next;
    };
    int main(){
    	int n,j,in,cn;
    	char c;
    	struct Stu *head = NULL;   //创建头指针 
    	printf("请输入你想要创建的节点个数:\n");
    	scanf("%d",&n);
    	head = create(n);
    	print(head);
    	while(true){
    	printf("请选择你想要执行的操作:\n");
    	printf("1.插入节点\n2.删除节点\n3.修改节点\n4.退出程序\n");
    	scanf(" %c",&c);
    	if(c =='1'){
    	printf("你想要在哪插入节点:\n");
    	scanf("%d",&in);
    	insertNode(head,in);
    	print(head); 
    	}else if(c == '2'){
    	printf("你想要删除哪个节点的数据:\n");
    	scanf("%d",&j);
    	deleteNode(head,j);
    	print(head);
    	}else if(c =='3'){
    	printf("你想要修改哪个节点的数据:\n");
    	scanf("%d",&cn);
    	change(head,cn);
    	print(head); 
    	}else if(c =='4'){
    		exit(0);
    	} 		
     } 
    }
    struct Stu *create(int n){
    	struct Stu *head,*node,*end;   						//定义头节点,普通节点,尾节点 
    	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
    	//head->id = n;										//头节点的数据域保存链表的长度 
    	end = head;        									//若是空表,则头尾地址一致 
    	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
    		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
    		scanf("%d %s",&node->id,node->name);			//给数据域赋值 
    		end->next = node;								//让上一个节点的数据域指向当前节点 
    		end = node;     								//end指向当前节点,最终end指向尾节点 
    	}
    	end->next = NULL;                                   //给end的指针域置空 
    	return head;                                        //返回头节点的地址 
    }
    void print(struct Stu *head){
    	struct Stu *p = head;
    	int j =1;
    	p = p->next;  //不打印头节点的数据域中的值 
    	while(p != NULL){
    		printf("%d\t%d\t%s\n",j,p->id,p->name);
    		p = p->next;
    		j++;
    	}
    }
    void deleteNode(struct Stu *head,int n){         //删除n处的节点 
    	struct  Stu *p = head,*pr = head;
    	int i =0;
    	while(i<n&&p!=NULL){       //到达指定节点,此时p指向指定节点,pr指向上一节点 
    		pr = p;
    		p = p->next;
    		i++;
    	}
    	if(p!=NULL){
    		pr->next = p->next;
    		free(p);
    	} else{
    		printf("节点不存在!\n"); 
    	}
    } 
    void insertNode(struct Stu *head,int n){    //插入节点 
    	struct Stu *p = head,*pr;
    	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
    	printf("input data:\n");
    	scanf("%d %s",&pr->id,pr->name);
    	int i = 0;
        //当插入位置是尾节点时,只要在尾节点后再插入一个节点,并让尾节点的指针域指向新建节点,新建节点的指针域置空
        while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
        	p = p->next;
    		i++;
    	}
    	if(p!=NULL){            //如果p没越界 
    		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
    		p->next = pr;       //使插入节点指向新建节点 
    	}else{
    		printf("节点不存在!\n");
    	}
    }
    void change(struct Stu *head,int n){
    	struct Stu *p = head;
    	int i = 0;
    	while(i<n && p!=NULL){      //使p指向需修改节点 
    		p = p->next;
    		i++;
    	}
    	if(p != NULL){             
    	printf("请输入修改之后的值:\n");
    	scanf("%d %s",&p->id,p->name);	
    	}else{
    		printf("节点不存在!\n");
    	} 	 
    } 

     

     

    展开全文
  • 关于c语言链表的详解

    2014-04-18 15:43:48
    链表的讲解,创建,查找,更改,删除等基本操作
  • c语言链表详解

    万次阅读 多人点赞 2016-11-24 16:56:33
    c语言链表 1. 链表介绍 c语言单向链表翻转是面试官常问问题之一,故此,咱就谈一谈,链表并不是如此可怕,学不会,想不通. 链表和数组一样都是存储数据,链表是非连续,非顺序存储结构. 链表是灵活内存动态管理(随机...

    c语言链表

    1. 链表介绍

    c语言的单向链表翻转是面试官常问问题之一,故此,咱就谈一谈,链表并不是如此可怕,学不会,想不通.

    链表和数组一样都是存储数据,链表是非连续,非顺序的存储结构.

    链表是灵活的内存动态管理(随机分配空间),删除创建结点非常方便

    链表组成:由一系列结点组成.

    链表结点:实际上是结构体变量.

    typedef struct _LINKNODE

    {

    int data;// 数据域

    struct _LINKNODE *next;// 指针域

    }Link_Node;

    链表结点包含两个部分:

    1.存储数据元素的数据域(结构体),

    2.存储下一个结点地址的指针域.

    clip_image002

    上图中的就是一个简单的单向链表,明白了单向链表就可以进军其余的链表结构了,都是一一相通的.

    结点:data数据域就是存放的结构体(含有各种数据),或者理解为int data;

    next就是链表的核心了,就是一个指针,指向下一个结点,与下一个结点建立联系.

    2. 链表和数组的区别

    数组:一次性分配连续的存储区域,int num[60] = {0};

    优点:随机访问元素效率高

    缺点:

    l 开辟内存过大时,易分配失败

    l 插入和删除元素效率低下

    链表:无需一次性分配连续的存储空间,只需要分配n快结点存储区域,通过指针建立联系

    优点:

    l 不需要一次性分配连续的存储区域

    l 删除和插入效率高

    缺点:

    随机访问元素效率低

    3. 链表分类

    l 1. 静态链表和动态链表

    链表按照线性表链式存储结构分为静态链表和动态链表

    静态链表:是在初始化的时候分配好足够的内存空间,存储空间是静态的,分配在栈上,模拟数组实现的,是顺序的存储结构

    动态链表:是动态申请内存的,每个节点物理地址不连续

    静态链表实例:

    #pragma warning(disable:4996)

    #include <stdio.h>

    #include <stdlib.h>

    #include <string.h>

    // 定义链表结点

    typedef struct _LINKNODE

    {

    int data;// 数据域

    struct _LINKNODE *next;// 指针域

    }Link_Node;

    int main(int argc, char *argv[])

    {

    // 初始化三个链表结点(结构体)

    Link_Node Node1 = {1,NULL};

    Link_Node Node2 = {2,NULL};

    Link_Node Node3 = {3,NULL};

    // 链表串联起来,第一个结点指向第二个

    Node1.next = &Node2;// Node1的next指针指向Node2

    Node2.next = &Node3;

    Node3.next = NULL;// 尾结点

    // 定义头结点,指向第一个结点

    Link_Node *head = &Node1;

    // 遍历链表,头结点-->尾结点

    while (head != NULL)

    {

    printf("data : [ %d ]\n",head->data);

    // 指针下移

    head = head->next;

    }

    printf("hello...\n");

    system("pause");

    return 0;

    }

    动态链表实例:

    #pragma warning(disable:4996)

    #include <stdio.h>

    #include <stdlib.h>

    #include <string.h>

    // 定义链表结点

    typedef struct _LINKNODE

    {

    int data;// 数据域

    struct _LINKNODE *next;// 指针域

    }Link_Node;

    int main(int argc, char *argv[])

    {

    // 动态申请3个结点

    Link_Node *Node1 = (Link_Node *)malloc(sizeof(Link_Node));

    // 初始化数据域

    Node1->data = 1;// Node是指针所以用指向箭头

    Link_Node *Node2 = (Link_Node *)malloc(sizeof(Link_Node));

    Node2->data = 2;

    Link_Node *Node3 = (Link_Node *)malloc(sizeof(Link_Node));

    Node3->data = 3;

    // 建立结点关系

    Node1->next = Node2;// Node1的next指向Node2;

    Node2->next = Node3;

    Node3->next = NULL;

    // 定义头结点指向第一个结点Node1

    Link_Node *head = Node1;

    // 遍历链表

    while (head != NULL)

    {

    printf("data:[ %d ]\n",head->data);

    // 指针下移

    head = head->next;

    }

    printf("hello...\n");

    system("pause");

    return 0;

    }

    l 2. 带头链表和不带头链表

    n 带头链表:固定一个节点作为头结点,不关心数据域,起一个标志位的作用,链表结点如何变化,此头结点固定不变

    clip_image004

    n 不带头结点:头结点不固定,所有结点都可以作为头,可以随机变化

    clip_image006

    链表按照类型:又划分为:单链表,双链表,循环链表

    单向链表:

    clip_image006[1]

    双向链表:

    clip_image008

    循环链表:

    clip_image010

    双向循环链表

    clip_image012

    4. 链表的基本操作à基于单向链表

    1. 创建链表结点域

    链表结点:数据域和指针域à结构体

    typedef struct _LINKNODE

    {

    int data;// 数据域

    struct _LINKNODE *next;// 指针域

    }Link_Node;

    2. 创建链表

    建立带头结点的单向链表,循环创建结点,结点数值为<=0时,作为结束,链表的头结点地址作为函数值返回.

    Link_Node* Init_Link_Node()

    {

    Link_Node *cur = NULL;// 保存上一个结点

    Link_Node *pNew = NULL;// 辅助指针

    Link_Node *head = NULL;// 固定为头结点

    // 创建头结点

    pNew = (Link_Node *)malloc(sizeof(Link_Node));

    // 初始化头结点(有头结点不保证数据安全)

    pNew->data = -1;

    pNew->next = NULL;

    head = cur = pNew;// head作为头结点,cur保存结点

    // 循环创建结点

    int dataid = 0;

    while (1)

    {

    printf("请输入data id编号:");

    scanf("%d",&dataid);

    if (dataid <= 0)

    {

    break;// 跳出循环

    }

    // 创建新结点

    pNew = (Link_Node *)malloc(sizeof(Link_Node));

    pNew->data = dataid;

    // 建立关联,头结点指向新结点

    cur->next = pNew;// 此时head已经指向了新结点

    pNew->next = NULL;

    cur = pNew;// 指针下移

    }

    return head;

    }

    3. 遍历链表

    // 遍历结点,传入链表

    int Print_Link_Node(Link_Node *head)

    {

    if (head == NULL)

    {

    return -1;

    }

    // 保存链表(带头链表的除了头之外的链表)

    Link_Node *cur = head->next;

    printf("head --> ");

    while (cur != NULL)

    {

    // 打印结点数据域

    printf("%d --> ",cur->data);

    // 指针下移操作

    cur = cur->next;

    }

    printf("NULL \n");// cur指向了NULL

    }

    4. 在头部插入结点

    // 头插法

    void Init_Head_Link_Node(Link_Node *head,int dataid)

    {

    if (head == NULL)

    {

    return;

    }

    // 保存第一个有效结点

    Link_Node *cur = head->next;

    // 创建新结点

    Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));

    pNew->data = dataid;

    // 建立关系

    head->next = pNew;

    pNew->next = cur;

    }

    5.尾部插入

    // 尾插法

    void Init_Tail_Link_Node(Link_Node *head,int dataid)

    {

    if (head == NULL)

    {

    return;

    }

    // 保存结点,获取最后一个结点

    Link_Node *cur = head;

    while (cur->next != NULL)

    {

    // 结点后移

    cur = cur->next;

    }

    // 创建新结点,插入

    Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));

    pNew->data = dataid;

    // 尾结点的next指向新结点

    cur->next = pNew;

    // 新结点的next指向NULL

    pNew->next = NULL;

    }

    6.指定位置

    // 找到data为num的前面插入,找不到就尾插

    void Init_Insert_Link_Node(Link_Node *head,int num,int dataid)

    {

    if (head == NULL)

    {

    return;

    }

    // cur为第一个有效结点

    Link_Node *cur = head->next;

    Link_Node *pre = head;//保存前结点

    while (cur != NULL)

    {

    if (cur->data == num)

    {

    break;

    }

    // 循环查找data

    // 指针下移

    pre = pre->next;

    cur = cur->next;

    }

    // 1.找到匹配结点,cur为匹配结点,pre为上一个结点

    // 2.没有找到,说明cur指向NULL,pre为cur的上一个结点

    // pre->next = cur

    // cur = NULL

    // 插入新结点

    Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));

    pNew->data = dataid;

    // 尾结点的next指向新结点

    pre->next = pNew;

    // 新结点的next指向NULL

    pNew->next = cur;

    }

    7. 删除指定data第一个值

    // 删除指定data第一个值

    void Del_Link_Node(Link_Node *head,int dataid)

    {

    if (head == NULL)

    {

    return;

    }

    // cur为第一个有效结点

    Link_Node *cur = head->next;

    // pre保存cur的上个结点

    Link_Node *pre = head;

    // 没有找到匹配结点,1代表找到

    int flag = 0;

    while (cur != NULL)

    {

    if (cur->data == dataid)

    {

    // 找到匹配结点

    flag = 1;

    pre->next = cur->next;

    free(cur);

    cur = NULL;

    break;

    }

    pre = pre->next;

    cur = cur->next;

    }

    if (0 == flag)

    {

    printf("没有找到%d的结点\n",dataid);

    }

    }

    8.释放链表

    // 清空链表

    void Destroy_Link_Node(Link_Node *head)

    {

    Link_Node *cur = head;

    while (cur->next != NULL)

    {

    // 先保存下一个结点

    head = head->next;

    // 释放第一个结点

    free(cur);

    cur = NULL;

    // 当前结点下移

    cur = head;

    }

    printf("链表清空\n");

    }

    9.main函数

    int main(int argc, char *argv[])

    {

    // 创建链表

    Link_Node *headLink_Node = Init_Link_Node();

    Print_Link_Node(headLink_Node);

    // 头插

    Init_Head_Link_Node(headLink_Node,1111);

    // 尾插法

    Init_Tail_Link_Node(headLink_Node,2222);

    Print_Link_Node(headLink_Node);

    // 查找4,插入

    Init_Insert_Link_Node(headLink_Node,4,3333);

    Print_Link_Node(headLink_Node);

    // 删除2

    Del_Link_Node(headLink_Node,2);

    Print_Link_Node(headLink_Node);

    // 清空链表

    Destroy_Link_Node(headLink_Node);

    printf("hello...\n");

    system("pause");

    return 0;

    }

    展开全文
  • 链表概述 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放一个地址。...链表的各类操作包括:学习单向链表的创建

    链表概述

    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”,每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址。因此,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。

    链表的各类操作包括:学习单向链表的创建、删除、 插入(无序、有序)、输出、 排序(选择、插入、冒泡)、反序等等。

    单向链表的图示:

    ---->[NULL]

    head

    图1:空链表

    ---->[p1]---->[p2]…---->[pn]---->[NULL]

    head p1->next p2->next pn->next

    图2:有N个节点的链表

    创建n个节点的链表的函数为:

    #include “stdlib.h”

    #include “stdio.h”

    #define NULL 0

    #define LEN sizeof(struct student)

    struct student

    {

    int num; //学号

    float score; //分数,其他信息可以继续在下面增加字段

    struct student *next; //指向下一节点的指针

    };

    int n; //节点总数

    /*

    ==========================

    功能:创建n个节点的链表

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Create()

    {

    struct student *head; //头节点

    struct student *p1 = NULL; //p1保存创建的新节点的地址

    struct student *p2 = NULL; //p2保存原链表最后一个节点的地址

    n = 0; //创建前链表的节点总数为0:空链表

    p1 = (struct student *) malloc (LEN); //开辟一个新节点

    p2 = p1; //如果节点开辟成功,则p2先把它的指针保存下来以备后用

    if(p1==NULL) //节点开辟不成功

    {

    printf ("\nCann’t create it, try it again in a moment!\n");

    return NULL;

    }

    else //节点开辟成功

    {

    head = NULL; //开始head指向NULL

    printf ("Please input %d node – num,score: ", n + 1);

    scanf ("%d %f", &(p1->num), &(p1->score)); //录入数据

    }

    while(p1->num != 0) //只要学号不为0,就继续录入下一个节点

    {

    n += 1; //节点总数增加1个

    if(n == 1) //如果节点总数是1,则head指向刚创建的节点p1

    {

    head = p1;

    p2->next = NULL; //此时的p2就是p1,也就是p1->next指向NULL。

    }

    else

    {

    p2->next = p1; //指向上次下面刚刚开辟的新节点

    }

    p2 = p1; //把p1的地址给p2保留,然后p1产生新的节点

    p1 = (struct student *) malloc (LEN);

    printf ("Please input %d node – num,score: ", n + 1);

    scanf ("%d %f", &(p1->num), &(p1->score));

    }

    p2->next = NULL; //此句就是根据单向链表的最后一个节点要指向NULL

    free(p1); //p1->num为0的时候跳出了while循环,并且释放p1

    p1 = NULL; //特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针",即地址不确定的指针

    return head; //返回创建链表的头指针

    }

    输出链表中节点的函数为:

    /*

    ===========================

    功能:输出节点

    返回: void

    ===========================

    */

    void Print(struct student *head)

    {

    struct student *p;

    printf ("\nNow , These %d records are:\n", n);

    p = head;

    if(head != NULL) //只要不是空链表,就输出链表中所有节点

    {

    printf(“head is %o\n”, head); //输出头指针指向的地址

    do

    {

    /*

    输出相应的值:当前节点地址、各字段值、当前节点的下一节点地址。

    这样输出便于读者形象看到一个单向链表在计算机中的存储结构,和我们

    设计的图示是一模一样的。

    */

    printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);

    p = p->next; //移到下一个节点

    }

    while (p != NULL);

    }

    }

    单向链表的删除图示:

    ---->[NULL]

    head

    图3:空链表

    从图3可知,空链表显然不能删除

    ---->[1]---->[2]…---->[n]---->NULL

    head 1->next 2->next n->next

    ---->[2]…---->[n]---->NULL

    head 2->next n->next

    图4:有N个节点的链表,删除第一个节点

    结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:

    1、你要明白head就是第1个节点,head->next就是第2个节点;

    2、删除后head指向第2个节点,就是让head=head->next,OK这样就行了。

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    ---->[1]---->[3]…---->[n]---->NULL

    head 1->next 3->next n->next

    图5:有N个节点的链表,删除中间一个(这里图示删除第2个)

    结合原链表和删除后的链表,就很容易写出相应的代码。操作方法如下:

    1、你要明白head就是第1个节点,1->next就是第2个节点,2->next就是第3个节点;

    2、删除后2,1指向第3个节点,就是让1->next=2->next。

    删除指定学号的节点的函数为:

    /*

    ==========================

    功能:删除指定节点

    (此例中是删除指定学号的节点)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Del (struct student *head, int num)

    {

    struct student *p1; //p1保存当前需要检查的节点的地址

    struct student *p2; //p2保存当前检查过的节点的地址

    if (head == NULL) //是空链表(结合图3理解)

    {

    printf ("\nList is null!\n");

    return head;

    }

    //定位要删除的节点

    p1 = head;

    while (p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的,并且它不是最后一个节点,就继续往下找

    {

    p2 = p1; //保存当前节点的地址

    p1 = p1->next; //后移一个节点

    }

    if(p1->num==num) //找到了。(结合图4、5理解)

    {

    if (p1 == head) //如果要删除的节点是第一个节点

    {

    head = p1->next; //头指针指向第一个节点的后一个节点,也就是第二个节点。这样第一个节点就不在链表中,即删除

    }

    else //如果是其它节点,则让原来指向当前节点的指针,指向它的下一个节点,完成删除

    {

    p2->next = p1->next;

    }

    free (p1); //释放当前节点

    p1 = NULL;

    printf ("\ndelete %ld success!\n", num);

    n -= 1; //节点总数减1个

    }

    else //没有找到

    {

    printf ("\n%ld not been found!\n", num);

    }

    return head;

    }

    单向链表的插入图示:

    ---->NULL

    head

    ---->[1]---->NULL

    head 1->next

    图7 空链表插入一个节点

    结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:

    1、你要明白空链表head指向NULL就是head=NULL;

    2、插入后head指向第1个节点,就是让head=1,1->next=NULL,OK这样就行了。

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    ---->[1]---->[2]---->[x]---->[3]…---->[n]---->NULL

    head 1->next 2->next x->next 3->next n->next

    图8:有N个节点的链表,插入一个节点(这里图示插入第2个后面)

    结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:

    1、你要明白原1->next就是节点2,2->next就是节点3;

    2、插入后x指向第3个节点,2指向x,就是让x->next=2->next,1->next=x。

    插入指定节点的后面的函数为:

    /*

    ==========================

    功能:插入指定节点的后面

    (此例中是指定学号的节点)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Insert (struct student *head, int num, struct student *node)

    {

    struct student *p1; //p1保存当前需要检查的节点的地址

    if (head == NULL) //(结合图示7理解)

    {

    head = node;

    node->next = NULL;

    n += 1;

    return head;

    }

    p1 = head;

    while(p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的,并且它不是最后一个节点,继续往下找

    {

    p1 = p1->next; //后移一个节点

    }

    if (p1->num==num) //找到了(结合图示8理解)

    {

    node->next = p1->next; //显然node的下一节点是原p1的next

    p1->next = node; //插入后,原p1的下一节点就是要插入的node

    n += 1; //节点总数增加1个

    }

    else

    {

    printf ("\n%ld not been found!\n", num);

    }

    return head;

    }

    单向链表的反序图示:

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    [NULL]<----[1]<----[2]<----[3]<----…[n]<----(反序后的链表)

    1->next 2->next 3->next n->next head

    图9:有N个节点的链表反序

    结合原链表和插入后的链表,就很容易写出相应的代码。操作方法如下:

    1、我们需要一个读原链表的指针p2,存反序链表的p1=NULL(刚好最后一个节点的next为NULL),还有一个临时存储变量p;

    2、p2在原链表中读出一个节点,我们就把它放到p1中,p就是用来处理节点放置顺序的问题;

    3、比如,现在我们取得一个2,为了我们继续往下取节点,我们必须保存它的next值,由原链表可知p=2->next;

    4、然后由反序后的链表可知,反序后2->next要指向1,则2->next=1;

    5、好了,现在已经反序一个节点,接着处理下一个节点就需要保存此时的信息:

    p1变成刚刚加入的2,即p1=2;p2要变成它的下一节点,就是上面我们保存的p,即p2=p。

    反序链表的函数为:

    /*

    ==========================

    功能:反序节点

    (链表的头变成链表的尾,链表的尾变成头)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Reverse (struct student *head)

    {

    struct student *p; //临时存储

    struct student *p1; //存储返回结果

    struct student *p2; //源结果节点一个一个取

    p1 = NULL; //开始颠倒时,已颠倒的部分为空

    p2 = head; //p2指向链表的头节点

    while(p2 != NULL)

    {

    p = p2->next;

    p2->next = p1;

    p1 = p2;

    p2 = p;

    }

    head = p1;

    return head;

    }

    对链表进行选择排序的基本思想就是反复从还未排好序的那些节点中,选出键值(就是用它排序的字段,我们取学号num为键值)最小的节点,依次重新组合成一个链表。

    我认为写链表这类程序,关键是理解:head存储的是第一个节点的地址,head->next存储的是第二个节点的地址;任意一个节点p的地址,只能通过它前一个节点的next来求得。

    单向链表的选择排序图示:

    ---->[1]---->[3]---->[2]…---->[n]---->NULL

    head 1->next 3->next 2->next n->next

    ---->NULL

    first

    tail

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    first 1->next 2->next 3->next tail->next

    图10:有N个节点的链表选择排序

    1、先在原链表中找最小的,找到一个后就把它放到另一个空的链表中;

    2、空链表中安放第一个进来的节点,产生一个有序链表,并且让它在原链表中分离出来(此时要注意原链表中出来的是第一个节点还是中间其它节点);

    3、继续在原链表中找下一个最小的,找到后把它放入有序链表的尾指针的next,然后它变成其尾指针;

    对链表进行选择排序的函数为:

    ==========================

    */

    struct student *SelectSort (struct student *head)

    {

    struct student *first; //排列后有序链的表头指针

    struct student *tail; //排列后有序链的表尾指针

    struct student *p_min; //保留键值更小的节点的前驱节点的指针

    struct student *min; //存储最小节点

    struct student *p; //当前比较的节点

    first = NULL;

    while(head != NULL) //在链表中找键值最小的节点

    {

    //注意:这里for语句就是体现选择排序思想的地方

    for (p = head, min = head; p->next != NULL; p = p->next) //循环遍历链表中的节点,找出此时最小的节点

    {

    if (p->next->num < min->num) //找到一个比当前min小的节点

    {

    p_min = p; //保存找到节点的前驱节点:显然p->next的前驱节点是p

    min = p->next; //保存键值更小的节点

    }

    }

    //上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表

    //第一件事

    if (first == NULL) //如果有序链表目前还是一个空链表

    {

    first = min; //第一次找到键值最小的节点

    tail = min; //注意:尾指针让它指向最后的一个节点

    }

    else //有序链表中已经有节点

    {

    tail->next = min; //把刚找到的最小节点放到最后,即让尾指针的next指向它

    tail = min; //尾指针也要指向它

    }

    //第二件事

    if (min == head) //如果找到的最小节点就是第一个节点

    {

    head = head->next; //显然让head指向原head->next,即第二个节点,就OK

    }

    else //如果不是第一个节点

    {

    p_min->next = min->next; //前次最小节点的next指向当前min的next,这样就让min离开了原链表

    }

    }

    if (first != NULL) //循环结束得到有序链表first

    {

    tail->next = NULL; //单向链表的最后一个节点的next应该指向NULL

    }

    head = first;

    return head;

    }

    对链表进行直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值(就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次对链表从头到尾执行一遍,就可以使无序链表变为有序链表。

    单向链表的直接插入排序图示:

    ---->[1]---->[3]---->[2]…---->[n]---->NULL

    head 1->next 3->next 2->next n->next

    ---->[1]---->NULL

    head

    图11

    ---->[3]---->[2]…---->[n]---->NULL

    first 3->next 2->next n->next

    图12

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    图13:有N个节点的链表直接插入排序

    1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。

    2、从图12链表中取节点,到图11链表中定位插入。

    3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。

    这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。

    对链表进行直接插入排序的函数为:

    /*

    ==========================

    功能:直接插入排序(由小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *InsertSort (struct student *head)

    {

    struct student *first; //为原链表剩下用于直接插入排序的节点头指针

    struct student *t; //临时指针变量:插入节点

    struct student *p,*q; //临时指针变量

    first = head->next; //原链表剩下用于直接插入排序的节点链表:可根据图12来理解

    head->next = NULL; //只含有一个节点的链表的有序链表:可根据图11来理解

    while(first != NULL) //遍历剩下无序的链表

    {

    //注意:这里for语句就是体现直接插入排序思想的地方

    for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //无序节点在有序链表中找插入的位置

    //退出for循环,就是找到了插入的位置,应该将t节点插入到p节点之后,q节点之前

    //注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了

    //下面的插入就是将t节点即是first节点插入到p节点之后,已经改变了first节点,所以first节点应该在被修改之前往后移动,不能放到下面注释的位置上去

    first = first->next; //无序链表中的节点离开,以便它插入到有序链表中

    if (q == head) //插在第一个节点之前

    {

    head = t;

    }

    else //p是q的前驱

    {

    p->next = t;

    }

    t->next = q; //完成插入动作

    //first = first->next;

    }

    return head;

    }

    对链表进行冒泡排序的基本思想就是对当前还未排好序的范围内的全部节点,自上而下对相邻的两个节点依次进行比较和调整,让键值(就是用它排 序的字段,我们取学号num为键值)较大的节点往下沉,键值较小的往上冒。即:每当两相邻的节点比较后发现它们的排序与排序要求相反时,就将它们互换。

    单向链表的冒泡排序图示:

    ---->[1]---->[3]---->[2]…---->[n]---->NULL

    head 1->next 3->next 2->next n->next

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    图14:有N个节点的链表冒泡排序

    任意两个相邻节点p、q位置互换图示:

    假设p1->next指向p,那么显然p1->next->next就指向q,

    p1->next->next->next就指向q的后继节点,我们用p2保存

    p1->next->next指针。即:p2=p1->next->next,则有:

    [ ]---->[p]---------->[q]---->

    p1->next p1->next->next p2->next

    图15

    [ ]---->[q]---------->[p]---->

    图16

    1、排序后q节点指向p节点,在调整指向之前,我们要保存原p的指向节点地址,即:p2=p1->next->next;

    2、顺着这一步一步往下推,排序后图16中p1->next->next要指的是p2->next,所以p1->next->next=p2->next;

    3、在图15中p2->next原是q发出来的指向,排序后图16中q的指向要变为指向p的,而原来p1->next是指向p的,所以p2->next=p1->next;

    4、在图15中p1->next原是指向p的,排序后图16中p1->next要指向q,原来p1->next->next(即p2)是指向q的,所以p1->next=p2;

    5、至此,我们完成了相邻两节点的顺序交换。

    6、下面的程序描述改进了一点就是记录了每次最后一次节点下沉的位置,这样我们不必每次都从头到尾的扫描,只需要扫描到记录点为止。 因为后面的都已经是排好序的了。

    对链表进行冒泡排序的函数为:

    /*

    ==========================

    功能:冒泡排序(由小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *BubbleSort (struct student *head)

    {

    struct student *endpt; //控制循环比较

    struct student *p; //临时指针变量

    struct student *p1,*p2;

    p1 = (struct student *) malloc (LEN);

    p1->next = head; //注意理解:我们增加一个节点,放在第一个节点的前面,主要是为了便于比较。因为第一个节点没有前驱,我们不能交换地址

    head = p1; //让head指向p1节点,排序完成后,我们再把p1节点释放掉

    for (endpt = NULL; endpt != head; endpt = p) //结合第6点理解

    {

    for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)

    {

    if (p1->next->num > p1->next->next->num) //如果前面的节点键值比后面节点的键值大,则交换

    {

    p2 = p1->next->next; //结合第1点理解

    p1->next->next = p2->next; //结合第2点理解

    p2->next = p1->next; //结合第3点理解

    p1->next = p2; //结合第4点理解

    p = p1->next->next; //结合第6点理解

    }

    }

    }

    p1 = head; //把p1的信息去掉

    head = head->next; //让head指向排序后的第一个节点

    free (p1); //释放p1

    p1 = NULL; //p1置为NULL,保证不产生“野指针”,即地址不确定的指针变量

    return head;

    }

    有序链表插入节点示意图:

    ---->NULL

    head

    图18:空有序链表(空有序链表好解决,直接让head指向它就是了。)

    以下讨论不为空的有序链表。

    ---->[1]---->[2]---->[3]…---->[n]---->NULL

    head 1->next 2->next 3->next n->next

    图18:有N个节点的有序链表

    插入node节点的位置有两种情况:一是第一个节点前,二是其它节点前或后。

    ---->[node]---->[1]---->[2]---->[3]…---->[n]---->[NULL]

    head node->next 1->next 2->next 3->next n->next

    图19:node节点插在第一个节点前

    ---->[1]---->[2]---->[3]…---->[node]…---->[n]---->[NULL]

    head 1->next 2->next 3->next node->next n->next

    插入有序链表的函数为:

    /*

    ==========================

    功能:插入有序链表的某个节点的后面(从小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *SortInsert (struct student *head, struct student *node)

    {

    struct student *p; //p保存当前需要检查的节点的地址

    struct student *t; //临时指针变量

    if (head == NULL) //处理空的有序链表

    {

    head = node;

    node->next = NULL;

    n += 1; //插入完毕,节点总数加

    return head;

    }

    p = head; //有序链表不为空

    while(p->num < node->num && p != NULL) //p指向的节点的学号比插入节点的学号小,并且它不等于NULL

    {

    t = p; //保存当前节点的前驱,以便后面判断后处理

    p = p->next; //后移一个节点

    }

    if (p == head) //刚好插入第一个节点之前

    {

    node->next = p;

    head = node;

    }

    else //插入其它节点之后

    {

    t->next = node; //把node节点加进去

    node->next = p;

    }

    n += 1; //插入完毕,节点总数加1

    return head;

    }

    综上所述,链表的各类操作函数的完整代码如下:

    #include “stdlib.h”

    #include “stdio.h”

    #define NULL 0

    #define LEN sizeof(struct student)

    struct student

    {

    int num; //学号

    float score; //分数,其他信息可以继续在下面增加字段

    struct student *next; //指向下一节点的指针

    };

    int n; //节点总数

    /*

    ==========================

    功能:创建n个节点的链表

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Create()

    {

    struct student *head; //头节点

    struct student *p1 = NULL; //p1保存创建的新节点的地址

    struct student *p2 = NULL; //p2保存原链表最后一个节点的地址

    n = 0; //创建前链表的节点总数为0:空链表

    p1 = (struct student *) malloc (LEN); //开辟一个新节点

    p2 = p1; //如果节点开辟成功,则p2先把它的指针保存下来以备后用

    if(p1==NULL) //节点开辟不成功

    {

    printf ("\nCann’t create it, try it again in a moment!\n");

    return NULL;

    }

    else //节点开辟成功

    {

    head = NULL; //开始head指向NULL

    printf ("Please input %d node – num,score: ", n + 1);

    scanf ("%d %f", &(p1->num), &(p1->score)); //录入数据

    }

    while(p1->num != 0) //只要学号不为0,就继续录入下一个节点

    {

    n += 1; //节点总数增加1个

    if(n == 1) //如果节点总数是1,则head指向刚创建的节点p1

    {

    head = p1;

    p2->next = NULL; //此时的p2就是p1,也就是p1->next指向NULL。

    }

    else

    {

    p2->next = p1; //指向上次下面刚刚开辟的新节点

    }

    p2 = p1; //把p1的地址给p2保留,然后p1产生新的节点

    p1 = (struct student *) malloc (LEN);

    printf ("Please input %d node – num,score: ", n + 1);

    scanf ("%d %f", &(p1->num), &(p1->score));

    }

    p2->next = NULL; //此句就是根据单向链表的最后一个节点要指向NULL

    free(p1); //p1->num为0的时候跳出了while循环,并且释放p1

    p1 = NULL; //特别不要忘记把释放的变量清空置为NULL,否则就变成"野指针",即地址不确定的指针

    return head; //返回创建链表的头指针

    }

    /*

    ===========================

    功能:输出节点

    返回: void

    ===========================

    */

    void Print(struct student *head)

    {

    struct student *p;

    printf ("\nNow , These %d records are:\n", n);

    p = head;

    if(head != NULL) //只要不是空链表,就输出链表中所有节点

    {

    printf(“head is %o\n”, head); //输出头指针指向的地址

    do

    {

    /*

    输出相应的值:当前节点地址、各字段值、当前节点的下一节点地址。

    这样输出便于读者形象看到一个单向链表在计算机中的存储结构,和我们

    设计的图示是一模一样的。

    */

    printf ("%o %d %5.1f %o\n", p, p->num, p->score, p->next);

    p = p->next; //移到下一个节点

    }

    while (p != NULL);

    }

    }

    /*

    ==========================

    功能:删除指定节点

    (此例中是删除指定学号的节点)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Del (struct student *head, int num)

    {

    struct student *p1; //p1保存当前需要检查的节点的地址

    struct student *p2; //p2保存当前检查过的节点的地址

    if (head == NULL) //是空链表(结合图3理解)

    {

    printf ("\nList is null!\n");

    return head;

    }

    //定位要删除的节点

    p1 = head;

    while (p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的,并且它不是最后一个节点,就继续往下找

    {

    p2 = p1; //保存当前节点的地址

    p1 = p1->next; //后移一个节点

    }

    if(p1->num==num) //找到了。(结合图4、5理解)

    {

    if (p1 == head) //如果要删除的节点是第一个节点

    {

    head = p1->next; //头指针指向第一个节点的后一个节点,也就是第二个节点。这样第一个节点就不在链表中,即删除

    }

    else //如果是其它节点,则让原来指向当前节点的指针,指向它的下一个节点,完成删除

    {

    p2->next = p1->next;

    }

    free (p1); //释放当前节点

    p1 = NULL;

    printf ("\ndelete %ld success!\n", num);

    n -= 1; //节点总数减1个

    }

    else //没有找到

    {

    printf ("\n%ld not been found!\n", num);

    }

    return head;

    }

    //销毁链表

    void DestroyList(struct student *head)

    {

    struct student *p;

    if(head==NULL)

    return 0;

    while(head)

    {

    p=head->next;

    free(head);

    head=p;

    }

    return 1;

    }

    /*

    ==========================

    功能:插入指定节点的后面

    (此例中是指定学号的节点)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Insert (struct student *head, int num, struct student *node)

    {

    struct student *p1; //p1保存当前需要检查的节点的地址

    if (head == NULL) //(结合图示7理解)

    {

    head = node;

    node->next = NULL;

    n += 1;

    return head;

    }

    p1 = head;

    while(p1->num != num && p1->next != NULL) //p1指向的节点不是所要查找的,并且它不是最后一个节点,继续往下找

    {

    p1 = p1->next; //后移一个节点

    }

    if (p1->num==num) //找到了(结合图示8理解)

    {

    node->next = p1->next; //显然node的下一节点是原p1的next

    p1->next = node; //插入后,原p1的下一节点就是要插入的node

    n += 1; //节点总数增加1个

    }

    else

    {

    printf ("\n%ld not been found!\n", num);

    }

    return head;

    }

    /*

    ==========================

    功能:反序节点

    (链表的头变成链表的尾,链表的尾变成头)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *Reverse (struct student *head)

    {

    struct student *p; //临时存储

    struct student *p1; //存储返回结果

    struct student *p2; //源结果节点一个一个取

    p1 = NULL; //开始颠倒时,已颠倒的部分为空

    p2 = head; //p2指向链表的头节点

    while(p2 != NULL)

    {

    p = p2->next;

    p2->next = p1;

    p1 = p2;

    p2 = p;

    }

    head = p1;

    return head;

    }

    /*

    ==========================

    功能:选择排序(由小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *SelectSort (struct student *head)

    {

    struct student *first; //排列后有序链的表头指针

    struct student *tail; //排列后有序链的表尾指针

    struct student *p_min; //保留键值更小的节点的前驱节点的指针

    struct student *min; //存储最小节点

    struct student *p; //当前比较的节点

    first = NULL;

    while(head != NULL) //在链表中找键值最小的节点

    {

    //注意:这里for语句就是体现选择排序思想的地方

    for (p = head, min = head; p->next != NULL; p = p->next) //循环遍历链表中的节点,找出此时最小的节点

    {

    if (p->next->num < min->num) //找到一个比当前min小的节点

    {

    p_min = p; //保存找到节点的前驱节点:显然p->next的前驱节点是p

    min = p->next; //保存键值更小的节点

    }

    }

    //上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表

    //第一件事

    if (first == NULL) //如果有序链表目前还是一个空链表

    {

    first = min; //第一次找到键值最小的节点

    tail = min; //注意:尾指针让它指向最后的一个节点

    }

    else //有序链表中已经有节点

    {

    tail->next = min; //把刚找到的最小节点放到最后,即让尾指针的next指向它

    tail = min; //尾指针也要指向它

    }

    //第二件事

    if (min == head) //如果找到的最小节点就是第一个节点

    {

    head = head->next; //显然让head指向原head->next,即第二个节点,就OK

    }

    else //如果不是第一个节点

    {

    p_min->next = min->next; //前次最小节点的next指向当前min的next,这样就让min离开了原链表

    }

    }

    if (first != NULL) //循环结束得到有序链表first

    {

    tail->next = NULL; //单向链表的最后一个节点的next应该指向NULL

    }

    head = first;

    return head;

    }

    /*

    ==========================

    功能:直接插入排序(由小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *InsertSort (struct student *head)

    {

    struct student *first; //为原链表剩下用于直接插入排序的节点头指针

    struct student *t; //临时指针变量:插入节点

    struct student *p,*q; //临时指针变量

    first = head->next; //原链表剩下用于直接插入排序的节点链表:可根据图12来理解

    head->next = NULL; //只含有一个节点的链表的有序链表:可根据图11来理解

    while(first != NULL) //遍历剩下无序的链表

    {

    //注意:这里for语句就是体现直接插入排序思想的地方

    for (t = first, q = head; ((q != NULL) && (q->num < t->num)); p = q, q = q->next); //无序节点在有序链表中找插入的位置

    //退出for循环,就是找到了插入的位置,应该将t节点插入到p节点之后,q节点之前

    //注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了

    //下面的插入就是将t节点即是first节点插入到p节点之后,已经改变了first节点,所以first节点应该在被修改之前往后移动,不能放到下面注释的位置上去

    first = first->next; //无序链表中的节点离开,以便它插入到有序链表中

    if (q == head) //插在第一个节点之前

    {

    head = t;

    }

    else //p是q的前驱

    {

    p->next = t;

    }

    t->next = q; //完成插入动作

    //first = first->next;

    }

    return head;

    }

    /*

    ==========================

    功能:冒泡排序(由小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *BubbleSort (struct student *head)

    {

    struct student *endpt; //控制循环比较

    struct student *p; //临时指针变量

    struct student *p1,*p2;

    p1 = (struct student *) malloc (LEN);

    p1->next = head; //注意理解:我们增加一个节点,放在第一个节点的前面,主要是为了便于比较。因为第一个节点没有前驱,我们不能交换地址

    head = p1; //让head指向p1节点,排序完成后,我们再把p1节点释放掉

    for (endpt = NULL; endpt != head; endpt = p) //结合第6点理解

    {

    for (p = p1 = head; p1->next->next != endpt; p1 = p1->next)

    {

    if (p1->next->num > p1->next->next->num) //如果前面的节点键值比后面节点的键值大,则交换

    {

    p2 = p1->next->next; //结合第1点理解

    p1->next->next = p2->next; //结合第2点理解

    p2->next = p1->next; //结合第3点理解

    p1->next = p2; //结合第4点理解

    p = p1->next->next; //结合第6点理解

    }

    }

    }

    p1 = head; //把p1的信息去掉

    head = head->next; //让head指向排序后的第一个节点

    free (p1); //释放p1

    p1 = NULL; //p1置为NULL,保证不产生“野指针”,即地址不确定的指针变量

    return head;

    }

    /*

    ==========================

    功能:插入有序链表的某个节点的后面(从小到大)

    返回:指向链表表头的指针

    ==========================

    */

    struct student *SortInsert (struct student *head, struct student *node)

    {

    struct student *p; //p保存当前需要检查的节点的地址

    struct student *t; //临时指针变量

    if (head == NULL) //处理空的有序链表

    {

    head = node;

    node->next = NULL;

    n += 1; //插入完毕,节点总数加

    return head;

    }

    p = head; //有序链表不为空

    while(p->num < node->num && p != NULL) //p指向的节点的学号比插入节点的学号小,并且它不等于NULL

    {

    t = p; //保存当前节点的前驱,以便后面判断后处理

    p = p->next; //后移一个节点

    }

    if (p == head) //刚好插入第一个节点之前

    {

    node->next = p;

    head = node;

    }

    else //插入其它节点之后

    {

    t->next = node; //把node节点加进去

    node->next = p;

    }

    n += 1; //插入完毕,节点总数加1

    return head;

    }

    /*

    以上函数的测试程序:

    提示:根据测试函数的不同注释相应的程序段,这也是一种测试方法。

    */

    int main(void)

    {

    struct student *head;

    struct student *stu;

    int thenumber;

    // 测试Create()、Print()

    head = Create();

    Print(head);

    //测试Del()

    printf("\nWhich one delete: ");

    scanf("%d",&thenumber);

    head = Del(head,thenumber);

    Print(head);

    //测试Insert()

    stu = (struct student *)malloc(LEN);

    printf("\nPlease input insert node – num,score: ");

    scanf("%d %f",&stu->num,&stu->score);

    printf("\nInsert behind num: ");

    scanf("%d",&thenumber);

    head = Insert(head,thenumber,stu);

    Print(head);

    //测试Reverse()

    printf("\nReverse the LinkList: \n");

    head = Reverse(head);

    Print(head);

    //测试SelectSort()

    printf("\nSelectSort the LinkList: \n");

    head = SelectSort(head);

    Print(head);

    //测试InsertSort()

    printf("\nInsertSort the LinkList: \n");

    head = InsertSort(head);

    Print(head);

    //测试BubbleSort()

    printf("\nBubbleSort the LinkList: \n");

    head = BubbleSort(head);

    Print(head);

    printf("\nSortInsert the LinkList: \n");

    //测试SortInsert():上面创建链表,输入节点时请注意学号num从小到大的顺序

    stu = (struct student *)malloc(LEN);

    printf("\nPlease input insert node – num,score: ");

    scanf("%d %f",&stu->num,&stu->score);

    head = SortInsert(head,stu);

    Print(head);

    //销毁链表

    DestroyList(head);

    printf ("\n");

    system (“pause”);

    }

    最后呢在给大家分享一个链表的视频资料,如果看文字懵的话可以参考这个

    C语言玩转链表

    http://www.makeru.com.cn/live/1392_338.html?s=45051

    数据类型、常量、变量及运算符

    http://www.makeru.com.cn/video/1877.html?s=45051

    C语言与数据结构的经典实战案例

    http://www.makeru.com.cn/live/5413_2014.html?s=45051

    提升C编程能力

    http://www.makeru.com.cn/live/1392_1166.html?s=45051

    夯实C语言,从小白到大牛的进阶之路!

    http://www.makeru.com.cn/live/5413_1980.html?s=45051

    指针

    http://www.makeru.com.cn/live/1392_238.html?s=45051

    指针换装你还认识吗

    http://www.makeru.com.cn/live/5413_2043.html?s=45051

    展开全文
  • c语言简单的链表详解

    2020-12-16 20:00:45
    详细解释了链表的基本操作,附有实例代码! +《链表——>小阿豪带你写链表》!!!!进入正文 1.首先,先想好自己要创建的链表格式以及最后的的显示界面!!! 2.主函数尽量放到后面写,前面写功能函数,在调用...
  • 1.首先,先想好自己要创建的链表格式以及最后的的显示界面!!! 2.主函数尽量放到后面写,前面写功能函数,在调用主函数之前要声明一下!! 3.先写链表主结构体,再写成员结构体,将成员结构体嵌入主结构体!!! ~...
                     +《链表——>小阿豪带你写链表》!!!!进入正文
    
    1.首先,先想好自己要创建的链表格式以及最后的的显示界面!!!
    2.主函数尽量放到后面写,前面写功能函数,在调用主函数之前要声明一下!!
    3.先写链表主结构体,再写成员结构体,将成员结构体嵌入主结构体!!!
    ~4.可以给你所需要的功能创建一个菜单,用switch-case语句实现功能!!!
    5.注意功能函数的放置次序,要不然会报错,必须声明!!!
    

    干货开始!!-》》》此处为伪代码内容
    例:
    0.先定义好你的成员结构体和主结构体//每一步都会用到!!!!

    struct student//定义学生信息系统结构体将其放到数据域中进行相应操作
    {
        char name[20];
        int num;
        int math;
    };
    struct node {             
        struct student data;             //数据域,用来存放数据
        struct node* next;    //指针域,用来存放下一个结构体的地址
    };
    

    1.struct node开始创建一个主结构体,//一个链表结构体至少有两个域->

     //struct student data;             //数据域,用来存放数据
        //struct node* next;    //指针域,用来存放下一个结构体的地址
    

    2.struct node* createList()//面向对象结构体类型//开始创建一个链表,创建链表前先创建一个空的指向指针节点,这是给链表节点进行初始化!!

        //该函数功能创建一个链表,给出一个链表开头空节点NULL
        //使用malloc函数去动态申请内存空间,标识符定义为newList(自己随便想一个标识符去定义,是给该链表申请一个结构体类型的内存)//struct node* newList = (struct node*)malloc(sizeof(struct node));
       //这一步不必写成员结构体,因为头空节点就是用来存放头节点的地址的,利用头插法每当插入一个元素就让头空节点去指向这个插入节点的地址(即这个新的头节点地址)!!!!
       //newList->next = NULL;//让该链表头空节点指向0地址NULL,下一次创建好链表头节点(创建链表节点,给链表第一个数据节点为NULL)后将头节点地址赋给它!!!
       //因为函数面向对象,创建完成后要return返回newList;
       //头空节点创建完成》》》》每当做完一个功能试运行调试!!!
    

    3.创建链表的第一个数据节点,并让头空节点指向它(注意头空节点永远指向头节点地址,临时操作改变之后也一定要连接回去)!!

      //将要创建的成员结构体类型用开始结构体创建时候的标识符号名形参传入
         //同样malloc函数去申请空间(这次的内存是给成员结构体申请的!),将该函数放在循环中即可连续添加成员!!!
         struct node* newNode = (struct node*)malloc(sizeof(struct student));
         //newNode->data=data;//让链表的data成员去标识你自己定义的成员结构体(即数据域!)
         //
         //newNode->next = NULL;//指针为空//尾巴节点的next永远指向空(即前闭后开)!!//该节点用头插法插入的话等下一个节点插入与他相连接之后就没它什么事了!!
         //因为函数面向对象,插入完成之后同样return返回要放在newList里面的这个节点newnode;
    

    4.打印函数提前写//为了调试方便》》》

     //void printfList(struct node* headNode)//把链表LIst传入该函数进行打印
       //struct node* pMove = headNode->next;定义一个主要结构体类型变量pMove把headNode(即->头空节点只不过是定义形参headNode来接收了newList)把头空节点的next(这个next里面存放的就是第一个节点的地址)赋给pMove,让他从第一个节点开始打印
       //自行设置要打印的格式,//pMove = pMove->next;将下一个节点的地址赋给当前游标pMove//放在循环里面让它一个一个成员遍历打印!!!
       //配合if语句调用主函数即可返回菜单!!!
    

    5.插入内容

      我给你写的直观一点,插入函数和插入内容没有放在一个函数中->认真看!!!
             1.先写一个插入函数去调用链表节点创建函数createNode()插入节点
                     void charu(struct node* headNode, struct student data)
                   //面向过程函数,使用形参传入要插的链表和要插入的数据
                       struct node* newNode = createNode(data);//调用创建节点函数去给要插入的数据申请一个位置来存放插入数据!!!
                    // newNode->next = headNode->next; 把头空节点的next的新插入节点相连!!!
                    //headNode->next = newNode;再把新节点地址放到头空节点的next里面去!!!!
             2.struct node* List = createList();//创建链表List;//在开始写添加成员函数时先定义一下你在整个过程中要用到的链表,此步调用创建链表函数来做!!!!!
               // 这步写添加成员函数,利用循环调用插入函数每当输入好一个成员信息就按回车连接到链表里面去作为新的头节点,每次缓冲区都留有一个回车符用setbuf(stdin,NULL);函数来清空缓冲区
    

    6.删除内容!!!

      // void shanchu(struct node* headNode, int num1)//面向过程void类型,创建删除函数
           //struct node* posnode = headNode->next;/*posnode相当于一个主的临时结构体变量指针,把头节点指向指针地址给临时结构体变量让他从第一个开始循环*/
           //struct node* posnodeFront = headNode;//同时也要定义一个主的结构体类型变量指针来存放主的临时结构体变量地址;
           //先判断头空指针的next是否指向NULL,是则链表为空,否则去进入到循环遍历,找到该成员则把该节点next的值赋给它前一个结点的next,并用free();函数去释放掉要删除节点的内存
           //在循环中寻找每当遍历下一个成员时,先posnodeFront = posnode;先把当前临时节点指针地址给前一个,后posnode = posnodeFront->next;再把给过去的next里面存放的下一个结点的地址给当前临时节点指针,进而去循环!!!
           //注意指针必须赋的是地址,而不是具体的值!!!!!
    

    7.修改内容与第六步同理只不过不释放空间不改变指针的连接,找到成员之后改掉要修改的对应成员体结构中的内容就好了!!!!!

    8.主函数开始写好框架,每添加一个功能函数就放到选择函数里面去!!!!

    》》》》》接下来看实例代码》》建议在codeblocks中运行,无报错!!!
    
    代码1:学生信息管理系统——>
    
    
    ```cpp
    #include<stdio.h>
    #include<stdlib.h>
    void choice();
    int main();
    void shanchu(struct node* headNode, int num1);
    void menu()
    {
        printf("\t\t\t***学生信息管理系统***\n");
        printf("\t\t\t       -》菜单《-     \n");
        printf("\t\t\t**********************\n");
        printf("\t\t\t*     1.插入内容     *\n");
        printf("\t\t\t*     2.显示内容     *\n");
        printf("\t\t\t*     3.删除内容     *\n");
        printf("\t\t\t*     4.修改内容     *\n");
        printf("\t\t\t*     5.退出系统     *\n");
        printf("\t\t\t*                    *\n");
        printf("\t\t\t*   制作人:小阿豪   *\n");
        printf("\t\t\t*    ^-^  ^-^  ^-^   *\n");
        printf("\t\t\t**********************\n\n");
    
    }
    
    struct student//定义学生信息系统结构体将其放到数据域中进行相应操作
    {
        char name[20];
        int num;
        int math;
    };
    struct node {             //一个链表结构体至少有两个域
        struct student data;             //数据域,用来存放数据
        struct node* next;    //指针域,用来存放下一个结构体的地址
    };
    
    //节点初始化
    struct node* createList()//面向对象结构体类型//开始创建一个链表,创建链表前先创建一个空的指向指针节点
    {
        struct node* newList = (struct node*)malloc(sizeof(struct node));
       // newList->data = struct student data;
        newList->next = NULL;
        return newList;
    };
    //创建链表节点,给链表第一个数据节点
    struct node* createNode(struct student data)//面向对象结构体类型
    {
        struct node* newNode = (struct node*)malloc(sizeof(struct student));
        newNode->data=data;//迭代器???
        newNode->next = NULL;//指针为空
        return newNode;
    };
    
    //打印内容
    void printfList(struct node* headNode)//面向过程void类型
    {
        struct node* pMove = headNode->next;
        printf("学号\t姓名\t数学成绩\n");//制表输出
        while (pMove)
        {
            printf("%d\t%s\t%d\n",pMove->data.num, pMove->data.name, pMove->data.math);
            pMove = pMove->next;
        }
        printf("\n");
        getchar();
        printf("是否要返回菜单(Y)退出(N)\n");
        char ok;
        scanf("%c",&ok);
        if(ok=='Y'||ok=='y'){
            main();
        }
        else exit(1);
    }
    
    //插入函数
    void charu(struct node* headNode, struct student data)//面向过程void类型
    {
        struct node* newNode = createNode(data);
        newNode->next = headNode->next;//headNode->next存放的是第一个节点的地址,
        headNode->next = newNode;
    };
    struct node* List = createList();//创建链表List;
      struct student info;//定义一个struct student变量info
    //插入内容
    void zengjia()
    {
    
            while(1)//给一个循环插入
            {
                printf("请输入学生的姓名 学号 数学成绩:");
                getchar();
                scanf("%s%d%d",info.name,&info.num,&info.math);
                charu(List,info);//到链表里面头插法插入一个student结构体
                printf("插入成功!\n");
                printf("是否要继续(Y),返回菜单输入M\n");
                setbuf(stdin,NULL);//清空缓冲区
                int choice=getchar();//是否要继续插入数据
                if(choice=='m'||choice=='M'){
                   main();
                }
            }
    }
    
    //删除内容
    void shanchu(struct node* headNode, int num1)//面向过程void类型
    {
        struct node* posnode = headNode->next;/*posnode相当于一个临时结构体变量,
                                              把头节点指向指针地址给临时结构体变量让他从第一个开始循环*/
        struct node* posnodeFront = headNode;
        if (headNode->next == NULL) {          //用头指针判读链表是否为空(即headnext->是否为NULL
            printf("链表为空不能删除!\n");
        }
        else {
            while (posnode->data.num != num1) {  //循环条件是否循环到了要删除的节点
                posnodeFront = posnode;         //posnode相当于一个临时结构体变量,把挨着找的结构体地址给这个临时的结构体
                posnode = posnodeFront->next;   /*再把之前那个结构体里面的下一个结构体的地址
                                                   给posnode让它成为当前结构体,好在下一轮继续循环下一个结构体变变量*/
                if (posnode == NULL) {
                    printf("没有找到该学生信息!\n");
                    system("pause");
                    getchar();
                    printf("是否要返回菜单(Y)退出(N)\n");
                    char ok;
                    scanf("%c",&ok);
                    if(ok=='Y'||ok=='y'){
                        main();
                    }
                    else exit(1);
                }
            }
            posnodeFront->next = posnode->next;//让最后一个结构体指针指向NULL
            free(posnode);//释放要删除节点的内存
            printf("删除成功!\n");
        }
        printf("是否要返回菜单(Y)退出(N)\n");
        char ok;
        scanf("%c",&ok);
        if(ok=='Y'||ok=='y'){
            main();
        }
        else exit(1);
    };
    //修改内容
    void xiugai(struct node* headNode, int num1)//面向过程void类型
    {
        struct node* posnode = headNode->next;/*posnode相当于一个临时结构体变量,
                                              把头节点指向指针地址给临时结构体变量让他从第一个开始循环*/
        struct node* posnodeFront = headNode;
        if (headNode->next == NULL) {          //用头指针判读链表是否为空(即headnext->是否为NULL
            printf("链表为空不能修改!\n");
        }
        else {
            while (posnode->data.num != num1) {  //循环条件是否循环到了要删除的节点
                posnodeFront = posnode;         //posnode相当于一个临时结构体变量,把挨着找的结构体地址给这个临时的结构体
                posnode = posnodeFront->next;   /*再把之前那个结构体里面的下一个结构体的地址
                                                   给posnode让它成为当前结构体,好在下一轮继续循环下一个结构体变变量*/
                if (posnode == NULL) {
                    printf("没有找到该学生信息!\n");
                    system("pause");
                    getchar();
                    printf("是否要返回菜单(Y)退出(N)\n");
                    char ok;
                    scanf("%c",&ok);
                    if(ok=='Y'||ok=='y'){
                        main();
                    }
                    else exit(1);
                }
            }
        printf("该学生信息为:\t%d\t%s\t%d\n",posnode->data.num,posnode->data.name,posnode->data.math);
        printf("请输入修改之后学生的姓名 学号 数学成绩:");
        scanf("%d%s%d",&posnode->data.num,posnode->data.name,&posnode->data.math);
    //        posnode->data.name=pos.name;
    //        posnode->data.num=pos.num;
    //        posnode->data.math=pos.math;
            printf("修改成功!\n");
            system("pause");
            main();
        }
    };
    
    
    //选择功能
    void choice()
    {
        int xuhao;
        printf("请输入你选择的序号:");
        scanf("%d",&xuhao);
        switch(xuhao)
        {
        case 1:
            zengjia();
            break;
        case 2:
             printfList(List);//打印函数打印链表
            break;
        case 3:
        printf("请输入你要删除的学生编号:");
        scanf("%d",&info.num);//直接放到了一个结构体中将数字
        shanchu(List,info.num);//删除链表里学号为num的那个人
            break;
        case 4:
        printf("请输入你要修改信息的学生编号:");
        scanf("%d",&info.num);//直接放到了一个结构体中将数字
        xiugai(List,info.num);
            break;
        case 5:
            printf("感谢您的使用!下次再见 》》》\n");
            exit(1);
            break;
        default:
            printf("没有该功能!\n");
            break;
        }
    }
    
    int main()
    {
    
        //struct node* posnode;
        menu();
        choice();
        system("pause");//按任意键继续
        return 0;
    }
    
    
    ```cpp
    代码2:洗脚城VIP会员系统
    
    #include<stdio.h>
    #include<stdlib.h>
    int main();
    void meun()
    {
        printf("\t\t\t              >洗脚城VIP会员系统<                \n");
        printf("\t\t\t*************************************************\n");
        printf("\t\t\t*                                               *\n");
        printf("\t\t\t*                  1.添加会员                   *\n");
        printf("\t\t\t*                  2.显示会员                   *\n");
        printf("\t\t\t*                  3.会员充值                   *\n");
        printf("\t\t\t*                  4.解除会员                   *\n");
        printf("\t\t\t*                  5.退出系统                   *\n");
        printf("\t\t\t*                              制作人:小阿豪   *\n");
        printf("\t\t\t*************************************************\n");
    }
    
     struct member       //成员信息结构体
     {
         int num;
         char name[20];
         int money=0;
     };
     struct xjc            //洗脚城结构体
     {
         struct member data;
         struct xjc *next;  //指向下一个结构体
    
     };
     struct xjc *createList()//洗脚城迭代器,创建链表,给予一个头部空节点
     {
         struct xjc *newList=(struct xjc*)malloc(sizeof(struct xjc));
         newList->next=NULL;
         return newList;
    
     };
    
     struct xjc *createNode(struct member data)//会员信息迭代器,创建链表的第一个节点,将其连到空节点//信息都是存在这里面,所以要有形参接收
     {
         struct xjc *newNode=(struct xjc*)malloc(sizeof(struct xjc));
         newNode->data=data;
         newNode->next=NULL;
         return newNode;
     };
     struct xjc *List=createList();
    
     //打印函数
     void printfList(struct xjc *headNode)
     {
         struct xjc *_Move=headNode->next;//next存放的为第一个节点
         printf("\t会员编号\t姓名\t余额\n");
         if(_Move==NULL){
            printf("\n\t还没有添加会员信息哦!!\n");
         }else{
             while(_Move){
                    printf("\t%d\t\t%s\t%d\n",_Move->data.num,_Move->data.name,_Move->data.money);
                    _Move=_Move->next;
             }
         }
         printf("\n");
         getchar();
         printf("是否要返回菜单(Y)退出(N)\n");
         char ok;
         scanf("%c",&ok);
         if(ok=='Y'||ok=='y'){
            main();
        }
         else exit(1);
     }
    
     //插入函数
    
     void charu(struct xjc*headNode,struct member data)
     {
         struct xjc*newnode=createNode(data);
         newnode->next=headNode->next;
         headNode->next=newnode;
     }
    
     struct member info;
     //插入会员
     void zengjia()
     {
         while(1){
             printf("请输入你要添加的会员编号 姓名 金额:");
             scanf("%d%s%d",&info.num,info.name,&info.money);
             charu(List,info);
             printf("添加成功!\n");
             getchar();
             printf("是否要返回菜单(Y)继续添加(N)\n");
             char ok;
             scanf("%c",&ok);
             getchar();
             if(ok=='y'||ok=='Y'){
                main();
             }else continue;
         }
    
    
     }
    
    //会员充值
    void chongzhi(struct xjc*headNode,int tnum,int tmoney)
    {
        struct xjc*posNode=headNode->next;
        struct xjc*posNodefront=posNode;
        if(posNode==NULL){
            printf("还没有添加会员!\n");
            main();
        }else{
                while(posNode->data.num!=tnum){
                    posNodefront=posNode;
                    posNode=posNodefront->next;
                     if (posNode == NULL) {
                        printf("没有找到该会员信息!\n");
                        system("pause");
                        getchar();
                        printf("是否要返回菜单(Y)退出(N)\n");
                        char ok;
                        scanf("%c",&ok);
                        if(ok=='Y'||ok=='y'){
                            main();
                        }
                        else exit(1);
                }
            }
                posNode->data.money=posNode->data.money+tmoney;
                printf("充值成功!\n");
    
            printf("是否要返回菜单(Y)退出(N)\n");
            setbuf(stdin,NULL);
            char ok;
            scanf("%c",&ok);
            if(ok=='y'||ok=='Y'){
                    printf("iavdj\n");
                main();
            }else exit(1);
        }
    }
    
    //删除会员
    void shanchu(struct xjc*headNode,int num)
    {
        struct xjc*posnode=headNode->next;
        struct xjc*posnodefront=headNode;
        if(headNode->next==NULL){
            printf("还未添加会员,不能删除!\n");
        }else{
            while(posnode->data.num!=num){
                posnodefront=posnode;//把地址给另一个变量
                posnode=posnodefront->next;//让临时变量指向他自己里面存的下一个域的地址
                if(posnode=NULL){
                    printf("没有找到该会员的信息!\n");
                    system("pause");
                    getchar();
                    printf("是否要返回菜单(Y)退出(N)\n");
                    char ok;
                    scanf("%c",&ok);
                    if(ok=='Y'||ok=='y'){
                        main();
                    }
                    else exit(1);
                }
            }
            posnodefront->next=posnode->next;
            free(posnode);
            printf("解除会员成功!\n");
        }
        printf("是否要返回菜单(Y)退出(N)\n");
        setbuf(stdin,NULL);
        char ok;
        scanf("%c",&ok);
        if(ok=='Y'||ok=='y'){
            main();
        }
        else exit(1);
    }
    void choice()
    {
        printf("请输入你要选择的功能序号:");
        int xuhao;
        scanf("%d",&xuhao);
        switch(xuhao)
        {
        case 1:
            zengjia();
            break;
        case 2:
            printfList(List);
            break;
        case 3:
            printf("请输入你要充值的会员编号 充值金额:");
            int tmoney;
            int tnum;
            scanf("%d%d",&tnum,&tmoney);
            chongzhi(List,tnum,tmoney);
            break;
        case 4:
            int num;
            printf("请输入你要解除的会员编号:");
            scanf("%d",&num);
            shanchu(List,num);
            break;
        case 5:
            exit(1);
            break;
        default:
            printf("没有该功能!\n");
            break;
        }
    
    }
    
    int main()
    {
        meun();
        choice();
        system("pause");
        return 0;
    }
    

    》》》》》干货到此结束》》》请多多支持与分享》》
    作者:爱写代码的阿豪吖!!

    展开全文
  • C语言实现动态链表创建(超详解

    千次阅读 多人点赞 2020-04-29 08:36:45
    链表,顾名思义:数据储存是一环扣一环,在C语言中用结构体+指针实现。其优势是方便数据插入、增、删、改,并且可以按照实际需求动态分配空间。 #include <stdio.h> #include <stdlib.h> struct ...
  • 链表详解 链表是一种常见的数据结构,结构体指针在这里得到了...链表的节点分为头结点和一般节点,头结点没有数据域。链表中每个节点一般都分为两部分,一个数据域,一个指针域。 1、创建链表 typedef struct stud...
  • 双向链表及其创建C语言详解

    千次阅读 2019-03-14 13:23:00
    目前我们所学到的链表,无论是动态链表还是静态链表,表中各节点中都只包含一个指针(游标),且都统一指向直接后继节点,通常称这类链表为单向链表(或单链表)。 虽然使用单链表能 100% 解决逻辑关系为 "一对...
  • 用两个函数 Load_LinkList() 和 Save_LinkList() 让链表与文件操作结合,除了打印函数,其他都是在内存中操作链表,这样写更有条理,在创建链表时没有采用书上用一个中间变量引导,并插入到结点前面,而是直接在链...
  • 本文是单链表的C语言实现方法,包括单链表的创建、插入、删除、修改、查找等基本操作。 双链表链表中的一种,他和单链表一样都是通过指针将一个个结点连接起来。他和单链表不同的地方在于:单链表的每个结点的指向...
  • 当用单向链表结构储存堆栈时,top只能位于链表表头,此时插入和删除都很方便,如果top在链表的表尾,那么无法进行删除操作。 1.基本结构 typedef struct SNode *stack; struct SNode { ElementType Data; struct ...
  • 链表】单链表基本操作详解(C语言)

    万次阅读 多人点赞 2019-06-01 22:02:15
    本文是单链表的C语言实现方法,包括创建单链表结点、创建单链表、显示链表的数据、获取链表长度、在链表指定位置插入结点、删除指定位置的结点、查找链表中指定的数据、修改链表中指定位置结点的值、修改链表中指定...
  • 《链表及创建》一节我们学习了如何使用...注意,以下对链表的操作实现均建立在已创建链表的基础上,创建链表的代码如下所示: //声明节点结构 typedef struct Link{ int elem;//存储整形元素 struct Link *...
  • C语言指针、链表与文件操作详解

    千次阅读 2017-05-02 22:48:27
    用两个函数 Load_LinkList() 和 Save_LinkList() 让链表与文件操作结合,除了打印函数,其他都是在内存中操作链表,这样写更有条理,在创建链表时没有采用书上用一个中间变量引导,并插入到结点前面,而是直接在链...
  • 前面学习了如何创建一个双向链表,本节学习有关双向链表的一些基本操作,即如何在双向链表中添加、删除、查找或更改数据元素。 本节知识基于已熟练掌握双向链表创建过程的基础上,我们继续上节所创建的双向链表来...
  • 上节,我们初步创建了一个静态链表,本节学习有关静态链表的一些基本操作,包括对表中数据元素的添加、删除、查找和更改。 本节是建立在已能成功创建静态链表的基础上,因此我们继续使用上节中已建立好的静态链表...
  • 前面详细地介绍了顺序表,本节给...与顺序表不同,链表不限制数据物理存储状态,换句话说,使用链表存储数据元素,其物理存储位置是随机。 例如,使用链表存储{1,2,3},数据物理存储状态如图1 所示: ...
  • 开始前废话几句,前几天做C语言笔记时,写到链表这块,懒得写链表的基本操作了,只浏览了一下概念,拖了好几天,今天打算把它完成,期间遇到了一个困惑,在这里再一次对马博老师表示感谢! //为了方便理解,链表的...
  • C语言中单链表的创建中的地址传递和打印以及逆置详解插法创建单链表**:**头插法建立单链表:**单链表逆置 插法创建单链表**: 首先要定义一个单链表,其中typedef关键字是用来给数据类型重命名的。我这里命名为...
  • 上篇文章我们讲到双向链表的创建和插入,那么这篇文章咱们继续哦讲解查找和删除吧! 4.双向链表的删除双链表 删除结点时,只需遍历链表找到要删除的结点,然后将该节点从表中摘除即可。 例如,删除元素 2 的操作...
  • 链表详解

    2019-05-27 22:49:33
    链表的创建、遍历、修改、插入、删除等基本操作的实现(C语言
  • 1、链表结构代码 typedef struct Node { char data; //数据域 struct Node* Lchild, * Rchild; //左右孩子指针 }BTNode,*BTree; 2、创建二叉树 int CreateBTree(BTree* T) { char ch; scanf("%c", &...
  • C语言 表、栈和队列详解 表ADT  形如A1,A2,A3…An表,这个表大小为n,而大小为0表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT相关操有PrintList打印表中元素;CreateEmpty创建一个空表;Find...
  • 链式栈C语言实现详解

    2019-11-30 23:03:18
    目录 ...在上一篇顺序栈中已经讲解过了栈基础知识,这篇主要来讲一下栈另一种结构 --- 链式栈,本文使用的链表结构为单向链表,当然了也可以使用双向链表来实现;对于栈入栈采用就是...
  • 目录 一、队列基础知识 二、链式队列数据结构 ...在上一篇顺序队列中已经讲解过了队列基础知识,这篇主要来讲一下队列另一种结构 --- 链式队列,本文使用的链表结构为单向链表。同样使用两个指针: h...
  • 前文:最近发现基础好重要,学过容易忘,刷letCode题时候,做到了跟数据结构相关的链表,树才发现,大学学,都忘了,没办法,选择了代码这条路,就要重新找回来基础,大学不努力,毕业徒伤悲,出来混总是要还。...
  • C语言制作个人通讯录管理系统—超详解(附源码)

    千次阅读 多人点赞 2020-06-08 11:09:36
    还有结构体链表的创建,贯穿了各个功能代码部分,必不可少。 2、联系人的添加 这部分主要涉及联系人的姓名、地址、电话、QQ号和邮箱(当然需要其他功能可自行添加),考虑到数组操作不便前提下,使用链表的尾插法,...
  • 打印链表,链表的遍历*//* 4.清除线性表L中的所有元素,即释放单链表L中所有的结点,使之成为一个空表 *//* 5.返回单链表的长度 *//* 6.检查单链表是否为空,若为空则返回1,否则返回0 *//* 7.返回单链表中第pos个...

空空如也

空空如也

1 2 3
收藏数 51
精华内容 20
关键字:

c语言链表的创建详解

c语言 订阅