鱼C论坛

 找回密码
 立即注册
查看: 4034|回复: 5

实现单链表的基本操作,必须包括初始化链表(元素为空)、销毁链表、求表长、查找、...

[复制链接]
发表于 2018-3-25 17:24:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>


  4. /************************类型定义************************/
  5. typedef char datatype;

  6. void printElem(datatype x)
  7. {
  8.         printf("%c",x);
  9. }

  10. typedef struct node
  11. {
  12.         datatype data;
  13.         struct node *next;
  14. }LNode,*LinkList;

  15. /**********************单链表的基本操作*********************/
  16. //创建空的单链表 (需说明是否带头结点)
  17. LinkList Create_Linklist()
  18. {
  19.         LinkList H=(LNode *)malloc(sizeof(LNode));
  20.         if(H)
  21.                 H->next=NULL;
  22.         return H;
  23. }

  24. //销毁单链表
  25. void Destroy_Linklist(LinkList *H)
  26. {
  27.         LinkList q,p;
  28.         p = *H;
  29.         while(p)
  30.         {
  31.                 q=p;
  32.                 p=p->next;
  33.                 free(q);
  34.         }
  35.         *H=NULL;
  36. }

  37. //求表长
  38. int Length_LinkList(LinkList H)
  39. {
  40.         LinkList j;
  41.         int i=0;
  42.         j=H->next;
  43.         while(j)
  44.         {
  45.                 i += 1;
  46.                 j=j->next;
  47.         }
  48.         return i;
  49. }

  50. //按序号查找
  51. LinkList Get_LinkList(LinkList H,int i)
  52. {
  53.         LinkList p;
  54.         p=H->next;
  55.         int ret=Length_LinkList(H);
  56.         if(i<=ret)
  57.                 for(int j=1;j<=ret;j++)
  58.                 {
  59.                         if(j==i)
  60.                                 return p;
  61.                         else
  62.                                 p=p->next;
  63.                 }
  64.         else
  65.                 return NULL;
  66. }

  67. //按值查找
  68. LinkList Get_LinkList(LinkList H,datatype x)
  69. {
  70.         LinkList p;
  71.         p=H->next;
  72.         int ret=Length_LinkList(H);
  73.         for(int i=0;i<ret;i++)
  74.         {
  75.                 if(p->data==x)
  76.                         return p;
  77.                 else
  78.                         p=p->next;
  79.         }
  80. }

  81. //插入
  82. int Insert_LinkList(LinkList H,int i,datatype x)
  83. {
  84.         LNode *p;
  85.         p = Get_LinkList(H,i-1);
  86.         if(p==NULL)
  87.         {
  88.                 printf("插入的位置错误!");
  89.                 return 0;
  90.         }
  91.         else
  92.         {
  93.                 LNode *s=(LNode *)malloc(sizeof(LNode));
  94.                 s->data=x;
  95.                 s->next=p->next;
  96.                 p->next=s;
  97.                 return 1;
  98.         }
  99. }

  100. //删除(按序号)
  101. int Delete_LinkList(LinkList H,int i)
  102. {
  103.         LNode *p,*s;
  104.         p = Get_LinkList(H,i-1);
  105.         if(p==NULL)
  106.         {
  107.                 printf("第i-1个结点不存在!");
  108.                 return -1;
  109.         }
  110.         else if(p->next=NULL)
  111.         {
  112.                 printf("第i个结点不存在!");
  113.                 return 0;
  114.         }
  115.         else
  116.         {
  117.                 s=p->next;
  118.                 p->next=s->next;
  119.                 free(s);
  120.                 return 1;
  121.         }
  122.        
  123. }

  124. //删除(按值)
  125. int Delete_LinkList(LinkList H,datatype x)
  126. {
  127.         LNode *p,*s;
  128.         p = Get_LinkList(H,x);
  129.         int ret=Length_LinkList(H);
  130.         s=H;
  131.         for(int i=1;i<=ret;i++)
  132.         {
  133.                 if(s->next==p)
  134.                         s->next=p->next;
  135.                 else
  136.                         s=s->next;
  137.         }
  138.         free(p);
  139.         return 1;
  140. }

  141. /*******************程序的功能函数**************************/
  142. //打印单链表(带头结点)
  143. void Print(LinkList H)
  144. {
  145.         printf("head:");
  146.     LinkList p=H->next;
  147.         while(p)
  148.         {
  149.                 printf("-->");
  150.                 printElem(p->data);
  151.                 p = p->next;       
  152.         }
  153.         printf("\n");
  154. }

  155. //查找(按值或按序号查找,用户可选择任意一种方式)
  156. void Search(LinkList H)
  157. {
  158.         int choice,x,i;
  159.         LNode *p,*s;       
  160.         printf("请选择按值查找or按序号查找(1 or 2):");
  161.         scanf("%d",&choice);
  162.         if(choice==1)
  163.         {
  164.                 printf("请输入将要查找的值:");
  165.                 scanf("%d",&x);
  166.                 p=Get_LinkList(H,x);
  167.                 s=H->next;
  168.                 int ret=Length_LinkList(H);
  169.                 for(int i=1;i<=ret;i++)
  170.                 {
  171.                         if(s==p)
  172.                                 printf("该值位于第i个位置");
  173.                         else
  174.                                 s=s->next;                                
  175.                 }       
  176.         }
  177.         else if(choice==2)
  178.         {
  179.                 printf("请输入序号:");
  180.                 scanf("%d",&i);
  181.                 p=Get_LinkList(H,i);
  182.                 printf("值为:%d",p->data);
  183.         }
  184.         else
  185.                 printf("输入错误!");
  186. }

  187. //插入
  188. void Insert(LinkList H)
  189. {
  190.         int x,i,p;
  191.         printf("请输入将要插入的值及其位置:");
  192.         scanf("%d %d",&x,&i);
  193.         p=Insert_LinkList(H,i,x);
  194.         if(p)
  195.                 printf("插入成功!");
  196.         else
  197.                 printf("插入失败!");       
  198. }

  199. //删除 (按值或按序号删除,用户可选择任意一种方式)
  200. void Delete(LinkList H)
  201. {
  202.         int choice,x,i,p;
  203.         printf("请选择按值删除or按序号删除(1 or 2):");
  204.         scanf("%d",&choice);
  205.         if(choice==1)
  206.         {
  207.                 printf("请输入将要删除的值:");
  208.                 scanf("%d",&x);
  209.                 p=Delete_LinkList(H,x);
  210.                 if(p)
  211.                         printf("删除成功!");
  212.         }
  213.         else if(choice==2)
  214.         {
  215.                 printf("请输入将要删除的序号:");
  216.                 scanf("%d",&i);
  217.                 p=Delete_LinkList(H,i);
  218.                 if(p)
  219.                         printf("删除成功!");
  220.         }
  221.         else
  222.                 printf("输入有误!");
  223.                
  224. }

  225. /*******************main函数**************************/
  226. void printChoice()
  227. {
  228.         printf("\n请选择功能:\n");
  229.         printf("\t1.打印\n");
  230.         printf("\t2.查找\n");   
  231.         printf("\t3.插入\n");
  232.         printf("\t4.删除\n");  
  233.         printf("\t5.退出程序\n");
  234.         printf("请选择:");
  235. }

  236. int main()
  237. {
  238.         LinkList H=Create_Linklist();
  239.         if(!H)
  240.         {
  241.                 printf("空间分配失败!");
  242.                 return 0;
  243.         }
  244.         int choice=-1;
  245.         while(1)
  246.         {
  247.                 printChoice();
  248.                 scanf("%d",&choice);
  249.                
  250.                 switch(choice)
  251.                 {
  252.                         case 1:
  253.                                 Print(H);
  254.                                 break;
  255.                         case 2:
  256.                                 Search(H);
  257.                                 break;
  258.                         case 3:
  259.                                 Insert(H);
  260.                                 break;
  261.                         case 4:
  262.                                 Delete(H);
  263.                                 break;
  264.                         default:
  265.                                 printf("程序结束!\n");
  266.                                 break;
  267.                 }
  268.                 if(choice==5)
  269.                         break;
  270.         }
  271. }
