线性表
- 2021-9-14【数据结构/严蔚敏】【顺序表】【代码实现算法2.1-2.7】
- 2021-9-18【数据结构/严蔚敏】【单链表】【代码实现算法2.8-2.12】
- 2021-9-18【数据结构/严蔚敏】【静态链表】【代码实现算法2.13-2.17】
- 2021-9-19【数据结构/严蔚敏】【双向链表】【代码实现算法2.18-2.19】
- 2021-9-19【数据结构/严蔚敏】【带头结点的线性表】【代码实现算法2.20-2.21】
- 2021-9-19【数据结构/严蔚敏】【一元多项式的表示及相加、相减、相乘】【代码实现算法2.22-2.23】
- 2021-9-23【数据结构】【单链表逆置】
- 2021-9-23【数据结构】【顺序表逆置】
栈&队列
- 2021-9-22【数据结构/严蔚敏】【顺序栈&链式栈&迷宫求解&表达式求值】【代码实现算法3.1-3.5】
- 2021-9-27【数据结构/严蔚敏】【链队列】
- 2021-9-28【数据结构/严蔚敏】【循环队列】
串
二叉树
持续更新中，尽请期待！！！
代码实现不易，希望在理解的基础上可以自行实现
切勿直接COPY
#include <bits/stdc++.h>
using namespace std;
#define Status int
typedef struct{
float coef;
int expn;
} term,ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
} * Link, *Position;
typedef struct{
Link head, tail;
int len;
} LinkList;
typedef LinkList polynomail;
Status MakeNode(Link &p, ElemType e){
//分配一个p指向的值为e的节点，并返回OK；如果分配失败，则error
p = new LNode;
p->data = e;
if(p)
return 1;
else
return 0;
}
void FreeNode(Link &p){
//释放p指向的节点
delete p;
p = NULL;
}
Status InitList(LinkList &L){
//初始化一个已经声明链表L
L.head = new LNode;
L.head->next = NULL;
L.tail = L.head;
L.len = 0;
if(L.head){
cout << "初始化成功"<<endl;
return 1;
}else
return 0;
}
Status ClearList(LinkList &L){
//将当前链表L清空，变成一个初始状态的链表
Link p = L.head->next;
while(p){
L.head->next = p->next;
delete p;
p = NULL;
L.len--;
p = L.head->next;
}
if(L.head->next==NULL){
return 1;
}else
return 0;
}
Status DestroyList(LinkList &L){
//销毁一个链表L
ClearList(L);
delete L.head;
L.head = NULL;
L.tail = NULL;
if(!L.head)
return 1;
else
return 0;
}
Status InsFirst(LinkList &L,Link h, Link s){
//在头节点位置插入一个新的节点,h指向头，s指向新的节点
s->next = h->next;
h->next = s;
if(h==L.tail)
L.tail = h->next;
L.len++;
return 1;
}
Status DelFirst(LinkList &L,Link h, Link &q){
//将头节点删除
q = h->next;
if(q){
h->next = q->next;
if(!h->next)
L.tail = h;
L.len--;
return 1;
}else
return 0;
}
Status Append(LinkList &L, Link s){
//向链表内插入数据，s以后的一个或若干个节点插入链表的尾部
//并修改链表的tail指针
int i = 1;
L.tail->next = s;
while(s->next){
s = s->next;
i++;
}
L.tail = s;
L.len += i;
return 1;
}
Status Remove(LinkList &L, Link &q){
//删除链表尾节点元素，由q返回
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
q = L.head;
while(q->next!=L.tail){
q = q->next;
}
L.tail = q;
q = q->next;
L.tail->next = NULL;
L.len--;
delete q;
q = NULL;
return 1;
}
Status SetCurElem(Link &p, ElemType e){
//修改当前指针p指向的元素的数据域的值为e
p->data = e;
return 1;
}
ElemType GetCurElem(Link p){
//获取当前指针p指向的元素的数据域的值，以e返回
return p->data;
}
Status ListEmpty(LinkList L){
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
if(L.head->next==NULL)
return 1;
else
return 0;
}
int ListLength(LinkList L){
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
return L.len;
}
Position GetHead(LinkList L)
{
//返回链表当中头节点的位置
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
return L.head;
}
Position PriorPos(LinkList L, Link p)
{
//由当前p指向的位置，查找p的邻接前一个节点的位置
Link q = L.head;
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
if(p==L.head)
return NULL;
while(q->next!=p){
q = q->next;
}
return q;
}
Position NextPos(LinkList L, Link p)
{
//由当前p指向的位置，查找p的下一个邻接元素的位置
if(!L.head){
cout << "线性链表不存在" << endl;
return 0;
}
if(p==L.tail)
return NULL;
return p->next;
}
Status LocateElem(LinkList L,ElemType e,Position &q,Status (*compare)(ElemType,ElemType)){
Link p = L.head, pp = p;
p = p->next;
while(p && (compare(p->data,e)<0)){
pp = p;
p = p->next;
}
if(!p||compare(p->data,e)>0){
q = pp;
return 0;
}
else{
q = p;
return 1;
}
}
void visit(ElemType e){
if (e.coef > 0 && e.coef != 1 && e.expn != 0)
{
if (e.expn > 0)
cout << e.coef << "x^" << e.expn ;
else
cout << e.coef << "x^(" << e.expn << ")";
}
else if (e.coef < 0 && e.expn != 0)
{
if (e.expn > 0)
cout << "(" << e.coef << ")x^" << e.expn ;
else
cout << "(" << e.coef << ")x^(" << e.expn << ")";
}
else if (e.coef == 1 && e.expn != 0)
{
if (e.expn > 0)
cout << "x^" << e.expn ;
else
cout << "x^(" << e.expn << ")";
}
else if (e.expn == 0 && e.coef != 0)
cout << e.coef;
else
cout << "";
}
Status ListTraverse(LinkList L,void(*visit)(ElemType))
{
Link p = L.head->next;
for (int i = 1; i <= L.len;i++)
{
visit(p->data);
if(i!=L.len)
cout<<"+";
p = p->next;
}
cout << "\b";
if(L.len == 0)
cout << "0";
return 1;
}
// typedef struct{
// float coef;
// int expn;
// } term,ElemType;
// typedef struct LNode{
// ElemType data;
// struct LNode *next;
// } * Link, *Position;
// typedef struct{
// Link head, tail;
// int len;
// } LinkList;
//---------------基本操作的函数原型-----------------------
//算法2.22
int cmp(term a,term b);
void CreatPolyn(polynomail &P,int m){
InitList(P);
Link h = GetHead(P);
ElemType e;
Link q, s;
e.coef = 0.0;
e.expn = -1;
SetCurElem(h, e);
for (int i = 1; i <= m;i++){
cout << "第"<<i<<"项"<<"的系数:";
cin >> e.coef;
cout << "第" << i << "项" << "的指数:";
cin >> e.expn;
if(!LocateElem(P,e,q,cmp) ){
if(e.coef!=0)
if(MakeNode(s,e))
InsFirst(P, q, s);
}else{
q->data.coef = q->data.coef + e.coef;
if(q->data.coef==0)
Remove(P, q);
}
}
}
void DestoryPolyn(polynomail &P){
DestroyList(P);
}
void PrintPolyn(polynomail P){
ListTraverse(P, visit);
}
int PolynLength(polynomail P){
return ListLength(P);
}
//算法2.23
void AddPolyn(polynomail &Pa,polynomail &Pb){
Link ha, hb, qa=NULL, qb=NULL;
ElemType a, b;
ha = GetHead(Pa); hb = GetHead(Pb);
if (Pa.len != 0 && Pb.len != 0)
{
qa = NextPos(Pa, ha);
qb = NextPos(Pb, hb);
while (qa && qb)
{
a = GetCurElem(qa);
b = GetCurElem(qb);
float sum;
switch (cmp(a, b))
{
case -1:
ha = qa;
qa = NextPos(Pa, ha);
break;
case 0:
sum = a.coef + b.coef;
if (sum != 0){
qa->data.coef = sum;
ha = qa;
}
else{
DelFirst(Pa ,ha, qa);
FreeNode(qa);
}
DelFirst(Pb ,hb, qb);
qb = NextPos(Pb, hb);
qa = NextPos(Pa, ha);
break;
case 1:
DelFirst(Pb ,hb, qb);
InsFirst(Pa ,ha, qb);
qb = NextPos(Pb, hb);
qa = NextPos(Pa, ha);
break;
}
}
if (!ListEmpty(Pb))
Append(Pa, qb);
FreeNode(hb);
}
if (Pa.len == 0){
Pa = Pb;
}
}
void SubtractPolyn(polynomail &Pa,polynomail &Pb){
Link p;
p = Pb.head;
while (p->next)
{
p = p->next;
p->data.coef *= -1;
}
AddPolyn(Pa, Pb);
}
void OrderInsert(LinkList &L,ElemType e,int (compare)(ElemType,ElemType)){
Link q, s;
if(LocateElem(L,e,q,compare)){
q->data.coef += e.coef;
if (!q->data.coef){
//系数为0，删除多项式中当前节点
s = PriorPos(L, q);
if(!s)//q无前驱
s = L.head;
DelFirst(L, s, q);
FreeNode(q);
}
}else{
//生成并插入
MakeNode(s, e);
InsFirst(L, q, s);
}
}
void MultiplyPolyn(polynomail &Pa,polynomail &Pb){
Link qa = GetHead(Pa);
Link qb = NULL;
polynomail Pc;
ElemType a, b, c;
InitList(Pc);
if (Pa.len != 0 && Pb.len != 0){
qa = qa->next;
while(qa){
a = GetCurElem(qa);
qb = GetHead(Pb);
qb = qb->next;
while(qb){
b = GetCurElem(qb);
c.coef = a.coef * b.coef;
c.expn = a.expn + b.expn;
OrderInsert(Pc, c, cmp);
qb = qb->next;
}
qa = qa->next;
}
DestoryPolyn(Pb);
ClearList(Pa);
Pa.head = Pc.head;
Pa.tail = Pc.tail;
Pa.len = Pc.len;
}
else if(Pb.len==0){
Pa = Pb;
}
}
//----------------基本算法描述------------------------
int cmp(term a,term b){
if (a.expn == b.expn)
return 0;
else
return (a.expn - b.expn) / abs(a.expn - b.expn);
}
int main()
{
polynomail A, B;
cout << "请输入第一个多项式的项数为：";
int length;
cin >> length;
CreatPolyn(A, length);
cout << "PA(x) = ";
ListTraverse(A, visit);
cout << endl;
cout << "请输入第二个多项式的项数为：";
cin >> length;
CreatPolyn(B, length);
cout << "PB(x) = ";
ListTraverse(B, visit);
cout << endl;
char m;
cout << "请输入运算符号:";
cin >> m;
switch (m){
case '+':
AddPolyn(A, B);
cout << "PA(x)+PB(x) = ";
ListTraverse(A, visit);
cout << endl;
break;
case '-':
SubtractPolyn(A, B);
cout << "PA(x)-PB(x) = ";
ListTraverse(A, visit);
cout << endl;
break;
case '*':
MultiplyPolyn(A, B);
cout << "PA(x)*PB(x) = ";
ListTraverse(A, visit);
cout << endl;
break;
default:
cout << "请输入正确符号";
}
system("pause");
return 0;
}
京公网安备 11010502036488号