数据结构之单向链表02

发布时间:2016-12-6 8:58:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构之单向链表02",主要涉及到数据结构之单向链表02方面的内容,对于数据结构之单向链表02感兴趣的同学可以参考一下。

今天的训练题目是,带头单向链表的操作 1.带头单向链表建立 2.带头单向链表节点添加 3.带头单向链表节点删除 4.带头单向链表数据排序 5.两个带头递减单向链表合并成一个链表 6.带头/不带头单向链表的倒序 ================================================================= 单链表操作 NOTE:包括插入,删除,排序,倒序等 ================================================================= 1.单项链表建立: typedef struct Node_t {      int data;      struct Node_t *next; }NODE_T; /* 带头的单项链表 */ NODE_T *Init_list(int len) {      NODE_T *head;      NODE_T *p1, p2;      int err = 0;      int n;      head = (NODE_T *)malloc(sizeof(struct Node_t));      if (!head) {          fprintf(stderr, "Create link list head failed\n");          return NULL;      }      p1 = head;      while (len--) {          p2 = (struct Node_t *)malloc(sizeof(struct Node_t));          if (!p2) {              err++;              break;          }          p1->next = p2;          p1 = p1->next;      }      p1->next = NULL;      /* free memory if malloc failed */      while (err--) {          p1 = head;          n = err;          while (n--) {              p2 = p1->next;              p1 = p2;          }          free(p1);          p1 = NULL;      }      return head; } ========================================================== 获取第i个元素,单向链表不支持随机读取,必须从头指针开始遍历 ========================================================== /** * @brief get_link_list * * @param link * @param i 1 <= i <= 表长,if i == 0,return list head * * @return */ NODE_T *get_link_list(NODE_T *link, int i) {      NODE_T *head, p;      if (!link)          return NULL;      head  = link;      while (i-- && head != NULL) {          p = head->next;          head = p;      }      return head; } ============================================================ 在第cursor节点之前插入节点,data域为value, 插入位置大于1, 必须在头指针以后, 0节点是头头节点 ============================================================ /** * @brief insert_linklist * * @param link * @param cursor    1 <= cursor <= 表长 * @param value * * @return */ int insert_linklist(NODE_T *link, int cursor, int value) {      NODE_T *head, *p;      int i;      if (!link)          return -1;      head = link;      i = 0;      while (head != NULL && i < cursor-1) {          head = head->next;          i++;      }      p = (NODE_T * )malloc(NODE_T);      if (p == NULL)          return -1;      p->next = head->next      p->data = value;      head->next = p;      return 0; } ======================================================= 删除节点操作,不允许删除链表头,需要先找到删除节点的前驱节点 比如删除第二个节点,需先找到第一个节点(节点计数从非头节点开始) ======================================================= int delete_linklist(NODE_T *head, int cursor) {      NODE_T *p, p1;      int i = 0;      if (!head)          return -1;      p = head;      while (p->next != NULL && i < cursor-1)    {          p = p->next;          i++;      }      if (p->next == NULL) /* the end */          fprintf(stderr, "No this position\n");      else {          p1 = p->next;          p->next = p->next->next;          free(p1);      }      return 0; } ======================================================== 带头单向链表的排序 使用冒泡法,递减排序 ======================================================== #define SWAP(a,b)    {a = a + b; \              b = a - b;    \              a = a - b;} int sort_list(NODE_T *head) {      NODE_T *p1, p2;      int n, len = 0;      if (!head)          return -1;      /* calc list length */      p1 = head->next;      while (p1 != NULL) {          len++;          p1 = p1->next;      }      while (len--) {          p1 = head->next;          /* no compare list head, compare count = len(no head) - 1 */          n = len - 1;          while (p1 != NULL && n--) {              p2 = p1->next;              if (p1->data <= p2->data)                  SWAP(p1->data, p2->data);              p1 = p2;          }      }      return 0; } ========================================================== 两个带头的递减链表,合并成一个递减的链表 ========================================================== NODE_T *merge_linklist(NODE_T *la, NODE_T *lb) {      NODE_T *pa, *pb, *pc;      if (!la || !lc)          return NULL;      lc = la; /* 以la节点头作为合并后节点头 */      pa = la->next;      pb = lb->next;      pc = lc;      while (pa != NULL && pb != NULL) {          if (pa->data >= pb->data) {              pc->next = pa;              pc = pa;              pa = pa->next;          }          else {              pc->next = pb;              pc = pb;              pb = pb->next;          }      }      /* 连接pa或pb中剩余的节点 */      if (pa != NULL)          pc->next = pa;      else          pc->next = pb;      return lc; } ============================================================= 单项链表的倒序 ============================================================= 基本思路有两种 1.遍历整个链表,将数据提取出来,然后在逆向赋值给链表各节点 这需要至少遍历两次链表,并且用于存储数据的数组,需要提前申请(没遍历 之前链表节点数量位置,则该数组大小不确定,是否应足够大),并且只是 数据倒序了,链表结构并没有倒序 2.逆向操作链表,即把第一个节点,作为最后一个,并依次倒置 下面描述第二种,区别带头节点和不带节点 带头单向链表的倒序 --------------------- 不带头单向链表倒序 --------------------- NODE_T *reverse_link(NODE_T *head) {      NODE_T *pn, *pt;      NODE_T *pr = NULL;      if (!head)          return NULL;      pn = head; /* no list head */      while (pn != NULL) {          pt = pn->next;          pn->next = pr;          pr = pn;          pn = pt;      }      return pr; } 带头单向链表倒序, 头节点不变 --------------------------------- NODE_T *reverse_link(NODE_T *head) {      NODE_T *pn, *pt, ph;      NODE_T *pr = NULL;      if (!head)          return NULL;      ph = head;      pn = head->next;      while (pn != NULL) {          pt = pn->next;          pn->next = pr;          pr = pn;          pn = pt;      }      ph->next = pr;      return ph; }

上一篇:Android深入浅出系列之Bluetooth—蓝牙操作(二)
下一篇:好看的外国电影

相关文章

相关评论