第一篇：数据结构C章节总结
第一章 绪论
数据结构：数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。数据结构被形式地定义为(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合.数据类型：一个值的集合和定义在这个值集上的一组操作的总称；数据运算：对数据施加的一种操作；数据结构和数据类型两个概念之间区别：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
逻辑结构：我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。
物理结构：抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。
数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称；数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据的最小单位。
数据对象：性质相同的数据元素的集合，是数据的一个子集。
数据结构：是相互之间一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性。数据结构包括逻辑结构（线性结构，如线性表，栈，队，串，数组 和非线性结构如 树结构、图结构）、物理（存储）结构（集合、线性结构、树形结构和图状结构或网状结构）和数据运算如插入、删除、修改、排序、查找。数据结构中，与所使用的计算机无关的数据叫逻辑结构，数据结构在计算机内存中的表示是指数据的存储结构
四大类存储结构：顺序存储、链式存储、索引存储和散列存储。顺序存储包括数据存储（把逻辑上相邻的元素存储在地址连续的存储单位）和数据关系存储（通过连续的物理地址体现关系）；链式存储包括数据存储（把逻辑上相邻的元素存放在物理地址随意的存储单元）和数据关系存储（不仅存放数据本身还存放数据元素的物理地址）
抽象数据类型ADT：一个数学模型以及定义在该模型上的一组操作，包括_数据和操作_两个部分 算法的特性：有穷性（执行有穷步结束）、确定性（确切含义，不会产生二义性）、可行性、输入（零个或多个输入）和输出（一个或多个输出）
算法设计的要求：正确性、可读写、健壮性、效率与低存储量需求。
2、数据的逻辑结构是指图形结构_三种类型，树形结构和图形结构合称为非线性结构_。数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构４种。
17_称为存储结构.1821、算法的执行时间是
371、某算法的时间复杂度为O(n2),表明该算法的_____.2.算法分析的目的是问题规模之间的关系;算法分析的两个主要方面是空间复杂度和时间复杂度
5．在决定选取何种存储结构时，一般不考虑
A.各结点的值如何B.结点个数的多少C.对数据有哪些运算D.编程语言实现这种结构是否方便。
10．程序段i ＝ 0；while（i<=n）｛i = i * 3
12数据项的个数要相同，而且对应的数据项的类型要一致 1.数据结构是一门研究非数值计算的程序设计问题中计算机的系和运算等的学科。数据结构式相互之间存在一种或多种特定关系的数据元素的集合。10.数据的运算最常用的有5-1-
第二章 线性表
1.线性表:一个线性表是n个类型相同的数据元素的有限序列。线性表的顺序表示：用一组地址连
续的存储单元依次存储线性表的数据元素。顺序存储结构的特点：优，可随机存取表中任一元素，方便快捷；缺，再插入或删除时，需移动大量元素，数组的静态空间分配。
2.线性结构与非线性结构的不同点：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反
映结点间的逻辑关系是多对多的。
3.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较个结点,4.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行 5.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，删除一个
元素时大约要移动表中的(n-1)/2两种情况下求平均个元素。
6.设单链表中指针p指着结点m，指针f指着将要插入的新结点x，当x插在链表中最后一个结点
m之后时，只要先修改后修改p->link=f即可。
7.在一个长度为n的顺序存储的线性表中，删除第i个元素(1<=i<=n)时，需要从前向后依次前移i个元素前插入元素需移动
存储结构需要分配较大空间，插入和删除不需要移动元素的线性表
9、在双向链表存储结构中，删除p所指的结点时需修改指针p所指的结点的前趋结点（若存在）时需修改指针
1.在循环双链表的p所指结点之前插入s所指结点的操作是12.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用_结点的双循环链表__存储方式最节省运算时间；某线性表最常用的操作是在最后一个结点之后插
入一个结点或删除第一个结点，故采用_仅有尾指针的单循环链表存储方式最节省运算时间；对
于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为用尾指针表示的循环单链表
14.15.16.17、不带头结点的单链表head为空的判定条件是 带头结点的~是
19、带头结点的双循环表L为空表的条件是。
20、非空的循环单链表head的尾结点(由p所指向)满足21.在一个长度为n(n>1)操作与链表的长度有关；与单链表相比，双链表的优点之一是顺序访问相邻结点更灵活
23线性表的链接存储中，元素之间的逻辑关系是通过链接指针决定的。
24、从顺序表中删除第i个元素时，首先把第i个元素赋给_针开始向后的所有元素均前移一个位置，最后使线性表的长度减1。
25,26、循环单链表L为空的条件是
27、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为。
28、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为，若p为一个数组a中的下标，则其后继结点的下标的a[p].next。
29、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点
时，需要进行的操作为a[j].next=a[i].next和a[i].next=j语句。
第三章 栈和队列
1.栈：是限定仅在表尾进行插入或删除操作的线性表。栈又称为先进后出LIFO的线性表。
2.判定一个栈ST（最多元素为m0）为空的条件是
2.栈的两种存储方法：一是顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存
放自栈底到栈顶的元素；二是栈的链式表示。
3.队列：队列是一种先进先出FIFO的线性表。允许插入的一端叫做队尾rear，允许删除的一段则
称为队头front
4.链队的出队入队操作：s入队,rear->next=s;rear=s;p出队：front->next=p->next
5.顺序队：插入元素：front不变，rear加1；删除元素：rear不变，front加1。判定一个顺序栈
st(最多元素为MaxSize)为空的条件是6.循环队列:空队满队都是rea=r=front为区分,规定循环队列中剩一个元素即为满队,front=rear+1
7.8.9.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行。
10.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时
应执行rear->next=s;rear=s;
11.若己知一个栈的进栈序列是1,2,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是是(qu->rear+1)%MaxSize==qu->front 列的元素个数是(rear-front+MaxSize)%MaxSize。 24.从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行5.栈顶指针 7.在链表qu中,判定只有一个结点的条件是设有一个顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为3。 9.设计一个判别表达式中左、右括号是否配对出现的算法，采用数据结构最佳 例：设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆 列车开出车站的所有可能的顺序。 答：至少有14种①全进之后再出情况,只有1种：4，3，2，1②进3个之后再出的情况，有 3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况,有5种，2,4,3,12,3,4,12,1, 3,4 2,1,4,32,1,3,4④进1个之后再出的情况,有5种，1,4,3,21,3,2,41,3,4,21, 2,3,41,2,4,3 第四章 串 1.串：由零个或多个字符组成的有限序列；串中字符的数目n称为串的长度，零个字符的串称为 空串。包含子串的串相应的称为主串，通常称字符在序列中的序号为该字符在串中的位置。 2．空串是，其长度等于度等于其包含的空格个数。组成串的数据元素只能是 单个字符。 4．一个字符串中称为该串的子串。 5.若串S= ‘software’,其子串的数目是字符串长度为n的字串的个数计算公式 :[n+(n-1)+...+ 1+1]） 60．串是一种特殊的线性表，其特殊性体现在61．设有两个串p和q，求q在p中首次出现的位置的运算称为 串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为 O（m）；求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。 第五章 数组（线性结构，元素受限，操作不限）和广义表 1.矩阵的压缩存储：是指为多个值相同的元只分配一个存储空间，对零元不分配空间。 2.树的存储结构： 一、双亲表示法：就是用一组连续空间存储树的结点，同时在每个结点中附设 一个指示器指示其双亲的结点在数组中位置。特点：找双亲容易，找孩子难； 二、孩子兄弟表示 法（又称二叉树和二叉链表表示法）链表结构中的两个链域分别指向该结点的的第一个孩子结点 和下一个兄弟结点。操作容易，破坏了树的层次 第六章 树和二叉树 1.树：树是由n个类型相同的元素构成的有限集。 2.二叉树的性质：在二叉树的第i层上至多有2i-1个结点；深度为k的二叉树最多有2k-1个结点； 叶子结点比度为2的结点个数多1。 3.遍历二叉树：先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）。前后序遍历确定 跟，中序遍历确定左右子树，依次判断，方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继 续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定.第七章图 一、图的定义和术语： 1、图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 2、有向图—有向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有 向边（也称弧）的有限集合，弧是顶点的有序对，记为 3、无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v），并且（v,w）=(w,v) 4、n个顶点的有向图最大边数是n(n-1)； n个顶点的无向图最大边数是n(n-1)/26、权——与图的边或弧相关的数叫~；简单路径——序列中顶点不重复出现的路径叫~ 14、简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~ 16、连通图——图中任意两个顶点都是连通的叫~；连通分量——非连通图的每一个连通部分叫~ 18、强连通图——有向图中，如果对每一对Vi,VjÎV, Vi¹Vj,从Vi到Vj 和从Vj到 Vi都存在路径 1、深度优先搜索----从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点 出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被 访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 深度遍历：V1-> V2->V4-> V8->V5->V3->V6->V72、广度优先遍历(BFS)——方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个 未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图 中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作 起点，重复上述过程，直至图中所有顶点都被访问为止 第九章 查找 1.静态查找——拆半查找：确定待查记录所在的范围，然后逐步缩小范围知道找到或找不到该记 录为止。假设low和high分别为待查元素所在范围的上下界，指针mid指示区域中间的位置，mid=[low+high]/2.此处low和high分别为位置而非数值。比较时与mid做比较，比mid大，low=mid+1，反之high=mid-1，mid重新计算。查找成功或失败最多比较关键字个数不超过[log2n]+1 例：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它 将依次与表中20，70，30，50 比较大小，查找结果是失败。 2.静态查找——顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，相等则查找成功，反之失败。平均查找长度：ASL=(n+1)/2 3.二叉排列树：或是一棵空树；或者是具有以下性质的二叉树：1.若它的左子树不空，则左子树 上所有结点的值均小于它的根结点的的值；2.若它的右子树不空，则右子树上所有借点得知均大 于它的根节点的值；3.它的左右子树上也分别为二叉排列树。 数据结构学习（C++）——树（总结） happycock（原作）CSDN 才刚开了个头，就要说再见了——在树这里，除了二叉树，别的都还没有讲。为什么可以总结了呢？因为前面已经涉及到了树的两个基本用途，而如果再讲B＋、B－，就不能不提到搜索，如果是胜者树就不能不提到排序。为此，把这部分放到后面。我前面所做的努力，只是让你有个基本概念，什么时候记得用树。树的两个基本用途，可以用物质和精神来比喻。 一个用途是做为数据储存，储存具有树结构的数据——目录、族谱等等。为了在实际上是线性的储存载体上（内存、磁盘）储存非线性的树结构，必须有标志指示出树的结构。因此，只要能区分根和子树，树可以采取各种方法来储存——多叉链表、左子女－右兄弟二叉链表、广义表、多维数组。由于操作的需求，储存方法并不是随意选取的。比如，在并查集的实现上，选取的是双亲链表。 一个用途是做为逻辑判断，此时会常常听到一个名词——判定树。最常用的结构是二叉树，一个孩子代表true，一个孩子代表false。关于多叉判定树，有个例子是求8皇后的全部解——这个连高斯都算错了（一共是92组解，高斯最开始说76组解），我们比不上高斯，但是我们会让computer代劳。 就像哲学界到现在还纠缠于物质和精神本源问题，实际上在树这里也是如此。有些情况下，并不能区分是做为储存来用还是做为判断来用，比如搜索树，既储存了数据，还蕴涵着判断。 和后面的图相比，树更基本，也更常用。你可以不知道最短路径怎么求，却每时每刻都在和树打交道——看看你电脑里的文件夹吧。 最后，附带一个求N皇后的全部解的程序。 #include #define N 8 int layout[N];//布局 int key = 0; int judge(int row, int col)//判断能否在（row，col）放下 { int i;for(i = 0;i < row;i++){if(layout[i] == col)return 0;//同一列if(icol)return 0;//同一条主对角线} if(i + layout[i] == row + col)return 0;//同一条副对角线 return 1; } void lay(int row)//在row行上放Queen { int i;if(row == N)//放完N个Queen输出布局 { }printf(“n%02d ”, ++key);for(i = 0;i < N;i++)printf(“%c%d ”, layout[i] + 'a', i + 1);} else {for(i = 0;i < N;i++)//在i列上放Queen} {} layout[row] = i;if(judge(row, i))lay(row + 1); int main() { } lay(0);return 0; c数据结构实验报告 数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;XX年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目 数据结构(C语言版)实验报告 专业：计算机科学与技术、软件工程 学号:____XX40703061___________________ 班级:_________软件二班______________ 姓名:________朱海霞______________ 指导教师:___刘遵仁________________ 青岛大学信息工程学院 XX年10月 实验1 实验题目：顺序存储结构线性表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。 程序代码: #include #include #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int* elem; int length; int listsize; }Sqlist; int InitList_Sq(Sqlist &L){ =(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!)return-1; =0; =LIST_INIT_SIZE; return OK; } int ListInsert_Sq(Sqlist&L,int i,int e){ if(i+1)return ERROR; if(==){ int *newbase; newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int)); if(!newbase)return-1; =newbase; +=LISTINCREMENT; } int *p,*q; q=&(); for(p=&();p>=q;--p) *(p+1)=*p; *q=e; ++; return OK; } int ListDelete_Sq(Sqlist &L,int i,int e){ int *p,*q; if(i)return ERROR; p=&(); e=*p; q=+; for(++p;p *(p-1)=*p; --; return OK; } int main(){ Sqlist L; InitList_Sq(L);//初始化 int i,a={3,-5,6,8,2,-5,4,7,-9}; for(i=1;i ListInsert_Sq(L,i,a); for(i=0;i printf(“ %d”,); printf(“ ”);//插入9个数 ListInsert_Sq(L,3,24); for(i=0;i printf(“ %d”,); printf(“ ”);//插入一个数 int e; ListDelete_Sq(L,2, e); for(i=0;i printf(“ %d”,);//删除一个数 printf(“ ”); return 0; } 实验结果： 3，-5,6,8,2，-5,4,7，-9 3，-5,24,6,8,2，-5,4,7，-9 3,24,6,8,2，-5,4,7，-9 心得体会： 顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。 实验主要步骤： 3、分析、理解给出的示例程序。 4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。 5、修改程序： (1)增加插入结点的功能。 (2)建立链表的方法有“前插”、“后插”法。 程序代码: #include #include #define NULL 0 #define OK 1 #define ERROR 0 typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList_L(LinkList &L){ L=(LinkList)malloc(sizeof(LNode));L->next=NULL; return OK; } int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s; int j; p=L;j=0; while(p&&j p=p->next;++j; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode));s->data=e; s->next=p->next; p->next=s; return OK; } int ListDelete_L(LinkList&L,int i,int &e){ LinkList p,q; int j; p=L;j=0; while(p->next&&j p=p->next;++j; } if(!(p->next)||j return ERROR; q=p->next;p->next=q->next;e=q->data;free(q); return OK; } int main(){ LinkList L,p; char a={'A','C','E','F','H','J','Q','U'};int i,j; InitList_L(L); for(i=1,j=0;i p=L->next; while(p!=NULL){ printf(“%c ”,p->data);p=p->next;}//插入八个字符 printf(“;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：; 1、掌握栈的顺序存储结构和链式存储结构，以便在实; 2、掌握栈的特点，即后进先出和先进先出的原则; 3、掌握栈的基本运算，如：入栈与出栈 } }//插入八个字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B'); p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一个字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0; 实验结果： A C E F H J Q U A B C E F H J Q U A B E F H J Q U 心得体会： 单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。 实验3 实验题目：栈操作设计和实现 实验目的： 1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈的特点，即后进先出和先进先出的原则。 3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。 实验要求： 回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 实验主要步骤 (1)数据从键盘读入; (2)输出要判断的字符串; (3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。 程序代码: #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW-2 #define N 100 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;// 在栈构造之前和销毁之后，base的值为NULL int *top;// 栈顶指针 int stacksize;// 当前已分配的存储空间，以元素为单位 } SqStack; int InitStack(SqStack &S) { // 构造一个空栈S if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int)))) exit(OVERFLOW);// 存储分配失败 =; =STACK_INIT_SIZE; return OK; } int StackEmpty(SqStack S) { // 若栈S为空栈，则返回TRUE，否则返回FALSE if(==) return TRUE; else return FALSE; } int Push(SqStack &S, int e) { // 插入元素e为新的栈顶元素 if(>=)// 栈满，追加存储空间 { =(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!) exit(OVERFLOW);// 存储分配失败 =+; +=STACKINCREMENT; } *()++=e; return OK; } int Pop(SqStack &S,int &e) { // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==) return ERROR; e=*--; return OK; } int main(){ SqStack s; int i,e,j,k=1; char ch = {0},*p,b = {0}; if(InitStack(s))// 初始化栈成功 { printf(”请输入表达式: “); gets(ch); p=ch; while(*p)// 没到串尾 Push(s,*p++); for(i=0;i if(!StackEmpty(s)){// 栈不空 Pop(s,e);// 弹出栈顶元素 b=e; } } for(i=0;i if(ch!=b) k=0; } if(k==0) printf(”NO!“); else printf(”输出:“) printf(”YES!“); } return 0; } 实验结果： 请输入表达式： abcba 输出：YES! 心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。 实验4 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 程序代码: 实验结果： 心得体会： 实验5 实验题目：图的遍历操作 实验目的： 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 实验要求： 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。 实验主要步骤： 设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 1.邻接矩阵作为存储结构 #include”“ #include”“ #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs;//顶点表 int edges;//邻接矩阵，可看作边表 int n,e;//图中的顶点数n和边数e }MGraph;//用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//输入顶点数和边数 scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++) { scanf(”%c“,&a); G->vexs=a;//读入顶点信息，建立顶点表 } for(i=0;in;i++) for(j=0;jn;j++) G->edges=0;//初始化邻接矩阵 printf(”Input edges,Creat Adjacency Matrix “); for(k=0;ke;k++){ //读入e条边，建立邻接矩阵 scanf(”%d%d“,&i,&j);//输入边(Vi，Vj)的顶点序号 G->edges=1;;G->edges=1;//若为;//=========定义标志向 量，为 全 局 变 量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1; G->edges=1;//若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 } } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度优先遍历的递归算法====== void DFSM(MGraph *G,int i) { //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 给出你的编码 //===========BFS：广度优先遍历======= void BFS(MGraph *G,int k) { //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 给出你的编码 //==========主程序main ===== void main() { int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph));//为图G请内存空间 CreatMGraph(G);//建立邻接矩阵 printf(”Print Graph DFS: “); DFS(G);//深度优先遍历 printf(” “); printf(”Print Graph BFS: “); BFS(G,3);//以序号为3的顶点开始广度优先遍历 printf(” “); } 2.邻接链表作为存储结构 #include”“ #include”“ #define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex;//邻接点域 struct node *next;//链域 申 }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex;//顶点域 EdgeNode *firstedge;//边表头指针 }VertexNode; typedef VertexNode AdjList;//AdjList是邻接表类型 typedef struct { AdjList adjlist;//邻接表 int n,e;//图中当前顶点数和边数 } ALGraph;//图类型 //=========建立图的邻接表======= void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s;//定义边表结点 printf(”Input VertexNum(n)and EdgesNum(e): “); scanf(”%d,%d“,&G->n,&G->e);//读入顶点数和边数 scanf(”%c“,&a); printf(”Input Vertex string:“); for(i=0;in;i++)//建立边表 { scanf(”%c“,&a); G->adjlist.vertex=a;//读入顶点信息 G->adjlist.firstedge=NULL;//边表置为空表 } printf(”Input edges,Creat Adjacency List “); for(k=0;ke;k++){ //建立边表 scanf(”%d%d“,&i,&j);//读入边(Vi，Vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表结点 s->adjvex=j;//邻接点序号为j s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//将新结点*S插入顶点Vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i;//邻接点序号为i s->next=G->adjlist.firstedge; G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部 } } //=========定义标志向量，为全局变量======= typedef enum{FALSE,TRUE} Boolean; Boolean visited; //========DFS：深度优先遍历的递归算法====== void DFSM(ALGraph *G,int i) { //以Vi为出发点对邻接链表表示的图G进行DFS搜索 给出你的编码 //==========BFS：广度优先遍历========= void BFS(ALGraph *G,int k) { //以Vk为源点对用邻接链表表示的图G进行广度优先搜索 给出你的编码 //==========主函数=========== void main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf(”Print Graph DFS: “); DFS(G); printf(” “); printf(”Print Graph BFS: “); BFS(G,3); printf(” "); } 实验结果： 1.邻接矩阵作为存储结构 2.邻接链表作为存储结构 心得体会： 实验6 实验题目：二分查找算法的实现 实验目的： 掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。 实验要求： 编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。 实验主要步骤： 1.建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。 2.给出算法的递归和非递归代码; 3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性? 程序代码 实验结果： 心得体会： 实验7 实验题目：排序 实验目的： 掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。 实验要求： 实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。 实验主要步骤： 程序代码 实验结果： 心得体会： 《数据结构》课程设计题目(程序实现采用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 课程教案 课程名称： 数据结构 授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了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数据结构实验报告
第四篇：数据结构经典题目及c语言代码总结
第五篇：数据结构教案C语言版
点击咨询 