数据结构实验指导书(C语言版)-罗先文.doc

信息管理系数据结构实验指导书DATA STRUCTURES罗先文LUOXIANWEN西南大学信息管理系Iinformation dept. SouthWest UniversityJanuary 24, 2010写在上机实习之前上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。通常，实习题中的问题比平时的习题复杂得多，也更接近实际。实习着眼于原理与应用的结合，使学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工程规范的训练和科学作风的培养。此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。为了达到上述目的，本篇安排了7个主实习单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。各实习单元与教科书的各章具有紧密的对应关系，在个别实习单元中安排有难度差别不等的多个实习题，以便学生选做。此外，每个实习题采取了统一的格式，实验目的、实验内容、实验要求、程序实现、程序运行情况和源程序清单等5个部分组成。在每个实习单元都提供了一个完整的实现代码，仅供同学们参考，绝大多数的同学在上机实习时千万不要机械的照抄本附录所提供的范文。而是应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。对于个别成绩较差的同学，实在是没法完成任务的建议你不妨抄一遍附录中的样题，以增强你的感性认识，强化你的实践基础，提高你的实践能力。本附录样题全部用c语言编写，并全部上机调试通过，但由于时间比较仓促，样题中提供的算法和程序并不是最好的算法和程序，相信不少的同学一定有能力设计出更好的算法和程序。随着计算机学科的不断发展，可以使用的语言工具越来越丰富，在本篇中的实习示例还只是应用面向过程的语言进行设计和编写的程序，同样的实习题，读者也可以用面向对象的语言来实现。我们希望实习报告示例能起到一个抛砖引玉的作用，在经过同学们的努力学习和积极使用以后，更多更优良的设计范例能不断涌现。文中存在的不妥之处，敬请各位不吝赐教！目录数据结构实验大纲4实验一、线性表操作2实验二、栈和队列的应用6实验三、多维数组和串12实验四、树和二叉树的操作17实验五、图的操作23实验六、各种查找操作30实验七、各种排序操作37数据结构实验大纲一. 课程名称：数据结构及算法分析课程编号：课程学时：70课程学分：3.5实验时数：20二. 所属实验室名称：计算机中心三. 实验教材及参考书：【1】数据结构题集（C语言版） 清华大学出版社 2000年【2】DATA STRUCTURES WITH C+ 清华大学出版社【3】本材料之后的附录四. 实验内容和目的：掌握四种基本数据结构：集合、线性结构、树形结构、网状结构在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。要求学生具有编制相当规模的程序的能力。养成一种良好的程序设计风格。五. 考核方式：上机考试、编程并运行通过。六. 实验环境：硬件最低要求：586微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。每个学生每次上机实验使用一台计算机。软件：C语言或Visual C+6.0七. 实验项目及安排序号实验名称类别学时目的与安排备注必选选开1链表、数组4插入、删除、合并、排序、查找2栈与队列43递规算法4汉诺塔问题4树及应用4递规、非递规遍历5图及应用4遍历算法、最小生成树6排序查找4排序、查找算法比较分析7串及应用4匹配算法8线索树4中序线索化操作Data Structures and Algorithm西南大学信息管理系 第 41 页 实验一、线性表操作一、实验目的1掌握用 C语言调试程序的基本方法。2掌握线性表的基本运算，如插入、删除等。二、实验内容1线性表在顺序存储结构上的插入元素，删除元素运算2线性表在链式存储结构上的建链表，插入结点，删除结点运算三、实验要求1 1 C+/C完成算法设计和程序设计并上机调试通过。2 2 撰写实验报告，提供实验结果和数据。3 3 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）五、程序运行情况写出输入数据及运行结果六、源程序清单 。程序1：顺序存储的线性表和运算#include#define MAXSIZE 100int listMAXSIZE;int n;/*insert in a seqlist*/int sq_insert(int list, int *p_n, int i, int x)int j;if (i*p_n) return(1);if (*p_n=MAXSIZE) return(2);for (j=*p_n+1; ji; j-)listj=listj-1;listi=x;(*p_n)+;return(0);/*delete in a seq list*/int sq_delete(int list, int *p_n, int i)int j;if (i=*p_n) return(1);for (j = i+1; j=*p_n; j+)listj-1 = listj;(*p_n)-;return(0);void main()int i,x,temp;printf(please input the number for nn);printf(n=);scanf(%d,&n);for (i=0; i=n; i+)printf(list%d=,i); scanf(%d,&listi);printf(The list before insertion isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to insert a valuenposition=);scanf(%d,&i);printf(please input the value you want to insert.nx=);scanf(%d,&x);temp=sq_insert(list,&n,i,x);switch(temp)case 0:printf(The insertion is successful!n);printf(The list is after insertion isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%dn,n);break;case 1:case 2:printf(The insertion is not successful!n);break;/*deleting*/printf(The list before deleting isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to delete a valuenposition=);scanf(%d,&i);temp=sq_delete(list,&n,i);switch(temp)case 0:printf(The deleting is successful!n);printf(The list is after deleting isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%d,n);break;case 1:printf(The deleting is not successful!);break;程序2链式存储的线性表和运算#include#includestruct nodechar data;struct node *next;typedef struct node NODE;/*This function creates a link_list with N nodes.*/NODE *create_link_list(int n)int i;NODE *head, *p, *q;if (n=0) return NULL;head = (NODE *) malloc(sizeof(NODE);p = head; printf(Please input %d chars for the link listn,n);for (i=0; idata);q=(NODE *)malloc(sizeof(NODE);printf(test3n);p-next=q;p=q;scanf(%c ,&(p-data);getchar();p-next=NULL;return (head);/*This function inserts a node whose value is b*/*before the node whose value is a, if the node is not exist,*/*then insert it at the end of the list*/void insert(NODE *p_head, char a, char b)NODE *p, *q;q = (NODE *)malloc(sizeof(NODE);q-data = b;q-next =NULL;if (* p_head = NULL) * p_head = q;elsep=(NODE*)malloc(sizeof(NODE);p = * p_head;while (p-data != a & p-next != NULL)p = p-next;q-next = p-next;p-next = q;/*The function deletes the node whose value is a,*/*if success, return 0, or return 1*/int deletenode(NODE *p_head, char a)NODE *p, *q;q=*p_head;if (q=NULL) return(1);if (q-data = a)* p_head = q-next;free(q);return (0);elsewhile (q-data != a & q-next != NULL)p = q;q = q-next;if (q-data = a)p-next = q-next;free(q);return(0);else return(1);void main()NODE *my_head,*p;/* create a link list with m nodes */int m;char ch_a,ch_b;printf(please input the number of nodes for the link_listnm=);scanf(%d,&m);getchar();printf(test1n);my_head = (NODE *) malloc(sizeof(NODE);my_head=create_link_list(m);/*Output the link list*/printf(The link list is like:n);p=my_head;while (p != NULL)printf(%c ,p-data);p=p-next;printf(n);/*insert a node whose value is b before a*/printf(Please input the position for an ch_a=);getchar();scanf(%c,&ch_a);getchar();printf(Please input the value that you want to insertn ch_b=);scanf(%c,&ch_b);getchar();insert(&my_head,ch_a,ch_b);printf(The link list after insertion is like:n);p=my_head;while (p != NULL)printf(%c ,p-data);p=p-next;printf(n);/*delete a node whose value is a*/printf(Please input the position for a a=);scanf(%c,&ch_a);getchar();deletenode(&my_head,ch_a);printf(The link list after deleting is like:n);p=my_head;while (p != NULL)printf(%c ,p-data);p=p-next;printf(n);实验二、栈和队列的应用一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵。二、实验内容1顺序栈的实现和运算2链栈的实现和运算3顺序队列的实现和运算4链式队列的实现和运算5循环队列的实现和运算三、实验要求1用C+/C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）程序运行情况五、写出输入数据及运行结果六、源程序清单 。程序1：顺序栈的实现和运算#include#define MAXN 26char stackMAXN;int top=0;int push(char x)if (top = MAXN)return(1); stacktop+=x; return(0);int pop(char *p_y)if (top = 0)return(1); *p_y = stack-top; return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to pushn);scanf(%c,&ch_x);while(ch_x!=0)if (push(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to pushnch_x=);getchar();scanf(%c,&ch_x);i=0;while(stacki!=0)printf(%c , stacki);i+;if (pop(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The pop char is %cn,ch_y);for (i=top-1; i=0; i-)printf(%c , stacki);程序2：链栈的实现和运算#include #include struct nodechar data; struct node *link;typedef struct node NODE;NODE * top = NULL;void push_l(char x)NODE *p; p = (NODE * )malloc(sizeof(NODE); p-data = x; p-link = top; top = p;int pop_l(char *p_y)NODE *p; if (top = NULL)return(1); * p_y = top-data; p = top; top = top-link; free(p); return(0);void main()NODE *p;char ch_x,ch_y;printf(input the char you want to pushn);scanf(%c,&ch_x);while(ch_x!=0)push_l(ch_x);getchar();scanf(%c,&ch_x);p=(NODE*)malloc(sizeof(NODE);p=top;while(p!=NULL)printf(%c ,p-data);p=p-link;printf(n);if (pop_l(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The pop char is %cn,ch_y);p=(NODE*)malloc(sizeof(NODE);p=top;while(p!=NULL)printf(%c ,p-data);p=p-link;printf(n);程序3：顺序队列的实现和运算#include#define MAXN 26char qMAXN;int head = -1, tail = -1;int en_queue(char x )if (tail = MAXN-1)return(1);q+tail = x;return(0);int de_queue(char *p_y )if (head = tail)return(1);*p_y = q+head;return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)if (en_queue(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to enqueuench_x=);getchar();scanf(%c,&ch_x);i=1;while(qi!=0)printf(%c , qi);i+;if (de_queue(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The dequeue char is %cn,ch_y);for (i=head+1; i=tail; i+)printf(%c , qi);程序4：链式队列的实现和运算#include#includestruct nodechar data; struct node * link;typedef struct node NODE;NODE *head, *tail;void en_queue_l(char x)NODE *p; p = (NODE *)malloc(sizeof(NODE); p-data = x; p-link = NULL; if (head = NULL)head = p; elsetail-link = p; tail = p;int de_queue_l(char *p_y)NODE *p; if (head = NULL)return(1); *p_y = head-data; p = head; head = head-link; free(p); return(0);void main()NODE *p;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)en_queue_l(ch_x);getchar();scanf(%c,&ch_x);p=(NODE*)malloc(sizeof(NODE);p=head;while(p!=NULL)printf(%c ,p-data);p=p-link;printf(n);if (de_queue_l(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The dequeue char is %cn,ch_y);p=(NODE*)malloc(sizeof(NODE);p=head;while(p!=NULL)printf(%c ,p-data);p=p-link;printf(n);程序5：循环队列的实现和运算#include#include#define MAXN 26char qMAXN;int head = 0, tail = 0;int en_c_q(char x)tail = (tail + 1) % MAXN;if (tail = head)if (tail = 0) tail = MAXN-1; else tail-;return(1);qtail = x;return(0);int de_c_q(char *p_y)if (head = tail) return(1); head = (head+1) % MAXN; *p_y = qhead; return(0);void main() int i;char ch_x,ch_y;printf(input the char you want to enqueuen);scanf(%c,&ch_x);while(ch_x!=0)if (en_c_q(ch_x)=1) printf(failure!n);elseprintf(success!n);printf(input a char for ch_x to enqueuench_x=);getchar();scanf(%c,&ch_x);i=1;while(qi!=0)printf(%c , qi);i+;if (de_c_q(&ch_y)=1) printf(failure!n);elseprintf(success!n);printf(The dequeue char is %cn,ch_y);for (i=head+1; i=tail; i+)printf(%c , qi);实验三、多维数组和串一、实验目的1掌握稀疏矩阵的特点(三元组存储方法)。2掌握串的运算（赋值，比较，联结，插入子串，模式匹配等）。二、实验内容1稀疏矩阵的存储及转置运算2串的基本操作三、实验要求1用C+/C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）程序运行情况五、写出输入数据及运行结果六、源程序清单 。程序1：稀疏矩阵的存储及转置运算#include typedef struct int row ; int col ; int val ; THA ;#defineMAX 20main( ) int i, j, count=1 ; int col, row, val ; THA sMAX; THA tMAX; printf(input the number of row ,col and elements:); scanf(%d,%d,%d,&s0.row,&s0.col,&s0.val); if(s0.val=0) return ; val =s0.val; for(i=1;i=val;i+); scanf(%d,%d,%d,&si.row,&si.col,&si.val); row = s0.row ; col= s0.col ; count=1 ; for( i=1; i= col ; i+)for ( j=1; j=val ; j+) if (sj.col=i) tcount.row = sj.col; tcount.col = sj.row; tcount+.val = sj.val; t0.row = col ; t0.col = row ; t0.val = val ; for(i=0;i=val;i+)printf(%d,%d,%dn,ti.row,ti.col,ti.val); 程序2：串的实现和运算#include #define MAXN 128typedef enum fail,success status;typedef enum false,true boolean;main() int strlen(); void strass(); boolean strcmp(); status strcat( ); status strins(); void patmatch(); int t,n,i; boolean b; status st; char sMAXN,s1MAXN,s2MAXN; printf(n1. The length of stringn); printf( 2. The assignment of stringn); printf( 3. A string compare with another string:n); printf( 4. A string connect with another string:n); printf( 5. A string to be inserted into another stringn); printf( 6. The pattern match of string :); printf( Please input a opertation:); scanf(%d,&t); switch(t) case 1: printf(please input a string:n); getchar(); gets(s); n=strlen(s); printf(the length is: %d,n); break; case 2: printf(please input the first string:n); getchar(); gets(s1); printf(please input the second string:n); getchar(); gets(s2); strass(s1,s2); break; case 3: printf(please input the first string:n); getchar(); gets(s1); printf(please input the second string: n); gets(s2); b=strcmp(s1,s2); if (b=true) printf(equaln); else printf(not equaln); break; case 4: printf(please input the first string:n); getchar(); gets(s1); printf(please input the second string:n); gets(s2); st=strcat(s1,s2); if(st=success) printf(answer is %sn,s1); else printf(error!n); break; case 5: printf(please input the first string:n); getchar(); gets(s1); printf(please input the second string:n); gets(s2); printf(please input i:); scanf(%d,&i); st=strins(s1,i,s2); if(st=success) printf(answer is %sn,s1); else printf(error!n); break; case 6: patmatch(); break; default: printf(There isnt this operation!); int strlen(s)char s; int i; for(i=0;si!=0;i+); return (i);void strass(s1,s2)char s1,s2; int i=0; while(s1i!=0) s2i=s1i; i+; s2i=0; printf(s2 is %s,s2); boolean strcmp(s1,s2)char s1,s2; int i=0; while (s1i=s2i & s1i!=0 & s2i!=0) i+; if (s1i=0 & s2i=0) return (true); else return (false);status strcat (s1,s2)char s1,s2; int i,j,k; i=strlen(s1); j=strlen(s2); if(i+j)=MAXN) return(fail); for(k=0;k=j;k+) s1i+k=s2k; return (success);status strins (s1,i,s2) char s1,s2; int i; int m,n,k; m=strlen(s1); n=strlen(s2); if (im|(m+n)MAXN ) return (fail) ; for(k=m;k=i;k-)s1k+n=s1k; for(k=0;kn;k+)s1i+k=s2k; return (success); int smatch(ch,n,pat,m)char ch,pat; int n,m; int s,p,k; for(s=0;s=n-m;s+) for(p=0,k=s;p=0) printf(nMatched sub string found in position %d,result); 实验四、树和二叉树的操作一、实验目的1进一步掌握树的结构及非线性特点，递归特点和动态性。2进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。二、实验内容1二叉树的实现和运算2线索二叉树的实现3哈夫曼树的实现三、实验要求1用C+/C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、程序实现写出每个操作的算法（操作过程）程序运行情况五、写出输入数据及运行结果六、源程序清单 。程序1：二叉树的实现和运算#include #include #include typedef struct btnode char data; /*suppose the data fields type is char*/ struct btnode *lchild; /*left pointer field */ struct btnode *rchild; /*right pointer field */ NODE;void main()NODE *root,*q,n;NODE *create(NODE *p);void preorder(NODE *root);void inorder(NODE *root);void postorder(NODE *root); int t;q=&n;root=create(q);printf(At the first,we create a treen);printf(Please input nodes of treen);if (root=NULL) printf(Its an empty tree!n);else printf(n1.The preordetraverse n); printf( 2.The inordertraverse n); printf( 3.The postordertraverse n);printf( Please choose a kind