链表 —— 双向循环

2019-11-11 05:10:32

字体：大中小

来源：转载

供稿：网友

代码示例

/* 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 DCNode{ Elemtype data; struct DCNode *PRior; struct DCNode *next;} DCNode;typedef struct DCNode* DCLinkList;/* 功能：初始化一个空的双向循环链表头，并且创建一个双向循环链表*/DCLinkList DCLinkList_Init_Create(){ // 初始化 DCLinkList head, p, s; head = (DCLinkList)malloc(sizeof(DCLinkList)); head->next = head; head->prior = head; // 创建 p = head; int flag = 1; Elemtype c; while (flag) { cin >> c; if (c != -99999) { s = (DCLinkList)malloc(sizeof(DCLinkList)); s->data = c; s->next = head; s->prior = p; p->next = s; head->prior = s; p = s; } else { flag = 0; } } return head;}/* 功能：计算双向循环链表的长度*/int DCLinkList_Length(DCLinkList *head){ DCLinkList p; p = *head; int count = 0; while (p->next != *head) { count++; p = p->next; } return count;}/* 功能：插入*/Status DCLinkList_Insert(DCLinkList *head, int i, Elemtype e){ DCLinkList pre, s; pre = *head; int k = 1; if (pre->next == NULL) { cout << "插入位置错误!" << endl; return ERROR; } if (i > DCLinkList_Length(head)) { cout << "插入位置错误!" << endl; return ERROR; } while (pre->next != *head && k < i) // 找到第 i-1 个位置 { pre = pre->next; k++; } s = (DCLinkList)malloc(sizeof(DCLinkList)); s->data = e; s->prior = pre; s->next = pre->next; pre->next->prior = s; pre->next = s; return OK;}/* 功能：正向打印双向循环链表*/Status DCLinkList_Print(DCLinkList *head){ DCLinkList p; p = (*head)->next; if (p == NULL) { cout << "空链表！" << endl; return ERROR; } while (p->next != (*head)->next ) { cout << p->data << " "; p = p->next; } cout << endl; return OK;}/* 功能：反向打印双向循环链表*/Status DCLinkList_Print2(DCLinkList *head){ DCLinkList p; p = (*head)->prior; if (p == NULL) { cout << "空链表！" << endl; return ERROR; } while (p != *head) { cout << p->data << " "; p = p->prior; } cout << endl; return OK;}void main(){ DCLinkList head; cout << "开始输入(这里是尾插法建表，输入-99999结束建表)..........." << endl; head = DCLinkList_Init_Create(); cout << "从头打印链表（利用*next）:" << endl; DCLinkList_Print(&head); cout << "从尾部反向打印链表（利用*prior）:" << endl; DCLinkList_Print2(&head); cout << "链表的长度为:"; cout << DCLinkList_Length(&head) << endl; cout << "开始插入.................................................." << endl; int i, j; cout << "输入插入的位置:" << endl; cin >> i; cout << "输入插入的数字:" << endl; cin >> j; DCLinkList_Insert(&head, i, j); cout << "从头打印链表（利用*next）:" << endl; DCLinkList_Print(&head); cout << "从尾部反向打印链表（利用*prior）:" << endl; DCLinkList_Print2(&head); cout << "链表的长度为:"; cout << DCLinkList_Length(&head) << endl; system("pause");}