鏈表 —— 雙向循環

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");}