【数据结构】 双链表的基本操作 （C语言版）
发布时间：2024年01月21日
目录
一、双链表
1、双链表的定义：
双链表也叫双向链表，是一种链表数据结构。它的每个数据结点包含两个指针，一个指向前一个结点，另一个指向后一个结点。这意味着从双向链表的任何节点都可以方便地访问其前驱或后继节点。通常，我们构造双向循环链表，它的特点是尾节点的指针域指向头结点，整个链表形成一个环。
?
2、双链表表的优缺点：?
双链表的优点：
- 可以方便地访问前驱和后继节点，既可以向前也可以向后遍历链表。
- 在某些情况下，双链表比单链表更节省空间，因为它不需要额外的指针来存储前驱和后继节点的信息。
双链表的缺点：
- 插入和删除节点相对复杂，需要更多的时间来调整指针。
- 双链表需要更多的存储空间，因为每个节点都需要额外的指针来存储前驱和后继节点的信息。
二、双链表的基本操作算法（C语言）
?1、宏定义
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;?2、创建结构体
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;3、双链表的初始化?
//双链表初始化
Status DInitList(DuLinkList &head) {
head = new DuLNode;
head->prior = NULL;
head->next = NULL;
return OK;
}4、双链表表插入
//插入
Status DListInsert(DuLinkList &head, int i, ElemType e) {
DuLinkList p = head;
int j = 0;
while (p && (j < i - 1)) {
p = p->next;
++j;
}
if (!p || j > i - 1) {
return ERROR;
}
DuLNode *s = new DuLNode;
s->data = e;
s->next = p->next;
if(p->next != NULL){
p->next->prior = s;
}
p->next = s;
s->prior = p;
return OK;
}5、双链表的查找
//查找
int DLocateLinkListElem(DuLinkList head, ElemType e) {
DuLinkList p = head->next;
int j = 1;
while (p && (p->data != e)) {
p = p->next;
j++;
}
if (p == NULL) {
return 0;
}
return j;
}6、双链表的取值
//取值
Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
DuLinkList p = head->next;
int j = 1;
while (p && j < i) {
p = p->next;
++j;
}
if (p == NULL) {
return ERROR;
}
e = p->data;
return OK;
}7、求双链表长度
//求双链表长度
Status DGetLinkListLength(DuLinkList head) {
DuLinkList p = head->next;
int length = 0;
while (p!=NULL) { //单链表不为空表时
length++;
p = p->next;
}
return length;
}8、双链表的删除
//删除
Status DListDelete(DuLinkList &head, int i, ElemType &e) {
DuLinkList p = head;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p) {
return ERROR;
}
DuLinkList q = p->next;
e = q->data;
p->next = q->next;
if(q->next != NULL){
q->next->prior=p;
}
delete q;
return OK;
}9、双链表的清空
//清空
Status DClearLinkList(DuLinkList &head) {
DuLinkList p = head->next;
DuLinkList q;
while (p) {
q = p;
p = p->next;
delete q;
}
head->next = NULL;
return OK;
}
10、双链表的销毁
//销毁
Status DestoryDLinkList(DuLinkList &head) {
DuLinkList p;
while (head) {
p = head;
head = head->next;
delete p;
}
return OK;
}11、输出链表元素
//输出链表元素
void DprintLinkList(DuLinkList head) {
DuLinkList p = head->next;
while (p) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
三、双链表的全部代码（C语言）
#include <stdio.h>
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;
//双链表初始化
Status DInitList(DuLinkList &head) {
head = new DuLNode;
head->prior = NULL;
head->next = NULL;
return OK;
}
//功能菜单
int choice() {
printf("==================================\n");
printf(" 双链表操作功能菜单 \n");
printf("1、插入元素 2、查询表长 3、按位查找\n");
printf("4、按值查找 5、删除元素 6、销毁链表\n");
printf("7、清空链表 8、批量插入 9、链表元素\n");
printf("==================================\n");
return 0;
}
//插入
Status DListInsert(DuLinkList &head, int i, ElemType e) {
DuLinkList p = head;
int j = 0;
while (p && (j < i - 1)) {
p = p->next;
++j;
}
if (!p || j > i - 1) {
return ERROR;
}
DuLNode *s = new DuLNode;
s->data = e;
s->next = p->next;
if(p->next != NULL){
p->next->prior = s;
}
p->next = s;
s->prior = p;
return OK;
}
//查找
int DLocateLinkListElem(DuLinkList head, ElemType e) {
DuLinkList p = head->next;
int j = 1;
while (p && (p->data != e)) {
p = p->next;
j++;
}
if (p == NULL) {
return 0;
}
return j;
}
//取值
Status DGetLinkList(DuLinkList head, int i, ElemType &e) {
DuLinkList p = head->next;
int j = 1;
while (p && j < i) {
p = p->next;
++j;
}
if (p == NULL) {
return ERROR;
}
e = p->data;
return OK;
}
//求双链表长度
Status DGetLinkListLength(DuLinkList head) {
DuLinkList p = head->next;
int length = 0;
while (p!=NULL) { //单链表不为空表时
length++;
p = p->next;
}
return length;
}
//删除
Status DListDelete(DuLinkList &head, int i, ElemType &e) {
DuLinkList p = head;
int j = 0;
while (p && j < i - 1) {
p = p->next;
j++;
}
if (!p) {
return ERROR;
}
DuLinkList q = p->next;
e = q->data;
p->next = q->next;
if(q->next != NULL){
q->next->prior=p;
}
delete q;
return OK;
}
//清空
Status DClearLinkList(DuLinkList &head) {
DuLinkList p = head->next;
DuLinkList q;
while (p) {
q = p;
p = p->next;
delete q;
}
head->next = NULL;
return OK;
}
//销毁
Status DestoryDLinkList(DuLinkList &head) {
DuLinkList p;
while (head) {
p = head;
head = head->next;
delete p;
}
return OK;
}
//输出链表元素
void DprintLinkList(DuLinkList head) {
DuLinkList p = head->next;
while (p) {
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
int main() {
DuLinkList Dlist;
printf("双链表正在初始化....\n");
int InitStatus = DInitList(Dlist);
if (InitStatus == OK) {
printf("双链表初始化成功！\n");
} else {
printf("双链表初始化失败！\n");
}
choice();
while (1) {
int flag;
printf("请输入所需的功能编号：\n");
scanf("%d", &flag);
switch (flag) {//通过开关进行功能选择
case 1: {//插入元素
//ListInsert_Dul(Dlist,1,'a');
int insertIndex;
ElemType inserElem;
printf("请输入插入元素位置及插入元素(请在英文状态下输入例如:1,a): \n");
scanf("%d,%c", &insertIndex, &inserElem);
Status InsertS = DListInsert(Dlist, insertIndex, inserElem);
if (InsertS == OK) {
printf("向双链表%d个位置,插入元素为%c成功！\n\n", insertIndex, inserElem);
} else {
printf("向双链表插入元素失败！\n\n");
}
}
break;
case 2: {//求单链表的长度
int length = DGetLinkListLength(Dlist);
printf("循环双链表的长度为:%d。 \n\n", length);
}
break;
case 3: {//取值
Status GetIndex;
printf("请输入需要查询的元素的位置：\n");
scanf("%d", &GetIndex);
ElemType GetElem;
int GetStatus = DGetLinkList(Dlist, GetIndex, GetElem);
if (GetStatus == OK) {
printf("从单链表中获取第%d位置元素成功，所获取到的元素为：%c。\n\n", GetIndex, GetElem);
} else {
printf("从单链表中获取第%d位置元素失败！\n\n", GetIndex);
}
}
break;
case 4: {//查找
ElemType LocateElem;
printf("请输入想要查找元素：\n");
getchar(); //用于接收回车
scanf("%c", &LocateElem);
Status LocateIndex = DLocateLinkListElem(Dlist, LocateElem);
if (LocateIndex > 0) {
printf("从双链表中查找元素%c成功，它在循环链表中的位置为第%d个！\n\n", LocateElem, LocateIndex);
} else {
printf("从双链表中查找元素%c失败！\n\n", LocateElem);
}
}
break;
case 5: {//删除
//ListDelete_DuL(list,1);
Status DeleteIndex;
printf("请输入想要删除元素的位置：\n");
scanf("%d", &DeleteIndex);
ElemType DeleteElem;
ElemType DeleteStatus = DListDelete(Dlist, DeleteIndex, DeleteElem);
if (DeleteStatus == OK) {
printf("删除双链表第%d个位置的元素成功，删除的元素为：%c。\n\n", DeleteIndex, DeleteElem);
} else {
printf("删除双链表第%d个位置的元素失败！\n\n", DeleteIndex);
}
}
break;
case 6: {//销毁
Status DestoryStatus = DestoryDLinkList(Dlist);
if (DestoryStatus == OK) {
printf("双环链表销毁成功！\n\n");
} else {
printf("双链表销毁失败！\n\n");
}
}
break;
case 7: {//清空
Status ClearStatus = DClearLinkList(Dlist);
if (ClearStatus == OK) {
printf("双链表清空成功！\n\n");
} else {
printf("双链表清空失败！\n\n");
}
}
break;
case 8: {//批量插入
int on;
printf("请输入想要插入的元素个数：\n");
scanf("%d", &on);
ElemType array[on];
for (int i = 1; i <= on; i++) {
getchar();
printf("向双链表第%d个位置插入元素为:", (i));
scanf("%c", &array[i]);
}
for (int i = 1; i <= on; i++) {
Status InsertStatus = DListInsert(Dlist, i, array[i]);
if (InsertStatus == OK) {
printf("向双链表第%d个位置插入元素%c成功！\n", i, array[i]);
} else {
printf("向双链表第%d个位置插入元素%c失败！\n", i, array[i]);
}
}
}
break;
case 9: {//输出链表元素
DprintLinkList(Dlist);
}
break;
default: {
printf("输入错误，无此功能，请检查输入:\n\n");
}
}
}
return 1;
}
四、运行结果
文章来源:https://blog.csdn.net/weixin_56814370/article/details/135732357
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！