数据结构课程设计课件

1、数据结构课程设计8/8/20221数据结构课程设计目录课程设计1 线性表的逆置课程设计2 栈(1)课程设计2 栈(2)8/8/20222数据结构课程设计序号实验项目名称时数必开选开每套仪器人数目的要求实验类型1顺序表3必开1了解线性表的特性，以及它们在实际问题中的应用。掌握顺序表的实现方法，以及它们的基本操作。验证2单链表3必开1掌握单链表的基本操作：插入、删除、查找等运算。验证3循环链表3选开1掌握循环链表的基本操作：插入、删除、查找等运算。设计4栈3必开1了解栈的特性，以及它在实际问题中的应用。掌握栈的实现方法以及它的基本操作，学会运用栈来解决问题。验证8/8/20223数据结构课程设计序

2、号实验项目名称时数必开选开仪器人数目的要求实验类型5队列3必开1了解顺序队列和链队列的特性，以及它们在实际问题中的应用。掌握链队列的实现方法，以及它们的基本操作。验证6树和二叉树(1)3必开1掌握二叉树的结构特征，进一步掌握指针变量、动态变量的含义以及二叉树的各种存储结构的特点及遍历方法；掌握用指针类型描述、访问和处理二叉树的运算。验证树和二叉树(2)3必开1了解树的一个应用，掌握建立哈夫曼树建立及应用验证7线索树3选开1了解线索二叉树的一个应用，掌握线索树建立、查找、删除结点等操作及应用设计8图(1)3必开1了解图的结构及存储形式，掌握图的邻接矩阵的存储方式验证图(2)3必开1掌握图的基本存

3、储方法；掌握图的深度优先遍历或广度优先遍历方法并用高级语言实现方法。验证9最小生成树3选开1了解最小生成树生成方法，掌握用高级语言实现最小生成树的方法。验证8/8/20224数据结构课程设计序号实验项目名称时数必开选开仪器人数目的要求实验类型10最短路径3选开1了解路径的概念及实现的算法，掌握用高级语言实现最短路径的算法。验证11排序（含排序1、排序2）6必开1掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；了解各种方法的排序过程，并掌握各种排序方法的时间复杂度的分析方法。验证12查找（含查找1、查找2）6必开1了解线性表的查找

4、方法，用一种查找方法实现对给定键值的查找，并能用高级语言实现查找算法。验证13大型作业18必开1综合以上知识，给出若干个题目，由学生任选一题，然后分析题意、查阅资料、设计算法、调试编程直到解决问题，并写出课程设计总结报告上交，最后进行面试、评分。综合8/8/20225数据结构课程设计成绩评定学生上交的课程设计的实验报告和编程质量占总成绩的50%，大作业和编程质量总成绩的占50%，成绩不合格者重修。课程设计最终成绩分为“优秀”、“良好”、“中等”、“及格”、“不及格”五级。 要求：实验报告用16开纸，手写8/8/20226数据结构课程设计课程设计1 线性表的逆置P158加头文件#include

5、Insert_sqlist函数Else if (il-last+1) Else if (il-last+1)8/8/20227数据结构课程设计P159Print_sqlist函数for(i=0;ilast-1;i+)for(i=0;ilast;i+)Inverse_sqlist函数J=L-last-1-i;J=L-last-i;8/8/20228数据结构课程设计P161Void print(head)Linklist *head;Void print(linklist *head)8/8/20229数据结构课程设计线性表1、顺序表的就地逆置方法32、单链表的就地逆置选做题设A和B是两个单链表，

6、其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。8/8/202210数据结构课程设计课程设计2 栈(1)题目1 P165 用栈逆置一个线性表。题目2 设计算法判断一个算术表达式的三种括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到( 就进栈，遇) 就退掉栈顶的元素，且判断与当前扫描到的字符是否匹配？如果匹配，继续扫描；否则，没有正确配对，停止扫描表达式，返回FALSE。表达式扫描完毕，如果栈应为空，则返回TRUE)二选一8/8/202211数据结构课程设计课程设计2 栈(2)题目一P168设两个顺序栈共享存储空

7、间，试写出两个栈公用的栈操作算法push(s,x,k)和pop(s,x,k),其中k为0或1，分别用来表示两个不同的栈号。请写一个完整的程序实现之。题目二设字符串train代表火车的座位席，其中，H表示硬席,S表示软席，试将S调到H的前面，并输出调整后的train字符串。train=“HHSHSHHH”train=“SSHHHHHH”要求用栈实现二选一8/8/202212数据结构课程设计顺序栈存储结构的描述：#define Maxsize 100 /*设顺序栈的最大长度为100，可依实现情况而修改*/typedef int datatype;typedef structdatatype sta

