数据结构

设计并编程实现一个应用单链表存储结构的通信录管理系统。定义适当数据类型，设计并编写完成下列8项基本功能的C语言程序：

[root@huhy ~]# cat test.c
/*一、功能要求：
 1.添加 2.查找 3.删除 4.修改 */
/*二、包含信息
 每一个联系人包含编号、姓名、手机、qq等信息*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TongXun{
        char ID[15];
        char name[12];
        char tel[15];
        char QQ[15];
}datatype;

typedef struct node{
        datatype data;
        struct node *next;
}Node, *LinkNode;

LinkNode head =NULL; //先确定头结点

/*功能函数*/
void Menu();                            //0.显示界面
void InitList();                        //1.通讯录的初始化***

                                                        //2.建立通讯录(单链表的建立)*******
void CreateList_Head();         //2.1头插法创建
int JudgeID(LinkNode ptr1,LinkNode ptr2);//2.11判断ID是否重复
void CreateList_Tail();         //2.2尾插法创建

void DelList();                 //3.删除数据(根据姓名删除) ********

void UpdateList();      //4.修改信息******

void SearchList();              //5.查找信息

                                                        //6.插入信息 ******
void InsertList_Pre();          //6.1前插法
void InputList(LinkNode ptr);                   //6.11输入指定结点指针相关信息
void InsertList_Back();         //6.2后插法


void TraverseList(); //7.遍历通讯录
void PrintList(LinkNode ptr); //7.1输出指定信息

void DestroyList();  //8.释放通讯录***

void save(LinkNode stu);        //9.用于将数组中的信息保存到文件中 (n个同学)
int NumList(LinkNode head);     //9.1 通过头指针，遍历单链表进行人数统计并返回

/*主控函数*/
int  main(void)
{
        int choice;

        while (1)
        {
                Menu();
                printf("请选择菜单：");
                scanf("%d", &choice);
                switch (choice)
                {
                    case 1:             //初始化通讯录
                                        InitList(); break;
                        case 2:         //建立通讯录
                                {
                                                int num;
                                                printf("请选择建立方式(1.头插法 2.尾插法):");
                                                scanf("%d", &num);   /****下边的大括号不可以省略 ****/
                                                if (num == 1)   //头插法
                                                {
                                                   CreateList_Head();  break;
                                                }

                                                if (num == 2)   //尾插法
                                                {
                                                        CreateList_Tail();  break;
                                                }


                                }

                        case 3:         //删除信息
                                        DelList(); break;

                        case 4:         //修改信息
                                        UpdateList(); break;

                        case 5:         //查找信息
                                        SearchList(); break;

                        case 6:         //添加信息
                       {

                                        int num;
                                        printf("请选择插入方式(1.前插法 2.尾插法)：");
                                        scanf("%d", &num);
                                        if (num == 1) //头插法
                                        {
                                                InsertList_Pre(); break;
                                        }
                                        if (num == 2) //尾插法
                                        {
                                            InsertList_Back(); break;
                                        }


                      }


                        case 7:         //遍历通讯录
                                        TraverseList(); break;

                        case 8: //释放通讯录
                                        DestroyList(); break;


                    default: return 0;
                }
        }
        return 0;
}

/*0.显示界面*/
void Menu()
{
        printf("\t\t\t****************************************************\n");
        printf("\t\t\t1.初始化通讯录                          2.建立通讯录\n");
        printf("\t\t\t3.删除联系人                            4.修改联系人\n");
        printf("\t\t\t5.查找联系人                            6.添加联系人\n");
        printf("\t\t\t7.输出通讯录                            8.释放通讯录\n");
        printf("\t\t\t***************其他按键视为退出**********************\n");
}
/*1.通讯录的初始化*/
//(建立头结点)
void InitList()
{
     head= (LinkNode)malloc(sizeof(Node));
     head->next = NULL;
     printf("初始化成功！\n");
     save(head);
}



