数据结构双向链表的基本操作，包括创立，删除，添加和遍历等

红太狼 2022-07-15 05:22 109阅读 0赞

最近在写双向链表，看了好长时间也没有成功，就在网上查了一个，感觉还不错，就转载了看看，仔细研究研究

\#include "stdafx.h"

\#include<stdio.h>  
\#include<stdlib.h>  
\#define TRUE 1  
\#define FALSE 0  
\#define OK 1  
\#define ERROR 0  
  
  
typedef int status;  
typedef int ElemType;  
  
  
typedef struct Node \{  
ElemType data;  
struct Node \*prior, \*next;  
\}Lnode, \*LinkList;  
  
  
typedef struct \{  
LinkList head, tail;  
int len;  
\}DuLinkList;  
  
  
void Build(DuLinkList &L)  
\{  
int n, x;  
LinkList p, q;  
L.head = (LinkList)malloc(sizeof(Lnode));  
L.tail = (LinkList)malloc(sizeof(Lnode));  
L.head->next = L.tail;  
L.tail->prior = L.head;  
p = L.head;  
printf("请输入n和n个数据元素\\n");  
scanf\_s("%d", &n);  
L.len = n;  
while (n--)  
\{  
q = (LinkList)malloc(sizeof(Lnode));  
scanf\_s("%d", &x);  
q->data = x;  
q->next = L.tail;  
L.tail->prior = q;  
q->prior = p;  
p->next = q;  
p = q;  
\}  
\}  
  
  
void Print1(DuLinkList &L)//正向遍历输出  
\{  
LinkList p;  
p = L.head->next;  
while (p != L.tail)  
\{  
printf("%d ", p->data);  
p = p->next;  
\}  
printf("\\n长度为:%d\\n", L.len);  
\}  
  
  
void Print2(DuLinkList &L)//逆向遍历输出  
\{  
LinkList p;  
p = L.tail->prior;  
while (p != L.head)  
\{  
printf("%d ", p->data);  
p = p->prior;  
\}  
printf("\\n长度为:%d\\n", L.len);  
\}  
  
  
void Tips()  
\{  
printf("按数字键选择相应操作\\n");  
printf("1、正向遍历输出\\n");  
printf("2、逆向遍历输出\\n");  
printf("3、删除值为X的元素\\n");  
printf("4、插入值为X的元素，使仍然有序\\n");  
printf("5、判断双向链表中元素是否对称若对称\\n");  
printf("6、把所有奇数排列在偶数之前\\n");  
printf("0、退出\\n");  
\}  
  
  
status Delete(DuLinkList &L, int x)  
\{  
LinkList p, q;  
p = L.head;  
while (p->next != L.tail && p->next->data != x)  
p = p->next;  
if (p->next != L.tail)  
\{  
q = p->next;  
p->next = q->next;  
q->next->prior = p;  
free(q);  
L.len--;  
return OK;  
\}  
return ERROR;  
\}  
status Insert(DuLinkList &L, int x)  
\{  
LinkList p, q;  
p = L.head;  
while (p->next != L.tail && p->next->data<x)  
p = p->next;  
q = (LinkList)malloc(sizeof(Lnode));  
q->data = x;  
q->prior = p;  
q->next = p->next;  
p->next->prior = q;  
p->next = q;  
L.len++;  
return OK;  
\}  
status Judge(DuLinkList &L)  
\{  
//p从头结点开始，q从尾结点开始，依次比较p->data和q->data  
int i;  
LinkList p, q;  
p = L.head->next;  
q = L.tail->prior;  
for (i = 0; i<L.len / 2; i++)  
\{  
if (p->data != q->data)  
break;  
p = p->next;  
q = q->prior;  
\}  
if (i == L.len / 2)  
return OK;  
return ERROR;  
\}  
  
  
status PaiLie(DuLinkList &L)  
\{  
//把所有的奇数结点都移到以s为头结点的链表上  
LinkList s, p, q, r;  
p = L.head;  
s = (LinkList)malloc(sizeof(Lnode));  
s->next = NULL;  
r = s;  
while (p->next != L.tail)  
\{  
if (p->next->data & 1)  
\{  
r->next = p->next;  
p->next->prior = r;  
p->next = p->next->next;  
p->next->prior = p;  
r = r->next;  
\}  
else  
p = p->next;  
\}  
//把链表s接到L.head  
r->next = L.head->next;  
L.head->next->prior = r;  
L.head->next = s->next;  
s->next->prior = L.head;  
return OK;  
\}  
  
  
int main()  
\{  
DuLinkList L;  
int op, x, flag;  
Build(L);  
Tips();  
scanf\_s("%d", &op);  
while (op)  
\{  
switch (op)  
\{  
case 1:  
Print1(L);  
break;  
case 2:  
Print2(L);  
break;  
case 3:  
printf("请输入要删除的x\\n");  
scanf\_s("%d", &x);  
flag = Delete(L, x);  
if (flag)  
printf("删除成功!!\\n\\n");  
else  
printf("元素不存在，删除失败!!\\n\\n");  
break;  
case 4:  
printf("请输入要插入的x\\n");  
scanf\_s("%d", &x);  
flag = Insert(L, x);  
if (flag)  
printf("插入成功!!\\n\\n");  
else  
printf("插入失败!!\\n\\n");  
break;  
case 5:  
flag = Judge(L);  
if (flag)  
printf("对称!!!\\n\\n");  
else  
printf("不对称!!!\\n\\n");  
break;  
case 6:  
flag = PaiLie(L);  
if (flag)  
printf("重新排列成功!!!\\n\\n");  
else  
printf("重新排列失败!!!\\n\\n");  
break;  
default:  
printf("输入错误!!!\\n\\n");  
break;  
  
  
\}  
Tips();  
scanf\_s("%d", &op);  
\}  
return 0;  
\}