华清远见嵌入式培训_第五周回顾与反思

article/2025/3/15 15:43:59

前言

        这是在华清学习的第五个周末，这一周主要学习的是数据结构。老师说数据结构是一门非常庞大的学科，单单是数据结构里的一个小分支，单拎出来一周都未必可以学透，因此这周的数据结构课程里更多的是思维方向的学习，学习数据结构的思维方式和算法、拓宽思路，大方向上，利用好的数据结构和算法，来提升程序的执行效率，合理的使用内存资源；现阶段上，学习数据结构可以提高代码的质量，提升代码量，强化对C语言知识的理解和认识，养成编程思维、逻辑思维。

        这一周里主要的学习内容有：顺序表、链表、栈、队列、数和哈希数组，每一部分都很重要，主要是算法思路和程序实现方面的问题。

周一

数据结构概况和顺序表

一、数据结构概括

1.1 什么是数据结构

        老教授说：程序 = 数据结构 + 算法；

        数据结构是独立于计算机和编程语言的，是一种处理数据的思想；

        数据结构是研究 数据逻辑关系、存储、及操作的知识；

        数据：能够输入到计算机中的描述客观事物的信息集合 (需要计算机处理的对象)；

        结构：数据之间的关系；

        算法：对特定问题求解的一种描述；

1.2 数据元素和数据项

        数据元素：一组数据；

        数据项：某组数据中的某个独立数据；

        数据对象：若干相同数据元素的集合；

 1.3 数据结构三要素

       逻辑结构、存储结构、运算。

        逻辑结构：数据元素之间的关系，与存储无关，独立于计算机。主要指数据间的逻辑关系，例如邻接关系、直接前驱、直接后继等。

        存储结构：指数据在计算机，尤其是内存中的分布方式。

        运算：对数据的操作，例如增删改查、加减乘除、排序等。

1.4 数据的逻辑结构

        主要分为线性结构和非线性结构。

        线性关系：一对一。

        树形关系：一对多。

        网状关系：多对多。

 1.5 数据的存储结构

        顺序存储：数据元素之间在内存上是连续存储的，一般通过数组方式实现。

        链式存储：数据元素之间在内存上不一定是连续存储的（可以是，也可以不是），一般通过链表方式实现。

        索引存储：根据数据元素的特殊字段(称为关键字key)，计算数据元素的存放地址，然后数据元素按地址存放。

1.6 算法（操作）

        增删改查、加减乘除、排序翻转等。

二、顺序表

2.1 基本概念

        存储结构：顺序存储，C语言中通过数组实现，在内存中以连续的空间进行存储。

        逻辑结构：线性结构（一对一），除首元素和尾元素外，有唯一前趋和唯一后继（与数组的区别）。

        算法：增删改查、排序、去重，遍历（学习阶段用来看现象）。

2.2 代码实现

        main.c