8、ckMaxsize;int top； /*栈顶指针*/SeqStack； /*顺序栈类型定义*/SeqStack *s； /*s为顺序栈类型变量的指针*/8/8/202213数据结构课程设计构造一个空顺序栈 SeqStack * InitStack( ) SeqStack *S ;S=(SeqStack *)malloc(sizeof(SeqStack);if (!S) /*空间申请失败*/ printf(“空间不足”)；return NULL; elseS-top=0; return S; 8/8/202214数据结构课程设计取顺序栈栈顶元素datatype GetTop(SeqStack

9、*S) if (S-top=0)printf(n栈是空的!); return FALSE; elsereturn S-stackS-top-1; 8/8/202215数据结构课程设计判别空栈int StackEmpty(SeqStack *S) if (S-top=0)return TRUE;elsereturn FALSE; 8/8/202216数据结构课程设计顺序栈的入栈操作例如用堆栈存放（A，B，C，D）AACBABAtop核心语句：顺序栈入栈函数PUSH（）SeqStack*Push(SeqStack *S，datatype x) if (S-top=Maxsize)return NU

10、LL; else S-stackS-top=x;S-top+; return S; Push (s,B);Push (s,C);Push (s,D);toptoptoptop低地址LPush (s,A);高地址MBCD8/8/202217数据结构课程设计顺序栈出栈操作例如从栈中取出BDCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD核心语句：pop ( );顺序栈出栈函数POP( )datatype pop( SeqStack *S) if (S-top= =0) printf(nThe sequence stack is empty!);return FALSE; S

11、-top-;return S-stackS-top; pop ( );printf( pop () );8/8/202218数据结构课程设计两个栈的共享技术： 利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0， M-1。 由于两个栈顶动态变化，可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。两栈共享比两个栈分别申请M/2的空间利用率高。 两栈共享的数据结构定义如下： typedef int datatype；/栈元素的数据类型，假设为整型int maxsize100；/栈的容量，元素最多不能超

12、过它typedef struct datatype datamaxsize； int top2；sqstack；/顺序栈类型定义8/8/202219数据结构课程设计（图） 共享栈 8/8/202220数据结构课程设计(1)初始化操作void InitStack(sqstack *S) S-top0= -1; S-top1= M; 8/8/202221数据结构课程设计(2)入栈操作int Push(sqstack *s, datatype x, int k)/s是指向栈类型的指针，x是将要入栈的数据，k是栈号if (s-top0+1= = s-top1) printf(“两个栈均满，不能进栈！”

13、)；return 0;/改栈顶指针加1或减1，来选择不满的栈if（k = = 0）s-topk+; else s-topk-；/将x插入当前栈顶s-datas-topk = x; return 1； 8/8/202222数据结构课程设计(3)出栈操作int pop(sqstack * S，datatype *x，int k)/出栈操作，栈顶元素由参数返回if (k = 0&s-top0 = -1)|( k =1&s-top1 = = maxsize)printf(“栈空，不能退栈！”)；return -1;*x = s-datas-topk; /取出栈顶元素值给X if（k = = 0）s-t

14、opk-; /改栈顶指针加1或减1else S-topk+；return 1;8/8/202223数据结构课程设计主程序编写输入部分：双重循环，外层输入栈号，内层输入数据。输出部分：分别将两个栈中的内容输出。先打印栈号，再打印数据。测试数据：P1688/8/202224数据结构课程设计课程设计（3）-队列8/8/202225数据结构课程设计队列的特性FIFO8/8/202226数据结构课程设计1、顺序队列约定：若队列不空，队头指针front，指向队头元素。队尾指针rear，指向队尾元素的下一个位置。8/8/202227数据结构课程设计顺序队的几种状态示意图头指针始终指向队头元素，尾指针始终指向

15、队尾元素的下一个元素为了防止出现假溢出，即在假溢出时，还能进行入队操作，我们采取循环队列。8/8/202228数据结构课程设计在出队时：队头指针也要采用front=(front+1)%MAXSIZE循环队列示意图在入队时：将数据区data0MAXSIZE-1看成是首尾相接的圆环,当入队到Maxsize-1时,若队头元素的前面仍有空闲位置,下一个地址就应翻转为0,使data0接在dataMAXSIZE-1之后, 通过求余运算rear=(rear+1)%MAXSIZE来求得。8/8/202229数据结构课程设计循环队列的几种状态在循环队列中当采用入队操作: rear=(rear+1)%MAXSIZ

16、E出队操作: front=(front+1)%MAXSIZE新问题：空队和队满时都有front=rear,那么又如何判断队空和队满？8/8/202230数据结构课程设计J2 J3J1 J4 J5frontrear解决方案-人为浪费一个单元：大小为MAXSIZE的数组，只存MAXSIZE-1个结点。约定：front和rear二者之一指向实元素，另一个指向空闲元素(假设front指向队头元素，rear指向队尾元素的下一个位置，即rear 所指的单元始终为空）。队空条件 : front = = rear (初始化时：front=rear)队满条件： front=（rear+1)%N (N=MAXSI

17、ZE)队列长度（即数据元素个数）：L=（Nrearfront）% N 8/8/202231数据结构课程设计循环队列循环队列类型定义：#define MAXSIZE 100 /*队列的最大元素数为100*/typedef struct /*定义循环队列*/ datatype dMAXSIZE; int front; /*头指针,若队列不空,则指向队头元素*/ int rear; /*尾指针,若队列不空,则指向队尾元素的下一位置*/ sequeue;sequeue *Q;8/8/202232数据结构课程设计循环队列的基本操作实现建循环队列循环队列入队循环队列的出队循环队列的判空8/8/202233

18、数据结构课程设计建循环队列void InitQueue(sequeue *Q) /*构造一个空队列Q*/ Q-front = Q-rear=0;8/8/202234数据结构课程设计循环队列入队操作sequeue *EnQueue(sequeue *Q, datatype x) /*入队*/if(Q-rear+1)% MAXSIZE= Q-front) printf(“队列已满，不能入队！n”)； return NULL; else dQ-rear=x; /*将x插入队尾*/ Q-rear =(Q-rear+1)% MAXSIZE; /*队尾指针后移*/ return Q; 8/8/202235

