Python数据结构与算法：第3-9课时：双向链表及添加元素、判断链表是否为空

双向链表

后继节点，某个节点，前驱节点。

例子：

比如40这个节点的前驱节点就是100， 后继节点就是6

定义：

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。

所需要的一些操作：

• is_empty() 链表是否为空
• length() 链表长度
• travel() 遍历链表
• add(item) 链表头部添加
• append(item) 链表尾部添加
• insert(pos, item) 指定位置添加
• remove(item) 删除节点
• search(item) 查找节点是否存在

实现

节点的代码：

class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None

self.next 为后继节点的地址，
prev 为前继节点的地址。

双链列表定义的代码：

只需要顶一个函数头就可以了，和单链列表一样。

class DLinkList(object):
    """双向链表"""
    def __init__(self,node = None):
        self._head = node

判断链表是否为空：

def is_empty(self):
    """判断链表是否为空"""
    return self._head == None

与单向链表一样。

判断双向链表的长度：

与单向链表一样：

只需要从头遍历到尾就可以实现了。

def length(self):
    """返回链表的长度"""
    cur = self._head
    count = 0
    while cur != None:
        count += 1
        cur = cur.next
    return count

遍历双向链表的长度：

也与单链列表一致：

def travel(self):
    """遍历链表"""
    cur = self._head
    while cur != None:
        print(cur.item)
        cur = cur.next

在头部插入一个节点 add：

让 之前表头self._head指向 新节点node地址。

实现代码：

def add(self, item):
    """头部插入元素"""
    node = Node(item)
    if self.is_empty():
        # 如果是空链表，将_head指向node
        self._head = node
    else:
        # 将node的next指向_head的头节点
        node.next = self._head
        # 将_head的头节点的prev指向node
        self._head.prev = node
        # 将_head 指向node
        self._head = node

在双向链表尾部添加元素：

实现代码：

def append(self, item):
    """尾部插入元素"""
    node = Node(item)
    if self.is_empty():
        # 如果是空链表，将_head指向node
        self._head = node
    else:
        # 移动到链表尾部
        cur = self._head
        while cur.next != None:
            cur = cur.next
        # 将尾节点cur的next指向node
        cur.next = node
        # 将node的prev指向cur
        node.prev = cur

在双向链表尾指定位置插入元素：

有数双向链表将节点的头尾均连起来，所以只需要一个游标就可以实现了。

实现代码：

def insert(self, pos, item):
    """在指定位置添加节点"""
    if pos <= 0:
        self.add(item)
    elif pos > (self.length()-1):
        self.append(item)
    else:
        node = Node(item)
        cur = self._head
        count = 0
        # 移动到指定位置的前一个位置
        while count < (pos-1):
            count += 1
            cur = cur.next
        # 将node的prev指向cur
        node.next = cur
        # 将node的next指向cur的下一个节点
        node.prev = cur.prev
        # 将cur的下一个节点的prev指向node
        cur.prev.next = node
        # 将cur的next指向node
        cur.prev = node

一、前言

线性表的顺序存储结构（例如：数组），存储空间是连续的因此我们不用担心元素之间的逻辑关系，线性表最大优点在于可以快速的存取表中任一位置的元素。
线性表顺序存储的缺点在于插入和删除操作时需要移动大量元素时间复杂度为O(n)，线性表的长度也难以适应变化较大的情况，且线性表的扩容需要重新开辟出一块满足大小需求且连续的空间，这容易造成空间碎片。
我们学习链式存储结构的单链表，单链表可以很好的解决数组的这些问题，但是访问单链表的某一位置的元素，需要遍历整个单链表，且每次都要头开始进行单方向的遍历。为了解决这些问题我们引用循环链表和双向链表。

二、循环链表

循环链表：将单链表中最后一个结点的指针域指向头结点（带头结点的链表）或首元结点（不带头结点的链表），使整个单链表形成一个首尾相连的环。

循环链表带头结点的空表：

非空表：