#include "sq_list.h"int main(int argc, const char *argv[])
{LIST_t *L = create_list();if(NULL == L){puts("创建顺序表失败！！");return 0;}int choose = 0;while(1){print_menu();printf("请输入所需模式-->");scanf("%d",&choose);switch(choose){case 1:		//任意位置插入数据insert_pos(L);show_list(L);break;case 2:		//任意位置删除数据delet_pos(L);show_list(L);break;case 3:		//根据姓名查找数据元素name_find(L);break;case 4:name_change(L);break;case 5:sort_name(L);show_list(L);break;case 6:rm_sm_name(L);show_list(L);break;case 7:break;default:puts("模式选择错误，请重新输入！！");break;	}if(7 == choose){return 0;}}show_list(L);return 0;
}

        sq_list.c

#include "sq_list.h"void print_menu(){puts("");puts("----------------------");puts("|1、插入      2、删除|");puts("|3、查找      4、修改|");puts("|5、排序      6、去重|");puts("|7、退出             |");puts("----------------------");
}
//创建顺序表；
LIST_t *create_list(void){LIST_t *L = (LIST_t *)malloc(sizeof(LIST_t));if(NULL == L){puts("创建顺序表失败！！");return NULL;}L->index = 0;memset(L,0,sizeof(LIST_t));return L;
}//地址传递的方式创建顺序表；
void create_list_2(LIST_t **L){}//释放顺序表
int free_list(LIST_t **L){if(NULL == L||NULL == *L){puts("传入参数非法！！");return -1;}free(*L);*L = NULL;return 0;
}//任意插入数据
int insert_pos(LIST_t *L){if(NULL == L){puts("传入位置参数非法！！");return -1;}if((L->index == N)){puts("顺序表已满，无法继续添加！！");return -1;}int i = 0;STU_t stu_inf;int pos = 0;printf("请输入要插入的位置-->");scanf("%d",&pos);if(pos>(L->index)){puts("所输入的位置参数过大！！");return -1;}printf("请输入学生信息-->");scanf("%s%d%d",stu_inf.name,&(stu_inf.age),&(stu_inf.score));for(i=L->index;i>pos;i--){L->stu_list[i] = L->stu_list[i-1];}L->stu_list[pos] = stu_inf;L->index++;return 0;
}//任意位置删除数据
int delet_pos(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可删除！！");return -1;}int i = 0;int pos = 0;printf("请输入要删除的位置-->");scanf("%d",&pos);if(pos>(L->index)){puts("所输入的位置参数过大！！");return -1;}for(i = pos;i<(L->index)-1;i++){L->stu_list[i]  = L->stu_list[i+1];}L->index--;return 0;
}//遍历顺序表
int show_list(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可遍历!!");return -1;}int i = 0;for(i=0;i<(L->index);i++){printf("姓名：%s\t年龄：%d\t成绩：%d\n",L->stu_list[i].name,L->stu_list[i].age,L->stu_list[i].score);}return 0;
}//根据姓名查找数据元素
int name_find(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可查找!!");return -1;}int i = 0;char name[20];printf("请输入要查询的学生姓名--->");scanf("%s",name);for(;i<(L->index);i++){if(0 == strcmp(L->stu_list[i].name,name)){puts("已找到：");printf("姓名：%s\t年龄：%d\t成绩：%d\n",L->stu_list[i].name,L->stu_list[i].age,L->stu_list[i].score);break;}}if(i==L->index){puts("未找到！！");}return 0;
}//根据姓名修改数据项
int name_change(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可修改!!");return -1;}int i = 0;char name[20];int new_score = 0;printf("请输入要查询的学生姓名--->");scanf("%s",name);for(;i<(L->index);i++){if(0 == strcmp(L->stu_list[i].name,name)){puts("已找到：");puts("请输入学生新的成绩：");scanf("%d",&new_score);L->stu_list[i].score = new_score;printf("姓名：%s\t年龄：%d\t成绩：%d\n",L->stu_list[i].name,L->stu_list[i].age,L->stu_list[i].score);break;}}if(i==L->index){puts("未找到！！");}return 0;
}//根据学生的成绩继续排序
int sort_name(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可排序!!");return -1;}if(1 == L->index){puts("表中只有一个元素，无需排序！！");return -1;}STU_t mid;memset(&mid,0,sizeof(mid));int i,j;for(i=0;i<L->index;i++){for(j=i+1;j<L->index;j++){if(L->stu_list[i].score>L->stu_list[j].score){memset(&mid,0,sizeof(mid));mid =  L->stu_list[i];L->stu_list[i] = L->stu_list[j];L->stu_list[j] = mid;}}}return 0;
}//根据学生姓名去重
int rm_sm_name(LIST_t *L){if(NULL == L){puts("传入表参数非法！！");return -1;}if(0 == L->index){puts("表为空，无数据可排序!!");return -1;}if(1 == L->index){puts("表中只有一个元素，无需排序！！");return -1;}int i,j,k;for(i=0;i<L->index;i++){//定点for(j=i+1;j<L->index;j++){//动点if(0==strcmp(L->stu_list[i].name,L->stu_list[j].name)){//动点与定点依次比较，相等则删除动点位置数据for(k = i;k<(L->index)-1;k++){L->stu_list[k]  = L->stu_list[k+1];}L->index--;j--;  //动点自减，不能漏掉删除后前移的首元素}}}return 0;
}

        sq_list.h

#ifndef __SQ_LIST_H__
#define __SQ_LIST_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define N 5typedef struct student{char name[20];unsigned int age;unsigned int score;
}STU_t;typedef struct list{STU_t stu_list[N];unsigned int index;
}LIST_t;
//打印菜单
void print_menu();//创建顺序表；
LIST_t *create_list(void);//地址传递的方式创建顺序表；
void create_list_2(LIST_t **L);//释放顺序表
int free_list(LIST_t **L);//任意位置插入数据
int insert_pos(LIST_t *L);//任意位置删除数据
int delet_pos(LIST_t *L);//遍历顺序表
int show_list(LIST_t *L);//根据姓名查找数据元素
int name_find(LIST_t *L);//根据姓名修改数据项
int name_change(LIST_t *L);//根据学生的成绩继续排序
int sort_name(LIST_t *L);//根据学生姓名去重
int rm_sm_name(LIST_t *L);#endif

周二

链表

一、链表

1.1 基本概念

        逻辑结构：线性结构，一对一，有唯一前趋和唯一后继。

        存储结构：链式存储，在内存中存储不一定是连续的，数据间的逻辑关系需要指针来构建。

        算法：增删改查、修改翻转排序等。

1.2 链表的理解

        1. 数据表在内存中的地址是连续的；

        2. 链表在内存中的地址，不一定是连续的（可能连续，也可能不连续）；

         3. 链表中的每个节点由：数据域和指针域组成；

             数据域用来存放数据，指针域用来存放下一个节点的首地址；

             C语言中链表节点的表现形式是结构体。

        4. 注意：如下链表节点，变量成员data可以是C语言中的任意数据类型，包括结构体；指针成员next必须是自身节点的指针类型，本例中为：struct node *类型，否则将无法构建线性逻辑关系。

struct node{int data;struct node *next;
};

1.3 顺序表（数组）和链表的区别

        相同点：逻辑结构相同，都属于线性结构，一对一，有唯一前趋和唯一后继（区别于其他非线性结构，如树状、网状和图状）。

        不同点：存储结构不同：

                顺序表：连续存储，数据在内存中连续存储。

                链表：链式存储，数据在内存中不一定连续存储。

        注意：

                1. 顺序表操作时有判满操作，链表没有；

                2. 顺序表插入或删除相对复杂，需要批量移动元素，链表只需要改变指针的指向即可；

                3. 顺序表需要明确长度，适合小数据量的项目，链表不需要明确长度，适合相对较大的项目；

                4. 顺序表查找比较方便，可以根据下标访问，直接定位，链表则必须通过指针遍历。

1.4 函数实现

        main.c

#include "link_list.h"int main(int argc, const char *argv[])
{link_list_t *L = create_list();if(NULL == L){puts("创建链表失败！");return -1;}int choose = 0;int flag = 0;while(1){menu_print();printf("请选择模式-->");scanf("%d",&choose);switch(choose){case 1:printf("请选择插入方式：\n");printf("1.头部插入 2.尾部插入 3.任意位置插入-->");scanf("%d",&flag);if(1 == flag){head_insert(L);show_list(L);}else if(2 == flag){tail_insert(L);show_list(L);}else if(3 == flag){pos_insert(L);show_list(L);}else{puts("输入有误！");}break;case 2:printf("请选择删除方式：\n");printf("1.头部删除 2.尾部删除 3.任意位置删除-->");scanf("%d",&flag);if(1 == flag){head_delete(L);show_list(L);}else if(2 == flag){tail_delete(L);show_list(L);}else if(3 == flag){pos_delete(L);show_list(L);}else{puts("输入有误！");}break;case 3:find_list(L);break;case 4:change_list(L);show_list(L);break;case 5:sort_list(L);show_list(L);break;case 6:rm_sm_list(L);show_list(L);break;case 7:overturn_list(L);show_list(L);break;case 8:break;case 9:free_list(&L);break;defualt:puts("选项输入有误，请检查！");break;}if(8 == choose){return 0;}}return 0;

        link_list.c

#include "link_list.h"//打印菜单
void menu_print(void){puts("----------------------");puts("|1、插入      2、删除|");puts("|3、查找      4、修改|");puts("|5、排序      6、去重|");puts("|7、翻转      8、退出|");puts("|9、释放链表         |");puts("----------------------");
}//创建链表
link_list_t *create_list(void){link_list_t *L = (link_list_t *)malloc(sizeof(link_list_t));if(NULL == L){puts("创建链表失败！");return NULL;}L->data = -1;L->next = NULL;return L;
}//释放链表
int free_list(link_list_t **L){if(NULL == *L||NULL == L){puts("入参错误，请检查！");return -1;}link_list_t *q = (*L)->next;link_list_t *p;while(NULL != q){p = q;q = p->next;printf("%d将被释放\n",p->data);free(p);}free(*L);*L = NULL;return 0;}//头插
int head_insert(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}link_list_t *New = create_list();if(NULL == New){puts("创建新节点失败！");return -1;}New->next = NULL;printf("请输入要插入的数据-->");scanf("%d",&(New->data));New->next = L->next;L->next = New;return 0;
}//尾插
int tail_insert(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}link_list_t *New = create_list();if(NULL == New){puts("创建新节点失败！");return -1;}New->next = NULL;printf("请输入要插入的数据-->");scanf("%d",&(New->data));link_list_t *q = L;while(NULL != q->next){q = q->next;}q->next = New;return 0;
}//任意位置插入
int pos_insert(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}link_list_t *New = create_list();if(NULL == New){puts("创建新节点失败！");return -1;}New->next = NULL;printf("请输入要插入的数据-->");scanf("%d",&(New->data));int pos = 0;printf("请输入要插入的位置-->");scanf("%d",&pos);link_list_t *q = L;for(int i = 0;i<pos;i++){q = q->next;if(q == NULL){puts("输入位置参数非法！");return -1;}}New->next = q->next;q->next = New;return 0;
}//遍历
int show_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表无数据，无需遍历！");return -1;}link_list_t *q = L->next;while(q != NULL){printf("%d ",q->data);q = q->next;}puts("");return 0;
}//头删
int head_delete(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可删除！");return -1;}link_list_t *p;p = L->next;L->next = L->next->next;free(p);p = NULL;return 0;
}//尾删
int tail_delete(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可删除！");return -1;}link_list_t *q = L;link_list_t *p;while(q->next->next != NULL){q = q->next;}p = q->next;q->next = NULL;free(p);p = NULL;return 0;
}//任意位置删除
int pos_delete(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可删除！");return -1;}int pos = 0;printf("请输入要删除的位置-->");scanf("%d",&pos);link_list_t *q = L;link_list_t *p;for(int i = 0;i<pos;i++){q = q->next;if(q->next == NULL){puts("输入位置参数非法！");return -1;}}p = q->next;q->next = p->next;free(p);p = NULL;return 0;
}//查找
int find_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可查找！");return -1;}int data_f = 0;printf("请输入要查找的值-->");scanf("%d",&data_f);link_list_t *q = L;while(q->next != NULL){q = q->next;if(q->data== data_f){printf("找到了-->");printf("%d\n",q->data);return 0;}}if(q->next == NULL){puts("未找到");}return 0;
}//修改
int change_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可修改！");return -1;}int data_f = 0;printf("请输入要查找的值-->");scanf("%d",&data_f);link_list_t *q = L;while(q->next != NULL){q = q->next;if(q->data== data_f){printf("找到了-->");printf("%d\n",q->data);printf("要将%d修改为-->",q->data);scanf("%d",&(q->data));puts("修改完成");return 0;}}puts("未找到");return 0;
}//翻转
int overturn_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可翻转！");return -1;}if(NULL == L->next->next){puts("链表只有一个数据，无需翻转");return -1;}link_list_t *q = L->next->next;link_list_t *p;L->next->next = NULL;while(q != NULL){p = q;q = p->next;p->next = L->next;L->next = p;}puts("翻转完毕");return 0;
}//排序
int sort_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可排序！");return -1;}if(NULL == L->next->next){puts("链表只有一个数据，无需排序");return -1;}link_list_t *q = L->next;link_list_t *p = q->next;int temp = 0;while(q->next != NULL){while(p !=NULL){if(p->data<q->data){temp = p->data;p->data = q->data;q->data = temp;}p = p->next;}q = q->next;p = q->next;}return 0;
}
#if 0
//去重
int rm_sm_list(link_list_t *L){if(NULL == L){puts("入参非法！");return -1;}if(NULL == L->next){puts("链表为空，无数据可去重！");return -1;}if(NULL == L->next->next){puts("链表只有一个数据，无需去重");return -1;}link_list_t *q = L->next;link_list_t *p = q->next;link_list_t *t;int temp = 0;while(q->next != NULL){while(p !=NULL){if(p->data == q->data){t = p;p->data = p->next->data;free(t);}p = p->next;}q = q->next;p = q->next;}return 0;
}
#endif

        link_list.h

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct node{int data;struct node *next;
}link_list_t;//打印菜单
void menu_print(void);//创建链表
link_list_t *create_list(void);//释放链表
int free_list(link_list_t **L);//头插
int head_insert(link_list_t *L);//尾插
int tail_insert(link_list_t *L);//任意位置插入
int pos_insert(link_list_t *L);//遍历
int show_list(link_list_t *L);//头删
int head_delete(link_list_t *L);//尾删
int tail_delete(link_list_t *L);//任意位置删除
int pos_delete(link_list_t *L);//查找
int find_list(link_list_t *L);//修改
int change_list(link_list_t *L);//翻转
int overturn_list(link_list_t *L);//排序
int sort_list(link_list_t *L);//去重
int rm_sm_list(link_list_t *L);#endif