19、数据结构课程设计循环队列的出队操作datatype DeQueue(sequeue *Q) /*出队列*/datatype y; if(Q-front= Q-rear) printf(“队列为空，无法出队！n”)； return 0; else y= Q-dQ-front; /*队头元素出队，存入y中*/ Q-front=(Q-front+1)%MAXSIZE; /*队头指针后移*/ return y; 8/8/202236数据结构课程设计循环队列的判空操作int QueueEmpty(sequeue *Q)if(Q-front= Q-rear) return 1; /*队列为空时返回1*/

20、else return 0; /*队列非空时返回0*/8/8/202237数据结构课程设计2、链队列#define NULL 0typedef struct node /*定义链队列结点类型*/ datatype data; struct node *next; linkqueue;typedef struct /*封装队头指针和队尾指针*/ linkqueue *front; /*定义队头指针*/ linkqueue *rear; /*定义队尾指针*/ Lqueue; 8/8/202238数据结构课程设计链队的几种状态示意图：(1)空链队的特征？front=rear(2) 链队会满吗？一般不

21、会，因为删除时有free动作。除非内存不足！(b)元素x入队(d)元素x出队此时，front= =rear修改rear指针修改头结点的指针域8/8/202239数据结构课程设计(3) 怎样实现链队的入队和出队操作？若设p所指结点为入队或出队结点入队（尾部插入）：rear-next=p; rear=p;出队（头部删除）：front-next=p-next;8/8/202240数据结构课程设计链队列基本操作的实现构造一个空链队链队入队链队出队判空队列8/8/202241数据结构课程设计构造一个空链队操作void InitQueue(Lqueue *Q) Q-front=(linkqueue *)m

