#include <iostream>
#include <string>using namespace std;typedef int Etype; // 自定义链表的数据元素为整数。
//定义数据元素节点结构
typedef struct ChainNode
{Etype data; // 存放结点的数据元素。ChainNode* next; // 指向下一个结点的指针。
};//ChainNode* p; //p是指向数据元素结构的指针
//p->data表示当前数据元素的值
//p->next表示下一个元素的地址
//p的值是某数据节点的起始地址typedef string HeadEtype; // 自定义表头的数据元素为整数。
//定义表头结构
typedef struct HeadNode
{HeadEtype Hdata; // 存放结点的数据元素。ChainNode* first; // 指向下一个结点的指针。
};//将表头结点和若干个数据节点链在一个组成一个链接表//我们定义一个表头类型的执行变量,这个变量也是一个链表:
//HeadNode* L, * L1, *stud;
或者
//ChainNode L, L1, stud;//如果表头节点和数据节点的结构是相同的,那么表头节点的结构也可以用
//数据节点的结构类型来定义:
// ChainNode* L, * L1, *stud;//将表头节点指向数据节点
typedef HeadNode* ChainList;
//创建一个空链表
void CreatChainList(ChainList& L)//输入一个数据节点
{L = new HeadNode;L->first = NULL;//表头节点的链接域设为NULLL->Hdata = "HeadNode类型的数据值";//表头节点的数据域填入相应数据
}//将第k个节点移动至表首bool MoveFirstChainList(ChainList &L,int k) {if (k < 1 || L->first) return false;//第k个节点为0,或者为空表ChainNode* current = L->first;//current为第一个数据的地址if (k == 1) return true;//如果要移至表首数据就是第一个,就不用移动了else {ChainNode* q = L->first;for (int index = 1; index < k - 1; index++) {q = q->next;//}//q目前为第k-1个元素的地址if (!q || !q->next) return false;//第k-1个元素的地址和k素地址为空current = q->next;//current为k数据的地址q->next = current->next;//将k元素的地址替换为k+1数据的地址}current->next = L->first;//将k元素的下一个元素换为原表第一个元素L->first = current;//将第一个元素的地址改为第k元素的地址return true;
}//将线性表L逆向
bool InvertChainList(ChainList &L) {ChainNode *current;ChainNode* p = L->first;//p为第一个元素地址L->first = NULL;//将表头指向上一个元素,自然是NULLwhile (p) {current = p;//第一次循环,current为第一个元素地址p = p->next;//p替换为第二个元素的地址current->next = L->first;//当前元素想前指L->first = current;//表头指向下一个元素}//NULL<-1<-2.......<-firstreturn true;
}//多项式的相加运算
struct PolyNode {int exp;//指数float coef;//系数PolyNode* next;//下一元素地址
};struct ChainNode {PolyNode data;//数据节点ChainNode* next;//下一数据节点地址
};//多项式链表L1和L2相加
void AddPolyL1(ChainList& L1, ChainList& L2)
{ChainNode* p;//存L1ChainNode* q;//存L2ChainNode* p0;ChainNode* x;int choice;p = L1->first;q = L2->first;p0 = NULL;while (p && q) {//当前节点不为空if (p->data.exp > q->data.exp) choice = 1;if (p->data.exp == q->data.exp) choice = 2;//指数相等if (p->data.exp < q->data.exp) choice = 3;//较大指针指向下一个节点,较小节点不动switch (choice){case 1:{p0 = p;//L1系数比较大p = p->next;//指向下一个节点break;}case 2: {//指数相等,将L1+l2存入L1p->data.coef = p->data.coef + q->data.coef;if (p->data.coef == 0) {p0->next = p->next;//p0指向下一节点delete p;//删除系数为0的节点p = p0->next;//p指向下一节点}else {p0 = p;//将结果存入结果链表中p = p0->next;//同时指向下一个节点}q = q->next;//指向下一个节点break;}case 3: {//L2系数比较大x = new ChainNode;x->data.coef = q->data.coef;x->data.exp = q->data.exp;x->next = p;//L1系数if (p0)p0->next = x;elseL1->first = x;p0 = x;q = q->next; //q指向下一节点break;}}}while (q) {//对比较长的链表,逐一移动到结果链表p0中x = new ChainNode;x->data.coef = q->data.coef;x->data.exp = q->data.exp;x->next = NULL;if (!L1->first) L1->first = x;else p0->next = x;p0 = x;q = q->next;}
}void AddPolyL3(ChainList& L1, ChainList& L2, ChainList& L3) {ChainNode* p, * q, * r, * x;int choice;float coef;p = L1->first;q = L2->first;r = L3->first;while (p && q) {if (p->data.exp > q->data.exp) choice = 1;if (p->data.exp == q->data.exp) choice = 2;//指数相等if (p->data.exp < q->data.exp) choice = 3;//较大指针指向下一个节点,较小节点不动switch (choice) {case 1: {//p指数比较大x = new ChainNode;//新建一个数据节点,用途是记录当前节点数据x->data.coef = p->data.coef;x->data.exp = p->data.exp;x->next = NULL;if (r)//r->next = x;//r下一个元素存入xelse//r目前指向第一个元素L3->first = x;//将p指向的数据作为链表的第一个数据r = x;//r当前元素存入xp=p->next;//p指向下一个数据break;}case 2: {//指数相等coef = p->data.coef + q->data.coef;if (coef)//指数不为零{x = new ChainNode;//新建一个数据节点,用途是记录当前节点数据x->data.coef = coef;x->data.exp = p->data.exp;x->next = NULL;if (r)//r->next = x;//r下一个元素存入xelse//r目前指向第一个元素L3->first = x;//将p指向的数据作为链表的第一个数据r = x;//r当前元素存入x}p = p->next;q = q->next;break;}case 3: {x = new ChainNode;//新建一个数据节点,用途是记录当前节点数据x->data.coef = q->data.coef;x->data.exp = q->data.exp;x->next = NULL;if (r)//r->next = x;//r下一个元素存入xelse//r目前指向第一个元素L3->first = x;//将p指向的数据作为链表的第一个数据r = x;//r当前元素存入xq = q->next;//p指向下一个数据break;}}}while (q)//p的系数读取完了,继续将q后续的指数存入L3{x = new ChainNode;//新建一个数据节点,用途是记录当前节点数据x->data.coef = q->data.coef;x->data.exp = q->data.exp;x->next = NULL;if (r)//r->next = x;//r下一个元素存入xelse//r目前指向第一个元素L3->first = x;//将p指向的数据作为链表的第一个数据r = x;//r当前元素存入xq = q->next;//p指向下一个数据}}
详细解决方案
深入理解数据结构——链表应用
热度:66 发布时间:2024-01-17 05:11:12.0
相关解决方案
- 算法效率(数据结构),该如何解决
- 数据结构,很无力~该怎么处理
- 数据结构,该怎么处理
- java 数据结构,该如何解决
- 数据库 数据结构 关于索引解决办法
- 数据结构,离散数学什么的重要吗。该怎么解决
- 数据结构 - 线性表学习(php模拟)
- 【数据结构】【归并排序】
- 数据结构 05——树与二叉树
- 数据结构——01数据结构绪论
- 数据结构——02算法简介
- 《数据结构(C语言版)》课程学习(15)——实验项目名称:矩阵的转置
- 数据结构--连续内存分配的实现
- n叉树 数据结构
- 链表 数据结构
- Hash表 数据结构
- 数据结构——红黑数学习
- c(数据结构)下树的创建的非递归算法
- 数据结构-时间复杂度大O排名
- 数据结构---顺序表
- 数据结构----顺序栈
- 【数据结构】#数据结构复习提纲
- 数据结构 递归遍历二叉树 C/C++
- 数据结构 C/C++ 冒泡排序
- 数据结构 C/C++ 关键路径
- 数据结构 C/C++ 链栈
- 数据结构 C/C++ 链式队列
- 数据结构 C/C++ 对角矩阵
- 数据结构 C/C++ 对称矩阵
- C/C++ 数据结构 单链表