雙向鏈表

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