| 本人因为实验报告作业要写，上网查了许多文章发现没有C语言能跑的，还有些是错的，为了缓解广大网友的痛苦所以写了这篇C能跑的。过程真的很花时间很无语(ˉ▽ˉ；)...点点赞吧1. 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下： Typedef struct {int top[2],bot[2]; //栈顶和栈底指针 SElemType *V; //栈数组 int m; //栈最大可容纳元素个数 }DblStack #include
#include
#include
#define SElemType int
typedef struct
{
int top[2], bot[2];
SElemType* V;
int m;
}DblStack;
int Init(DblStack *s){
(*s).m = 10;
(*s).top[0] = -1;
(*s).bot[0] = 0;
(*s).top[1] = (*s).m;
(*s).bot[1] = (*s).m - 1;
(*s).V =(SElemType*)malloc(sizeof(SElemType) *(*s).m);
return 1;
}
int push(DblStack *s, int i, int x){
if (i 1) {
printf("栈号输入不对");
return 0; }
if ((*s).top[1] - (*s).top[0]==1){
printf("栈已满");
return 0;
}
switch (i){
case 0: (*s).V[++(*s).top[0]] = x;break;
case 1: (*s).V[--(*s).top[1]] = x;
}
return 0;
}
SElemType pop(DblStack (*s), int i) {
if (i 1) {
printf("栈号输入错误");
return 0;
}
switch (i) {
case 0: if ((*s).top[0] - 1top = -1;
}
int StackEmpty(SqStack S)
{
if (S.top == -1)
return 1;
else
return 0;
}
int Push(SqStack* S, char e)
{
if (S->top == StackSize - 1)
{
return 0;
}
S->top++;
S->data[S->top] = e;
return 1;
}
char Pop(SqStack* S)
{
if (S->top == -1)
return 0;
char e = S->data[S->top];
S->top--;
return e;
}
int JudgeHuiWen(char* str)
{
SqStack s;
InitStack(&s);
int i;
char temp;
int len = strlen(str);
for (i = 0; i base = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
if (!S->base)
return 0;
S->top = S->base;
S->stacksize = MAXSIZE;
return 1;
}
void InOutS(SqStack *S)
{
ElemType e;
int n;
if (InitStack(S))
printf("初始化成功\n");
printf("输入元素个数\n");
scanf("%d", &n);
printf("开始入栈");
for (int i = 0; i top - S->base == S->stacksize)
{
printf("栈满\n");
return ERROR;
}
*(S->top++) = e;
}
else
{
if (S->top == S->base)
{
printf("栈空\n");
return ERROR;
}
printf("%d ", *(--S->top));
printf("\n");
}
}
printf("全部出栈\n");
while (S->top!= S->base)
{
printf("%d ", --S->top);
}
return OK;
}
int main()
{
SqStack S;
InOutS(&S);
return 0;
}4. 从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、、/四种运算。例如：234 34+2$。#pragma warning(disable:4996)
#include
#include
// 操作数用链栈
typedef struct Node {
int data;
struct Node* next;
}SNode, * LinkStack;
void Init_int(LinkStack* L)
{
*L = NULL;
}
void Push_int(LinkStack* L, int e)
{
SNode* s = (SNode*)malloc(sizeof(SNode));
s->data = e;
s->next = *L;
*L = s;
}
void Pop_int(LinkStack* L, int* e)
{
SNode* p = *L;
if (*L == NULL)
{
printf("Pop int failuer!\n");
return;
}
*e = (*L)->data;
(*L) = (*L)->next;
free(p);
}
int GetTop_int(LinkStack L)
{
if (!L)
{
printf("GetTop int failuer!\n");
return;
}
return L->data;
}
int In(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/')
return 1;
else return 0;
}
int Opreate(int a, char ch, int b)
{
switch (ch)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return b / a;
}
}
int Polan()
{
char ch[10];
LinkStack OPND;
Init_int(&OPND);
scanf("%s", &ch);
while (ch[0] != '$')
{
if (!In(ch[0])) //In 函数为判断 字符 是否为操作符
{
Push_int(&OPND, atoi(ch)); //atoi()函数为 将字符串转化成Int型
}
else {
int a, b;
Pop_int(&OPND, &a);
Pop_int(&OPND, &b);
Push_int(&OPND, Opreate(a, ch[0], b));
}
scanf("%s", &ch);
}
return GetTop_int(OPND);
}
int main()
{
printf("=%d\n", Polan());
return 0;
}5. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack*);
void Push(SqStack*);
int JudgeLegal(SqStack*);
int main(int argc, char* argv[])
{
SqStack s;
InitStack(&s);
Push(&s);
int Flag = JudgeLegal(&s);
if (Flag) {
printf("The subsqence illegal!\n");
}
else {
printf("The subsquence legal!\n");
}
return 0;
}
//初始化栈
void InitStack(SqStack* s)
{
s->top = -1;
}
//入栈
void Push(SqStack* s)
{
ElemType x;
do {
scanf("%c", &x);
s->data[++s->top] = x;
} while (x != '\n');
}
//判断合法性
int JudgeLegal(SqStack* s)
{
int i = 0;
int j = 0;
int k = 0;
while (s->data[i] != '\0') {
switch (s->data[i]) {
case 'I':j++; break;
case 'O':k++; if (k > j) { return -1; }break;
}
i++;
}
if (j != k) {
return -1;
}
else {
return 0;
}
}6. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。#include
#include
#include
#define Datatype int
//先定义链队结构
typedef struct queuenode { //结点类型的定义
Datatype data;
struct queuenode* next;
} QueueNode;
typedef struct { //只设一个指向队尾元素的指针
QueueNode* rear;
}LinkQueue;
//置空队
void InitQueue(LinkQueue* Q)
{ //置空队：就是使头结点成为队尾元素
QueueNode* s;
Q->rear = Q->rear->next; //将队尾指针指向头结点
while (Q->rear != Q->rear->next) //当队列非空，将队中元素逐个出队
{
s = Q->rear->next;
Q->rear->next = s->next;
free(s); //回收结点空间
}
}
//判队空
int EmptyQueue(LinkQueue* Q)
{
return Q->rear->next == Q->rear; //判队空，当头结点的next指针指向自己时为空队
}
//入队
void EnQueue(LinkQueue *Q, Datatype x) //入队，也就是在尾节点 处插入元素
{
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); //申请新结点
p->data = x;
p->next = Q->rear->next; //初始化新结点并链入
Q ->rear->next = p;
Q->rear = p; //将尾指针移至新结点
}
// 出队
Datatype DeQueue(LinkQueue* Q) //出队，把头结点之后的元素摘下
{
QueueNode* p;
if (EmptyQueue(Q))
printf("Queue underflow");
p = Q->rear->next->next; //p指向将要摘下得结点
Datatype x = p->data; //保存结点中的数据
if (p == Q->rear) //当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
{
Q->rear = Q->rear->next; Q->rear->next = p->next;
}
else
Q->rear->next->next = p->next;
free(p); //摘下结点p
return x; //释放被删结点
}
int main() {
LinkQueue Q;
QueueNode q;
Q.rear = &q;
Q.rear->next=&q;
EnQueue(&Q, 1);
EnQueue(&Q, 2);
EnQueue(&Q, 3);
EnQueue(&Q, 4);
Datatype a=DeQueue(&Q);
Datatype b=DeQueue(&Q);
Datatype c=DeQueue(&Q);
printf("%2d%2d%2d", a, b, c);
return 0;
}7. 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。#include
#include
//创建循环队列
#define MAXQSIZE 50
typedef struct {
int* base;
int front;
int rear;
}SqQueue;
int tag;
//初始化
int InitQueue(SqQueue* q)
{
q->base = (int*)malloc(sizeof(int) * MAXQSIZE);
if (!q->base)
return 0;
q->front = q->rear = 0;
tag = 0;
return 1;
}
//入队
int EnQueue(SqQueue* Q, int e)
{
if (Q->rear % MAXQSIZE == Q->front && tag == 1)
return 0;
Q->base[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXQSIZE;
if (Q->front == Q->rear)
tag = 1;
return 1;
}
//出队
int DeQueue(SqQueue* Q)
{
int e;
if (Q->rear % MAXQSIZE == Q->front && tag == 0)
return 0;
e = Q->base[Q->front];
Q->front = (Q->front + 1) % MAXQSIZE;
if (Q->rear == Q->front)
tag = 0;
return e;
}
int main()
{
SqQueue Q;
InitQueue(&Q);
EnQueue(&Q, 2);
EnQueue(&Q, 1);
EnQueue(&Q, 3);
EnQueue(&Q, 7);
EnQueue(&Q, 10);
int a = 0;
for (int i = 0; i front = qu->rear = 0;// 队首和队尾指针重合并指向0
}
/* 入队（从队头插入） */
/* qu指的是要插入元素的队列；x指的是要插入的元素 */
int enQueue(SqQueue*qu, int x) {
if (qu->rear == (qu->front - 1 + maxSize) % maxSize) { // 如果队满，则不能入队
return 0;
}
else {
/* 注意：这里是先入队，再修改指针 */
qu->data[qu->front] = x;
qu->front = (qu->front - 1 + maxSize) % maxSize;
return 1;
}
}
/* 出队（从队尾出队）
/* qu指的是要出队的队列；&x指的是要存储出队元素的值 */
int deQueue(SqQueue* qu) {
if (qu->rear == qu->front) { // 如果队空，就不能出队了
return 0;
}
else {
/* 注意：这里是先入队，再修改指针 */
int x = qu->data[qu->rear];
qu->rear = (qu->rear - 1 + maxSize) % maxSize;
return 1;
}
}
/* 打印队列 */
void printQueue(SqQueue qu) {
printf("\n");
while (qu.rear != qu.front) {
qu.front = (qu.front + 1) % maxSize;
printf("%d\t", qu.data[qu.front]);
}
printf("\n");
}
int main() {
SqQueue qu;
initQueue(&qu);
int nums[] = { 1,2,3,4,5,6 };
int n = 6;
for (int i = 0; i next = NULL;
return OK;
}
//链表的取值
int AssigList(LinkList L)
{
LinkList p, t;
p = L;
int e, i, n = 0;
printf("请说明要插入几个元素\n");
scanf("%d", &i);
printf("请说明要输入的值：");
while (1)
{
scanf("%d", &e);
t = (LinkList)malloc(sizeof(LNode));
t->data = e;
t->next = NULL;
p->next = t;
p = t;
n++;
if (n == i)
break;
}
return OK;
}
//取最大值
Status MAX(LinkList L)
{
int a;
if (!L->next)
return L->data;
a = MAX(L->next);
return a >= L->data ? a : L->data;
}
//求结点
Status Length(LinkList L)
{
if (!L->next)
return 1;
else
return Length(L->next) + 1;
}
//求平均值
float Average(LinkList L, int n)
{
float b;
if (!L->next)
return L->data;
else
{
b = Average(L->next, n - 1);
return (b * (n - 1) + L->data) / n;
}
}
int main()
{
int a, n;
float b;
LinkList L;
InitList(&L);
AssigList(L);
a = MAX(L->next);
printf("输入的最大数是：%d\n", a);
a = Length(L->next);
n = a;
printf("结点的个数为：%d\n", a);
b = Average(L->next, n);
printf("所有元素的平均值为：%f\n", b);
return 0;
}
|