Written with StackEdit中文版.

双向链表

简介

为克服单链表、循环链表的单向性，即如果要查询结点的直接前驱需要从表头指针出发，双向链表中的结点具有两个指针域：其一指向直接后继，另一指向直接前驱

声明与定义

1
2
3
4
5
6
7
8
9
10
11
12
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;

//双向链表的存储结构
typedef struct DuLNode
{
  ElemType data;//数据域
  struct DuLNode* prior;//前驱指针域
  struct DuLNode* next;//后继指针域
}DuLNode, * DuLinkList;

相关方法

手动输入n个元素的值，创建一个双向链表L

注意是用返回值接收链表L

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
DuLinkList CreateList_L(int n){
  DuLNode* end, * p, * L;
  L = (DuLinkList)malloc(sizeof(DuLNode));//L是头结点
  if (L == NULL){
    return ERROR;
  }
  end = L;
  for (int i = 0; i < n; i++){
    p = (DuLinkList)malloc(sizeof(DuLNode));//p是普通结点
    if (p == NULL){
      return ERROR;
    }
    scanf_s("%d", &p->data);
    end->next = p;
    //双向
    p->prior = end;
    end = p;//这个end很重要,保留这个循环产生的p结点,在下一个循环中使用
  }
  end->next = L;//end是尾结点，指针域是头结点，形成循环链表
  L->prior = end;//头结点的前驱再指向尾结点，形成双向循环链表
  return L;
}

返回链表L的第i个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status GetElem_L(DuLinkList* L, int i,ElemType* e){
  //L是带头结点的单链表的头指针,若第i个元素存在则赋值给e并返回
  DuLinkList p;
  p = (DuLinkList)malloc(sizeof(DuLNode));
  p = (*L)->next;
  int j = 1;
  while (p && j < i){
    p = p->next;
    ++j;
  }
  if (!p || j > i || p == *L){
    printf("第%d个元素不存在或该结点是头结点!\n", i);
    return ERROR;
  }
  *e = p->data;
  return OK;
}

在链表L的第i个位置插入元素e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Status ListInsert_DuL(DuLinkList* L, int i, ElemType e){
  DuLinkList p;
  p = (DuLinkList)malloc(sizeof(DuLNode));
  p = *L; int j = 0;

  while (p && j < i) {//寻找第i个结点
    p = p->next; ++j;
  }
  if (!p || j > i || p == *L) {
    printf("第%d个元素不存在或该结点是头结点!\n", i);
    return ERROR;
  }
  DuLinkList s;
  s = (DuLinkList)malloc(sizeof(DuLNode));//生成一个新节点并插入L中
  if (s != NULL){
    s->data = e;
    //双向
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
  }
  return ERROR;
}

删除链表L的第i个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListDelete_DuL(DuLinkList *L, int i, ElemType* e){
  //将被删除的第i个元素赋值给e并返回
  DuLinkList p;
  p = (DuLinkList)malloc(sizeof(DuLNode));
  p = *L; int j = 0;
  while (p->next && j < i - 1) {//寻找第i个结点，并令p指向其前驱
    p = p->next; ++j;
  }
  if (!(p->next) || j > i - 1 || p->next == *L) {//删除位置不合理
    printf("删除的位置不合理!\n");
    return ERROR;
  }
  p = p->next;//让p指向被删除元素的位置，而不是其前驱
  *e = p->data;//赋值被删除元素
  p->prior->next = p->next; //被删除的结点 其前驱的后继 指向 其后继
  p->next->prior = p->prior;//被删除的结点 其后继的前驱 指向 其前驱
  free(p); //释放被删除的结点
  return OK;
}

链表排序函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status SelectSort(DuLinkList *L){
  printf("开始对链表进行冒泡排序!\n");
  DuLinkList p, q, small;
  DuLNode* head = *L;
  ElemType temp, temp1;

  //冒泡排序的变形
  for (p = (*L)->next; p->next != head; p = p->next) {
    //每次循环都找出一个最小值，将最小值交换到第一位，然后将指针向后移动一位
    small = p;
    for (q = p->next; q != head; q = q->next) { /*由前向后遍历，找出最小的节点*/
      if (q->data < small->data) small = q;//小于就是从小到大排序，大于就是从大到小排序
    }
    if (small != p) {//将较小或最小的结点的数据域与当前循环的起始结点交换
      temp = p->data;
      p->data = small->data;
      small->data = temp;
    }
  }
  return OK;
}

顺序遍历链表的所有元素

1
2
3
4
5
6
7
8
9
10
void ListTraverse(DuLinkList L)
{
  DuLNode* p = L;//储存链表头指针
  printf("遍历双向链表的全部元素: ");
  while (L->next != p){ //注意循环结束条件是下一个结点是头结点
    L = L->next;
    printf("%d ", L->data);
  }
  printf("\n");
}

方法测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main(void)//上述函数的测试
{
  DuLinkList MyList;
  int size = 0;
  int pos = 0;
  ElemType e = 0;

  printf("输入链表的大小: ");
  scanf_s("%d", &size);
  printf("根据大小按顺位序对双向链表赋值\n");
  MyList = CreateList_L(size);
  ListTraverse(MyList);
  
  printf("需要返回双向链表第几位的元素：");
  scanf_s("%d", &pos);
  GetElem_L(&MyList, pos, &e);
  printf("链表第%d位的元素是:%d\n", pos, e);

  printf("需要向双向链表第几位插入元素：");
  scanf_s("%d", &pos);
  printf("需要插入的元素是：");
  scanf_s("%d", &e);
  ListInsert_DuL(&MyList, pos, e);
  ListTraverse(MyList);

  printf("需要删除双向链表的第几位元素: ");
  scanf_s("%d", &pos);
  ListDelete_DuL(&MyList, pos, &e);
  printf("被删除的元素是:%d\n", e);
  ListTraverse(MyList);

  SelectSort(&MyList);
  ListTraverse(MyList);
  return 0;
}