线性表的抽象数据类型的实现
淮海工学院计算机工程学院
实验报告书
课程名：数据结构
题目：线性表的抽象数据类型的实现
班级：D软件101
学号：511021112
姓名：丁冬梅
评语：
成绩：指导教师：
批阅时间：2011年月日
1实验题目或内容
实验题目：
一、顺序表的基本操作实现实验
二、链表（带头结点）基本操作实验
实验内容：
一、按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：
1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；
2）打印（遍历）该线性表（依次打印出表中元素值）；
3）在线性表中查找第i个元素，并返回其值；
4）在线性表中第i个元素之前插入一已知元素；
5）在线性表中删除第i个元素；
6）求线性表中所有元素值（整数）之和；
二、按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：
1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；
2）打印（遍历）该链表（依次打印出表中元素值）；
3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；
4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；
5）在链表中按照有序方式插入一已知字符元素；
6）在线性表中删除第i个结点；
7）计算链表的长度。
2目的与要求
实验目的：
1）掌握线性表的顺序存储结构和链式存储结构；
2）熟练掌握顺序表和链表基本算法的实现；
3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；
4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；
5）按时提交实验报告。
实验要求：
一、要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：
1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；
2）打印（遍历）该线性表（依次打印出表中元素值）；
3）在线性表中查找第i个元素，并返回其值；
4）在线性表中第i个元素之前插入一已知元素；
5）在线性表中删除第i个元素；
6）求线性表中所有元素值（整数）之和；
二、要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：
1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；
2）打印（遍历）该链表（依次打印出表中元素值）；
3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；
4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素；
6）在线性表中删除第i个结点；
7）计算链表的长度。
3实验步骤与源程序
一、顺序表的源程序
#include
#include
#include
int list[25];int i,n,a,sum=0,k,l;
int eleminsert;
/*------------------创建函数--------------*/
void initlist()
{
printf("Please input the total of the elems:");
scanf("%d",&n);
if(n>25||n<1) {printf("ERROE!");return;}
printf("Please input the elems:...\n");
for(i=0;i {scanf("%d",&list[i]); } return; } /*------------------打印函数--------------*/ void Print(int list[],int n) { int j; for(j=0;j printf("%d\t",list[j]); printf("\n"); return; } /*------------------查找函数------------*/ void Search(int list[],int n,int m) { if(m<1||m>n){printf("ERROR!\n"); return ;} else printf("The elem is %d at %d place\n",list[m-1],m); return; } /*----------------插入函数------------*/ void Insert(int list[],int n,int m,int elem) { int j; if(m<1||m>n){printf("ERROR!\n"); return ;} for(j=n-1;j>=m-1;j--) {list[j+1]=list[j];} list[m-1]=elem; n=n+1; printf("The new list are:" ); Print(list,n); return; } /*---------------删除函数-----------*/ void Delete(int list[],int n,int m) { int q; if(m<1||m>n) {printf("ERROR!\n"); return ;} for(q=m-1;q<=n;q++) {list[q]=list[q+1];} printf("The new list are:"); Print(list,n-1); return; } /*-------------求和函数------------*/ void Sum(int list[],int n,int sum) { int j; for(j=0;j {sum=sum+list[j];} printf("The sum is :%d",sum); return; } void menu() { int j; /*------------菜单函数------------*/ menulab: printf("********************** MENU ******************\n\n"); printf("Create a new int list :...................press 1\n\n"); printf("Print the whole list :....................press 2\n\n"); printf("Search by order :........................press 3\n\n"); printf("Insert the elem in the place i:...........press 4\n\n"); printf("Delete the elem by order :................press 5\n\n"); printf("Sum all elem in the list :................press 6\n\n"); printf("exit the programe :.......................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~6)....."); checklabel: scanf("%1d",&j);getchar(); if(j<0||j>7) {printf("Error! Please choose again......"); goto checklabel; } printf("\n\tYou choose the number %d\n ",j); printf("\n\tPress any key to continue....."); getchar(); system("cls"); /*clear screen*/ switch(j) { case 1:/*创建任意整数线性表*/ initlist(); system("cls"); /*clear screen*/ goto menulab; case 2: /*打印（遍历）该线性表*/ printf("The original list is:"); Print(list,n); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 3:/*在线性表中查找第i个元素，并返回其值*/ printf("Input which LNode you want to Search(Input number):"); scanf("%d",&a); getchar(); Search(list,n,a); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 4:/*在线性表中第i个元素之前插入一已知元素*/ printf("Please input the elem's place where you want to insert"); scanf("%d",&k); printf("Input the elem which you want to insert:"); scanf("%d",&eleminsert); Insert(list,n,k,eleminsert); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 5:/*在线性表中删除第i个元素*/ printf("Please input the elem you want to delete:"); scanf("%d",&l); n=n+1; Delete(list,n,l); n=n-1; printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 6:/*求线性表中所有元素值（整数）之和*/ Sum(list,n,sum); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 0:/*退出程序*/ printf("Press any key to continue....."); getchar(); exit(0); }} void main() { void menu(); menu(); } 二、链表（带头结点）的源程序 #include #include struct LNode{ char elem; struct LNode* next; }*l,*p,*new; int i,a,k,n;char c,s; /*----------------创建函数-------------*/ void intilist(void) { l=(struct LNode *)malloc(sizeof(struct LNode)); l->next=NULL; system("cls"); printf("Input the total of the elems:....."); scanf("%d",&n); getchar(); if(n>15) printf("Error!"); for(i=n;i>0;i--) { new=(struct LNode *)malloc(sizeof(struct LNode)); new->next=l->next;l->next=new; } p=l; while(p->next!=NULL) p=p->next; p->next=l; printf("Input elems:.......\n"); p=l->next; for(i=1;i<=n;i++) { scanf("%c",&p->elem);getchar(); p=p->next; } return; } /*----------------排序函数-------------*/ void Sequence(struct LNode * l, int n) { int i;char swap,*e,*f; for(i=1;i<=n-1;i++) { p=l->next; while(p->next!=l) {if(p->elem>p->next->elem) {e=&p->elem; f=&p->next->elem;swap=*e;*e=*f;*f=swap;} p=p->next;} } return; } /*----------------打印函数-------------*/ void Print(struct LNode * l, int n) { int i; p=l->next; for(i=1;i<=n;i++) { printf("%c\t",p->elem); p=p->next; } printf("\n"); return; } /*----------------查找函数-------------*/ void Locate(struct LNode * l, int n,int m) { int i; if(m>n) { printf("FALSE!\t");return; } else { p=l; for(i=1;i<=m;i++) {p=p->next;} printf("The elem is:%c\n",p->elem); } return; } /*------已知字母匹配首结点查找函数------*/ void LocateLNode(struct LNode * l, int n,char m) { int i; p=l; for(i=1;i<=n;i++) {p=p->next; if(p->elem==m) {printf("TRUE!\n");return;}} if(i>n) printf("FALSE!\n"); return; } /*----------------插入函数-------------*/ void Insert(struct LNode * l, int n,char m) { new=(struct LNode *)malloc(sizeof(struct LNode)); new->next=l->next; l->next=new; new->elem=m; n=n+1; Sequence(l,n); Print(l,n); return; } /*----------------删除函数-------------*/ void Delete(struct LNode * l, int n,int m) { int i; p=l; for(i=1;i {p=p->next;} p->next=p->next->next; n=n-1; printf("The new list is:"); Print(l,n); return;} /*----------------求表长函数-------------*/ void Length(int n) { int i;int length=0; for(i=1;i<=n+1;i++) {length=length+sizeof(struct LNode);} printf("The length of the list is:%d",length); return; } /*----------------菜单函数-------------*/ void menu() { int j; menulab: printf("********************** MENU ******************\n\n"); printf("Create the new list :..................press 1\n\n"); printf("Sequence the list :...................press 2\n\n"); printf("Search the Lnode by order :............press 3\n\n"); printf("Search the Lnode by elem :.............press 4\n\n"); printf("Insert the elem :......................press 5\n\n"); printf("Delete the elem by order :.............press 6\n\n"); printf("Return the length of the list :........press 7\n\n"); printf("exit the programe :....................press 0\n\n"); printf("********************** END *******************\n\n"); printf("Please choose the number from (0~7)....."); checklabel: scanf("%1d",&j);getchar(); if(j<0||j>7) {printf("Error! Please choose again......"); goto checklabel; } printf("\n\tYou choose the number %d\n ",j); printf("\n\tPress any key to continue....."); getchar(); system("cls"); /*clear screen*/ switch(j) { case 1:/*创建链表并输入元素*/ intilist(); system("cls"); /*clear screen*/ goto menulab; case 2: /*排序并打印链表*/ Sequence(l,n); printf("The orignal list is:\n"); Print(l,n); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 3:/*查找第i个元素*/ printf("Input which LNode you want to locate(Input number):"); scanf("%d",&a);getchar(); Locate(l,n,a); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 4:/*查找与已知字符相同的第一个结点*/ printf("Input the elem you want to search "); scanf("%c",&c);getchar(); LocateLNode(l,n,c); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 5:/*插入已知字符的结点*/ printf("Input the elem you want to insert:"); scanf("%c",&s);getchar(); Insert(l,n,s); n=n+1; printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 6:/*删除第i个结点*/ printf("Input which one you want to delete:"); scanf("%d",&k); if(k<1||k>n)printf("ERROR!"); else{Delete(l,n,k);} n=n-1; getchar(); system("cls"); /*clear screen*/ goto menulab; case 7:/*计算链表长度*/ Length(n); printf("Press any key to continue....."); getchar(); system("cls"); /*clear screen*/ goto menulab; case 0:/*退出链表程序*/ printf("Press any key to continue....."); getchar(); exit(0); }} /*------------------主函数---------------*/ main() { void menu(void); menu(); } 4测试数据与实验结果 一、顺序表程序抓图及其简要说明 菜单选项如下图所示：该菜单由八个函数组成，实现八项功能 选择菜单1，创建一个链表。 如上图所示的操作，其余也是一样例如，当选择“2”时如下图： 当执行1时如下图：创建链表完成，按任意键返回到菜单 当执行2时如下图： 当执行3时如下图： 当执行4时如下图： 当执行5时如下图： 当执行6时如下图： 当执行0时：退出程序，按任意键返回到菜单。 二、链表（带头结点）程序抓图及其简要说明 菜单函数如下图所示：该菜单包含了程序的八项基本操作，实现了创建、排序、查找、以及删除等功能。具体执行过程如下 选择菜单1，创建一个链表。 如上图所示的操作，其余也是一样例如，当选择“2”时如下图： 当执行1时如下图：创建链表完成，按任意键返回到菜单 当执行2时如下图：链表排序成功，将排好的链表打印出来，按任意键返回到菜单。 当执行3时如下图：按排序位置查找节点，并打印出查得元素，按任意键返回到菜单。 当执行4时如下图：按元素查找与之相同的节点，返回TURE或FALSE，按任意键返回到菜单。 当执行5时如下图：插入元素，自动排序，打印出新链表元素，按任意键返回到菜单。 当执行6时：删除一元素，打印出要删除的元素，按任意键返回到菜单。 当执行7时如下图：打印出链表长度，按任意键返回到菜单。 当执行0时：退出程序，按任意键返回到菜单。 5结果分析与实验体会 一、顺序表的基本操作实现实验 原程序代码中clrscr(); 都要改成system("cls"); Search(l,n,a);都要改成Search(list,n,a);起初的时候执行到第四步老是直接跳到第一步，不懂为什么，就去问同学了，后来才知道原来要接着执行第二步，通过此次实验，我了解了线性表的顺序存储结构，掌握了顺序表的基本算法核心，利用线性表数据结构作出相关程序。 有些程序看不懂，是但是看很多书，反复琢磨就能理解其实质，虽然中间出过错误，但是最后能调试出结果，作完题目。整体的技巧灵活性还需要加强，我会在以后的实验中，多多训练，提高灵活性 二、链表（带头结点）基本操作实验 同样运行程序出错，需要改代码，把源程序中的“new”都要改成例如“newn”，clrscr(); 都要改成system("cls");然后根据要求一步步坐下来，刚开始先做的是链表带头节点基本实验操作，程序执行时不会参照它我才完成顺序表的基本操作实现实验，开始不懂里面的内涵，慢慢一步一步自己琢磨，发现其实操作不难，主要自己耐心看书学习，虚心求教，这就是我此次实验的的心得体会 ADT Rational { //起名要易懂 数据对象：D={e1,e2|e1,e2∈Z,e2≠0} //分母不为零 数据关系：R={ Status InitRational(Rational &Q,ElemType v1, ElemType v2){ //构造有理数Q，分子分母分别为v1,v2，若v2=0则Q赋空，返回Error if(v2==0){Q=NULL;return ERROR;} /*return后括号可有可无*/ Q=(ElemType *)malloc(2*sizeof(ElemType)); //莫忘malloc.h if(!Q)exit(OVERFLOW);//分配存储空间失败, stdlib.h,注意!及适用场合用法Q[0]=v1;Q[1]=v2; /*之前的else可省略，若不省略最好加花括号*/ return(OK); } Status DestroyRational(Rational &Q) //销毁有理数Q { if(Q) { free(Q); Q=NULL; return OK; } } void OutputRational(Rational Q){ //以分数形式输出有理数Q if(!Q)printf(“the rational does not exist! \n‘); printf(“ %d/%d ”,Q[0],Q[1]); } 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 上机5 设计strcmp（s，t）算法，实现两个串和的比较 代码： #include (1) 整数型 整数包括bigint、int、smallint和tinyint，从标识符的含义就可以看出，它们的表示数范围逐渐缩小。 l bigint：大整数，数范围为-263 (-9223372036854775808)～263-1 (9223372036854775807) ，其精度为19，小数位数为0，长度为8字节。 l int：整数，数范围为-231 (-2,147,483,648) ～231 - 1 (2,147,483,647) ，其精度为10，小数位数为0，长度为4字节。 l smallint：短整数，数范围为-215 (-32768) ～215 - 1 (32767) ，其精度为5，小数位数为0，长度为2字节。 l tinyint：微短整数，数范围为0～255，长度为1字节，其精度为3，小数位数为0，长度为1字节。 (2) 精确整数型 精确整数型数据由整数部分和小数部分构成，其所有的数字都是有效位，能够以完整的精度存储十进制数。精确整数型包括decimal 和numeric两类。从功能上说两者完全等价，两者的唯一区别在于decimal不能用于带有identity关键字的列。 声明精确整数型数据的格式是numeric | decimal(p[,s])，其中p为精度，s为小数位数，s的缺省值为0。例如指定某列为精确整数型，精度为6，小数位数为3，即decimal(6,3)，那么若向某记录的该列赋值56.342689时，该列实际存储的是56.3427。 decimal和numeric可存储从-1038 +1 到1038 –1 的固定精度和小数位的数字数据，它们的存储长度随精度变化而变化，最少为5字节，最多为17字节。 l 精度为1～9时，存储字节长度为5； l 精度为10～19时，存储字节长度为9； l 精度为20～28时，存储字节长度为13； l 精度为29～38时，存储字节长度为17。 例如若有声明numeric(8,3)，则存储该类型数据需5字节，而若有声明numeric(22,5)，则存储该类型数据需13字节。 注意：声明精确整数型数据时，其小数位数必须小于精度；在给精确整数型数据赋值时，必须使所赋数据的整数部分位数不大于列的整数部分的长度。 (3) 浮点型 浮点型也称近似数值型。顾名思义，这种类型不能提供精确表示数据的精度，使用这种类型来存储某些数值时，有可能会损失一些精度，所以它可用于处理取值范围非常大且对精确度要求不是十分高的数值量，如一些统计量。 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ Excel中常用的数据类型 在Excel的单元格中可以输入多种类型的数据，如文本、数值、日期、时间等等。下面简单介绍这几种类型的数据。 1．字符型数据。在Excel中，字符型数据包括汉字、英文字母、空格等，每个单元格最多可容纳32000个字符。默认情况下，字符数据自动沿单元格左边对齐。当输入的字符串超出了当前单元格的宽度时，如果右边相邻单元格里没有数据，那么字符串会往右延伸；如果右边单元格有数据，超出的那部分数据就会隐藏起来，只有把单元格的宽度变大后才能显示出来。 如果要输入的字符串全部由数字组成，如邮政编码、电话号码、存折帐号等，为了避免Excel把它按数值型数据处理，在输入时可以先输一个单引号“'”(英文符号)，再接着输入具体的数字。例如，要在单元格中输入电话号码“64016633”，先连续输入“'64016633”，然后敲回车键，出现在单元格里的就是“64016633”，并自动左对齐。 2．数值型数据。在Excel中，数值型数据包括0~9中的数字以及含有正号、负号、货币符号、百分号等任一种符号的数据。默认情况下，数值自动沿单元格右边对齐。在输入过程中，有以下两种比较特殊的情况要注意。 (1)负数：在数值前加一个“”号或把数值放在括号里，都可以输入负数，例如要在单元格中输入“66”，可以连续输入“66”“(66)”，然后敲回车键都可以在单元格中出现“66”。 (2)分数：要在单元格中输入分数形式的数据，应先在编辑框中输入“0”和一个空格，然后再输入分数，否则Excel会把分数当作日期处理。例如，要在单元格中输入分数“2/3”，在编辑框中输入“0”和一个空格，然后接着输入“2/3”，敲一下回车键，单元格中就会出现分数“2/3”。 3．日期型数据和时间型数据。在人事管理中，经常需要录入一些日期型的数据，在录入过程中要注意以下几点： (1)输入日期时，年、月、日之间要用“/”号或“-”号隔开，如“2002-8-16”“2002/8/16”。 (2)输入时间时，时、分、秒之间要用冒号隔开，如“10:29:36”。 (3)若要在单元格中同时输入日期和时间，日期和时间之间应该用空格隔开。 （信息技术教育室供稿） 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 实验三串 //串的基本操作 #include "stdio.h" #include "stdlib.h" #define MAXSTRLEN 255 typedef unsigned char SString[MAXSTRLEN+1]; void strlength(SString S)//求字串并放到 S[0] 中 { int m; for(m=1;S[m]!='\0';m++); S[0]=m-1; } void insert(SString S,int n,char a)//是插入的位置 a 是插入的字符{ strlength(S); int i; for(i=S[0];i>=n;i--) S[i+1]=S[i]; S[n]=a; S[S[0]+2]='\0'; } int compare(SString S,SString T) { strlength(S); strlength(T); int i; for(i=1;i<=S[0]&&i<=T[0];i++) { if(S[i]>T[i]) return 1; if(S[i] else if(S[0] 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 抽象数据类型线性表的定义如下： ADT List { 数据对象：D={ a i | a i∈ElemSet, i =1, 2, ……, n, n≥0} 数据关系：R1 = { < a i-1 , a i > | a i-1 , a i ∈D, i =2, ……, n } 基本操作： InitList (&L ) 操作结果：构造一个空的线性表L 。 DestoryList (&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ClearList (&L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty (L) 初始条件：线性表L已存在。 操作结果：若L 为空表，则返回TRUE，否则返回FALSE。 ListLength (L) 初始条件：线性表L已存在。 操作结果：返回L中数据元素个数。 GetElem ( L, i, &e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。 操作结果：用e返回L中第i个数据元素的值。 LocateElem ( L,e, compare() ) 初始条件：线性表L已存在，compare()是判定函数。 操作结果：返回L中第1个与e满足关系compare() 的数据元素的位序。若这样的数据元素不存在，则返 回值0。 PriorElem ( L, cur_e, &pre_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素且不是第1个， 则用pre_e返回它的前驱，否则操作失败。 NextElem ( L, cur_e, &next_e ) 初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素且不是最后一个， 则用next_e返回它的后继，否则操作失败。 ListInsert ( &L, i, e ) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e， L的长度加1。 ListDelete( &L, i, &e ) 初始条件：线性表L已存在且非空，1≤i≤ListLength(L)。 操作结果：删除L的第i个数据元素，并用e返回其值， 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 实验一抽象数据类型的表示与实现 一．实验目的及要求 （1）熟悉类C语言的描述方法，学会将类C语言描述的算法转换为C源程序实现； （2）理解抽象数据类型的定义，编写完整的程序实现一个抽象数据类型（如三元组）； （3）认真阅读和掌握本实验的参考程序，上机运行程序，保存和打印出程序的运行结果，并结合程序进行分析。 二．实验内容 （1）编程实现对一组从键盘输入的数据，计算它们的最大值、最小值等，并输出。 要求：将计算过程写成一个函数，并采用引用参数实现值的求解。 （2）编程实现抽象数据类型三元组的定义、存储和基本操作，并设计一个主菜单完成各个功能的调用。 三．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现对一组从键盘输入的数据，计算它们的最大值、最小值等，并输出。 要求：将计算过程写成一个函数，并采用引用参数实现值的求解。 程序代码部分： 头文件： #define N 10000 void comparason(double a[],int n,double &max,double &min); 主函数： #include"" #include"" int main() { int n; printf("请输入数据个数\n"); scanf("%d",&n); double a[N],max,min; int i; printf("请输入数据（空格隔开）\n"); for(i=0;i 专题1 数据结构分类与抽象数据类型 1.1 数据结构分类 数据结构讨论现实世界和计算机世界中的数据及其相互之间的联系，这体现在逻辑和存储两个层面上，相应称之为逻辑结构和存储结构。也就是说，在现实世界中讨论的数据结构是指逻辑结构，在计算机世界中讨论的数据结构是指存储结构，又称为物理结构。 数据的逻辑结构总体上分为4种类型：集合结构、线性结构、树结构和图结构。数据的存储结构总体上也分为4种类型：顺序结构、链接结构、索引结构和散列结构。原则上，一种逻辑结构可以采用任一种存储结构来存储（表示）。 对于现实世界中的同一种数据，根据研究问题的角度不同，将会选用不同的逻辑结构；对于一种逻辑结构，根据处理问题的要求不同，将会选用不同的存储结构。 对于复杂的数据结构，不论从逻辑层面上还是从存储层面上看，都可能包含有多个嵌套层次。如假定一种数据结构包含有两个层次，第一层（顶层）的逻辑结构可能是树结构，存储结构可能是链接结构；第二层（底层）的逻辑结构可能是线性结构，存储结构可能是顺序结构。第一层结构就是数据的总体结构，第二层结构就是第一层中数据元素的结构。 数据的逻辑结构通常采用二元组来描述，其中一元为数据元素的集合，另一元为元素之间逻辑关系的集合，每一个逻辑关系是元素序偶的集合，如 课题一的具体实验内容 1、构造元素类型为整型的线性表，将以下元素插入分别插入线性表： <34 56 20 9 15 5> 2、查找表中是否存在元素20，实现元素20与元素9的交换； 3、按照课题要求编写函数，实现线性表元素<34 56 9 20 15 5>的倒置，即倒置后的表应为< 5 15 20 9 56 34 >。 #include //free(h); //以下为链表的输出 p=L->next; printf("交换后输出\n"); while(p!=NULL) { printf("%d\n",p->num); p=p->next; } //以下为链表的倒置 p=L; while(p->next->next!=NULL) p=p->next; q=p->next; q->next=p; p->next=NULL; p=L; for(i=0;i<4;i++) {while(p->next->next!=NULL) p=p->next; k=p->next; k->next=p; p->next=NULL; p=L; } L->next=q; //倒置后链表的输出 p=L->next; printf("倒置后输出\n"); while(p!=NULL) { printf("%d ",p->num); p=p->next; } }有理数抽象数据类型定义
数据结构试题及答案
严蔚敏版数据结构课后习题答案-完整版
数据结构线性表2答案
数据结构串的比较
数据库常用数据类型
数据结构课后习题及答案
Excel中常用的数据类型
数据结构试题答案
数据结构串基本操作代码
数据结构线性表答案
数据结构习题与答案
抽象数据类型线性表的定义
数据结构线性表的应用实验报告
数据结构作业及答案
抽象数据类型的表示与实现(实验一)
抽象数据类型
数据结构C语言实现线性表插入键、交换、倒置