《算法与数据结构》上机指导书
《 算法与数据结构 》课程上机指导书电子信息工程 专业周月霞 编佛山科学技术学院2005 年 8 月摘 要本书是为了配合电子信息工程专业《算法与数据结构》课程而编写的，与高等教育出版社出版的《数据结构――用C语言描述》（唐策善等编）相配套本指导书针对教学内容组织了十三个上机实验题目，分别涵盖线性表、栈与队列、串、数组和广义表、树和二叉树、图、动态存储管理、集合（查找表）、内部排序和外部排序、文件等内容并给予必要的上机指导，使学生能更深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序 本书内容丰富，涉及面广，实用性强，与《算法与数据结构》课程内容紧密结合可以供各类学生课程学习使用，也可供教师或其他专业技术人员参考目 录 前言实验一 顺序表基本操作………………………………… 1实验二 顺序表其它操作………………………………… 5实验三 链表基本操作…………………………………… 10实验四 链表其它操作…………………………………… 14实验五 表达式求值……………………………………… 24实验六 数组的建立和使用……………………………… 26实验七 二叉树基本操作………………………………… 26实验八 二叉树其它操作………………………………… 27实验九 图的基本操作…………………………………… 29实验十 图的其它操作…………………………………… 33实验十一 二叉排序树操作………………………………… 41实验十二 哈希表操作……………………………………… 44实验十三 各种内部排序方法……………………………… 52主要参考书 …………………………………………………… 57附录1 程序设计风格和注释要求…………………………… 58附录2 上机实验报告格式…………………………………… 59前 言算法与数据结构是计算机科学与技术专业和其他有志从事计算机技术工作的人员的一门重要的专业基础课。
算法与数据结构课程的教学要求是学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应的算法，初步掌握算法的时间与空间性能分析技巧，得到复杂程序设计的训练本书是与高等教育出版社出版的《数据结构――用C语言描述》（唐策善等编）相配套的，给出了十三个上机实验指导，每个实验都给出了几道上机题目，每个实验题目都介绍了实验目的，主要采用的方法与技术和C语言实现程序通过实验使学生了解并学会如何运用数据结构只是去解决现实世界的某些实际问题，具备设计较复杂程序的初步能力本书的出发点是帮助学生学好算法与数据结构这门课程，所以在使用本书的过程中要注意以下几点：第一要与课程内容的学习同步，有利于进一步理解掌握各知识点和巩固课堂效果教学第二算法设计具有不唯一性，对实验题目本书只给出一种或几种算法，要在学习、理解、领会的基础上自己动手设计算法程序，这样才会取得良好的效果切忌照抄照搬，否则会影响学习效果第三要学会举一反三，触类旁通，实验内容知识点是有限的，但运用这些知识点、运用所介绍的方法和技术解决的实际问题却是无限的，重在掌握基本原理、基本方法和基本技术，并学会灵活运用第四要有C语言的基础。
本书算法是用C语言描述，所以读者应先了解C语言的基本内容由于时间仓促和作者水平有限，本书一定还存在着许多问题，敬请广大读者批评指正 作者 2005年8月63实验一 顺序表基本操作一、目的和要求1、熟悉C语言的上机环境，掌握C语言的基本结构2、会定义线性表的顺序存储结构3、熟悉对顺序表的一些基本操作和具体的函数定义 二、实验内容1、该程序的功能是对元素类型为整型的顺序表进行一些操作该程序包括顺序表结构类型的定义以及对顺序表操作的具体的函数定义和主函数 三、仪器、设备和材料1、 计算机若干台 四、实验步骤/* 定义ElemType为int类型 */typedef int ElemType;/*顺序表存储空间的总分配量*/#define MAXSIZE 100#define FALSE 0#define TRUE 1/* 顺序存储类型 */typedef struct{ElemType data[MAXSIZE]; /*存放线性表的数组*/ int length; /* length是顺序表的长度*/}SeqList;/* 初始化顺序表 */SeqList SeqListInit( ){SeqList L; L.length=0; return L; }/* 清空顺序表 */SeqList ListClear(SeqList L){L.length=0; return L;}/* 求顺序表长度 */int ListLength(SeqList L) {return(L.length);}/* 检查顺序表是否为空 */int ListEmpty(SeqList L){if(L.length) return(FALSE); else return(TRUE);}/*检查顺序表是否为满 */int ListFull(SeqList L){if(L.length==MAXSIZE) return(TRUE); else return(FALSE);}/* 遍历顺序表 */void ListTraverse(SeqList L){int i; if(L.length<=0) printf("顺序表为空\n"); else {printf("当前顺序表中的元素为:\n"); for(i=1;i<=L.length;i++) printf("%d ",L.data[i-1]); printf("\n"); }}/* 从顺序表中查找元素 */ElemType ListGet(SeqList L ,int i){ElemType e; e=L.data[i-1]; return(e);}/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */int ListLocate(SeqList L, ElemType x){int i=0; while(i
实验二 顺序表其它操作一、目的和要求1、进一步掌握在线性表的顺序存储结构上的一些其它操作 二、实验内容1、已知一个线性表，用另辟空间和利用原表两种方法把线性表逆置2、已知两个非递减有序的线性表LA和LB，将LA和LB合并成一个线性表LC，LC也非递减有序3、已知两个非递减有序的线性表LA和LB，长度分别为m和n，假设LA的空间足够大，利用原表LA，将LA和LB合并成一个仍然非递减有序的线性表要求时间复杂度为O(m+n)4、约瑟夫环问题：任给正整数N和K，按下述方法可以得到1,2, …,n的一个置换，将数字1,2,…,n环形排列，按顺时针方向自1开始报数，报到K时输出该位置上的数字，并使其出列然后从他在顺时针方向的下一个数字继续报数，如此下去，直到所有的数字全部出列为止例如N=10，K=3，则正确的出列顺序应为3，6，9，2，7，1，8，5，10，4 三、仪器、设备和材料1、 计算机若干台 四、实验步骤1、已知一个线性表，用另辟空间和利用原表两种方法把线性表逆置typedef int ElemType; /* 定义ElemType为int类型 *//*顺序表存储空间的总分配量*/#define MAXSIZE 100#define FALSE 0#define TRUE 1typedef struct /* 顺序存储类型 */{ElemType data[MAXSIZE]; /*存放线性表的数组*/ int length; /* length是顺序表的长度*/}SeqList;SeqList reverse(SeqList A) /*顺序表的就地逆置 */{ int i,j;ElemType temp; for(i=0,j=A.length-1;i SeqList MergeSeqList(SeqList La,SeqList Lb){int i,j,k;SeqList Lc; i=0;j=0;k=0; while(i 要求时间复杂度为O(m+n)SeqList MergeSeqList(SeqList La,SeqList Lb,int m,int n){int i,j,k; SeqList Lc; i=La.length-1;j=Lb.length-1;k=m+n-1;/*从后向前比较*/ while(i>=0&&j>=0)if(La.data[i]>=Lb.data[j]) /*大的向La的后面复制*/ {La.data[k]=La.data[i];i--;k--;} else {La.data[k]=Lb.data[j];j--;k--;} while(i>0) {Lc.data[k]=La.data[i];i--;k--;}/*La没有结束*/ while(j>0) {Lc.data[k]=Lb.data[j];j--;k--;} /*Lb没有结束*/ La.length=m+n; /*合并后的表长*/ return La;}void ListTraverse(SeqList L) /* 遍历顺序表 */{int i; if(L.length<=0) printf("顺序表为空\n"); else {printf("当前顺序表中的元素为:\n"); for(i=1;i<=L.length;i++) printf("%d ",L.data[i-1]); printf("\n"); }}SeqList create(){SeqList L;ElemType e; int i=0; scanf("%d",&e); while(e!=-1) { L.data[i]=e;i++;scanf("%d",&e);} L.length=i; return L;}main(){int n;SeqList La,Lb,Lc; printf("请输入非递减有序的La的元素,输入-1结束:\n"); La=create(); printf("请输入非递减有序的Lb的元素,输入-1结束:\n"); Lb=create(); Lc=MergeSeqList(La,Lb,La.length,Lb.length); printf("顺序表已经合并\n"); ListTraverse(Lc);}4、约瑟夫环问题#define MAXSIZE 100void Js(int n,int k){int i,j,s,A[MAXSIZE]; for(i=0;i 实验三 链表基本操作一、目的和要求1、定义单链表的结点类型 2、熟悉对单链表的一些基本操作和具体的函数定义3、通过单链表的定义掌握线性表的链式存储结构的特点 4、掌握循环链表和双链表的定义和构造方法二、实验内容1、该程序的功能是实现单链表的定义和操作该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数 三、仪器、设备和材料1、 计算机若干台 四、实验步骤 /* 定义ElemType为int类型 */typedef int ElemType;#define TRUE 1#define FALSE 0#define NULL 0#define flag -1typedef struct Lnode /* 单链表的结点类型 */{ElemType data; struct LNode *next;} LNode,*LinkedList;LinkedList LinkedListInit() /* 初始化单链表 */{LinkedList L; L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL; return L;}void LinkedListClear(LinkedList L) /* 清空单链表 */{L->next=NULL; printf("链表已经清空\n");}int LinkedListEmpty(LinkedList L) /* 检查单链表是否为空 */{if(L->next==NULL) return TRUE; else return FALSE;}void LinkedListTraverse(LinkedList L) /* 遍历单链表 */{LinkedList p; p=L->next; if(p==NULL) printf("单链表为空表\n"); else {printf("链表中的元素为:\n"); while(p!=NULL) {printf("%d ",p->data); p=p->next;} } printf("\n");}int LinkedListLength (LinkedList L){LinkedList p; int j; p=L->next; j=0; while(p!=NULL) { j++;p=p->next; } return j; }LinkedList LinkedListGet(LinkedList L,int i){LinkedList p;int j; p=L->next; j=1; while (p!=NULL && jnext; j++; } if (j==i) return p; else return NULL;}int LinkedListLocate ( LinkedList L, ElemType x){LinkedList p;int j; p=L->next; j=1; while ( p!=NULL && p->data != x) {p=p->next;j++;} if(p) return j; else return 0; }void LinkedListInsert(LinkedList L, int i, ElemType x){LinkedList p,s; int j; j=1;p=L; while(p&&j \n"); scanf("%d",&d); return(d);}main(){int quit=0;int i,locate;ElemType e; LinkedList L,p; while(!quit) switch(scan()) {case 1:L=LinkedListInit();printf("\n");break; case 2:LinkedListClear(L);printf("\n");break; case 3:printf("链表的长度为 %d\n",LinkedListLength(L));break; case 4:if(LinkedListEmpty(L))printf("链表为空\n");else printf("链表非空\n");break; case 5:LinkedListTraverse(L); break; case 6:printf("请输入待查询元素在链表中的位置:"); scanf("%d",&i); p=LinkedListGet(L,i); if(p) printf("链表中第%d个元素的值为:%d\n",i,p->data); else printf("查询位置不正确\n"); break; case 7:printf("请输入待查询元素的值:"); scanf("%d",&e); locate=LinkedListLocate(L,e); if(locate) printf("%d在链表中的位置是:%d\n",e,locate); else printf("链表中没有值为%d的元素\n",e); break; case 8:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n"); scanf("%d%d",&i,&e); LinkedListInsert(L,i,e); break; case 9:if(LinkedListLength(L)==0) printf("链表已经为空,不能删除\n"); else {printf("请输入待删除元素的位置:\n"); scanf("%d",&i); LinkedListDel(L,i);} break; case 10:L=LinkedListCreat(); printf("\n");break; default:quit=1;}}实验四 链表其它操作一、目的和要求1、熟悉对单链表的一些其它操作。 2、掌握循环链表和双链表的一些操作，理解与单链表操作的不同二、实验内容1、设单链表L是一个非递减有序表，写一算法将x插入其中后仍保持L的有序性2、利用原空间，将两个单链表合并成一个单链表3、已知两个非递减有序的单链表la和lb，将la和lb合并成一个线性表lc，lc也非递减有序4、已知一个单链表，利用原表把单链表逆置5、在计算机上先输入一串正整数的序列请编写一个程序，首先用链表存储该序列然后执行删除操作，即先从链表中找出最小的结点，删除它然后再在剩余的链表中，找出最小的结点，再删除之直至表空为止6、利用单循环链表作为存储结构，实现实验二中的约瑟夫环问题7、在双向链表上实现线性表运算8、设有一个双链表，每个结点中除有prior，next及data〔可设为正整数〕三个域之外，还有一个专门记录访问该结点次数的数据域freq，其值在初始化时为零每当在链表中进行一次Search〔l，key〕时，则数据域data之值等于key的结点，其freq域之值将加一并使该双链表中结点按freq之值的递减顺序排列，freq值越大的结点越靠近表头请编写符合上述要求的Search〔l，key〕程序 三、仪器、设备和材料1、 计算机若干台 四、实验步骤1、将x插入L后仍保持L的有序性。 include "stdio.h"#define NULL 0typedef struct LNode{int data; struct LNode *next;} LNode,*LinkedList;LinkedList LinkedListCreat( ){ LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL; r=L; printf("请输入递增的有序序列,输入-1结束\n"); scanf("%d",&x); while (x!=flag) {p=(LinkedList)malloc(sizeof(LNode)); p->data=x; r->next=p; r=p; scanf("%d",&x); } r->next=NULL; return L;}void InsertList(LinkedList L,int x){LinkedList p,q,s; q=L;p=q->next; while(p!=NULL&&p->data include "stdio.h"#define NULL 0typedef struct LNode{int data; struct LNode *next;} LNode,*LinkedList;LinkedList LinkedListCreat( ){ LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL; r=L; printf("请输入链表中的结点,以-1结束\n"); scanf("%d",&x); while (x!=flag) {p=(LinkedList)malloc(sizeof(LNode)); p->data=x; r->next=p; r=p; scanf("%d",&x); } r->next=NULL; return L;}LinkedList ListConcat(LinkedList La,LinkedList Lb)/*把链表Lb接在La后面*/{ LinkedList Lc,p; Lc=La;p=La; while(p->next) p=p->next; p->next=Lb->next; return Lc;}void print(LinkedList L) /*输出链表中的结点*/{LinkedList p; p=L->next; while(p!=NULL) {printf("%d ",p->data); p=p->next; }}main( ){LinkedList La,Lb; La=LinkedListCreat( ); Lb= LinkedListCreat( ); La=ListConcat(La,Lb); print(La);}3、两个非递减有序的单链表la和lb，合并成一个非递减有序线性表lc。 define NULL 0typedef struct LNode{int data; struct LNode *next;} LNode,*LinkedList;LinkedList LinkedListCreat(){ LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL; r=L; printf("请输入非递减有序表,以-1结束\n"); scanf("%d",&x); while (x!=flag) {p=(LinkedList)malloc(sizeof(LNode)); p->data=x; r->next=p; r=p; scanf("%d",&x); } r->next=NULL; return L;}LinkedList un(LinkedList La,LinkedList Lb) /*合并链表*/{LinkedList p,q,r; p=La->next; q=Lb->next; r=La; while((p!=NULL)&&(q!=NULL)) if(p->data<=q->data) {r->next=p; r=p;p=p->next;} else {r->next=q; r=q;q=q->next;} if(p!=NULL) r->next=p; if(q!=NULL) r->next=q; return La;}void print(LinkedList L) /*输出链表中的结点*/{LinkedList p; p=L->next; while(p!=NULL) {printf("%d ",p->data); p=p->next; }}main( ){LinkedList La,Lb,Lc; La=LinkedListCreat( ); Lb= LinkedListCreat( ); Lc=un(La,Lb); print(Lc);}4、把单链表逆置（见课后习题）。 5、在计算机上先输入一串正整数的序列首先用链表存储该序列然后从链表中找出最小的结点，删除它直至表空为止6、利用单循环链表作为存储结构，实现实验二中的约瑟夫环问题7、在双向链表上实现线性表的下列运算：a) 建立 DLinkedList creat()b) 插入void DlistInsert(DLinkedList L,int x,int i)c)删除void DlistDelete(DLinkedList L,int i)8、设有一个双链表，每个结点中除有prior，next及data〔可设为正整数〕三个域之外，还有一个专门记录访问该结点次数的数据域freq，其值在初始化时为零每当在链表中进行一次Search〔l，key〕时，则数据域data之值等于key的结点，其freq域之值将加一并使该双链表中结点按freq之值的递减顺序排列，freq值越大的结点越靠近表头define NULL 0typedef struct DLNode{int data,freq; struct DLNode *prior,*next;}DLNode,*DLinkedList;DLinkedList creat(){int num; DLinkedList head,p1,p2; head=(DLinkedList)malloc(sizeof(DLNode));head->next=NULL; /*表头为空 */ p2=head;printf("输入元素,以-1结束:");scanf("%d",&num);while(num!=-1) {p1=(DLinkedList)malloc(sizeof(DLNode)); p1->data=num; p1->freq=0; p2->next=p1; p1->prior=p2; p2=p1; scanf("%d",&num); } p2->next=NULL;return head;}void search(DLinkedList head, int key){DLinkedList p1,p2,temp; p2=head; p1=p2->next; while(p1) {if(p1->data==key) { p1->freq++; break;} else {p2=p1; p1=p2->next;} } if(p1==NULL) printf("没有发现.\n"); else {if(p1->next==NULL) {p2->next=p1->next; temp=p1;} else {p2->next=p1->next; p1->next->prior=p2;temp=p1;}for(p2=head,p1=p2->next; p1 && p1->freq > temp->freq;p2=p1,p1=p2->next); /*插入*/ if(p1==NULL) {p2->next=temp; temp->prior=p2; temp->next=NULL; } else {p2->next=temp; temp->prior=p2; temp->next=p1; p1->prior=temp;}}}void print(DLinkedList head){DLinkedList p; p=head->next; do{printf("元素=%d " , p->data); printf("频度=%d\n", p->freq); p=p->next; }while(p);}int main(){DLinkedList head; int key; head=creat(); printf("现在元素和其访问的频度(按递减的顺序输出)为:\n" ); print(head); printf("请输入要访问的元素,以-1结束:"); scanf("%d",&key); while(key!=-1) {search(head,key); print(head); printf( "请输入要访问的元素,以-1结束:"); scanf("%d",&key); }}实验五 表达式求值一、目的和要求1、会定义顺序栈和链栈的结点类型。 2、掌握栈的插入和删除结点在操作上的特点3、熟悉对栈的一些基本操作和具体的函数定义 二、实验内容1、实现顺序栈的定义和操作该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数2、用顺序栈实现算术表达式求值3、用链栈实现算术表达式求值 三、仪器、设备和材料1、 计算机若干台 四、实验步骤1、该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数typedef int DataType; /* 定义DataType为int类型 */ /* 栈的结点类型 */#define MAXSIZE 1024 typedef struct{。
