1.循环单链表的初始化
typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; bool InitList(LinkList &L) { L=(LNode*)malloc(sizeof(LNode));//建立一个空表分配一个头结点 if(L==NULL) return false; L->next=L;//头结点next指向头结点 return true; } //判断循环单链表是否为空 bool Empty(LinkList L) { if(L->next==L) return ture; else return false; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L,LNode *p) { if(p->next==L) return true; else return false; } L->next=L;
2.循环双链表
typedef int ElemType; typedef struct DNode{ ElemType data; struct DNode *prior,*next; } bool InitDLinkList(DLinkList &L) { L=(DNode*)malloc(sizeof(DNode)); if(L==NULL) return false; L->prior=L; L->next=L; return true; } //判断循环双链表是否为空表 bool Empty(DLinkList L) { if(L->next==L) return true; else return false; } //判断结点p是否为循环双链表的表尾结点 bool isTail(DLinkList L,DNode *p) { if(p->next==L) return true; else return false; } void testLinkList() { DLinkList L; InitDLinkList(L); }
对于普通双链表的插入操作而言
s->next=p->next;
p->next->prior=s;//是有错误的
s->prior=p;
p->next=s;
但是对于循环双链表而言是正确的
对于普通链表的删除操作而言
p->next=q->next;
q->next->prior=p;//要删除的结点q是最后一个结点，这里就会存在问题
free(q);
但是对循环双链表而言是正确的
3. 静态链表
单链表和静态链表的区别
1.单链表的指针是指明了具体的内存地址，静态链表的游标指的是下一个元素的数组下标，例如0号结点，他的游标是2，那么第一个元素就是下标为2的元素，即1
2.单链表的表尾元素是指向NULL的，而静态链表中最后一个结点的游标可以设为-1
3.如图所示，如果每个数据元素4B，每个游标4B(每个结点是8B)，e1的地址就是（0号结点的地址）+8*2（要寻找的结点的数组下标）
#define MaxSize 10 typedef int ElemType; struct Node{ ElemType data; int next; }; void testLinkList(){ struct Node a[MaxSize]; //a是一个Node型数组 } //也可以写为 typedef struct{ ElemType data; int next; }SLinkList[MaxSize]; void testLinkList(){ SLinkList a;//a是一个数组，这个数组有10个元素 //这里a是一个静态链表 }
测试代码
#include<stdio.h> #include<stdlib.h> #define MaxSize 10 struct Node{ int data; int next; }; typedef struct{ int data; int next; }SLinkList[MaxSize]; int main() { struct Node x; printf("sizeX=%d\n",sizeof(x)); struct Node a[MaxSize]; printf("sizeA=%d\n",sizeof(a)); SLinkList b; printf("sizeB=%d\n",sizeof(b)); return 0; }
结果
可以看到
struct Node a[MaxSize]等价于LinkList a
(1)静态链表的初始化
对于单链表而言，初始化就是将结点指向NULL
所以对于静态链表的初始化就是将头结点指向-1
(2)静态链表的插入
①找到一个空的结点，存入数据元素
②从头结点出发找到位序为i-1的结点
③修改新节点的next
④修改i-1的结点的next
举个例子
#include <stdio.h> #define MaxSize 100 typedef struct { int data; int next; } SLinkList[MaxSize]; // 初始化静态链表 void InitList(SLinkList list) { for (int i = 0; i < MaxSize; i++) { list[i].next = -1; // 初始化指针域为-1，表示空节点 } } // 插入元素到静态链表的末尾 void Insert(SLinkList list, int data) { int index = 0; while (list[index].next != -1) { index = list[index].next; // 找到最后一个节点 } // 创建新节点 list[index].next = index + 1; // 设置最后一个节点的指针指向新节点 list[index + 1].data = data; // 设置新节点的数据域 list[index + 1].next = -1; // 新节点的指针域设置为-1 } // 打印静态链表 void PrintList(SLinkList list) { int index = list[0].next; while (index != -1) { printf("%d ", list[index].data); index = list[index].next; } printf("\n"); } int main() { SLinkList list; InitList(list); // 在静态链表中插入元素 Insert(list, 10); Insert(list, 20); Insert(list, 30); // 打印静态链表 PrintList(list); return 0; }
静态链表的优点
增删操作不需要大量的移动元素
静态链表的缺点
不能随机存取，只能从头结点开始一次往后查找
容量固定不变
