双向链表

2019-11-11 05:22:13

字体：大中小

来源：转载

供稿：网友

代码示例

/* function：双向链表的基本操作 created by ： xilong date: 2017.2.6*/#include "iostream"using namespace std;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef double Elemtype;typedef int Status;typedef struct DNode{ Elemtype data; struct DNode *PRior; struct DNode *next;}DNode;typedef struct DNode *DLinkList;/* 功能：初始化一个双向链表头，并且创建一个双向链表*/DLinkList DLinkList_Init(){ DLinkList head; DLinkList p, s; head = (DLinkList)malloc(sizeof(DLinkList)); head->next = head->prior = NULL; p = head; int flag = 1; Elemtype c; while (flag) { cin >> c; if (c != -99999) { s = (DLinkList)malloc(sizeof(DLinkList)); s->data = c; p->next = s; s->prior = p; s->next=NULL; p = s; } else { flag = 0; p->next = NULL; } } return head;}/* 功能：计算链表的长度*/int DLinkList_Length(DLinkList *head){ DLinkList p; p = *head; int count = 0; while (p->next != NULL) { count++; p = p->next; } return count;}/* 功能：插入结点*/Status DLinkList_Insert(DLinkList *head, int i, Elemtype e){ DLinkList pre, s; pre = *head; int k = 1; if (pre->next == NULL) { cout << "插入位置错误!" << endl; return ERROR; } if (i > DLinkList_Length(head)) { cout << "插入位置错误!" << endl; return ERROR; } while (pre->next != NULL && k < i) // 找到第 i-1 个位置 { pre = pre->next; k++; } //cout << pre->data << endl; s = (DLinkList)malloc(sizeof(DLinkList)); s->data = e; s->next = pre->next; s->prior = pre; pre->next->prior = s; pre->next = s; return OK;}/* 功能：从链表的头部开始，正序打印*/Status DLinkList_Print(DLinkList *head){ DLinkList p; p = (*head)->next; if (p == NULL) { cout << "空链表！" << endl; return ERROR; } while (p != NULL) { cout << p->data << " "; p = p->next; } cout << endl; return OK;}/* 功能：从链表的尾开始逆序打印*/Status DLinkList_Print2(DLinkList *head){ DLinkList p; p = (*head)->next; while (p->next!= NULL) { p = p->next; } while (p != *head) { cout << p->data << " "; p = p->prior; } cout << endl; return OK;}void main(){ DLinkList head; cout << "开始输入(这里是尾插法建表，输入-99999结束建表)..........." << endl; head = DLinkList_Init(); cout << "从头打印链表............................................." << endl; DLinkList_Print(&head); cout << "从尾部反向打印链表......................................." << endl; DLinkList_Print2(&head); cout << "链表的长度为..........."; cout << DLinkList_Length(&head) << endl; cout << "***********************************************************************" << endl; cout << "开始插入.................................................." << endl; int i, j; cout << "输入插入的位置:" << endl; cin >> i; cout << "输入插入的数字:" << endl; cin >> j; DLinkList_Insert(&head, i, j); cout << "从头打印链表............................................." << endl; DLinkList_Print(&head); cout << "从尾部反向打印链表......................................." << endl; DLinkList_Print2(&head); cout << "链表的长度为..........."; cout << DLinkList_Length(&head) << endl; system("pause");}