浦项建设(中国)有限公司网站,域名注册免费平台,网页设计心得体会400字,湖南网站设计外包服务目录
前言
一、顺序表的优缺点
二、单链表的表示和实现
1.初始化
2.清空表
3.销毁
4.表长
5.表空
6.获取表中的元素
7.下标
8.直接前驱
9.直接后继
10.插入
11.删除
12.遍历链表
13.测试代码 前言 这篇博客主要介绍单链表的表示和实现。
一、顺序表的优缺点 线…
目录
前言
一、顺序表的优缺点
二、单链表的表示和实现
1.初始化
2.清空表
3.销毁
4.表长
5.表空
6.获取表中的元素
7.下标
8.直接前驱
9.直接后继
10.插入
11.删除
12.遍历链表
13.测试代码 前言 这篇博客主要介绍单链表的表示和实现。
一、顺序表的优缺点 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单直观的公式来表示。当然这种存储结构也存在弱点:在作插入或删除操作时,需移动大量元素。
二、单链表的表示和实现 单链表的两个要素数据域指针域。其中数据域表示的是当前结点的数据指针域指向的下一个结点的地址。 单链表的定义如下
// - - - - - 线性表的单链表存储结构 - - - - -
typedef int ElemType;
typedef int Staus;
typedef struct LNode {ElemType data; // 数据域struct LNode *next; // 指针域
} LNode, *LinkList;
1.初始化
// 链表初始化
Staus initLinkList(LinkList linkList) {linkList new LNode; // 创建头结点if (!linkList) { // 内存分配失败return false;}linkList-next nullptr; // 头结点的指针域置空return true;
}
2.清空表 遍历单链表置空指针
// 清空链表
void clearLinkList(LinkList linkList) {LinkList p, q;p linkList-next;while (p) {q p;p p-next;delete q;}linkList-next nullptr;
}
3.销毁
// 销毁链表
void destroyLinkList(LinkList linkList) {clearLinkList(linkList);delete linkList;linkList nullptr;
}
4.表长
// 表长
int linkListLength(LinkList link){LNode * p link-next;int len 0;while (p) {p p-next;len;}return len;
}
5.表空
// 表空
Status linkListEmpty(LinkList link){return linkListLength(link) 0;
}
6.获取表中的元素
// 获取表中的元素
Status getElemLinkList(LinkList link,int pos,ElemType * element){if (pos 1|| pos linkListLength(link)) {return 0;}LinkList p link-next;int j 1;while (p j pos) {p p -next;j;}if (!p ||j pos) {return 0;}*element p-data;return 1;
}
7.下标
// 获取数据元素element下标
Status getLocateinkList(LinkList link,ElemType element,int * location){LinkList p link-next;int j 1;while (p) {if (p-data element) {* location j;return 1;}p p -next;j;}return 0;
}8.直接前驱
// 直接前驱
Status priorElemLinkList(LinkList link,ElemType current,ElemType * priorElement){LinkList p link-next;LinkList head link;int j 1;while (p) {if (p-data current) {//找到数据元素if (j 1) {* priorElement head-data;return 1;}}p p -next;head head-next;j;}return 0;
}
9.直接后继
// 直接后继
Status nextElemLinkList(LinkList link,ElemType current,ElemType * nextElement){LinkList p link-next;while (p) {if (p-data current) {//找到数据元素if (p - next ! nullptr) {* nextElement p-next-data;return 1;}}}return 0;
}
10.插入
// 单链表插入
Status insertLinkList(LinkList head, int pos, int element) {if (pos 1) { // 位置非法return 0;}LinkList p head;int j 0;while (p j pos - 1) {p p-next;j;}if (!p || j pos - 1) {return 0;}LinkList q new LNode; // 生成新节点if (!q) { // 内存分配失败return 0;}q-data element;q-next p-next;p-next q;return 1;
}
11.删除
// 单链表删除
Status deleteLinkList(LinkList head, int pos) {if (pos 1 || !head-next) { // 位置非法或空链表return false;}LinkList p head;int j 0;while (p-next j pos - 1) { // 找到要删除结点的前一个结点p p-next;j;}if (!p-next || j pos - 1) { // 删除位置超出范围return false;}LinkList q p-next; // 要删除的结点p-next q-next; // 前一个结点指向后一个结点delete q; // 释放删除结点的内存return true;
}
12.遍历链表
// 遍历链表
void traverseList(LinkList linkList) {LinkList p linkList-next;while (p) {cout p-data ;p p-next;}cout endl;
}
13.测试代码
void testLinkList(void){LinkList myList;if (!initLinkList(myList)) {cout 链表初始化失败 endl;}cout表长:linkListLength(myList)endl;int values[] {1, 2, 3, 4, 5};int size sizeof(values) / sizeof(values[0]);if (!createLinkList(myList, values, size)) {cout 创建链表失败 endl;destroyLinkList(myList); // 避免内存泄漏}cout 链表元素;traverseList(myList);cout表长:linkListLength(myList)endl;cout 获取某个位置的数据元素endl;for (int i -1; i 6; i) {int element;if (getElemLinkList(myList, i, element)) {cout第i个数据元素获取成功,数据元素为:element\tendl;}else{cout第i个数据元素获取失败!endl;}}coutendl;cout 获取单链表数据元素下标endl;for (int i -1; i 6; i) {int locate;if (getLocateinkList(myList, i, locate)) {cout数据元素i下标获取成功,下标为:locate\tendl;}else{cout数据元素i下标获取失败!endl;}}coutendl;cout 获取单链表数据元素直接前驱endl;for (int i -1; i 6; i) {int element;if (priorElemLinkList(myList, i, element)) {cout数据元素i直接前驱为:element\tendl;}else{cout数据元素i没有直接前驱!endl;}}// 插入元素int insertPos 3;int insertElement 10;if (!insertLinkList(myList, insertPos, insertElement)) {cout 插入元素失败 endl;destroyLinkList(myList); // 避免内存泄漏}cout 插入后的链表元素;traverseList(myList);// 删除元素int deletePos 2;if (!deleteLinkList(myList, deletePos)) {cout 删除元素失败 endl;destroyLinkList(myList); // 避免内存泄漏}cout 删除后的链表元素;traverseList(myList);// 清空链表clearLinkList(myList);cout 链表已清空 endl;// 销毁链表destroyLinkList(myList);cout 链表已销毁 endl;
}
