循环单链表的基本操作

代码示例

/* function：循环单链表的基本操作 created by ： xilong date: 2017.2.4 */ #include "iostream" using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef 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"); }

程序截图

---

说明：

　　程序中不管是插入，删除和查找函数，都做了判断输入的位置是否合法，比如查找第0号元素，会返回查找位置错误，或者是查找的位置大于链表长度，也会返回查找位置错误，删除和插入做了同样的处理，判断输入的位置是否合法。