周三

单向循环链表、双向循环链表、顺序栈

一、单向循环链表

1.1 示意图

二、双向循环链表

2.1 示意图

2.2 插入节点流程图

2.3 删除节点流程图

三、栈（stack）

3.1 基本概念

        栈是一种先进后出的数据结构（FILO：first in last out）。

        栈的逻辑结构为线性结构。

        栈分为顺序栈和链式栈。

3.2 顺序栈

3.2.1 基本概念

        顺序栈是一种基于顺序表实现的栈的结构，它是顺序表的一种约束，相当于只能在同一端进行插入和删除元素，遵循先进后出的原则。

        一般需要配合一个“栈顶指针”(数组下标) TOP 使用。

        逻辑结构：线性结构；

        存储结构：顺序结构；

3.2.2 代码实现

main.c

#include "sq_stack.h"int main(int argc, const char *argv[])
{STACK_t *S = creat_sq_stack();if(NULL == S){puts("创建顺序栈失败");return -1;}int key = 0;while(1){menu_print();printf("请输入功能选项-->");scanf("%d",&key);switch(key){case 1:push_stack(S);show_top(S);show_stack(S);break;case 2:pull_stack(S);show_top(S);show_stack(S);break;case 3:show_top(S);break;case 4:free_stack(&S);break;case 7:break;case 5:S = creat_sq_stack();if(NULL == S){puts("创建顺序栈失败");return -1;}puts("已重新创建栈空间");break;case 6:show_stack(S);break;default:puts("输入有误，请重新选择");break;}if(7 == key){return 0;}}return 0;
}

