1. 单向循环链表
对于单链表,每个结点只存储了向后的指针,这样当中某一结点就无法找到它的前驱结点。
将单链表中终端结点的指针由空指针改为指向头结点,就使整个单链表形成一个环, 这种头尾相接的单链表称为单循环链表,简称循环链表。循环链表解决了一个很麻烦的问题:如何从当中一个结点出发,访问到链表的全部结点。
循环链表和单链表的主要差异就是在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。
1.1 单向循环链表的创建
单向循环链表的创建分为两种情况:
- 链表第一次创建: 创建一个新的结点 新结点的next指向自身(L)->next = (L);
- 链表已经创建,直接插入数据: 找到链表的尾结点,将尾结点的next指向新结点 ,新结点的next指向(*L)
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定,这里假设为int */
// 定义结点
typedef struct Node {
ElemType data;
struct Node *next;
} Node;
typedef struct Node * LinkList;
// 单向循环链表初始化
Status CreateList (LinkList *L) {
int item;
LinkList temp = NULL;
LinkList r = NULL; // 记录最后一个节点
printf("请输入新的结点, 当输入0时结束!\n");
while (1) {
scanf("%d",&item);
if (*L == NULL) {
// 如果输入的链表是空。则创建一个新的节点,使其next指针指向自己 (*head)->next=*head;
*L = (LinkList)malloc(sizeof(Node));
if(!*L) return ERROR;
(*L)->data = item;
(*L)->next = *L;
r = *L;
} else {
// 输入的链表不是空的,寻找链表的尾节点,使尾节点的next=新节点。新节点的next指向头节点(插入操作)
temp = (LinkList)malloc(sizeof(Node));
if (!temp) return ERROR;
temp->data = item; // 创建新的节点
temp->next = *L;
r->next = temp;
r = temp;
}
}
return OK;
}
1.2 单向循环链表的遍历
遍历循环链表,循环链表的遍历最好用do while语句,因为头节点就有值
// 遍历单向循环链表
void show(LinkList p) {
if (p == NULL) {
printf("打印的链表为空!\n");
return;
} else {
LinkList temp;
temp = p;
do {
printf("%5d",temp->data);
temp = temp->next;
} while (temp != p);
}
}
1.3 单向循环链表的插入
- 如果插入的位置为首元结点,所以需要特殊处理
- 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
- 找到链表最后的结点指向尾结点,
- 让新结点的next,指向头结点.
- 尾结点的next 指向新的头结点;
- 让头指针指向temp(临时的新结点)
- 如果插入的位置在其他位置;
- 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
- 先找到插入的位置,如果超过链表长度,则自动插入队尾;
- 通过target找到要插入位置的前一个结点, 让target->next = temp;
- 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置;
单向循环链表插入数据
Status ListInsert(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if (place == 1) {
// 如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
temp = (LinkList)malloc(sizeof(Node)); // 1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
if (!temp == NULL) return ERROR;
temp->data = num;
for (target = *L; target->next != *L; target = target->next); // 2. 找到链表最后的结点_尾结点,
temp->next = *L; // 3. 让新结点的next 指向头结点.
target->next = temp; // 4. 尾结点的next 指向新的头结点;
*L = temp; // 5. 让头指针指向temp(临时的新结点)
} else {
// 如果插入的位置在其他位置;
temp = (LinkList)malloc(sizeof(Node)); // 1.创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
if (!temp == NULL) return ERROR;
temp->data = num;
for (i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++); // 2.先找到插入的位置,如果超过链表长度,则自动插入队尾;
temp->next = target->next; // 3.通过target找到要插入位置的前一个结点, 让target->next = temp;
target->next = temp; // 4.插入结点的前驱指向新结点,新结点的next 指向target原来的next位置;
}
return OK;
}
1.4 单向循环链表的删除
- 如果删除首元节点
-
- 如果删除到只剩下首元结点了,则直接将*L置空;
-
- 链表还有很多数据,但是删除的是首结点;
- 2.1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
- 2.2. 新结点做为头结点,则释放原来的头结点
- 如果删除其他结点
- 找到删除结点前一个结点target
- 使得target->next 指向下一个结点
- 释放需要删除的结点temp
// 单向循环链表删除元素
Status LinkListDelete(LinkList *L,int place) {
LinkList temp, target;
int i;
temp = *L; // temp 指向链表首元结点
if(!temp) return ERROR;
if (place == 1) {
// 如果删除首元节点
// 1.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
// 2.链表还有很多数据,但是删除的是首结点;
// 2.1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
// 2.2. 新结点做为头结点,则释放原来的头结点
for (target = *L; target->next != *L; target = target->next);
temp = *L;
*L = (*L)->next;
target->next = *L;
free(temp);
} else {
// 如果删除其他结点
for (i = 1, target = *L; target->next != *L && i != place -1; target = target->next, i++); //1. 找到删除结点前一个结点target
temp = target->next;
target->next = temp->next; // 2. 使得target->next 指向下一个结点
free(temp); // 3. 释放需要删除的结点temp
}
return OK;
}
1.5 单向循环链表的查询
// 单向循环链表查询值
int findValue(LinkList L,int value) {
int i = 1;
LinkList p;
p = L;
// 1.寻找链表中的结点 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
// 2.当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i;
}
2. 双向链表
单链表访问一个结点的后续结点,而无法直接访问其前驱结点。 为此我们在单链表结点结构中新增加一个前驱指针域,指向前驱结点的数据域,使其不但能够访问其后续结点,也可以方便的访问其前驱结点,这种节点结构叫做双向链表的结点结构
2.1 双向链表的创建
define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType; /* ElemType类型根据实际情况而定,这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * LinkList;
// 创建双向链接
Status createLinkList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node)); // 指向头结点
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->prior = NULL;
temp->next = NULL;
temp->data = i;
//2.为新增的结点建立双向链表关系
p->next = temp; // 2.1. temp 是p的后继
temp->prior = p; // 2.2. temp 的前驱是p
p = p->next; // 3.2. 记录最后的结点的位置,方便下一次插入
}
return OK;
}
2.2 双向链表的插入
双向链表插入元素
Status ListInsert(LinkList *L, int i, ElemType data) {
if (i < 1) return ERROR; // 1.插入的位置不合法 为0或者为负数
LinkList temp = (LinkList)malloc(sizeof(Node)); // 2.新建结点
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
LinkList p = *L; // 3.将p指向头结点!
for(int j = 1; j < i && p;j++) // 4.找到插入位置i直接的结点
p = p->next;
if(!p) return ERROR; // 5.如果插入的位置超过链表本身的长度
if (p->next == NULL) { // 6.判断插入位置是否为链表尾部;
p->next = temp;
temp->prior = p;
} else {
//1️⃣ 将p->next 结点的前驱prior = temp
p->next->prior = temp;
//2️⃣ 将temp->next 指向原来的p->next
temp->next = p->next;
//3️⃣ p->next 更新成新创建的temp
p->next = temp;
//4️⃣ 新创建的temp前驱 = p
temp->prior = p;
}
return OK;
}
2.3 双向链表的删除
删除双向链表指定位置上的结点
Status ListDelete(LinkList *L, int i, ElemType *e) {
int k = 1;
LinkList p = (*L);
//1.判断双向链表是否为空,如果为空则返回ERROR;
if (*L == NULL) {
return ERROR;
}
//2. 将指针p移动到删除元素位置前一个
while (k < i && p != NULL) {
p = p->next;
k++;
}
//3.如果k>i 或者 p == NULL 则返回ERROR
if (k>i || p == NULL) {
return ERROR;
}
//4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
LinkList delTemp = p->next;
*e = delTemp->data;
//5. p->next 等于要删除的结点的下一个结点
p->next = delTemp->next;
//6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
//7.删除delTemp结点
free(delTemp);
return OK;
}
2.4 双向链表的查询
int selectElem(LinkList L,ElemType elem) {
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return i;
}
i++;
p = p->next;
}
return -1;
}
2.5 双向链表的更新节点
// 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem) {
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
3. 双向循环链表
3.1 双向循环链表的创建
// 双向循环链表初始化
Status creatLinkList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node));
if (!*L) return ERROR;
(*L)->next = (*L);
(*L)->prior = (*L);
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
LinkList temp = (LinkList)malloc(sizeof(Node)); // 1.创建1个临时的结点
temp->data = i;
// 2.为新增的结点建立双向链表关系
p->next = temp; // 2.1.temp 是p的后继
temp->prior = p; // 2.2.temp 的前驱是p
temp->next = (*L); // 2.3.emp的后继是*L
p->prior = temp; // 2.4. 的前驱是新建的temp
p = p->next; // 2.5. 要记录最后的结点的位置,方便下一次插入
}
return OK;
}
3.2 双向循环链表的插入
双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType e) {
LinkList p = (*L); // 1.创建指针p,指向双向链表头
int i = 1;
if(!*L) return ERROR; // 2.双向循环链表为空,则返回error
while (i < index && p->next != *L) { // 3.找到插入前一个位置上的结点p
p = p->next;
i++;
}
if (i > index) return ERROR; // 4.如果i>index 则返回error
LinkList temp = (LinkList)malloc(sizeof(Node)); // 5.创建新结点temp
if (temp == NULL) return ERROR; // 6.temp 结点为空,则返回error
temp->data = e; // 7.将生成的新结点temp数据域赋值e.
temp->prior = p; // 8.将结点temp 的前驱结点为p;
temp->next = p->next; // 9.temp的后继结点指向p->next;
p->next = temp; // 10.p的后继结点为新结点temp;
if (*L != temp->next) {
temp->next->prior = temp; // 11.如果temp 结点不是最后一个结点,temp节点的下一个结点的前驱为temp结点
} else {
(*L)->prior = temp;
}
return OK;
}
3.3 双向循环链表的删除
// 双向循环链表删除结点
Status LinkListDelete(LinkList *L,int index,ElemType *e) {
int i = 1;
LinkList temp = (*L)->next;
if (!*L == NULL) return ERROR;
// 如果删除到只剩下首元结点了,则直接将*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
while (i < index) { // 1.找到要删除的结点
temp = temp->next;
i++;
}
*e = temp->data; // 2.给e赋值要删除结点的数据域
temp->prior->next = temp->next; // 3.修改被删除结点的前驱结点的后继指针
temp->next->prior = temp->prior; // 4.修改被删除结点的后继结点的前驱指针
free(temp); // 5.删除结点temp
return OK;
}
4. 顺序存储结构与链式存储结构总结
- 存储分配方式:
- 顺序存储结构用一段连续的存储单元依然存储线性表的数据元素。
- 链式存储结构用一组任意的存储单元存放线性表的玩意。
- 时间性能:
- 查找:顺序存储结构O(1),单链表O(n)。
- 插入与删除:顺序存储结构O(n),链式存储结构为O(1)。
- 空间性能
- 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢。
- 链式存储结构不需要分配存储空间,只要有就可以分配,元素个数也不受限制。
- 结论
- 若线性表需要频繁查找,很少进入插入和删除操作时,宜采用顺序存储结构。
- 若需要频繁插入和删除时,宜采用链式存储结构。
- 当线性表中的元素个数变化较大或者根本不知道有多大时,最好用链式存储结构,这样可以不用考虑存储空间大小问题。
- 而如果事先知道线性表的大致长度,比如一年12个月,这种用顺序存储结构效率会高很多。