2021-11-9【数据结构平时实验】

LNode *p;

if (!FindPreNode(L, data, p))

{

cout << “没有找到此结点!\n”;

return 0;

}

else

{

LNode *s = p->next;

p->next = s->next;

free(s);

return 1;

}

}

//打印链表元素

void TraveList(LinkList L)

{

LNode *p = L->next;

if (p == NULL)

{

cout << “链表为空表!\n”;

}

else

{

while (p != NULL)

{

cout << p->data << ’ ';

p = p->next;

}

cout << endl;

}

}

int main()

{

LinkList L;

InitList(L);

int n;

cout << “请输入要插入字母数：\n”;

cin >> n;

for (int i = 1; i <= n; i++)

{

char ch;

cin >> ch;

InsertNode(L, ch);

}

TraveList(L);

cout << “请输入要删除字母数：\n”;

cin >> n;

for (int i = 1; i <= n; i++)

{

char ch;

cin >> ch;

DeleteNode(L, ch);

}

TraveList(L);

return 0;

}

[](()2-2.用有序链表实现集合的并、交、差运算；

#include

using namespace std;

typedef int ElemType;

//链表结构体

typedef struct LNode

{

ElemType data;

LNode *next;

} LNode, *LinkList;

//链表初始化

bool InitList(LinkList &L)

{

L = new LNode;

if (L == NULL)

{

cout << “初始化失败!\n”;

return false;

}

L->next = NULL;

return 1;

}

void ClearList(LinkList &L)

{

LNode *temp = L, *p = L->next;

while (p != NULL)

{

temp = p;

p = p->next;

free(temp);

}

L->next = NULL;

}

//寻找合适的插入位置

bool LocatePosition(LinkList L, ElemType data, LNode *&pos)

{

LNode *pre = L, *p = L->next;

while (p != NULL && (p->data) < data)

{

pre = p;

p = p->next;

}

if (p == NULL || data < (p->data))

{ // 集合中不存在data或data小于p->data,需要将元素插入

pos = pre;

return true;

}

else

{ // 否则data等于p->data，不需要插入元素

pos = NULL;

return false;

}

}

//查看集合中有无此元素

bool FindNode(LinkList L, ElemType data)

{

LNode *p = L->next;

while (p != NULL && (p->data) != data)

{

p = p->next;

}

if (p == NULL)

return 0;

else

return 1;

}

//插入结点

bool InsertNode(LinkList &L, ElemType data)

{

LNode *p;

if (LocatePosition(L, data, p))

{

LNode *s = new LNode;

if (s == NULL)

{

cout << “初始化结点失败!\n”;

return 0;

}

s->data = data;

s->next = p->next;

p->next = s;

}

return 1;

}

//打印链表元素

void TraveList(LinkList L)

{

LNode *p = L->next;

if (p == NULL)

{

cout << “链表为空表!\n”;

}

else

{

while (p != NULL)

{

cout << p->data << ’ ';

p = p->next;

}

cout << endl;

}

}

//并集

void _Union(LinkList La, LinkList Lb, LinkList &Lc)

{

ClearList(Lc);

LNode *pa = La->next, *pb = Lb->next;

while (pa != NULL)

{

InsertNode(Lc, pa->data);

pa = pa->next;

}

while (pb != NULL)

{

InsertNode(Lc, pb->data);

pb = pb->next;

}

}

//交集

void _Intersection(LinkList La, LinkList Lb, LinkList &Lc)

{

ClearList(Lc);

LNode *pa = La->next, *pb = Lb->next;

while (pa != NULL)

{

if (FindNode(Lb, pa->data))

{ // a,b集合均出现的元素

InsertNode(Lc, pa->data);

}

pa = pa->next;

}

}

//差集

void _Difference(LinkList La, LinkList Lb, LinkList &Lc)

{

LinkList Ld; //暂存交集

InitList(Ld);

ClearList(Lc);

_Union(La, Lb, Lc);

_Intersection(La, Lb, Ld);

LNode *prc = Lc, *pc = Lc->next, *pd = Ld->next;

while (pc != NULL) // 用并集减交集

{

if (FindNode(Ld, pc->data))

{

LNode *temp = pc;

prc->next = pc->next;

pc = pc->next;

free(temp);

continue;

}

prc = pc; //前驱结点

pc = pc->next;

}

}

int main()

{

LinkList La, Lb, Lc; //Lc用来存储集合运算后的结果

InitList(La);

InitList(Lb);

InitList(Lc);

int n;

cout << “请输入要插入A集合的元素数：\n”;

cin >> n;

for (int i = 《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 1; i <= n; i++)

{

int ifo;

cin >> ifo;

InsertNode(La, ifo);

}

TraveList(La);

cout << “请输入要插入B集合的元素数：\n”;

cin >> n;

for (int i = 1; i <= n; i++)

{

int ifo;

cin >> ifo;

InsertNode(Lb, ifo);

}

TraveList(Lb);

cout << “\na,b集合的并集为：\n”;

_Union(La, Lb, Lc);

TraveList(Lc);

cout << “\na,b集合的交集为：\n”;

_Intersection(La, Lb, Lc);

TraveList(Lc);

cout << “\na,b集合的差集为：\n”;

_Difference(La, Lb, Lc);

TraveList(Lc);

return 0;

}

[](()第三章 栈和队列

---

[](()3-1.表达式求值

#include

using namespace std;

#define true 1

#define false 0

#define OPSETSIZE 8

typedef int Status;

unsigned char Prior[8][8] =

{ // 运算符优先级表

// ‘+’ ‘-’ ‘*’ ‘/’ ‘(’ ‘)’ ‘#’ ‘^’

/‘+’/ ‘>’, ‘>’, ‘<’, ‘<’, ‘<’, ‘>’, ‘>’, ‘<’,

/‘-’/ ‘>’, ‘>’, ‘<’, ‘<’, ‘<’, ‘>’, ‘>’, ‘<’,

/''*/ ‘>’, ‘>’, ‘>’, ‘>’, ‘<’, ‘>’, ‘>’, ‘<’,

/‘/’/ ‘>’, ‘>’, ‘>’, ‘>’, ‘<’, ‘>’, ‘>’, ‘<’,

/‘(’/ ‘<’, ‘<’, ‘<’, ‘<’, ‘<’, ‘=’, ’ ', ‘<’,

/‘)’/ ‘>’, ‘>’, ‘>’, ‘>’, ’ ', ‘>’, ‘>’, ‘>’,

/‘#’/ ‘<’, ‘<’, ‘<’, ‘<’, ‘<’, ’ ', ‘=’, ‘<’,

/‘^’/ ‘>’, ‘>’, ‘>’, ‘>’, ‘<’, ‘>’, ‘>’, ‘>’};

typedef struct StackChar

{

char c;

struct StackChar *next;

} SC; //StackChar类型的结点SC

typedef struct StackFloat

{

float f;

struct StackFloat *next;

} SF; //StackFloat类型的结点SF

SC *Push(SC *s, char c) //SC类型的指针Push，返回p

{

SC *p = (SC *)malloc(sizeof(SC));

p->c = c;

p->next = s;

return p;

}

SF *Push(SF *s, float f) //SF类型的指针Push，返回p

{

SF *p = (SF *)malloc(sizeof(SF));

p->f = f;

p->next = s;

return p;

}

SC *Pop(SC *s) //SC类型的指针Pop

{

SC *q = s;

s = s->next;

free(q);

return s;

}

SF *Pop(SF *s) //SF类型的指针Pop

{

SF *q = s;

s = s->next;

free(q);

return s;

}

float Operate(float a, unsigned char theta, float b) //计算函数Operate

{

switch (theta)

{

case ‘+’:

return a + b;

case ‘-’:

return a - b;

case ‘*’:

return a * b;

case ‘/’:

return a / b;

case ‘^’:

return pow(a, b);

default:

return 0;

}

}

char OPSET[OPSETSIZE] = {‘+’, ‘-’, ‘*’, ‘/’, ‘(’, ‘)’, ‘#’, ‘^’};

Status In(char Test, char *TestOp)

{

int Find = false;

for (int i = 0; i < OPSETSIZE; i++)

{

if (Test == TestOp[i])

Find = true;

}

return Find;

}

Status ReturnOpOrd(char op, char *TestOp)

{

for (int i = 0; i < OPSETSIZE; i++)

{

if (op == TestOp[i])

return i;

}

return false;

}

char precede(char Aop, char Bop)

{

return Prior[ReturnOpOrd(Aop, OPSET)][ReturnOpOrd(Bop, OPSET)];

}

float EvaluateExpression(char *MyExpression)

{

// 算术表达式求值的算符优先算法

// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合

SC *OPTR = NULL; // 运算符栈，字符元素

SF *OPND = NULL; // 运算数栈，实数元素

char TempData[20];

float Data, a, b;

char theta, *c, Dr[] = {‘#’, ‘\0’};

OPTR = Push(OPTR, ‘#’);

c = strcat(MyExpression, Dr);

strcpy(TempData, “\0”); //字符串拷贝函数

while (*c != ‘#’ || OPTR->c != ‘#’)

{

if (!In(*c, OPSET))

{

Dr[0] = *c;

strcat(TempData, Dr); //字符串连接函数

c++;