在判断单链表是否是最后一个结点时只需要判断p->next是否为NUll，但是循环链表需要判断p->是否等于头结点，若等于则说明是最后一个结点，否则不是。

当我们经常在链表尾部进行增查操作时，我们可以使用带尾指针的循环链表，将头指针换成尾指针指向链表最后一个结点即可。

循环链表解决约瑟夫环问题

约瑟夫环问题： 即有n个人围成一圈每个人编号为1-n，从第k个人开始报号，报号为m的人出圈，剩余的人继续重复此过程，直至所有人都出圈，输出出圈的先后顺序。

约瑟夫环有两大难题：

1. 如何循环重复出圈
2. 如歌判断循环结束而不会造成死循环

第一个问题我们用环形的循环链表完美解决，出圈的人只需要删除此结点即可。
解决第二个问题有三种思路

• 带头结点的循环链表这样可以通过判断是否只剩一个头结点实现，但是每次循环要判断结点是否为头结点然后跳过头结点。这样显然是没有体现链式存储结构不连续不需要就删除的优点
• 如果不用头结点，只是循环判断条件为p->next != null 这样最后剩余的一个结点会造成死循环。我们换一个思路，最后剩余的一个结点一定是最后出圈的，既然这样我们在循环结束之后再出圈也是可以的，那么只要最后一个结点的next是自己就说明只剩一个结点了这个时候结束循环，最后再单独让最后一个结点出圈。
• 我们可以另外用一个变量记录圈中剩余的人数，这样在剩余人数为0时跳出循环即可。

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	int data;
	struct node*next;
}Node,*link;
yuesefuhuan(int n,int m,int k)
{
	int i,count=0;
	Node *p = NULL,*pr = NULL,*q = NULL;  //q暂存第一个节点以便后续建立循环链表 
	for(i = 1;i <= n;i++){
			p=(Node*)malloc(sizeof(Node));
	if(p == NULL)
	{
		printf("memory out use");
		exit(0);
	}
		p->data = i;
	if(q == NULL)  //第一个节点的情况 
	{
		q = p;
		pr = p;        //pr挂起整个链表 
	}else {          //非第一个节点 
	   pr->next = p;
	   pr = p; 
	        }
   }
		p->next = q;  //链表最后一个节点指向第一个节点构成循环链表 
	p = q;
	for(i = 0;i < k-1;i++){         
		p = p->next;   //p指向开始报数的节点 
	}
      while(p != p->next){    //循环退出的条件仅剩一个节点最后另外输出否则就是死循环 
           count++;    //计数 
      if(count != m)
	{
		q = p;  //q指向要删除节点的前一个节点 
		p = p->next;
	}else {
		count = 0;
		 pr = p;   //pr 暂存要删除的节点，以便删除后不影响p继续循环下一个节点 
		printf("%5d",pr->data);
		q->next = pr->next;
		free(pr);
		p = p->next;	
	}
	
 } 
 printf("%5d",p->data);
	
}
int main()
{
	int n,m,k;
	printf("请输入总人数：");
	scanf("%d",&n);
		printf("请输入到第几个人出列：");
	scanf("%d",&m);
	printf("请输入从第几个人开始报数："); 
	scanf("%d",&k);
	 yuesefuhuan(n,m,k);
	return 0;
}

循环数组解法：

#include<stdio.h>
#include <stdlib.h>
int fun(int n, int m, int k);
int main() {
    int n = 0, m = 0, k = 0;
     scanf("%d%d%d", &n, &m, &k);
     fun(n, m, k);
     return 0;
}
int fun(int n, int m, int k) {
   //动态创建数组 开辟内存 
   int *flags = (int*)malloc(sizeof(int)*n); 
    int i;
   //数组全初始化为0 
for(  i = 0;i < n;i++ ){
	flags[i] = 0;
}
  int nowIndex = k - 1;                    // 当前下标
   int count = 0;                           // 计数器
  int nowLength = n;                         // 剩余人数
  while (nowLength > 0) {
        if (flags[nowIndex] == 0) {
             count ++;
             if (count == m) {
                   count = 0;
                   flags[nowIndex] = 1;
                   nowLength --;
                   printf("%d ", nowIndex + 1);
                  }
             }
           nowIndex ++;
              if (nowIndex == n) {
              nowIndex = 0;
              }
     }
}