/*2.建立通讯录(单链表的建立)*/
//2.1插入数据，建立通讯录（头插法）
//首先建立新结点，为其动态开辟内存空间
//接着为该结点的data域存入数据
//然后经典头插代码（为让新结点插入头结点和首元结点之间）
//先让新结点的指针域指向原首元结点;然后让头结点的指针域指向该新结点
//就是通过结点间的指针进行连接/相关联
void CreateList_Head()
{
    LinkNode ptr;
    LinkNode ptr2;
    int item=1;         //用来控制循环（决定是否继续录入信息）
    int n;

    //需要实现：循环直至自行决定，不继续建立新的联系人
    //另写函数2.11，实现排除输入ID重复
    while(item!=0)
    {
        ptr = (LinkNode)malloc(sizeof(Node));//动态分配内存(新结点)


        printf("请输入通讯信息：\n");
        printf("请输入姓名：");
        scanf("%s",&(ptr->data.ID));
                ptr2 = head->next;
        n = JudgeID(ptr,ptr2); //ID有重复n=1;
        //调用函数2.11进行判断ID是否重复

        while(n==1)
        {
                        printf("姓名已存在请重新输入：\n");
                        scanf("%s",&(ptr->data.ID));
                        n = JudgeID(ptr,ptr2); //ID有重复n=1;
                }

                    printf("请输入电话：\n");
                    scanf("%s",&(ptr->data.name));
                    printf("请输入QQ：\n");
                    scanf("%s",&(ptr->data.tel));
                    printf("请输入住址：\n");
                    scanf("%s",&(ptr->data.QQ));

                    //头插法的经典代码
                    ptr->next = head->next;
                    head->next = ptr;
                    printf("是否继续录入，继续：1，退出：0\n");
                    scanf("%d",&item);

        }
        save(head);
   return ;
}
//2.11实现排除输入ID重复
//传入需要比对的结点,遍历单链表逐个比对ID
//要和首元结点的指针域指向的结点比较（次首元结点）,就是新结点的指针域所指结点
//如果有重复返回 1，否则返回0;
int JudgeID(LinkNode ptr1,LinkNode ptr2)
{
        while(ptr2!=NULL)
        {
          if(strcmp(ptr1->data.ID,ptr2->data.ID)==0)
             return 1;
          else
            ptr2 = ptr2->next;
        }
        return 0;
}

/*
   2.建立通讯录(单链表的建立)
//2.1插入数据，建立通讯录（头插法）
void CreateList_Head()
{
        List *node; //插入节点
        int count = 0;
        int flag = 1;//用于判断是否继续输入下一条记录
        while (flag)
        {
                count++;
                node= (List *)malloc(sizeof(List));  //为新建的结点开辟内存
                printf("插入第%d条记录：\n", count);
                printf("ID：");
                scanf("%s", &(node->data.ID));

                //判断ID是否重复
                List *p = L->next;
                while (p)
                {
                        if (strcmp(p->data.ID, node->data.ID) == 0)
                        {
                                printf("ID重复，请重新输入!\n");
                                printf("ID：");
                                scanf("%s", &(node->data.ID));
                        }
                        else
                                p = p->next;
                }
                printf("姓名：");
                scanf("%s", &(node->data.name));
                printf("电话：");
                scanf("%s", &(node->data.tel));
                printf("QQ：");
                scanf("%s", &(node->data.QQ));

                //头插法的核心 代码
                node->next = L->next; //对于新建立的结点，先确定其指针域，再确定头指针的指向
                L->next = node;
                printf("是否继续录入(1.继续 0.完成录入)：");
                scanf("%d", &flag);
                if (flag == 0)
                        break;
        }
}
*/
/*2.2尾插法创建 */
//首先先建立一个新结点和一个尾结点rear（一直指向尾结点）
//依旧需要为新结点的data域赋值
//依旧让rear指向头结点
//但是尾插法核心仍然是：
//先让新结点作为rear的后继结点，然后让rear还指向尾结点;
void CreateList_Tail()
{
        LinkNode  ptr, rear=head;       //定义新结点和尾节点
        LinkNode  ptr2;
    int item = 1; //用来判断循环是否继续
    int n;
    while(item ==1 )
        {
                ptr = (LinkNode)malloc(sizeof(Node));//动态分配内存(新结点)
                printf("请输入通讯信息：\n");
        printf("请输入姓名：");
        scanf("%s",&(ptr->data.ID));
                  ptr2 = head->next;
            n = JudgeID(ptr,ptr2); //ID有重复n=1;
        //调用函数2.11进行判断ID是否重复

        while(n==1)             //如果加入的ID与之前重复，便一直循环重新输入
        {
                        printf("姓名已存在请重新输入：\n");
                        scanf("%s",&(ptr->data.ID));
                        n = JudgeID(ptr,ptr2); //ID有重复n=1;
                }
        printf("请输入电话：\n");
                scanf("%s",&(ptr->data.name));
                printf("请输入QQ：\n");
                scanf("%s",&(ptr->data.tel));
                printf("请输入住址：\n");
                scanf("%s",&(ptr->data.QQ));
        //尾插法的核心
                  rear->next =ptr;
                  ptr->next = NULL;
                  rear = ptr;

                printf("是否继续录入，继续：1，退出：0\n");
                scanf("%d",&item);
        }
        return ;
}

