Chinaunix首页 | 论坛 | 博客

不忘初心，方得始终！c0732.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

jsxthncn

  • 博客访问： 556144
  • 博文数量： 127
  • 博客积分： 1169
  • 博客等级： 少尉
  • 技术积分： 1298
  • 用 户 组： 普通用户
  • 注册时间： 2010-03-16 14:29
个人简介

空白

文章分类

全部博文（127）

推荐博文
相关博文
单链表实现（c语言）

分类： C/C++

2012-03-06 19:16:34

单链表常用操作实现：linklist.h文件
  1. /*
  2.     linklist.h
  3.     时间：2012年3月6日 14:07:17
  4.     目的：练习C语言基础知识，实现单链表常用操作
  5. */

  7. #include <stdio.h>
  8. #include <stdlib.h>

  10. #define TRUE 1
  11. #define FALSE 0
  12. #define OK 1
  13. #define ERROR 0
  14. #define INFEASIBLE -1
  15. #define OVERFLOW -2

  17. typedef int Status;
  18. typedef int ElemType;

  20. /*链表结点*/
  21. typedef struct LNode
  22. {
  23.     ElemType data;        
  24.     struct LNode * next;
  25. } * LinkList, LNode;

  27. /*构造一个空的线性表L*/
  28. Status InitLinkList(LinkList *L);

  30. /*线性表L已存在，操作结果：销毁线性表L*/
  31. void DestroyList(LinkList L);

  33. /*置空线性表,释放出头节点之外的所有的节点*/
  34. void ClearList(LinkList L);

  36. /*判断链表是否为空*/
  37. Status ListEmpty(LinkList L);

  39. /*链表L已存在，返回L中数据元素个数*/
  40. int ListLength(LinkList L);

  42. /*获取链表L中第i个结点的值*/
  43. Status GetElem(LinkList L, int i, ElemType *e);

  45. /*创建包含n个结点的链表*/
  46. void CreateList(LinkList L, int n);

  48. /*在链表L中的第i个结点之前插入一个结点*/
  49. Status ListInsert(LinkList L, int i, ElemType e);

  51. /*删除链表L中第i个位置的节点，e保存节点data域的值*/
  52. Status ListDelete(LinkList L, int i, ElemType *e);

  54. Status compile(ElemType e1, ElemType e2);

  56. int LocateElem(LinkList L, ElemType e);

  58. /*
  59. 链表L，cur_e不是第一个结点，如果链表中存在cur_e结点，则用pur_e返回该结点前驱
  60. 并返回OK，否则返回INFEASIBLE
  61. */
  62. Status PriorElem(LinkList L, ElemType cur_e, ElemType *pur_e);

  64. Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e);

  66. Status ListTransver(LinkList L);
