设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › 数据结构与算法 › 实现单链表的基本操作，必须包括初始化链表(元素为空)、 ...
返回列表 发新帖
查看: 4893|回复: 5

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

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

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

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

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


  6. /************************类型定义************************/
  7. typedef char datatype;

  9. void printElem(datatype x)
  10. {
  11.         printf("%c",x);
  12. }

  14. typedef struct node
  15. {
  16.         datatype data;
  17.         struct node *next;
  18. }LNode,*LinkList;

  20. /**********************单链表的基本操作*********************/
  21. //创建空的单链表 （需说明是否带头结点）
  22. LinkList Create_Linklist()
  23. {
  24.         LinkList H=(LNode *)malloc(sizeof(LNode));
  25.         if(H)
  26.                 H->next=NULL;
  27.         return H;
  28. }

  30. //销毁单链表
  31. void Destroy_Linklist(LinkList *H)
  32. {
  33.         LinkList q,p;
  34.         p = *H;
  35.         while(p)
  36.         {
  37.                 q=p;
  38.                 p=p->next;
  39.                 free(q);
  40.         }
  41.         *H=NULL;
  42. }

  44. //求表长
  45. int Length_LinkList(LinkList H)
  46. {
  47.         LinkList j;
  48.         int i=0;
  49.         j=H->next;
  50.         while(j)
  51.         {
  52.                 i += 1;
  53.                 j=j->next;
  54.         }
  55.         return i;
  56. }

  58. //按序号查找
  59. LinkList Get_LinkList(LinkList H,int i)
  60. {
  61.         LinkList p;
  62.         p=H->next;
  63.         int ret=Length_LinkList(H);
  64.         if(i<=ret)
  65.                 for(int j=1;j<=ret;j++)
  66.                 {
  67.                         if(j==i)
  68.                                 return p;
  69.                         else
  70.                                 p=p->next;
  71.                 }
  72.         else
  73.                 return NULL;
  74. }

  76. //按值查找
  77. LinkList Get_LinkList(LinkList H,datatype x)
  78. {
  79.         LinkList p;
  80.         p=H->next;
  81.         int ret=Length_LinkList(H);
  82.         for(int i=0;i<ret;i++)
  83.         {
  84.                 if(p->data==x)
  85.                         return p;
  86.                 else
  87.                         p=p->next;
  88.         }
  89. }

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

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

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

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

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

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

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

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

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

