Chinaunix首页 | 论坛 | 博客
  • 博客访问: 187883
  • 博文数量: 54
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2018
  • 用 户 组: 普通用户
  • 注册时间: 2013-03-31 23:14
文章存档

2014年(2)

2013年(52)

分类: 嵌入式

2013-08-19 20:40:35

数据结构含三个内容:逻辑结构;线性(线性表、栈、队)和非线性(树形、图形)
                              储存结构;顺序和链式
                              运算算法;检索,排序,插入,删除,修改等
实现对链表的基本操作:重点是掌握    指针与结构体   链表与结构体指针
链表含有头结点,对链表的操作就是以头结点开始的遍历过程,在过程中操作;
是单向链表,链表的操作主要是指针的操作,本程序clist.c的实现细节不重要,重要的是指针的应用。
conmon.h

点击(此处)折叠或打开

  1. //本程序中的链表都带头节点
  2. #ifndef _COMMON_H_
  3. #define _COMMON_H_

  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <strings.h>

  8. #define TRUE 1
  9. #define FALSE 0

  10. typedef int datatype;
  11. typedef struct clist
  12. {
  13.     datatype data;
  14.     struct clist *next;
  15. }clistnode, *clistlink;

  16. clistlink creat_clist_node(datatype x);
  17. clistlink creat_clist(void);
  18. void set_empty_clist(clistlink head);
  19. int isempty_clist(clistlink head);
  20. int get_length_clist(clistlink head);
  21. int get_elem_clist(clistlink head, int i, datatype *ret);
  22. int locate_clist(clistlink head, datatype x);
  23. void insert_clist(clistlink head, datatype x, int i);
  24. int del_clist(clistlink head, int i, datatype *ret);
  25. void show_clist(clistlink head);
  26. #endif
clist.c

点击(此处)折叠或打开

  1. ////本程序中的链表都带头节点
  2. #include "common.h"

  3. clistlink creat_clist_node(datatype x)//创建空节点
  4. {
  5.     clistlink q = (clistlink)malloc(sizeof(clistnode));
  6.     assert(q);
  7.     q->data = x;
  8.     q->next = NULL;
  9.     return q;
  10. }
  11. clistlink creat_clist(void)//创建头节点
  12. {
  13.     clistlink head = creat_clist_node(-1);
  14.     return head;
  15. }
  16. void set_empty_clist(clistlink head)//清空链表,(不是对内存单元的清空,而是对头指针的指向操作
  17. {
  18.     head->next = NULL;
  19. }
  20. int isempty_clist(clistlink head)//判断是否为空链表
  21. {
  22.     return head->next == NULL ? TRUE : FALSE;
  23. }
  24. int get_length_clist(clistlink head)//获取链表长度
  25. {
  26.     clistlink p = NULL;
  27.     int count = 0;
  28.     p = head->next;
  29.     while(p)
  30.     {
  31.         count ++;
  32.         p = p->next;
  33.     }
  34.     return count;
  35. }
  36. int get_elem_clist(clistlink head, int i, datatype *ret)//获取链表元素
  37. {
  38.     int j=1;
  39.     clistlink p = head->next;
  40.     if(i<1 || i>get_length_clist(head))
  41.     {
  42.         printf("i is wrong!\n");
  43.         return FALSE;
  44.     }
  45.     while(j<i)
  46.     {
  47.         p = p->next;
  48.         j++;
  49.     }
  50.     *ret = p->data;
  51.     return TRUE;
  52. }
  53. int locate_clist(clistlink head, datatype x)//返回值为x的节点在链表中的位置
  54. {
  55.     int i = 0;
  56.     clistlink p = head->next;
  57.     if(p == NULL)
  58.         return i;
  59.     while(p)
  60.     {
  61.         if(p->data != x)
  62.         {
  63.             p = p->next;
  64.             i++;
  65.         }
  66.         else
  67.             return i+1;
  68.     }
  69. }

  70. void insert_clist(clistlink head, datatype x, int i)//在第i个元素前插入值为x的节点
  71. {
  72.     int j = 1;
  73.     clistlink p = NULL, q = NULL;
  74.     if(i<1 || i>get_length_clist(head)+1)
  75.     {
  76.         printf("i is wrong!\n");
  77.         return;
  78.     }
  79.     q = creat_clist_node(x);
  80.     p = head;
  81.     while(j<i)
  82.     {
  83.         p = p->next;
  84.         j++;
  85.     }
  86.     q->next = p->next;
  87.     p->next = q;
  88.     
  89. }
  90. int del_clist(clistlink head, int i, datatype *ret)//删除指定位置的元素
  91. {
  92.     int j=1;
  93.     clistlink p = head, q = NULL;
  94.     if(isempty_clist(head))
  95.     {
  96.         printf("clist is empty!\n");
  97.         return FALSE;
  98.     }
  99.     if(i<1 || i>get_length_clist(head))
  100.     {
  101.         printf("i is wrong!\n");
  102.         return FALSE;
  103.     }
  104.     while(j<i)
  105.     {
  106.         p = p->next;
  107.         j++;
  108.     }
  109.     q = p->next;
  110.     *ret = q->data;
  111.     p->next = q->next;
  112.     free(q);
  113.     q = NULL;
  114.     return TRUE;
  115. }

  116. void show_clist(clistlink head)//打印链表
  117. {
  118.     clistlink p = head->next;
  119.     while(p)
  120.     {
  121.         printf("%d,",p->data);
  122.         p = p->next;
  123.     }
  124.     putchar('\n');
  125. }
main.c

点击(此处)折叠或打开

  1. #include "common.h"

  2. int main (int argc, char *argv[])
  3. {
  4.     int i=1;
  5.     datatype k;
  6.     clistlink head = creat_clist();
  7.     while(i<=5)//创建一个1,2,3,4,5的链表
  8.     {
  9.         insert_clist(head, i, i);
  10.         i++;
  11.     }
  12.     show_clist(head);//打印链表
  13.     get_elem_clist(head, 3, &k);//获取指定位置的元素,并返回值
  14.     printf("%d\n",k);
  15.     del_clist(head, 2, &k);//删除指定元素,并返回值
  16.     show_clist(head);
  17.     return 0;
  18. }

阅读(1085) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~