sq_stack.c

#include "sq_stack.h"void menu_print(void){puts("");puts("1、入栈     2、出栈       3、查看栈顶元素");puts("4、释放栈   5、重新建栈   6、出栈顺序");puts("7、退出");puts("");
}STACK_t *creat_sq_stack(void){STACK_t *S = (STACK_t *)malloc(sizeof(STACK_t));if(NULL == S){puts("创建顺序栈失败");return NULL;}memset(S,0,sizeof(STACK_t));S->top =-1;return S;
}
int empty_stack(STACK_t *S){if(NULL == S){puts("入参非法");return -1;}return S->top==-1?-1:0;
}
int full_stack(STACK_t *S){if(NULL == S){puts("入参非法");return -1;} return S->top==N-1?:0;
}
int push_stack(STACK_t *S){if(NULL == S){puts("入参非法");return -1;}if(full_stack(S)){puts("顺序栈已满，入栈失败");return -1;}data_t value = 0;puts("请输入入栈元素-->");scanf("%d",&value);S->data[S->top+1] = value;S->top++;return 0;
}
int pull_stack(STACK_t *S){if(NULL == S){puts("入参非法");return -1;}if(empty_stack(S)){puts("顺序栈为空，出栈失败");return -1;}data_t ret = S->data[S->top];printf("%d已出栈\n",ret);S->top--;return 0;
}
int free_stack(STACK_t **S){if(NULL == S||NULL == *S){puts("入参非法");return -1;}free(*S);*S = NULL;puts("顺序表空间已释放");return 0;
}
data_t show_top(STACK_t *S){if(NULL == S){puts("入参非法");return -1;}if(empty_stack(S)){puts("顺序栈为空，无栈顶元素");return -1;}printf("此时栈顶元素为：%d\n",S->data[S->top]);return 0;
}
data_t show_stack(STACK_t *S){if(NULL == S){puts("入参非法");return -1;}if(empty_stack(S)){puts("顺序栈为空，无元素");return -1;}int i = S->top;printf("出栈顺序-->");while(i != -1){printf("%d ",S->data[i]);i--;}puts("");return 0;
}