复制代码

运行时可以正常插入数据,但其它功能均有异常。。。
微信图片_20180325172147.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-3-25 18:18:49 | 显示全部楼层
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>

  4. /************************类型定义************************/
  5. typedef char datatype;

  6. void printElem(datatype x)
  7. {
  8.         printf("%c",x);
  9. }

  10. typedef struct node
  11. {
  12.         datatype data;
  13.         struct node *next;
  14. }LNode,*LinkList;

  15. /**********************单链表的基本操作*********************/
  16. //创建空的单链表 (需说明是否带头结点)
  17. LinkList Create_Linklist()
  18. {
  19.         LinkList H=(LNode *)malloc(sizeof(LNode));
  20.         if(H)
  21.                 H->next=NULL;
  22.         return H;
  23. }

  24. //销毁单链表
  25. void Destroy_Linklist(LinkList *H)
  26. {
  27.         LinkList q,p;
  28.         p = *H;
  29.         while(p)
  30.         {
  31.                 q=p;
  32.                 p=p->next;
  33.                 free(q);
  34.         }
  35.         *H=NULL;
  36. }

  37. //求表长
  38. int Length_LinkList(LinkList H)
  39. {
  40.         LinkList j;
  41.         int i=0;
  42.         j=H->next;
  43.         while(j)
  44.         {
  45.                 i += 1;
  46.                 j=j->next;
  47.         }
  48.         return i;
  49. }

  50. //按序号查找
  51. LinkList Get_LinkList(LinkList H,int i)
  52. {
  53.         LinkList p;
  54.         p=H->next;
  55.         int ret=Length_LinkList(H);
  56.         if(i<=ret)
  57.                 for(int j=1;j<=ret;j++)
  58.                 {
  59.                         if(j==i)
  60.                                 return p;
  61.                         else
  62.                                 p=p->next;
  63.                 }
  64.         else
  65.                 return NULL;
  66. }

  67. //按值查找
  68. LinkList Get_LinkList(LinkList H,datatype x)
  69. {
  70.         LinkList p;
  71.         p=H->next;
  72.         int ret=Length_LinkList(H);
  73.         for(int i=0;i<ret;i++)
  74.         {
  75.                 if(p->data==x)
  76.                         return p;
  77.                 else
  78.                         p=p->next;
  79.         }
  80. }

  81. //插入
  82. int Insert_LinkList(LinkList H,int i,datatype x)
  83. {
  84.         LNode *p;
  85.         if(i==1)
  86.         {
  87.                 LNode *s=(LNode *)malloc(sizeof(LNode));
  88.                 s->data=x;
  89.                 H->next=s;
  90.                 s->next=NULL;
  91.         }
  92.         else
  93.         {
  94.                 p = Get_LinkList(H,i-1);
  95.                 if(p==NULL)
  96.                         {
  97.                                 printf("插入的位置错误!");
  98.                                 return 0;
  99.                         }
  100.                 else
  101.                 {
  102.                         LNode *s=(LNode *)malloc(sizeof(LNode));
  103.                         s->data=x;
  104.                         s->next=p->next;
  105.                         p->next=s;
  106.                         return 1;
  107.                 }
  108.         }
  109. }

  110. //删除(按序号)
  111. int Delete_LinkList(LinkList H,int i)
  112. {
  113.         LNode *p,*s;
  114.         p = Get_LinkList(H,i-1);
  115.         if(p==NULL)
  116.         {
  117.                 printf("第%d个结点不存在!",i-1);
  118.                 return -1;
  119.         }
  120.         else if(p->next=NULL)
  121.         {
  122.                 printf("第%d个结点不存在!",i);
  123.                 return 0;
  124.         }
  125.         else
  126.         {
  127.                 s=p->next;
  128.                 p->next=s->next;
  129.                 free(s);
  130.                 return 1;
  131.         }
  132.        
  133. }

  134. //删除(按值)
  135. int Delete_LinkList(LinkList H,datatype x)
  136. {
  137.         LNode *p,*s;
  138.         p = Get_LinkList(H,x);
  139.         int ret=Length_LinkList(H);
  140.         s=H;
  141.         for(int i=1;i<=ret;i++)
  142.         {
  143.                 if(s->next==p)
  144.                         s->next=p->next;
  145.                 else
  146.                         s=s->next;
  147.         }
  148.         free(p);
  149.         return 1;
  150. }

  151. /*******************程序的功能函数**************************/
  152. //打印单链表(带头结点)
  153. void Print(LinkList H)
  154. {
  155.         printf("head:");
  156.     LinkList p=H->next;
  157.         while(p)
  158.         {
  159.                 printf("-->");
  160.                 printElem(p->data);
  161.                 p = p->next;       
  162.         }
  163.         printf("\n");
  164. }

  165. //查找(按值或按序号查找,用户可选择任意一种方式)
  166. void Search(LinkList H)
  167. {
  168.         int choice,i;
  169.         char x;
  170.         LNode *p,*s;       
  171.         printf("请选择按值查找or按序号查找(1 or 2):");
  172.         scanf("%d",&choice);
  173.         if(choice==1)
  174.         {
  175.                 printf("请输入将要查找的值:");
  176.                 scanf("%s",&x);
  177.                 p=Get_LinkList(H,x);
  178.                 s=H->next;
  179.                 int ret=Length_LinkList(H);
  180.                 for(int i=1;i<=ret;i++)
  181.                 {
  182.                         if(s==p)
  183.                                 printf("该值位于第%d个位置\n",i);
  184.                         else
  185.                                 s=s->next;                                
  186.                 }       
  187.         }
  188.         else if(choice==2)
  189.         {
  190.                 printf("请输入序号:");
  191.                 scanf("%d",&i);
  192.                 p=Get_LinkList(H,i);
  193.                 printf("值为:%d",p->data);
  194.         }
  195.         else
  196.                 printf("输入错误!");
  197. }

  198. //插入
  199. void Insert(LinkList H)
  200. {
  201.         int i,p;
  202.         char x;
  203.         printf("请输入将要插入的值及其位置:");
  204.         scanf("%s %d",&x,&i);
  205.         p=Insert_LinkList(H,i,x);
  206.         if(p)
  207.                 printf("插入成功!");
  208.         else
  209.                 printf("插入失败!");       
  210. }

  211. //删除 (按值或按序号删除,用户可选择任意一种方式)
  212. void Delete(LinkList H)
  213. {
  214.         int choice,i,p;
  215.         char x;
  216.         printf("请选择按值删除or按序号删除(1 or 2):");
  217.         scanf("%d",&choice);
  218.         if(choice==1)
  219.         {
  220.                 printf("请输入将要删除的值:");
  221.                 scanf("%s",&x);
  222.                 p=Delete_LinkList(H,x);
  223.                 if(p)
  224.                         printf("删除成功!");
  225.         }
  226.         else if(choice==2)
  227.         {
  228.                 printf("请输入将要删除的序号:");
  229.                 scanf("%d",&i);
  230.                 p=Delete_LinkList(H,i);
  231.                 if(p)
  232.                         printf("删除成功!");
  233.         }
  234.         else
  235.                 printf("输入有误!");
  236.                
  237. }

  238. /*******************main函数**************************/
  239. void printChoice()
  240. {
  241.         printf("\n请选择功能:\n");
  242.         printf("\t1.打印\n");
  243.         printf("\t2.查找\n");   
  244.         printf("\t3.插入\n");
  245.         printf("\t4.删除\n");  
  246.         printf("\t5.退出程序\n");
  247.         printf("请选择:");
  248. }

  249. int main()
  250. {
  251.         LinkList H=Create_Linklist();
  252.         if(!H)
  253.         {
  254.                 printf("空间分配失败!");
  255.                 return 0;
  256.         }
  257.         int choice=-1;
  258.         while(1)
  259.         {
  260.                 printChoice();
  261.                 scanf("%d",&choice);
  262.                
  263.                 switch(choice)
  264.                 {
  265.                         case 1:
  266.                                 Print(H);
  267.                                 break;
  268.                         case 2:
  269.                                 Search(H);
  270.                                 break;
  271.                         case 3:
  272.                                 Insert(H);
  273.                                 break;
  274.                         case 4:
  275.                                 Delete(H);
  276.                                 break;
  277.                         default:
  278.                                 printf("程序结束!\n");
  279.                                 break;
  280.                 }
  281.                 if(choice==5)
  282.                         break;
  283.         }
  284. }
