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

àì夳堔傛蜴生んèń 2022-04-22 02:20 266阅读 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;          //op用来记录用户的选项 
    	int n=0;         //n记录链表中节点的个数,并初始化为0
    	struct link *head=NULL; //定义一个链表头指针并置为空；
    	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;
    }
    
    创建链表//
    函数参数:一个空的头指针和表示要创建的链表的个数n
    返回值:头指针；
    struct link *AppendNode(struct link *head,int &n){
    	int i;   //用于循环；
    	struct link *p=NULL,*pr=head;//为头结点申请内存空间；并使pr和head同时指向他；
    	pr=head=(struct link*)malloc(sizeof(struct link)); 
    	if(pr==NULL)
    	{
    		printf("申请内失败");
    		exit(0);	
    	}
    	head->next=NULL;   //head头结点的数据域不存放数据域，指针域置为空；
    	printf("请输入要保存的联系人信息的数量:  ");
    	scanf("%d",&n);
    	if(n<=0)
    	{     //对用户给的个数n进行检查，判断是否是有效的数据；
    		printf("联系人个数必须是正数!请重新输入\n\n\n");
    		return head;
    	}
    	for(i=1;i<=n;i++)
    	{   //申请分配内存，并将返回的地址给指针p 	
    		p=(struct link*)malloc(sizeof(struct link)); 
    		if(p==NULL)    //检测申请内存成功是否成功
    		{
    			printf("申请内失败");
    			exit(0);
    		}
    		printf("请输入第%d个联系人的名字:  ",i);   scanf(" %s",p->name);
    		printf("请输入第%d个联系人的电话:  ",i);   scanf(" %s",p->number);
    		p->next=NULL; //将新节点的指针域赋值为空；
    		pr->next=p;  //将新申请的节点的地址放在pr的指针域中；
    		pr=p;	//使指针pr指向p；
    	}
    	DisplyNode(head,n);
    	return head;
    }
    
    ///显示链表//
    //函数参数:链表的头指针和链表中节点的个数
    //返回值：没有
    int DisplyNode(struct link *head, int &n)
    {
    	struct link *p=head->next; //将头指针的指针域中的地址赋给指针p
    	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;
    	int n;   //记录用户输入的要删除的节点的位置
    	struct link *p=head; //pr指向头结点 
    	struct link *pr=NULL;
    	printf("请输入要删除第几个联系人:");
    	scanf("%d",&n);
    	if(n<1 || n>m)  //判断用户输入的位置是否在范围内
    	{
    		printf("输入的位置不存在！\n\n\n");
    		return head;
    	}
        for(i=0;i<m;i++)
    	{
    		if(i==n-1)//当找到链表的n-1号节点（p指针指向n-1号节点）
    		{
    			pr=p->next;//将n号位置的地址保存
    			//将n+1号节点地址放在n-1号节点的指针域里面
    			p->next=p->next->next;	   
    			free(pr);  	//释放n号元素内存
    			printf("  删除成功  !\n");
    			m=m-1;//总节点个数-1
    			//若删除的是一号元素,头节点中的指针域就变成了2号元素的地址了；
    			if(n-1==0)  head=p; 
    			DisplyNode(head,m);
    			return head;
    		}
    		p=p->next;//移动到下一个节点	
    	}
    	return head;
    }
    
    
    
    插入节点//
    struct link *addNode(struct link *head,int &m)
    {
    	int i=0,n;   //n用于记录要插入节点的位置
    	struct link *pr=head;   //用于索引
    	struct link *pnew=NULL; //保存新申请的内存单元的地址
    	printf("请输入要插入联系人的位置: ");
    	scanf("%d",&n);
    	if(n<0 || n>m+1) //判断用户输入的n值是否在范围内
    	{
    		printf("输入的位置不存在！\n\n\n");
    		return head;
    	}
    
        for(i=0;i<=m;i++) //0~m（1~m+1）共循环m+1次
    	{
    		if(i==n-1) //找到n-1号节点
    		{
    			pnew=(struct link*)malloc(sizeof(struct link));//为新节点申请内存单元
    			printf("请输入要插入的联系人的姓名: ");	scanf(" %s",pnew->name);
    			printf("请输入要插入的联系人的电话: ");	scanf(" %s",pnew->number);
    			pnew->next=pr->next; //将原来的n号节点与新节点链接起来；
    			pr->next=pnew;//再将新节点与原来的n-1号节点链接起来
    			printf("插入成功!\n");
    	        m=m+1; //总节点个数+1
    			DisplyNode(head,m); //调用链表展示函数便于用户观察
    	        return head;
    		}
    		pr=pr->next; //若没有找到n-1号节点就让指针p指向下一个节点
    	}
    	return head;
    }