今天学习的是线性表里面的最后一部分双向链表
栈和队列的相关知识可以查看http://t.csdnimg.cn/R1ls3
链表的相关知识可以查看http://t.csdnimg.cn/NX464
顺序表的相关知识可以查看http://t.csdnimg.cn/5IMAZ
目录
双向链表
结构体
操作函数
1.创建一个空的双向链表
2.向双向链表的指定位置插入数据
3.遍历双向链表
4.删除双向链表指定位置的数据
5.删除双向链表中的指定数据
双向链表的相关操作案例
双向链表
1.逻辑结构：线性结构
2.存储结构：链式存储
3.操作：增、删、改、查
结构体
typedef struct node_t
{
datatype data; // 数据域
struct node_t *next; // 指向下一个节点的指针 next 下一个
struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} link_node_t, *link_list_t;// 将双向链表的头指针和尾指针封装到一个结构体里，有点像学的链式队列
typedef struct doublelinklist
{
link_list_t head; // 指向双向链表的头指针
link_list_t tail; // 指向双向链表的尾指针
int len;
} double_node_t, *double_list_t;
操作函数
1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{double_list_t p = (double_list_t)malloc(sizeof(double_node_t));if (p == NULL){perror("createEmptyDoubleLinkList函数创建结构体出错\n");return NULL;}p->len = 0;p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));if (p->head == NULL){perror("createEmptyDoubleLinkList创建链表节点出错\n");return NULL;}p->head->next = NULL;p->head->prior = NULL;return p;
}2.向双向链表的指定位置插入数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{// 1.容错判断if (post < 0 || post > p->len){perror("insertIntoDoubleLinkList函数出错\n");return -1;}// 2.开辟一个新节点空间存放数据link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));if (pnew == NULL){perror("insertIntoDoubleLinkList函数创建新节点出错\n");return -1;}pnew->data = data;pnew->next = NULL;pnew->prior = NULL;link_list_t temp = NULL;// 3.将结点插入链表// (1).先对插入的位置进行判断if (post == p->len) // 尾插{p->tail->next = pnew;pnew->prior = p->tail;p->tail = pnew; // 移动尾指针}else // 中间插{// (1)将temp移动到被插入的位置if (post < p->len / 2) // 前半段{temp = p->head;for (int i = 0; i <= post; i++){temp = temp->next;}}else // 后半段{temp = p->tail;for (int i = 0; i < p->len - 1 - post; i++){temp = temp->prior;}}// (2)进行插入操作(先连前面，再连后面)temp->prior->next = pnew;pnew->prior = temp->prior;pnew->next = temp;temp->prior = pnew;}// 长度+1p->len++;return 0;
}3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{link_list_t temp = NULL;printf("正向遍历:\n");temp = p->head;while (temp->next != NULL){temp = temp->next;printf("%d ", temp->data);}printf("\n");printf("反向遍历:\n");temp = p->tail;while (temp != p->head){printf("%d ", temp->data);temp = temp->prior;}printf("\n");
}
4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{// 1.容错判断if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p)){perror("deletePostDoubleLinkList函数出错\n");return -1;}// 2.对删除的位置进行判断link_list_t temp = NULL;if (post == p->len - 1) // 尾删{// 向前移动尾指针p->tail = p->tail->prior;// 释放被删除的节点free(p->tail->next);p->tail->next = NULL;}else // 中间删{// (1)将temp移动到要删除的位置if (post < p->len / 2) // 前半段{temp = p->head;for (int i = 0; i <= post; i++){temp = temp->next;}}else // 后半段{temp = p->tail;for (int i = 0; i < p->len - 1 - post; i++){temp = temp->prior;}}// (2)进行删除temp->prior->next = temp->next;temp->next->prior = temp->prior;free(temp);temp = NULL;}// 长度-1p->len--;return 0;
}5.删除双向链表中的指定数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{if (isEmptyDoubleLinkList(p)){perror("deleteDataDoubleLinkList函数出错\n");return -1;}link_list_t q = p->head->next;while (q != NULL){if (q->data == data) // 删除{if (q == p->tail) // 尾删{p->tail = p->tail->prior;free(p->tail->next);p->tail->next = NULL;q = NULL;}else // 中间删{q->prior->next = q->next;q->next->prior = q->prior;link_list_t pdel = q;q = q->next;free(pdel);pdel = NULL;}p->len--;}else // 不相等{q = q->next;}}return 0;
}
双向链表的相关操作案例
头文件doublelinklist.h：
#ifndef _DOUBLELINKLIST_H_
#define _DOUBLELINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node_t
{datatype data; // 数据域struct node_t *next; // 指向下一个节点的指针 next 下一个struct node_t *prior; // 指向前一个节点的指针 prior 前一个
} link_node_t, *link_list_t;// 将双向链表的头指针和尾指针封装到一个结构体里
// 思想上有点像学的链式队列
typedef struct doublelinklist
{link_list_t head; // 指向双向链表的头指针link_list_t tail; // 指向双向链表的尾指针int len;
} double_node_t, *double_list_t;// 1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList();
// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data);
// 3.遍历双向链表
void showDoubleLinkList(double_list_t p);
// 4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post);
// 5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p);
// 6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p);
// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p, datatype data);
// 8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p, int post, datatype data);
// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data);
#endif双向链表函数doublelinklist.c：
#include "doublelinklist.h"
// 1.创建一个空的双向链表
double_list_t createEmptyDoubleLinkList()
{double_list_t p = (double_list_t)malloc(sizeof(double_node_t));if (p == NULL){perror("createEmptyDoubleLinkList函数创建结构体出错\n");return NULL;}p->len = 0;p->head = p->tail = (link_list_t)malloc(sizeof(link_node_t));if (p->head == NULL){perror("createEmptyDoubleLinkList创建链表节点出错\n");return NULL;}p->head->next = NULL;p->head->prior = NULL;return p;
}// 2.向双向链表的指定位置插入数据 post位置， data数据
int insertIntoDoubleLinkList(double_list_t p, int post, datatype data)
{// 1.容错判断if (post < 0 || post > p->len){perror("insertIntoDoubleLinkList函数出错\n");return -1;}// 2.开辟一个新节点空间存放数据link_list_t pnew = (link_list_t)malloc(sizeof(link_node_t));if (pnew == NULL){perror("insertIntoDoubleLinkList函数创建新节点出错\n");return -1;}pnew->data = data;pnew->next = NULL;pnew->prior = NULL;link_list_t temp = NULL;// 3.将结点插入链表// (1).先对插入的位置进行判断if (post == p->len) // 尾插{p->tail->next = pnew;pnew->prior = p->tail;p->tail = pnew; // 移动尾指针}else // 中间插{// (1)将temp移动到被插入的位置if (post < p->len / 2) // 前半段{temp = p->head;for (int i = 0; i <= post; i++){temp = temp->next;}}else // 后半段{temp = p->tail;for (int i = 0; i < p->len - 1 - post; i++){temp = temp->prior;}}// (2)进行插入操作(先连前面，再连后面)temp->prior->next = pnew;pnew->prior = temp->prior;pnew->next = temp;temp->prior = pnew;}// 长度+1p->len++;return 0;
}// 3.遍历双向链表
void showDoubleLinkList(double_list_t p)
{link_list_t temp = NULL;printf("正向遍历:\n");temp = p->head;while (temp->next != NULL){temp = temp->next;printf("%d ", temp->data);}printf("\n");printf("反向遍历:\n");temp = p->tail;while (temp != p->head){printf("%d ", temp->data);temp = temp->prior;}printf("\n");
}// 4.删除双向链表指定位置的数据
int deletePostDoubleLinkList(double_list_t p, int post)
{// 1.容错判断if (post < 0 || post >= p->len || isEmptyDoubleLinkList(p)){perror("deletePostDoubleLinkList函数出错\n");return -1;}// 2.对删除的位置进行判断link_list_t temp = NULL;if (post == p->len - 1) // 尾删{// 向前移动尾指针p->tail = p->tail->prior;// 释放被删除的节点free(p->tail->next);p->tail->next = NULL;}else // 中间删{// (1)将temp移动到要删除的位置if (post < p->len / 2) // 前半段{temp = p->head;for (int i = 0; i <= post; i++){temp = temp->next;}}else // 后半段{temp = p->tail;for (int i = 0; i < p->len - 1 - post; i++){temp = temp->prior;}}// (2)进行插入删除temp->prior->next = temp->next;temp->next->prior = temp->prior;free(temp);temp = NULL;}// 长度-1p->len--;return 0;
}
// 5.判断双向链表是否为空
int isEmptyDoubleLinkList(double_list_t p)
{return p->len == 0;
}
// 6.求双向链表的长度
int lengthDoubleLinkList(double_list_t p)
{return p->len;
}// 7.查找指定数据出现的位置 data被查找的数据
int searchPostDoubleLinkList(double_list_t p, datatype data)
{link_list_t q = p->head;int post = 0;while (q->next != NULL){q = q->next;if (q->data == data){return post;}post++;}return -1;
}// 8.修改指定位置的数据,post修改的位置 data被修改的数据
int changeDataDoubleLinkList(double_list_t p, int post, datatype data)
{// 1.容错判断if (post < 0 || post >= p->len){perror("changeDataDoubleLinkList函数出错\n");return -1;}// 2.移动指针link_list_t temp = NULL;if (post < p->len / 2) // 前半段{temp = p->head;for (int i = 0; i <= post; i++){temp = temp->next;}}else // 后半段{temp = p->tail;for (int i = 0; i < p->len - 1 - post; i++){temp = temp->prior;}}// 3.修改数据temp->data = data;return 0;
}// 9.删除双向链表中的指定数据 data代表删除所有出现的data数据
int deleteDataDoubleLinkList(double_list_t p, datatype data)
{if (isEmptyDoubleLinkList(p)){perror("deleteDataDoubleLinkList函数出错\n");return -1;}link_list_t q = p->head->next;while (q != NULL){if (q->data == data) // 删除{if (q == p->tail) // 尾删{p->tail = p->tail->prior;free(p->tail->next);p->tail->next = NULL;q = NULL;}else // 中间删{q->prior->next = q->next;q->next->prior = q->prior;link_list_t pdel = q;q = q->next;free(pdel);pdel = NULL;}p->len--;}else // 不相等{q = q->next;}}return 0;
}
主函数main.c：
#include "doublelinklist.h"int main(int argc, char const *argv[])
{int post;int data;double_list_t p = createEmptyDoubleLinkList();insertIntoDoubleLinkList(p, 0, 1);insertIntoDoubleLinkList(p, 1, 2);insertIntoDoubleLinkList(p, 2, 3);insertIntoDoubleLinkList(p, 3, 4);printf("双向链表为:\n");showDoubleLinkList(p);printf("双向链表的长度为：\n");printf("%d\n", lengthDoubleLinkList(p));printf("请输入你要插入的数据的位置和数据:\n");scanf(" %d %d", &post, &data);insertIntoDoubleLinkList(p, post, data);printf("插入数据以后的双向链表为:\n");showDoubleLinkList(p);printf("请输入你要删除的数据的位置:\n");scanf(" %d", &post);deletePostDoubleLinkList(p, post);printf("删除以后的双向链表为:\n");showDoubleLinkList(p);printf("双向链表的长度为：\n");printf("%d\n", lengthDoubleLinkList(p));printf("请输入你要查询的数据：\n");scanf(" %d", &data);printf("该数据的位置为：%d\n", searchPostDoubleLinkList(p, data));printf("请输入你要修改的数据的位置和数据:\n");scanf(" %d %d", &post, &data);changeDataDoubleLinkList(p, post, data);printf("修改数据以后的双向链表为:\n");showDoubleLinkList(p);printf("请输入你要删除的数据:\n");scanf(" %d", &data);deleteDataDoubleLinkList(p, data);printf("删除数据以后的双向链表为:\n");showDoubleLinkList(p);printf("双向链表的长度为：\n");printf("%d\n", lengthDoubleLinkList(p));return 0;
}
