数据结构——电话本-链表-不带头结点

古城微笑少年丶 2022-04-22 02:20 204阅读 0赞

//记录书本的名称和价格；
    //用单向链表，实现了创建链表，删除节点，
    //插入节点，展示链表，释放节点等功能
    #include<stdio.h>
    #include<stdlib.h>
    
    //声明函数原型
    struct link *AppendNode(struct link *head,int &n);  //创建链表
    struct link *delNode(struct link *head,int &n);     //删除节点
    struct link *addNode(struct link *head,int &n);     //插入节点
    int DisplyNode(struct link *head,int &n);          //展示链表
    void DeleteMemory(struct link *head);        //释放链表
    
    //定义链表的一个单节点
    struct link 
    {
    	char name[12];         //数据域：存储学生姓名
    	char number[15];	   //数据域：存储学号；
    	struct link *next; //指针域：存储下个节点的地址
    };
    
    //主函数部分
    int main()
    {
    	int op,n=0;          //用来记录用户的选项
    	struct link *head=NULL; // 链表头指针至为空；
    	//head=AppendNode(head);  //向head为头指针的链表末尾添加节点，并至为头指针；
    	while(1)
    	{
    	printf("        ***菜单***\n");
        	printf("  ------------------------\n");
    		printf("  |    1.建立联系人信息     |\n");
    		printf("  |    2.添加联系人信息     |\n");
    	    printf("  |    3.删除联系人信息     |\n"); 
    		printf("  |    4.打印联系人信息     |\n");
            printf("  |    0.退出程序           |\n");
    		printf("  ------------------------\n");
    		printf("请选择你要进行的操作(0~4):");
    		scanf("%d",&op);
    		if(op==1)       	head=AppendNode(head,n); 
    		else if(op==3)	    head=delNode(head,n); //调用删除节点函数
    		else if(op==2)      head=addNode(head,n); //调用添加节点函数
    		else if(op==4)  	DisplyNode(head,n);   //调用输出链表函数
    		else if(op==0)   break;              //退出程序
    		else printf("输入的选项有误，请重新输入!\n");
    	}
    		DeleteMemory(head); //释放链表
    		return 0;
    }
    
    //创建返回头指针的单向链表//
    //函数参数是一个空的头指针，返回值是头指针；
    struct link *AppendNode(struct link *head,int &m)
    {
    	int i,n=0; //n用于要建立的节点的个数
    	printf("请输入要保存的联系人信息的数量:  ");
    	scanf("%d",&n);
    	m=m+n;
    	if(n<0 )
    	{
    		printf("联系人个数必须是正数!请重新输入\n\n\n");
    		return head;
    	}
    	for(i=1;i<=n;i++)
    	{
    		struct link *p=NULL,*pr=head;
    		//申请分配内存，并将返回的地址给指针p
    		p=(struct link*)malloc(sizeof(struct link)); 
    		//检测申请内存成功是否成功
    		if(p==NULL) 
    		{
    			printf("申请内失败");
    			exit(0);
    		}
    		//将链表的第一个元素的地址赋给头指针
    		if(head==NULL) 
    		{
    			head=p;		
    		}
    		//找到末尾元素，将新申请的内存地址放在末尾元素的指针域里
    		else
    		{
    			while(pr->next != NULL)
    			{
    				pr=pr->next;
    			}
    			pr->next=p;
    		}
    		printf("请输入第%d个联系人的名字:  ",i);
    		scanf(" %s",p->name);
    		printf("请输入第%d个联系人的电话:  ",i);
    		scanf(" %s",p->number);
    		//将尾指针的地址域置为空；
    		p->next=NULL;
    	}
    	DisplyNode(head,m);
    	return head;
    }
    
    ///显示链表中所有节点的节点号和该节点的数据项内容/
    //函数参数是链表的头指针，没有返回值
    int DisplyNode(struct link *head, int &n)
    {
    	struct link *p=head; 
    	int j=1;
    	if(n==0)
    	{
    		printf("还没有保存任何联系人信息！\n\n\n");
    		return 0;
    	}
    	else printf("共有%d个联系人的信息！\n",n);
       	printf("----------------------------------------\n");
    	printf("  序号         姓名         电话号码\n");
    	while(p!=NULL)
    	{
    		printf("%5d    %10s   %12s\n",j,p->name,p->number);
    		p=p->next;
    		j++;
    	}
    	printf("----------------------------------------\n\n\n");
    	return 1;
    }
    
    ///释放head指向的链表中所有节点占用的内存/
    //函数参数是链表的头指针，没有返回值
    //链表的释放只能每个节点逐个释放；
    void DeleteMemory(struct link *head)
    {
    	struct link *p=head,*pr=NULL;
    	while(p!=NULL)
    	{
    		pr=p; //首先让指针pr指向p所在的内存地址；
    		p=p->next;//再让p保存下个节点的地址，避免链表断裂
    		free(pr);//释放pr指向的内存
    	}
    }
    
    删除节点//
    //函数参数是链表的头指针，返回链表的头指针；
    struct link *delNode(struct link *head,int &m)
    {
    	int i=1,n; //n存储的是删除的节点的位置
    	struct link *pr=head;   
    	struct link *temp=NULL;
    	printf("请输入要删除第几个联系人:");
    	scanf("%d",&n);
    	if(n<1 || n>m)
    	{
    		printf("输入的位置不存在！\n\n\n");
    		return head;
    	}
    	//当要删除的是第一个元素的时候，
    	//只要将链表的头指针指向链表的第二个元素
    	//再将链表的第一个元素的内存空间释放掉即可；
    	if(i==n) 
    	{
    		head=pr->next;
    		free(pr);
    		printf("  删除成功  !\n");
    	}
    	//若是要删除的不是首元素时，只要将n号节点指针域中
    	//存储的n+1号节点的地址赋给n-1号元素即可；
    	else
    	{
    		while(pr!=NULL)
    		{
    			temp=pr; //保存n-1号的节点信息；
    			pr=pr->next;//移动链表；
    			i++;
    			if(pr==NULL)//链表为空
    			{
    				printf("没有找到要删除的节点\n");
    			}
    			else if(i==n)//找到n号元素
    			{
    				//将n+1号元素的地址赋给n-1号元素的地址；
    				temp->next=pr->next;
    				//释放n号元素内存
    				free(pr);
    				printf("  删除成功  !\n");
    				break;
    			}
    		}
    	}
    	m=m-1;
    	DisplyNode(head,m);
    	return head;
    }
    
    
    
    插入节点//
    struct link *addNode(struct link *head,int &m)
    {
    	int i=0,n;   //n用于记录要插入节点的位置
    	struct link *pr=head;   //用于索引
    	struct link *temp=NULL; //用于存储插入节点的下一个元素的地址
    	struct link *pnew=NULL; 
    	printf("请输入要插入联系人的位置: ");
    	scanf("%d",&n);
    	if(n<0 || n>m+1)
    	{
    		printf("输入的位置不存在！\n\n\n");
    		return head;
    	}
    	if(n==1)
    	{
    		//申请为新节点分配内存
    		pnew=(struct link*)malloc(sizeof(struct link));
    		printf("请输入要插入的联系人的姓名: ");
    		scanf(" %s",pnew->name);
    		printf("请输入要插入的联系人的电话: ");
    		scanf(" %s",pnew->number);
    		pnew->next=head;
    		head=pnew;
    		printf("插入成功!  \n");
    		m=m+1;
    		DisplyNode(head,m);
    		return head;
    	}
    	//当插入的位置不是首地址时；
    	//我们需要将n号位置的上一个节点n-1号节点
    	//的指针域指向这个新建的节点，
    	//再将新建的节点的指针域指向原来的n号位置的节点；
    	for(pr;pr!=NULL;pr=pr->next)
    	{
    		temp=pr->next; //将原来的n号地址保存起来
    		i++;
    		if(i==n-1) //找到n-1号节点
    		{
    			pnew=(struct link*)malloc(sizeof(struct link));
    			printf("请输入要插入的联系人的姓名: ");
    			scanf(" %s",pnew->name);
    			printf("请输入要插入的联系人的电话: ");
    			scanf(" %s",pnew->number);
    			pr->next=pnew; //将n-1号节点与新节点链接起来；
    			pnew->next=temp;//再将新节点与原来的n号节点链接起来
    		}
    	}
    	printf("插入成功!\n");
    	m=m+1;
    	DisplyNode(head,m);
    	return head;
    }