数据结构与算法 单链表

单链表

单链表是一种线性结构，单链表存储分成两部分，一部分存储数据，另一部分存储下一个节点（也就是指向下一个链表的地址（单指向））的地址。

1.定义链表，初始化链表

创建头节点，指针域置空。—代码注释为详细内容

//结构体定义链表 typedef struct _LinkNode { int data; //数据域(存储数据) struct _LinkNode* next; //指针节点，指向(存储)下个链表节点的地址 }LinkNode,LinkList; 链表节点、链表 //初始化链表,定义头节点 bool InitList(LinkList* &L) { //构造一个空的单链表 L L = new LinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) { cout << "初始化链表失败！" << endl; return false;//生成结点失败 } L->next = NULL; //头结点的指针域置空 cout << "初始化链表成功！" << endl; return true; }

2.单链表增加元素（前插法）

头节点后为每次插入的新节点，先插后出（最先插入的节点的节点元素，输出时则在最后面）

//前插法 bool ListInsert_front(LinkList*& L, LinkNode* node) {//L为头节点，node为新节点(子节点) if (!L || !node) return false;//防止链表为空 node->next = L->next;//将头节点指向的下一个节点的地址赋值给新节点 L->next = node; //将头节点指针指向新节点的地址 return true; }

3.尾插法

循环找出最后一个节点，然后在该位置插入，原最后节点指针指向新节点，新节点指针设置为空。

//尾插法 bool ListInsert_back(LinkList*& L, LinkNode* node) { LinkNode* last = NULL; if (!L || !node) return false;//判断是否为空 last = L;//指向头链表，将头链表的地址赋给last指针 //通过循环找到最后一个(节点)链表，即指针域存储为NULL的链表 while (last->next) last = last->next;//如果链表中next指针不为空，那么就指向下一个链表的地址 node->next = NULL;//将新节点的指针域设置为空 last->next = node;//将原链表中最后一个节点的指针指向新链表的地址 return true; }

4.任意位置插入法

通过循环找出要插入位置的节点，然后将(要插入位置的)前节点指针指向新节点的地址，再将新节点指针指向(i+1)的节点的地址。

//任意位置插入 bool LinkInsert(LinkList*& L, int i, int& e) { //在单链表L中，在第i个位置插入元素e if (!L) return false; //判断是否为空 int j = 0; LinkList* p, * s; p = L; //指针p指向头节点 //找出要插入节点位置的前一个结点 while (p && j < i - 1) {//查找位置为i-1的节点，p指向该节点 p = p->next; j++; } if (!p || j > i - 1) {//判断p是否为空或者i值是否合法 return false; } s = new LinkNode;//生成新节点 s->data = e;//把插入的元素值赋值给新结点的数据域 s->next = p->next;//将新节点指针指向原i节点的地址 p->next = s;//将原(i-1)节点指针指向新节点地址 return true; }

5.获取单链表中的元素

通过要查找的位置i循环查找链表，找到后把元素值赋值给e。

//单链表的取值 bool Link_GetElem(LinkList* &L,int i,int &e) { //在带头结点的单链表L中查找第i个元素(i为查找的元素位置) //用e记录L中第i个数据元素的值(e为被查找的元素值) int index; LinkList* p; if (!L || !L->next) return false; //判断是否为空 p = L->next;//p指向第一个节点 index = 1; //计数器，记录当前为哪一个节点（链表） while (p && index<i) {//链表依次向后扫描,直到指针p指向所指i个元素或者p为空 p = p->next; //p指向下一个节点(下一个链表的地址) index++; //每循环一次index加1 } if (!p || index > i) { return false; //要查询的元素个数i不合法,i>n或i<=0 } e = p->data;//将被查找节点的元素赋值给e return true; }

6.单链表查找元素

循环判断该节点元素值是否与要查找元素值相等。

//单链表查找元素(查询) bool Link_FindElem(LinkList* L, int e, int &index) {//按值查找 //在带头结点的单链表L中查找值为e的元素 LinkList* p; p = L->next; //指针p指向第一个节点 index = 1; //计数器 if (!L || !L->next) { index = -1; return false; }//判断是否为空 while (p && p->data != e) { //判断该节点元素值是否与要查找元素值相等 p = p->next; index++; //该节点位置 } if (!p) { index = -1; return false;//查无此值 } return true; }