22、alloc(sizeof(linkqueue);if(!Q-front)printf(“Overflow!”);/*存储分配失败*/elseQ-front-next =NULL;Q-rear = Q-front;8/8/202242数据结构课程设计链队入队操作linkqueue *EnQueue(Lqueue *Q, datatype x)linkqueue *p; p=(linkqueue *)malloc(sizeof(linkqueue);/*开辟新结点*/ if(!p)printf(“Overflow!”);return NULL; /*存储分配失败*/ elsep-data=x; p

23、-next= NULL;Q-rear-next=p; Q-rear=p; return Q;8/8/202243数据结构课程设计链队出队操作datatype DeQueue(Lqueue *Q)datatype y; linkqueue *p; if(Q-rear = Q-front) printf(“队列为空，无法出队！n”)； return -1; else p=Q-front-next; y=p-data; /*队头元素存入y*/ Q-front-next=p-next; /*队头指针后移*/ if(Q-rear=p) Q-rear=Q-front; /*出队后为空队*/ free(p)

24、; /*释放存储空间*/ return y; 8/8/202244数据结构课程设计判空队列函数int QueueEmpty(Lqueue *Q)if(Q-rear=Q-front) return 1; /*队列为空时返回1*/else return 0; /*队列非空时返回0*/ 8/8/202245数据结构课程设计设计题目请设计一个算法，用一个栈S将一个队列Q逆置。要求：采用链栈和链队列来实现。调试运行实例： 含多个元素的队列（2，4，6，8，10）； 含一个元素的队列（5）； 空队列（）。 8/8/202246数据结构课程设计解题思路8/8/202247数据结构课程设计课程设计4 Huff

25、man树8/8/202248数据结构课程设计例:a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611188/8/202249数据结构课程设计8/8/202250数据结构课程设计8/8/202251数据结构课程设计Huffman树的定义#define n 7 /n为叶子结点个数#define m 2*n-1 /m为哈夫曼树的结点总数#define MAXVAL 999 /最小权值初始化用typedef int datatype;typedef struct char ch;/存放的字符float weight; /权值datatype lchild,rchild,par

26、ent; /左右孩子域和双亲 hufmtree;8/8/202252数据结构课程设计必做题目题目一对于给定的n个结点的权值，建立一棵哈夫曼树。具体要求如下：算法输入：n个结点的权值。算法输出：哈夫曼树，打印出哈夫曼树的所有的结点序号、双亲结点、左孩子、右孩子和权值。测试数据：结点数n=7，权值为7、5、2、3、8、10、20；结点数n=8，权值为7、19、2、6、32、3、21、10。 8/8/202253数据结构课程设计Huffman算法的应用（一）题目二输入一串字符，根据不同字符的出现频率构造字符的Huffman编码。（1）编码：将输入字符串按 Huffman编码输出（可放到一个文件里）。

27、（2）解码：输入按某Huffman编码的01串，进行译码，输出译码后的字符。8/8/202254数据结构课程设计编码如图所示，输入“hhhhhhhuffffffffman”之后，先输出每个字符的编码，然后输出整个字符串的编码“11111111111111101100000000100110001010”,共38位。8/8/202255数据结构课程设计解码输入“11101100100110001010”输出“huffman”8/8/202256数据结构课程设计Huffman算法的应用（二）题目三输入一串字符，根据不同字符的出现频率构造字符的Huffman编码。（1）编码：将输入字符串按 Huff

28、man编码输出到一个文件里，要求将“0”“1”作为二进制的“0”“1”写入到文件里。提示：需要二进制到十进制的转换。（2）解码：输入按某Huffman编码的文件，进行译码，输出译码后的字符。提示：需要十进制到二进制的转换。8/8/202257数据结构课程设计编码如图所示，输入“hhhhhhhuffffffffman”之后，输出整个字符串的编码“11111111111111101100000000100110001010 0000000110”“255 254 192 54 40 6”(写入文件的内容)最后2个字节：一个用来存放部分有效编码，后面一个字节用来指示前面的一个字节中有效编码的位数（取

29、值18）。每8位二进制数可以用一个short型的无符号整数来表示，整个编码应该占6个字节，而如果用ASCII编码的话，18个字符需要占18个字节。8/8/202258数据结构课程设计解码输入“255 254 192 54 40 6”输出“hhhhhhhuffffffffman”8/8/202259数据结构课程设计要求时间：两次课（本周及下周）题目一必做题目二、三选1个做8/8/202260数据结构课程设计图实验一对给出的无向图，编写一个完整的程序，建立其邻接矩阵，并输出此邻接矩阵。实验二编写一个用菜单驱动的完整的程序，建立无向图的邻接表，要求其邻接表中的结点按顶点序号从大到小顺序排列。实验三编

30、写一个用菜单驱动的完整的程序实现，建立有向图G的邻接表。编一个函数根据用户输入的偶对（以输入0表示结束）建立有向图G的邻接表，并输出这个邻接表。实验四编写一个用菜单驱动的完整的程序实现，利用深度优先搜索方法求出无向图中通过给定点Vi的简单回路（邻接表存储）。 实验五： 编写一个用菜单驱动的完整的程序实现图的深度优先遍历的非递归算法。8/8/202261数据结构课程设计无向图及其邻接矩阵、邻接表8/8/202262数据结构课程设计要求选择一（五选二）请你任选两个题目，将它们编写在一个完整的程序中（两周内完成）。选择二（三选二）三、四、五题中任选二题，对所选的每道题单独编成完整程序（每周完成一个）

31、。8/8/202263数据结构课程设计查找线性表的查找基本知识点：线性表的数据类型定义、查找操作8/8/202264数据结构课程设计一、顺序查找(Sequential Search) 基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。8/8/202265数据结构课程设计又称折半查找，它是一种效率较高的查找方法。要求：要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。二、二分查找 8/8/202266数据结构课程设计Low是查找的开始位置，high是查找的结束位置二分查找的基本思想是：（1）首先确定该区间的中点位置： mid = （2）然后将中间位置记录的键值Rmid.key和所给关键字K进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。8/8/202267数据结构课程设计二分查找判定树的组成如对表R3，7，11，1