数据结构学习指导.实验指导.课程设计(2008年修改版).doc

目 录第一章 绪论61.1本章内容61.1.1基本内容61.1.2学习要点61.1.3 例题解析61.2习题91.2.1基础题91.2.2 综合题111.3 实验131.3.1验证算法的源程序结构及举例131.3.2实验要求181.3.3 C语言复习实验20第二章 线性表222.1本章内容222.1.1基本内容222.1.2学习要点222.1.3 例题解析222.2习题242.2.1基础题242.2.2 综合题262.3 实验352.3.1实验要求352.3.2线性表操作实验35第三章 栈和队列373.1本章内容373.1.1基本内容373.1.2学习要点373.1.3 例题解析373.2习题403.2.1基础题403.2.2 综合题413.3 实验443.3.1实验要求443.3.2栈和队列操作实验44第四章 串464.1本章内容464.1.1基本内容464.1.2学习要点464.1.3 例题解析464.2习题494.2.1基础题494.2.2 综合题504.3 实验514.3.1实验要求514.3.2串操作实验51第五章 数组与广义表525.1本章内容525.1.1基本内容525.1.2学习要点525.1.3 例题解析525.2习题555.2.1基础题555.2.2 综合题575.3 实验615.3.1实验要求615.3.2数组与广义表操作实验61第6章 树和二叉树626.1 本章内容626.1.1基本内容626.1.2学习要点626.1.3 例题解析626.2 习题656.2.1 基础题656.2.2 综合题696.3 实验716.3.1实验要求716.3.2树和二叉树操作实验72第7章 图747.1 本章内容747.1.1基本内容747.1.2学习要点747.1.3 例题解析747.2 习题777.2.1 基础题777.2.2 综合题797.3 实验827.3.1实验要求827.3.2图操作实验82第8章 查找868.1 本章内容868.1.1 基本内容868.1.2 学习要点868.1.3 例题解析878.2 习题918.2.1 基础题918.2.2 综合题928.3 实验948.3.1实验要求948.3.2查找操作实验94第9章 排序969.1 本章内容969.1.1 基本内容969.1.2 学习要点969.1.3 例题解析979.2 习题1009.2.1 基础题1009.2.2 综合题1029.3 实验1039.3.1实验要求1039.3.2排序操作实验103第10章 数据结构课程设计10510.1 课程设计的基本要求和方法10510.1.1课程设计目的10510.1.2 课程设计的基本要求10510.1.3 课程设计报告内容10510.2 数据结构课程设计题目10610.2.1 一元稀疏多项式计算器10610.2.2 迷宫问题10610.2.3 哈夫曼编/译码器10710.2.4 教学计划编制问题10810.2.5 成绩分析问题10910.2.6 二叉排序树与平衡二叉树的实现11010.2.7 图的基本操作与实现11010.2.8 全国交通咨询模拟11110.2.9 内部排序算法的性能分析11110.2.10 背包问题的求解11110.2.11 简单个人书管理系统的设计与实现11210.2.12 简易电子表格的设计11210.2.13 停车厂模拟管理程序的设计与实现11210.2.14 农夫过河问题的求解11210.2.15 电话号码查询系统112附录A 参考答案112第一章 绪论参考答案1121.2.1 基础题答案1121.2.2 综合题答案1121.3.3 C语言复习实验答案112第二章 线性表参考答案1122.2.1 基础题答案1122.2.2 综合题答案1122.3.2线性表操作实验答案112第三章 栈和队列参考答案1123.2.1 基础题答案1123.2.2 综合题答案1123.3.2 栈和队列操作实验答案112第四章 串参考答案1124.2.1基础题答案1124.2.2 综合题答案1124.3 串操作实验答案112第五章 数组与广义表参考答案1125.2.1基础题答案1125.2.2 综合题答案1125.3.2 数组与广义表操作实验答案112第六章 树和二叉树参考答案1126.2.1 基础题答案1126.2.2 综合题答案1126.3.2树和二叉树操作实验答案112第七章 图参考答案1127.2.1 基础题答案1127.2.2 综合题答案1127.3.2图操作实验答案112第八章 查找参考答案1128.2.1基础题答案1128.2.2 综合题答案1128.3.2 查找操作实验答案112第九章 排序参考答案1129.2.1基础题答案1129.2.2 综合题答案1129.3.2 排序操作实验答案112第10章 数据结构课程设计参考答案11210.2.1 一元稀疏多项式计算器参考答案11210.2.2 迷宫问题参考答案11210.2.3 哈夫曼编/译码器参考答案11210.2.4 教学计划编制问题参考答案11210.2.5 成绩分析问题参考答案11210.2.6 二叉排序树与平衡二叉树的实现参考答案11210.2.7 图的基本操作与实现参考答案11210.2.9 内部排序算法的性能分析参考答案11210.2.10 背包问题的求解参考答案112附录B 课程设计报告范文112参考文献112 第一章 绪论1.1本章内容1.1.1基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；算法的定义、设计的基本要求以及从时间和空间角度分析算法的方法。1.1.2学习要点（1） 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。熟悉逻辑结构的四种基本类型和存储结构两种基本机内表示方法。（2） 理解算法五个要素的确切含义：1）动态有穷性（能执行结束）；2）确定性（对于相同的输入执行相同的路径）；3）有输入；4）有输出；5）可行性（用以描述算法的操作都是可实现的）。（3） 掌握计算语句频度和估算算法时间复杂度的方法。1.1.3 例题解析【例1-1】有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它分别属于何种结构。（1）L=(D,R)，其中D=1，2，3，4，5，6，7，8R=rr=,（2）T=(D,R)，其中D=1，2，3，4，5，6，7，8R=rr=,（3）G=(D,R)，其中D=1，2，3，4，5，6，7R=rr=,，解：（1）对应的图形如图1-1所示。图1-1 线性结构在L中，每一个数据元素有且只有一个前驱元素（除第一个结点5外），有且只有一个后续（除最后一个元素6外），所以为线性结构。（2）对应的图形如图1-2所示。图 1-2 树型结构在T中，每一个数据元素有且只有一个前驱元素（除根结点1外），但可以有任意多个后续结点（树叶可看成为具有0个后续结点），所以为树型结构。(3) 对应的图形如图1-3所示。图 1-3 有向图型结构在G中，每一个数据元素可以有任意多个前驱元素和任意多个后续元素，所以为图型结构。【例1-2】 求下列算法的时间复杂度。 （1）int sum(int a,int n)/*累加求和*/s=0;/*给累加变量s赋初值*/for (i =0; i n; i +) /*进行累加求和*/ s+=ai; return(s);/*返回s的值*/（2）matrixadd(int an, int bn, int cn, int n) /*矩阵相加*/*a,b,c分别为n阶矩阵，a,b表示两个加数，c表示和*/for (i=0; in; +i)for (j=0; j1 & change; -i) change = FALSE; for (j=0; j aj+1) temp=aj; aj=aj+1; aj+1=temp; change = TRUE; /* bubble_sort*/（4）void select_sort(int a, int n) /*将a中整数序列重新排列成自小至大有序的整数序列*/ for ( i = 0; i n-1; +i ) j = i; for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) ajai /*select_sort*/（5）for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n) goto L2; /*n+1次*/ s+=ai; /*n次*/ i +;/*n次*/ goto L1/*n次*/L2:return (s); /* 1次*/因此该算法的时间复杂性为：T(n)=4n+4=O(n)（2）通过与（1）相似的分析过程，可得到该算法的时间复杂性为：T(n)=4n2+5n+2=O(n2)（3）基本操作为赋值操作，次数未知，最坏情况下的次数为n(n+1)/2，时间复杂度：O(n2)（4）基本操作为比较(数据元素)操作，时间复杂度：O(n2)（5）基本操作为乘法操作，时间复杂度：O(n3)1.2习题1.2.1基础题单项选择题1数据对象是指_。 A. 描述客观事物且由计算机处理的数值、字符等符号的总称 B. 数据的基本单位C. 性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2在数据结构中，数据的基本单位是_。A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 3数据结构中数据元素之间的逻辑关系被称为_。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构4在数据结构中，与所使用计算机无关的是数据的_。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 5在链式存储结构中，数据之间的关系是通过_体现的。A. 数据在内存的相对位置 B. 指示数据元素的指针C. 数据的存储地址 D. 指针6在定义ADT时，除数据对象和数据关系外，还需说明_。 A. 数据元素 B. 算法 C. 基本操作 D. 数据项7计算算法的时间复杂度是属于一种_。A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法8在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_。 A. n2 B. nlogn C. n D. logn 9设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_。A. O(1) B. O(n) C. O(200n) D. O(nlog2n)10有如下递归函数fact(a)，其时间复杂度为_。 int fact(int a) if(n=0) retrun 1; else return(n*fact(n-1); A. O(n) B. O(n2) C. O(n3) D. O(n4)11线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以12线性结构的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取填空题1数据结构由数据的 、 和 三部分组成。 2程序包括两个内容： 和 。 3数据结构在物理上可分为 存储结构和 存储结构。4数据的物理结构，指数据元素在 中的表示，也即 。5数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。 6我们把每种数据结构均视为抽象类型，它不但定义了数据的 方式，还给出了处理数据的 。 7一个算法的时间复杂度是用该算法 的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的_的大小来度量的。8算法具有如下特点： 、可执行性、 、结果性、一般性。9对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的 的意义，并在 内计算出结果。10下面程序段的时间复杂度为 。 i=1; while(i0) if(d%2=1) p=p*f;f=f*f; d=d/2; 6设 n 为正整数。试确定下列各程序段中前置以记号的语句的频度： （1）i = 1; k = 0;while (i=n - 1) k + = 10 * i ; i +;（2）i =1;k=0;do k+=10* i; i +;while (i =n-1)(3) i = 1; k = 0;while (i=n - 1) i +; k + = 10 * i ;(4) k = 0;for ( i = 1;i=n ;i+) for ( j = i;j=n ;j+) k + +;(5) i=1;j=0;while (i+jj) j+; else i+;(6) for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=(y+1) * (y + 1) y +;(8) x= 91; y= 100;while (y0) if (x100)x-=10; y - -; else x + ;7阅读下列算法：void suan_fa(int n)int i, j,k,s,x; for(s=0, i=0; in; i+ ) for(j=i; jn; j+) s+; i=1;j=n; x=0; while(ij) i+; j-; x+=2; printf(“s=%d”, “x=%d”, s,x); （1）分析算法中语句“s+;”的执行次数；（2）分析算法中语句“x+=2;”的执行次数；（3）分析算法的时间复杂度；（4）假定n=5，试指出执行该算法的输出结果。8求两个 n 阶矩形的乘法 C=AB，其算法如下，分析该算法的时间复杂度。 #define MAX 100 void maxtrixmult(int n，float aMAXMAX，float bMAXMAX，float cMAXMAX) int i，j，k； float x； for (i=1；i=n；i+) for (j=1；j=n；j+) x=0； for(k=1;karrsize 或对某个k(1kn)使k!*2k maxint时，应按出错处理，注意选择你认为较好的出错处理方法。 1.3 实验1.3.1验证算法的源程序结构及举例目前数据结构教材上的算法一般用类C语言来描述，但要验证算法只能用标准C来验证，所以存在类C语言与标准C的转换及验证算法的源程序编写问题。1类C语言与标准C的转换要点（1）预定义常量和类型的问题在类C语言的算法中出现了下列常量，验证时就需在源程序中定义：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define int Status（2）算法描述的变量问题在类C语言算法（函数）中，辅助变量没有作变量说明，但在验证源程序的函数定义时，需对所有使用的变量（除函数参数外）作说明。例1.3 顺序表的插入算法中变量说明类C语言算法描述：Status ListInsert_Sq(SqList &L, int pos, ElemType e) /* 在顺序线性表L的第pos个元素之前插入新的元素e，pos为位序*/* pos的合法值为1posListlength_Sq(L)+1*/if (pos 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.elempos-1); /* q指示插入位置*/for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;/* 插入位置及之后的元素右移*q = e; /* 插入e*/+L.length; /* 表长增1*/return OK; /*ListInsert_Sq*/验证算法源程序中算法所对应的函数定义：int ListInsert_Sq(SqList *L, int pos, ElemType e)ElemType *newbase,*p,*q;if (pos L-length+1) return (-1);if (L-length = L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(-1);L-elem = newbase;L-listsize += LISTINCREMENT;q =&(L-elem)pos-1);for (p=&(L-elem)L-length-1);p=q;-p) *(p+1)=*p;*q = e;+L-length;return (1);（3）算法描述的参数问题在类C语言算法（函数）中，在形参定义时，以“&”打头的参数作为引用参数，即在函数调用后发生改变的量，但在验证源程序的函数定义时，需对引用参数转换为指针类型，在函数定义内，把引用参数的使用转换为引用参数对象的使用。例1.4 顺序表的插入算法中参数问题类C语言描述：Status ListInsert_Sq(SqList &L, int pos, ElemType e) if (pos 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.elempos-1); for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;*q = e; +L.length; return OK; 验证算法源程序中算法所对应的函数定义：int ListInsert_Sq(SqList *L, int pos, ElemType e)ElemType *newbase,*p,*q;if (pos L-length+1) return (-1);if (L-length = L-listsize)newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(-1);L-elem = newbase;L-listsize += LISTINCREMENT;q =&(L-elem)pos-1);for (p=&(L-elem)L-length-1);p=q;-p) *(p+1)=*p;*q = e;+L-length;return (1);2验证算法的源程序结构文件包含预处理符号常量的定义类型定义/*确定数据结构*/返回类型 自定义函数名（形式参数表）/*自定义函数的定义，即算法*/ main()变量定义；/*定义处理对象*/建立对象；/*根据存储类型，给变量赋值，以确定具体的处理对象*/调用自定义函数；/*引用函数对处理对象进行操作，实现算法的功能*/打印输出；/*给出结果*/3验证算法的源程序举例例1.5 顺序表插入算法的验证方法顺序表的插入算法：Status ListInsert_Sq(SqList &L, int pos, ElemType e) if (pos 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.elempos-1);for (p = &(L.elemL.length-1); p = q; -p) *(p+1) = *p;*q = e; +L.length;return OK; 验证“顺序表的插入算法”的源程序：/*文件包含预处理*/#include #include /*符号常量的定义*/#define LIST_INIT_SIZE 5#define LISTINCREMENT 5/*类型定义（确定数据结构）*/typedef int ElemType;typedef struct ElemType *elem;int length;int listsize; SqList; int InitList_Sq(SqList *L)L-elem=(ElemType*)malloc(LIST_INIT_SIZE *sizeof(ElemType);if (!L-elem) exit(-1);L-length = 0;L-listsize = LIST_INIT_SIZE;return (1);int ListInsert_Sq(SqList *L, int pos, ElemType e)ElemType *newbase,*p,*q;if (pos L-length+1) return (-1);if (L-length = L-listsize)newbase = (ElemType *)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof (ElemType);if (!newbase) exit(-1);L-elem = newbase;L-listsize += LISTINCREMENT;q =&(L-elem)pos-1);for (p=&(L-elem)L-length-1);p=q;-p) *(p+1)=*p;*q = e;+L-length;return (1);void traverse(SqList L) int i; printf(the list data is:n); for (i=0;iL.length;i+) printf(%5d,L.elemi); printf(n); getchar(); void main()int i; SqList L; /*定义处理对象*/InitList_Sq(&L); /*建立对象：根据存储类型，给变量赋值，以确定具体的处理对象*/for (i=1;inext; if(s=NULL) return; q=NULL; p=s; while(p!=NULL) p=p-next; s-next=q; /*逆转指针*/ q=s; /*指针前移*/ s=p; h-next=q; /*头指针h的后继是p*/【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C中的元素c为 例如：A=(3,5,8,11) B=(2,6,8,9,11,15,20)则 C=(2,3,5,6,8,8,9,11,11,15,20)实现本题功能的函数如下：Lnode *hb(Lnode *pa,Lnode *pb)Lnode *p,*q,*pc; pc=(Lnode*)malloc(sizeof(Lnode); /*建立表c 的头结点pc*/ p=pc; /*p指向C表头结点*/ while(pa!=NULL&pb!=NULL) q=(Lnode*)malloc(sizeof(Lnode); /*建立新结点q*/ if(pb-datadata) /*比较A、B表中当前结点的数据域值的大小*/ q-data=pb-data; /*B中结点值小，将其值赋给q的数据域*/ pb=pb-next; /*B中指针pb后移*/ else q-data=pa-data; /*相反，将A结点值赋给q的数据域*/ pa=pa-next; /*A中指针pa后移*/ p-next=q; /*将q接在p的后面*/p=q; /*p始终指向C表当前尾结点*/while(pa!=NULL) /*若表A比B长，将A余下的结点链在C表尾*/ q=(Lnode*)malloc(sizeof(Lnode); q-data=pa-data; pa=pa-next; p-next=q; p=q; while(pb!=NULL) /*若表B比A长，将B余下的结点链在C表尾