成都的设计院有哪些_找工程承包找哪个平台_给你一个网站seo如何做_四川网站推广公司

4. 栈

4.2. 链式栈

4.2.1. 特性

逻辑结构：线性结构
存储结构：链式存储结构
操作：创建，入栈，出栈，清空，获取

4.2.2. 代码实现

头文件 LinkStack.h

#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__
typedef int datatype;
typedef struct linkstack
{datatype data;struct linkstack *next;
} linkstack_t;
//1.创建一个空的栈
void createEmptyLinkStack(linkstack_t **ptop);
//2.入栈,ptop是传入的栈针的地址，data是入栈的数据
int pushLinkStack(linkstack_t **ptop, datatype data);
//3.判断栈是否为空
int isEmptyLinkStack(linkstack_t *top);
//4.出栈
datatype popLinkStack(linkstack_t **ptop);
//5.清空栈
void clearLinkStack(linkstack_t **ptop);
//6.求栈的长度
int lengthLinkStack(linkstack_t *top);
//7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针
datatype getTopLinkStack(linkstack_t *top);
#endif

1.创建一个空的栈

void createEmptyLinkStack(linkstack_t **ptop)
{*ptop = NULL;
}

2. 入栈

int pushLinkStack(linkstack_t **ptop, datatype data)
{// 定义一个指针pnew，指向新节点linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if(pnew == NULL){printf("New Node Creation Failed!!\n");return -1;}// 初始化pnew->data = data;pnew->next = *ptop;	// 新节点的指针域，指向旧节点的地址// 栈针移动到最新的节点*ptop = pnew;
}

3. 判断栈是否为空

int isEmptyLinkStack(linkstack_t *top)
{// 栈针指向NULL时，栈为空return top == NULL;
}

4. 出栈

datatype popLinkStack(linkstack_t **ptop)
{// 容错判断if (isEmptyLinkStack){printf("Stack is empty!!\n");return NULL;}// 定义指针pdel，指向出栈节点linkstack_t* pdel = NULL;// 定义中间变量，暂存出栈数据datatype data = 0;// pdel指向出栈节点pdel = *ptop;// data暂存出栈数据data = pdel->data;// 栈针移动，释放出栈节点*ptop = (*ptop)->next;free(pdel);pdel = NULL;// 返回出栈数据return data;
}

5. 清空栈

void clearLinkStack(linkstack_t **ptop)
{while(!isEmptyLinkStack(*ptop)){popLinkStack(ptop);}
}

6. 求栈的长度

int lengthLinkStack(linkstack_t *top)
{// 定义一个变量，作为长度的计数int len = 0;// 链式栈长度的计算实际上是无头单向链表的遍历问题while(top =  NULL){len ++;	// 累计计数top = top->next;	// 栈针移动}
}

7. 获取栈顶数据

datatype getTopLinkStack(linkstack_t *top)
{// 容错判断if (!isEmptyLinkStack(top)){printf("Stack is empty\n");return -1;}// 返回栈顶数据return top->data;
}

5. 队列

5.1. 特性

1. 一端只能输入，称为队尾；另一端只能输出，称为队头
2. 先进先出：FIFO
3. 存在假溢出现象：
   1）当数据存满后，有数据从队头出列后，应该可以存入新的数据，但是因为数据在队列里面不移动，所以队尾不存在空位，新数据无法入列，但是队列未满，如下图
   
   2）解决方法：顺序队列

5.2. 顺序队列（循环队列）

需要实现头和尾都可以走完最后一位之后再走回来，比如4->5->0->1。
方法一：

if(i==N)i = 0;
elsei++;

方法二：

i = (i+1)%N;

5.2.1. 代码实现

头文件 sequeue.h

#ifndef __SEQUEUE_H__
#define __SEQUEUE_H__
#define N 6
typedef int datatype;
typedef struct
{datatype data[N];//循环队列的数组int rear;//存数据端 rear 后面int front;//取数据端 front 前面
}sequeue_t;// 1. 创建一个空的队列
sequeue_t *createEmptySequeue();
// 2. 判断队列是否为满
int isFullSequeue(sequeue_t *p);
// 3. 入列 data代表入列的数据
int inSequeue(sequeue_t *p,datatype data);
// 4. 判断队列是否为空
int isEmptySequeue(sequeue_t *p);
// 5. 出列 
datatype outSequeue(sequeue_t *p);
// 6. 求队列的长度
int lengthSequeue(sequeue_t *p);
// 7. 清空队列函数
void clearSequeue(sequeue_t *p);
#endif

1. 创建一个空队列

sequeue_t *createEmptySequeue()
{// 申请空间存放队列结构sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if(p == NULL){printf("Space opening failure !!\n");return NULL;}// 初始化p->rear = 0;p->front = 0;return p;
}

2. 判断是否为满

int isFullSequeue(sequeue_t *p)
{// 循环队列的判满公式return p->front == (p->rear + 1) % N;
}

3. 入列

int inSequeue(sequeue_t *p, datatype data)
{// 容错判断if( isFullSequeue(p) ){printf("Space is Full !!\n");return -1;}// 入列p->data[p->rear] = data;// 队尾向后移动一个数据单位p->rear = (p->rear + 1) % N;return 0;
}

4. 判断是否为空

int isEmptySequeue(sequeue_t *p)
{// 空返回1，非空返回0return p->rear == p->front;
}

5. 出列

datatype outSequeue(sequeue_t *p)
{// 容错判断if ( isEmptySequeue(p) ){printf("Space is empty !!\n");return -1;}// 出列// 1）定义一个变量，暂存出列数据datatype data = p->data[p->front];// 2）队头移动p->front = (p->front + 1) % N;return data;
}

6. 求队列的长度

int lengthSequeue(sequeue_t *p)
{// 队尾可以大于队头，也可以小于队头// rear >= front, rear - front 是长度// rear < front, rear + N -front ,这种情况相当于，队尾套了队头一圈// 两种情况综合之后得到公式 ( rear + N - front ) % Nreturn ( p->rear - p->front + N ) % N;
}

+N 之后 %N 对结果来说，相当于没操作

7. 清空队列函数

void clearSequeue(sequeue_t *p)
{// p->front = p->rear;	// 不返回数据while(!isEmptySequeue(p))outSequeue(p);	// 可以返回出列数据， 看需求
}