复制代码

程序改为这个后,可以插入,按值查找正常,但按序号查找和按序号删除均不正常
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-25 21:09:27 | 显示全部楼层
//我是这么写的:
#include <stdio.h>
#include<stdlib.h>
#define MaxLen 20

///定义单链表
typedef struct LinkNode
{
        int data;                                //数据域
        struct LinkNode *next;  //指针域
}LinkList;

void ShowLinkList(LinkList *head); //声明打印函数

///单链表初始化(生成头结点动态分配存储空间,返回头结点)
LinkList * InitList()
{
        LinkList * head;
        head = (LinkList *)malloc(sizeof(LinkList));
        head -> next = NULL;
        return head;
}

///头插法建表
LinkList * CreateListH(LinkList *head)
{
        int n;
    int i;
        LinkList * l;
        printf("请输入该链表需要存入多少个数字:");
        scanf("%d", &n);

        printf("请输入要存入该链表的数字(以空格隔开):");
        for(i = 0;i < n;i++)
        {
                l = (LinkList *)malloc(sizeof(LinkList));
                scanf("%d", &l -> data);
                l -> next = head -> next;               
                head -> next = l;
        }
        ShowLinkList(head);                //打印一下
       
        return head;
}

///尾插法建表
LinkList * CreateListL(LinkList *head)
{
        int n;
    int i;
        LinkList *l, *p;
        printf("请输入该链表需要存入多少个数字:");
        scanf("%d", &n);

        p = head;
        printf("请输入要存入该链表的%d数字(以空格隔开):", n);
        for(i = 0;i < n;i++)
        {
                l = (LinkList *)malloc(sizeof(LinkList));
                scanf("%d", &l -> data);
                l -> next = NULL;

                while(p -> next != NULL)
                {
                        p = p -> next;
                }
                p -> next = l;
        }
        ShowLinkList(head);//打印一下
        return head;
}

