——信息管理系《数据结构》实验指导书《DATA STRUCTURES》罗先文LUOXIANWEN西南大学信息管理系Iinformation dept. SouthWest UniversityJanuary 24, 2010写在上机实习之前上机实践是学生对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。
通常，实习题中的问题比平时的习题复杂得多，也更接近实际。
实习着眼于原理与应用的结合，使学生学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。
平时的练习较偏重于如何编写功能单一的“小”算法，而实习题是软件设计的综合训练，包括问题分析，总体结构设计，用户界面设计，程序设计基本技能和技巧，多人合作，以至一整套软件工程规范的训练和科学作风的培养。
此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。
为了达到上述目的，本篇安排了7个主实习单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。
各实习单元与教科书的各章具有紧密的对应关系，在个别实习单元中安排有难度差别不等的多个实习题，以便学生选做。
此外，每个实习题采取了统一的格式，实验目的、实验内容、实验要求、程序实现、程序运行情况和源程序清单等5个部分组成。
在每个实习单元都提供了一个完整的实现代码，仅供同学们参考，绝大多数的同学在上机实习时千万不要机械的照抄本附录所提供的范文。
而是应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。
对于个别成绩较差的同学，实在是没法完成任务的建议你不妨抄一遍附录中的样题，以增强你的感性认识，强化你的实践基础，提高你的实践能力。
本附录样题全部用c语言编写，并全部上机调试通过，但由于时间比较仓促，样题中提供的算法和程序并不是最好的算法和程序，相信不少的同学一定有能力设计出更好的算法和程序。
随着计算机学科的不断发展，可以使用的语言工具越来越丰富，在本篇中的实习示例还只是应用面向过程的语言进行设计和编写的程序，同样的实习题，读者也可以用面向对象的语言来实现。
我们希望实习报告示例能起到一个抛砖引玉的作用，在经过同学们的努力学习和积极使用以后，更多更优良的设计范例能不断涌现。
文中存在的不妥之处，敬请各位不吝赐教！目录《数据结构》实验大纲 (4)实验一、线性表操作 (5)实验二、栈和队列的应用 (9)实验三、多维数组和串 (15)实验四、树和二叉树的操作 (20)实验五、图的操作 (26)实验六、各种查找操作 (33)实验七、各种排序操作 (40)《数据结构》实验大纲一.课程名称：数据结构及算法分析课程编号：课程学时：70课程学分：3.5实验时数：20二.所属实验室名称：计算机中心三.实验教材及参考书：【1】数据结构题集（C语言版）清华大学出版社2000年【2】DATA STRUCTURES WITH C++ 清华大学出版社【3】本材料之后的附录四.实验内容和目的：掌握四种基本数据结构：集合、线性结构、树形结构、网状结构在求解实际问题中的应用，以及培养书写规范文档的技巧。
学习基本的查找和排序技术。
要求学生具有编制相当规模的程序的能力。
养成一种良好的程序设计风格。
五.考核方式：上机考试、编程并运行通过。
六.实验环境：硬件最低要求：586微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。
每个学生每次上机实验使用一台计算机。
软件：C语言或Visual C++6.0七.实验项目及安排实验一、线性表操作一、实验目的1．掌握用C语言调试程序的基本方法。
2．掌握线性表的基本运算，如插入、删除等。
二、实验内容1．线性表在顺序存储结构上的插入元素，删除元素运算2．线性表在链式存储结构上的建链表，插入结点，删除结点运算三、实验要求1．1．C++/C完成算法设计和程序设计并上机调试通过。
2．2．撰写实验报告，提供实验结果和数据。
3．3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、程序实现写出每个操作的算法（操作过程）五、程序运行情况写出输入数据及运行结果六、源程序清单。
程序1：顺序存储的线性表和运算#include<stdio.h>#define MAXSIZE 100int list[MAXSIZE];int n;/*insert in a seqlist*/int sq_insert(int list[], int *p_n, int i, int x){int j;if (i<0 || i>*p_n) return(1);if (*p_n==MAXSIZE) return(2);for (j=*p_n+1; j>i; j--)list[j]=list[j-1];list[i]=x;(*p_n)++;return(0);}/*delete in a seq list*/int sq_delete(int list[], int *p_n, int i){int j;if (i<0 || i>=*p_n) return(1);for (j = i+1; j<=*p_n; j++)list[j-1] = list[j];(*p_n)--;return(0);}void main(){int i,x,temp;printf("please input the number for n\n");printf("n=");scanf("%d",&n);for (i=0; i<=n; i++){printf("list[%d]=",i);scanf("%d",&list[i]);}printf("The list before insertion is\n");for (i=0; i<=n; i++) printf("%d ",list[i]);printf("\n");printf("please input the position where you want to insert a value\nposition=");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 is\n");for(i=0; i<=n; i++) printf("%d ",list[i]);printf("\n");printf("%d\n",n);break;case 1:case 2:printf("The insertion is not successful!\n");break;}/*deleting*/printf("The list before deleting is\n");for (i=0; i<=n; i++) printf("%d ",list[i]);printf("\n");printf("please input the position where you want to delete a value\nposition=");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 is\n");for(i=0; i<=n; i++) printf("%d ",list[i]);printf("\n");printf("%d",n);break;case 1:printf("The deleting is not successful!");break;}}程序2链式存储的线性表和运算#include<stdio.h>#include<malloc.h>struct node{char 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 list\n",n);for (i=0; i<n; i++){scanf("%c ", &(p->data));q=(NODE *)malloc(sizeof(NODE));printf("test3\n");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;else{p=(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);}else{while (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_list\nm=");scanf("%d",&m);getchar();printf("test1\n");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 a\n ch_a=");getchar();scanf("%c",&ch_a);getchar();printf("Please input the value that you want to insert\n 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)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。
