数据结构-双链表详解
数据结构-双链表详解
定义结点结构
/** * 定义结点类型结构体 */
typedef struct DNode {
int data; // 数据域
struct DNode* prior; // 指向前驱结点
struct DNode* next; // 指向后继结点
}DNode, * DLinkList;
尾插法建立双链表
/** * 尾插法建立双链表 * @param L 引用类型，双链表L * @param n 结点个数 */
void Create_DLinkList(DLinkList& L, int n) {
L = (DLinkList)malloc(sizeof(DNode));
if (L)
{
L->prior = NULL;
L->next = NULL;
}
DNode* r, * s;
r = L;
for (int i = 0; i < n; ++i) {
s = (DNode*)malloc(sizeof(DNode));
if (s)
{
scanf_s("%d", &s->data);
if (r) // 与建立单链表类似，但要多加一个指向前驱的指针
{
r->next = s;
s->prior = r;
r = s;
}
}
}
if (r)
{
r->next = NULL;
}
}
插入一个结点到双链表中
/** * 插入一个结点到双链表中 * @param L 引用类型，双链表L * @param location 插入结点的位置 * @param elem 插入的元素值 */
int InsertElem_DLinkList(DLinkList& L, int location, int elem) {
DNode* p = L, * s;
int i = 1;
while (p->next != NULL && i < location) {
// 让指针p走到插入位置
p = p->next;
++i;
}
s = (DNode*)malloc(sizeof(DNode));
if (s)
{
s->data = elem;
if (location >= i + 1) {
return 0;
}
else if (p->next == NULL) {
// 插入位置在结尾要单独处理
s->next = p->next;
s->prior = p;
p->next = s;
return 1;
}
else {
// 注意插入顺序,1、2步必须在第3步前，要小心指针会丢失
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
return 1;
}
}
}
插入操作的代码片段如下：（顺序不唯一，但1、2步必须在第3步前，要小心指针会丢失）
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
从双链表中删除一个结点
/** * 从双链表中删除一个结点 * @param L 引用类型，双链表L * @param location 删除结点的位置 * @param elem 返回删除结点的值 */
int DeleteElem_DLinkList(DLinkList& L, int location, int& elem) {
DNode* p = L;
int i = 0;
while (p->next != NULL && i < location) {
p = p->next;
++i;
}
if (location >= i + 1) {
return 0;
}
else if (p->next == NULL) {
// 删除尾部元素单独处理
p->prior->next = p->next;
}
else {
// 要改前驱和后继两个指针
p->prior->next = p->next;
p->next->prior = p->prior;
}
elem = p->data;
free(p);
return 1;
}
按顺序打印双链表
/** * 按顺序打印双链表 * @param L 引用类型，双链表L */
void Print_DLinkList(DLinkList L) {
DNode* p = L;
while (p->next != NULL) {
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
按逆序打印双链表
/** * 按逆序打印双链表 * @param L 引用类型，双链表L */
void ReversePrint_DLinkList(DLinkList L) {
DNode* p = L;
while (p->next != NULL) {
p = p->next;
}
while (p != L) {
printf("%d ", p->data);
p = p->prior;
}
printf("\n");
}
双链表的好处之一就是可以通过前驱指针来进行逆序操作
完整测试代码
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
/** * 定义结点类型结构体 */
typedef struct DNode {
int data; // 数据域
struct DNode* prior; // 指向前驱结点
struct DNode* next; // 指向后继结点
}DNode, * DLinkList;
/** * 尾插法建立双链表 * @param L 引用类型，双链表L * @param n 结点个数 */
void Create_DLinkList(DLinkList& L, int n) {
L = (DLinkList)malloc(sizeof(DNode));
if (L)
{
L->prior = NULL;
L->next = NULL;
}
DNode* r, * s;
r = L;
for (int i = 0; i < n; ++i) {
s = (DNode*)malloc(sizeof(DNode));
if (s)
{
scanf_s("%d", &s->data);
if (r) // 与建立单链表类似，但要多加一个指向前驱的指针
{
r->next = s;
s->prior = r;
r = s;
}
}
}
if (r)
{
r->next = NULL;
}
}
/** * 插入一个结点到双链表中 * @param L 引用类型，双链表L * @param location 插入结点的位置 * @param elem 插入的元素值 */
int InsertElem_DLinkList(DLinkList& L, int location, int elem) {
DNode* p = L, * s;
int i = 1;
while (p->next != NULL && i < location) {
// 让指针p走到插入位置
p = p->next;
++i;
}
s = (DNode*)malloc(sizeof(DNode));
if (s)
{
s->data = elem;
if (location >= i + 1) {
return 0;
}
else if (p->next == NULL) {
// 插入位置在结尾要单独处理
s->next = p->next;
s->prior = p;
p->next = s;
return 1;
}
else {
// 注意插入顺序，1、2步必须在3、4步前面，指针会丢失
s->next = p->next;
p->next->prior = s;
p->next = s;
s->prior = p;
return 1;
}
}
}
/** * 从双链表中删除一个结点 * @param L 引用类型，双链表L * @param location 删除结点的位置 * @param elem 返回删除结点的值 */
int DeleteElem_DLinkList(DLinkList& L, int location, int& elem) {
DNode* p = L;
int i = 0;
while (p->next != NULL && i < location) {
p = p->next;
++i;
}
if (location >= i + 1) {
return 0;
}
else if (p->next == NULL) {
// 删除尾部元素单独处理
p->prior->next = p->next;
}
else {
// 要改前驱和后继两个指针
p->prior->next = p->next;
p->next->prior = p->prior;
}
elem = p->data;
free(p);
return 1;
}
/** * 按顺序打印双链表 * @param L 引用类型，双链表L */
void Print_DLinkList(DLinkList L) {
DNode* p = L;
while (p->next != NULL) {
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
/** * 按逆序打印双链表 * @param L 引用类型，双链表L */
void ReversePrint_DLinkList(DLinkList L) {
DNode* p = L;
while (p->next != NULL) {
p = p->next;
}
while (p != L) {
printf("%d ", p->data);
p = p->prior;
}
printf("\n");
}
int main() {
DLinkList L;
int n;
scanf_s("%d", &n);
Create_DLinkList(L, n);
Print_DLinkList(L);
ReversePrint_DLinkList(L);
int location, elem;
scanf_s("%d %d", &location, &elem);
if (InsertElem_DLinkList(L, location, elem)) {
Print_DLinkList(L);
ReversePrint_DLinkList(L);
}
else {
printf("插入失败\n");
}
scanf_s("%d", &location);
if (DeleteElem_DLinkList(L, location, elem)) {
Print_DLinkList(L);
ReversePrint_DLinkList(L);
printf("删除的元素为%d\n", elem);
}
else {
printf("删除失败：\n");
}
return 0;
}
创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！
投递中国移动等公司8个岗位 >