linklist.c文件：
  1. #include "linklist.h"

  3. /*构造一个空的线性表L*/
  4. Status InitLinkList(LinkList *L)
  5. {
  6.     //生成头结点
  7.     *L = (LinkList)malloc(sizeof(LNode));
  8.     if (!(*L))
  9.     {
  10.         return ERROR;
  11.     }

  13.     (*L)->next = NULL;

  15.     return OK;
  16. }

  18. /*创建包含n个结点的链表，从表头插入数据*/
  19. void CreateList(LinkList L, int n)
  20. {
  21.     int i;
  22.     LinkList p;

  24.     for (i = n; i > 0; --i)
  25.     {
  26.         p = (LinkList)malloc(sizeof(LNode));
  27.         p->data = i;
  28.         p->next = L->next;
  29.         L->next = p;
  30.     }
  31. }

  33. /*创建包含n个结点的链表，在表尾插入数据*/
  34. void CreateList2(LinkList L, int n)
  35. {
  36.     //链表为空，L为头结点指针
  37.     int i;
  38.     LinkList p = L, s;
  39.     for (i = 1; i <= n; i++)
  40.     {
  41.         s = (LinkList)malloc(sizeof(LNode));
  42.         s->data = i;
  43.         p->next = s;
  44.         p = s;                     
  45.     }
  46.     p->next = NULL; //最后将最后插入元素的next域指向NULL
  47. }


  50. /*线性表L已存在，操作结果：销毁线性表L*/
  51. void DestroyList(LinkList L)
  52. {
  53.     LinkList q;
  54.     while (L)
  55.     {
  56.         q = L->next;
  57.         free(L);
  58.         L = q;
  59.     }
  60. }

  62. /*置空线性表,释放出头节点之外的所有的节点*/
  63. void ClearList(LinkList L)
  64. {
  65.     LinkList q = L->next, p;
  66.     while (q)
  67.     {
  68.         p = q->next; // p = q;
  69.         free(q); // q = q->next;
  70.         q = p; // free(p);
  71.     }
  72.     L->next = NULL;
  73. }

  75. /*判断链表是否为空*/
  76. Status ListEmpty(LinkList L)
  77. {
  78.     if (L->next)
  79.         return FALSE;
  80.     else
  81.         return TRUE;
  82. }

  84. /*链表L已存在，返回L中数据元素个数*/
  85. int ListLength(LinkList L)
  86. {
  87.     LinkList q = L->next; //q指向第一个结点
  88.     int i = 0;
  89.     while (q)
  90.     {    
  91.         i++;
  92.         q = q->next;
  93.     }
  94.     return i;
  95. }

  97. /*获取链表L中第i个结点的值*/
  98. Status GetElem(LinkList L, int i, ElemType *e)
  99. {
  100.     int j = 1;
  101.     LinkList q = L->next;
  102.     while (q && j < i)
  103.     {
  104.         q = q->next; //q指向i个结点
  105.         j++;
  106.     }
  107.     if (!q || j > i)
  108.     {
  109.         return ERROR;
  110.     }
  111.     *e = q->data;

  113.     return OK;
  114. }

  116. /*在链表L中的第i个结点之前插入一个结点*/
  117. Status ListInsert(LinkList L, int i, ElemType e)
  118. {
  119.     LinkList p = L, s;
  120.     int j = 1;
  121.     while (p && j < i)
  122.     {
  123.         p = p->next; //p指向第i个位置前一个结点
  124.         j++;
  125.     }
  126.     if (!p || j > i)
  127.         return ERROR;

  129.     s = (LinkList)malloc(sizeof(LNode));
  130.     s->data = e;        //
  131.     s->next = p->next; //
  132.     p->next=s;

  134.     return OK;
  135. }

  137. /*删除链表L中第i个位置的节点，并返回节点data域的值*/
  138. Status ListDelete(LinkList L, int i, ElemType *e)
  139. {
  140.     LinkList p = L, q;
  141.     int j = 1;
  142.     while (p && j < i)
  143.     {
  144.         p = p->next; //p指向第i个元素的前一个元素
  145.         j++;
  146.     }
  147.     if (!p || j > i)
  148.         return ERROR;

  150.     q = p->next; //q指向第i个元素
  151.     p->next = q->next;
  152.     *e = q->data;
  153.     free(q);
  154.     
  155.     return OK;
  156. }

  158. Status compile(ElemType e1, ElemType e2)
  159. {
  160.     if (e1 > e2)
  161.         return OK;
  162.     else
  163.         return FALSE;
  164. }

  166. int LocateElem(LinkList L, ElemType e)
  167. {
  168.     int i = 0;
  169.     LinkList p = L->next;
  170.     while (p)
  171.     {
  172.         i++;
  173.         if (compile(p->data, e))
  174.             return i;
  175.         p = p->next;
  176.     }
  177.     return 0;
  178. }


  181. /*
  182. 链表L，cur_e不是第一个结点，如果链表中存在cur_e结点，则用pur_e返回该结点前驱
  183. 并返回OK，否则返回INFEASIBLE
  184. */
  185. Status PriorElem(LinkList L, ElemType cur_e, ElemType *pur_e)
  186. {
  187.     LinkList p = L->next, q; //p指向第一个结点
  188.     while(p->next) //p的下一个结点不为空
  189.     {
  190.         q = p->next; //q指向p的下一个结点，
  191.         if (q->data == cur_e) //如果p的下一个结点值与cur_e相等
  192.         {
  193.             //*pur_e = (ElemType *)malloc(sizeof(ElemType));
  194.             *pur_e = p->data; //pur_e存放p的值
  195.             return OK;
  196.         }
  197.         p = q; //
  198.     }
  199.     return INFEASIBLE;
  200. }

  202. Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
  203. {
  204.     LinkList p = L->next;
  205.     while (p->next)
  206.     {
  207.         if (p->data == cur_e)
  208.         {
  209.             *next_e = p->next->data;
  210.             return OK;
  211.         }
  212.         p = p->next;
  213.     }
  214.     return INFEASIBLE;
  215. }

  217. /*对链表结点数据域排序，由大到小输出*/
  218. void ListSort(LinkList L)
  219. {
  220.     int i, j, tmp, len = ListLength(L);
  221.     LinkList p, q;
  222.     for (i = 0, p = L->next; i < len - 1; i++, p = p->next)
  223.     {
  224.         for (j = 0, q = L->next; j < len - i - 1; j++, q = q->next)
  225.         {
  226.             if (q->data > q->next->data)
  227.             {
  228.                 tmp = q->data;
  229.                 q->data = q->next->data;
  230.                 q->next->data = tmp;
  231.             }
  232.         }
  233.     }
  234. }

  236. Status ListTransver(LinkList L)
  237. {
  238.     LinkList p = L->next; //p指向第一个有效结点
  239.     while (NULL != p)
  240.     {
  241.         printf("%d ", p->data);
  242.         p = p->next;
  243.     }
  244.     printf("\n");
  245.     return OK;
  246. }

