C语言程序设计基础课件 06 数据结构

数据结构C语言程序设计基础目录CONTENTS010203栈队列二叉树04综合应用举例学习目标理解作用理解数据结构在程序设计中的作用，数据存储结构会影响算法好坏和程序执行效率。了解概念了解栈、队列和二叉树的概念，掌握它们的顺序和链式存储结构。掌握应用通过学习，熟练掌握栈、队列及二叉树等常用数据结构的使用方法和技巧。数据结构概述定义与研究内容数据结构主要研究数据的组织形式以及建立在这些组织形式之上的各种运算算法的实现。在程序设计中的重要性在程序设计中，数据是“原料”，合理的数据结构对提高程序设计技能至关重要。01栈导例：播报站名问题描述模拟播报北京公交1路由阜成门开往朝阳门途径站点。030201040506问题分析算法描述程序实现运行结果程序分析公交站点编号具有“后进先出”特点，采用顺序栈表示站点。依次将站点编号入栈，显示返程站点时退栈并显示对应站名。通过C语言代码实现顺序栈的建立与使用，模拟站点入栈和出栈操作。输出北京公交1路由阜成门开往朝阳门途径站点。该例便于读者理解栈“后进先出”的特点。导例：播报站名导例：播报站名#include<stdio.h>#defineMAXSIZE8//定义栈的结构体typedefstructnode/*声明顺序栈*/{ intstation[MAXSIZE];/*利用一维数组，存放栈中的各元素*/ inttop;/*表示栈顶元素的位置（下标）*/}SeqStack;/*顺序栈的类型名为SeqStack*/

voidStackInitiate(SeqStack*s);/*初始化顺序栈s*/intStackNotEmpty(SeqStack*s); /*判断顺序栈s非空否。非空返回1，否则返回0*/voidStackPush(SeqStack*s,intx); /*入栈，即把x压入顺序栈s中*/intStackPop(SeqStack*s); /*退栈，弹出顺序栈s栈顶的数据值*/

intmain(){ SeqStackmyStation;/*声明一个顺序栈myStation*/ inti,stationNumber; StackInitiate(&myStation);/*初始化顺序栈myStation*/ for(i=1;i<=7;i++) { StackPush(&myStation,i);/*调用入栈函数将站点编号压入栈中*/ } printf("北京公交1路由阜成门开往朝阳门途径站点如下：\n"); while(StackNotEmpty(&myStation)) { stationNumber=StackPop(&myStation);/*调用出栈函数，取栈顶站点编号*/ switch(stationNumber)/*利用分支语句，将站点编号显示为站名*/ { case1:printf("朝阳门\n");break; case2:printf("东四\n");break; case3:printf("灯市口\n");break; case4:printf("东安市场\n");break; case5:printf("北海\n");break; case6:printf("西四\n");break; case7:printf("阜成门\n");break; } }

}voidStackInitiate(SeqStack*s)/*初始化顺序栈s*/{ s->top=-1;}intStackNotEmpty(SeqStack*s) /*判断顺序栈s非空否。非空返回1，否则返回0*/{if(s->top<0)return0; elsereturn1;}voidStackPush(SeqStack*s,intx) /*入栈，即把x压入顺序栈s中*/{ s->top++; s->station[s->top]=x;

}intStackPop(SeqStack*s) /*退栈，弹出顺序栈s栈顶的数据值*/{ intx=s->station[s->top]; s->top--;returnx;}导例：简单编译器问题描述设计一个简单的编译器，检查输入字符串中“{”和“}”是否匹配。030201040506问题分析算法描述程序实现运行结果程序分析采用栈数据结构，根据栈的后进先出特性判断括号是否配对。扫描字符串，左括号入栈，右括号匹配时出栈，最后判断栈是否为空。使用C语言代码实现链栈的建立与使用，判断括号匹配情况。输出检测结果，如匹配正确、左括号多或右括号多。介绍链栈优点及使用方法，可尝试扩展判断不同种类括号的配对情况。导例：简单编译器导例：简单编译器#include<stdio.h>#include<stdlib.h>

typedefcharItem;structNode{Itemitem;structNode*

next;}LinkStack;

structNode*InitiateStack();/*初始化链栈*/intStackNotEmpty(structNode*S);/*判断链栈S非空否。非空返回1，否则返回0*/intStackPush(structNode*S,Itemitem);/*入栈，即把item压入链栈S中*/ItemStackPop(structNode*S);/*退栈，弹出链栈S栈顶的数据值*/ItemGetTop(structNode*S);/*取链栈S栈顶的数据值*/

