單鏈表的基本操作

2019-11-14 12:19:33

字體：大中小

供稿：網(wǎng)友

代碼示例

/* function：?jiǎn)捂湵淼幕静僮? 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 // 結(jié)構(gòu)體定義{ ElemType data; struct Node *next;} Node;typedef struct Node *LinkList;/* 功能: 初始化一個(gè)帶有頭結(jié)點(diǎn)的單鏈表*/LinkList InitList(){ LinkList head; head = (LinkList)malloc(sizeof(LinkList)); head->next = NULL; // 頭結(jié)點(diǎn)指向NULL表示這是一個(gè)帶有頭結(jié)點(diǎn)的空單鏈表 return head;}/* 功能：頭插法(隨機(jī))建立一個(gè)單鏈表*/void CreateFormHead(LinkList *head, int n){ LinkList s; int i; srand(time_t(1)); // 隨機(jī)種子 for (i = 0; i < n; i++) { s = (LinkList)malloc(sizeof(LinkList)); // 申請(qǐng)內(nèi)存 s->data = rand() % 100 + 1; // 隨機(jī)生成0-100內(nèi)任意的一個(gè)數(shù) s->next = (*head)->next; // 將申請(qǐng)結(jié)點(diǎn)的next指向原來(lái)頭結(jié)點(diǎn)的next (*head)->next = s; // 將頭結(jié)點(diǎn)的next指向申請(qǐng)的結(jié)點(diǎn) }}/* 功能：頭插法(自己輸入)建立一個(gè)單鏈表*/void CreateFormHead2(LinkList *head){ LinkList s; double c; int flag = 1; while (flag) { cin >> c; if (c != -99999) // 輸入-99999結(jié)束輸入 { s = (LinkList)malloc(sizeof(LinkList)); // 申請(qǐng)內(nèi)存 s->data = c; // 將輸入的數(shù)據(jù)放到申請(qǐng)結(jié)點(diǎn)的data中 s->next = (*head)->next; // 將申請(qǐng)結(jié)點(diǎn)的next指向原來(lái)頭結(jié)點(diǎn)的next (*head)->next = s; // 將頭結(jié)點(diǎn)的next指向申請(qǐng)的結(jié)點(diǎn) } else { flag = 0; } }}/* 功能：利用尾插法創(chuàng)建單鏈表*/void CreateFormTail(LinkList *head){ LinkList r,s; r = *head; double c; int flag = 1; while (flag) { cin >> c; if (c != -99999) // 輸入-99999結(jié)束輸入 { s = (LinkList)malloc(sizeof(LinkList)); s->data = c; // 將輸入的數(shù)據(jù)放到申請(qǐng)結(jié)點(diǎn)的data中 r->next = s; // 第一次時(shí)，r原本指向頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)的next指向申請(qǐng)的結(jié)點(diǎn) r = s; // 將r指向申請(qǐng)結(jié)點(diǎn)，意思是，r和s都指向最后一個(gè)結(jié)點(diǎn) } else { flag = 0; r->next = NULL; } }}/* 功能:在帶頭節(jié)點(diǎn)的單鏈表第 i 個(gè)位置插入元素 e*/Status List_Insert(LinkList *head, int i, ElemType e){ LinkList PRe, s; pre = *head; // 將指針 pre 指向鏈表的頭結(jié)點(diǎn) int k=1; while (pre && k < i) // 找到第 i-1 個(gè)結(jié)點(diǎn)，使指針 pre 指向它 { pre = pre->next; k++; } if (!pre || k > i) { cout << "插入位置不合理！" << endl; return ERROR; } s = (LinkList)malloc(sizeof(Node)); // 為 e 申請(qǐng)一個(gè)新的結(jié)點(diǎn)并由 s 指向它 s->data = e; // 將帶插入結(jié)點(diǎn)的值 e 賦給 s 的數(shù)據(jù)域 s->next = pre->next; // 插入操作 pre->next = s; // 插入操作 return OK;}/* 功能：刪除單鏈表第 i 個(gè)位置的元素，并將刪除的元素保存到變量 *e 中*/Status List_Delete(LinkList *head, int i, ElemType *e){ LinkList pre, r; pre = *head; int k = 1; // 如果k=0, 則下面程序找到的是第 i 個(gè)元素 while (pre->next && k < i) // 找到第 i-1 個(gè)結(jié)點(diǎn)，使指針 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 個(gè)元素，并將該的元素保存到變量 *e 中*/Status Get_Data(LinkList *head, int i, ElemType *e){ LinkList p; p = *head; int k = 0; // 如果k=1, 則下面程序找到的是第 i-1 個(gè)元素 while (p && k < i) // 找到第 i 個(gè)元素，指針 p 指向第 i 個(gè)元素 { p = p->next; k++; } if (!p || k > i) { cout << "查找位置不合理！" << endl; return ERROR; } *e = p->data; // 將第 i 個(gè)元素保存到變量 *e 中 return OK;}/* 功能：顯示單鏈表中所有數(shù)據(jù)*/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 << "開(kāi)始初始化..............................................." << endl; head = InitList(); // 初始化一個(gè)空鏈表 cout << "初始化操作完畢！" << endl; cout << "開(kāi)始建表(這里是尾插法建表，輸入-99999結(jié)束建表)..........." << endl; //CreateFormHead(&head,10); // 頭插法，隨機(jī)插入10個(gè)數(shù)（可用） //CreateFormHead2(&head); // 頭插法，自己創(chuàng)建（可用） CreateFormTail(&head); // 尾插法，自己創(chuàng)建 cout << "建表操作完畢！" << endl; cout << "開(kāi)始插入................................................." << endl; List_Insert(&head, 5, 21); // 插入21在第5個(gè)位置上 cout << "插入操作完畢！" << endl; cout << "打印線性表中的所有數(shù)據(jù)："; PrintList(&head); cout << "--------------------------------------------" << endl; cout << "開(kāi)始刪除（這里刪除第2個(gè)元素）............................" << endl; List_Delete(&head, 2, &e); // 刪除第2個(gè)元素 cout << "刪除操作完畢!" << endl; cout << "刪除后打印線性表中的所有數(shù)據(jù)："; PrintList(&head); cout << "--------------------------------------------" << endl; cout << "開(kāi)始查找（這里查找第6個(gè)元素）............................." << endl; Get_Data(&head,6, &e); // 查找第6個(gè)元素 cout << "查找操作完畢!" << endl; cout << "打印查找到的數(shù)據(jù)："; cout << e << endl; // 打印第6個(gè)元素 system("pause");}