C题目【2】
2020-05-05 本文已影响0人
全村滴希望
将字符串指定位置字符替换
例如：
输入： S1: bbadddd S2: ccc rep: 3
输出： bbcccdddd
思路：
线性表有两种表示方法：顺序存储表示和链式存储表示
顺序存储表示：用一组地址连续的存储单元依次存储线性表的数据元素。这种结构称为顺序表。（数组）
链式存储表示：用一组任意的存储单元存储线性表的数据元素，可以不连续。这种结构称为链表。（单链表）
顺序表和链表的比较：
| 性能 | 顺序表 | 链表 |
|---|---|---|
| 空间性能 | 必须预先分配空间，元素个数扩充受限，易造成空间浪费和空间溢出；存储密度大，结点空间利用率高。 | 不需要预先分配空间，内存空间允许，可以无限制创建元素个数；存储密度小，结点需要额外存储指针域，利用率低。 |
| 时间性能 | 指定任意位置序号即可取值，取值效率高；进行插入或删除操作时，平均要移动一般的结点，插入删除效率低。 | 只能从表头开始依次向后遍历，取值效率低；进行插入或删除操作时，无需移动数据，只需要修改指针，插入删除效率高。 |
基于此：
对于线性表的长度变化较大，宜采用链表，当变化较小，易于事先确定其大小，宜采用顺序表。
对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。
代码：
#include<stdio.h>
#include<string.h>
#include<malloc.h>
//构建结构体
typedef struct node
{
int data;
struct node *next;
} node;
//创建单链表
node* createList(char str[])
{
node *head, *tail, *p; //头指针、尾指针、工作指针
int len = strlen(str); //创建节点的个数
head = (node*)malloc(sizeof(node)); //创建头节点
head->data = str[0]; //头节点放数据
tail = head; //目前只有一个节点，尾指针指向头节点
for(int i=1; i<len; i++)
{
p = (node*)malloc(sizeof(node));//创建下一个节点
p->data = str[i]; //该节点放数据
tail->next = p; //链接该节点
tail = p; //尾指针指向该节点
}
tail->next = NULL; //节点末尾指向为空
return (head); //返回头节点即为返回整个链表
}
void main()
{
//1. 获取两个字符串
char str_1[100];
char str_2[100];
int rep,i=0;
printf("please input str_1：");
scanf("%s",&str_1);
printf("please input str_2：");
scanf("%s",&str_2);
printf("please input the replace num: ");
scanf("%d",&rep);
//
node *head_1= createList(str_1);
node *head_2= createList(str_2);
node *p = head_1;
node *q = head_2;
node *s;
//寻找字符串2的尾指针
node *tail_2;
while(q!=NULL)
{
tail_2=q;
q=q->next;
}
//寻找删除位置
while(i<rep-2)
{
p = p->next;
i++;
}
//删除
s=p->next;
p->next=s->next;
free(s);
//插入字符串2
tail_2->next=p->next;
p->next=head_2;
p = head_1; //工作指针指向头节点
while(p!=NULL) //工作指针指向内容不为空
{
printf("%c->",p->data); //打印
p = p->next; //工作指针后移，开始打印下一个节点
}
printf("\n");
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
//构建结构体
typedef struct node
{
int data;
struct node *next;
} node;
//创建单链表，这里使用后插法
node* createList(char str[])
{
node *head, *tail, *p; //头指针、尾指针、工作指针
int len = strlen(str); //创建节点的个数
head = (node*)malloc(sizeof(node)); //创建头节点
head->data = str[0]; //头节点放数据
tail = head; //目前只有一个节点，尾指针指向头节点
for(int i=1; i<len; i++)
{
p = (node*)malloc(sizeof(node));//创建下一个节点
p->data = str[i]; //该节点放数据
tail->next = p; //链接该节点
tail = p; //尾指针指向该节点
}
tail->next = NULL; //节点末尾指向为空
return (head); //返回头节点即为返回整个链表
}
//删除整个单链表
void deleteAllList(node* head)
{
node *p = head,*q; //p指针指向第一个节点
while(p!=NULL)
{
q=p->next; //先存放p的下一个节点
free(p); //释放p;
p=q; //从下一个节点继续
}
}
//打印单链表
void printList(node* head)
{
node *p = head; //工作指针指向头节点
while(p!=NULL) //工作指针指向内容不为空
{
printf("%c->",p->data); //打印
p = p->next; //工作指针后移，开始打印下一个节点
}
}
//删除结点
node* deleteNode(node* p, int rep) //这里不能写void类型，必须返回p指针
{
int i = 0;
node *s;
//寻找删除位置
while(i<rep-2)
{
p = p->next;
i++;
}
//删除结点
s=p->next;
p->next=s->next;
free(s);
return (p);
}
//插入单链表
void insertList(node* p, node* head_2, node* tail_2)
{
tail_2->next=p->next;
p->next=head_2;
}
void main()
{
//1. 获取两个字符串
char str_1[100];
char str_2[100];
int rep, i=0;
printf("please input str_1：");
scanf("%s",&str_1);
printf("please input str_2：");
scanf("%s",&str_2);
printf("please input the replace num: ");
scanf("%d",&rep);
//创建两个单链表
node *head_1= createList(str_1);
node *head_2= createList(str_2);
//声明并初始化三个工作指针
node *p = head_1;
node *q = head_2;
//寻找字符串2的尾指针
node *tail_2;
while(q!=NULL)
{
tail_2=q;
q=q->next;
}
//删除结点
p = deleteNode(p, rep);
//插入字符串2
insertList(p, head_2, tail_2);
//tail_2->next=p->next;
//p->next=head_2;
printList(head_1);
printf("\n");
deleteAllList(head_1);
printList(head_1);
}
单链表反转
输入一个链表，反转链表后，输出新链表的表头。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct ListNode
{
char data;
struct ListNode *next;
} ListNode;
ListNode* CreateList(char str[])
{
ListNode *head, *tail, *p;
int len = strlen(str);
head = (ListNode*)malloc(sizeof(ListNode));
head->data = str[0];
tail = head;
for(int i=1; i<len; i++)
{
p = (ListNode*)malloc(sizeof(ListNode));
p->data = str[i];
tail->next = p;
tail = p;
}
tail->next = NULL;
return (head);
}
void PrintList(ListNode* head)
{
ListNode *p = head;
while(p!=NULL)
{
printf("%c->",p->data);
p = p->next;
}
}
//反转单链表，从头节点开始为当前节点（head即为当前节点的工作指针）
//声明两个指针，一个next指向当前节点的下一个节点，一个pre指向当前节点的上一个节点
ListNode* ReverseList(ListNode* head)
{
if(head == NULL)
{
return NULL;
}
ListNode *next = NULL;
ListNode *pre = NULL;
while(head != NULL)
{
next = head->next;//保存下一个节点防止断链
head->next = pre;//当前节点指向上一个节点
pre = head;//pre指针和head指针后移
head = next;
}
return pre;
}
void main()
{
char str[100];
printf("please input str：");
scanf("%s",&str);
ListNode *head= CreateList(str);
ListNode *resHead = ReverseList(head);
PrintList(resHead);
printf("\n");
}
猴子选大王
/*
N 个猴子围成一个圈
1、从第一只猴子开始报数，第一只猴子报 1
2、每个报 2 的猴子退出，然后从下一只猴子重新开始报数，
3、要求输出退出的顺序和最后剩下的人
*/
思路
代码
#include<stdio.h>
#include<malloc.h>
//构建结构体
typedef struct node
{
int data;
struct node *next;
} node;
void main()
{
//获取猴子的个数
int n, i;
node *p,*pre_p,*tail;
printf("please input the monkey number:\n");
scanf("%d",&n);
// 构造循环单链表
p = (node*)malloc(sizeof(node));
p->data=1;
tail=p;
for(i=2; i<=n; i++) //构造N个节点
{
pre_p = (node*)malloc(sizeof(node));
pre_p->data = i;
tail->next = pre_p;
pre_p->next = p; //指向头节点
tail = pre_p; //尾指针后移
}
//开始循环，每次循环将第2只猴子出局
for(i=0; i<n; i++) //共有N个人，一共循环N次
{
p = p->next;
pre_p = pre_p->next;
if(i==n-1)
{
printf("%d号猴子----大王\n", p->data);
}
else
{
printf("%d号猴子----出局\n", p->data);
}
tail=p; //删除指针指向要被删除的节点
pre_p->next=p->next; //删除该节点
p=p->next; //p指针后移
free(tail); //释放该节点的存储空间
}
}
约瑟夫环
/*
约瑟夫环运作如下：
1、一群人围在一起坐成环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列，约瑟夫环结束
*/
思路
-
构建结构体
-
构造循环单链表
-
将p指针定位到开始报数的人K
-
开始循环，每次循环将第M的人出局(共有N个人，一共循环N次)
删除指针指向要被删除的节点
删除该节点
p指针后移并 释放该节点的存储空间
代码
#include<stdio.h>
#include<string.h>
#include<malloc.h>
//构建结构体
typedef struct node
{
int data;
struct node *next;
} node;
void main()
{
//获取n、k、m
int n,m,k;
int i,j;
node *p,*pre_p,*tail,*del;
printf("请输入N、K、M：\n");
scanf("%d%d%d",&n,&k,&m);
// 构造循环单链表
p = (node*)malloc(sizeof(node));
p->data=1;
tail=p;
for(i=2; i<=n; i++) //构造N个节点
{
pre_p = (node*)malloc(sizeof(node));
pre_p->data = i;
tail->next = pre_p;
pre_p->next = p; //指向头节点
tail = pre_p; //尾指针后移
}
//将p指针定位到开始报数的人K
for(i=0; i<k-1; i++)
{
p = p->next;
pre_p = pre_p->next;
}
//开始循环，每次循环将第M的人出局
for(i=0; i<n; i++) //共有N个人，一共循环N次
{
for(j=0; j<m-1; j++)
{
p = p->next;
pre_p = pre_p->next;
}
printf("%d号----出局\n", p->data);
del=p; //删除指针指向要被删除的节点
pre_p->next=p->next; //删除该节点
p=p->next; //p指针后移
free(del); //释放该节点的存储空间
}
}
顺序栈的基本操作
教科书规范：
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
#define OK 1
#define ERROR 0
typedef int StackType; //栈元素类型
typedef struct stack{
StackType *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
StackType *top; //栈顶指针, 指向栈顶元素的上一个位置
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//栈的初始化
int InitStack(SqStack *p) {
p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
if (p->base == NULL) return ERROR; //内存分配失败
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
return OK;
}
//判断栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return OK;
else return ERROR;
}
//顺序栈的压入
int Push(SqStack *p,StackType e) {
//插入元素e为新的栈顶元素
if ((p->top - p->base)>= p->stacksize) return ERROR; //栈满
*(p->top) = e;
(p->top)++;
return OK;
}
// 顺序栈的弹出
int Pop(SqStack *p,StackType *e) {
//若栈不空，则删除p的栈顶元素，用e返回其值
if (p->top == p->base) return ERROR;
--(p->top);
*e = *(p->top);
return OK;
}
//顺序栈的销毁
int DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
return OK;
}
//返回顺序栈的栈顶元素
int GetTop(SqStack *p, StackType *e) {
//若栈不为空，则用e返回p的栈顶元素
if (p->top > p->base)
{
*e = *(p->top - 1);
return OK;
}
else return ERROR;
}
//打印栈中元素
int printStack(SqStack *p)
{
if(p->top == p->base) return ERROR;
else
{
int i = 0;
while(i< (p->top - p->base))
printf("%d ", *(p->base + i++));
printf("\n");
return OK;
}
}
//测试栈的各种操作
void main() {
int n,i;
StackType *e,a;
e=(StackType*)malloc(sizeof(int)); //为指针e分配内存地址
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack); //初始化栈
if (EmptyStack(pstack)) printf("*** stack empty ***\n");
printf("please input the stack element number:");
scanf("%d", &n);
printf("please input the stack element: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a);
Push(pstack, a);
}
if (!EmptyStack(pstack)) printf("*** stack not empty ***\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
printf("the stack element has: \n");
printStack(pstack);
printf("***********************\n");
printf("please push the element: ");
scanf("%d", &a);
Push(pstack, a);
printf("***********************\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
GetTop(pstack, e);
printf("the top element of stack is: %d\n", *e);
printf("***********************\n");
printf("*** pop the element ***\n");
Pop(pstack, e);
printf("the element has poped is: %d\n", *e);
printf("********************\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
printf("*** stack destroy ***\n");
if (DestroyStack(pstack) == 0) printf("stack is destroied\n");
}
考试书写：
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
typedef struct stack{
int *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
int *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//栈的初始化
void InitStack(SqStack *p) {
p->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
}
//判断栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return 1;
else return 0;
}
//顺序栈的压入
void Push(SqStack *p,int e) {
*(p->top) = e;
(p->top)++;
}
// 顺序栈的弹出
int Pop(SqStack *p) {
--(p->top);
return *(p->top);
}
//顺序栈的销毁
void DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
//返回顺序栈的栈顶元素
int GetTop(SqStack *p) {
//若栈不为空，则用e返回p的栈顶元素
return *(p->top - 1);
}
//打印栈中元素
void printStack(SqStack *p) {
int i = 0;
while (i< (p->top - p->base))
printf("%d ", *(p->base + i++));
printf("\n");
}
//测试栈的各种操作
void main() {
int n,i;
int a;
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack); //初始化栈
if (EmptyStack(pstack)) printf("*** stack empty ***\n");
printf("please input the stack element number:");
scanf("%d", &n);
printf("please input the stack element: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a);
Push(pstack, a);
}
if (!EmptyStack(pstack)) printf("*** stack not empty ***\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
printf("the stack element has: \n");
printStack(pstack);
printf("***********************\n");
printf("please push the element: ");
scanf("%d", &a);
Push(pstack, a);
printf("***********************\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
printf("the top element of stack is: %d\n", GetTop(pstack));
printf("***********************\n");
printf("*** pop the element ***\n");
printf("the element has poped is: %d\n", Pop(pstack));
printf("********************\n");
printf("the stack element number is: %d\n", pstack->top - pstack->base);
printf("***********************\n");
printf("*** stack destroy ***\n");
DestroyStack(pstack);
}
输出单链表的第k个节点
输入一个链表，输出该链表中倒数第k个结点
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct ListNode
{
char data;
struct ListNode *next;
} ListNode;
ListNode* CreateList(char str[])
{
ListNode *head, *tail, *p;
int len = strlen(str);
head = (ListNode*)malloc(sizeof(ListNode));
head->data = str[0];
tail = head;
for(int i=1; i<len; i++)
{
p = (ListNode*)malloc(sizeof(ListNode));
p->data = str[i];
tail->next = p;
tail = p;
}
tail->next = NULL;
return (head);
}
ListNode* FindKthToTail(ListNode* head, int k)
{
ListNode *p = head;
ListNode *pre = head;
// 先将工作指针p向后移动k个节点
for(int i=0; i<k; i++)
{
p = p->next;
}
// 然后同时移动两个指针，直到末尾，此时pre指针指向倒数第k个节点
while(p != NULL)
{
p = p->next;
pre = pre->next;
}
return pre;
}
void main()
{
char str[100];
int k;
printf("please input str：");
scanf("%s",&str);
printf("please input k：");
scanf("%d",&k);
ListNode *head= CreateList(str);
ListNode *resNode = FindKthToTail(head, k);
if(resNode != NULL)
{
printf("kth to tail node is %c\n", resNode->data);
}
else
{
printf("Wrong input!\n");
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_INIT_SIZE 100
typedef struct ListNode
{
char data;
struct ListNode *next;
} ListNode;
ListNode* CreateList(char str[])
{
ListNode *head, *tail, *p;
int len = strlen(str);
head = (ListNode*)malloc(sizeof(ListNode));
head->data = str[0];
tail = head;
for(int i=1; i<len; i++)
{
p = (ListNode*)malloc(sizeof(ListNode));
p->data = str[i];
tail->next = p;
tail = p;
}
tail->next = NULL;
return (head);
}
typedef struct stack
{
int *base;
int *top;
int stacksize;
}SqStack;
void InitStack(SqStack *p)
{
p->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
p->top = p->base;
p->stacksize = STACK_INIT_SIZE;
}
void Push(SqStack *p,int e)
{
*(p->top) = e;
(p->top)++;
}
int Pop(SqStack *p)
{
--(p->top);
return *(p->top);
}
void DestroyStack(SqStack *p)
{
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
/*
思路：由于栈是先进后出，因此可以通过栈来实现单链表的倒数
*/
ListNode* FindKthToTail(ListNode* head, int k)
{
if(head == NULL)
{
return NULL;
}
ListNode *resNode = (ListNode*)malloc(sizeof(ListNode));
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack);
//遍历单链表，将单链表的每一个节点入栈，并计数
ListNode *tail = head;
int count = 0;
while(tail!=NULL){
Push(pstack, tail->data);
tail = tail->next;
count++;
}
//如果单链表节点个数小于k或者k为0，则返回空
if(count < k || k==0){
return NULL;
}
//出k-1次栈
for(int i=0; i<k-1; i++){
Pop(pstack);
}
//此时栈顶元素为倒数第k个节点，将出栈的值保存在结果节点。
resNode->data = Pop(pstack);
DestroyStack(pstack);
return resNode;
}
void main()
{
char str[100];
int k;
printf("please input str：");
scanf("%s",&str);
printf("please input k：");
scanf("%d",&k);
ListNode *head= CreateList(str);
ListNode *resNode = FindKthToTail(head, k);
if(resNode != NULL)
{
printf("kth to tail node is %c\n", resNode->data);
}
else
{
printf("Wrong input!\n");
}
}
括号匹配 1
检验表达式中所含括号是否正确匹配，如果匹配，则返回true，否则返回false，表达式以 “#” 结束
( ( [ ( ) ] ) ) ------- 合法
) ( [ [ ( ) ] ) ( ] ------- 不合法
思路
-
初始化一个空栈
-
设置标记性标量 flag，用来标记匹配结果以控制循环及返回结果，初始值为 true
-
遍历表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：
如果 ch 是左括号 “ [ ” 或 “ ( ”，则将其压入栈
如果 ch 是右括号 “ ) ”，则根据当前栈顶元素的值分情况考虑：如果栈非空且栈顶元素是 “ ( ”，则正确，否则错误
如果 ch 是右括号 “ ] ”，则根据当前栈顶元素的值分情况考虑：如果栈非空且栈顶元素是 “ [ ”，则正确，否则错误
-
退出循环后，如果栈空且flag值为true， 则匹配成功
代码
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
typedef struct stack{
char *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//顺序栈的初始化
void InitStack(SqStack *p) {
p->base = (char*)malloc(STACK_INIT_SIZE * sizeof(char));
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
}
//判断顺序栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return 1;
else return 0;
}
//顺序栈的压入
void Push(SqStack *p,char e) {
*(p->top) = e;
(p->top)++;
}
//顺序栈的弹出
char Pop(SqStack *p) {
--(p->top);
return *(p->top);
}
//顺序栈的销毁
void DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
//返回顺序栈的栈顶元素
char GetTop(SqStack *p) {
//若栈不为空，则用e返回p的栈顶元素
return *(p->top - 1);
}
//打印顺序栈中元素
void printStack(SqStack *p) {
int i = 0;
while (i< (p->top - p->base))
printf("%c ", *(p->base + i++));
printf("\n");
}
void main() {
//1.初始化一个空栈
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack);
//2.设置标记性标量 flag，用来标记匹配结果以控制循环及返回结果，初始值为 true
bool flag = true;
char ch, x;
scanf("%c", &ch);
//3.遍历表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作：
while(ch != '#' && flag)
{
switch(ch)
{
//如果 ch 是左括号 “ [ ” 或 “ ( ”，则将其压入栈
case '[': case '(':
Push(pstack, ch);
break;
//如果 ch 是右括号 “ ) ”，则判断：如果栈非空且栈顶元素是 “ ( ”，则正确，否则错误
case ')':
if(!EmptyStack(pstack) && GetTop(pstack)=='(')
{
x = Pop(pstack);
}
else
{
flag = false;
}
break;
//如果 ch 是右括号 “ ] ”，则判断：如果栈非空且栈顶元素是 “ [ ”，则正确，否则错误
case ']':
if(!EmptyStack(pstack) && GetTop(pstack)=='[')
{
x = Pop(pstack);
}
else
{
flag = false;
}
break;
}
scanf("%c", &ch);
}
//退出循环后，如果栈空且flag值为true， 则匹配成功
if(EmptyStack(pstack) && flag)
{
printf("This is legal\n");
}
else
{
printf("This is illegal\n");
}
DestroyStack(pstack);
}
括号匹配 2
题目描述:
在某个字符串（长度不超过 100）中有左括号，右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号，不能匹配的左括号用“”，“?”和空格组成，“
思路
-
初始化一个空栈
-
声明一个结果数组，用来记录每一个元素得到的匹配结果，位置顺序对应，并且声明count工作指针
-
遍历表达式，依次读入字符ch，如果表达式没有遍历完毕并且 flag 非零，则循环执行以下操作：
如果 ch 是左括号 " ( "，则将其压入栈，此 " ( " 有可能时不能被匹配的，所以先对应数组位置写入 “ $ ”
如果 ch 是右括号 " ) "，则根据当前栈顶元素的值分情况考虑：
如果栈非空且栈顶元素是 " ( "，说明该 " ) " 匹配成功，出栈并将当前元素位置放置空格。循环向前遍历，将遍历到的第一个 “ $ ” 改为空格。
如果栈空或者栈顶元素是 " ) ", 说明该 " ) " 匹配失败，将当前元素位置放置 “?”
如果ch是字母，则直接将当前元素位置放置空格
-
退出循环后，如果栈空且flag值为true，则匹配成功
代码
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
typedef struct stack{
char *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//顺序栈的初始化
void InitStack(SqStack *p) {
p->base = (char*)malloc(STACK_INIT_SIZE * sizeof(char));
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
}
//判断顺序栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return 1;
else return 0;
}
//顺序栈的压入
void Push(SqStack *p,char e) {
*(p->top) = e;
(p->top)++;
}
//顺序栈的弹出
char Pop(SqStack *p) {
--(p->top);
return *(p->top);
}
//顺序栈的销毁
void DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
//返回顺序栈的栈顶元素
char GetTop(SqStack *p) {
//若栈不为空，则用e返回p的栈顶元素
return *(p->top - 1);
}
void main() {
//1.初始化一个空栈
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack);
//2.声明结果数组，用来记录每一个元素得到的匹配结果，位置顺序对应，并且声明count工作指针
char res[100];
int res_len = 0;
int count = 0;
char ch, x;
scanf("%c", &ch);
//3.遍历表达式，依次读入字符ch，如果表达式没有扫描完毕，则循环执行以下操作：
while(ch != '#')
{
switch(ch)
{
//如果 ch 是左括号 “ ( ”，则将其压入栈，此 “ ( ” 有可能是不能被匹配的，所以先写入 ‘ $ ’
case '(':
Push(pstack, ch);
res[res_len] = '$';
break;
//如果 ch 是右括号 “ ) ”，则根据当前栈顶元素的值分情况考虑：
case ')':
//如果栈非空且栈顶元素是 “ ( ”，说明该右括号 “ ) ”匹配成功，出栈并将当前元素位置放置空格。
if(!EmptyStack(pstack) && GetTop(pstack)=='(')
{
x = Pop(pstack);
res[res_len] = ' ';
//循环向前遍历，将遍历到的第一个 ' $ ' 改为空格
count = res_len;
while(res[count]!='$')
count--;
res[count] = ' ';
}
//如果栈空或者栈顶元素不是 “ ( ”，说明说明该右括号 “ ) ”匹配失败，将当前元素位置放置 ' ? '
else
{
res[res_len] = '?';
}
break;
//如果 ch 是字母，则直接将当前元素位置放置空格
default:
res[res_len] = ' ';
break;
}
scanf("%c", &ch);
res_len++;
}
res[res_len] = '\0';
printf("%s\n", res);
DestroyStack(pstack);
}
合法出栈判断
【问题描述】对于一个栈，已知元素的进栈序列，判断一个由栈中所有元素组成的排列是否
是可能的出栈序列。
比如，进栈序列为 1 2 3 4，则可能的出栈序列有 4 3 2 1，1 4 3 2 等。而 1 4 2 3 就不
是。如果指定栈的容量为3，那么出栈序列 4 3 2 1也不是
【输入形式】从标准输入读取第一行是一个整数 N（3≤N≤10），代表有 N 个元素，其进栈
序列是 1 2 3 …… N。第二个整数M（2≤M≤10），代表栈的容量为 M 个空间。
第二行是空格分隔的 1~N 的数字的一个排列。
【输出形式】向标准输出打印结果。如果该排列是可能的出栈序列，则打印“YES”，
否则打印“NO”。在行末要输出一个回车符。
【输入样例】
please input the length of push sequence: 5
please input the capacity of the stack: 4
1 2 3 4 5
5 4 3 2 1
【输出样例】
NO
【样例说明】进栈序列为 1 2 3 4 5 ，栈容量为4 的出栈序列里没有 5 4 3 2 1
【评分标准】结果完全正确得 20 分，每个测试点 4 分。上传 c 语言源程序为 outstack.c。
思路
-
读入压栈序列，读入出栈序列
-
循环遍历，
如果栈为空 或者 栈顶元素小于当前出栈元素
如果当前栈的元素个数小于 M， 则入栈，否则栈空间有限，无法继续入栈如果栈顶元素等于当前出栈序列的元素，则出栈
如果栈顶元素大于当前出栈序列的元素，则返回错误
全部都可以出栈，则序列正确
代码
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
typedef struct stack{
int *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
int *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//顺序栈的初始化
void InitStack(SqStack *p) {
p->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
}
//判断顺序栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return 1;
else return 0;
}
//顺序栈的压入
void Push(SqStack *p,int e) {
*(p->top) = e;
(p->top)++;
}
//顺序栈的弹出
int Pop(SqStack *p) {
--(p->top);
return *(p->top);
}
//顺序栈的销毁
void DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
//返回顺序栈的栈顶元素
int GetTop(SqStack *p) {
//若栈不为空，则用e返回p的栈顶元素
return *(p->top - 1);
}
//打印顺序栈中元素
void printStack(SqStack *p) {
int i = 0;
while (i< (p->top - p->base))
printf("%d ", *(p->base + i++));
printf("\n");
}
void main() {
SqStack *pstack,stack;
pstack = &stack;
InitStack(pstack);
int N, M;
printf("please input the length of push sequence: ");
scanf("%d",&N);
printf("please input the capacity of the stack: ");
scanf("%d",&M);
int push[50];
int pop[50];
//读入压栈序列
for (int i = 0; i < N; i++)
{
scanf("%d", &push[i]);
}
//读入出栈序列
for (int j = 0; j < N; j++)
{
scanf("%d", &pop[j]);
}
i = j = 0;
while(j < N)
{
//如果栈为空 或者 栈顶元素小于当前出栈序列元素
if ( EmptyStack(pstack) || GetTop(pstack) < pop[j])
{
//如果当前栈的元素个数小于 M， 则入栈
if(pstack->top - pstack->base < M)
{
Push(pstack, push[i]);
i++;
}
//栈空间有限，无法继续入栈
else
{
printf("NO, stack capacity is not enough\n");
break;
}
}
//如果栈顶元素等于当前出栈序列的元素，则出栈
if(GetTop(pstack) == pop[j])
{
Pop(pstack);
j++;
}
//如果栈顶元素大于当前出栈序列的元素，则返回错误
else if(GetTop(pstack) > pop[j])
{
printf("NO, sequence illegal\n");
break;
}
}
if (j == N) printf("YES\n"); //全部都可以出栈(目前栈空)，则序列正确
DestroyStack(pstack);
}
堆栈的应用-表达式求值
题目描述：读入一个只包含 +，-，*，/的非负整数字符串计算表达式，计算该表达式的值。
输入：
测试输入包含若干测试用例，每个测试用例占一行，每行不超过 200 个字符，没有非法表达式。用 # 结束
输出：
对每个测试用例输出 1 行，即表达式的值。
样例输出：
3 * 4 - 5 #
样例输出：
7
思路
-
初始化OPTR栈和OPND栈，将表达式起始符 " # "压入OPTR栈。
-
遍历表达式，读入第一个字符ch，如果表达式没有扫面完毕至 “ # ” 或OPTR的栈顶元素不为 “ # ” 时，则循环执行以下操作：
如果 ch 不是运算符，则压入OPND栈，读入下一个字符 ch ；
如果 ch 是运算符，则根据OPTR的栈顶元素和 ch 的优先级比较结果，做不同的处理： 如果小于，则 ch 压入OPTR栈，读入下一个字符 ch； 如果大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈。 如果等于，则OPTR的栈顶元素是 “ ( ” 且 ch 是 “ ) ”，这时弹出OPTR栈顶的 “ ( ”，相当于括号匹配成功，然后读入下一字符 ch -
OPND栈顶元素即为表达式求职结果，返回此元素。
代码
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//栈的容量（最大元素个数）
typedef struct stack{
char *base; //栈底指针，在构造之前和销毁之后，base的值为NULL
char *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack; //顺序栈
//顺序栈的初始化
void InitStack(SqStack *p) {
p->base = (char*)malloc(STACK_INIT_SIZE * sizeof(char));
p->top = p->base; //栈顶与栈底相同表示一个空栈
p->stacksize = STACK_INIT_SIZE;
}
//判断顺序栈是否为空
int EmptyStack(SqStack *p) {
//若为空栈 则返回OK，否则返回ERROR
if (p->top == p->base) return 1;
else return 0;
}
//顺序栈的压入
void Push(SqStack *p,char e) {
*(p->top) = e;
(p->top)++;
}
//顺序栈的弹出
char Pop(SqStack *p) {
--(p->top);
return *(p->top);
}
//顺序栈的销毁
void DestroyStack(SqStack *p) {
//释放栈底空间并置空
free(p->base);
p->base = NULL;
p->top = NULL;
p->stacksize = 0;
}
//返回顺序栈的栈顶元素
char GetTop(SqStack *p) {
//若栈不为空，则用e返回p的栈顶元素
return *(p->top - 1);
}
//打印顺序栈中元素
void printStack(SqStack *p) {
int i = 0;
while (i< (p->top - p->base))
printf("%c ", *(p->base + i++));
printf("\n");
}
//判定字符是否为运算符
int IsOptr(char ch)
{
if(ch<'0' || ch>'9')
return 1;
else
return 0;
}
//判定两个字符的优先级关系
char Precede( char optr_1, char optr_2 )
{
/*
优先级矩阵，若 mat[i][j] == >, 则表示 i 号运算符优先级大于 j
号运算符，运算符编码规则为+为 0 号，-为 1 号，*为 2 号，/为 3 号，
(为 4 号，) 为 5 号， # 为6 号。
*/
const char mat[7][7] = {
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', 'E',
'>', '>', '>', '>', 'E', '>', '>',
'<', '<', '<', '<', '<', 'E', '='
};
int i=0, j=0;
//此处出现重复代码，原则上应该再写一个函数
//但是考试时【功能类函数】太多的话，这种目的是节省代码行数的函数可以不写
switch(optr_1)
{
case '+':
i = 0;
break;
case '-':
i = 1;
break;
case '*':
i = 2;
break;
case '/':
i = 3;
break;
case '(':
i = 4;
break;
case ')':
i = 5;
break;
case '#':
i = 6;
break;
}
switch(optr_2)
{
case '+':
j = 0;
break;
case '-':
j = 1;
break;
case '*':
j = 2;
break;
case '/':
j = 3;
break;
case '(':
j = 4;
break;
case ')':
j = 5;
break;
case '#':
j = 6;
break;
}
return mat[i][j];
}
//二元运算函数
char Operate( char opnd_a, char optr, char opnd_b )
{
int a = opnd_a -'0';
int b = opnd_b -'0';
int res = 0;
switch(optr)
{
case '+':
res = a+b;
break;
case '-':
res = a-b;
break;
case '*':
res = a*b;
break;
case '/':
res = a/b;
}
return res+'0';
}
void main() {
//初始化OPTR栈和OPND栈，将表达式起始符 " # "压入OPTR栈。
SqStack *optr,optr_stack;
optr = &optr_stack;
InitStack(optr);
SqStack *opnd,opnd_stack;
opnd = &opnd_stack;
InitStack(opnd);
Push(optr, '#');
char ch;
char theta, a, b, x;
scanf("%c", &ch);
//遍历表达式，读入第一个字符ch，如果表达式没有扫面完毕至 “ # ” 或OPTR的栈顶元素不为 “ # ” 时，则循环执行以下操作：
while(ch!='#' || GetTop(optr)!='#')
{
//如果 ch 不是运算符，则压入OPND栈，读入下一个字符 ch ；
if(!IsOptr(ch))
{
Push(opnd, ch);
scanf("%c", &ch);
}
//如果 ch 是运算符，则根据OPTR的栈顶元素和 ch 的优先级比较结果，做不同的处理：
else
{
switch(Precede(GetTop(optr), ch))
{
//如果小于，则 ch 压入OPTR栈，读入下一个字符 ch；
case '<':
Push(optr, ch);
scanf("%c", &ch);
break;
//如果大于，则弹出OPTR栈顶的运算符，从OPND栈弹出两个数，进行相应运算，结果压入OPND栈。
case '>':
theta = Pop(optr);
b = Pop(opnd);
a = Pop(opnd);
Push(opnd, Operate(a, theta, b));
break;
//如果等于，则OPTR的栈顶元素是 “ ( ” 且 ch 是 “ ) ”，这时弹出OPTR栈顶的 “ ( ”，相当于括号匹配成功，然后读入下一字符 ch
case '=':
x = Pop(optr);
scanf("%c", &ch);
break;
}
}
}
//OPND栈顶元素即为表达式求职结果，返回此元素。
if(GetTop(opnd)>'0' && GetTop(opnd)<'9')
{
printf("the reult is %c\n", GetTop(opnd));
}
else
{
printf("the reult is %d\n", GetTop(opnd)-'0');
}
DestroyStack(opnd);
DestroyStack(optr);
}
二叉树的基本操作
#include<stdio.h>
#include<stdlib.h>
//二叉树的二叉链表存储表示
typedef struct BiTNode{
char data; //结点的数据域
struct BiTNode *lChild; //结点的左子树
struct BiTNode *rChild; //结点的右子树
}BiTNode;
//先序遍历的顺序建立二叉链表
BiTNode* BiTreeCreate(BiTNode *T)
{//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
scanf("%c", &ch);
if (ch == '#') T = NULL;
else
{
T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = ch;
T->lChild = BiTreeCreate(T->lChild);
T->rChild = BiTreeCreate(T->rChild);
}
return T;
}
//先序遍历的顺序建立二叉链表
void BiTreeCreate(BiTNode **T)
{//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
scanf("%c", &ch);
if (ch == '#') *T = NULL;
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode));
(*T)->data = ch;
BiTreeCreate(&(*T)->lChild);
BiTreeCreate(&(*T)->rChild);
}
}
//计算二叉树的深度
int BiTreeDepth(BiTNode *T)
{
int lChildDepth = 0;
int rChildDepth = 0;
//如果是空树，深度为0，递归结束
if (T == NULL) return 0;
else
{
lChildDepth = BiTreeDepth(T->lChild); //递归计算左子树的深度
rChildDepth = BiTreeDepth(T->rChild); //递归计算右子树的深度
//二叉树的深度为左子树深度与右子树深度较大者加1
return (lChildDepth > rChildDepth) ? (lChildDepth + 1):(rChildDepth + 1);
}
}
//统计二叉树中结点的个数
int BiTreeNodeCount(BiTNode *T)
{
//如果是空树，则结点个数为0
if (T == NULL) return 0;
//否则结点个数为左子树的结点个数 + 右子树的结点个数
else return BiTreeNodeCount(T->lChild) + BiTreeNodeCount(T->rChild) + 1;
}
//统计二叉树中叶子结点的个数
int BiTreeLeafCount(BiTNode *T)
{
//如果是空树，则叶子结点个数为0
if (T == NULL) return 0;
//如果树不空，但是左子树和右子树都为空，则叶子结点个数为1
else if(T->lChild == NULL && T->rChild == NULL) return 1;
//否则结点个数为左子树的叶子结点个数 + 右子树的叶子结点个数
else return BiTreeLeafCount(T->lChild) + BiTreeLeafCount(T->rChild);
}
//先序遍历二叉树
void PreOrderTraverse(BiTNode *T)
{
//如果是空树，直接返回
if (T == NULL) return;
//否则先访问根节点，再先序遍历左子树，最后先序遍历右子树
else
{
printf("%c ", T->data);
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}
//中序遍历二叉树
void InOrderTraverse(BiTNode *T)
{
//如果是空树，直接返回
if (T == NULL) return;
//否则先中序遍历左子树，然后访问根节点，最后中序遍历右子树
else
{
InOrderTraverse(T->lChild);
printf("%c ", T->data);
InOrderTraverse(T->rChild);
}
}
//后序遍历二叉树
void PostOrderTraverse(BiTNode *T)
{
//如果是空树，直接返回
if (T == NULL) return;
//否则先后序遍历左子树，然后后序遍历右子树，最后访问根节点
else
{
PostOrderTraverse(T->lChild);
PostOrderTraverse(T->rChild);
printf("%c ", T->data);
}
}
//遍历叶子结点
void LeafNodeTraverse(BiTNode *T)
{
//如果是空树，直接返回
if (T == NULL) return;
//如果树不空，但是左子树和右子树都为空，则访问叶子节点
else if(T->lChild == NULL && T->rChild == NULL) printf("%c ", T->data);
//否则先遍历左子树的叶子节点，再遍历右子树的叶子结点
else
{
LeafNodeTraverse(T->lChild);
LeafNodeTraverse(T->rChild);
}
}
//左结点插入
BiTNode* BitreeInsertLeftNode(BiTNode *T, char ch)
{
BiTNode *temp;
if (T != NULL)
{
BiTNode *new_N = NULL;
new_N = (BiTNode *)malloc(sizeof(BiTNode)); //结点分配内存空间
new_N->data = ch; //结点放置数据
new_N->rChild = NULL; //结点右子树置为NULL
//将结点左子树接入T的左子树，结点称为T新的左子树
temp = T->lChild;
new_N->lChild = temp;
T->lChild = new_N;
}
return T;
}
//右结点插入
BiTNode* BitreeInsertRightNode(BiTNode *T, char ch)
{
BiTNode *temp;
if (T != NULL)
{
BiTNode *new_N = NULL;
new_N = (BiTNode *)malloc(sizeof(BiTNode)); //结点分配内存空间
new_N->data = ch; //结点放置数据
new_N->lChild = NULL; //结点左子树置为NULL
//将结点左子树接入T的左子树，结点称为T新的左子树
temp = T->rChild;
new_N->rChild = temp;
T->rChild = new_N;
}
return T;
}
//查找结点
BiTNode* BiTreeSearch(BiTNode *T, char ch)
{
//如果是空树，递归结束
if(T == NULL) return NULL;
//如果查找到该结点，返回该结点指针
else if(T->data == ch) return T;
else
{
//查找左子树，如果查找到了，返回左子树的结果
if( BiTreeSearch(T->lChild, ch)!=NULL)
return BiTreeSearch(T->lChild, ch);
//否则返回左子树的结果
else
return BiTreeSearch(T->rChild, ch);
}
}
//复制二叉树
BiTNode* BiTreeCopy(BiTNode *T, BiTNode *new_T)
{
//如果是空树，递归结束
if(T == NULL) new_T = NULL;
else
{
new_T = (BiTNode *)malloc(sizeof(BiTNode));
new_T->data = T->data; //复制根节点
new_T->lChild = BiTreeCopy(T->lChild, new_T->lChild); //递归复制左子树
new_T->rChild = BiTreeCopy(T->rChild, new_T->rChild); //递归复制右子树
}
return new_T;
}
//销毁二叉树
void BiTreeDestroy(BiTNode **T)
{
//如果是空树，递归结束
if(*T == NULL) return;
else
{
BiTreeDestroy(&(*T)->lChild); //销毁左子树
BiTreeDestroy(&(*T)->rChild); //销毁右子树
free(*T); //释放内存
*T = NULL; //指针置NULL
}
}
//删除左子树
void LChildDestroy(BiTNode **T)
{
//如果是空树，递归结束
if(*T == NULL) return;
else
{
BiTreeDestroy(&(*T)->lChild);
(*T)->lChild = NULL;
}
}
//删除右子树
void RChildDestroy(BiTNode **T)
{
//如果是空树，递归结束
if(*T == NULL) return;
else
{
BiTreeDestroy(&(*T)->rChild);
(*T)->rChild = NULL;
}
}
void main()
{
//先序遍历的顺序建立二叉树
printf("PreOrder create the tree, '#'means no child\n");
BiTNode *T = NULL;
T = BiTreeCreate(T);
//计算二叉树的深度
printf("The bitree depth: %d\n", BiTreeDepth(T));
//统计二叉树中结点的个数
printf("The bitree node count: %d\n", BiTreeNodeCount(T));
//统计二叉树中叶子结点的个数
printf("The bitree leaf count: %d\n", BiTreeLeafCount(T));
//先序遍历二叉树
printf("PreOrder traverse bitree: \n");
PreOrderTraverse(T);
printf("\n");
//中序遍历二叉树
printf("InOrder traverse bitree: \n");
InOrderTraverse(T);
printf("\n");
//后序遍历二叉树
printf("PostOrder traverse bitree: \n");
PostOrderTraverse(T);
printf("\n");
//遍历叶子结点
printf("LeafNode traverse: \n");
LeafNodeTraverse(T);
printf("\n");
//左结点插入
printf("Insert the left node: ");
char ch;
fflush(stdin);
scanf("%c", &ch);
T = BitreeInsertLeftNode(T, ch);
//中序遍历插入左结点的二叉树
printf("InOrder traverse insert left node bitree: \n");
InOrderTraverse(T);
printf("\n");
//右结点插入
printf("Insert the right node: ");
fflush(stdin);
scanf("%c", &ch);
T = BitreeInsertRightNode(T, ch);
//中序遍历插入右节点的二叉树
printf("InOrder traverse insert right node bitree: \n");
InOrderTraverse(T);
printf("\n");
//查找结点
printf("Search the node in BiTree: ");
fflush(stdin);
scanf("%c", &ch);
BiTNode *E = NULL;
E = BiTreeSearch(T, ch);
if(E!=NULL)
printf("The result of search is: %c\n", E->data);
else
printf("Could not find it! \n");
//free(E) 不可以释放该节点
//复制二叉树
printf("copy T bitree to new_T bitree \n");
BiTNode *new_T = NULL;
new_T = BiTreeCopy(T, new_T);
//中序遍历复制后的二叉树
printf("InOrder traverse new bitree: \n");
InOrderTraverse(new_T);
printf("\n");
//销毁二叉树
BiTreeDestroy(&T);
BiTreeDestroy(&new_T);
}
哈夫曼树（Huffman）
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 6
typedef struct HTNode
{
int weight; //哈夫曼树中结点的权值
struct HTNode *lChild;
struct HTNode *rChild;
}HTNode;
//创建哈夫曼树
HTNode* HTreeCreate(int arr[])
{
HTNode *ptrArr[LENGTH]; //指针数组中存放指向森林中每个树的根结点的指针
HTNode *ptr, *T=NULL;
for(int i=0; i<LENGTH; i++)
{//将参数数组的每一个元素转化为结构体，作为森林中的每一棵树
ptr = (HTNode *)malloc(sizeof(HTNode));
ptr->weight = arr[i];
ptr->lChild = ptr->rChild = NULL;
ptrArr[i] = ptr; //指针数组当前元素存放当前指针
}
for(i=1; i<LENGTH; i++)
{//进行 n-1 次循环建立哈夫曼树
int k1 = -1, k2; //k1表示当前森林中具有最小权值的树根结点的下标,k2为次最小的下标
for(int j=0; j<LENGTH; j++)
{//将 k1 和 k2 两个下标【重新赋予】当前指针数组不为空的元素位置
if(ptrArr[j] != NULL && k1==-1)
{
k1 = j;
continue;
}
if(ptrArr[j] != NULL)
{
k2 = j;
break;
}
}
for(j=k2; j<LENGTH; j++)
{//将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
if(ptrArr[j] != NULL)
{
if(ptrArr[j]->weight < ptrArr[k1]->weight)
{//如果 j 下标存储的根结点 小于 k1下标存储的根结点，说明找到比k1小的根结点
k2 = k1;
k1 = j;
}
else if(ptrArr[j]->weight < ptrArr[k2]->weight)
{//再不比k1小，再判断如果j 下标存储的根结点 < k2下标存储的根结点，说明找到比k1大但是比k2小的根结点
k2 = j;
}
}
}
//得到权值最小的和次最小的根结点指针，开始构造新的树
T = (HTNode *)malloc(sizeof(HTNode));
T->weight = ptrArr[k1]->weight + ptrArr[k2]->weight;
T->lChild = ptrArr[k1]; //权值最小的根结点作为左子树
T->rChild = ptrArr[k2]; //权值最小的根结点作为右子树
//将新的树的根结点指针覆盖指针数组中k1的位置，k2位置置空
ptrArr[k1] = T;
ptrArr[k2] = NULL;
}
return T;
}
//中序遍历哈夫曼树的结点
void InOrderTraverse(HTNode *T)
{
if (T == NULL) return;
else
{
InOrderTraverse(T->lChild);
printf("%d ", T->weight);
InOrderTraverse(T->rChild);
}
}
//打印哈夫曼树中某个结点的左右孩子结点。如果是叶子结点，那么直接打印权值
void HTNodeInfo(HTNode *T)
{
if(T->lChild == NULL && T->rChild == NULL)
printf("\nThe %d is the leaf node in the Huffman tree \n", T->weight);
if(T->lChild != NULL)
printf("\nThe left child node of %d in the Huffman tree is %d\n", T->weight, T->lChild->weight);
if(T->rChild != NULL)
printf("\nThe right child node of %d in the Huffman tree is %d\n", T->weight, T->rChild->weight);
}
//先序打印哈夫曼树的结点
void PreOrderTraverse(HTNode *T)
{
if (T == NULL) return;
else
{
HTNodeInfo(T);
PreOrderTraverse(T->lChild);
PreOrderTraverse(T->rChild);
}
}
//计算哈夫曼树带权路径长度WPL
int HTreeWeightLength(HTNode *T, int len)
{
if (T == NULL) return 0;
else
{
if(T->lChild==NULL && T->rChild==NULL)
{//如果是叶子结点，直接返回 权值 * 路径长度
return T->weight * len;
}
else
{//如果不是叶子结点，那么返回 左子树的带权路径长度 + 右子树的带权路径长度
return HTreeWeightLength(T->lChild, len+1) + HTreeWeightLength(T->rChild, len+1);
}
}
}
//哈夫曼树编码(叶子节点按中序方式依次打印其编码)
void HuffmanCoding(HTNode *T, int len)
{
//静态局部变量相当于全局变量(只是只有在这个函数中能访问,但是生命周期是和全局变量差不多的)函数退出之后变量还在,而且只在第一次进入的时候做初始化,以后会跳过初始化语句,保留原来的值
static int arr[20]; //不用static 也可以写在所有函数的外面
if (T != NULL)
{
if(T->lChild==NULL && T->rChild==NULL)
{//如果是叶子结点，直接循环打印数组
printf("Encoding with a node weight of %d: ", T->weight);
for(int i=0; i<len; i++)
{
printf("%d", arr[i]);
}
printf("\n");
}
else
{//如果不是叶子结点
//数组当前位置(路径长度作为下标)先放置0，再递归左子树
//数组当前位置(路径长度作为下标)先放置1，再递归右子树，
arr[len] = 0;
HuffmanCoding(T->lChild, len+1);
arr[len] = 1;
HuffmanCoding(T->rChild, len+1);
}
}
}
void main()
{
int arr[] = {3, 9, 5, 12, 6, 15};
HTNode *T = NULL;
T = HTreeCreate(arr);
printf("******** InOrderTraverse Huffman tree ********\n");
InOrderTraverse(T);
printf("\n\n");
printf("******** PreOrderTraverse Huffman node relation ********\n");
PreOrderTraverse(T);
printf("\n");
printf("******** calculate Huffman tree weight length ********\n");
printf("HTreeWeightLength = %d\n", HTreeWeightLength(T, 0));
printf("\n");
printf("******** Huffman code each node ********\n");
HuffmanCoding(T, 0);
}
层序遍历、先序遍历、中序遍历、后序遍历的非递归算法
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
public static void main(String[] args){
TreeNode root = new TreeNode(4);
TreeNode left = new TreeNode(2);
TreeNode leftLeft = new TreeNode(1);
TreeNode leftRight = new TreeNode(3);
TreeNode right = new TreeNode(6);
TreeNode rightLeft = new TreeNode(5);
TreeNode rightRight = new TreeNode(7);
root.left = left;
root.right = right;
left.left = leftLeft;
left.right = leftRight;
right.left = rightLeft;
right.right = rightRight;
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList = SequenceTraversal(root);
System.out.println("SequenceTraversal: "+arrayList.toString());
arrayList = PreOrderTraversal(root);
System.out.println("PreOrderTraversal: "+arrayList.toString());
arrayList = InOrderTraversal(root);
System.out.println("InOrderTraversal: "+arrayList.toString());
arrayList = PostOrderTraversal(root);
System.out.println("PostOrderTraversal: "+arrayList.toString());
}
public static ArrayList<Integer> SequenceTraversal(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
if(root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
while(!deque.isEmpty()){
TreeNode treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
if(treeNode.left != null) deque.offerLast(treeNode.left);
if(treeNode.right !=null) deque.offerLast(treeNode.right);
}
return arrayList;
}
public static ArrayList<Integer> PreOrderTraversal(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
while(!deque.isEmpty()){
TreeNode treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
if(treeNode.right !=null) deque.offerFirst(treeNode.right);
if(treeNode.left != null) deque.offerFirst(treeNode.left);
}
return arrayList;
}
public static ArrayList<Integer> InOrderTraversal(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
TreeNode treeNode = root;
while(treeNode!=null || !deque.isEmpty()){
if(treeNode != null){
deque.offerFirst(treeNode);
treeNode = treeNode.left;
}else{
treeNode = deque.pollFirst();
arrayList.add(treeNode.val);
treeNode = treeNode.right;
}
}
return arrayList;
}
public static ArrayList<Integer> PostOrderTraversal(TreeNode root) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (root == null) return arrayList;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerLast(root);
TreeNode preTreeNode = null;
while(!deque.isEmpty()){
TreeNode treeNode = deque.peekFirst();
if((treeNode.left==null&&treeNode.right==null) ||
(treeNode!=null && (preTreeNode==treeNode.left || preTreeNode==treeNode.right))){
arrayList.add(treeNode.val);
preTreeNode = deque.pollFirst();
}else{
if(treeNode.right != null)
deque.offerFirst(treeNode.right);
if(treeNode.left != null)
deque.offerFirst(treeNode.left);
}
}
return arrayList;
}
}
排序
#include <stdio.h>
#define LENGTH 10
void ShellSort(int *arr, int len)
{
int i,j, temp, gap;
for (gap = len / 2; gap >= 1; gap /= 2) { // 初始化步长为数组长度的一半，每次遍历后步长减半
//对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
for (i = 0 + gap; i < len; i += gap) { //初始化i为后一个元素
temp = arr[i]; //先把arr[i]位置空出来
j = i - gap; //j初始化为i的前一个元素（与i相差gap长度）
while (j >= 0 && arr[j] > temp) {
arr[j + gap] = arr[j]; //将在a[i]前且比temp的值大的元素向后移动一位
j = j - gap;
}
arr[j + gap] = temp;
}
}
}
void BubbleSort(int *arr, int len)
{
int i, j, temp;
for(i=0; i<len-1; i++)
{//冒泡排序只需要操作len-1个元素
for(j=0; j<len-1-i; j++)
{//遍历一遍每一对相邻元素，所以时间复杂度比较高
if(arr[j] > arr[j+1])
{//这里是从小到大排序，如果前面的大于后面的，那么向后冒泡，交换元素
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void QuickSort(int *arr, int left, int right)
{
if(left>=right) return; //如果左边索引大于或者等于右边的索引就代表已经完成左边或者右边这组元素的一趟分隔了
int i=left;
int j=right;
int key=arr[i]; //保存基准值，这时可以理解arr[i]的位置空了
while(i<j) //操作边界控制
{
while(i<j&&key<=arr[j]) //从后向前找比基准值小的，如果比基准值大那么继续向前
j--;
arr[i]=arr[j]; //退出while循环说明已经找到比基准值小的，发生交换，可以理解将arr[j]放在空的arr[i]位置
//此时可以理解为arr[j]的位置空了
while(i<j&&key>=arr[i]) //发生交换后开始 从前向后找比基准值大的，如果比基准值小那么继续向后
i++;
arr[j]=arr[i]; //退出while循环说明已经找到比基准值小的，发生交换，可以理解将arr[i]放在空的arr[j]位置
//此时可以理解为arr[i]的位置空了
}
arr[i]=key; //当前组内分隔已经完成，基准值放置在空出来的位置（中间位置）
QuickSort(arr, left, i-1); //递归左边组
QuickSort(arr, i+1, right); //递归右边组
}
void SelectSort(int *arr, int len)
{//与冒泡排序对比学习
int i,j,k,temp;
for(i=0;i<len-1;i++)
{//遍历每一个数，然后两两比较
k=i; //k用来记录此趟排序中最小的值的位置
for(j=i+1;j<len;j++) //j初始化为i+1
{
if(arr[j]<arr[k]) //如果遍历到的元素比最小的值还要小
k=j; //那么就更新最小的位置
}
if(k!=i)
{//如果k的值发生了变化，说明找到了最小值，交换位置。否则 i 的位置就是最小值
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
}
void Merge(int *arr, int *temp_arr,int start,int mid,int end)
{
//二路归并左边一路的边界
int left_start = start ;
int left_end = mid ;
//二路归并右边一路的边界
int right_start = mid+1 ;
int right_end = end ;
int index = start ;
//比较指针所指向的数据，选择小的元素放入到归并空间（此时一定是未归并元素中最小的），并移动指针到下一位置
while(left_start<=left_end&&right_start<=right_end)
{
if(arr[left_start]>arr[right_start])
temp_arr[index++] = arr[right_start++] ;
else
temp_arr[index++] = arr[left_start++] ;
}
//判断是什么情况下退出上面的循环
//如果是右边一路元素已经归并完了，那么将左边一路剩下元素依次归并进临时数组
while(left_start<=left_end)
temp_arr[index++] = arr[left_start++] ;
//如果是右边一路元素已经归并完了，那么将左边一路剩下元素依次归并进临时数组
while(right_start<=right_end)
temp_arr[index++] = arr[right_start++] ;
//将临时数组依次放入原始数组
for(index = start ;index<=end ;++index)
arr[index] = temp_arr[index] ;
}
void MergeSort(int *arr, int *temp_arr,int start,int end)
{//与快速排序对比学习
if(start<end)
{
int mid = (start+end)/2 ; //划分左右两边的边界
MergeSort(arr,temp_arr,start,mid) ; //先递归划分左边的边界
MergeSort(arr,temp_arr,mid+1,end) ; //再递归划分右边的边界
Merge(arr,temp_arr,start,mid,end) ; //然后进行二路归并
}
}
void main()
{
int i;
int arr[LENGTH] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
int temp_arr[LENGTH];
printf("\n******** Insert Sort ********\n");
ShellSort(arr, LENGTH);
printf("\nSorted by Shell's Sort: \n");
for (i = 0; i < LENGTH; i++) {
printf("%d\t",arr[i]);
}
printf("\n\n");
printf("\n******** Swap Sort ********\n");
BubbleSort(arr, LENGTH);
printf("\nSorted by Bubble Sort: \n");
for (i = 0; i < LENGTH; i++) {
printf("%d\t",arr[i]);
}
printf("\n\n");
QuickSort(arr, 0, LENGTH-1);
printf("\nSorted by Quick Sort: \n");
for (i = 0; i < LENGTH; i++) {
printf("%d\t",arr[i]);
}
printf("\n\n");
printf("\n******** Select Sort ********\n");
SelectSort(arr, LENGTH);
printf("\nSorted by Select Sort: \n");
for (i = 0; i < LENGTH; i++) {
printf("%d\t",arr[i]);
}
printf("\n\n");
printf("\n******** Merge Sort ********\n");
MergeSort(arr, temp_arr, 0, LENGTH-1);
printf("\nSorted by Merge Sort: \n");
for (i = 0; i < LENGTH; i++) {
printf("%d\t",arr[i]);
}
printf("\n\n");
}
链表排序
public class Solution{
public static void main(String[] args){
int[] nums = {5,4,3,2,1};
int[] temp = new int[nums.length];
MergeSort(nums, temp, 0, 4);
for(int i=0; i<nums.length; i++) {
System.out.print(nums[i] + ",");
}
System.out.println();
ListNode head = new ListNode(-1);
ListNode p = head;
for(int i=0; i<nums.length; i++) {
ListNode listNode = new ListNode(nums[i]);
p.next = listNode;
p = p.next;
}
p.next = null;
MergeSort(head.next);
p = head.next;
while(p != null) {
System.out.print(p.val + "->");
p = p.next;
}
}
public static void MergeSort(int[] nums, int[] temp, int start, int end) {
if(start < end){
int mid = (start+end) >> 1;
MergeSort(nums, temp, start, mid);
MergeSort(nums, temp,mid+1, end);
Merge(nums, temp,start, mid, end);
}
}
public static void Merge(int[] nums, int[] temp, int start, int mid, int end) {
int leftStart = start;
int leftEnd = mid;
int rightStart = mid+1;
int rightEnd = end;
int index = start;
while(leftStart <= leftEnd && rightStart <= rightEnd) {
if(nums[leftStart] < nums[rightStart])
temp[index++] = nums[leftStart++];
else
temp[index++] = nums[rightStart++];
}
while(leftStart <= leftEnd)
temp[index++] = nums[leftStart++];
while(rightStart <= rightEnd)
temp[index++] = nums[rightStart++];
for(index=start; index<=end; index++)
nums[index] = temp[index];
}
public static ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static ListNode MergeSort(ListNode head) {
if(head == null || head.next ==null) return head;
ListNode mid = getMiddle(head);
ListNode midNext = mid.next;
mid.next = null;
return Merge(MergeSort(head), MergeSort(midNext));
}
public static ListNode Merge(ListNode listNode1, ListNode listNode2) {
if(listNode1 == null) return listNode2;
if(listNode2 == null) return listNode1;
ListNode res = new ListNode(-1);
ListNode head = res;
while(listNode1 != null && listNode2 != null) {
if(listNode1.val < listNode2.val){
head.next = listNode1;
listNode1 = listNode1.next;
head = head.next;
}else{
head.next = listNode2;
listNode2 = listNode2.next;
head = head.next;
}
}
if(listNode1 != null) {
head.next = listNode1;
}
if(listNode2 != null) {
head.next = listNode2;
}
return res.next;
}
}
队列
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_INIT_SIZE 100//队列的容量（最大元素个数）
typedef struct queue{
int *base; //存储空间的基地址
int front; //头指针
int rear; //尾指针
}SqQueue; //顺序队列
//队列的初始化
void InitQueue(SqQueue *p) {
p->base = (int*)malloc(QUEUE_INIT_SIZE * sizeof(int));
p->front = p->rear = 0; //头指针和尾指针0，队列为空
}
//判断队列是否为空
int EmptyQueue(SqQueue *p) {
//若为空队列 则返回OK，否则返回ERROR
if (p->front == p->rear) return 1;
else return 0;
}
//求循环队列的长度
int QueueLength(SqQueue *p) {
return (p->rear-p->front + QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
}
//顺序队列的入队
void EnQueue(SqQueue *p,int e) {
p->base[p->rear] = e;
p->rear = (p->rear+1) % QUEUE_INIT_SIZE;
}
//顺序队列的出队
int DeQueue(SqQueue *p) {
int e = p->base[p->front];
p->front = (p->front + 1) % QUEUE_INIT_SIZE;
return e;
}
//顺序队列的销毁
void DestroyQueue(SqQueue *p) {
//释放队列
free(p->base);
p->front = p->rear = 0;
}
//返回顺序队列的队头元素
int GetHead(SqQueue *p) {
//若栈不为空，则用e返回p的栈顶元素
return p->base[p->front];
}
//打印队列中元素
void PrintQueue(SqQueue *p) {
int i = 0;
int len = (p->rear-p->front + QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
while (i< len)
printf("%d ", p->base[p->front + i]);
printf("\n");
}
//测试栈的各种操作
void main() {
int n,i;
int a;
SqQueue *pqueue,queue;
pqueue = &queue;
InitQueue(pqueue); //初始化队列
if (EmptyQueue(pqueue)) printf("*** queue empty ***\n");
printf("please input the queue element number:");
scanf("%d", &n);
printf("please input the queue element: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &a);
EnQueue(pqueue, a);
}
if (!EmptyQueue(pqueue)) printf("*** queue not empty ***\n");
printf("the queue element number is: %d\n", QueueLength(pqueue));
printf("***********************\n");
printf("the queue element has: \n");
PrintQueue(pqueue);
printf("***********************\n");
}