/*3.删除数据(根据姓名删除)
void DelList()
{
        LinkNode p = head->next;
        LinkNode q = head;
        char ID[10];
        printf("请输入要删除的ID：");
        scanf("%s", &ID);
        while (p && strcmp(p->data.ID, ID) != 0)//找到ID一样的，让P指向该结点
        {
                p = p->next;
                q = q->next;
        }
        if (p!= NULL)
        {
                q->next = p->next;
                printf("删除成功!\n");
                printf("被删除数据的信息为：\n");
                printf("ID：%s\n", p->data.ID);
                printf("姓名：%s\n", p->data.name);
                printf("电话：%s\n", p->data.tel);
                printf("QQ：%s\n", p->data.QQ);
                free(p);
        }
        else
        {
                printf("通讯录中不存在此人信息！\n");
        }
}
*/
/*3.删除数据(根据姓名删除)*/
//关键点：单链表所有结点间通过结点指针的指向来联系
//首先明确两个结点指针：p,q
//分别用来 使整个单链表联系;找到需要删除信息的结点
//然后需要保证-->单链表的完整连接性，
//最后释放-->需要删除的结点信息
void DelList()
{
   LinkNode p, q;
   p = head;
   q = head->next;
   char str[20];
   printf("请输入需要删除姓名：\n");
   scanf("%s",&str);
   //可能一开始就是空链表，或者遍历到最后（通过指针q来判断）
   while(q!=NULL && strcmp(q->data.ID,str)!=0) //遍历单链表,让结点指针q指向需要删除的结点
   {
          q = q->next;
          p = p->next;
   }

   if(q==NULL)//遍历单链表找不到该信息
   {
                printf("该信息不存在\n");
   }
   else
   {
           p->next = q->next;   //让p在单链表中保证其完整性
           printf("该信息如下：\n");
           printf("姓名为：%s\n",q->data.ID);
           printf("电话为：%s\n",q->data.name);
           printf("QQ号为：%s\n",q->data.tel);
           printf("住址为：%s\n",q->data.QQ);

           printf("通讯信息删除成功\n");
             free(q);
   }
   save(head);

}

/*4.修改信息*/
//先定义一个结点指针，让它指向首元结点
//进行遍历，与输入的ID进行比较，找到该信息所在结点
//然后进行（循环）修改信息：1.姓名 2.手机号 3.QQ号
void UpdateList()
{
        LinkNode ptr = head->next;
        int item=1,n=0;  //item控制是否继续修改信息
                                        //n用来判断是否修改该信息
        char str[20];
        printf("请输入需要修改的姓名：\n");
        scanf("%s",&str);
        while(ptr!=NULL&&strcmp(ptr->data.ID,str)!=0)//遍历单链表，找和所输入ID一致的结点
        {
                ptr = ptr->next;
        }
        if(ptr==NULL)
        {
                 printf("该信息不存在\n");
                 return ;
        }
          //能够找到该信息，就会进行修改
        while(item==1) //item为1表示继续修改信息
        {
                printf("是否要修改电话:（是：1 否：0）\n");
                   if(scanf("%d",&n),n==1)
                     scanf("%s",&ptr->data.name);
                printf("是否要修改QQ号:（是：1 否：0）\n");
                        if(scanf("%d",&n),n==1)
                      scanf("%s",&ptr->data.tel);
                printf("是否要修改住址:（是：1 否：0）\n");
                        if(scanf("%d",&n),n==1)
                      scanf("%s",&ptr->data.QQ);
                printf("是否需要重新修改信息：(是：1 否：0)\n");
                scanf("%d",&item);
        }
        save(head);
}

/*5.查找指定ID信息*/
//先定义一个结点指针，指向首元结点
//接着进行遍历单链表，找该信息所在结点
//然后输出该信息
void SearchList()
{
        LinkNode ptr = head->next;
        char str[20];
        printf("请输入需要查找的姓名：\n");
        scanf("%s",&str);
        while(ptr!=NULL&&strcmp(ptr->data.ID,str)!=0)//遍历单链表，找和所输入ID一致的结点
        {
                ptr = ptr->next;
        }
        if(ptr==NULL)
        {
                 printf("该信息不存在\n");
                 return ;
        }

        //如果找到该信息，就会输出

        printf("该通讯信息如下：\n");
        PrintList(ptr);

}


