1、第第11章章 算法和数据结构基础算法和数据结构基础结构设计之美结构设计之美哈尔滨工业大学哈尔滨工业大学12.1 从定长数组到动态数组从定长数组到动态数组n本节主要讨论如下问题：本节主要讨论如下问题：（1）什么是动态内存分配？如何进行动态内存分配？）什么是动态内存分配？如何进行动态内存分配？（2）常见的内存错误有哪些？如何避免这些内存错误？）常见的内存错误有哪些？如何避免这些内存错误？12.1.1 动态内存分配动态内存分配nC程序中变量的内存分配方式有以下程序中变量的内存分配方式有以下3种：种：（1）从静态存储区分配）从静态存储区分配（2）在栈上分配）在栈上分配（3）从堆上分配）从堆上分配1.函
2、数函数malloc()函数函数malloc()的原型为：的原型为：void *malloc(unsigned int size);2.函数函数calloc()函数函数calloc()的函数原型为：的函数原型为：void *calloc(unsigned int num,unsigned int size);3.函数函数free()函数函数free()的函数原型为：的函数原型为：void free(void*p);4.函数函数realloc()函数函数realloc()的函数原型为：的函数原型为：void *realloc(void*p,unsigned int size);12.1.1 动态内
3、存分配动态内存分配void*型指针型指针不指定其指向变量的类型，可指向任意类型的变量不指定其指向变量的类型，可指向任意类型的变量是一种是一种generic（通用）或（通用）或typeless（无类型）的指针（无类型）的指针 使用时，需强转使用时，需强转(Type*)为其他类型为其他类型12.1.1 动态内存分配动态内存分配void*malloc(unsigned int size);向系统申请向系统申请size字节的连续内存块，系统找到一块未占用的内存，将其标记为已占用，把首地址返回字节的连续内存块，系统找到一块未占用的内存，将其标记为已占用，把首地址返回p=(float*)malloc(n*
4、sizeof(float);free(p);/释放释放p指向的内存指向的内存l频繁申请频繁申请/释放，速度慢，易造成内存碎片释放，速度慢，易造成内存碎片l程序员不释放程序员不释放内存泄漏内存泄漏l释放仍继续使用释放仍继续使用野指针野指针freeheapn空指针空指针的用途的用途 l定义指针时进行初始化定义指针时进行初始化l在程序中常用作状态比较在程序中常用作状态比较n指针不能与非指针类型变量进行比较指针不能与非指针类型变量进行比较l但可与但可与NULL（即（即0值）进行相等或不等的关系运算值）进行相等或不等的关系运算 p=(int*)malloc(n*sizeof(int);if(p=NULL
5、)/判断内存申请是否成功判断内存申请是否成功 printf(No enough memory!n);exit(0);int*p;freeheapHeap（堆区）（堆区）若申请不成功则返回若申请不成功则返回12.1.1 动态内存分配动态内存分配【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽完为止，键或者学生名单中的学生全部抽完为止，要求每个学生最多只能被抽中一次，即不能被重复点到名字。要求每个学生最多只能
6、被抽中一次，即不能被重复点到名字。#include#include#include#include#define NO 120#define SIZE 30typedef struct char nameSIZE;short flag;/标记是否被点过名标记是否被点过名ROLL;int ReadFromFile(char fileName,ROLL msg);void MakeRollCall(ROLL msg,int total);int main(void)ROLL msgNO;/定长数组定长数组 char*fileName=student.txt;int total=ReadFromFi
7、le(fileName,msg);printf(总计总计%d名学生名学生n现在开始随机点名现在开始随机点名n,total);MakeRollCall(msg,total);/随机点名随机点名 return 0;12.1.2 动态数组实例动态数组实例随机点名随机点名使用定长的结构体数组来实现点名神器【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽完为止，键或者学生名单中的学生全部抽完为止，要求每个学生最多只
8、能被抽中一次，即不能被重复点到名字。要求每个学生最多只能被抽中一次，即不能被重复点到名字。12.1.2 动态数组实例动态数组实例随机点名随机点名/函数功能：从文件函数功能：从文件filename中读取名单存入数组中读取名单存入数组msgint ReadFromFile(char fileName,ROLL msg)FILE*fp=fopen(fileName,r);if(fp=NULL)printf(can not open file%sn,fileName);return 1;int i=0;while(fgets(msgi.name,sizeof(msgi.name),fp)i+;fclo
9、se(fp);return i;【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽完为止，键或者学生名单中的学生全部抽完为止，要求每个学生最多只能被抽中一次，即不能被重复点到名字。要求每个学生最多只能被抽中一次，即不能被重复点到名字。12.1.2 动态数组实例动态数组实例随机点名随机点名/函数功能：随机点名，总计名单中有函数功能：随机点名，总计名单中有total个学生个学生void MakeRollCall
10、(ROLL msg,int total)srand(time(NULL);for(int i=0;itotal;i+)msgi.flag=0;/标记都没有被点过标记都没有被点过 char ch=;int i=0;do int k=rand()%total;/随机确定被点名学生的下标随机确定被点名学生的下标 if(kbhit()&msgk.flag=0)/当有按键，并且第当有按键，并且第k个人也没有被点过个人也没有被点过 ch=getch();/等待用户按任意键，以回车符结束输入等待用户按任意键，以回车符结束输入 if(ch!=27)i+;printf(请第请第%d位同学回答问题：位同学回答问题
11、：%sn,i,msgk.name);msgk.flag=1;/标记其已经被点过标记其已经被点过 while(ch!=27&i total);if(ch=27)printf(点名结束点名结束n);else printf(所有同学均已点名完毕所有同学均已点名完毕n);【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽完为止，键或者学生名单中的学生全部抽完为止，要求每个学生最多只能被抽中一次，即不能被重复点到名字
12、。要求每个学生最多只能被抽中一次，即不能被重复点到名字。int main(void)int n;printf(How many students?);scanf(%d,&n);/输入学生人数输入学生人数 ROLL*msg=(ROLL*)malloc(n*sizeof(ROLL);/向系统申请内存向系统申请内存 if(msg=NULL)/确保指针使用前是非空指针，为空指针时结束程序运行确保指针使用前是非空指针，为空指针时结束程序运行 printf(No enough memory!n);exit(1);char*fileName=student.txt;int total=ReadFromFil
13、e(fileName,msg,n);printf(总计总计%d名学生名学生n现在开始随机点名现在开始随机点名n,total);MakeRollCall(msg,total);/随机点名随机点名 free(msg);/释放向系统申请的内存释放向系统申请的内存 return 0;12.1.2 动态数组实例动态数组实例随机点名随机点名使用一维动态数组来实现点名神器【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽
14、完为止，键或者学生名单中的学生全部抽完为止，要求每个学生最多只能被抽中一次，即不能被重复点到名字。要求每个学生最多只能被抽中一次，即不能被重复点到名字。/函数功能：从文件函数功能：从文件filename中读取名单存入数组中读取名单存入数组msg，返回名单中的实际人数，返回名单中的实际人数int ReadFromFile(char fileName,ROLL*msg,int n)FILE*fp=fopen(fileName,r);if(fp=NULL)printf(can not open file%sn,fileName);return 1;int i;for(i=0;in;i+)/读取你条记
15、录，若已经读到文件尾，则结束循环读取你条记录，若已经读到文件尾，则结束循环 if(!fgets(msgi.name,sizeof(msgi.name),fp)break;fclose(fp);return i;/返回名单中的实际人数返回名单中的实际人数12.1.2 动态数组实例动态数组实例随机点名随机点名【例例12.1】请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从请编写一个点名神器，从文件中读取学生名单，每按一次回车键，就从学生名单中随机抽取学生名单中随机抽取1个学生，直到按个学生，直到按ESC键或者学生名单中的学生全部抽完为止，键或者学生名单中的学生全部抽完为止，要求每个学
16、生最多只能被抽中一次，即不能被重复点到名字。要求每个学生最多只能被抽中一次，即不能被重复点到名字。/函数功能：随机点名，总计名单中有函数功能：随机点名，总计名单中有total个学生个学生void MakeRollCall(ROLL*msg,int total)srand(time(NULL);for(int i=0;itotal;i+)msgi.flag=0;/标记都没有被点过标记都没有被点过 char ch=;int i=0;do int k=rand()%total;/随机确定被点名学生的下标随机确定被点名学生的下标 if(kbhit()&msgk.flag=0)/当有按键，并且第当有按键
17、，并且第k个人也没有被点过个人也没有被点过 ch=getch();/等待用户按任意键，以回车符结束输入等待用户按任意键，以回车符结束输入 if(ch!=27)i+;printf(请第请第%d位同学回答问题：位同学回答问题：%sn,i,msgk.name);msgk.flag=1;/标记其已经被点过标记其已经被点过 while(ch!=27&i next!=NULL)/若未到表尾若未到表尾p=p-next;/pr指向下指向下一一节点节点 p-next=newP;/末节点指针指向新建节点末节点指针指向新建节点 newP=(struct link*)malloc(sizeof(struct link
18、);newP-data=nodeData;newP-next=NULL;12.2.2 单向链表的基本操作单向链表的基本操作n删除节点删除节点n分两种情况：空表、非空表（待删节点为头节点、非头节点）分两种情况：空表、非空表（待删节点为头节点、非头节点）datanextheaddatanext pr/找待删除节点while(p-data!=nodeData&p-next!=NULL)/未找到且未到表尾未找到且未到表尾pr=p;/在在pr中保存当前节点的指针中保存当前节点的指针 p=p-next;/p指向当前节点的下一节点指向当前节点的下一节点 p p12.2.2 单向链表的基本操作单向链表的基本操
19、作n分两种情况：空表、非空表（待删节点为头节点、非头节点）分两种情况：空表、非空表（待删节点为头节点、非头节点）若原链表为空表，则退出程序若原链表为空表，则退出程序 若待删节点若待删节点p是头节点，则将是头节点，则将head指向当前节点的后继节点即可指向当前节点的后继节点即可datanextheaddatanext pif(p-data=nodeData)/找到待删节点找到待删节点if(p=head)/若待删节点若待删节点p为头节点为头节点 head=p-next;/head指向待删除节点指向待删除节点p的后继节点的后继节点 else /若待删节点不是头节点若待删节点不是头节点 pr-next
20、=p-next;/前驱节点指向待删节点的后继前驱节点指向待删节点的后继 free(p);/释放为已删除节点分配的内存释放为已删除节点分配的内存12.2.2 单向链表的基本操作单向链表的基本操作若待删节点不是头节点，则若待删节点不是头节点，则前驱前驱节点指向节点指向后继后继节点节点datanextdatanextdatanext pdatanext若已搜到表尾若已搜到表尾（p-next=NULL）仍未找到待删仍未找到待删除节点，则显示除节点，则显示“未找到未找到”prif(p-data=nodeData)/找到待删节点找到待删节点if(p=head)/若待删节点若待删节点p为头节点为头节点 he
21、ad=p-next;/head指向待删除节点指向待删除节点p的后继节点的后继节点 else /若待删节点不是头节点若待删节点不是头节点 pr-next=p-next;/前驱节点指向待删节点的后继前驱节点指向待删节点的后继 free(p);/释放为已删除节点分配的内存释放为已删除节点分配的内存else /找到表尾仍未找到找到表尾仍未找到 printf(Not found!n);12.2.2 单向链表的基本操作单向链表的基本操作n在升序的链表中插入节点在升序的链表中插入节点n分两种情况：空表、非空有序表分两种情况：空表、非空有序表非空表分三种情况：在头节点前、中间节点、表尾节点后插入新节点非空表分
22、三种情况：在头节点前、中间节点、表尾节点后插入新节点n若原链表为空表，则将新节点若原链表为空表，则将新节点p作为头节点，让作为头节点，让head指向新节点指向新节点p headdata pif(head=NULL)/若原链表为空表若原链表为空表 head=p;/待插入节点作为头节点待插入节点作为头节点else/若原链表为非空若原链表为非空 /找待插入位置找待插入位置 while(nodeData pr-data&pr-next!=NULL)temp=pr;/在在temp中保存当前节点中保存当前节点的指针的指针pr=pr-next;/pr指向当前节点的后继指向当前节点的后继节点节点 p=(str
23、uct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;head12.2.2 单向链表的基本操作单向链表的基本操作nodeData next pdatanextdata prprtempp=(struct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;pr=head;if(head=NULL)/若原链表为空表若原链表为空表 head=p;/待插入节点作为头节点待插入节点作为头节点else/若原链表为非空若原链表为非空 /找待插入位置 while(
24、nodeData pr-data&pr-next!=NULL)temp=pr;/在在temp中保存当前节点中保存当前节点的指针的指针pr=pr-next;/pr指向当前节点的后继指向当前节点的后继节点节点 n若原链表非空，则若原链表非空，则按节点值大小（假按节点值大小（假设升序）确定插入设升序）确定插入新节点的位置新节点的位置12.2.2 单向链表的基本操作单向链表的基本操作headdatanext pdatanextdatanextdataif(nodeData data)/不在表尾插入不在表尾插入if(pr=head)/若在头节点前插入新节点若在头节点前插入新节点 p-next=head;
25、/将新节点指向链头将新节点指向链头 head=p;/head指向新节点指向新节点else /若在链表中间插入新节点若在链表中间插入新节点 pr=temp;p-next=pr-next;/新节点指向后继节点新节点指向后继节点 pr-next=p;/前驱节点指向新节点前驱节点指向新节点若在头节点前插入节点，则将新若在头节点前插入节点，则将新节点的指针域指向原链表的头节节点的指针域指向原链表的头节点点，且让且让head指向新节点指向新节点p=(struct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;prdatanext1
26、2.2.2 单向链表的基本操作单向链表的基本操作若在链表中间插入新节点，则将若在链表中间插入新节点，则将新节点的指针域指向下一节点且新节点的指针域指向下一节点且让前一节点的指针域指向新节点让前一节点的指针域指向新节点datanext pdatanextdatanextdataprtempif(nodeData data)/不在表尾插入不在表尾插入if(pr=head)/若在头节点前插入新节点若在头节点前插入新节点 p-next=head;/将新节点指向链头将新节点指向链头 head=p;/head指向新节点指向新节点else /若在链表中间插入新节点若在链表中间插入新节点 pr=temp;p-
27、next=pr-next;/新节点指向后继节点新节点指向后继节点 pr-next=p;/前驱节点指向新节点前驱节点指向新节点p=(struct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;prdatanext12.2.2 单向链表的基本操作单向链表的基本操作若在表尾插入新节点，则若在表尾插入新节点，则末节点指针域指向新节点末节点指针域指向新节点datanext pprdatanext/找待插入节点找待插入节点while(nodeData pr-data&pr-next!=NULL)temp=pr;pr=pr-next
28、;if(nodeData data)/不在表尾插入不在表尾插入 else/即即pr-next=NULL，表示若在表尾插入新节点表示若在表尾插入新节点pr-next=p;/末节点指向新节点末节点指向新节点 p=(struct link*)malloc(sizeof(struct link);p-data=nodeData;p-next=NULL;除尾节点的后继指针指向首节点外，均与单链表一致每个节点只包含一个指针，即后继指针/单向链表struct linkint data;struct link*next;/双向链表struct DNodeint data;struct DNode*prev;/
29、指向前驱指向前驱 struct DNode*next;/指向后继指向后继;12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题【例例12.212.2】据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大据说，鲁智深一天中午匆匆来到开封府大相国寺，想蹭顿饭吃，当时大相国寺有相国寺有9999个和尚，只做了个和尚，只做了9999个馒头，智清长老不愿得罪鲁智深，便把他安排在一个馒头，智清长老不愿得罪鲁智深，便把他安排在一个特定位置，之后对所有人说：从我开始报数（围成一圈），第个特定位置，之后对
30、所有人说：从我开始报数（围成一圈），第5 5个人可以吃到馒个人可以吃到馒头（并退下），按此方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上，请问他头（并退下），按此方法，所有和尚都吃到了馒头，唯独鲁智深没有吃上，请问他在哪个位置？在哪个位置？方法方法1：用一维数组实现/函数功能：用数组求解循环报数问题函数功能：用数组求解循环报数问题/函数参数：函数参数：n为参与报数的总人数，为参与报数的总人数，m表示每隔表示每隔m人有一人退出圈子人有一人退出圈子/函数返回值：返回剩下的最后一个人的编号函数返回值：返回剩下的最后一个人的编号int NumberOff(int n,int m)int i,c=0,c
31、ounter=0,aN;for(i=1;i=n;+i)/按从按从1到到n的顺序给每个人编号的顺序给每个人编号 ai=i;do for(i=1;i=n;+i)if(ai!=0)c+;/元素不为元素不为0,则则c加加1,记录报数的人数记录报数的人数 if(c%m=0)/c除以除以m的余数为的余数为0,说明此位置为第说明此位置为第m个报数的人个报数的人 ai=0;/将退出圈子的人的编号标记为将退出圈子的人的编号标记为0 counter+;/记录退出的人数记录退出的人数 while(counter!=n-1);/当退出圈子的人数达到当退出圈子的人数达到n-1人时结束循环，否则继续循环人时结束循环，否则
32、继续循环 for(i=1;i=n;+i)if(ai!=0)return i;return 0;方法方法1：用一维数组实现#include#define N 150typedef struct person int num;/自己的编号自己的编号 int nextp;/下一个人的编号下一个人的编号LINK;void CreatQueue(LINK link,int n);void CountsOff(LINK link,int n,int m);void PrtLastNum(LINK link,int n);int main(void)int m,n;LINK linkN+1;printf(I
33、nput n,m(nm):);scanf(%d,%d,&n,&m);CreatQueue(link,n);/n个人循环报数，报到个人循环报数，报到m出队，只留最后一个出队，只留最后一个 last=CountsOff(link,n,m);printf(n最后的成员是：最后的成员是：%dn,last);return 0;linklink0link1link2link3.linkN12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题方法2：用结构体数组实现静态循环链表void CreatQueue(LINK link,int n)int i;for(i=1;i=n;i+)li
34、nki.num=i;/从从1开始编号开始编号 if(i=n)/尾指向头尾指向头 linki.nextp=1;else linki.nextp=i+1;int CountsOff(LINK link,int n,int m)int h=n,i,j,last;printf(出圈成员及顺序：出圈成员及顺序：);for(j=1;jn;j+)/出队出队n-1人人 i=0;while(i!=m)/没有报到没有报到m h=linkh.nextp;/报下一个报下一个 if(linkh.num!=0)/越过越过0元素元素 i+;/报数计数报数计数 printf(%3d,linkh.num);linkh.num=
35、0;/出队元素标记为出队元素标记为0 for(i=1;im):);scanf(%d,%d,&n,&m);head=CreateLink(n);last=CountsOff(head,n,m);printf(最后的成员是：最后的成员是：%dn,last);DeleteMemory(head,n);return 0;12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题方法3：用单向链表实现动态循环链表LINK*CreateLink(int n)/加入了节点内存申请是否成功的判断加入了节点内存申请是否成功的判断 int i;LINK*p1,*p2,*head=NULL;for
36、(i=1;inext=p1;p1-num=i;p2=p1;p2-next=head;return head;void DeleteMemory(LINK*head,int n)LINK*p=head,*pr=NULL;int i;for(i=1;inext;free(pr);方法3：用单向链表实现动态循环链表12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题int CountsOff(LINK*head,int n,int m)/循环报数循环报数 int i,j;LINK*p1=head,*p2=p1;if(n=1|m=1)return 1;for(i=1;in;i+
37、)/删掉删掉n-1个节点个节点 for(j=1;jnext;p2=p1;/p2指向第指向第m个节点的前驱节点个节点的前驱节点 p1=p1-next;/p1指向待删除的节点指向待删除的节点 p1=p1-next;/p1指向待删除节点的后继节点指向待删除节点的后继节点 free(p2-next);/释放释放p2的后继节点（即待删除节点）的后继节点（即待删除节点）p2-next=p1;/让让p1成为成为p2的后继节点，即删掉第的后继节点，即删掉第m个节点个节点 return p1-num;方法3：用单向链表实现动态循环链表12.2.3单向循环链表应用实例单向循环链表应用实例循环报数问题循环报数问题小
38、结小结定长数组定长数组动态数组动态数组动态数据结构动态数据结构优点优点连续存储，随机访问连续存储，随机访问使用直观方便使用直观方便数据访问效率高数据访问效率高连续存储，随机访问，连续存储，随机访问，空间不浪费，可像数组空间不浪费，可像数组一样使用一样使用节省空间，无浪费节省空间，无浪费数据插入和删除效率高数据插入和删除效率高适用于适用于存储长度固定的数存储长度固定的数据集合据集合适用于长度在程序运行适用于长度在程序运行时才能确切知道的集合时才能确切知道的集合适用于长度在程序运行过适用于长度在程序运行过程中动态变化的集合程中动态变化的集合缺点缺点插入、删除操作效率低插入、删除操作效率低属于静态内
39、存分配，程序属于静态内存分配，程序一旦运行长度不能改变，一旦运行长度不能改变，若想改变，只能修改程序，若想改变，只能修改程序，按最大需求定义数组，浪按最大需求定义数组，浪费空间，还容易发生下标费空间，还容易发生下标越界越界程序员自己负责内存的程序员自己负责内存的分配和释放分配和释放频繁申请频繁申请/释放，速度慢释放，速度慢运行时间稍长后，还会运行时间稍长后，还会造成内存空间碎片化造成内存空间碎片化分散存储分散存储顺序访问，不可随机访问顺序访问，不可随机访问，数据访问效率低，数据访问效率低操作较为复杂操作较为复杂n静态数据结构和动态数据结构的区别静态数据结构和动态数据结构的区别12.3 限定性线
40、性表之栈和队列限定性线性表之栈和队列n本节主要讨论如下问题：本节主要讨论如下问题：（1）栈和队列两种数据结构各有什么不同的特点？）栈和队列两种数据结构各有什么不同的特点？（2）如何实现栈和队列的顺序存储和链式存储？）如何实现栈和队列的顺序存储和链式存储？n数组是一种数组是一种“连续存储、随机访问连续存储、随机访问”的线性表的线性表n链表则属于链表则属于“分散存储、连续访问分散存储、连续访问”的线性表的线性表它们的每个数据都有其相对位置，有至多一个直接前驱和至多一个直接后继它们的每个数据都有其相对位置，有至多一个直接前驱和至多一个直接后继n栈和队列也属于线性表，但它们都是运算受限的线性表，也称限
41、定栈和队列也属于线性表，但它们都是运算受限的线性表，也称限定性线性表。性线性表。栈限定数据只能在栈顶执行插入（入栈）和删除（出栈）操作。栈限定数据只能在栈顶执行插入（入栈）和删除（出栈）操作。队列限定只能队头执行删除操作（出队），在队尾执行插入操作（入队）。队列限定只能队头执行删除操作（出队），在队尾执行插入操作（入队）。12.3.1 栈的应用实例栈的应用实例再谈回文诗再谈回文诗n栈是一种特殊的线性表，只允许在线性表的顶端执行数据的增删操作，对栈进栈是一种特殊的线性表，只允许在线性表的顶端执行数据的增删操作，对栈进行运算的一端称为栈顶（行运算的一端称为栈顶（top），栈顶的第一个元素称为栈顶元
42、素），栈顶的第一个元素称为栈顶元素n常用的堆栈运算包括：常用的堆栈运算包括：n（1）压入堆栈（）压入堆栈（Push），简称压栈，即向一个栈中插入新元素，即把该元素），简称压栈，即向一个栈中插入新元素，即把该元素放到栈顶元素的上面，使其成为新的栈顶元素；放到栈顶元素的上面，使其成为新的栈顶元素；n（2）弹出堆栈（）弹出堆栈（Pop），简称弹栈，即从一个栈中删除元素，使原栈顶元素下），简称弹栈，即从一个栈中删除元素，使原栈顶元素下方的相邻元素成为新的栈顶元素。方的相邻元素成为新的栈顶元素。/函数功能：判断回文字符串函数功能：判断回文字符串int IsPlalindrome(const char s
43、tr)char revN;Reverse(str,rev);/计算字符串计算字符串str的逆序字符串的逆序字符串rev return strcmp(str,rev)=0?1:0;/函数功能：采用字符数组做函数参数实现字符串逆序函数功能：采用字符数组做函数参数实现字符串逆序void Reverse(const char str,char rev)int i;int len=strlen(str);STACK s;InitStack(&s);/初始化栈初始化栈top为为-1 for(i=0;ilen;i+)Push(&s,stri);/字符依次压栈字符依次压栈 for(i=0;itop=s-top
44、+1;/更新栈顶更新栈顶 s-datas-top=data;/给新栈顶元素赋值给新栈顶元素赋值)return 1;12.3.1 栈的应用实例栈的应用实例再谈回文诗再谈回文诗n【例例12.3】采用栈这种数据结构，重新编写例采用栈这种数据结构，重新编写例10.5的判断回文字符的判断回文字符串的程序。串的程序。/函数功能：从堆栈函数功能：从堆栈stack中弹出栈顶数据中弹出栈顶数据int Pop(STACK*s,char*data)if(EmptyStack(s)/判断栈是否为空判断栈是否为空 printf(stack is empty!n);return 0;*data=s-datas-top;/
45、弹出栈顶元素，对应图弹出栈顶元素，对应图12-19(d)s-top=s-top-1;/更新栈顶，对应图更新栈顶，对应图12-19(e)return 1;12.3.1 栈的应用实例栈的应用实例再谈回文诗再谈回文诗n【例例12.3】采用栈这种数据结构，重新编写例采用栈这种数据结构，重新编写例10.5的判断回文字符的判断回文字符串的程序。串的程序。/函数功能：判断栈是否为空函数功能：判断栈是否为空int EmptyStack(STACK*s)return s-top=-1?1:0;/函数功能：判断栈是否已满函数功能：判断栈是否已满int FullStack(STACK*s)return s-top=
46、N-1?1:0;/函数功能：初始化栈函数功能：初始化栈void InitStack(STACK*s)s-top=-1;/初始化栈初始化栈top为为-112.3.1 栈的应用实例栈的应用实例再谈回文诗再谈回文诗n【例例12.3】采用栈这种数据结构，重新编写例采用栈这种数据结构，重新编写例10.5的判断回文字符的判断回文字符串的程序。串的程序。typedef struct stack char dataN;/每个元素保存一个字符每个元素保存一个字符 int top;/指示栈顶指示栈顶 STACK;int main(void)char aN;printf(Input a string:);gets(
47、a);if(IsPlalindrome(a)/判断是否是回文判断是否是回文 printf(Yesn);else printf(Non);return 0;/函数功能：判断回文字符串函数功能：判断回文字符串int IsPlalindrome(const char str)char revN;Reverse(str,rev);/计算字符串计算字符串str的逆序字符串的逆序字符串rev return strcmp(str,rev)=0?1:0;/函数功能：采用字符数组做函数参数实现字符串逆序函数功能：采用字符数组做函数参数实现字符串逆序void Reverse(const char str,char
48、 rev)int i;int len=strlen(str);STACK*top=InitStack(top);/初始化栈初始化栈top指向指向NULL for(i=0;ilen;i+)top=Push(top,stri);/字符依次压栈字符依次压栈 for(i=0;idata=data;/给新节点赋值给新节点赋值 p-next=top;/新节点链接到原栈顶指针，对应图新节点链接到原栈顶指针，对应图12-20(b)top=p;/更新栈顶指针指向新节点，对应图更新栈顶指针指向新节点，对应图12-20(c)return top;/返回新的栈顶指针返回新的栈顶指针12.3.1 栈的应用实例栈的应用实
49、例再谈回文诗再谈回文诗n【例例12.3】采用栈这种数据结构，重新编写例采用栈这种数据结构，重新编写例10.5的判断回文字符的判断回文字符串的程序。串的程序。/函数功能：从堆栈函数功能：从堆栈stack中弹出栈顶数据中弹出栈顶数据STACK*Pop(STACK*top,char*data)if(EmptyStack(top)/判断栈是否为空判断栈是否为空 printf(stack is empty!n);return NULL;STACK*p=top;/让让p指向栈顶，对应图指向栈顶，对应图12-20(d)*data=p-data;/弹出栈顶数据弹出栈顶数据 top=top-next;/更新栈顶
50、指针，对应图更新栈顶指针，对应图12-20(e)free(p);/释放删除的节点，对应图释放删除的节点，对应图12-20(f)return top;/返回新的栈顶指针返回新的栈顶指针12.3.1 栈的应用实例栈的应用实例再谈回文诗再谈回文诗n【例例12.3】采用栈这种数据结构，重新编写例采用栈这种数据结构，重新编写例10.5的判断回文字符的判断回文字符串的程序。串的程序。/函数功能：判断栈是否为空函数功能：判断栈是否为空int EmptyStack(STACK*top)return(top=NULL)?1:0;/函数功能：初始化栈函数功能：初始化栈STACK*InitStack(STACK*t