运行时可以正常插入数据，但其它功能均有异常。。。
微信图片_20180325172147.png
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

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

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

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

  13. typedef struct node
  14. {
  15.         datatype data;
  16.         struct node *next;
  17. }LNode,*LinkList;

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

  29. //销毁单链表
  30. void Destroy_Linklist(LinkList *H)
  31. {
  32.         LinkList q,p;
  33.         p = *H;
  34.         while(p)
  35.         {
  36.                 q=p;
  37.                 p=p->next;
  38.                 free(q);
  39.         }
  40.         *H=NULL;
  41. }

  43. //求表长
  44. int Length_LinkList(LinkList H)
  45. {
  46.         LinkList j;
  47.         int i=0;
  48.         j=H->next;
  49.         while(j)
  50.         {
  51.                 i += 1;
  52.                 j=j->next;
  53.         }
  54.         return i;
  55. }

  57. //按序号查找
  58. LinkList Get_LinkList(LinkList H,int i)
  59. {
  60.         LinkList p;
  61.         p=H->next;
  62.         int ret=Length_LinkList(H);
  63.         if(i<=ret)
  64.                 for(int j=1;j<=ret;j++)
  65.                 {
  66.                         if(j==i)
  67.                                 return p;
  68.                         else
  69.                                 p=p->next;
  70.                 }
  71.         else
  72.                 return NULL;
  73. }

  75. //按值查找
  76. LinkList Get_LinkList(LinkList H,datatype x)
  77. {
  78.         LinkList p;
  79.         p=H->next;
  80.         int ret=Length_LinkList(H);
  81.         for(int i=0;i<ret;i++)
  82.         {
  83.                 if(p->data==x)
  84.                         return p;
  85.                 else
  86.                         p=p->next;
  87.         }
  88. }

  90. //插入
  91. int Insert_LinkList(LinkList H,int i,datatype x)
  92. {
  93.         LNode *p;
  94.         if(i==1)
  95.         {
  96.                 LNode *s=(LNode *)malloc(sizeof(LNode));
  97.                 s->data=x;
  98.                 H->next=s;
  99.                 s->next=NULL;
  100.         }
  101.         else
  102.         {
  103.                 p = Get_LinkList(H,i-1);
  104.                 if(p==NULL)
  105.                         {
  106.                                 printf("插入的位置错误!");
  107.                                 return 0;
  108.                         }
  109.                 else
  110.                 {
  111.                         LNode *s=(LNode *)malloc(sizeof(LNode));
  112.                         s->data=x;
  113.                         s->next=p->next;
  114.                         p->next=s;
  115.                         return 1;
  116.                 }
  117.         }
  118. }

  120. //删除(按序号)
  121. int Delete_LinkList(LinkList H,int i)
  122. {
  123.         LNode *p,*s;
  124.         p = Get_LinkList(H,i-1);
  125.         if(p==NULL)
  126.         {
  127.                 printf("第%d个结点不存在！",i-1);
  128.                 return -1;
  129.         }
  130.         else if(p->next=NULL)
  131.         {
  132.                 printf("第%d个结点不存在！",i);
  133.                 return 0;
  134.         }
  135.         else
  136.         {
  137.                 s=p->next;
  138.                 p->next=s->next;
  139.                 free(s);
  140.                 return 1;
  141.         }
  142.        
  143. }

  145. //删除(按值)
  146. int Delete_LinkList(LinkList H,datatype x)
  147. {
  148.         LNode *p,*s;
  149.         p = Get_LinkList(H,x);
  150.         int ret=Length_LinkList(H);
  151.         s=H;
  152.         for(int i=1;i<=ret;i++)
  153.         {
  154.                 if(s->next==p)
  155.                         s->next=p->next;
  156.                 else
  157.                         s=s->next;
  158.         }
  159.         free(p);
  160.         return 1;
  161. }

  163. /*******************程序的功能函数**************************/
  164. //打印单链表(带头结点)
  165. void Print(LinkList H)
  166. {
  167.         printf("head:");
  168.     LinkList p=H->next;
  169.         while(p)
  170.         {
  171.                 printf("-->");
  172.                 printElem(p->data);
  173.                 p = p->next;       
  174.         }
  175.         printf("\n");
  176. }

  178. //查找(按值或按序号查找，用户可选择任意一种方式)
  179. void Search(LinkList H)
  180. {
  181.         int choice,i;
  182.         char x;
  183.         LNode *p,*s;       
  184.         printf("请选择按值查找or按序号查找(1 or 2)：");
  185.         scanf("%d",&choice);
  186.         if(choice==1)
  187.         {
  188.                 printf("请输入将要查找的值:");
  189.                 scanf("%s",&x);
  190.                 p=Get_LinkList(H,x);
  191.                 s=H->next;
  192.                 int ret=Length_LinkList(H);
  193.                 for(int i=1;i<=ret;i++)
  194.                 {
  195.                         if(s==p)
  196.                                 printf("该值位于第%d个位置\n",i);
  197.                         else
  198.                                 s=s->next;                                
  199.                 }       
  200.         }
  201.         else if(choice==2)
  202.         {
  203.                 printf("请输入序号：");
  204.                 scanf("%d",&i);
  205.                 p=Get_LinkList(H,i);
  206.                 printf("值为：%d",p->data);
  207.         }
  208.         else
  209.                 printf("输入错误！");
  210. }

  212. //插入
  213. void Insert(LinkList H)
  214. {
  215.         int i,p;
  216.         char x;
  217.         printf("请输入将要插入的值及其位置：");
  218.         scanf("%s %d",&x,&i);
  219.         p=Insert_LinkList(H,i,x);
  220.         if(p)
  221.                 printf("插入成功!");
  222.         else
  223.                 printf("插入失败!");       
  224. }

  226. //删除 (按值或按序号删除，用户可选择任意一种方式)
  227. void Delete(LinkList H)
  228. {
  229.         int choice,i,p;
  230.         char x;
  231.         printf("请选择按值删除or按序号删除(1 or 2)：");
  232.         scanf("%d",&choice);
  233.         if(choice==1)
  234.         {
  235.                 printf("请输入将要删除的值：");
  236.                 scanf("%s",&x);
  237.                 p=Delete_LinkList(H,x);
  238.                 if(p)
  239.                         printf("删除成功!");
  240.         }
  241.         else if(choice==2)
  242.         {
  243.                 printf("请输入将要删除的序号：");
  244.                 scanf("%d",&i);
  245.                 p=Delete_LinkList(H,i);
  246.                 if(p)
  247.                         printf("删除成功!");
  248.         }
  249.         else
  250.                 printf("输入有误！");
  251.                
  252. }

  254. /*******************main函数**************************/
  255. void printChoice()
  256. {
  257.         printf("\n请选择功能：\n");
  258.         printf("\t1.打印\n");
  259.         printf("\t2.查找\n");   
  260.         printf("\t3.插入\n");
  261.         printf("\t4.删除\n");  
  262.         printf("\t5.退出程序\n");
  263.         printf("请选择:");
  264. }

  266. int main()
  267. {
  268.         LinkList H=Create_Linklist();
  269.         if(!H)
  270.         {
  271.                 printf("空间分配失败！");
  272.                 return 0;
  273.         }
  274.         int choice=-1;
  275.         while(1)
  276.         {
  277.                 printChoice();
  278.                 scanf("%d",&choice);
  279.                
  280.                 switch(choice)
  281.                 {
  282.                         case 1:
  283.                                 Print(H);
  284.                                 break;
  285.                         case 2:
  286.                                 Search(H);
  287.                                 break;
  288.                         case 3:
  289.                                 Insert(H);
  290.                                 break;
  291.                         case 4:
  292.                                 Delete(H);
  293.                                 break;
  294.                         default:
  295.                                 printf("程序结束!\n");
  296.                                 break;
  297.                 }
  298.                 if(choice==5)
  299.                         break;
  300.         }
  301. }
复制代码

程序改为这个后，可以插入，按值查找正常，但按序号查找和按序号删除均不正常
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

K鱼C
发表于 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;
}
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

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

这个按值查找我基本都实现了，还有就是插入数据时可以在任何逻辑正确的位置插入，就是这个按序号查找我的程序会出现其他结果。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

K鱼C
发表于 2018-4-3 16:52:24 | 显示全部楼层
链表貌似不包含这个功能
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

810778176@qq.co
发表于 2018-5-13 15:57:03 | 显示全部楼层
你这是带还是不带头结点
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2025-5-14 04:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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