测试主函数:main.c
  1. #include "linklist.c"

  3. int main()
  4. {
  5.     //LinkList L = (LinkList)malloc(sizeof(LNode));
  6.     LinkList L;
  7.     ElemType e;
  8.     printf("初始化链表:-->");
  9.     if(InitLinkList(&L))
  10.     {
  11.         printf("链表初始化成功!\n");
  12.     }

  14.     /*----------------------------*/
  15.     printf("创建链表:\n");
  16.     int n;
  17.     printf("-->输入链表结点数量: ");
  18.     scanf("%d", &n);
  19.     CreateList(L, n);
  20.     printf("-->创建%d个结点链表为: ", n);
  21.     ListTransver(L);
  22.     printf("-->链表长度为: %d\n", ListLength(L));

  24.     /*----------------------------*/
  25.     printf("链表是否为空: ");
  26.     if (FALSE == ListEmpty(L))
  27.         printf("非空\n");
  28.     else
  29.         printf("空\n");

  31.     //-----------------------------
  32.     printf("释放链表中除头结点之外的所有结点: \n");
  33.     ClearList(L);
  34.     printf("-->链表是否为空: ");
  35.     if (FALSE == ListEmpty(L))
  36.         printf("非空\n");
  37.     else
  38.         printf("空\n");
  39.     printf("-->链表长度为: %d\n", ListLength(L));

  41.     //----------------------------------------
  42.     printf("创建新链表:\n");
  43.     printf("-->输入链表结点数量: ");
  44.     scanf("%d", &n);
  45.     CreateList2(L, n);
  46.     printf("-->创建%d个结点链表为: ", n);
  47.     ListTransver(L);
  48.     printf("-->链表长度: %d\n", ListLength(L));

  50.     //在第3个结点之前插入结点
  51.     printf("在第3个结点之前插入结点: \n");
  52.     ListInsert(L, 3, 6);
  53.     printf("-->插入新结点后: ");
  54.     ListTransver(L);

  56.     //将链表数据域按从大到小排序
  57.     printf("-->链表数据域按从大到小排序: \n");
  58.     printf("排序前: ");
  59.     ListTransver(L);
  60.     ListSort(L);
  61.     printf("排序后: ");
  62.     ListTransver(L);
  63.     
  64.     //获取第3个结点值
  65.     printf("获取第4个结点值: \n");
  66.     GetElem(L, 4, &e);
  67.     printf("-->第3个结点的值为: %d\n", e);

  69.     //删除第4个结点的值
  70.     printf("删除第3个结点的值:\n");
  71.     printf("删除前链表: ");
  72.     ListTransver(L);
  73.     ListDelete(L, 3, &e);
  74.     printf("-->第3个结点的值为: %d\n", e);
  75.     printf("删除后链表: ");
  76.     ListTransver(L);

  78.     //获取指定结点前驱
  79.     
  80.     //e = (ElemType *)malloc(sizeof(ElemType));
  81.     printf("获取值为5的结点的前驱: \n");
  82.     if (PriorElem(L, 5, &e) == OK)
  83.     {
  84.         printf("-->该结点有前驱，前驱值为: %d\n", e);
  85.     }
  86.     else
  87.     {
  88.         printf("-->不存在值为5的结点的前驱\n");
  89.     }

  91.     //获取指定结点后驱
  92.     printf("获取值为5的结点的后驱: \n");
  93.     if (NextElem(L, 5, &e) == OK)
  94.     {
  95.         printf("-->该结点有后驱，前驱值为: %d\n", e);
  96.     }
  97.     else
  98.     {
  99.         printf("-->不存在值为5的结点的后驱\n");
  100.     }
  101.     //free(e);

  103.     //释放整个链表
  104.     DestroyList(L);
  105.     //ListTransver(L);
  106.     return OK;
  107. }

阅读(2017) | 评论(0) | 转发(0) |
0

上一篇：树的遍历

下一篇：线性表的顺序实现(c语言)

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6