数据结构实训指导书.doc

项目（实训）指导书系 别： 计算机系 专 业： 软件工程 课 程： 数据结构 制 订 人： 审 核 人： 制订时间： 2012年2月 目录目录项目一 线性表- 1 -项目二 栈- 8 -项目三 队列- 13 -项目四 串- 19 -项目五 二叉树- 23 -项目六 图- 28 -项目七 排序- 33 - 41 -数据结构与算法-项目（实训）指导书项目一 线性表一、 项目（实训）名称线性表的创建、插入和删除二、 项目（实训）学时数4学时三、 项目（实训）目标实训目标：1、掌握线性表的逻辑特征2、掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算3、熟练掌握线性表的链式存储结构定义及基本操作4、理解循环链表和双链表的特点和基本运算5、加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行结果。2、说明调试过程中出现的现象3、实训报告获得的知识：1、顺序表的定义及基本操作算法。2、链表的定义及基本操作算法。3、掌握数据结构程序的编写方法。四、 项目（实训）中的具体任务1、编写程序，实现顺序表的创建、插入和删除等基本操作算法。具体要求：(1)顺序表的存储结构定义#define MAXSIZE 100typedef int ElemType;typedef struct SqList ElemType dataMAXSIZE; int length;SqList; (2)从键盘上依次输入21、18、30、75、42、56，创建顺序表，并输出顺序表中的各元素值。(3)分别在顺序表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出顺序表中的各元素值。(4)删除顺序表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出顺序表中的各元素值。2、编写程序，实现链表的创建、插入和删除等基本操作算法。具体要求：(1)单链表的存储结构定义typedef int ElemType;typedef struct LinkNodeElemType data; / 数据域struct LinkNode *next; / 指针域 LinkList; (2)从键盘上依次输入21、18、30、75、42、56，逆序创建单链表，并输出单链表中的各元素值。(3)分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值。(4)删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。五、 教师知识和能力要求1、提供线性表定义数据类型代码；2、提供线性表基本操作，如插入、删除等函数的名称。六、 学生知识和能力准备1、复习C语言中数组的用法；2、了解线性表和顺序表的概念，顺序表的定义方法；3、掌握线性表在顺序存储结构上实现基本操作：查找、插入、删除和合并的算法。4、复习C语言中指针的用法，特别是结构体的指针的用法；5、了解单链表的概念，单链表的定义方法；6、掌握线性表在链式存储结构上实现基本操作：查找、插入、删除的算法；7、提交实训报告。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点1、顺序表的部分代码：(1)顺序表结构的定义：#define MAXSIZE 100typedef int ElemType;typedef struct SqList ElemType dataMAXSIZE; int length;SqList;(2)顺序表插入（在第i号元素前插入一个新的元素）int insertList(SqList *sq,int i,int x)int j;if(isq- length -1)printf(n The value of i is wrong!);return 0;if(sq- length = MAXSIZE)printf(n overflow!); return 0;for(j=sq-length;j=i;j-)sq-dataj+1=sq-dataj;sq-datai=x;sq-length+;return 1; (3)顺序表删除int deleteList(SqList *sq,int i)if(isq- length)printf(n the position is wrong!n); return 0;for(i;ilength;i+)sq-datai-1=sq-datai;sq-length-;return 1;2、单链表的部分代码(1)单链表的结构定义：typedef int ElemType;typedef struct LinkNode ElemType data; struct LinkNode *next;LinkNode,*LinkList;(2)建立单链表的算法int n; /*n作为整个程序的全局变量*/LinkList create(void)LinkNode *head,*p1, *p2;n=0;p1=p2=(LinkNode *)malloc(sizeof(LinkNode);scanf(%d,&p1-data);head=NULL;while(p1-data!=0)n=n+1;if(n=1) head=p1;else p2-next=p1;p2=p1;p1=(LinkNode *)malloc(sizeof(LinkNode);scanf(%d,&p1-data);p2-next=NULL;return(head); (3)单链表的插入算法int insertLink(LinkList head, int i,ElemType e)LinkNode *p, *s; int j;p=head; j=0;while(p & jnext;j+;if(!p|ji-1) printf(无法插入);return 0;s=(LinkNode *)malloc(sizeof(LinkNode);s-data=e;s-next=p-next;p-next=s;return 1; (4)单链表的删除算法int deleteLink(LinkList head,int i) LinkNode *p, *q;int j;p=head; j=0;while(p-next & jnext;j+;if(!(p-next)|ji-1) printf(无法删除);return 0;q=p-next;p-next=q-next;free(q);return 1;十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目二 栈一、 项目（实训）名称栈二、 项目（实训）学时数2学时三、 项目（实训）目标实训目标：1、熟练掌握栈的特点2、掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用3、加深对栈结构的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行结果。2、说明调试过程中出现的现象3、实训报告获得的知识：1、熟练掌握栈的概念和特点2、理解并掌握栈的基本操作算法描述。四、 项目（实训）中的具体任务1、编写程序，实现顺序栈的创建、进栈和出栈等基本操作算法。具体要求：(1)顺序栈的定义#define MAXSIZE 5typedef int ElemType;typedef struct ElemType stackMAXSIZE;int top;QStackType;(2)依次进栈数据为1,2,3,4,5，再全部出栈，输出出栈序列。(3)先进栈3,2,1，出栈2次，进栈4,5,6,7，再全部出队，输出每次入栈，出栈序列。2、编写程序，实现链栈的创建、进栈和出栈等基本操作算法，具体要求同上。五、 教师知识和能力要求1、提供栈定义数据类型主要代码；2、提供栈相关操作，如进栈、出栈等函数的名称及代码算法。六、 学生知识和能力准备1、掌握栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；2、熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。3、提交实训报告。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点主要代码：(1)顺序栈的结构定义#define MAXSIZE 5typedef int ElemType;typedef struct ElemType stackMAXSIZE;int top;QStackType;(2)顺序栈的初始化算法void initQStack(QStackType *s)s-top=-1; (3)顺序栈进栈操作算法int pushQStack(QStackType *s,ElemType x)if(s-top=MAXSIZE-1) return 0;else s-stack+(s-top)=x;printf(%d ,s-stacks-top);return 1; (4)顺序栈出栈操作算法ElemType popQStack(QStackType *s)if(s-topstacks-top);return(s-stack(s-top)-); (5)链栈的结构定义typedef int ElemType;typedef struct node ElemType data; struct node *next;LinkStack;LinkStack *top;(6)链栈的进栈操作算法void push(LinkStack *top,ElemType x) LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack); p-data=x; p-next=top-next; top-next=p; (7)链栈的出栈操作算法ElemType pop(LinkStack *top) LinkStack *p; ElemType x; p=top-next; if(p=NULL) printf(“栈已空！”); return 0; else top-next=p-next; x=p-data; free(p); return(x); 十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目三 队列一、项目（实训）名称队列二、项目（实训）学时数2学时三、项目（实训）目标实训目标：1、熟练掌握队列的特点2、掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作3、加深对队列结构的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行结果。2、说明调试过程中出现的现象。3、实训报告获得的知识：1、熟练掌握队列的概念和特点2、理解并掌握队列的基本操作算法描述。四、项目（实训）中的具体任务1、编写程序，实现顺序队列的创建、入队和出队等基本操作算法。具体要求：(1)顺序队列的定义#define MAXSIZE 6typedef int ElemType;typedef struct QueueNodeElemType dataMAXSIZE;int front;int rear; SeQueue;(2)依次入队数据为1,2,3,4,5，再全部出队，输出出队队列序列。(3)先入队数据3,2,1，出队2次，入队4,5,6,7，最后所有数据出队，输出每次入队和出队序列。2、编写程序，实现循环队列的创建、入队和出队等基本操作算法，具体要求同上。五、 教师知识和能力要求1、提供队列定义数据类型主要代码；2、提供队列相关操作，如入队、出队等函数的名称及代码算法。六、 学生知识和能力准备1、掌握队列这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；2、熟练掌握循环队列和链队列的基本操作实现算法，特别注意在循环队列中队满和队空的描述方法。3、提交实训报告。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点主要代码：(1)顺序队列的结构定义：#define MAXSIZE 6typedef int ElemType;typedef struct QueueNodeElemType dataMAXSIZE;int front;int rear; SeQueue; (2)初始化队列void initQueue(SeQueue *q)q-front=-1;q-rear=-1;(3)顺序队列的进队列操作算法（在队列尾插入）void enQueue(SeQueue *q,ElemType x)if (q-rearrear+;q-dataq-rear=x;printf(%d ,q-dataq-rear);elseprintf(n队已满，%d无法入队，请清空队列！n,x);(4)顺序队列的出队列操作算法（在队列头删除）void deQueue(SeQueue *q)ElemType x;if (q-frontfront+;x=q-dataq-front;printf(%d ,x);elseprintf(n队中已无数据！n); (5)循环队列的结构定义#define MAXSIZE 6typedef int ElemType;typedef struct ElemType queueMAXSIZE; int front; int rear; CirQueueType;(5)循环队列进队列操作算法int InCirQueue(CirQueueType *q,ElemType x) if(q-rear+1)%MAXSIZE=q-front) printf(“n 队列已满！”); return 0; q-rear=(q-rear+1)%MAXSIZE; q-queueq-rear=x;return 1;(6)循环队列出队列操作算法 ElemType OutCirQueue(CirQueueType *q) if (q-front=q-rear) printf(“n 队列已空！”); return 0; q-front=(q-front+1)%MAXSIZE; return q-queueq-front; 十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目四 串一、 项目（实训）名称串二、 项目（实训）学时数2学时三、 项目（实训）目标实训目标：1、掌握串的顺序和链式存储结构的实现方法；2、掌握串的模式匹配算法；3、能够学会利用串解决一些实际问题。最终成果：1、演示程序运行的过程和结果。2、说明调试过程中出现的现象。3、实训报告。获得的知识：1、理解并掌握串的概念。2、熟练掌握串常见算法的编写。四、 项目（实训）中的具体任务1、设计串的模式匹配算法（子串定位）。2、若s和t是两个采用顺序结构存储的串，编写一个比较两个串大小的算法，若st，则返回1，若st，则返回-1，否则返回0。五、 教师知识和能力要求1、提供串定义数据类型主要代码；2、提供串相关操作算法。六、 学生知识和能力准备1、了解串的存储方法，理解串的两种模式匹配算法。2、掌握串的顺序和链式存储结构的实现方法；3、提交实训报告。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点主要代码：1、匹配算法(1)串存储结构的定义#define MAXSIZE 100typedef struct char strMAXSIZE; int curlen;string;(2)匹配算法int matchStr(string *s,string *t) int i,j; i=0; j=0; while (icurlen & jcurlen) if (s-stri=t-strj) i+; j+; else i=i-j+1; j=0; if (j=t-curlen) return (i-j+1); else return 0;十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目五 二叉树一、 项目（实训）名称二叉树二、 项目（实训）学时数2学时三、 项目（实训）目标实训目标：1、熟练掌握二叉树的二叉链表存储结构2、掌握二叉树的非线性和递归性特点3、熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现4、加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行的过程和结果。2、说明调试过程中出现的现象。3、实训报告。获得的知识：1、理解并掌握二叉树的定义及特点；2、熟练掌握二叉树遍历的方法。四、 项目（实训）中的具体任务1、用前序方法建立一棵二叉树。2、编写前序遍历、中序遍历、后序遍历二叉树的程序。具体要求：(1)二叉树的二叉链表存储结构类型的定义。typedef char ElemType;typedef struct BinTreeNode ElemType data; struct BinTreeNode *lchild; struct BinTreeNode *rchild;BinTreeNode; (2)建立下图所示的二叉树。(3)编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列。(4)统计以上二叉树中叶子结点的个数。五、 教师知识和能力要求1、提供二叉树定义数据类型主要代码；2、提供二叉树相关操作代码算法。六、 学生知识和能力准备1、了解树的结构特点及概念、二叉树的概念及结构特点。2、了解树和二叉树的基本概念和术语。3、二叉树的三种遍历方法（先序、中序、后序遍历）4、二叉树的各种存储结构及其适用范围，特别是链式存储结构。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点主要代码：(1)二叉树的链式存储结构定义typedef char ElemType;typedef struct BinTreeNode ElemType data; struct BinTreeNode *lchild; struct BinTreeNode *rchild;BinTreeNode; (2)二叉树的建立算法BinTreeNode *CreateBinTree()BinTreeNode *t;ElemType ch;char yes;/scanf(%c,&ch); /读入一个字符 printf(n请输入结点：);ch=getche();t=(BinTreeNode *)malloc(sizeof(BinTreeNode); /生成一个新结点t-data=ch;printf(n是否要生成%c的左子树(y/n)?,ch);yes=getche();/scanf(%c,&yes);if (yes=y)t-lchild=CreateBinTree(); /生成左子树elset-lchild=NULL;printf(n是否要生成%c的右子树(y/n)?,ch);/scanf(%c,&yes);yes=getche();if (yes=y)t-rchild=CreateBinTree(); /生成右子树elset-rchild=NULL;printf(n); return t; (3)二叉树的先序遍历算法void PreOrderTraverse(BinTreeNode *t)ElemType e;if(t)e=t-data;printf(%c,e);PreOrderTraverse(t-lchild);PreOrderTraverse(t-rchild);二叉树的中序遍历和后序遍历算法与先序遍历算法类似。十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目六 图一、项目（实训）名称图二、 目（实训）学时数2学时三、 项目（实训）目标实训目标：1、熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法2、掌握图的基本运算及应用3、加深对图的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行的过程和结果。2、说明调试过程中出现的现象。3、实训报告。获得的知识：1、理解并掌握图的定义和特点。2、熟练掌握图的基本算法，如最短路径算法等。四、 项目（实训）中的具体任务1、求从某个源点到其余各顶点的最短路径算法（迪杰斯特拉算法）；2、求每一对顶点之间的最短路径算法（费洛伊德算法）。五、 教师知识和能力要求1、提供图定义数据类型主要代码；2、提供图相关操作代码算法。六、 学生知识和能力准备1、图的定义和基本术语；2、图的四种存储结构（数组表示法、邻接表、十字链表和邻接多重表）；3、图的两种遍历策略（深度优先搜索和广度优先搜索），并应该注意图的遍历和树的遍历算法之间的区别；4、图的连通性、连通分量和最小生成树的概念和实现方法；5、拓扑排序和关键路径、两类求最短路径问题的解法。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点主要代码：(1)图的结构定义（这里使用数组表示法）#define MaxInt 32767/表示极大值#define MVNum 10/最大顶点数typedef char VerTexType;/顶点数据类型typedef int ArcType;typedef struct AMGraphVerTexType vexsMVNum;/顶点表ArcType arcsMVNumMVNum;/邻接矩阵int vexnum,arcnum;/图的当前点数和边数AMGraph; (2)迪杰斯特拉算法 void ShortestPath_DIJ(AMGraph *g,int v0)int v,n,w;int sMVNum,dMVNum,pathMVNum;int min;int i;n=g-vexnum;for(v=0;varcsv0v;if(dvMaxInt)pathv=v0;elsepathv=-1; dv0=0; sv0=1; for(v=1;vn;v+) min=MaxInt; for(w=0;wn;w+)if(!sw & dwmin) v=w;min=dw; sv=1; for(w=0;warcsvwarcsvw;pathw=v; for (i=0;in;i+)printf(%d,si); (3)费洛伊德算法 void ShortestPath_Floyed(AMGraph *g)int v,u,w;int dMVNumMVNum,pathMVNumMVNum;for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)dvw=g-arcsvw;if(dvwMaxInt)pathvw=1; elsepathvw=-1;for(u=0;uvexnum;u+)for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(dvu+duwdvw)dvw=dvu+duw;pathvw=pathuw;十、 考核或评价标准实训成绩将主要根据学生对待实训的态度、对关键知识点和编程技巧的掌握程度、实训报告的内容、答辩情况等进行综合评定。最后的成绩将分优秀、良好、中等、及格和不及格五个等级。具体评判标准如下：优秀：实训认真、刻苦，有钻研精神，不无故缺席。熟练掌握了本实训的关键知识点，具有良好的独立思考问题和解决问题的能力，具备了较好的C语言编程能力，编制的程序运行正确。实训记录内容丰富、齐全，答辩时能清晰明了地阐明问题，回答问题反映敏捷、思路清晰。良好：能认真对待实训，不无故缺席。掌握了本实训的关键知识点，具备了较好的C语言编程能力，编写的程序运行正确。实训记录内容齐全，答辩时能清晰明了地阐明问题，能正确回答全部问题。中等：能认真对待实训，不无故缺席。基本掌握了本实训的关键知识点，具备了一定的C语言编程能力，编写的程序运行基本正确，无致命错误。实训记录内容较齐全，答辩时能正确回答大部分问题。及格：对待实训不够认真，有少量迟到、早退或无故缺席现象。基本掌握了本实训的主要内容，具有了用C语言编程的基本能力，但掌握不全面、扎实，编写的程序总体结构符合要求，基本能正常运行，但还存在少量错误。实训记录内容基本齐全，答辩时能在教师提示下正确回答大部分问题。不及格：对待实训马虎、敷衍，经常迟到、早退或无故缺席。不能正确理解本实训的主要内容，不具备基本的C语言编程能力，编制的程序不能正常运行，或是抄袭他人程序，应付答辩。答辩时即使经教师提示仍不能正确回答大部分问题。项目七 排序一、 目（实训）名称排序二、 项目（实训）学时数2学时三、 项目（实训）目标实训目标：1、熟练掌握常用排序算法的基本思想及实现2、深刻理解各种算法的特点，并加以灵活应用3、加深对查找和排序的理解，逐步培养解决实际问题的编程能力最终成果：1、演示程序运行的过程和结果。2、说明调试过程中出现的现象。3、实训报告。获得的知识：1、理解各种排序算法的基本思想及特点。2、掌握各种排序算法的程序设计方法。四、 项目（实训）中的具体任务设有关键字序列k= 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 ,试用各种排序算法进行排序。具体要求：(1)从键盘输入上述8个整数，存放在数组quick8中，并输出值。(2)输出各种排序算法每一趟排序的结果，观察关键字次序的变化。(3)如果上述8个整数按照升序输入，即k1= 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 ，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。(4)如果上述8个整数按照降序输入，即k2= 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。(5)测试各排序算法的执行时间，比较执行效率。(6)随机产生3万个数，对其进行排序，观察其结果。五、 教师知识和能力要求1、提供各种排序算法代码描述。2、提供演示编写程序的步骤。六、 学生知识和能力准备1、掌握排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。七、 工具与设备1、PC机。2、Windows 2003/XP操作系统。3、Visual Studio C+ 6。八、 教学资料数据结构与算法(C语言版)，严蔚敏著，人民邮电出版社，2011年2月九、 实施步骤与技术要点部分代码：typedef int SeqList;(1)插入排序代码void InsertSort(SeqList *sqList,int n)int i,j,t;printf(插入排序过程n);for (i = 1; i n; i+) if (sqListi = 0 & t sqListj; j-) sqListj + 1 = sqListj; sqListj + 1 = t; printf(第%d趟排序过程：,i);printSeqList(sqList,n); (2)冒泡排序代码void