/*5.插入数据（前插法）
void InsertList_Pre()
{
   LinkNode p, q, r, node;
        p = head->next;
        q = head;
        char ID[10];
        printf("请输入要插入的位置(输入该位置的ID)：");
        scanf("%s", &ID);//结点指针p用来遍历指向 所要添加的位置
        while (p && strcmp(p->data.ID, ID) != 0)
        {
                p = p->next;
                q = q->next;
        }

        if (p != NULL)
        {
                //给新节点分配空间
                node = (LinkNode)malloc(sizeof(Node));
                //录入新节点数据
                printf("请输入新节点信息：\n");
           judge:
                        printf("ID：");
                        scanf("%s", &(node->data.ID));
                        //判断ID是否重复
                    r = head->next;
                    while (r && strcmp(r->data.ID, node->data.ID) != 0)
                        {
                                r = r->next;
                    }
          if (r != NULL)
          {
                  printf("ID重复，请重新输入！\n");
                  //free(r); 这里不能free(r),如果释放r,会失去r的下一个节点的信息，链表会被破坏
                  goto judge;
          }
          printf("姓名：");
          scanf("%s", &(node->data.name));
          printf("电话：");
          scanf("%s", &(node->data.tel));
          printf("QQ：");
          scanf("%s", &(node->data.QQ));
        }



        else
        {
                //如果没有该ID
                int choice1;
                printf("通讯录中未找到该ID,是否使用默认方式将新节点插入到最后(1.是 0.否)：");
                scanf("%d", &choice1);
                if (choice1 == 1)
                {
                        //给新节点分配空间
                        node = (LinkNode)malloc(sizeof(Node));
                        //给新节点输入数据
                        printf("请输入新节点信息：\n");
                judge1:
                        printf("ID：");
                        scanf("%s", &(node->data.ID));
                        //判断ID是否重复
                        r = head->next;
                        while (r && strcmp(r->data.ID, node->data.ID) != 0)
                        {
                                r = r->next;
                        }
                        if (r != NULL) //ID重复
                        {
                                printf("ID重复,请重新输入!\n");
                                goto judge1;
                        }
                        printf("姓名：");
                        scanf("%s", &(node->data.name));
                        printf("电话：");
                        scanf("%s", &(node->data.tel));
                        printf("QQ：");
                        scanf("%s", &(node->data.QQ));
                }
                else
                        return;
        }
        node->next = q->next;
        q->next = node;
        printf("插入成功！\n");
}
*/
/*6.1仿头插法-->前插法(添加信息到指定位置)*/
//首先输入ID，确定新结点插入位置 (让结点指针p指向该位置)
//接着为新结点 ptr 开辟内存并赋值
//然后就是模仿-->经典的头插法
//建立链表时，（头插法建立）已经写好的函数进行封装，接着在该函数进行调用;
void InsertList_Pre()
{
         LinkNode p,L,ptr;        //结点指针L伴随着p一起移动
         char str[20];
         L = head;
         p = head->next;

         //需要输入ID，遍历单链表，将p指向该结点

         //情况1：如果p不是空指针，最后进行仿头指针的经典代码（将指针L假想成头指针）
         //情况2：如果p是空指针，此时便是头结点
         //可以为新结点 ptr 依次输入信息(记得查重复ID)
         //因此两种情可以用一个经典代码（将结点指针L，假想为头结点）进行插入添加

        printf("请输入姓名（新信息会插入到该信息前）：\n");
         scanf("%s",&str);
         while(p!=NULL && strcmp(p->data.ID,str)!=0)    //逻辑符号的使用
         {
                p = p->next;
                L = L->next;
         }

         if(p==NULL)
         {
                printf("所输入的姓名不存在\n");
                return;
         }


        //为新结点开辟内存并赋值
          ptr =(LinkNode)malloc(sizeof(Node));
          //函数InputList()   为指定结点指针-->输入相关信息
           InputList(ptr);

        //经典头插法核心代码
           //仿头插法(将 L的指向看作头结点，p的指向看作首元结点)
           ptr->next = L->next;
           L->next =ptr;
           printf("信息插入成功\n");
           save(head);
}
/*6.11输入指定结点指针相关信息*/
//功能中实现防输入重复ID
void InputList(LinkNode ptr)
{
        int n=0;
        printf("请输入通讯信息：\n");
    printf("请输入姓名：");
    scanf("%s",&(ptr->data.ID));
    LinkNode ptr2 = head->next;
      n = JudgeID(ptr,ptr2); //ID有重复n=1;
        //调用函数2.11进行判断ID是否重复

    while(n==1)         //如果加入的ID与之前重复，便一直循环重新输入
    {
                printf("姓名已存在请重新输入：\n");
                scanf("%s",&(ptr->data.ID));
                n = JudgeID(ptr,ptr2); //ID有重复n=1;
        }

                    printf("请输入电话：\n");
                    scanf("%s",&(ptr->data.name));
                    printf("请输入QQ号：\n");
                    scanf("%s",&(ptr->data.tel));
                    printf("请输入住址：\n");
                    scanf("%s",&(ptr->data.QQ));

}
/*6.2仿尾插法-->后插法(添加信息到指定位置)*/
//首先让指针结点遍历单链表，来找指定ID的位置
//然后创建新结点，为其开辟动态内存并赋值
//最后仿尾插法运用经典代码

