第一篇：数据结构教案C语言版
课程教案
课程名称：
数据结构 授课教师：
学习对象：
任课时间：
一、学生情况分析
数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。
二、课程教学目标
《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。
三、课程教学内容
第一章 绪论
教学内容：
1）什么是数据结构
2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言
3）数据结构的抽象层次 4）算法定义
5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求：
了解：数据结构基本概念及数据结构的抽象层次
了解：抽象数据类型概念
了解：算法的定义及算法特性
掌握：算法的性能分析与度量方法 第二章 线性表
教学内容：
1）线性表的定义和特点
2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例 教学要求：
了解：线性表的定义和特点
熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法 第三章 栈和队列
教学内容：
1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链式存储表示
2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链式存储表示 3）队列的应用举例 教学要求：
熟练掌握：栈的定义及实现 熟练掌握：队列的定义及实现
掌握：能运用栈和队列解决简单实际问题 第四章 串
教学:内容：
1)字符串的抽象数据类型 2)字符串操作的实现 3)字符串的模式匹配 教学要求：
熟练掌握：字符串的定义方式
熟练掌握：字符串的各种操作的实现 了解：字符串的模式匹配算法 第五章 数组和广义表
教学:内容：
1)数组的定义和初始化
2)作为抽象数据类型的数组的顺序存储方式 教学要求：
了解：作为抽象数据类型的数组的定义 熟练掌握：顺序表的数组定义方式及实现 第六章 树和二叉树
教学内容：
1)树和森林的概念：树的定义；树的术语；树的抽象数据类型；森林的概念 2)二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 3)二叉树的表示：数组表示；链表存储表示
4)二叉树的遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的实例；二叉树的中序非递归算法
5)线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化
6)树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历 7)二叉树的计数
8)霍夫曼树：路径长度；霍夫曼树；霍夫曼树编码 教学要求：
了解：树和森林的概念
掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法
掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法 掌握：树和森林的实现及遍历方法
掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法 掌握：霍夫曼树的实现方法及霍夫曼编码的概念 第七章 图
教学内容：
1）图的基本概念：图的基本概念；图的抽象数据类型 2）图的存储表示：邻接矩阵；邻接表；邻接多重表
3）图的遍历与连通性；深度优先搜索；广度优先搜索；连通分量 4）最小生成树：克鲁斯卡尔算法；普里姆算法 教学要求：
掌握：图的基本概念和图的存储表示
熟练掌握：图的两种遍历方法与求解连通性问题的方法 掌握：构造最小生成树的Prim和Kruskal方法 第九章 查找
教学内容：
1)静态查找表：顺序表的查找；有序表的查找；索引顺序表的查找 2)二叉排序树：二叉排序树上的搜索、插入和删除 教学要求：
熟练掌握：静态搜索表的顺序搜索和折半搜索方法
熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法 第十章 内部排序
教学内容：
1)概述
2)插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序 3)选择排序：直接选择排序；堆排序 教学要求：
掌握：排序的基本概念和性能分析方法
掌握：插入排序、选择排序、等内排序的方法及性能分析方法
单元名称：第 一 讲：绪论
一、教学目标
1.了解《数据结构》课程的体系结构 2.掌握本章介绍的各种基本概念和术语 3.了解数据结构的二元组表示
4.掌握逻辑结构与物理结构之间的映像关系。
二、重点与难点
重点：数据结构的基本概念；逻辑结构与物理结构之间的映像关系。难点：逻辑结构与物理结构之间的映像关系。
三、教学内容与教学过程
介绍本学期课程的内容及安排
本课程是计算机专业的重要专业课之一，主要介绍常用的数据结构以及相关算法。本课程主要讲授线性表、栈和队列、串、数组、树和二叉树、图、查找、排序等内容。
成绩考核方式为：期末成绩+平时成绩，其中期末成绩占70%，平时成绩占 30%，平时成绩为：作业成绩+出勤率+上机成绩。
讲授新课
1.1 什么是数据结构
讲解：（数据结构课程的研究背景）
从计算机最初以数值计算为主到大量非数值计算出现引出数据结构。
讲解：（数据结构课程的研究对象）
例1-1图书馆的书目检索系统自动化问题。1-2计算机和人机对奕问题
1-3多叉路口交通灯的管理问题 总结：
从以上三个例子可以看出，描述这类非数值计算问题的数学模型不再是数学方程，而 是诸如线性表、树和图等之类的数据结构，这些都是数据结构课程的研究对象。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。
介绍数据结构课程的发展以及与其他课程之间的关系。
1.2基本概念和术语
基本概念：数据、数据元素、数据项、数据对象、数据结构、结构
（1）常见基本结构（逻辑结构）：集合、线性结构、树形结构、图状结构或网状结构 数据结构的形式定义：
数据结构一般用一个二元组来表示： Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上的关系的有限集
DS表示一种数据结构，它由数据元素集合K和在K上定义的一种二元关系的集合R所组成。其中：
K{Ki|0in,n0}是数据元素的有限集合，n为DS中数据元素的个数。
R{Rj|0jm,m0}的取值为1。
是K上关系的有限集合，m为K上关系的个数，通常情况下mK上任何一个二元关系Rj是序偶的集合。对于Rj中的任一序偶
数据结构中的数据元素和数据元素之间的关系还可以用图形直观地表示出来。图形中的每个结点对应一个数据元素，两结点之间带箭头的连线对应二元关系中的一个序偶，其中序偶的第一个元素称为弧尾，第二个元素称为弧头。举例讲解：
例
数据结构line={K，R}，其中K={01，02，03，04，05，06，07，08，09，10}，R={r}，r={<01，02>，<02，03>，<03，04>,<04，05>，<05，06>，<06，07>，<07，08>，<08，09>，<09，10>}。
例数据结构tree={K，R}，其中K={01，02，03，04，05，06，07，08，09，10}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<04，07>，<04，08>，<06，09>，<06，10>}。
例 数据结构graph={K，R}，其中K={01，02，03，04，05}，R={r}，r={<01，02>，<02，01>，<01，04>，<04，01>，<01，03>，<03，01>，<02，04>，<04，02>，<03，05>，<05，03>}。
介绍常见数据结构（集合、线性结构、树型结构、图型结构）具体表示方式(2)逻辑结构
上述数据结构的定义是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。根据这种逻辑关系通常将数据结构划分为线性结构和非线性结构，其中非线性结构又分为树型结构和图型结构。
(3)物理结构
数据结构在计算机中的表示（存储映象）称为数据的物理结构或存储结构，它涉及到数据元素及其相互关系在计算机内部的表示形式。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。根据数据元素相互之间的关系在计算机中的表示形式将数据的物理结构划分为顺序结构和链式结构。
顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
注意：数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据的逻辑结构，而算法的实现依赖于采用的存储结构。
（4）数据结构一般包括三方面内容：
数据的逻辑结构、数据的存储结构、数据的运算
（举例讲解）小结： 总结本讲的主要内容
四、作业布置
见习题集
单元名称：第 二 讲：线性表的类型定义，线性表的顺序存储
一、教学目标
掌握线性表的顺序表示和实现
二、重点与难点
线性表的顺序表示和实现。
三、教学过程的具体安排
讲授新课
2.1线性表的类型定义
线性表的定义：一个线性表是n 个数据元素的有限序列。其中每个数据元素的具体含义，在不同的情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属于同一数据对象。例如：26个英文字母表；学生健康情况登记表（图2.1）等。
例如线性表（a1,…,ai-1,ai,ai+1,…,an），称ai-1是ai的直接前驱元素，ai+1是 ai的直接后继。引导学生自己总结线性结构的特点。
线性表的长度：线性表中元素的个数（n≥0），n=0为空表。线性表中数据元素的位序（如数据元素ai在线性表中的位序为i）。
抽象数据类型线性表的定义：
讲解定义中的数据对象，数据关系以及基本操作（教材P19），重点讲解常用的基本操作含义。
通过示例2-1，2-2讲解更复杂的基本操作，并分析时间复杂度。2.2 线性表的顺序表示和实现
（1）线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。
（2）顺序储存的地址关系：假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(a i+1)和第i个数据元素的存储位置LOC(a i)之间满足下列关系：
LOC(a i+1)=LOC(a i)+l
线性表的第i个数据元素ai的存储位置为：
LOC(ai)=LOC(a1)+(i-1)*l，其中LOC(a1)为线性表的基地址。
（3）顺序表及其特点, 顺序储存结构是一种随机存取的存储结构。（4）线性表的动态分配顺序存储结构。
#define LIST_INIT_SIZE
#define LISTINCREMENT 10 Typedef struct { ElemType *elem;int
length;int
listsize;}SqList;(1)基于顺序存储结构的基本操作的实现
主要介绍下面的基本操作并且分析时间复杂度。
InitList_Sq(SqList &L);ListInsert_Sq(SqList &L, int i, ElemType e);
ListDelete_Sq(SqList &L, int i, ElemType &e);LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));MergeList_Sq(SqList La,SqList Lb, SqList &Lc);重点讲解：
顺序存储结构上实现线性表的插入操作
12i1ii1n，为了保证线性表的有序性，当在位设线性表置i1in1之前插入一个新的数据元素x时，需要将第i个到第n个数据元Aa,a,,a,a,a,,a素均向后移动一个位置，然后将数据元素x存储到第i个位置上并改变线性表的长度。
Status ListInsert_Sq(SqList &L, int i, ElemType e){ // 在顺序线性表L的第i个元素之前插入新的元素e，// i的合法值为1≤i≤Listlength_Sq(L)+1
if(i < 1 || i > L.length+1)return ERROR;// 插入位置不合法 if(L.length >= L.listsize){// 当前存储空间已满，增加分配
newbase =(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);// 存储分配失败 L.elem = newbase;// 新基址
L.listsize += LISTINCREMENT;// 增加存储容量 } q = &(L.elem[i-1]);// q指示插入位置
for(p = &(L.elem[L.length-1]);p >= q;--p)*(p+1)= *p;// 插入位置及之后的元素右移 *q = e;// 插入e ++L.length;// 表长增1 return OK;} // ListInsert_Sq
平均时间复杂度分析：f(n)(012n)/(n1)n/2O(n)
顺序存储结构上实现线性表的删除操作
12i1ii1n，设线性表为了保证线性表的有序性,当删除第i(1in)个位置上的元素后，需要将第i+1个到第n个数据元素均向前移动Aa,a,,a,a,a,,a一个位置并改变线性表的长度。
Status ListDelete_Sq(SqList &L, int i, ElemType &e){ // 在顺序线性表L中删除第i个元素，并用e返回其值。// i的合法值为1≤i≤ListLength_Sq(L)
if((i < 1)||(i > L.length))return ERROR;// 删除位置不合法 p = &(L.elem[i-1]);
// p为被删除元素的位置 e = *p;
// 被删除元素的值赋给e q = L.elem+L.length-1;// 表尾元素的位置
for(++p;p <= q;++p)*(p-1)= *p;// 被删除元素之后的元素左移--L.length;// 表长减1 return OK;} // ListDelete_Sq
平均时间复杂度分析：f(n)(012(n1))/nn1/2O(n)总结： 顺序存储结构的优缺点 顺序结构的优点是结构简单，对数据元素既可以实现顺序访问，又可以实现随机访问；缺点是插入和删除操作需要移动大量的数据元素。
小结：本讲主要介绍了线性表的逻辑结构定义和基本运算，线性表的插入和删除操作在顺序存储结构上的实现。
小结：总结本讲的主要内容
四、作业布置
见习题集
实验作业见实验指导
单元名称：第 三 讲：线性表链式存储
一、教学目标
掌握单链表的表示和实现
二、重点与难点
单链表的存储结构和基本操作实现。
三、教学内容与教学过程
复习线性表的顺序存储结构的特点引入另一种表示方法链式存储结构。
讲授新课
2.3.1线性链表（1）线性链表
线性链表：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。
线性链表的存储结构：
以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素
或
数据元素的映象)，其中指针域只有一个。
举例讲解：教材图2.5 线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。
有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。线性表为空时，头结点的指针域为空。举例如图2.7.线性表的单链表存储结构的C语言描述： typedef struc LNode{ // 定义单链表结点
ElemType
data;
struct LNode
*next；
// 指向后继的指针域 }LNode, *LinkList； 单链表操作的实现：
GetElem(L, i, e)
// 取第i个数据元素 ListInsert(&L, i, e)
// 插入数据元素
ListDele CreateList(&L, n)// 生成含 n 个数据元素的链表 CreateList(&L, n)// 生成含 n 个数据元素的链表 MergeList(&La,&Lb,&Lc)//合并两个有序链表
(1)建立单链表（要求从头部插入）void CreateList_L(LinkList &L, int n){
// 逆位序输入n个元素的值，建立带表头结点的单链线性表L。L =(LinkList)malloc(sizeof(LNode));L->next = NULL;// 先建立一个带头结点的单链表 for(i = n;i > 0;--i){
p =(LinkList)malloc(sizeof(LNode));// 生成新结点 scanf(&p->data);// 输入元素值
p->next = L->next;L->next = p;// 插入到表头 } } // CreateList_L 注：从头部插入元素建立单向链表得到的线性序列为输入序列的逆序列。(2)建立单链表（要求从尾部插入）void CreateList_L(LinkList &L, int n){
//正位序输入n个元素的值，建立带表头结点的单链线性表L。L =(LinkList)malloc(sizeof(LNode));r = L;L->next = NULL;// 先建立一个带头结点的单链表 for(i = n;i > 0;--i){
p =(LinkList)malloc(sizeof(LNode));// 生成新结点 scanf(&p->data);// 输入元素值
p->next=r->next;r->next=p;r = p;// 插入到表尾 } } // CreateList_L(3)在带头结点的单链表中插入结点
分析：设在结点a和结点b之间插入数据为x的结点，通过图来分析则插入前和插入后的情况。
Status ListInsert_L(LinkList L, int i, ElemType e){ // 在带头结头的单链表L中第i位置之前插入元素e p = L;j = 0;while(p && j < i-1){ p = p->next;++j;} // 寻找第i-1个结点 if(!p || j > i-1)return ERROR;// i小于1或者大于表长 s =(LinkList)malloc(sizeof(LNode));// 生成新结点 s->data = e;s->next = p->next;// 插入L中 p->next = s;return OK;} // LinstInsert_L(4)在带头结点的单链表中删除结点
Status ListDelete_L(LinkList L, int i, ElemType &e){ p = L;j = 0;while(p->next && j < i-1){ p = p->next;++j;} //寻找第i个结点并令p指向其前趋
if(!(p->next)|| j > i-1)return ERROR;// 删除位置不合理 q = p->next;p->next = q->next;// 删除并释放结点 e = q->data;free(q);return OK;} // ListDelete_L 注：上述两个算法的时间复杂度均为O(n)。单链表的优点：
它是一种动态结构，整个存储空间为多个链表共用
不需预先分配空间
插入、删除操作方便 单链表的缺点：
指针占用额外存储空间
不能随机存取，查找速度慢 小结：本讲主要介绍了单链表的存储结构，以及的基本操作（建立、插入和删除）的实现。
四、作业布置
见习题集
实验作业见实验指导。
第四讲 循环链表，双向链表，链表应用
一、教学目标
1．了解循环链表和的基本概念；
2．掌握双向链表的插入和删除操作；
3．掌握一元多项式的表示及加法在链式存储结构上的实现。
二、重点与难点
双向链表的存储结构和基本操作实现。
三、教学内容与教学过程
讲授新课 单向循环链表 设指针p指向单向链表中最后一个结点，则p->next的值是0，表示该结点是单向链表的最后一个结点。如果将单向链表中的最后一个结点的指针域改为存放单向链表中第一个结点的地址值，使得整个线性链表构成一个环，则称这种线性链表为单向循环链表。设p指向单向循环链表中的最后一个结点，则p->next的值不是0而是等于指向循环链表中的第一个结点head的值。双向链表
如果链表中的每个结点都有两个指针域，分别指向其前驱结点和后继结点，则称这种链表为双向链表。双向链表中的结点类型描述如下：
typedef struct DuLNode {
ElemType data;
// 数据域
struct DuLNode *prior;// 指向前驱的指针域 struct DuLNode *next;// 指向后继的指针域 } DuLNode, *DuLinkList;设指针p指向双向链表中的某个结点，则显然有以下的结论： p->prior->next==p==p->next->prior(1)双向链表的插入操作
设指针变量p指向双向链表中的结点A，指针变量q指向被插入的新结点B，则在结点A的后面插入结点B的操作序列为：
(1)q->next=p->next；
(2)p->next->prior=q；(3)p->next=q；
(4)q->prior=p；
(2)双向链表的删除操作
设指针变量p指向双向链表中被删除的结点X，则删除结点X的操作序列为：(1)p->prior->next=p->next；
(2)p->next->prior=p->prior；
(3)free(p)；
注：在双向链表或双向循环链表中进行插入和删除操作时，尤其要注意修改有关结点指针域的操作次序，以免丢失链域信息而造成链表中断的错误。链式存储结构的应用：一元多项式的表示及相加
一元多项式Pn(x)可按升幂写成：
2n
Pn(x)P0Px1P2xPnx它由n+1个系数唯一确定。在计算机中，可用一个线性表P来表示：
P(P0,P1,P2,,Pn)
每项系数i隐含在系数Pi的序号里。
若Qm(x)为一个一元多项式，同样用线性表Q表示：
Q(Q0,Q1,Q2,,Qm)
这两个多项式可以相加，结果为Rn(x)Pn(x)Qm(x)，其中设nm，则用线性表表示R为： R(P0Q0,P1Q1,P2Q2,,PmQm,Pm1,,Pn)
我们可以采用顺序存储结构存放P、Q和R，使得多项式相加算法定义十分简介。然而，在通常的应用中，多项式的次数很高且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如S(x)=1+3x10001+2x20000的多项式时，要用长度为20001的线性表来表示。如果对每个元素使用两个数据项，一个为系数项，另一个为指数项，则这样构成的线性表可表示成：
P((P0,e0),(P1,e1),(P2,e2),,(Pn,en))
因此上式S(x)可表示成((1, 0),(3, 1001),(2, 20000))。显然这样的线性表应采用链式存储结构。课本 P41 图2.17中两个线性链表分别表示一元多项式A(x)=7+3x+9x8+5x11和一元多项式B(x)=8x+22x7-9x8，由这两个多项式得到的和多项式如图课本 P412.18所示。
用链表表示多项式时，链表中的数据类型描述成： typedef struct polynomial{ float coef;int expn;
struct polynomial *next;}ElemType;根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成和多项式中的一项；对于两个一元多项式中所有指数不相同的项则分别抄到和多项式中去。
第一步：分别从A表和B表的表头开始，根据比较pa->expn和pb->expn的比较结果分三种情况讨论，直到A表或B表全部处理完。
(1)pa->expn==pb->expn：则相加此两项的系数，如果相加后该项系数不等于0，则在C表中生成一个新结点存放该项，修改pa和pb使其指向各自的下一个结点。
(2)pa->expn > pb->expn：则复制A表中pa所指向的结点到C表中，修改pa使其指向下一个结点。
(3)pa->expn < pb->expn：则复制B表中pb所指向的结点到C表中，修改pb使其指向下一个结点。
第二步：若B表没有处理完，将B表中剩余结点复制到C表中；反之则将A表中剩余结点复制到C表中。
void create_item(LinkList &pc,float coef,int expn){ p=(LinkList)malloc(sizeof(LNode));p->coef=coef;p->expn=expn;pc->next=p;pc=p;} void ploy_add(LinkList pah,LinkList pbh,LinkList &pch){ pa = pah;pb = pbh;pc = pch=(LinkList *)malloc(sizeof(LNode));// 为c链表添加一个头结点 while(pa!=0 && pb!=0){ if(pa->expn==pb->expn){ x=pa->coef+pb->coef;if(x!=0)create_item(pc,x,pa->expn);pa=pa->next;pb=pb->next;} else if(pa->expn>pb->expn){ create_item(pc,pa->coef,pa->expn);pa=pa->next;} else {create_item(pc,pb->coef,pb->expn);pb=pb->next;} } while(pa!=0){create_item(pc,pa->coef,pa->expn);pa=pa->next;} while(pb!=0){create_item(pc,pb->coef,pb->expn);pb=pb->next;} pc->next=0;pc=pch;pch=pch->next;free(pc);/* 释放c链中的头结点 */ }
小结：本讲主要介绍了循环链表和双向链表的基本概念，双向链表的插入和删除操作，一元多项式的表示及相加在链式存储结构上的实现。
四、作业布置
见习题集
实验作业见实验指导。
单元名称：第 五 讲：栈
一、教学目标
1．了解栈的基本概念和基本操作；
2．掌握栈的基本操作在两种存储结构上的实现。
二、重点与难点
栈的基本操作在两种存储结构上实现。
三、教学内容与教学过程
首先复习线性表的知识，引入限定性的数据结构栈和队列。讲授新课 3.1 栈
3.1.1 抽象数据类型栈的定义
栈：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。
通过教材P44的图3.1讲解栈顶，栈底以及栈后进先出的特点。栈的抽象数据类型定义： ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{
基本操作：
InitStack(&S)StackEmpty(S)Push(&S, e)
DestroyStack(&S)
StackLength(S)
ClearStack(&S)
GetTop(S, &e)
Pop(&S, &e)
} ADT Stack 3.1.2 栈的表示和实现 顺序栈
类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。
栈的顺序存储表示：
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT
10;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;顺序栈的基本操作的算法描述：
初始化，返回栈顶元素，入栈，出栈。(a)栈空栈满条件 栈空条件：top=base 栈满条件：base-top=stacksize(b)入栈操作
Status Push(SqStack &S, SElemType e){ if(S.top-S.base>=S.stacksize){ S.base=(SElemType*)realloc
(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;} *S.top++ = e;return OK;}(c)出栈操作
Status Pop(SqStack &S, SElemType &e){ if(S.top==S.base)return ERROR;e=*--S.top;return OK;}
链栈：栈的链式存储结构。栈顶指针就是链表的头指针
栈的链式存储结构类似单链表的存储结构，链表中第一个结点表示栈顶，最后一个结点表示栈底。由于链表的长度可以动态增长，因此进行入栈操作时无需考虑栈的上溢，但进行出栈操作时，必需考虑栈的下溢，下溢的条件是top的值为0。
链式栈的入栈操作
Status Push(LinkList &top, ElemType x){ p=(LinkList *)malloc(sizeof(LNode));p->data=x;p->next=top;top=p;return OK;}(2)链式栈的出栈操作
Status Pop(LinkStack &top, ElemTye &y){ if(top==0)return ERROR;p=top;y=p->data;top=p->next;free(p);return OK;} 小结；本讲主要介绍了栈的基本概念，栈的基本运算，栈在顺序存储结构和链式存储结构上实现基本操作。
四、作业布置
见习题集
实验作业见实验指导。
单元名称：第 六 讲：队列
一、教学目标
1．了解栈的基本概念和基本操作；
2．掌握栈的基本操作在两种存储结构上的实现。
二、重点与难点
栈的基本操作在两种存储结构上实现。
三、教学内容与教学过程
讲授新课 队列的基本概念
队列是一种限制所有插入操作在线性表的一端进行，而所有的删除操作在线性表的另一端进行的特殊线性表。允许插入（入队）操作的一端称为队尾，允许删除（出队）操作的一端称为队头。
设队列为q(a1,a2,,an)，则a1是队头元素，an是队尾元素。队列中的元素按照a1,a2,,an的顺序进入队列的，退出队列也只能按照这个次序依次退出，即只有在 a1,a2,,an1都退出队列后，an才能退出队列。因此队列也称为先进先出（FIFO）的线性表。
2、队列的基本操作
InitQueue(&Q)QueueEmpty(Q)
DestroyQueue(&Q)
ClearQueue(&Q)QueueLength(Q)GetHead(Q, &e)EnQueue(&Q, e)DeQueue(&Q, &e)
3、队列的顺序存储结构和循环队列
在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需要附设两个指针front和rear。为了在C语言中描述方便起见，在此我们约定：初始化建立空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。
讨论：将数据10，20，30，40，50，60按照入队列、入队列、入队列、出队列、出队列、入队列、入队列、入队列、出队列和出队列的顺序，观察队列中队头和队尾指针的变化状态。
假设当前为队列分配的最大空间为6，则不可再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破环，然而，此时又不宜如顺序栈那样进行存储再分配扩大数组空间，因为队列的实际可用空间并末占满。解决这个问题的巧妙方法是将顺序队列的存储空间想象成一个逻辑上首尾相连的环状空间，这种存储结构称为循环队列。
分析课本P64图3.14可知，Q.front=Q.rear无法判断队列空间是“满”还是“空”。解决这个问题有两种方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以队头指针在队尾指针的下一个位置上作为队列“满”的标志。因此，判断队列空的条件为Q.front=Q.rear；判断队列满的条件为Q.front =(Q.rear+1)% MAXQSIZE。
(a)顺序循环队列的类型描述
typedef struct { QElemType *base;int front;int rear;} SqQueue;(b)顺序循环队列的入队列操作
status EnQueue(SqQueue&Q, QelemType e){ if((Q.rear+1)%MAXSIZE==Q.front)return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;}(c)顺序循环队列的出队列操作
status DeQueue(SqQueue &Q, QelemType &e){ if(Q.rear==Q.front)return ERROR;e = Q.base[Q.front];Q.front =(Q.front+1)%MAXSIZE;return OK;}
4、队列的链式存储结构
队列的链式存储结构实际上是一个同时带有头指针和尾指针的单向链表，头指针指向队头元素，尾指针指向队尾元素。为了操作方便起见，给链式队列添加一个头结点。空的链式队列的判断条件为头指针和尾指针都指向头结点。
(a)链式循环队列的类型描述 typedef struct QNode { QElemType data;
struct QNode *next;} QNode, *QueuePtr;typedef struct {
QueuePtr front;// 队头指针 QueuePtr rear;// 队尾指针 } LinkQueue;(b)链式队列的入队列操作
stutus EnQueue(LinkQueue &Q, QelemType e){ p=(QueuePtr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;}(c)链式队列的出队列操作。
status DeQueue(LinkQueue &Q, QelemType &e){ if(Q.front==Q.rear returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return OK;} 注意：当队列中最后一个元素被删除后，队列尾指针也丢失了，因此需要对队尾指针重新赋值。
小结：主讲主要介绍了队列的基本概念和基本操作，以及队列的基本操作在顺序存储结构和链式存储结构上的实现。
四、作业布置
见习题集
实验作业见实验指导。
单元名称：第 七 讲：串
一、教学目标
1.熟悉串的定义以及基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。
2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。3.掌握串的堆分配存储结构以及在其上实现串操作的基本方法。4.了解串的块链存储结构
二、重点与难点 串的存储结构以及基本操作的实现。
三、教学内容与教学过程
讲授新课
4.1 串类型的定义（1）基本概念：
串（string）：由零个或多个字符组成的有限序列，也称字符串。记为：
S = „a1a2a3……an‟(n≥0)如：A= „BEIJING‟，B= „JING‟
串的长度：串中字符的数目n。
空串：不含任何字符的串，串长度为0，空格串：仅由一个或多个空格组成的串，长度为串中空格字符的个数。
如： „
‟，C= „ BEI JING ‟
子串：由串中任意个连续的字符组成的子序列。
主串：包含子串的串。如：A= „ BEIJING ‟
B= „ JING ‟
字符在串中的位置：字符在序列中的序号。
子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。
如：A= „ BEIJING ‟，B= „JING ‟，B在A中的位置为4。
串相等：当且仅当两个串的值相等。也就是说，只有两个串的长度相等
且各个对应位置的字符都相等时才相等。
（2）串的抽象数据类型定义： ADT String { 数据对象：D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n } 基本操作：（见教材P71）} ADT String
通过基本操作可以实现更复杂的操作。如通过判等、求串长和求子串等操作可以实现定位函数Index。
4.2 串的表示和实现 4.2.1 定长顺序存储表示
用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：
#define MAXSTRLEN 255
// 用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN + 1];
// 0号单元存放串的长度
特点：
串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”。
按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”（通过串联接和求子串来讲解）。
4.2.2 堆分配存储表示
以一组地址连续的存储单元存储串值的字符序列，存储空间在程序执行过程中动态分配。
C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。串堆分配存储表示： typedef struct {
char *ch;
// 若是非空串，则按串长分配存储区,否则ch为NULL int length;// 串长度 } HString;这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制（以串的复制操作为例）。
讲解串堆分配的表示与实现（P76，77）4.2.3 块链存储表示
以链表存储串值，除头指针外还可以附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的传存储结构为块链结构。
#define CHUNKSIZE 80 // 可由用户定义的块大小
typedef struct Chunk { // 结点结构
char ch[CUNKSIZE];struct Chunk *next;
} Chunk;typedef struct { // 串的链表结构
Chunk *head, *tail;// 串的头和尾指针
int
curlen;
// 串的当前长度
} LString;讲解块链存储表示在串处理系统中的应用。小结：总结本讲的主要内容
四、作业布置
见习题集
实验作业见实验指导。
单元名称：第九讲 数 组
一、教学目标
1.熟悉数组的定义。
2.掌握数组的顺序表示和基本操作的实现。
3.掌握特殊矩阵的压缩存储和稀疏矩阵三元组顺序表存储。4.了解稀疏矩阵的行逻辑链接的顺序表和十字链表表示储存
二、重点与难点 数组的压缩存储。
三、教学内容与教学过程
讲授新课 5.1 数组的定义
数组的抽象数据类型定义： ADT Array {
数据对象：
数据关系：
基本操作： }ADT Array 数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组 可以看成是线性表的线性表。举例
对于数组的操作一般只有两类：（与线性表对比讲解）（1）获得特定位置的元素值；（2）修改特定位置的元素值。5.2 数组的顺序表示和实现
对于数组A，一旦给定其维数n及各维长度bi（1≤i≤n），则该数组中元素的个数是固
定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。
数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和
PASCAL语言都是以行序为主。另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主。
以二维数组为例，假设每个元素只占L个存储单元，“以行为主”存放数组，下标从
0开始，首元素a00的地址为Loc[0,0] 求任意元素aij的地址，可由如下计算公式得到：
Loc[i,j]=Loc[0,0]+b2×i+j 其中b2为第二维的长度。
对于ｎ维数组我们只要把上式推广，就可以容易地得到ｎ维数组中任意元素aj1j2…jn的存
储地址的计算公式。
Loc[j1，j2，…jn]=Loc[0，0，…，0]+
ci1niji
其中cn=L，ci-1=bi×ci，1 特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，对于零元素不分配空间。 （1）对称矩阵 满足条件：aij=aji 1≤i，j≤n（2）三角矩阵（3）带状矩阵 使用一维数组存储以上特殊矩阵，通过示例讲解矩阵中元素与一维数组中元素的对应关系。 5.3 稀疏矩阵 稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总 数的5或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。（1）稀疏矩阵的三元组表表示法 对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。 稀疏矩阵的三元组顺序存储表示 #define MAXSIZE 1000 typedef struct {int i, j; ElementType e； }Triple;typedef struct {Triple data[MAXSIZE+1]; int mu, nu, tu; }TSMatrix； 用三元组表实现稀疏矩阵的转置运算 矩阵转置：指变换元素的位置，把位于（row，col）位置上的元素换到（col，row）位置上，也就是说，把元素的行列互换。 用三元组实现稀疏矩阵转置运算的两种方式 重点掌握第一种方式：由转置后的矩阵中元素在三元组中的次序依次在转置前的矩阵中找到相应的三元组进行转置。通过程序结合矩阵进行讲解。 （2）矩阵的行逻辑链接的顺序表（了解）（3）十字链表表示 （了解）小结：总结本讲的主要内容 四、作业布置 见习题集 实验作业见实验指导。 数据结构【第四次】实验报告 学院： 班级： 学号： 姓名： 实验四 （一）实验名称：C语言数据结构与指针 （二）实验目的：巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。 （三）实验内容： 1)学生信息的显示，具体要求如下： 定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)； 设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型； 设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于5人）。 2)输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如 输入：10 2 30 4 5，逆置后显示为：5 4 30 2 10。 （四）源代码： #define MAXSIZE 100 #include ElemType data[MAXSIZE];int length; } SqList;SqList l; void InitList(SqList &L) { L.length = 0;} void CreatSqlist(SqList &L,int n) { printf(“请输入节点”);int i;for(i=0;i } void Output(SqList &L) { int i;for(i=0;i printf(“n”);} int chazhao(SqList &L,int x){ int i,k;printf(“n请输入你要查找的元素 x=?”);scanf(“%d”,&x);for(i=0;i<=(L.length+1);i++){ if(x==L.data[i]) {printf(“要查找的元素%d位于线性表第%d位上nn”,x,i+1); k=0; break; } } if(k!=0)printf(“所要查找的元素%d不在线性表中”,x);return 0;} int GET(SqList &L,int i){ int m;if((i<0)||(i>L.length)){printf(“所查找范围超出线性表长度”);return 1;} else if((i>=1)&&(i<=L.length)){ m=L.data[i-1];}printf(“%d ”,m);return 0;} int DELETE(SqList &L,int i){ int j;if(i<1||i>L.length){printf(“删除错误”);return 0;} else { for(j=i;j L.data[j-1]=L.data[j]; L.length--; } return 1;} int INSERT(SqList &L,int x,int i){ int j;if(L.length>=MAXSIZE-1){printf(“over flow”);return 1;} else if((i<1)||(i>L.length+1)){printf(“插入错误”);return 1;} else {for(j=L.length;j>=i-1;j--)L.data[j+1]=L.data[j];L.data[i-1]=x;L.length=L.length+1;} return 0;} int main(){int n,i,k,x;InitList(l);printf(“请输入线性表的长度 ”);scanf(“%d”,&n);CreatSqlist(l,n);Output(l); printf(“请输入你要查找的数所在的节点位置”);scanf(“%d”,&i);GET(l,i);chazhao(l,x);printf(“请输入你要删除元素的位置=?”);scanf(“%d”,&k);DELETE(l,k);Output(l);printf(“请输入你要插入的数和位置x,i=?”);scanf(“%d,%d”,&x,&i);INSERT(l,x,i);Output(l);return 0;} （五）代码运行结果： （六）需求分析 1、输入的形式和输出值的范围：1）输入10个整数。2）输出整个顺序线性表。 2、输出的形式：完成各种功能后的线性表。 3、程序所能达到的功能：1）所存储顺序线性表的显示、元素的查找、删除和插入。 （七）所用到的函数： void CreatSqlist void Output Int chazhao int GET int INSERT int DELETE （八）心得体会： 此次实验的过程中还是遇到了很多意想不到的问题，让我再一次深刻的体会到了理论和实践的差距。使我清楚的知道技术上的东西，细节更显得尤为重要和值得重视。困难虽有，但在我的努力下，最后还是成功完成了实验。总而言之，这次实验又增长了我不好知识。 《数据结构》课程设计题目(程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include typedef struct _RingNode { int pos; struct _RingNode *next;}RingNode, *RingNodePtr; // 创建约瑟夫环，pHead:链表头指针，count:链表元素个数 void CreateRing(RingNodePtr pHead, int count){ RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr =(RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead;// 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n){ RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr!= NULL) { if(i == n) { // 踢出环 printf(“n%d”, pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if(pPrev == pCurr) { // 最后一个 printf(“nKing is %d”, pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main(){ int n = 0, m = 0; RingNodePtr pHead = NULL; printf(“M(person count)= ”); scanf(“%d”, &m); printf(“N(out number)= ”); scanf(“%d”, &n); if(m <= 0 || n <= 0) { printf(“Input Errorn”); return 0; } // 建立链表 pHead =(RingNodePtr)malloc(sizeof(RingNode)); pHead->pos = 1; pHead->next = NULL; CreateRing(pHead, m);// 开始出圈 printf(“nKick Order: ”); KickFromRing(pHead, n); printf(“n”); system(“pause”); return 0;} //数组做： #include void SelectKing(int MonkeyNum, int CallNum); void main(){ int MonkeyNum; int CallNum; /* 输入猴子的个数 */ printf(“Monkey Num = ”); scanf(“%d”, &MonkeyNum); /* 输入M的值 */ printf(“Call Num = ”); scanf(“%d”, &CallNum); SelectKing(MonkeyNum, CallNum); } void SelectKing(int MonkeyNum, int CallNum){ int *Monkeys;// 申请一个数组，表示所有的猴子； int counter = 0;//计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0;// 位置，数组的下标，轮流遍历数组进行报数； int token = 0;// 令牌，将报数时数到M的猴子砍掉； // 申请猴子个数大小的数组，把桌子摆上。 Monkeys =(int *)malloc(sizeof(int)* MonkeyNum); if(NULL == Monkeys) { printf(“So many monkeys, system error.n”); return; } // 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); // 循环，直到选中大王 while(counter!= MonkeyNum) { // 如果这个位置的猴子之前没有砍掉，那么报数有效 if(Monkeys[position] == 0) { token++;// 成功报数一个，令牌+1，继续报数直到等于M // 如果报数到M，那么将这个猴子砍去 if(token == CallNum) { Monkeys[position] = 1;// 设置为1，表示砍去 counter++;// 计数增加 token = 0;// 设置为0，下次重新报数 // 如果是最后一个猴子，把它的位置打印，这个就是大王了 if(counter == MonkeyNum) { printf(“The king is the %d monkey.n”, position+1); } } } // 下一个猴子报数 position =(position + 1)%MonkeyNum; } // 释放内存，开头为所有猴子创建的桌子 free(Monkeys); return;} 题目2 ：字符逆转（学时：3） 从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。 #include struct node { struct node *prev; char c; struct node *next;};struct node *input(struct node *top);int main(void){ struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c=' ';bottom=input(top);p=bottom->prev;while(p!=NULL){ printf(“%c”,p->c); p=p->prev;} return 0;} struct node *input(struct node *top){ struct node *t;char x;while((x=getchar())!='n'){ top->c=x;t=(struct node *)malloc(sizeof(struct node));top->next=t;t->prev=top;t->next=NULL;t->c=' ';top=top->next; } } return top;题目3 ：工资核算（学时：3） 设有一个单位的人员工资有如下信息：name、department、base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。 #include char name[100];char department[100]; int basepay; int allowance; int total;}stuff[SIZE];main(){ FILE *fp; int i; printf(“Please enter name department basepay allowance：n”); for(i=0;i scanf(“%s %s %f %f”,&stuff[i].name,&stuff[i].department,&stuff[i].basepay,&stuff[i].allowance); if((fp=fopen(“paydata.dat”,“wb”))==NULL) { printf(“Can't open filen”); return 0;} for(i=0;i if(fwrite(&stuff[i],LENTH,1,fp)!=1) printf(“文件写入出错n”); fclose(fp); if((fp=fopen(“paydata.dat”,“rb”))==NULL) { } printf(“Can't open filen”); printf(“修改过后的结果：n”); for(i=0;i { fread(&stuff[i],LENTH,1,fp); stuff[i].total=stuff[i].basepay+100+stuff[i].allowance; printf(“%-10s%-10s %f %f %fn”,stuff[i].name,stuff[i].department,stuff[i].basepay+100,stuff[i].allowance,stuff[i].total); } fclose(fp);return 0;} 题目4：满足条件的有序表生成（学时：3） 已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。 #include int a[7],b[5],c[6],d[7]; int i,j,k,t,m;printf(“nPlease enter 7 numbers of A:”);for(i=0;i<7;i++)scanf(“%d”,&a[i]);for(j=0;j<6;j++) for(i=0;i<6-j;i++) if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i<7;i++)printf(“%5d”,a[i]); printf(“nPlease enter 5 numbers of B:”); for(i=0;i<5;i++)scanf(“%d”,&b[i]);printf(“n”);for(j=0;j<4;j++)for(i=0;i<4-j;i++) if(b[i]>b[i+1]){t=b[i];b[i]=b[i+1];b[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<5;i++)printf(“%5d”,b[i]); printf(“nPlease enter 6 numbers of C:”); for(i=0;i<6;i++)scanf(“%d”,&c[i]); for(j=0;j<5;j++) for(i=0;i<5-j;i++) if(c[i]>c[i+1]){t=c[i];c[i]=c[i+1];c[i+1]=t;} printf(“the sorted numbers：n”);for(i=0;i<6;i++)printf(“%5d”,c[i]);printf(“n”); for(i=0;i<5;i++){ for(j=0;j<6;j++){ if(b[i]==c[j]){ for(k=0;k<7;k++){ if(b[i]==a[k]) } } } } a[k]=m; printf(“n”);k=0;for(i=0;i<7;i++) if(a[i]!=m){ } printf(“生成的有序表d为 ”);for(i=0;i printf(“%4d”,d[i]);d[k]=a[i];k++;printf(“n”);} 题目5：一元 多项式的减法（学时：6） 设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。 #include struct Polynode { int coef;int exp;Polynode *next;}Polynode,*Polylist;void Polycreate(Polylist head){ } void Polyadd(Polylist polya,Polylist polyb){ Polynode *p,*q,*tail,*temp;int sum;p=polya->next;Polynode *rear,*s;int c,e;rear=head;printf(“请输入多项式的系数项和指数项”);scanf(“%d,%d”,&c,&e);while(c!=0){ } rear->next=NULL;s=(Polynode*)malloc(sizeof(Polynode));s->coef=c;s->exp=e;rear->next=s;rear=s;scanf(“%d,%d”,&c,&e); q=polyb->next;tail=polya;while(p!=NULL&&q!=NULL){ if(p->exp sum=p->coef+q->coef;if(sum!=0){ } else { temp=p;p->coef=sum;tail->next=p;tail=p;p=p->next;temp=q;q=q->next;free(temp); } } } } p=p->next;free(temp);q=q->next;free(temp);else { } tail->next=q;tail=q;q=q->next;if(p!=NULL)tail->next=p;else tail->next=q;void Polysubstract(Polylist polya,Polylist polyb){ Polylist h=polyb;Polylist p=pb->next;Polylist pd;while(p){p->coef*=-1;p=p->next;} pd=Polyadd(pa,h);for(p=h->next;p;p=p->next)p->coef*=-1;return pd； } void PrintPolyn(Polyn P) void printfPolyn(Polynode *head){ Polynode *p=head->next;while(p){printf(“%dx^%d”,p->coef,p->exp);if(p->next)printf(“+”);p=p->next;} } int main(){ Polynode *La,Lb;La=Polycreate();Lb=Polycreate();PrintPolyn(La);printf(“/n”);PrintPolyn(Lb); } printf(“/n”);Polyadd(polya,polyb);printPolyn(polya);return 0; 题目6：床位分配（学时：6） 某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。 #include typedef struct Room { int roomlevel;int roomnum;int bednum;int peoplenum;int bed[N];int sex;char name[10];struct Room *next;}Room;Room *creat(int roomlevel,int room[],int bed[]){ Room *head,*p,*q; int i=1,j,h,num=1; head=(Room *)malloc(sizeof(Room));head->peoplenum=0;q=head;while(i<=roomlevel) { for(j=1;j<=room[i];j++) { p=(Room *)malloc(sizeof(Room)); p->roomlevel=i;p->roomnum=num++; p->sex=-1; for(h=0;h q->next=p; q=p;} i++;} p->next=NULL; p->peoplenum=0; return(head);} void Init(Room *head){ Room *p;int i;p=head;while(p!=NULL){ p->peoplenum=0; p->sex=-1; for(i=0;i p->bed[i]=0; p=p->next;} printf(“nn 操作成功} void Getin(Room *head){ Room *p;n”); int i,s,lev,age;char name[10];int number=0;int bednumber=0;printf(“nn 欢迎使用订房系统 nn”); printf(“请输入性别（1为男，2为女）：”); scanf(“%d”,&s);printf(“nn 请输入想入住的房间等级：”);scanf(“%d”,&lev);p=head->next;while(p!=NULL){ if((p->roomlevel==lev)&&((p->sex==s)||(p->sex==-1))){ } for(i=0;i if(p->bed[i]==0){ } if(number!=0)break;number=p->roomnum;bednumber=i+1;p->bed[i]=1;p->sex=s;p->peoplenum++;break; } p=p->next;if(number==0&&bednumber==0) else { head->peoplenum++; printf(“n订单已下，请输入客人信息: n”);printf(“n 满客 n”); printf(“名字:n”);scanf(“%s”,name); printf(“年龄 :n”);scanf(“%d”,&age); printf(“您的订单3:n”); printf(“名字 年龄 性别 到达时间 房间等级 房间号 床位号n”); if(s==1) printf(“%s %d male 11-19 %d %d %dn”,name,age,p->roomlevel,p->roomnum,bednumber); else printf(“%s %d formale 11-19 %d %d %d n”,name,age,p->roomlevel,p->roomnum,bednumber); } printf(“n”); } void Checkout(Room *head){ Room *p;int number,bednumber,i,s;printf(“欢迎使用退房系统：”);printf(“nn 请输入房间号：”);scanf(“%d”,&number);printf(“nn 请输入性别（1为男，0为女）：”);scanf(“%d”,&s);printf(“请输入床位号：”);scanf(“%d”,&bednumber);p=head->next;while(p!=NULL){ if(p->roomnum==number) for(i=0;i roomlevel;i++) if(i+1==bednumber){ p->bed[i]=0;p->peoplenum--;if(p->peoplenum<0) p->peoplenum=0; } } } if(p->peoplenum==0) p->sex=-1; printf(“您已退房，欢迎下次光临”);break;p=p->next;void Display(Room *head){ Room *p;int i=0;p=head->next;printf(“nn已订房间查询”);if(head->peoplenum==NULL){ printf(“所有等级房间空房”); return;} while(p->peoplenum!=NULL){ if(p->sex==1) printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：男”,p->roomnum,p->roomlevel,p->peoplenum); else printf(“n 房间号：%d，房间等级：%d，已住人数：%d，住房人性别：女”,p->roomnum,p->roomlevel,p->peoplenum); } void main(){ int n,k=1,i,roomlevel,room[10],bed[10],sum=0; Room *head; printf(“请输入房间等级数:n”);printf(“Roomlevel:”);scanf(“%d”,&roomlevel);for(i=1;i<=roomlevel;i++) { printf(“n %d等级房间数:”,i); } printf(“n”);p=p->next; while(i peoplenum) if(p->bed[i]==1) { printf(“，已住床位号：%d”,i+1); i++; } } scanf(“%d”,&room[i]);printf(“n %d房间内床位数:”,i); scanf(“%d”,&bed[i]);sum+=room[i]*bed[i];head=creat(roomlevel,room,bed); while(k==1) { printf(“ n欢迎光临 :n”); printf(“1:订房n2:退房n3:查询n4:退出系统n”); printf(“请输入您的选择:n”); scanf(“%d”,&n); switch(n) { case 1: Getin(head);break; case 2: Checkout(head);break; case 3: Display(head);break; case 4: k=0;break; default : printf(“Error！please input again:”);break; } } } 题目7：文本文件单词的检索及计数（学时：6） 要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。 #include }SW; void CreatTextFile(){ char filename[10],ch; FILE*fp; printf(“请输入所用的文件名:”);scanf(“n%s”,filename);fp=fopen(filename,“w”); printf(“请输入一段文字，以$号结束:n”);scanf(“%s”,&ch); while(ch!='$'){ fwrite(&ch,sizeof(ch),1,fp); } scanf(“%c”,&ch); } fclose(fp);void CountWord(){ FILE *fp;SW S,T;char ch;char filename[10]; int i=0,number=0; printf(“输入文本文件名：”); scanf(“%s”,filename);fp=fopen(filename,“r”); printf(“输入要统计计数的单词：”); scanf(“%s”,T.ch); while(!feof(fp)){ ch= fgetc(fp); if(ch==' ') { if(i!=0){ S.ch[i]=' ';i=0; } } } if(strcmp(S.ch,T.ch)==0)number++;else if(ch=='n'){ if(i!=0) } else { } S.ch[i]=ch;i++;{ S.ch[i]=' '; i=0; } if(strcmp(S.ch,T.ch)==0)number++;if(number==0)printf(“单词不在文本中 n”);else printf(“单词%s在文件%s中共出现了%d次:”,T.ch,filename,number); fclose(fp);} void SearchWord(){ FILE*fp;SW S,T;char filename[10]; int i,i_r,line,flag=0;char ch;printf(“n输入文本文件名：”); scanf(“%s”,filename);fp=fopen(filename,“r”);printf(“输入要统计计数的单词：”); scanf(“%s”,T.ch); i=i_r=0;line=1;while(!feof(fp)){ ch=fgetc(fp); if(ch==' ') { if(i!=0) { i_r++;S.ch[i]=' '; i=0; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); %d 行,%d列 flag=1; break; } } } else if(ch=='n') { if(i!=0) { i_r++;S.ch[i]=' '; if(strcmp(T.ch,S.ch)==0){ printf(“%s单词第一次出现是在n”,T.ch,line,i_r); flag=1; break; } i=0;i_r=0;line++; } else { line++;i_r=0; } } else { %d 行,%d列 S.ch[i]=ch;i++;} } if(flag==0) printf(“%s单词不在文本中n”,T.ch); fclose(fp);} int main(){ } CreatTextFile();CountWord();SearchWord(); 题目8：二叉树的遍历（学时：6） 二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。 #include b=NULL;else { b=(BTNode *)malloc(sizeof(BTNode)); b->data=ch; b->lchild=CreatBTree();//递归先序建立左子树 b->rchild=CreatBTree();//递归先序建立右子树 } return b;} void PreOrder(BTNode *b)//递归先序遍历二叉树函数 { if(b!=NULL) { printf(“%c ”,b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b)//非递归中序遍历二叉树函数 { BTNode *stack[M],*p;int top=-1;if(b!=NULL){ p=b; while(top>-1||p!=NULL) { while(p!=NULL)//扫描p的所有左结点并入栈 { top++; stack[top]=p; } p=p->lchild;if(top>-1){ p=stack[top];//出栈访问结点 top--;printf(“%c ”,p->data); p=p->rchild;//扫描p的右结点 } } printf(“n”);} } void PostOrder(BTNode *b)//非递归后序遍历二叉树函数 { BTNode *stack[M],*p;int sign,top=-1;if(b!=NULL){ do { while(b!=NULL)// b所有左结点入栈 { top++; stack[top]=b; b=b->lchild; } p=NULL;// p指向栈顶前一个已访问结点 sign=1; //置b为已访问 while(top!=-1 && sign){ b=stack[top];//取出栈顶结点 if(b->rchild==p)//右孩子不存在或右孩子已访问则访问b { printf(“%c ”,b->data); top--;p=b;//p指向被访问的结点 } else { b=b->rchild;//b指向右孩子结点 sign=0;//置未访问标记 } } }while(top!=-1); printf(“n”);} } void change(BTNode *b) //左右子树交换(递归){ BTNode *r;r=(BTNode *)malloc(sizeof(BTNode));int f1=0,f2=0;if(b==0)return; //树为空时，跳出 if(b->lchild){ change(b->lchild); r->lchild=b->lchild; f1++; //有左子树，符号位不为空 } if(b->rchild){ change(b->rchild); r->rchild=b->rchild; f2++; //有右子树，符号位不为空 } if(f1==0)r->lchild=NULL; //否则，给中间变量赋空值 if(f2==0)r->rchild=NULL;if(f1||f2){ b->rchild=r->lchild; //左右子树交换 b->lchild=r->rchild;} } int max(int m,int n){ } if(m>n)return m;else return n;int count(BTNode *b) //计算树高(递归){ if(b==NULL) return 0;else return(1+max(count(b->lchild),count(b->rchild)));} int main() { BTNode *root = NULL; printf(“-----------------二叉树的遍历-----------------nn”); printf(“请按先序递归顺序创建二叉树(结束符 #):n”); root = CreatBTree(); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); printf(“n树高: %dn”,count(root));printf(“n左右子树交换位置:”); change(root); printf(“n递归先序遍历结果:n”); PreOrder(root); printf(“n非递归中序遍历结果:n”); InOrder(root); printf(“非递归后序遍历结果:n”); PostOrder(root); return 0; 题目9：创建二叉排序树（学时：3） 二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。 #include typedef struct node { int data;struct node *lchild ,*rchild;}BSTNode,*BSTTree; //二叉排序树的插入（递归算法）void InsertBST(BSTTree *BST , int key){ } if((*BST)==NULL){ } else if((*BST)->data>key)//如果待插入的元素比根结点元素值小 InsertBST(&((*BST)->lchild),key);//插入在根结点的左子树(*BST)=(BSTNode*)malloc(sizeof(BSTNode));(*BST)->data=key;(*BST)->lchild=NULL;(*BST)->rchild=NULL;else InsertBST(&((*BST)->rchild),key);//插入在根结点的右子树上 //创建一棵二叉排序树 BSTTree CreateBSTTree(){ } //中序遍历 void InOrder(BSTTree BST){ if(BST!=NULL){ } InOrder(BST->lchild);printf(“%5d”,BST->data);InOrder(BST->rchild);BSTTree bst=NULL;int x;while(1){ } return bst; scanf(“%d”,&x);if(x==00)break;InsertBST(&bst,x);} void main(){ BSTTree BST; printf(“建立二叉排序树，请输入序列:n”); BST=CreateBSTTree(); printf(“中序遍历后输出的该序列为:”);InOrder(BST); printf(“n”); } 题目10：霍夫曼编码应用（学时：3） 假设一串由大写字母构成的电文，采用霍夫曼规则对其进行编码，以菜单方式设计并完成功能任务：建立霍夫曼树、霍夫曼编码生成、编码文件译码。 #include char ch; int parent,lchild,rchild;}HTNode; typedef struct{ char ch; char bits[n+1]; }CodeNode; typedef struct { char cha;int number;}COUNTER; int Init(HTNode ht[])//初始化函数，为每一个字母信息赋权值 { int i,s=1;COUNTER counter[27];char ch;printf(“请输入字符：n”);scanf(“%c”,&ch);counter[1].cha='A';counter[2].cha='B';counter[3].cha='C';counter[4].cha='D'; counter[5].cha='E';counter[6].cha='F';counter[7].cha='G';counter[8].cha='H';counter[9].cha='I';counter[10].cha='J';counter[11].cha='K';counter[12].cha='L';counter[13].cha='M';counter[14].cha='N';counter[15].cha='O';counter[16].cha='P';counter[17].cha='Q'; counter[18].cha='R'; counter[19].cha='S';counter[20].cha='T';counter[21].cha='U';counter[22].cha='V';counter[23].cha='W';counter[24].cha='X';counter[25].cha='Y';counter[26].cha='Z';for(i=1;i<=26;i++)counter[i].number=0;while(ch!=' '){ switch(ch){ case 'A':counter[1].number++;break;case 'B':counter[2].number++;break;case 'C':counter[3].number++;break;case 'D':counter[4].number++;break;case 'E':counter[5].number++;break;case 'F':counter[6].number++;break;case 'G':counter[7].number++;break;case 'H':counter[8].number++;break;case 'I':counter[9].number++;break;case 'J':counter[10].number++;break;case 'K':counter[11].number++;break;case 'L':counter[12].number++;break;case 'M':counter[13].number++;break;case 'N':counter[14].number++;break;case 'O':counter[15].number++;break; case 'P':counter[16].number++;break; case 'Q':counter[17].number++;break;case 'R':counter[18].number++;break;case 'S':counter[19].number++;break;case 'T':counter[20].number++;break;case 'U':counter[21].number++;break;case 'V':counter[22].number++;break;case 'W':counter[23].number++;break;case 'X':counter[24].number++;break; } } case 'Y':counter[25].number++;break;case 'Z':counter[26].number++;break;} scanf(“%c”,&ch);for(i=1;i<=26;i++){ } s=s-1;return s;if(counter[i].number!=0){ } ht[s].weight=counter[i].number;ht[s].ch=counter[i].cha;s++; void select(HTNode ht[],int q,int *p1,int *p2)//select函数 { int i,j,x=0,y=0;for(j=1;j<=q;++j){ } if(ht[j].parent==0){ } x=j;break;for(i=j+1;i<=q;++i){ } for(j=1;j<=q;++j){ } for(i=j+1;i<=q;++i){ if(ht[i].weight //选出第二小结点 if(ht[j].parent==0&&x!=j){ } y=j;break;if(ht[i].weight //选出最小结点 } } } if(x>y){ } else { } *p1=x;*p2=y;*p1=y;*p2=x;void huffman_setup(HTNode ht[],int s){ int i,a;int p1,p2;a=2*s-1;for(i=1;i<=a;i++){ if(i<=s){ } else { ht[i].weight=ht[i].weight; } } } ht[i].weight=0;ht[i].parent=ht[i].lchild=ht[i].rchild=0;for(i=s+1;i<=a;++i) //建立赫夫曼树 { } select(ht,i-1,&p1,&p2);ht[p1].parent=i;ht[p2].parent=i;ht[i].lchild=p1;ht[i].rchild=p2;ht[i].weight=ht[p1].weight+ht[p2].weight;void huffman_show(CodeNode hc[],HTNode ht[],int s)//给字符编码 { char q[n];int i,p,c,f;q[s-1]=' ';for(i=1;i<=s;i++) { p=s-1;for(c=i,f=ht[i].parent;f;c=f,f=ht[f].parent){ } } if(ht[f].lchild==c){ } else { } q[--p]='1';q[--p]='0';strcpy(hc[i].bits,&q[p]);} hc[i].ch=ht[i].ch;//-----------------编码 void huffman_code(CodeNode hc[]){ int i=1;char ch,ah;printf(“请输入编码的信息：n”);scanf(“%c”,&ch);printf(“编码是：n”);while(ch!=' '){ ah=hc[i].ch;while(ch!=ah){ } i++;ah=hc[i].ch;printf(“%s”,hc[i].bits);scanf(“%c”,&ch);i=1; } } //-----------------解码 void huffman_read(HTNode ht[],int s)//根据编码来返回字母信息 { int i,j,t;char b;t=2*s-1;i=t;printf(“进行解码n”);fflush(stdin);scanf(“%c”,&b);printf(“解码后的信息是：n”);while(b!=' '){ if(b=='0')i=ht[i].lchild;else i=ht[i].rchild;if(ht[i].lchild==0){ } } } printf(“%c”,ht[i].ch);j=i;i=t;scanf(“%c”,&b);int main(){ int flag=1,choice;int s,i;HTNode ht[m];CodeNode hc[n];printf(“霍夫曼树：n”);s=Init(ht);huffman_setup(ht,s);huffman_show(hc,ht,s);for(i=1;i<=s;i++){ } while(flag){ printf(“%c---> %sn”,hc[i].ch,hc[i].bits); } } printf(“请输入您想要进行的操作：n 1 编码n 2 解码n 3 退出n”);fflush(stdin);scanf(“%d”,&choice);switch(choice){ case 1: huffman_code(hc);printf(“n”);break; case 2: } huffman_read(ht,s);printf(“n”);break; case 3: flag=0;return 0;题目11：关键路径寻找（学时：6） 对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。 #include 目录 前言..................................................................................................................2 概要设计..................................................................................................................3 1.1 数据结构设计...........................................................................................3 2.1 算法设计...................................................................................................3 2.1.1 建立链表的算法..............................................................................3 2.1.2 链表插入一个元素的算法..............................................................3 2.1.3 链表删除一个元素的算法..............................................................3 3.1 ADT描述..................................................................................................4 4.1 详细设计…………………………………………… ……………………………… 4 4.1.1 数据存储结构……………………………… ……………………………… 4.4.1.2 主要伪代码…… …………………… ……………………………………… 4 软件测试..................................................................................................................7 心得体会................................................................................................................11 源代码...................................................................................................................12 参考文献………………………………………………………………………...21 前言 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。 随着计算机科学的技术和发展，计算机的功能和运算速度不断地提高，其应用于信息处理的范围日益扩大。与之相应的，计算机的加工处理对象也从简单的数据发展到一般的符号，进而发展到更复杂的数据结构。数据结构是计算机程序设计的重要理论技术基础，数据结构的表示和操作都涉及到算法，如何描述数据的结构和讨论有关的算法，又涉及到程序设计语言。因此，它不仅是计算机学科的核心课程，而且已经成为其他理工专业的热门选修课。我们通过对这门基础课程的学习，要学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适合的逻辑结构，储存结构及其相应的算法，并初步掌握算法时间分析和空间分析的技术。通过实际操作去了解数据结构原理，练习编写代码的能力，以及抽象能力。 从课程性质上讲，“数据结构”是一门专业技术基础课。它的要求是学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读，符合软件工程的规范。 概要设计 1.1 数据结构设计 采用链式储存结构。typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;2.1 算法设计 2.1.1 建立链表的算法 （1）算法思想分析 首先从表尾到表头逆向建立单链表,然后再建立的单链表基础上进行对链表上的元素进行查询,删除,插入的操作。（2）要点描述 首先建立一个带头结点的单链表，通过申请内存，先建立一个空链表。然后结点的插入，建立一个有多个结点的链表。在进行查询等操作。（3）时间和空间复杂度分析 程序的时间复杂度为O(n)。 2.1.2 链表插入一个元素的算法 （1）算法思想分析 要生成一个新数据域为X的结点，然后插入在单链表中。（2）要点描述 在链表中插入结点只需要修改指针。若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。 （3）时间和空间复杂度分析 时间复杂度O(n)2.1.3 链表删除一个元素的算法 （1）算法思想分析 要删除一个结点，必须修改指针并且释放空间。（2）要点描述 找到线性表中第i-1个结点，修改其指向后继的指针。 （3）时间和空间复杂度分析 时间复杂度O(n) 3.1 ADT描述 ADT LinkList{ 数据对象：D={ e | e∈LNode } 数据关系：R1={ 基本操作： GreateList_L(&L, n) 操作结果：构造了一个长为n的数据链表 ListDelete_L(&L, i, &e) 初始条件：链表L已存在而且非空 操作结果：删除L的第i个数据，并且用e返回其值 ListInsert_L(&L, i, e) 初始条件：链表L已存在 操作结果： 在L的第i个位置插入数据e GetElem(L, i, e) 初始条件：链表L已存在 操作结果：用e返回L中的第i个数据 }ADT LinkList 4.1 详细设计 4.1.1数据存储结构设计 采用单链式线性表实现 4.1.2 主要伪代码 Status GetElem(LinkList L, int i, ElemType *e){ int j=0;int d;LinkList p = L;while(p&&j } if(!p || j > i)return ERROR;printf(“您要查询的元素是:n”);d=p->data;printf(“%d”,d);printf(“n”);} void InitList(LinkList *L){ *L =(LinkList)malloc(sizeof(struct LNode));if(!*L)exit(OVERFLOW);(*L)->next = NULL;} Status ListInsert(LinkList L, int i, ElemType e){ int j = 0;LinkList p = L, s;while(p && j < i-1){ p = p->next;j++;} if(!p|| j > i-1)return ERROR;s =(LinkList)malloc(sizeof(struct LNode));s->data = e;s->next = p->next;p->next = s;return OK;} Status ListDelete(LinkList L, int i, ElemType *e){ int j = 0;LinkList p = L, q;while(p->next && j < i-1){ p = p->next; j++;} if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;} void ListTraverse(LinkList L, void(*vi)(ElemType)){ LinkList p = L->next;while(p){ vi(p->data);p = p->next;} printf(“n”);} void ListPrint(LinkList L){ LinkList p = L->next;while(p){ printf(“%d ”, p->data);p = p->next;} printf(“n”);} void printInt(int data){ printf(“%d ”, data);}.软件测试 图一(主界面) 图二(插入学生信息) 图三(显示所有学生信息) 图四(查询个人信息) 图五(统计信息) 图六(修改信息) 图七(保存数据) 图八(删除信息) 心得体会 通过本程序的设计，我对数据结构作了以下总结：要解决一道程序题必须先要认真捕捉改程序中的有用信息，找出解决方法。先规划好，程序需要什么样的数据结构，什么函数，对程序有什么要求。然后从整体把握对程序设计进行分工，相应地把程序分成若干模块，具体实现各部分实行相应的功能。一个程序要顺利地进行设计，一是要对程序的功能有全面的了解，如果漏了某些部分，都会使得这个程序调试不出来或者是令该程序没有达到预想的效果。其次，在程序的编译中，必须注重程序设计过程中的细节，像单链表的程序，就要理解链表的概念，理解链表的数据特点，要清楚知道数据域和指针域的作用，否则，很容易会浪费大量时间在检测错误上面。要说到解题的思考方向，如果要总结成规律，我认为要灵活的进行方法的设计，通过不同的方法来实现不同的功能，如通过结点的插入来实现链表的创建。同时应该注意各种语句的选择，要先预想好需要什么样的语句来实现函数定义，尽量简单快捷地完成，避免出错。 要规范面向对象程序设计师的书写协管，在这次课程设计中，我们再次感受到，规范的程序书写，可以更好的进行后期的差错补漏。还应该注意各种面向对象语言语法的运用，例如继承的方法，都要严格按照语法来进行，否则很容易就会出现错误，甚至严重影响课程设计的进度。 源代码 #include “stdio.h” #include “stdlib.h” #include “string.h” int shoudsave=0;// struct student { char num[10];//学号 char name[20]; char sex[4]; int cgrade; int mgrade; int egrade; int totle; int ave; char neartime[10];//最近更新时间 }; typedef struct node { struct student data; struct node *next;}Node,*Link; int menu(){ char m[3]; int n; printf(“ ************************欢迎进入学生成绩管理系统******************************nn”); printf(“t欢迎使用本学生管理系统，本系统将为您提供历史学生信息查询，学生成绩信息管理功能。n”); printf(“********************************************************************************”); printf(“t1输入学生资料ttttt2删除学生资料n”); printf(“t3查询学生资料ttttt4修改学生资料n”); printf(“t5显示学生资料ttttt6统计学生成绩n”); printf(“t7保存学生资料n”); printf(“ttplease choose a operation(1-7):n”); printf(“*********************************************************************** *********n”); scanf(“%s”,m); n=atoi(m); return(n);} void printstart(){ printf(“---------n”);} void Wrong(){ printf(“n=====>提示:输入错误!n”);} void Nofind(){ printf(“n=====>提示:没有找到该学生!n”);} void printc()// 本函数用于输出中文 { printf(“学号t 姓名 性别 英语成绩 数据库成绩 数据结构成绩 总分平均分n”);} void printe(Node *p)//本函数用于输出英文 { printf(“%-12s%stt%st%dtt%dt%dt%dt %dn”,p->data.num,p->data.name,p->data.sex,p->data.egrade,p->data.mgrade,p->data.cgrade,p->data.totle,p->data.ave);} Node* Locate(Link l,char findmess[],char nameornum[])//该函数用于定位连表中符合要求的接点，并返回该指针 { Node *r; if(strcmp(nameornum,“num”)==0)//按学号查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.num,findmess)==0) return r; r=r->next; } } else if(strcmp(nameornum,“name”)==0)//按姓名查询 { r=l->next; while(r!=NULL) { if(strcmp(r->data.name,findmess)==0) return r; r=r->next; } } return 0;} void Add(Link l)//增加学生 { Node *p,*r,*s; char num[10]; r=l; s=l->next; while(r->next!=NULL) r=r->next;//将指针置于最末尾 while(1) { printf(“请你输入学号(以'0'返回上一级菜单:)”); scanf(“%s”,num); if(strcmp(num,“0”)==0) break; while(s) { if(strcmp(s->data.num,num)==0) { printf(“=====>提示:学号为'%s'的学生已经存在,若要修改请你选择'4 修改'!n”,num); printstart(); printc(); printe(s); printstart(); printf(“n”); return; } s=s->next; } p=(Node *)malloc(sizeof(Node)); strcpy(p->data.num,num); printf(“请你输入姓名:”); scanf(“%s”,p->data.name); getchar(); printf(“请你输入性别:”); scanf(“%s”,p->data.sex); getchar(); printf(“请你输入数据结构成绩:”); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入数据库成绩:”); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入英语成绩:”); scanf(“%d”,&p->data.egrade); getchar(); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle / 3; //信息输入已经完成p->next=NULL; r->next=p; r=p; shoudsave=1; } } void Qur(Link l)//查询学生 { char findmess[20]; Node *p; if(!l->next) { printf(“n=====>提示:没有资料可以查询!n”); return; } printf(“请你输入要查找的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“tttt查找结果n”); printstart(); printc(); printe(p); printstart(); } else Nofind();} void Del(Link l)//删除 { Node *p,*r; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以删除!n”); return; } printf(“n=====>确定进行删除操作请按 1，按其他按键退出该操作nnnn”); if(menu()==1) { printf(“请你输入要删除的学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); printf(“n=====>提示:该学生已经成功删除!n”); shoudsave=1; } else Nofind(); } else exit;} void Modify(Link l)//修改函数 { Node *p; char findmess[20]; if(!l->next) { printf(“n=====>提示:没有资料可以修改!n”); return; } printf(“请你输入要修改的学生学号:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“请你输入新学号(原来是%s):”,p->data.num); scanf(“%s”,p->data.num); printf(“请你输入新姓名(原来是%s):”,p->data.name); scanf(“%s”,p->data.name); getchar(); printf(“请你输入新性别(原来是%s):”,p->data.sex); scanf(“%s”,p->data.sex); printf(“请你输入新的数据结构成绩(原来是%d分):”,p->data.cgrade); scanf(“%d”,&p->data.cgrade); getchar(); printf(“请你输入新的数据库成绩(原来是%d分):”,p->data.mgrade); scanf(“%d”,&p->data.mgrade); getchar(); printf(“请你输入新的英语成绩(原来是%d分):”,p->data.egrade); scanf(“%d”,&p->data.egrade); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle/3; printf(“n=====>提示:资料修改成功!n”); shoudsave=1; } else Nofind(); } void Disp(Link l)//显示函数 { int count=0; Node *p; p=l->next; if(!p) { printf(“n=====>提示:没有资料可以显示!n”); return; } printf(“tttt显示结果n”); printstart(); printc(); printf(“n”); while(p) { printe(p); p=p->next; } printstart(); printf(“n”);} void Tongji(Link l)//统计函数 { Node *pm,*pe,*pc,*pt,*pa;//用于指向分数最高的接点 Node *r=l->next; if(!r) { printf(“n=====>提示:没有资料可以统计!n”); return; } pm=pe=pc=pt=pa=r; while(r!=NULL) { if(r->data.cgrade>=pc->data.cgrade) pc=r; if(r->data.mgrade>=pm->data.mgrade) pm=r; if(r->data.egrade>=pe->data.egrade) pe=r; if(r->data.totle>=pt->data.totle) pt=r; if(r->data.ave>=pa->data.ave) pa=r; r=r->next; } printf(“------------------------------统计结果-n”); printf(“总分最高者:t%s %d分n”,pt->data.name,pt->data.totle); printf(“平均分最高者:t%s %d分n”,pa->data.name,pa->data.ave); printf(“英语最高者:t%s %d分n”,pe->data.name,pe->data.egrade); printf(“数据库最高者:t%s %d分n”,pm->data.name,pm->data.mgrade); printf(“数据结构最高者:t%s %d分n”,pc->data.name,pc->data.cgrade); printstart();} void Save(Link l)//保存函数 { FILE* fp; Node *p; int flag=1,count=0; fp=fopen(“c:student”,“wb”); if(fp==NULL) { printf(“n=====>提示:重新打开文件时发生错误!n”); exit(1); } p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp)==1) { p=p->next; count++; } else { flag=0; break; } } if(flag) { printf(“n=====>提示:文件保存成功.(有%d条记录已经保存.)n”,count); shoudsave=0; } fclose(fp);} void main(){ Link l;//连表 FILE *fp;//文件指针 char ch; char jian; int count=0; Node *p,*r; l=(Node*)malloc(sizeof(Node)); l->next=NULL; r=l; fp=fopen(“C:student”,“rb”); if(fp==NULL) { fp=fopen(“C:student”,“wb”); exit(0); } printf(“n=====>提示:文件已经打开,正在导入记录......n”); while(!feof(fp)) { p=(Node*)malloc(sizeof(Node)); if(fread(p,sizeof(Node),1,fp))//将文件的内容放入接点中 { p->next=NULL; r->next=p; r=p;//将该接点挂入连中 count++; } } fclose(fp);//关闭文件 printf(“n=====>提示:记录导入完毕,共导入%d条记录.n”,count); for(;;) { switch(menu()) { case 1:Add(l);break;//增加学生 case 2:Del(l);break;//删除学生 case 3:Qur(l);break;//查询学生 case 4:Modify(l);break;//修改学生 case 5:Disp(l);break;//显示学生 case 6:Tongji(l);break;//统计学生 case 7:Save(l);break;//保存学生 default: Wrong(); getchar(); break; } } } 参考文献 《数据结构（C语言版）》----------------清华大学出版社 严蔚敏 吴伟民 编著 《C语言程序设计》------------------------中国铁道出版社 丁峻岭 余坚 编著 第一章 绪论 一、教学目标：要求学生对C语言及C语言程序有一概括的的了解，并掌握C语言环境的功能及使用方法，为以后熟练地使用它进行上机练习做准备。 二、教学重点：掌握简单C语言程序的结构，及C语言的上机步骤。 三、教学难点：C语言编程环境的熟悉。 四、课程：讲授新课。 五、学时：两学时。 六、教学过程： 第一节 C语言概述 一、C语言简史 二、C语言的特点（优点、缺点） （1）语言简洁紧凑，使用方便、灵活。（2）运算符丰富。（3）数据结构丰富。 （4）具有结构化的控制语句。 （5）语法限制不太严格，程序设计自由度大。 （6）C语言能进行位操作，可以直接对硬件进行操作。（7）生成目标代码质量高，程序执行效率高。 第二节 C语言程序 举例如下所示： main(){ int a,b,c;scanf(“%d,%dn”,&a,&b);c=max(a,b);printf(“max=%dn”,c);} int max(int x,int y){ int z;if(x>y)z=x;else z=y;return(z);} 一、源程序的书写格式 （1）C程序是由函数构成的。一个C源程序至少仅包含一个main函数，也可包含一个main函数和若干其他函数。 （2）函数名后必须有一对圆括号“（”和“）”，这是函数的标志。（3）函数必须由左大括号“{”和“}”结束。（4）程序中的每个语句必须有一个分号“；”。 （5）C程序书写格式自由，一行内可写多个语句，一个语句可以写在多行上。 （6）C语言本身没有输入输出语句。输入输出函数由库函数scanf和printf等函数来完成。 （7）可以用/*„*/对C程序中的任何部分作诠释。 举例：举出例子，由学生说出所举例子程序书写格式的错误。学时：两课时 二、函数的定义形式 C语言函数由两部分组成。 （1）函数的首部，即函数的第一行，包括函数名，函数类型，参数名，参数类型。（2）函数体：即大括号弧内{„}的部分。如果一函数有多个大括号弧，最外层的一对{ }号函数体的范围。 举出例子：int max(int x,int y)由学生说出函数的组成。{ } 第三节 上机操作 一、上机步骤安排如下： 1、打开Turboc2环境； 2、输入程序； 3、保存文件“Alt+F”选择，F2进行保存； 4、选择compile菜单下的“compile to OBJ”,然后再选择“compile/Link EXE file”,得到EXE文件。 5、执行程序，选择Run或“Alt+F9”按“Alt+F5”得到执行结果。 布置几个程序，由学生输入，运行，检查其结果。 七、小结：通过本章的学习，要求学生必掌握C语言的书写格式及其结构介绍，并能输入程序在Turboc环境下调试运行。 八、“教学后记：在本章的学习过程中，学生基本能熟练操作Turboc环境，并能输入程序进行调试，但由于对C语言程序结构未能完全理解，调试过程常遇到错误。第二篇：C语言数据结构与指针
第三篇：数据结构经典题目及c语言代码总结
第四篇：数据结构实验报告(报告+C语言源代码)
第五篇：c语言教案
点击咨询 