三、双向链表

双向链表：链表中每个结点有两个指针域，一个指向直接前趋，一个指向后继，构成一个双向的链表。

//链表结点定义：
typedef struct node{
	int data;  //数据域
	struct node* next;  //直接前趋
	struct node* prior;  //直接后继
}Node;

双向链表带头结点的空表：

非空表：

删除结点操作

	//p为待删除结点    
	q=p->prior;
	q->next=p->next;
	p->next->prior=q;
	free(p);

插入结点操作：

p->prior = q;  //p的前驱指向q
q->next->prior = p;   // q的直接后继结点的前驱指向p
p->next = q->next;   //p的后继指向q的直接后继结点
q->next = p; // q的后继指向p

双向链表的创建、遍历、删除某一个结点

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
	int data;
	struct node*next;
	struct node*prior;
}Node;
Node*create(Node*head,int n)
{
	//创建头结点 
	head=(Node*)malloc(sizeof(Node));
	head->next=NULL;
	head->prior=NULL;
	head->data=0;
	int a;
	Node*p=NULL,*q=head;
    //初始化双向链表 
	for(int i=0;i<n;i++)
	{
		//初始化新的结点 p 
			p=(Node*)malloc(sizeof(Node));
	    p->next=NULL;
     	p->prior=NULL;
		scanf("%d",&a);
		p->data=a;
		 //移动q指针，指向最后一个结点 
		q->next=p;
		p->prior=q;
		q=q->next;

	 }         
      return head; 
}
  //遍历双向链表，前后两种遍历 
void display(Node*head)
{
	Node*pr = head->next,*p = NULL;
	while(pr)
	{
		printf("%5d",pr->data);
		p=pr;
		pr=pr->next;
	}
	printf("\n");
	while(p->prior)
	{
		printf("%5d",p->data);
		p=p->prior;
	} 
	printf("\n");  
}
 Node*del(Node*head,int num)
{
	Node*p=head->next,*q=NULL;
	if(head==NULL)
	{
		printf("empty list\n");
		return NULL;
	}
	while(p->data != num)
	{
		p = p->next;
	}
	if( p == NULL)
	{
		printf("not find \n");
	}
	//p为待删除结点    
	q=p->prior;
	q->next=p->next;
	p->next->prior=q;
	free(p);
return head;
}

//在链表尾部加入一个结点  
Node*add(Node*head,int num)
{
	Node*p=NULL,*pr=head;
	p=(Node*)malloc(sizeof(Node));
	if(p==NULL){
		printf("memory out use \n");
		return NULL;
	}
	p->data=num;
    //遍历得到最后一个结点 
		while(pr->next){
			pr=pr->next;
		}
		//增加一个结点 
		pr->next=p;
		p->prior=pr;
		p->next=NULL;
	return head;
}
int main()
{
	int n,m,k;
	scanf("%d",&n);
	Node*head=NULL;
	head=create(head,n);
	display(head);
	printf("please input a delete number:\n");   //删除一个数k 
	scanf("%d",&k);
	head=del(head,k);
	display(head);
	printf("please input a add number:\n");  //增加一个数m 
	scanf("%d",&m);
	head=add(head,m); 
	display(head);   
	return 0;
}

四、总结

1. 不管是循环链表还是双向链表本质都是线性链式存储的链表，不同的是改变链表的指针指向和数量使得链表能够更加方便进行某一场景的使用。

2. 在解决链表问题中为了使插入和删除任何位置都能一致操作，通常会加入一个头结点，头结点不是第一个结点，头结点也称为哑结点，其数据域没有意义。当然头结点并不是必须的，只是方便操作引用的一个结点。
3. 链表的增删操作结合图形更方便写代码和理解过程。

参考《大话数据结构》(程杰)