///1.求表长
int GetLengthList(LinkList *head)
{
        int count = 0;
        LinkList *p = head -> next;
        while(p)
        {
                p = p-> next;
                count++;
        }
        return count;
}

///2.按值查找
void Locate(LinkList *head)
{
        int i = 1,x;
        printf("请输入需要查找的数值:");
        scanf("%d", &x);

        LinkList *p = head -> next;
        while(p && p -> data != x)
        {
                p = p -> next;
                i++;
        }
        if(p)
        {
                printf("已找到,在第%d个\n", i);
        }
        else
        {
                printf("未找到!\n");
        }
}

///3.插入节点
void InsList(LinkList *head)
{
        int i, j;
        LinkList *p = head,*q;
       

        printf("请输入需要在第几个位置(头结点算是第0个)插入: ");
        scanf("%d", &i);

        if(i <= 0 || i > GetLengthList(head))
        {
                printf("插入失败,插入位置错误!\n");
        }
        else
        {
                j = 1;
                while(p && j < i)
                {
                        p = p-> next;
                        j++;
                }
                        q = (LinkList *)malloc(sizeof(LinkList));

                        printf("请输入需要插入的数: ");
                        scanf("%d", &q -> data);

                        q -> next = p -> next;
                        p -> next = q;

                        printf("插入成功!");
                        ShowLinkList(head);                //打印一下
        }
}


