C语言实现的双链表功能完整示例分享！

本文实例讲述了C语言实现的双链表功能。分享给大家供大家参考，具体如下：

Dlist.h

  #ifndef __DLIST_H__  #define __DLIST_H__  #include<cstdio>  #include<malloc.h>  #include<assert.h>  typedef int ElemType;  typedef struct Node {    ElemType data;    struct Node *prio;    struct Node *next;  }Node,*PNode;  typedef struct List {    PNode first;    PNode last;    size_t size;  }List;  void InitDlist(List *list);//初始化双链表  void push_back(List *list, ElemType x);//在双链表的末尾插入元素  void push_front(List *list, ElemType x);//在双链表的头部插入元素  void show_list(List *list);//打印双链表  void pop_back(List *list);//删除双链表的最后一个元素  void pop_front(List *list);//删除双链表的第一个元素  void insert_val(List *list, ElemType val);//将数据元素插入到双链表中（要求此时双链表中的数据元素顺序排列）  Node* find(List *list, ElemType x);//查找双链表中数据值为x的结点  int length(List *list);//求双链表的长度  void delete_val(List *list, ElemType x);//按值删除双链表中的某个数据元素  void sort(List *list);//对双链表进行排序  void reverse(List *list);//逆置双链表  void clear(List *list);//清除双链表  void destroy(List *list);//摧毁双链表  //优化  Node* _buynode(ElemType x);//创建结点  #endif    

Dlist.cpp

  #include"Dlist.h"  Node* _buynode(ElemType x) {    Node *s = (Node*)malloc(sizeof(Node));    assert(s != NULL);    s->data = x;    s->prio = s->next = NULL;    return s;  }  void InitDlist(List *list) {    Node *s = (Node*)malloc(sizeof(Node));    assert(s != NULL);    list->first = list->last = s;    list->first->prio = NULL;    list->last->next = NULL;    list->size = 0;  }  void push_back(List *list, ElemType x) {    Node *s = _buynode(x);    s->prio = list->last;    list->last->next = s;    list->last = s;    list->size++;  }  void push_front(List *list,ElemType x) {    Node *s = _buynode(x);    if (list->first == list->last) {      s->prio = list->first;      list->first->next = s;      list->last = s;    }    else {      s->next = list->first->next;      s->next->prio = s;      s->prio = list->first;      list->first->next = s;    }    list->size++;  }  void show_list(List *list) {    Node *p = list->first->next;    while (p != NULL) {      printf("%d->", p->data);      p = p->next;    }    printf("Nul.n");  }  void pop_back(List *list) {    if (list->size == 0) return;    Node *p = list->first;    while (p->next != list->last)      p = p->next;    free(list->last);    list->last = p;    list->last->next = NULL;    list->size--;  }  void pop_front(List *list) {    if (list->size == 0) return;    Node *p = list->first->next;    if (list->first->next == list->last) {      list->last = list->first;      list->last->next = NULL;    }    else {      list->first->next = p->next;      p->next->prio = list->first;    }    free(p);    list->size--;  }  void insert_val(List *list, ElemType x) {    Node *p = list->first;    while (p->next != NULL && p->next->data < x)      p = p->next;    if (p->next == NULL)      push_back(list, x);    else {      Node *s = _buynode(x);      s->next = p->next;      s->next->prio = s;      s->prio = p;      p->next = s;      list->size++;    }  }  Node* find(List *list, ElemType x) {    Node *p = list->first->next;    while (p!=NULL && p->data != x)      p = p->next;    return p;  }  int length(List *list) {    return list->size;  }  void delete_val(List *list, ElemType x) {    if (list->size == 0) return;    Node *p = find(list, x);    if (p == NULL) {      printf("要删除的数据不存在！n");      return;    }    if (p == list->last) {      list->last = p->prio;      list->last->next = NULL;    }    else {      p->next->prio = p->prio;      p->prio->next = p->next;    }    free(p);    list->size--;  }  void sort(List *list) {    if (list->size == 0 || list->size == 1) return;    Node *s = list->first->next;    Node *q = s->next;    list->last = s;    list->last->next = NULL;    while (q != NULL) {      s = q;      q = q->next;      Node *p = list->first;      while (p->next != NULL && p->next->data < s->data)        p = p->next;      if (p->next == NULL) {        s->next = NULL;        s->prio = list->last;        list->last->next = s;        list->last = s;      }      else {        s->next = p->next;        s->next->prio = s;        s->prio = p;        p->next = s;      }    }  }  void reverse(List *list) {    if (list->size == 0 || list->size == 1) return;    Node *p = list->first->next;    Node *q = p->next;    list->last = p;    list->last->next = NULL;    while (q != NULL) {      p = q;      q = q->next;      p->next = list->first->next;      p->next->prio = p;      p->prio = list->first;      list->first->next = p;    }  }  void clear(List *list) {    if (list->size == 0) return;    Node *p = list->first->next;    while (p != NULL) {      if (p == list->last) {        list->last = list->first;        list->last->next = NULL;      }      else {        p->next->prio = p->prio;        p->prio->next = p->next;      }      free(p);      p = list->first->next;    }    list->size = 0;  }  void destroy(List *list) {    clear(list);    free(list->first);    list->first = list->last = NULL;  }    

• 1
• 2
• 下一页