//结点指针 p,L;分别用来作为当前遍历的首元结点，总是指向当前的尾结点
//就是用指针p来遍历单链表
//当p为NULL时，即没有找到指定ID，将此时L作为尾结点进行处理
//当p不是NULL，即找到指定ID，将此时p作为尾结点进行处理
void InsertList_Back()
{
        LinkNode p,L,ptr;         //结点指针L伴随着p一起移动
        LinkNode node;  //暂存所指结点后的结点（以防出现单链表中途插入新信息）
        char str[20];
        L = head;
        p = head->next;

        printf("请输入姓名（新信息会插入到该信息前）：\n");
        scanf("%s",&str);
        while(p!=NULL && strcmp(p->data.ID,str)!=0)     //逻辑符号的使用
        {
                p = p->next;
                L = L->next;
        }


        if(p == NULL)
        {
          printf("所输入的姓名不存在\n");
           return;
         /*
          L->next = ptr;
          L = ptr;
          ptr = NULL;
        */
        }

                //为新结点开辟内存并赋值
          ptr =(LinkNode)malloc(sizeof(Node));
        //函数InputList()   为指定结点指针-->输入相关信息
           InputList(ptr);


           //暂存 所指结点后的结点（以防出现单链表中途插入新信息）
            node = p->next;

           //经典尾插法的核心代码
           p->next = ptr;
           p = ptr;

           //保证插入后单链表的完整性
           ptr->next = node;
          // ptr = NULL;   //仿尾插法,可能所要插入的ID不在单链表的最后

        save(head);
}


/*7.遍历通讯录*/
void TraverseList()
{
        LinkNode p;
        if (head == NULL)
        {
                printf("通讯录为空！\n");
                return;
        }
        else
        {
                p = head->next;
                printf("通讯录中全部信息如下：\n");
                while (p)
                {
                        PrintList(p);
                        p = p->next;
                }
        }
}

//7.1输出指定信息
void PrintList(LinkNode ptr)
{
    printf("姓名：%-15s\t", ptr->data.ID);
        printf("电话：%-10s\t", ptr->data.name);
        printf("QQ：%-15s\t", ptr->data.tel);
        printf("住址：%-15s\n", ptr->data.QQ);

}
/*8.释放通讯录*/
//需要释放内存后，接着把指针指向NULL
//释放头结点，首元结点和遍历单链表所指向的结点
//先定义两个结点指针 p,t;
//分别用来遍历单链表，暂时指向所遍历之处的结点
void DestroyList()
{
        LinkNode p, t;
        p = head->next;
        while(p!= NULL) //遍历单链表，进行内存释放,数据置空
        {
                t = p;
                free(t);
                t = NULL;
                p = p->next ;
        }
        //遍历完单链表，此时p为空指针
        free(p);
        free(head);
        head = NULL;

        printf("单链表清空成功\n");
         save(head);
}

/* 9.用于将数组中的信息保存到文件中 (n个同学)*/
//调用fwrite()函数 ,将数组中的信息存入文件中
//了解exit()函数 ,用来终止正在执行的程序
void save(LinkNode stu)
{
        FILE *fp;
        int n;
        n = NumList(stu);
        if((fp = fopen("D:\\student1.txt","w")) == NULL)
        {
                printf("打开文件失败\n");
                exit(0);
        }

        fwrite(stu , n*sizeof(Node) , 1,fp); //一个学生信息，用一个结构体数组存储
        fclose(fp);
}
//9.1 通过头指针，遍历单链表进行人数统计并返回
int NumList(LinkNode head)
{
        int num=0;
        LinkNode L;
        L = head->next;
        while(L!=NULL)
        {
           num++;
           L =L->next;
        }

        return num;
}