循环单链表的基本操作

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