---

1. 循环单链表的实现

结构体：

typedef struct LNode{           
    ElemType data;                  
    struct LNode *next; 
}LNode, *Linklist;
1
2
3
4

1.1 循环单链表的初始化：InitList(LinkList &L)

bool InitList(LinkList &L){    
    L = (LNode *)malloc(sizeof(LNode));  
    if(L==NULL)             
        return false;    
    // 最后一个结点的next指针指向头结点    
    L->next = L;       
    return true;
}
1
2
3
4
5
6
7
8

1.2 判断循环单链表是否为空：Empty(LinkList L)

bool Empty(LinkList L){    
    if(L->next == L)       
        return true;    
    else             
        return false;
}
1
2
3
4
5
6

1.3 判断结点p是否为循环单链表的表尾结点：isTail(LinkList L, LNode *p)

bool isTail(LinkList L, LNode *p){ 
    if(p->next == L)          
        return true;      
    else            
        return false;
}
1
2
3
4
5
6

---

2. 循环双链表的实现

结构体：

typedef struct DNode{           
    ElemType data;                  
    struct LNode *next; 
}DNode, *Linklist;
1
2
3
4

2.1 循环双链表的初始化：InitList(LinkList &L)

bool InitDLinkList(DLinklist &L){  
    L = (DNode *) malloc(sizeof(DNode));  
    if(L==NULL)            
        return false;    
    // 头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点 
    L->prior = L;      
    L->next = L;
}
1
2
3
4
5
6
7
8

2.2 判断循环双链表是否为空：Empty(LinkList L)

和单链表一样

bool Empty(DLinklist L){   
    if(L->next == L)       
        return true;      
    else           
        return false;
}
1
2
3
4
5
6

2.3 判断结点p是否为循环双链表的表尾结点：isTail(LinkList L, LNode *p)

和单链表一样

// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){   
    if(p->next == L)        
        return true;     
    else            
        return false;
}
1
2
3
4
5
6
7

2.4 循环双链表的后插：InsertNextDNode(DNode *p, DNode *s)

2.5 循环双链表的后删除：DeletNextDNode(DNode *p)

注意，循环双链表不需要if判断

bool DeletNextDNode(DNode *p){  
    // 找到p的后继结点q       
    DNode *q =p->next;        
    //循环双链表不用担心q结点的下一个结点为空  
    p->next = q->next;    
    q->next->prior=p;    
    free(q);      
    return true;
}
1
2
3
4
5
6
7
8
9

---

3. 静态链表

静态链表的定义：用数组的方式实现的链表。
分配一整片连续的内存空间，各个结点集中安置，每个结点包括：数据元素和下一个结点的数组下标。

特点:
优点：增、删操作不需要大量移动元素。
缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！
 
适用场景：
①不支持指针的低级语言；
②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

3.1 静态链表的使用

#define MaxSize 10        //静态链表的最大长度
struct Node{              //静态链表结构类型的定义  
    ElemType data;        //存储数据元素    
    int next;             //下一个元素的数组下标
};

// 用数组定义多个连续存放的结点
void testSLinkList(){    
    struct Node a[MaxSize];  //数组a作为静态链表, 每一个数组元素的类型都是struct Node    
    ...
}

1
2
3
4
5
6
7
8
9
10
11
12

也可以这么定义：

#define MaxSize 10        //静态链表的最大长度
typedef struct{           //静态链表结构类型的定义       
    ELemType data;        //存储数据元素     
    int next;             //下一个元素的数组下标
}SLinkList[MaxSize];

void testSLinkList(){      
    SLinkList a;
}
1
2
3
4
5
6
7
8
9

第一种是我们更加熟悉的写法，第二种写法则更加侧重于强调 a 是一个静态链表而非数组。

---

3.2 静态链表的初始化

---

3.3 其他操作