前言
这是在华清学习的第五个周末,这一周主要学习的是数据结构。老师说数据结构是一门非常庞大的学科,单单是数据结构里的一个小分支,单拎出来一周都未必可以学透,因此这周的数据结构课程里更多的是思维方向的学习,学习数据结构的思维方式和算法、拓宽思路,大方向上,利用好的数据结构和算法,来提升程序的执行效率,合理的使用内存资源;现阶段上,学习数据结构可以提高代码的质量,提升代码量,强化对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;
}
反思与总结
这周学的内容很多,代码量也很大,暴露了很多问题,听都能听懂,但自己真正考试上手写,各位错误,各种小细节、大的逻辑的问题很多,具体分析,当考虑到函数的健壮性的时候,容易落掉东西,或者会考虑的太多;再就是对老师教的写程序前,先画逻辑图帮助理解思路的方法,用的不熟练,也容易出问题。这周结束后,课程的基础部分就算结束了,对于以上这些问题,要抓紧时间了。
写在最后:写这篇文章是笔者一边看老师的目录,一边回想老师讲的内容,仅仅选取了我自己认为比较重要的,或者自己之前没接触过的进行汇总、总结,知识体系不完善,内容也不详细,仅供笔者复习使用。如果是有需要笔记,或者对这方面感兴趣,可以私信我,发你完整的知识体系和详细内容的笔记。写的仓促、水平有限,如有任何错误请多指正,也欢迎友好交流,定会虚心听取大佬的宝贵意见!