sq_stack.h

#ifndef __SQ_STACK_H__
#define __SQ_STACK_H__#define N 5#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef int data_t;typedef struct stack{data_t data[N];int top;
}STACK_t;void menu_print(void);
STACK_t *creat_sq_stack(void);
int empty_stack(STACK_t *S);
int full_stack(STACK_t *S);
int push_stack(STACK_t *S);
int pull_stack(STACK_t *S);
int free_stack(STACK_t **S);
data_t show_top(STACK_t *S);
data_t show_stack(STACK_t *S);#endif

3.3 链式栈

3.3.1基本概念

        链式栈是一种基于链表实现的栈的结构，他是链表的一种约束，相当于只能在同一端进行插入和删除元素。

        一般使用入栈的操作使用 头插法 时间复杂度 O(1)

        出栈的操作使用 头删法 时间复杂度是O(1)

        也就是说，链表的头部最为栈顶，链表的尾部作为栈底。

3.3.2 示意图

3.3.3 入栈和出栈

3.3.4 代码实现

1. 链式栈的本质是限制在一段操作的链表，遵循先进后出的原则；

2. 链式栈同样不允许任意位置插入，翻转、排序等操作；

3. 链式栈只存在入栈、出栈、栈判空、查看栈顶元素、查看栈底元素和栈置空操作，注意链式栈没有判满操作；

4. 如果链式栈的入栈操作为头部插入，则出栈操作则为头部删除，入栈尾部操作同理。

link_stack.h

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__#include <stdio.h>
#include <stdlib.h>
#include <string.h>//链式栈节点的结构体
typedef struct __NODE{int data;struct __NODE *next;
}node_t;//链式栈的结构体
typedef struct __STACK{node_t *top;//指向栈顶元素的指针int count;//栈中元素的个数
}stack_t;int create_stack(stack_t **my_stack);
int create_node(node_t **p, int data);
int push_stack(stack_t *my_stack, int data);
int print_stack(stack_t *my_stack);
int pop_stack(stack_t *my_stack, int *num);
int is_empty(stack_t *my_stack);
int clean_stack(stack_t *my_stack);
int destroy_stack(stack_t **my_stack);#endif

link_stack.c

#include "./link_stack.h"//创建栈
int create_stack(stack_t **my_stack){if(NULL == my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}*my_stack = (stack_t *)malloc(sizeof(stack_t));if(*my_stack == NULL){printf("%s-%s(%d):内存分配失败\n",__FILE__,__func__,__LINE__);exit(-1);}//初始化(*my_stack)->top = NULL;(*my_stack)->count = 0;return 0;
}//创建数据节点的函数 -- 内部使用
int create_node(node_t **p, int data){if(NULL == p){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}*p = (node_t *)malloc(sizeof(node_t));if(NULL == *p){printf("%s-%s(%d):内存分配失败\n",__FILE__,__func__,__LINE__);exit(-1);}//节点初始化(*p)->next = NULL;(*p)->data = data;return 0;
}//入栈的函数
int push_stack(stack_t *my_stack, int data){if(NULL == my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}//链式栈无需检查栈满//创建新节点，将data装进新节点node_t *pnew = NULL;create_node(&pnew, data);//将新节点入栈pnew->next = my_stack->top;my_stack->top = pnew;my_stack->count++;return 0;
}//打印栈中所有元素
int print_stack(stack_t *my_stack){if(NULL == my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}node_t *ptemp = my_stack->top;while(ptemp != NULL){printf("%d  ", ptemp->data);ptemp = ptemp->next;}printf("\n");return 0;
}//判断栈是否为空 返回 1 空  0 非空  -1 出错
int is_empty(stack_t *my_stack){if(NULL == my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}return my_stack->top == NULL? 1 : 0;
}//出栈
int pop_stack(stack_t *my_stack, int *num){if(NULL == my_stack || NULL == num){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}//判断栈是否为空if(is_empty(my_stack)){printf("%s-%s(%d):栈已经空了 出栈失败\n",__FILE__,__func__,__LINE__);return -1;}//执行出栈的操作*num = my_stack->top->data;my_stack->count--;//执行头删法node_t *pdel = my_stack->top;my_stack->top = pdel->next;free(pdel);pdel = NULL;return 0;
}//清空栈中元素
int clean_stack(stack_t *my_stack){if(NULL == my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}//循环头删node_t *pdel = NULL;while(my_stack->top != NULL){pdel = my_stack->top;my_stack->top = pdel->next;free(pdel);}pdel = NULL;my_stack->count = 0;return 0;
}//销毁栈
int destroy_stack(stack_t **my_stack){if(NULL == my_stack || NULL == *my_stack){printf("%s-%s(%d):入参为NULL 请检查\n",__FILE__,__func__,__LINE__);return -1;}//先执行清空操作clean_stack(*my_stack);//然后再销毁free(*my_stack);*my_stack = NULL;return 0;
}

