首页 > 代码库 > 数据结构（4）——线性表的链式表示和实现
数据结构（4）——线性表的链式表示和实现
<style></style>
2.3.1 线性链表
线性链表的链式存储结构的特定是用一组任意的存储单元存储线性表的数据元素（这组数据存储单元可以是连续的，也可以是不连续的）。
节点包括：数据域和指针域
只包含一个指针域的称为线性链表又称为单链表。
单链表的主要操作代码如下：
#include<iostream>#include<string>using namespace std;// 定义元素类型typedef int ElemType;// 定义线性表的单链表存储结构typedef struct LNode{ ElemType data; struct LNode *next;}LNode, *LinkList;// 功能: 获取第i个结点上的值// 入参: L 带头结点的单链表// 入参: i 位置i// 入参: e 第i个位置上的值// 返回: ERROR 没找到, OK 找到string GetElemByIndex(LinkList L, int i, ElemType &e){ // L为带头结点的单链表 // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p = L->next; int j = 1; while(p && j < i) { p = p->next; j ++; } if (!p || j > i) { return "ERROR"; } e = p ->data; return "OK";}// 功能: 在第 i 个位置前插入数值e// 入参: L 单链表// 入参: i 第i个位置// 入参: e 要插入第i个位置的值// 返回: OK 插入成功，ERROR 插入不成功string InsertLinkList(LinkList &L, int i, ElemType e){ // 带头结点的单链表 LinkList p = L->next; int j = 1; // 寻找第 i - 1 个结点 while(p && j < i - 1) { p = p->next; j ++; } if (!p || j > i - 1) { return "ERROR"; } LinkList s = (LinkList)malloc(sizeof(LNode)); s->data =http://www.mamicode.com/ e; s->next = p->next; p->next = s; return "OK";}// 功能: 删除带头结点单链表第i个位置上的值// 入参: 带头结点的单链表// 入参: i 第i个结点// 返回: ERROR 删除不成功，OK 删除成功string DelLinkList(LinkList &L, int i){ LinkList p = L->next; int j = 1; while(p && j < i - 1) { p = p->next; j ++; } if (!p || j > i - 1) { return "ERROR"; } LinkList q = p->next; p->next = q->next; free(q); return "OK";}// 功能: 创建一个单链表// 入参: LinkList &L 单链表// 入参: int n 单链表的长度// 返回值: 空void CreateLinkList(LinkList &L, int n){ // 创建头结点 L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; LinkList p; int i; for(i = 0; i <= n ; i++) { p = (LinkList)malloc(sizeof(LNode)); p->data =http://www.mamicode.com/ i; p->next = L->next; L->next = p; }}// 功能: 遍历输出单链表// 入参: 带头结点的单链表// 返回值: 空void Display(LinkList L){ LinkList p = L->next; cout << "遍历单链表结果如下:" << endl; while(p) { cout << p->data << " "; p = p->next; } cout << endl;}// 主函数void main(){ // 带头结点的单链表 LinkList L; // 创建10个结点个数的单链表 CreateLinkList(L, 10); // 遍历输出单链表 Display(L); // 获取第i个位置上的元素 ElemType e; string status = GetElemByIndex(L, 12, e); cout << status << "," << e << endl; // 在第 i 个位置之前插入数值e string insertStatus = InsertLinkList(L, 4, 90); cout << insertStatus << endl; Display(L); // 删除第i个位置上的结点 string delStatus = DelLinkList(L, 5); cout << delStatus << endl; Display(L);}
数据结构（4）——线性表的链式表示和实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。