循環單鏈表的基本操作

2019-11-14 10:03:24

字體：大中小

來源：轉載

供稿：網友

代碼示例

/* function：循環單鏈表的基本操作 created by ： xilong date: 2017.2.4*/#include "iostream"using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int Elemtype;typedef int Status;typedef struct Node{ Elemtype data; struct Node *next;} Node;typedef struct Node *CLinkList;/* 功能：初始化一個循環空鏈表*/CLinkList CLinkList_Init(){ CLinkList head; head = (CLinkList)malloc(sizeof(CLinkList)); head->next = head; return head;}/* 功能：創建循環鏈表*/void CreateCLinkList(CLinkList *head){ CLinkList p, s; p = *head; int flag = 1; double c; while (flag) { cin >> c; if (c != -99999) { s = (CLinkList)malloc(sizeof(CLinkList)); s->data = c; s->next = *head; // 因為是尾插法，所以申請結點的next指向鏈表頭，構成循環 p->next = s; p = s; } else { flag = 0; } }}/* 功能：循環鏈表中元素的個數*/int CLinkList_Length(CLinkList *head){ CLinkList p; p = *head; int count = 0; while (p->next != *head) { count++; p = p->next; } return count;}/* 功能：在第 i 個位置插入一個元素*/Status CLinkList_Insert(CLinkList *head, int i, Elemtype e){ CLinkList PRe, s; pre = *head; int k = 1; while (pre && k < i) // 找到第 i-1 個元素 { pre = pre->next; k++; } if (!pre || k > i) { cout << "插入位置錯誤！" << endl; return ERROR; } if (i > CLinkList_Length(head) + 1) { cout << "插入位置錯誤！" << endl; return ERROR; } else { s = (CLinkList)malloc(sizeof(CLinkList)); s->data = e; s->next = pre->next; pre->next = s; } return OK;}/* 功能：刪除第 i 個元素，并將其值賦給*e*/Status CLinkList_Delete(CLinkList *head, int i, Elemtype *e){ CLinkList pre, r; pre = *head; int k = 1; while (pre && k < i) // 找到第 i-1 個元素 { pre = pre->next; k++; } if (!pre || k > i) { cout << "刪除位置錯誤！" << endl; return ERROR; } r = pre->next; if (i > CLinkList_Length(head)) { cout << "刪除位置錯誤！" << endl; return ERROR; } else pre->next = pre->next->next; *e = r->data; //free(r); return OK;}/* 功能：查找第 i 個元素，并將查找到的元素放入 *e 中*/Status CLinkList_GetData(CLinkList *head, int i, Elemtype *e){ CLinkList p; p = *head; int k = 0; while (p && k < i) // 找到第 i 個元素 { p = p->next; k++; } if (!p || k > i) { cout << "查找位置錯誤！" << endl; return ERROR; } if (i > CLinkList_Length(head) || i <= 0) { cout << "查找位置錯誤！" << endl; return ERROR; }else { *e = p->data; } return OK;}/* 功能：打印整個鏈表*/Status PrintList(CLinkList *head){ CLinkList p; p = (*head)->next; if (p != NULL) { while (p != *head) { cout << p->data << " "; p = p->next; } } else { cout << "沒有元素！" << endl; return ERROR; } cout << endl; return OK;}void main(){ CLinkList head; Elemtype e; cout << "開始初始化..............................................." << endl; head = CLinkList_Init(); cout << "初始化操作完畢！" << endl; cout << "開始建表(這里是尾插法建表，輸入-99999結束建表)..........." << endl; CreateCLinkList(&head); cout << "建表操作完畢！" << endl; cout << "打印線性表中的所有數據："; PrintList(&head); cout << "打印線性表的長度："; int count = CLinkList_Length(&head); cout << count << endl; cout << "-------------------------------------------------" << endl; cout << "開始插入（在第6個位置插入81）............................" << endl; CLinkList_Insert(&head, 6, 81); cout << "插入操作完畢！" << endl; cout << "打印線性表中的所有數據："; PrintList(&head); cout << "打印線性表的長度："; int count2 = CLinkList_Length(&head); cout << count2 << endl; cout << "-------------------------------------------------" << endl; cout << "開始刪除（這里刪除第2個元素）............................" << endl; CLinkList_Delete(&head, 2, &e); cout << "刪除操作完畢!" << endl; cout << "刪除后打印線性表中的所有數據："; PrintList(&head); cout << "-------------------------------------------------" << endl; cout << "開始查找（這里查找第5個元素）............................." << endl; if (CLinkList_GetData(&head, 5, &e)) { cout << "查找操作完畢!" << endl; cout << "打印查找到的數據："; cout << e << endl; } else { cout << "查找位置錯誤！" << endl; } system("pause");}