main.c

#include "./link_stack.h"int main(){//创建栈stack_t *my_stack = NULL;create_stack(&my_stack);//入栈push_stack(my_stack, 10);push_stack(my_stack, 20);push_stack(my_stack, 30);//遍历栈print_stack(my_stack);/*//出栈int num = 0;pop_stack(my_stack, &num);printf("num = %d\n", num);pop_stack(my_stack, &num);printf("num = %d\n", num);pop_stack(my_stack, &num);printf("num = %d\n", num);//遍历栈print_stack(my_stack);pop_stack(my_stack, &num);printf("num = %d\n", num);
*///清空栈clean_stack(my_stack);//遍历栈print_stack(my_stack);//销毁栈destroy_stack(&my_stack);printf("my_stack = %p\n", my_stack);return 0;
}

练习：

        编码实现：输入一个十进制数，输出他的二进制数--使用栈的功能实现

        如：44

        输出：101100

周四

队列   

补充：数据结构考试

18、写出一个循环队列的结构体，该队列元素最多是m个。

        1.      写出如何判断该队列为空的函数

        2.      写出如何判断该队列为满的函数

        3.      写出计算当前队列中的元素个数的函数

您的答案：

typedef struct queue{

    int data[m];

    unsigned int front;

    unsigned int rear;

}cyc_queue_t;

//1. 判断该队列为空的函数

int empty_queue(cyc_queue_t *Q)

{

    if(NULL == Q){

        puts("入参非法");

        return -1;

    }

    return (Q->front) == (Q->rear)?-1:0;

}

//2. 判断该队列为满的函数

int full_queue(cyc_queue_t *Q)

{

    if(NULL == Q){

        puts("入参非法");

        return -1;

    }

    return (Q->rear)%m == (Q->front)?-1:0;

}

//3. 计算当前队列中的元素个数的函数

int size_queue(cyc_queue_t *Q)

{

    if(NULL == Q){

        puts("入参非法");

        return -1;

    }

    return ((Q->front)-(Q->rear)+m)%m;

}

17、写出程序删除有头单链表中除头节点外的所有数据节点的函数。
//头删
int delete_link_list(link_list_t *L){
    if(NULL == L){
        puts("入参非法！");
        return -1;
    }
    if(NULL == L->next){
        puts("链表为空，无数据可删除！");
        return -1;
    }
    link_list_t *tem;
    while(L->next != NULL){
        tem = L->next;
        L->next = L->next->next;
        printf("%d将被删除\n",tem->data);
        free(tem);
        tem = NULL;
    }
    return 0;
} 

18、简述算法和思路，用两个栈实现一个队列的功能？
      答：   声明两个栈，s1,s2,
    1. 将元素入栈到s1中去，
    2. 判断当栈s2为空时，将s1依次取出栈顶元素，入栈到s2中去，
    3. 判断当s2不为空时，打印数据，出栈操作 

19、简述： 一个单向链表，不知道头节点,一个指针指向其中的一个节点，问如何删除这个指针指向的节点？
      答：假设节点 q-next 指向该节点，新建一个节点指针p，执行以下命令
    p = q;
    q->data = q->next->data；
    q->next = q->next->netx;
    free(p);
    p = NULL;
    但会有一个问题，如果该指针指向尾节点，则无法删除。 

20、写程序将一个单链表翻转。
  例如：1->2->3->4->5
  翻转后为：5->4->3->2->1.

int overturn_link_list(link_list_t *L)
{
    //健壮性
    if(NULL == L){
        puts("入参错误");
        return -1;
    }
    if(NULL == L->next){
        puts("链表为空，无法翻转");
        return -1;
    }
    if(NULL == L->next-next){
        puts("链表内只有一个元素，无需翻转");
        return -1;
    }
    link_list_t *q = L->next->next;
    L->next->next = NULL;
    link_list_t *p;

    while(q != NULL){
        p = q;
        q = p->next;
        p->next = L->next;
        L->next = p;
    }
    return 0;
}

