顺序表和链表
如何创建顺序表和链表
顺序表
1 编制C/C++程序，利用顺序存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表；然后根据屏幕提示，进行数据的插入或删除等操作，并在插入或删除数据后输出线性表。如图所示：
2.编制C/C++程序，利用链接存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表，输入输出要有相应的字幕提示
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int * e;
typedef struct list
{
e arr;
int size; //数组的长度
int indexSize; //实际上数组占用的长度
} ArrList;
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
//初始化线性
void initList(struct list *l,int length) {
l->size = length;
l->arr = (int *)malloc(sizeof(int) * length);
l->indexSize = 0;
}
//增加
/**/
int insert(ArrList * l ,int insertVlaue ,int insertIndex) {
//判断插入的值是否大于自身
if (insertIndex > l->indexSize+1 || insertIndex<0)
{
printf("插入的位置不合法");
return 0;
}
//先判断线性表是否已经满
if (l->size <= l->indexSize)
{
//位运算
l->arr=(int *)realloc(l->arr, sizeof(l->arr) * 10);
l->size = l->size * 10; //数组的长度变化
}
//printf("csss");
//判断是否是最后一个元素插入，如果是直接插入
if (l->indexSize+1==insertIndex)
{
l->arr[insertIndex-1] = insertVlaue; //写入数据
l->indexSize=l->indexSize + 1;
return 1;
}
//创建临时变量
int temp;
//进行插入动作
for (int i = (l->indexSize); i >= insertIndex; i--)
{
//先挪(从后面挪)
l->arr[i] = l->arr[i -1];
if (i == insertIndex)
{
//插入数据
l->arr[insertIndex - 1] = insertVlaue;
l->indexSize = l->indexSize + 1;
}
}
}
void del(ArrList* l,int indexDel) {
//判断删除的最后一个元素
if (indexDel>l->indexSize|| indexDel<0)
{
printf("下标非法不可删除");
return;
}
//进行操作删除
for (int i = indexDel; i < l->indexSize; i++)
{
l->arr[i - 1] = l->arr[i];
if (i+1 == l->indexSize)
{
l->arr[i] = 0;
l->indexSize = l->indexSize - 1;
}
}
}
//void menu()
// 在链表末尾插入新节点
void insertNode(struct Node** head, int value) {
// 创建新节点
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (*head == NULL) {
// 空链表，将新节点设为头节点
*head = newNode;
}
else {
// 遍历链表找到末尾节点
struct Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
// 将新节点插入到末尾
current->next = newNode;
}
}
// 输出链表
void printList(struct Node* head) {
struct Node* current = head;
printf("线性表内容：");
while (current != NULL) {
printf(" %d", current->data);
current = current->next;
}
printf("\n");
}
int main() {
int length;//定义一个常数
ArrList arrList;
printf("请输入要初始化的线性表的个数：");
scanf("%d", &length);
initList(&arrList, length);
int indexSize=0;
printf("顺序表初始化完成\n");
printf("请输入线性表的各个元素：\n");
for (int i = 0; i < length; i++)
{
scanf("%d", &arrList.arr[i]);
indexSize++;
}
printf("原线性表如下：\n");
arrList.indexSize = indexSize;
for (int i = 0; i < indexSize; i++)
{
printf(" %d ", arrList.arr[i]);
}
printf("\n");
//printf("初始化数据和填充数据完成\n");
int insertIndex;//插入的位置
int insertValue;//插入的元素
printf("请输入插入的元素和位置：\n");
scanf("%d %d", &insertValue, &insertIndex);
insert(&arrList, insertValue, insertIndex);
for (int i = 0; i < arrList.indexSize; i++)
{
printf(" %d ", arrList.arr[i]);
}
printf("\n");
printf("请输入删除元素的第几个：\n");
int indexDel;
scanf("%d", &indexDel);
del(&arrList, indexDel);
for (int i = 0; i < arrList.indexSize; i++)
{
printf(" %d ", arrList.arr[i]);
}
printf("\n");
printf("第二题=========================\n");
Node* head = NULL;
int value;
printf("请输入整数（以-1结束）：");
while (1) {
scanf("%d", &value);
if (value == -1) {
break; // 输入-1时退出循环
}
insertNode(&head, value);
}
printList(head);
printf("\n");
return 0;
}链表
题目：
1、编制C/C++程序，利用链式存储方式实现下列功能：从键盘输入学生成绩建立一个单链表（整数），然后根据屏幕提示，进行求学生成绩个数、查找学生成绩、删除学生成绩等操作。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct ListLink* Node; //定义一个结构体指针变量类型
typedef struct ListLink
{
float score; //成绩得分
Node nextLink; //下一个指针点
}ListLink;
int nodelength = 0; //保存链表的长度
Node initNodeList() {
Node head = (Node)malloc(sizeof(ListLink));
head->nextLink = NULL;
head->score = 0;
return head;
}
//插入
void insertList(ListLink* head, float value) {
//创建新的结点(创建下一个结点)
Node newNode = (Node)malloc(sizeof(struct ListLink));
newNode->score = value;
newNode->nextLink = NULL;
//如果说head=null，就是空的链表表直接插入
if (head->nextLink == NULL)
{
head->nextLink = newNode;//赋值结点
nodelength++;
}
//如果不是就找最后的结点，然后找出最后一个结点
else
{
Node next = head;
//如果不等于空，就继续找最后一个
while (next->nextLink != NULL)
{
next = next->nextLink;
}
next->nextLink = newNode;
nodelength++;
}
}
//查找链表
int findByNum(ListLink* list, int index) {
//先判断是否越界
if (index <= 0 || index > nodelength)
{
printf("查询非法越界\n");
return 0;
}
//查出第几个
Node node = list;
for (int i = 0; i < index; i++)
{
node = node->nextLink;
}
return (int)node->score;
}
//删除链表
void delByNum(ListLink* list, int index) {
//先判断是否越界
if (index <= 0 || index > nodelength)
{
printf("删除非法越界\n");
return;
}
//删除操作（n-1）//查出第几个
Node node = list;
for (int i = 0; i < index - 1; i++)
{
//查出n-1的结点
node = node->nextLink;
}
//找出下一个结点
Node delNode = node->nextLink; //
//判断是否是最后的结点，如果是就直接删除
if (node->nextLink == NULL)
{
free(delNode);
}
else
{
node->nextLink = delNode->nextLink;
}
printf("你要删除的第%d个学生的成绩：%d", index, (int)delNode->score);
free(delNode);
printf("\n");
//
}
//输出链表
void printList(ListLink* list) {
printf("链表内容：\n");
while (list->nextLink != NULL)
{
list = list->nextLink;
printf(" %d ", (int)list->score);
}
}
int main() {
printf("请输入学生的成绩，以-1为结束 \n");
//先设置头结点
Node head = initNodeList();
//ListLink head;
//head.nextLink = NULL;
//head.score = 0;
float value;
//循环输入
while (1) {
scanf("%f", &value);
if ((int)value == -1)
{
break;
}
//插入
insertList(head, value);
}
printList(head);
printf("\n");
printf("你输入学生的个数为%d", nodelength);
printf("\n");
printf("请输入你要查找的第几个学生的成绩：");
int num;
scanf("%d", &num);
int score = findByNum(head, num);
printf("他的成绩: ");
printf("%d", score);
printf("\n");
printf("请输入你要删除的第几位学生的信息: ");
int delNum;
scanf("%d", &delNum);
delByNum(head, delNum);
printf("\n");
printList(head);
printf("\n");
printf("2313202060332 王志毫\n");
return 1;
}题目：
编制C/C++程序，利用循环单链表实现下列功能：
1）从键盘输入数据建立两个循环单链表（整数），并输出相应链表，输入输出要有相应的字幕提示。
2）实现两个循环单链表的连接。要求结果链表仍旧使用原来两个链表的存储空间，不另外开辟空间。如下图所示。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct ListLink* Node; //定义一个结构体指针变量类型
typedef struct ListLink
{
int score; //成绩得分
Node nextLink; //下一个指针点
}ListLink;
int nodelength1 = 0; //保存链表1的长度
int nodelength2 = 0; //保存链表2的长度
Node headNodeList1; //记录第一个链表的头结点
Node headNodeList2; //记录第二个链表的头结点
Node tailNodeList1; //记录第一个链表的尾结点
Node tailNodeList2; //记录第二个链表的尾结点
Node initNodeList() {
Node head = (Node)malloc(sizeof(ListLink));
head->nextLink = NULL;
head->score = 0;
return head;
}
//插入
void insertList(ListLink* head, int value, int chooseList) {
if (!(chooseList == 1 || chooseList == 2))
{
printf("chooseList非法值");
return;
}
//int* nodelength =chooseList == 1 ? &nodelength1 : &nodelength2;
//创建新的结点(创建下一个结点)
Node newNode = (Node)malloc(sizeof(struct ListLink));
newNode->score = value;
newNode->nextLink = head;
//如果说head=null，就是空的链表表直接插入
if (head->nextLink == NULL)
{
head->nextLink = newNode;//赋值结点
}
//如果不是就找最后的结点，然后找出最后一个结点
else
{
Node next = head;
//如果不等于空，就继续找最后一个
while (next->nextLink != head)
{
next = next->nextLink;
}
next->nextLink = newNode;
}
if (chooseList == 1)
{
tailNodeList1 = newNode;
}
else
{
tailNodeList2 = newNode;
}
}
//输出链表
void printList(ListLink* list) {
Node head = list;
while ((list->nextLink)!= head)
{
list = list->nextLink;
printf(" %d ", (int)list->score);
}
}
//合并两个链表（后面的链表接前面的链表）
void mergeList(ListLink* list1, ListLink* list2) {
tailNodeList1->nextLink= list2->nextLink;
tailNodeList2->nextLink= headNodeList1;
}
int main() {
int nodeNum;
printf("请输入第一个循环单链表的结点个数: ");
scanf("%d", &nodeNum);
//printf("\n");
Node head1 =initNodeList();
headNodeList1 = head1;
int value;
for (int i = 0; i < nodeNum; i++)
{
scanf("%d", &value);
//插入
insertList(head1, value,1);
}
printf("第一个循环的单链表的值：");
printList(head1);
printf("\n");
//第二小问
printf("请输入第二个循环单链表的结点个数: ");
int nodeNum1;
scanf("%d", &nodeNum1);
Node head2 = initNodeList();
headNodeList2 = head2;
int value1;
for (int i = 0; i < nodeNum1; i++)
{
scanf("%d", &value1);
//插入
insertList(head2, value1, 2);
}
printf("第二个循环的单链表的值：");
printList(head2);
printf("\n");
printf("合并后的循环链表：");
mergeList(head1, head2);
printList(head1);
printf("\n");
return 1;
}顺序栈和链栈
如何创建顺序栈和链栈
程序填空，下表中代码一是用Ｃ++实现顺序栈的各种基本操作的代码，请将其中“...”的部分补充完整。并运行代码，执行各个菜单功能，将运行结果截图粘贴到代码下方。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define Max_Size 10 //初始化
typedef struct Stack* st;
typedef int t;
typedef struct Stack
{
t* arr;
int top; //栈顶
int bottom; //栈底
int size; //栈的大小
}Stack;
//菜单
void menu() {
printf("菜单列表\n");
printf("1.进栈\n");
printf("2.出栈\n");
printf("3.获取栈顶元素\n");
printf("4.栈置空\n");
printf("5.由栈顶到栈底依次输出栈元素\n");
printf("6.退出\n");
}
//初始化
Stack* initStack() {
st stack = (st)malloc(sizeof(Stack));
stack->arr = (int*)malloc(sizeof(stack->arr) * Max_Size);
stack->top = -1;
stack->bottom = -1;
stack->size = Max_Size;
return stack;
}
//判断栈是否为空
int isEmpty(st stack) {
if (stack->top == -1)
{
return 1;
}
return 0;
}
int isFull(st stack) {
if (stack->top >= stack->size)
{
return 1;
}
return 0;
}
//入栈(可以多次入栈)
void push(Stack* stack) {
printf("输入你想要入栈的值(-1结束): ");
int stackPushValue;
while (1)
{
scanf("%d", &stackPushValue);
if (stackPushValue == -1)
{
break;
}
//判断栈是否满,如果满的话就扩容
if (stack->top >= (stack->size) - 1)
{
stack->arr = (int*)realloc(stack->arr, sizeof(*(stack->arr) * 2));
stack->size = (stack->size) * 2;
}
stack->top++;
stack->arr[stack->top] = stackPushValue;
}
}
//出栈
void pop(st stack) {
//先判断栈是否为空
if (isEmpty(stack))
{
printf("栈是空的");
return;
}
printf("出栈的数据：");
printf(" %d", stack->arr[stack->top]);
stack->arr[stack->top] = 0;
stack->top--;
printf("\n");
}
void getTop(st stack) {
//先判断栈顶是否为空
if (isEmpty(stack))
{
return;
}
printf("栈顶的元素是：");
printf(" %d", stack->arr[stack->top]);
printf("\n");
}
//置空
void makeEmpty(st stack) {
//先判断栈是否为空
if (isEmpty(stack))
{
printf("栈是空的");
return;
}
printf("出栈的数据：");
while (stack->top < -1)
{
printf(" %d", stack->arr[stack->top]);
stack->arr[stack->top] = 0;
stack->top--;
}
printf("\n");
}
void print(st stack) {
if (isEmpty(stack))
{
printf("栈是空的");
printf("\n");
return;
}
printf("打印栈的数据：");
st copyStack = stack;
while (copyStack->top != -1)
{
printf(" %d", copyStack->arr[copyStack->top]);
copyStack->arr[copyStack->top] = 0;
copyStack->top--;
}
printf("\n");
}
//执行菜单里的功能
void execMenu(Stack* stack, int num) {
switch (num) {
case 1:
push(stack);
break;
case 2:
//出栈
pop(stack);
break;
case 3:
//获取栈顶元素
getTop(stack);
break;
case 4:
makeEmpty(stack);
break;
case 5:
print(stack);
break;
case 6:
printf("感谢使用");
break;
default:
break;
exit(0);
}
}
int main()
{
Stack* stack = initStack();
while (1)
{
menu();
int value;
printf("请输入你想要的操作功能: ");
scanf("%d", &value);
execMenu(stack, value);
}
}编写C++程序实现栈的链式存储（链栈LinkStack），使其实现与代码一中一样的基本功能（建栈、判断栈是否非空、求栈的长度、输出从栈顶到栈底的元素等）
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkSatck* LK;
typedef struct LinkSatck
{
int data;
LK linkSatckNext;
}LinkSatck;
//菜单
void menu() {
printf("菜单列表\n");
printf("1.进栈\n");
printf("2.出栈\n");
printf("3.获取栈顶元素\n");
printf("4.栈置空\n");
printf("5.由栈顶到栈底依次输出栈元素\n");
printf("6.退出\n");
}
//初始化链表
LK initLinkSatck() {
LK head = (LK)malloc(sizeof(LK));
head->data = 0;
head->linkSatckNext = NULL;
return head;
}
//头插法
void push(LK head) {
int values;
printf("请输入你要插入栈的元素：");
scanf("%d", &values);
//开辟空间
LK lkNode = (LK)malloc(sizeof(LinkSatck));
lkNode->data = values;
//先判断是否是第一个元素
if (head->linkSatckNext == NULL)
{
lkNode->linkSatckNext = NULL;
head->linkSatckNext = lkNode;
}
//否则的话
else
{
//找到头结点的下个结点
lkNode->linkSatckNext = head->linkSatckNext;
head->linkSatckNext = lkNode;
}
}
//出栈
void pop(LK head) {
//先判断是否是空栈
if (head->linkSatckNext == NULL)
{
printf("当前是空栈无法出栈");
return;
}
else if (head->linkSatckNext->linkSatckNext == NULL) {
/* printf("当前出栈的元素: %d", head->linkSatckNext->data);*/
free(head->linkSatckNext);
head->linkSatckNext = NULL;
}
else
{
LK popNode = head->linkSatckNext;
/* printf("当前出栈的元素: %d", popNode->data);*/
head->linkSatckNext = popNode->linkSatckNext;
free(popNode);
}
}
void getTop(LK head) {
//先判断栈顶是否为空
if (head->linkSatckNext == NULL)
{
printf("当前是空栈无法出栈 \n");
return;
}
printf("栈顶的元素是：");
printf(" %d", head->linkSatckNext->data);
printf("\n");
}
void makeEmpty(LK head) {
if (head->linkSatckNext == NULL)
{
printf("当前是空栈无法出栈 \n");
}
printf("当前是由栈顶到栈底置空元素: ");
LK orderNode = head;
int i = 0;
while (orderNode->linkSatckNext != NULL)
{
orderNode = orderNode->linkSatckNext;
i++;
}
while (i!=0)
{
pop(head);
i--;
}
}
//当前出栈的顺序
void print(LK head) {
if (head->linkSatckNext == NULL)
{
printf("当前是空栈无法出栈 \n");
}
printf("当前是由栈顶到栈底依次输出栈元素: ");
LK orderNode = head;
while (orderNode->linkSatckNext != NULL)
{
orderNode = orderNode->linkSatckNext;
printf("%d ", orderNode->data);
}
}
//执行菜单里的功能
void execMenu(LK head, int num) {
switch (num) {
case 1:
push(head);
break;
case 2:
//出栈
pop(head);
break;
case 3:
//获取栈顶元素
getTop(head);
break;
case 4:
makeEmpty(head);
break;
case 5:
print(head);
break;
case 6:
printf("感谢使用");
break;
default:
break;
exit(0);
}
}
int main() {
//初始化数据
LK head = initLinkSatck(); //头结点
while (1) {
menu();
int value;
printf("请输入你想要的操作功能: ");
scanf("%d", &value);
execMenu(head, value);
}
}2023.10.08持续更新中~
2023.10.14j继续更新中~
顺序队列（循环队列）和链表
队列的基本操作包括：
1、初始化2、置空(清除内容)3、判空4、计数5、取队列首元素的值6、入队7、出队8、遍历
1、初始化2、置空(清除内容)3、判空4、计数5、取队列首元素的值6、入队7、出队8、遍历
1、代码一是实现链队列的各种基本运算，请将其中链队列的基本运算实现。并在主函数中测试算法的正确性。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
/*=========================
* 队列的链式存储结构（链队）
==========================*/
#define TRUE 1 // 真/是
#define FALSE 0 // 假/否
#define OK 1 // 通过/成功
#define ERROR 0 // 错误/失败
/* 状态码类型 */
typedef int Status;
/* 链队列中数据元素类型定义 */
typedef int QElemType;
// 队列结点结构
typedef struct QNode {
QElemType data;
struct QNode* next;
}QNode;
// 队列结构
typedef struct LinkQueue {
QNode* front; // 队头指针
QNode* rear; // 队尾指针
}LinkQueue; // 队列的链式存储表示
Status InitQueue(LinkQueue* Q);//初始化函数声明
Status ClearQueue(LinkQueue* Q);//置空函数声明
Status QueueEmpty(LinkQueue Q);//判空函数声明
int QueueLength(LinkQueue Q);//计数函数声明
Status GetHead(LinkQueue Q, QElemType* e);//取值函数声明
Status EnQueue(LinkQueue* Q, QElemType e);//入队函数声明
Status DeQueue(LinkQueue* Q, QElemType* e);//出队函数声明
Status PrintQueue(LinkQueue Q);//遍历函数声明
//初始化函数（带头结点）
Status InitQueue(LinkQueue* Q) {
//申请一个头结点
QNode* nodeQue = (QNode*)malloc(sizeof(QNode));
nodeQue->data = 0;
nodeQue->next = NULL;
Q->front = Q->rear = nodeQue;
return OK;
}
//判断是否为空
Status QueueEmpty(LinkQueue Q) {
return Q.front == Q.rear ? TRUE : FALSE;
}
/*
* 入队
*
* 将元素e添加到队列尾部。
*/
Status EnQueue(LinkQueue* Q, QElemType e) {
QNode* nodeQue = (QNode*)malloc(sizeof(QNode));
nodeQue->data = e;
nodeQue->next = NULL;
//入队(判断是否空)
if (QueueEmpty(*Q) == TRUE)
{
Q->rear->next = nodeQue;
Q->rear = nodeQue;
}
else
{
//加入队尾
QNode* tailNode = Q->rear;
tailNode->next = nodeQue;
Q->rear = nodeQue;
}
return OK;
}
/*
* 遍历
*
* 用visit函数访问队列Q
*/
Status PrintQueue(LinkQueue Q) {
//遍历
if (QueueEmpty(Q) == TRUE)
{
printf("当前的队列为空，无法遍历");
printf("\n");
}
else
{
//取对头元素
QNode* nodeFront = Q.front;
//没有队列元素()
while (nodeFront->next != NULL)
{
nodeFront = nodeFront->next;
printf("%d ", nodeFront->data);
}
}
}
/*
* 计数
*
* 返回链队包含的有效元素的数量。
*/
int QueueLength(LinkQueue Q) {
//计数
//取对头元素
QNode* nodeFront = Q.front;
//没有队列元素()
int i = 0;
while (nodeFront->next != NULL)
{
i++;
nodeFront = nodeFront->next;
//printf("%d ", nodeFront->data);
}
return i;
}
/*
* 出队
*
* 移除队列头部的元素，将其存储到e中。
*/
Status DeQueue(LinkQueue* Q, QElemType* e) {
//出队
if (QueueEmpty(*Q) == TRUE)
{
printf("当前的队列为空,无法出队");
printf("\n");
return ERROR;
}
//看看是否是只有第一个结点
QNode* headNode = Q->front;
if (headNode->next->next == NULL) {
QNode* frontNode=headNode->next;
*e = frontNode->data;
headNode->next == NULL;
free(frontNode);//释放空间
Q->rear = headNode;
return OK;
}
else
{
QNode* frontNode = headNode->next;
*e = frontNode->data;
headNode->next = frontNode->next;
free(frontNode);
}
}
/*
* 取值
*
* 获取队头元素，将其存储到e中。
* 如果可以找到，返回OK，否则，返回ERROR。
*/
Status GetHead(LinkQueue Q, QElemType* e) {
//出队
if (QueueEmpty(Q) == TRUE)
{
printf("当前的队列为空,无法获取到对头元素");
printf("\n");
return ERROR;
}
else
{
(*e) = Q.front->next->data;
return OK;
}
}
/*
* 置空(内容)
*
* 这里需要释放链队中非头结点处的空间。
*/
Status ClearQueue(LinkQueue * Q) {
//出队
if (QueueEmpty(*Q) == TRUE)
{
printf("当前的队列为空,无法出队");
printf("\n");
return ERROR;
}
//置空
//统计多少个
int length = QueueLength(*Q);
int es;
for (int i = 0; i < length; i++)
{
//不停的出队
DeQueue(Q,&es);
}
return OK;
}
int main() {
LinkQueue Q;//定义结构体变量Q
Q.front = Q.rear = NULL;//初始化头指针Q.front和尾指针Q.rear为空指针
printf("******测试初始化函数 InitQueue \n");
{
printf(" 初始化链队 Q ...\n");
InitQueue(&Q);
}
printf("\n");
printf("******测试判空函数QueueEmpty \n");
{
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
}
printf("\n");
printf("******测试入队函数 EnQueue \n");
{
int i; //接收输入的值
printf("请输入入队元素值，多个值以空格分隔，-1为结束标志：");
while (1)
{
scanf("%d", &i);
if (i == -1)
{
break;
}
EnQueue(&Q, i);
}
}
printf("\n");
printf("******测试打印函数 PrintQueue \n");
{
printf("Q 中的元素为：Q = ");
PrintQueue(Q);
}
printf("\n");
printf("******测试求长度函数 QueueLength \n");
{
int length = QueueLength(Q);
printf(" Q 的长度为 %d \n", length);
}
printf("\n");
printf("****测试求出队函数DeQueue \n");
{
int returnE;
DeQueue(&Q, &returnE);
printf(" 队头元素 \"%d\" 出队...\n", returnE);
printf("Q 中的元素为：Q = ");
PrintQueue(Q);
}
printf("\n");
printf("****测试求获得链队列首元素的值的函数GetHead \n");
{
int returnE;
int k = GetHead(Q, &returnE);
if (k == 0)
printf("Q 为空！\n");
else
printf("队列首元素的值为 \"%d\" \n", returnE);
}
printf("****测试清空函数 ClearQueue \n");
{
printf("清空 Q 前：");
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
ClearQueue(&Q);
printf("清空 Q 后：");
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
}
printf("\n");
return 1;
}2、代码二是实现循环队列的各种基本运算，请将其中循环队列的基本运算实现。并在主函数中测试算法的正确性。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
/*=============================
* 队列的顺序存储结构（循环顺序队列）
==============================*/
#define TRUE 1 // 真/是
#define FALSE 0 // 假/否
#define OK 1 // 通过/成功
#define ERROR 0 // 错误/失败
/* 宏定义 */
#define MAXSIZE 5 //最大队列长度
/* 状态码类型 */
typedef int Status;
/* 链队列中数据元素类型定义 */
typedef int QElemType;
// 循环队列的顺序存储结构
typedef struct {
QElemType* base; // 动态分配存储空间
int front; // 头指针，若队列不空，指向队列首元素
int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SeQueue;
Status InitQueue(SeQueue* Q);//初始化
Status DestroyQueue(SeQueue* Q);//销毁
Status ClearQueue(SeQueue* Q);//置空
Status QueueEmpty(SeQueue Q);//判空
int QueueLength(SeQueue Q);//计数
Status GetHead(SeQueue Q, QElemType* e);//取值
Status EnQueue(SeQueue* Q, QElemType e);//入队
Status DeQueue(SeQueue* Q, QElemType* e);//出队
Status PrintQueue(SeQueue Q);//遍历
/*
* 初始化
*
* 构造一个空的顺序队列。
* 初始化成功则返回OK，否则返回ERROR。
*
*【注】
* 这里的队列是循环队列
*/
Status InitQueue(SeQueue* Q) {
//初始化
Q->base = (QElemType*)malloc(sizeof(Q->base) * MAXSIZE);
Q->front = 0;
Q->rear = 0;
}
/*
* 判空
*
* 判断循环顺序队列中是否包含有效数据。
*
* 返回值：
* TRUE : 循环顺序队列为空
* FALSE: 循环顺序队列不为空
*/
Status QueueEmpty(SeQueue Q) {
//判空
return Q.front == Q.rear ? TRUE : FALSE;
}
/*
* 入队
*
* 将元素e添加到队列尾部。
*/
Status EnQueue(SeQueue* Q, QElemType e) {
//判断是否满了(追上队首)
if ((Q->rear + 1) % MAXSIZE == Q->front)
{
printf("队列已经满了\n");
return FALSE;
}
Q->rear = (Q->rear + 1) % MAXSIZE; //队尾向前一位
Q->base[Q->rear] = e;
return TRUE;
}
/*
* 遍历队列Q
*/
Status PrintQueue(SeQueue Q) {
//遍历
int front = Q.front;
int rear = Q.rear;
//模拟出队
while (front != rear)
{
//出队
printf("%d ", Q.base[front + 1]);
front = (front + 1) % MAXSIZE;
}
}
/*
* 计数
*
* 返回循环顺序队列包含的有效数据元素的数量。
*/
int QueueLength(SeQueue Q) {
//计数
//遍历
int front = Q.front;
int rear = Q.rear;
//模拟出队
int i = 0;
while (front != rear)
{
//出队
i++;
front = (front + 1) % MAXSIZE;
printf("%d ", Q.base[front]);
}
return 1;
}
/*
* 出队
*
* 移除队列头部的元素，将其存储到e中。
*/
Status DeQueue(SeQueue* Q, QElemType* e) {
if (QueueEmpty(*Q) == TRUE)
{
printf("当前队列是空的");
return ERROR;
}
else
{
Q->front = (Q->front + 1) % MAXSIZE;
*e = Q->base[Q->front];
}
}
/*
* 取值
*
* 获取队头元素，将其存储到e中。
* 如果可以找到，返回OK，否则，返回ERROR。
*/
Status GetHead(SeQueue Q, QElemType* e) {
if (QueueEmpty(Q) == TRUE)
{
printf("当前队列是空的");
return ERROR;
}
else
{
*e = Q.base[(Q.front + 1) % MAXSIZE];
return OK;
}
}
/*
* 置空(清空内容)
*
* 只是置空循环顺序队列，不释放顺序队列所占内存。
*/
Status ClearQueue(SeQueue* Q) {
if (QueueEmpty(*Q) == TRUE)
{
printf("当前队列是空的");
return ERROR;
}
//置空
while (Q->front != Q->rear)
{
Q->front = (Q->front + 1) % MAXSIZE;
Q->base[Q->front] = 0;
//出队
}
Q->front = Q->rear = 0;
return OK;
}
/*
* 销毁(结构)
*
* 释放循环顺序队列所占内存。
*/
Status DestroyQueue(SeQueue* Q) {
//销毁
ClearQueue(Q);//清除再置空
free(Q->base);
Q->base = NULL;
return OK;
}
int main() {
SeQueue Q;
int i;
QElemType e;
QElemType x;
printf("******测试初始化函数 InitQueue \n");
{
printf("初始化循环顺序队列 Q ...\n");
InitQueue(&Q);
}
printf("\n");
printf("******测试判空函数 QueueEmpty \n");
{
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
}
printf("\n");
printf("******测试入队函数EnQueue \n");
{
printf("请输入入队元素值，多个值以空格分隔， - 1为结束标志：");
while (1)
{
scanf("%d", &x);
if (x == -1)
{
break;
}
EnQueue(&Q, x);
}
}
printf("\n");
printf("******测试打印函数 PrintQueue \n");
{
printf("Q 中的元素为：Q = ");
PrintQueue(Q);
}
printf("\n");
printf("******测试求长度函数QueueLength \n");
{
i = QueueLength(Q);
printf("Q 的长度为 %d \n", i);
}
printf("\n");
printf("****测试求出队函数DeQueue \n");
{
DeQueue(&Q, &e);
printf("队头元素 \"%d\" 出队...\n", e);
printf("Q 中的元素为：Q = ");
PrintQueue(Q);
}
printf("\n");
printf("****测试求获得链队列首元素的值的函数GetHead \n");
{
int k = GetHead(Q, &e);
if (k == 0)
printf("Q 为空！\n");
else
printf("队头元素的值为 \"%d\" \n", e);
}
printf("\n");
printf("****测试清空函数ClearQueue \n");
{
printf("清空 Q 前：");
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
ClearQueue(&Q);
printf("清空 Q 后：");
if (QueueEmpty(Q) == TRUE)
printf("Q 为空！\n");
else
printf("Q 不为空！\n");
}
printf("\n");
printf("****测试销毁函数 DestroyQueue \n");
{
printf("销毁 Q 前：");
if (Q.base != NULL)
printf(" Q 存在！\n");
else
printf(" Q 不存在！！\n");
DestroyQueue(&Q);
printf("销毁 Q 后：");
if (Q.base != NULL)
printf(" Q 存在！\n");
else
printf(" Q 不存在！！\n");
}
return 1;
}更新完毕，持续更新~ 2023.10.14
更新~ 2023.11.14
二叉树
要求：按照示例代码给出二叉树类的实现（采用双链表作为存贮结构，完成二叉树的建立；给出先序、中序、和后序遍历算法；给出求二叉树所有结点个数、叶子结点个数及树高度的算法），并设计一棵二叉树测试运行效果。
1)构建要求：给出二叉树扩充的先序序列，唯一地构造一棵二叉树。
2)数据要求：树中每个结点的数据类型设定为整型。
3)遍历算法要求：三种遍历都采用递归算法。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
//定义一个结构体
typedef struct BTreeNode {
int data;
struct Bnode* Lchild, * Rchild;
}Bnode, * ptr;
//函数声明
void inOrder(ptr); //中序遍历
void preOrder(ptr); //先序遍历
void postOrder(ptr); //后序遍历
int BTreeSize(ptr); //结点个数
int BTreeLeves(ptr); //叶子结点
int BTreeHeight(ptr); //树高
ptr createBTree();//根据扩充序列构建二叉树（题目是先序），扩充二叉树是指在二叉树中出现空子树的位置增加空树叶所形成的二叉树
//递归扩充序列构建二叉树（题目是先序）
ptr createBTree() {
int inputData;
scanf("%d", &inputData);
if (inputData == 0)//如果输入的是为0，就返回
{
return NULL;
}
//否则的话就创建一个结点
ptr p = (ptr)malloc(sizeof(Bnode));
p->data = inputData;
p->Lchild = createBTree();
p->Rchild = createBTree();
return p; //最后返回的是根结点
}
void preOrder(ptr root) {
if (root != NULL)
{
printf("%d ", root->data);
preOrder(root->Lchild);
preOrder(root->Rchild);
}
}
void inOrder(ptr root) {
if (root != NULL)
{
inOrder(root->Lchild);
printf("%d ", root->data);
inOrder(root->Rchild);
}
}
void postOrder(ptr root) {
if (root != NULL)
{
postOrder(root->Lchild);
postOrder(root->Rchild);
printf("%d ", root->data);
}
}
//菜单
void menu() {
printf("===========================\n");
printf("1:先序遍历\n");
printf("2:中序遍历\n");
printf("3:后序遍历\n");
printf("4:求结点的个数\n");
printf("5:求叶子结点个数\n");
printf("6:求树的高度\n");
printf("===========================\n");
}
int BTreeSize(ptr root) {
int k, m, n;
if (root != NULL)
{
k = 1;
m = BTreeSize(root->Lchild);
n = BTreeSize(root->Rchild);
return k + m + n;
}
else
{
return 0;
}
}
int BTreeLeves(ptr root) {
int m, n;
if (root != NULL)
{
if (root->Lchild == NULL && root->Rchild == NULL) {
return 1; //得出一个结点
}
m = BTreeLeves(root->Lchild);
n = BTreeLeves(root->Rchild);
return m + n;
}
else {
return 0;
}
}
int BTreeHeight(ptr root) {
int m, n;
if (root != NULL)
{
m = BTreeHeight(root->Lchild);
n = BTreeHeight(root->Rchild);
return 1 + (m > n ? m : n);
}
else
{
return 0;
}
}
int main() {
ptr root; //记录根结点
printf("请输入一个扩充序列：\n");
root = createBTree(); //根结点
printf("二叉树构造完成 \n");
menu(); //输出菜单
int inputSelectId;
while (1)
{
printf("请输入操作代码：");
scanf("%d", &inputSelectId);
switch (inputSelectId)
{
case 1:
preOrder(root);
break;
case 2:
inOrder(root);
break;
case 3:
postOrder(root);
break;
case 4:
printf("树共有%d个结点\n", BTreeSize(root));
break;
case 5:
printf("树共有%d个叶子\n", BTreeLeves(root));
break;
case 6:
printf("树高为%d\n", BTreeHeight(root));
break;
default:
printf("输入有误，请重新输入\n");
break;
}
printf("\n");
}
printf("32 王志毫");
return 1;
}