单链表的基本操作

2019-11-14 12:19:33

字体：大中小

来源：转载

供稿：网友

代码示例

/* function：单链表的基本操作 created by ： xilong date: 2017.2.3*/#include "iostream"#include <stdlib.h>using namespace std;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status;typedef int ElemType;typedef struct Node // 结构体定义{ ElemType data; struct Node *next;} Node;typedef struct Node *LinkList;/* 功能: 初始化一个带有头结点的单链表*/LinkList InitList(){ LinkList head; head = (LinkList)malloc(sizeof(LinkList)); head->next = NULL; // 头结点指向NULL表示这是一个带有头结点的空单链表 return head;}/* 功能：头插法(随机)建立一个单链表*/void CreateFormHead(LinkList *head, int n){ LinkList s; int i; srand(time_t(1)); // 随机种子 for (i = 0; i < n; i++) { s = (LinkList)malloc(sizeof(LinkList)); // 申请内存 s->data = rand() % 100 + 1; // 随机生成0-100内任意的一个数 s->next = (*head)->next; // 将申请结点的next指向原来头结点的next (*head)->next = s; // 将头结点的next指向申请的结点 }}/* 功能：头插法(自己输入)建立一个单链表*/void CreateFormHead2(LinkList *head){ LinkList s; double c; int flag = 1; while (flag) { cin >> c; if (c != -99999) // 输入-99999结束输入 { s = (LinkList)malloc(sizeof(LinkList)); // 申请内存 s->data = c; // 将输入的数据放到申请结点的data中 s->next = (*head)->next; // 将申请结点的next指向原来头结点的next (*head)->next = s; // 将头结点的next指向申请的结点 } else { flag = 0; } }}/* 功能：利用尾插法创建单链表*/void CreateFormTail(LinkList *head){ LinkList r,s; r = *head; double c; int flag = 1; while (flag) { cin >> c; if (c != -99999) // 输入-99999结束输入 { s = (LinkList)malloc(sizeof(LinkList)); s->data = c; // 将输入的数据放到申请结点的data中 r->next = s; // 第一次时，r原本指向头结点，将头结点的next指向申请的结点 r = s; // 将r指向申请结点，意思是，r和s都指向最后一个结点 } else { flag = 0; r->next = NULL; } }}/* 功能:在带头节点的单链表第 i 个位置插入元素 e*/Status List_Insert(LinkList *head, int i, ElemType e){ LinkList PRe, s; pre = *head; // 将指针 pre 指向链表的头结点 int k=1; while (pre && k < i) // 找到第 i-1 个结点，使指针 pre 指向它 { pre = pre->next; k++; } if (!pre || k > i) { cout << "插入位置不合理！" << endl; return ERROR; } s = (LinkList)malloc(sizeof(Node)); // 为 e 申请一个新的结点并由 s 指向它 s->data = e; // 将带插入结点的值 e 赋给 s 的数据域 s->next = pre->next; // 插入操作 pre->next = s; // 插入操作 return OK;}/* 功能：删除单链表第 i 个位置的元素，并将删除的元素保存到变量 *e 中*/Status List_Delete(LinkList *head, int i, ElemType *e){ LinkList pre, r; pre = *head; int k = 1; // 如果k=0, 则下面程序找到的是第 i 个元素 while (pre->next && k < i) // 找到第 i-1 个结点，使指针 pre 指向它 { pre = pre->next; ++k; } if (!(pre->next) || k > i) { cout << "删除位置不合理！" << endl; return ERROR; } r = pre->next; pre->next = r->next; *e = r->data; free(r); return OK;}/* 功能：查找第 i 个元素，并将该的元素保存到变量 *e 中*/Status Get_Data(LinkList *head, int i, ElemType *e){ LinkList p; p = *head; int k = 0; // 如果k=1, 则下面程序找到的是第 i-1 个元素 while (p && k < i) // 找到第 i 个元素，指针 p 指向第 i 个元素 { p = p->next; k++; } if (!p || k > i) { cout << "查找位置不合理！" << endl; return ERROR; } *e = p->data; // 将第 i 个元素保存到变量 *e 中 return OK;}/* 功能：显示单链表中所有数据*/Status PrintList(LinkList *head){ LinkList p; p = (*head)->next; if (head != NULL) do { cout << p->data << " "; p = p->next; } while (p != NULL); cout << endl; return OK;}void main(){ LinkList head; ElemType e; cout << "开始初始化..............................................." << endl; head = InitList(); // 初始化一个空链表 cout << "初始化操作完毕！" << endl; cout << "开始建表(这里是尾插法建表，输入-99999结束建表)..........." << endl; //CreateFormHead(&head,10); // 头插法，随机插入10个数（可用） //CreateFormHead2(&head); // 头插法，自己创建（可用） CreateFormTail(&head); // 尾插法，自己创建 cout << "建表操作完毕！" << endl; cout << "开始插入................................................." << endl; List_Insert(&head, 5, 21); // 插入21在第5个位置上 cout << "插入操作完毕！" << endl; cout << "打印线性表中的所有数据："; PrintList(&head); cout << "--------------------------------------------" << endl; cout << "开始删除（这里删除第2个元素）............................" << endl; List_Delete(&head, 2, &e); // 删除第2个元素 cout << "删除操作完毕!" << endl; cout << "删除后打印线性表中的所有数据："; PrintList(&head); cout << "--------------------------------------------" << endl; cout << "开始查找（这里查找第6个元素）............................." << endl; Get_Data(&head,6, &e); // 查找第6个元素 cout << "查找操作完毕!" << endl; cout << "打印查找到的数据："; cout << e << endl; // 打印第6个元素 system("pause");}