反思与总结

        这周学的内容很多，代码量也很大，暴露了很多问题，听都能听懂，但自己真正考试上手写，各位错误，各种小细节、大的逻辑的问题很多，具体分析，当考虑到函数的健壮性的时候，容易落掉东西，或者会考虑的太多；再就是对老师教的写程序前，先画逻辑图帮助理解思路的方法，用的不熟练，也容易出问题。这周结束后，课程的基础部分就算结束了，对于以上这些问题，要抓紧时间了。

        写在最后：写这篇文章是笔者一边看老师的目录，一边回想老师讲的内容，仅仅选取了我自己认为比较重要的，或者自己之前没接触过的进行汇总、总结，知识体系不完善，内容也不详细，仅供笔者复习使用。如果是有需要笔记，或者对这方面感兴趣，可以私信我，发你完整的知识体系和详细内容的笔记。写的仓促、水平有限，如有任何错误请多指正，也欢迎友好交流，定会虚心听取大佬的宝贵意见！


http://chatgpt.dhexx.cn/article/rIusl9U8.shtml

相关文章

利用Python识别txt文本并根据其内容进行文件分类

利用Python识别txt文本并根据其内容进行文件分类

事情是这样的&#xff0c;有一个图片数据集需要根据分成很多类以便于给其设置标签&#xff0c;但所有的图片都在一个文件里&#xff0c;另外又给了个.txt文件&#xff0c;其中每行都是对应图片的类别。例如第1行对应的第0001.jpg是第14类&#xff08;每个类都有多张图片&#x…
阅读更多...
C# 批量修改文件名称

C# 批量修改文件名称

目的 对文件夹中所有文件名实现批量修改&#xff08;添加新字符&#xff09; 思路 获取文件夹路径获取文件夹中所有文件的文件名对文件名进行批量修改 方法 窗口设计 获取文件夹路径 使用FolderBrowserDialog控件获取文件夹路径&#xff0c;并用Directory.Exists方法对路径…
阅读更多...
Unity Shader入门精要之Unity 提供的内置文件和变量

Unity Shader入门精要之Unity 提供的内置文件和变量

Unity系列文章目录 文章目录 Unity系列文章目录前言5.3.1 内置的包含文件5.3.2 内置的变量 二、Unity 提供的Cg/HLSL 语义5.5 程序员的烦恼&#xff1a;Debug5.6 小心&#xff1a;渲染平台的差异5.7 Shader 整洁之道参考 前言 上一节讲述了如何在Unity 中编写一个基本的顶点/片…
阅读更多...
《python数学实验与建模》（10）图论模型

《python数学实验与建模》（10）图论模型

10.1 写出图10.20所示非赋权无向图的关联矩阵和邻接矩阵 绘制图 import networkx as nx import pylab as plt import numpy as np Anp.zeros((6,6)) List[(1,2),(1,4),(2,3),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)] for i in List:A[i[0]-1,i[1]-1]1 Gnx.Graph(A) posnx.spring…
阅读更多...
2021年美国数学建模C题的数据处理

2021年美国数学建模C题的数据处理

2021年美国数学建模C题的数据处理 C题数据分类存放部分批量提取图像数据转化jpg图像格式 C题数据分类存放部分 在拿到C题的数据后&#xff0c;避让要做的一个事情是图像数据的分类。根据2021MCM_ProblemC_ Images_by_GlobalID表格中&#xff0c;可以将图片和ID号对应起来&…
阅读更多...
Unity Shader入门精要笔记（五）：其他数学相关介绍

Unity Shader入门精要笔记（五）：其他数学相关介绍

本系列文章由Aimar_Johnny编写&#xff0c;欢迎转载&#xff0c;转载请标明出处&#xff0c;谢谢。 http://blog.csdn.net/lzhq1982/article/details/73747162 前两篇介绍了Unity Shader的主要数学部分&#xff0c;书上还有些相关的数学介绍&#xff0c;将在这篇做最后的总结。…
阅读更多...
2020年数维杯国际大学生数学建模B题股票价格的混沌模型求解全过程文档及程序

2020年数维杯国际大学生数学建模B题股票价格的混沌模型求解全过程文档及程序

2020年数维杯国际大学生数学建模 B题 股票价格的混沌模型 原题再现&#xff1a; 上市公司股价的变化可以直接反映上市公司的经营状况和市场的认可度。股票价格的建模和预测一直是一个难题。最重要的因素是股票价格既有趋势因素又有随机因素。因此&#xff0c;股票市场是一个非…
阅读更多...
ugpost_tcl文件

ugpost_tcl文件

########################## TCL Event Handlers ########################## b.tcl - 3_axis_mill 这是 3 轴铣床。 Created by dp Wednesday, November 06, 2019 8:52:33 AM China Standard Time with Post Builder version 10.0.3. #####################################…
阅读更多...
数据结构课设 （快餐店 POS 机计费系统、成绩分析、算术表达式）

数据结构课设 （快餐店 POS 机计费系统、成绩分析、算术表达式）

目录 快餐店 POS 机计费系统 学生成绩分析系统 算术表达式 参考文献 快餐店 POS 机计费系统 【任务描述】 校园快餐店一共出售三大类食品&#xff1a;饮料&#xff0c;主食&#xff0c;小食品。设计一个快餐店的 POS 机计费系统&#xff0c; 对快餐店的食品信息、销售信息…
阅读更多...
linux文件系统-文件的写与读

linux文件系统-文件的写与读