7.单链表中元素的删除(通过位置删除)

被删除节点要释放内存空间

//单链表中元素的删除 bool LinkDelete(LinkList*& L, int i) {//i为要删除节点的位置 LinkList* p,*q; int index = 0; p = L;//将指针p指向头节点(链表) if (!L || !L->next) { return false; }//判断是否为空 //判断p指针是否为空 要删除节点位置i是否合法 while ((p->next) && (index < i - 1)) {//循环查找i节点 p = p->next; index++; } if (!p->next || (index > i - 1)) {//当i>n或者i<1时,删除位置不合理 return false; } q = p->next; //临时保存被删除节点的地址以备释放空间 p->next = q->next; //将(被删除节点)的前节点的指针指向(被删除节点)的后节点的地址 delete q; //释放被删除节点的空间 return true; }

8.单链表的销毁

通过循环释放内存空间，完成销毁。

//单链表的销毁 void LinkDestroy(LinkList*& L) { //定义临时节点p指向头节点 LinkList* p = L; //将指针p指向头节点(链表) cout << "销毁链表" << endl; while (p) { L = L->next;//L指向下一个节点 delete p; //删除当前节点 p = L; //p移向下一个节点 } }

9.完整代码

#include <iostream> #include <string> #include <stdlib.h> using namespace std; //结构体定义链表 typedef struct _LinkNode { int data; //数据域(存储数据) struct _LinkNode* next; //指针节点，指向(存储)下个链表节点的地址 }LinkNode,LinkList; 链表节点、链表 //初始化链表,定义头节点 bool InitList(LinkList* &L) { //构造一个空的单链表 L L = new LinkNode; //创建新结点作为头结点，用头指针L指向头结点 if (!L) { cout << "初始化链表失败！" << endl; return false;//生成结点失败 } L->next = NULL; //头结点的指针域置空 cout << "初始化链表成功！" << endl; return true; } //前插法 bool ListInsert_front(LinkList*& L, LinkNode* node) {//L为头节点，node为新节点(子节点) if (!L || !node) return false;//防止链表为空 node->next = L->next;//将头节点指向的下一个节点的地址赋值给新节点 L->next = node; //将头节点指针指向新节点的地址 return true; } //遍历链表 void LinkPrint(LinkList*& L) { LinkNode* p = NULL; if (!L) { cout << "链表为空." << endl; return; } p = L->next; while (p) { cout << p->data << "\t"; p = p->next; } printf("\n"); } //尾插法 bool ListInsert_back(LinkList*& L, LinkNode* node) { LinkNode* last = NULL; if (!L || !node) return false;//判断是否为空 last = L;//指向头链表，将头链表的地址赋给last指针 //通过循环找到最后一个(节点)链表，即指针域存储为NULL的链表 while (last->next) last = last->next;//如果链表中next指针不为空，那么就指向下一个链表的地址 node->next = NULL;//将新节点的指针域设置为空 last->next = node;//将原链表中最后一个节点的指针指向新链表的地址 return true; } //任意位置插入 bool LinkInsert(LinkList*& L, int i, int& e) { //在单链表L中，在第i个位置插入元素e if (!L) return false; //判断是否为空 int j = 0; LinkList* p, * s; p = L; //指针p指向头节点 //找出要插入节点位置的前一个结点 while (p && j < i - 1) {//查找位置为i-1的节点，p指向该节点 p = p->next; j++; } if (!p || j > i - 1) {//判断p是否为空或者i值是否合法 return false; } s = new LinkNode;//生成新节点 s->data = e;//把插入的元素值赋值给新结点的数据域 s->next = p->next;//将新节点指针指向原i节点的地址 p->next = s;//将原(i-1)节点指针指向新节点地址 return true; } //单链表的取值 bool Link_GetElem(LinkList* &L,int i,int &e) { //在带头结点的单链表L中查找第i个元素(i为查找的元素位置) //用e记录L中第i个数据元素的值(e为被查找的元素值) int index; LinkList* p; if (!L || !L->next) return false; //判断是否为空 p = L->next;//p指向第一个节点 index = 1; //计数器，记录当前为哪一个节点（链表） while (p && index<i) {//链表依次向后扫描,直到指针p指向所指i个元素或者p为空 p = p->next; //p指向下一个节点(下一个链表的地址) index++; //每循环一次index加1 } if (!p || index > i) { return false; //要查询的元素个数i不合法,i>n或i<=0 } e = p->data;//将被查找节点的元素赋值给e return true; } //单链表查找元素(查询) bool Link_FindElem(LinkList* L, int e, int &index) {//按值查找 //在带头结点的单链表L中查找值为e的元素 LinkList* p; p = L->next; //指针p指向第一个节点 index = 1; //计数器 if (!L || !L->next) { index = -1; return false; }//判断是否为空 while (p && p->data != e) { //判断该节点元素值是否与要查找元素值相等 p = p->next; index++; //该节点位置 } if (!p) { index = -1; return false;//查无此值 } return true; } //单链表中元素的删除 bool LinkDelete(LinkList*& L, int i) {//i为要删除节点的位置 LinkList* p,*q; int index = 0; p = L;//将指针p指向头节点(链表) if (!L || !L->next) { return false; }//判断是否为空 //判断p指针是否为空 要删除节点位置i是否合法 while ((p->next) && (index < i - 1)) {//循环查找i节点 p = p->next; index++; } if (!p->next || (index > i - 1)) {//当i>n或者i<1时,删除位置不合理 return false; } q = p->next; //临时保存被删除节点的地址以备释放空间 p->next = q->next; //将(被删除节点)的前节点的指针指向(被删除节点)的后节点的地址 delete q; //释放被删除节点的空间 return true; } //单链表的销毁 void LinkDestroy(LinkList*& L) { //定义临时节点p指向头节点 LinkList* p = L; //将指针p指向头节点(链表) cout << "销毁链表" << endl; while (p) { L = L->next;//L指向下一个节点 delete p; //删除当前节点 p = L; //p移向下一个节点 } } int main(void) { LinkList* L = NULL; //定义一个链表指针,值置为空 LinkList* s = NULL; //1.初始化链表 InitList(L); //------------------------------------------------------------------------------- //2.前插法 int n; cout << "前插法创建单链表" << endl; cout << "请输入元素个数:"; cin >> n; cout << "\n请依次输入n个元素："; while (n-- > 0) { s = new LinkNode; //生成新节点 cin >> s->data; ListInsert_front(L,s); } //打印链表 LinkPrint(L); cout << "-------------------" << endl; //------------------------------------------------------------------------------- //3.尾插法 cout << "尾插法创建单链表" << endl; cout << "请输入元素个数:"; cin >> n; cout << "\n请依次输入n个元素："; while (n > 0) { s = new LinkNode; //生成新节点 cin >> s->data; ListInsert_back(L, s); n--; } //打印链表 LinkPrint(L); //------------------------------------------------------------------------------- //4.任意位置插入元素 int o; cout << "请问你要插几个元素:"; cin >> o; for (int r = 0; r < o; r++) { int i, x; cout << "请输入插入的位置和元素（用空格隔开）:"; cin >> i; cin >> x; if (LinkInsert(L, i, x)) { cout << "插入成功!\n\n"; } else { cout << "插入失败!\n\n"; } //打印链表 LinkPrint(L); } //------------------------------------------------------------------------------- //5.获取链表中指定位置的元素值 int value = 0; int i = 0; cout << "你要获取哪个位置的元素?" << endl; cin >> i; if (Link_GetElem(L, i, value)) { cout << "获取成功! 值为:" << value << endl; } else { cout << "获取失败!" << endl; } //------------------------------------------------------------------------------- //6.查询链表中的元素 int index = 0; int e; cout << "输入你要查询的元素值:"; cin >> e; if (Link_FindElem(L, e, index)) { cout << "查询成功! 值为:" << e << endl; cout << "该值位置为" << index << endl; } else { cout << "查询失败!" << endl; } //------------------------------------------------------------------------------- //7.单链表中元素的删除 int w = 0; cout << "输入你要删除的元素位置:"; cin >> w; if (LinkDelete(L, w)) { cout << "删除成功!" << endl; } else { cout << "删除失败!" << endl; } //打印链表 LinkPrint(L); //------------------------------------------------------------------------------- //8.销毁链表 LinkDestroy(L); system("pause"); return 0; }