///4.删除结点
void DelNode(LinkList *head)
{
        int i, j;
        LinkList *p = head,*q;
       

        printf("请输入需要在第几个位置(头结点算是第0个)删除: ");
        scanf("%d", &i);

        if(i <= 0 || i > GetLengthList(head))
        {
                printf("删除失败,删除位置错误!\n\n\n");
        }
        else
        {
                j = 0;
                while(p && j < i - 1)
                {
                        p = p-> next;
                        j++;
                }

                if(p)
                {
                        q = p -> next;
                        j = q -> data;
                        p -> next = q -> next;

                        printf("删除第%d个数%d成功!", i, j);
                        ShowLinkList(head);                //打印一下
                }
                else
                {
                        printf("删除失败,删除位置错误!\n\n\n");
                }
        }
}

///打印链表
void ShowLinkList(LinkList *head)
{
        LinkList *p = head -> next;
        printf("当前链表为: ");
        while(p)
        {
                printf("%d ",p -> data);
                p = p-> next;
        }
        printf("\t长度为%d个。\n\n\n", GetLengthList(head));
}

///主函数
int main()
{
        LinkList *head = CreateListL(InitList());
        int a = 0;

        printf("-----------------------------------单链表操作---------------------------------\n\n");

        for(int j = 0;j < MaxLen;j++)
        {
                printf("请输入您要进行操作的序号:1.求表长\n\t\t\t 2.按值查找\n\t\t\t 3.插入结点\n\t\t\t 4.删除结点\n\n ");
                scanf("%d",&a);
                switch(a)
                {
                        case 1:printf("当前链表的长度为:%d \n\n\n" ,GetLengthList(head));break;
                        case 2:Locate(head);break;
                        case 3:InsList(head);break;
                        case 4:DelNode(head);break;                       
                        default :printf("\n操作失败!无此操作序号。\n\n");
                }
        }
               
        free(head);

        getchar();
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-3-25 21:22:28 | 显示全部楼层
K鱼C 发表于 2018-3-25 21:09
//我是这么写的:
#include
#include

这个按值查找我基本都实现了,还有就是插入数据时可以在任何逻辑正确的位置插入,就是这个按序号查找我的程序会出现其他结果。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-3 16:52:24 | 显示全部楼层
链表貌似不包含这个功能
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-13 15:57:03 | 显示全部楼层
你这是带还是不带头结点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 14:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表