只有打开可文件以后&#xff0c;或者建立起进程与文件之间的连接之后&#xff0c;才能对文件进行读写。文件的读写主要是通过系统调用read和write来完成的&#xff0c;对于读写的进程&#xff0c;目标文件由一个打开文件号代表。 为了提高效率&#xff0c;稍微复杂一点的操作系…
阅读更多...
数学模型——泊车模型（2022年Mathorcup数学建模挑战赛C题，含Matlab代码）

数学模型——泊车模型（2022年Mathorcup数学建模挑战赛C题，含Matlab代码）

写在前面 之前做了一个2022年Mathorcup数学建模挑战赛C题的比赛心得&#xff0c;上一篇文章主要讲了A*算法的改进以及A*算法如何在C题的第3问的应用。本文主要介绍C题的第2问&#xff0c;即三种泊车模型如何建立&#xff0c;因此部分并非我写&#xff0c;在比赛期间&#xff0…
阅读更多...
Python小白的数学建模课-16.最短路径算法

Python小白的数学建模课-16.最短路径算法

最短路径问题是图论研究中的经典算法问题&#xff0c;用于计算图中一个顶点到另一个顶点的最短路径。在图论中&#xff0c;最短路径长度与最短路径距离却是不同的概念和问题&#xff0c;经常会被混淆。求最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法…
阅读更多...
数学建模有关DNA序列k-mer index的问题

数学建模有关DNA序列k-mer index的问题

原问题是这样的&#xff1a; 给定一个DNA序列&#xff0c;这个系列只含有4个字母ATCG&#xff0c;如 S “CTGTACTGTAT”。给定一个整数值k&#xff0c;从S的第一个位置开始&#xff0c;取一连续k个字母的短串&#xff0c;称之为k-mer&#xff08;如k 5&#xff0c;则此短串为CT…
阅读更多...
数学建模暑期集训26：遗传算法

数学建模暑期集训26：遗传算法

遗传算法是优化类问题的经典智能算法。本篇将介绍遗传算法的基本概念以及利用遗传算法来求解单目标规划模型。 达尔文进化论的基本思想 遗传算法的设计是受到达尔文进化论的启发。先看下面这张图的几个基本概念。 一些花构成一个种群。 每朵花被称为个体。 每个个体内有染色…
阅读更多...
2021年亚太杯三等奖选手C题思路

2021年亚太杯三等奖选手C题思路

文章目录 亚太杯C题第一小问亚太杯C题第二小问亚太杯C题第三小问亚太杯C题第四小问亚太杯C题第五小问 昨天晚上刚出了亚太杯的成绩&#xff0c;获得了三等奖&#xff0c;毕竟是第一次参加数学建模比赛&#xff0c;不是成功参与奖就很高兴了&#xff0c;结束了之后&#xff0c;还…
阅读更多...
python使用networks读取txt文件画一个有权有向图

python使用networks读取txt文件画一个有权有向图

class demo():def __init__(self):self.file_pathtest.txt#图文件 def draw_graph(self):G2 nx.DiGraph() # 创建&#xff1a;空的 有向图f open(self.file_path)lines [l.split() for l in f.readlines() if l.strip()]# print(lines)for i in lines:G2.add_edge(i[0],…
阅读更多...
数学建模常用功能

数学建模常用功能

目录 pandas读取数据 查看数据异常 提取指定列 将dataframe数据以numpy形式提取 数据划分 随机森林回归 GBDT回归 特征重要性可视化 输出&#xff1a; ​ 绘制3D散点图 导入自定义包且.py文件修改时jupyter notebook自动同步 dataframe删除某列中重复字段并删除对应行…
阅读更多...
c语言文件操作

c语言文件操作

文件操作读写 1 文件处理原理及基本概念 C语言的文件处理功能&#xff0c;大体上分为两种&#xff1a;一种是设置缓冲区&#xff0c;另一种是不设置缓冲区。因为不设置缓冲区的方法直接对磁盘进行操作&#xff0c;速度较慢&#xff0c;并且由于不是C的标准函数&#xff0c;跨…
阅读更多...
无人机视角展示(无人机图像定位 )--某数学建模A题MATLAB代码

无人机视角展示(无人机图像定位 )--某数学建模A题MATLAB代码

近期没啥空&#xff0c;水个简单的。。。。 目前只写了第一问&#xff0c;有空再写。。。。。 问题描述 无人驾驶飞机简称“无人机”&#xff0c;是利用无线电遥控设备和自备的程序控制装置操纵的不载人飞机。搭载图像设备的无人机在高空航拍、区域巡视、军事侦查等方面有广泛…
阅读更多...
2020 全国大学生数学建模竞赛C题思路+代码

2020 全国大学生数学建模竞赛C题思路+代码

题目链接&#xff1a;天翼云盘 珍藏美好生活 家庭云|网盘|文件备份|资源分享 前言 又是一年数据挖掘题型&#xff0c;第一次接触这种题型还是在去年的mathorcup上&#xff0c;这种题的难度就在于指标的建立和数据的处理上。后面会出一份关于数据挖掘题型&#xff0c;我的相关经…
阅读更多...
推荐文章

Copyright @ 2022~2023