intmain(){structNode*S=InitiateStack();//创建空栈inti;Itemitem;chara[100];printf("请输入待检测的字符串：\n");gets(a);for(i=0;a[i]!='\0';i++){ if((a[i]=='{')) { StackPush(S,a[i]);//入栈 }elseif((a[i]=='}')&&StackNotEmpty(S)==1){ item=StackPop(S); } elseif(((a[i]=='}'))&&StackNotEmpty(S)==0) { printf("检测结果：右括号多"); return0; }}if(StackNotEmpty(S)==1) printf("检测结果：左括号多"); else printf("检测结果：匹配正确");

//清理while(StackNotEmpty(S)){StackPop(S);}return0;}

structNode*InitiateStack(){structNode*S;S=(structNode*)malloc(sizeof(structNode));S->next=NULL;returnS;}

intStackNotEmpty(structNode*S){if(S->next==NULL)return0; elsereturn1;}

intStackPush(structNode*S,Itemitem){structNode*temp;temp=(structNode*)malloc(sizeof(structNode));if(temp==NULL){printf("Outofspace!\n");return0;}else{temp->item=item;temp->next=S->next;S->next=temp;return1;}}

ItemStackPop(structNode*S){structNode*top;Itemitem;if(StackNotEmpty(S)==0){printf("Stackisempty!\n");return-1;}else{top=S->next;item=top->item;S->next=top->next;free(top);returnitem;}}

ItemGetTop(structNode*S){if(StackNotEmpty(S)==1){returnS->next->item;}else{printf("Stackisempty!\n");return-1;}}栈的相关概念与基本操作栈的定义栈是一种运算受限的线性表，仅能在栈顶进行插入或删除操作，遵循后进先出原则。栈的基本操作置空栈初始化栈，使栈顶top值为-1。进栈从栈顶压入一个数据元素，栈中元素增加。退栈将栈顶元素从栈中弹出，栈顶元素改变。取栈顶元素取栈顶元素的值，栈顶元素不变。判断空栈若栈非空返回1，否则返回0。在顺序栈上实现基本操作存储结构由一维数组和记录栈顶元素位置的变量组成。操作实现通过C语言代码实现顺序栈的初始化、判断空栈、进栈、退栈和取栈顶元素等操作。在链栈上实现基本操作存储结构通过单链表实现，栈顶放在表头位置，不设置头结点。操作实现使用C语言代码实现链栈的构造空栈、判断空栈、进栈、退栈和取栈顶元素等操作。利用栈组织数据的基本特征01.结构特点栈是运算受限的线性表，遵循后进先出原则，分为顺序栈和链栈。02.顺序栈适合频繁访问栈顶元素的操作，链栈适合需要频繁调整大小的应用场景。栈在函数调用、表达式求值等方面有广泛应用。应用场景02队列导例：智能填写手机号问题描述实现一个简单的智能填写功能，识别字符串中的手机号码。030201040506问题分析算法描述程序实现运行结果程序分析手机号码具有连续数字字符且长度为11的特点，采用顺序队列区分手机号和其他数字。遍历字符串，保存数字字符，根据长度判断是否为手机号。实现使用C语言代码实现顺序队列的建立与使用，识别手机号码。输出识别出的手机号码。介绍顺序队列的使用方法，通过入队和出队操作处理数字字符。。导例：智能填写手机号导例：智能填写手机号#include<stdio.h>#include<stdlib.h>#defineSIZE50typedefcharDataType;typedefstructnode{ DataTypequeue[SIZE];/*利用一维数组，存放队列中的各元素*/ intfront;/*队头位置*/ intrear;/*队尾位置*/ intcount;}SeqCQueue;/*顺序队列的类型名为SeqCQueue*/voidQueueInitiate(SeqCQueue*Q);//初始化队列intQueueNotEmpty(SeqCQueue*Q);//判断队列是否为空，非空返回1，空返回0voidenqueue(SeqCQueue*Q,DataTypeelement);//入队操作DataTypedequeue(SeqCQueue*Q);//出队操作intmain(){ chars[100]; inti; SeqCQueuemobil; QueueInitiate(&mobil); printf("请输入信息：\n"); gets(s); for(i=0;s[i]!='\0';i++)//遍历字符串中的字符 { if(s[i]>='0'&&s[i]<='9')//是否为数字字符 enqueue(&mobil,s[i]);//入队 else if(mobil.count==11) break; else QueueInitiate(&mobil);//清空队列 } printf("您的手机号是："); while(QueueNotEmpty(&mobil)!=0)//输出队列内容 printf("%c",dequeue(&mobil));}voidQueueInitiate(SeqCQueue*Q)//初始化队列{ Q->front=0; Q->rear=0; Q->count=0;}intQueueNotEmpty(SeqCQueue*Q)//判断队列是否为空，非空返回1，空返回0{ if(Q->count!=0)return1; elsereturn0;}voidenqueue(SeqCQueue*Q,DataTypeelement)//入队操作{if(Q->front==Q->rear&&Q->count>0)printf("队列已满\n");else{Q->queue[Q->rear]=element;Q->rear=(Q->rear+1)%SIZE;Q->count++;}}DataTypedequeue(SeqCQueue*Q)//出队操作{DataTypex;x=Q->queue[Q->front];Q->front=(Q->front+1);Q->count--;returnx;}导例：解密电话号码问题描述帮助L同学解密M教授的电话号码。030201040506问题分析算法描述程序实现运行结果程序分析利用队列的先进先出原则，对加密号码进行解密。将加密号码入队，按规则进行出队和入队操作，得到解密号码。使用C语言代码实现链式队列的建立与使用，解密电话号码。输出解密后的电话号码。介绍链式队列的使用方法，通过入队和出队操作完成解密。导例：解密电话号码导例：解密电话号码#include<stdio.h>#include<stdlib.h>

typedefintDataType;typedefstructnode{DataTypestate;structnode*next;}Qnode; /*声明队列中结点类型*/

typedefstructQueue{Qnode*front;//队头指针Qnode*rear;//队尾指针intcount;//计数队列的长度}StateQueue; /*声明链队列的类型，名为StateQueue*/

StateQueue*QueueIniti(); /*置空队列*/intQueueNotEmpty(StateQueue*Q);/*判断队列是否为空，非空返回1，空返回0*/voidEnQueue(StateQueue*Q,DataTypeelement);/*入队操作*/DataTypeDeQueue(StateQueue*Q) ; /*出队操作*/

intmain(){ StateQueue*data; data=QueueIniti(); inti,x; intmi[11]={1,6,3,4,5,8,1,5,2,7,3}; for(i=0;i<11;i++) EnQueue(data,mi[i]); printf("M教授的电话号码为："); while(QueueNotEmpty(data)!=0) { printf("%d",DeQueue(data));//出队，输出 if(QueueNotEmpty(data)!=0) { x=DeQueue(data);//出队，存入x EnQueue(data,x);//x入队 } }return0;}StateQueue*QueueIniti() /*置空队列*/{StateQueue*q;q=(StateQueue*)malloc(sizeof(StateQueue));q->front=(Qnode*)malloc(sizeof(Qnode));q->front->next=NULL;q->rear=q->front;q->count=0;returnq;}

intQueueNotEmpty(StateQueue*Q)/*判断队列是否为空，非空返回1，空返回0*/{ return(Q->front!=Q->rear);}voidEnQueue(StateQueue*Q,DataTypeelement)/*入队操作*/{ Qnode*temp;temp=(Qnode*

)malloc(sizeof(Qnode));temp->state=element;temp->next=NULL; if(Q->rear==NULL) Q->front=Q->rear=temp; else{ Q->rear->next=temp; Q->rear=temp; } Q->count++;}

DataTypeDeQueue(StateQueue*Q) /*出队*/{DataTypex;Qnode*s;if(QueueNotEmpty(Q)==0){printf("队列空!\n");returnNULL;}s=Q->front->next;Q->front->next=s->next;if(s->next==NULL)Q->rear=Q->front;x=s->state;free(s);Q->count--;returnx;

}

队列的相关概念与基本操作队列的定义队列是一种运算受限的线性表，只能在队尾插入，队头删除，遵循先进先出原则。队列的基本操作置空队列初始化队列，使其不含任何数据元素。入队将新数据元素插入到队列的队尾。出队队头元素出队，队头元素改变。取队头元素取队列中的队头元素的值，队头元素不变。判断空队若队列空返回0，否则返回1。在顺序队列上实现基本操作存储结构由一维数组和记录队头、队尾元素位置的变量组成。操作实现通过C语言代码实现顺序队列的创建空队列、判队列空、入队、出队和取队头操作。假溢出问题顺序队列会出现假溢出，可采用循环队列解决。在链队列上实现基本操作存储结构通过单链表实现，增设头指针和尾指针。操作实现使用C语言代码实现链队列的创建空队列、判队列空、入队、出队和取队头元素等操作。利用队列组织数据的基本特征结构特点队列是操作受限的线性表，遵循先进先出原则，分为顺序队列和链式队列。顺序队列适合数据规模较小且固定的场景，链队列适合处理大规模数据。应用场景顺序队列会出现假溢出，通常采用循环队列；链式队列适用于处理大规模数据。队列在操作系统调度算法、广度优先搜索、网络请求处理、多线程管理和排队系统等方面有广泛应用，满足“先进先出”特性的问题可尝试用队列解决。03二叉树导例：统计叶子节点数目问题描述统计二叉树的叶子节点个数。030201040506问题分析算法描述程序实现运行结果程序分析叶子节点的特征是左子树和右子树均为空，采用结构体描述二叉树结点信息。递归创建二叉树，统计叶子节点个数。实现使用C语言代码实现二叉树的创建和叶子节点统计。输出二叉树的叶子节点个数。介绍统计叶子节点的方法和相关代码实现。导例：统计叶子节点数目导例：统计叶子节点数目#include<stdio.h>#include<stdlib.h>intleafcount=0;typedefstructTree{ chardata; structTree*Lchild; structTree*Rchild;}*BitTree;BitTreecreateTree(){ BitTreeT; chardata; chartemp; scanf("%c",&data); temp=getchar(); if(data=='.') { returnNULL; } else{ T=(BitTree)malloc(sizeof(Tree)); T->data=data; printf("请输入%c的左子树：",data); T->Lchild=createTree(); printf("请输入%c的右子树：",data); T->Rchild=createTree(); returnT; }}voidLeafcount(BitTreeT){ if(T==NULL)return; else { if(T->Lchild==NULL&&T->Rchild==NULL) leafcount++; Leafcount(T->Lchild); Leafcount(T->Rchild); } }

intmain(){ BitTreeS; printf("请输入根节点的数据："); S=createTree();//S接受创建好的二叉树

Leafcount(S); printf("leafcount=%d",leafcount); return0;}导例：动态查找问题描述以给定序列创建动态查找表，实现对指定数据的动态查找。030201040506问题分析算法描述程序实现运行结果程序分析采用二叉排序树实现动态查找，二叉排序树具有特定的性质。在二叉排序树中查找和插入结点，实现动态查找。使用C语言代码实现二叉排序树的创建和动态查找。运行结果输出原数据序列、建立的二叉排序树和中序遍历结果。输出解密后的电话号码。介绍动态查找表的创建过程、中序遍历特点和查找性能分析。导例：动态查找导例：动态查找#defineN50#include<stdio.h>#include<stdlib.h>typedefintDataType; /*DataType可以是任何类型，这里假设为char*/typedefstructnode{DataTypedata; /*二叉树中结点类型DataType*/structnode*lchild,*rchild; /*二叉树的左、右指针域*/ }LinkBTree; /*二叉链表的类型名为LinkBTree*/

LinkBTree*BstInsert(LinkBTree*bt,DataTypekey);voidInOrder(LinkBTree*bt);

voidmain(){DataTypearray[N]={60,21,83,46,74,12,57,98,35},n=9;LinkBTree*bt=NULL;inti;printf("\n原数据序列:");for(i=0;i<n;i++)printf("%4d",array[i]);

printf("\n建立二叉排序树......\n");for(i=0;i<n;i++)bt=BstInsert(bt,array[i]);

printf("\n中序遍历二叉排序树......\n");InOrder(bt);}voidLeafcount(BitTreeT){ if(T==NULL)return; else { if(T->Lchild==NULL&&T->Rchild==NULL) leafcount++; Leafcount(T->Lchild); Leafcount(T->Rchild); } }

intmain(){ BitTreeS; printf("请输入根节点的数据："); S=createTree();//S接受创建好的二叉树

Leafcount(S); printf("leafcount=%d",leafcount); return0;}二叉树的相关概念与基本操作二叉树的定义二叉树是n