《数据结构》实验指导书(C语言版)(浦江学院).doc

实验1: 顺序表的操作实验一、实验名称和性质所属课程数据结构实验名称顺序表的操作实验学时4实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。三、实验内容1建立顺序表。2在顺序表上实现插入、删除和查找操作（验证性内容）。3删除有序顺序表中的重复元素（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC+6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。2. 实验相关原理线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#define MAXLEN 30 /*线性表的最大长度*/typedef struct Elemtype elemMAXLEN; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/ int length; /*顺序表的长度，即元素个数*/ Sqlist; /*顺序表的类型*/【核心算法提示】（1）顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1in+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。（2）顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1in，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。（3）顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。【核心算法描述】status Sqlist_insert(Sqlist &L,int i,Elemtype x) /*在顺序表L中第i个元素前插入新元素x*/ if (iL.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length=MAXLEN) return OVERFLOW; /*顺序表L中已放满元素，再做插入操作则溢出*/ for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj;/*将第i个元素及后续元素位置向后移一位*/ L.elemi-1=x; /*在第i个元素位置处插入新元素x*/ L.length+; /*顺序表L的长度加1*/ return OK; status Sqlist_delete(Sqlist &L,int i,Elemtype &e) /*在顺序表L中删除第i个元素*/ if (iL.length) return ERROR; /*删除位置不正确则出错*/for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; /*将第i+1个元素及后继元素位置向前移一位*/ L.length-; /*顺序表L的长度减1*/ return OK； int Sqlist_search(Sqlist L,Elemtype x) /* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/ for (i=1;i=L.length&L.elemi-1!=x;i+);/*从第一个元素开始依次将每个元素值与给定值x比较*/ if (i=L.length) return i; else return o;3源程序代码参考 #include#define MAXLEN 50typedef structint elemMAXLEN;int length;Sqlist;Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/int j; if(iL.length+1) printf(ERROR!); else if(L.length=MAXLEN) printf(OVERFLOW!); else for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; L.elemi-1=x; L.length+; return L;Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/int j; if(iL.length) printf(ERROR!); else for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj;L.length-; return L;int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ int i; for(i=1;i=L.length&L.elemi-1!=x;i+); if (i=L.length) return i; else return 0;void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ int j; for(j=0;j=L.length-1;j+) printf(%4d,L.elemj); printf(n); void main() /*主函数 */ Sqlist L; int i,x,j; printf(nplease input the length:);/*请求输入顺序表中元素个数*/ scanf(%d,&L.length); printf(please input the Value:n);/*请求输入顺序表中各个元素*/ for(j=0;j=L.length-1;j+)scanf(%d,&L.elemj); printf(please input the insert position:); /*请求输入插入操作位置*/ scanf(%d,&i); printf(please input the insert node:);/*请求输入需要插入的新元素*/ scanf(%d,&x); L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(please input the delete position:);/*请求输入删除操作位置*/ scanf(%d,&i); L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(please input the search node:); scanf(%d,&x); if (Sqlist_search(L,x) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查找不成功*/ printf(search is success and %d is %d positionn,x,Sqlist_search(L,x); else printf(search is unsuccessn); 4运行结果参考如图1-1所示 图1-1 验证性实验运行结果七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。（1）实验要求 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。（2）核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。（3）非核心源代码提示#include #define maxsize 100typedef struct nodeint datamaxsize;int last;seqList;int main()int i=0,j,k;seqList L;scanf(%d,&L.last);for (i=0;iL.last;i+)scanf(%d,&L.datai);/核心算法代码for (i=0;inext=NULL;/*头结点的指针域初始为空*/ scanf(%d,&node);while(node!=0) p=(Linklist)malloc(sizeof(LNODE);/*为一个新结点的分配空间*/ p-data=node; /*为新结点数据域赋值*/ p-next=L-next;/*新结点指针域指向开始结点*/ L-next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/scanf(%d,&node); void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插法建立一个带头结点的单链表的函数*/ L=(Linklist)malloc(sizeof(LNODE);/*为头结点分配空间*/ L-next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/scanf(%d,&node);while(node!=0) p=(Linklist)malloc(sizeof(LNODE);/*为一个新结点分配空间*/ p-data=node; /*新结点数据域赋值*/ p-next=NULL; /*新结点指针域为空*/ r-next=p;/*尾结点指针域指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/scanf(%d,&node); status list_search(Linklist L, int i;Elemtype &e) /*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/ p=L-next; /*使指针p指向第1个元素结点*/j=1; /*计数器赋初值为1*/while (p& jnext; j+;if (!p& ji) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/e=p-data; /*如果第i个元素存在，则将该元素值赋给e*/return OK; status list_insert(Linklist &L,int i;Elemtype x) /*在带头结点的单链表L中第i个位置之前插入新元素x*/ p=L;j=0; while(p!=NULL&jnext; +j; if(p=NULL|ji-1) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE); /*分配一个新结点的空间*/ s-data=x; /*为新结点数据域赋值*/ /*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/ s-next=p-next; /*新结点指针域指向p的后继结点*/ p-next=s; /*新结点成为p的后继结点*/ return OK;status list_delete(Linklist &L,int i,Elemtype &x)/*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/ p=L;j=0; while(p-next!=NULL&jnext; +j; if (p-next=NULL|ji-1) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p-next; /* q指向p的后继结点*/ p-next=q-next; /*q的后继结点成为p的后继结点*/ x=q-data; /*用x返回第i个位置的元素*/free(q); /*释放q所指的被删结点的空间*/return OK;3源程序代码参考#include#includetypedef struct Lnode int data; struct Lnode *next; LNODE,*Linklist;Linklist creat(Linklist L) /*单链表建立函数（尾插法）*/int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE); L-next=NULL; printf(nplease input the node(end with 0):n); /*请求输入线性表中各个元素，以0结束*/ scanf(%d,&node); while(node!=0) p=(Linklist)malloc(sizeof(LNODE); if (!p) exit(); p-data=node; p-next=L-next; L-next=p; scanf(%d,&node); return L;Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ int j;Linklist p,s; p=L; j=0; while (p!=NULL&jnext; +j; if (p=NULL|ji-1) printf(n ERROR position!n); else s=(Linklist)malloc(sizeof(LNODE); s-data=x; s-next=p-next; p-next=s; return L;Linklist delete(Linklist L,int i) /*单链表删除函数*/ int j,x; Linklist p,q; p=L; j=0; while(p-next!=NULL&jnext; +j; if(p-next=NULL|ji-1) printf(n ERROE position!n); else q=p-next; p-next=q-next; x=q-data; printf(the delete data is:%dn,x); free(q); return L;int search(Linklist L, int i) /*单链上的查找函数*/ Linklist p; int j; p=L-next; j=1; while (p& jnext; j+; if (!p& ji) return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else return(p-data); /*否则函数返回第i个元素的值*/void display(Linklist L) /*单链表元素输出函数*/ Linklist p; p=L-next; while(p!=NULL) printf(%4d,p-data); p=p-next; printf(n);void main() /*主函数*/ Linklist L=NULL; int i,x; L=creat(L);/*调用单链表建立函数*/ printf(the Linklist is:n); display(L); /*调用单链表元素输出(遍历)函数*/ printf(please input the position you want to insert:);/*请求输入插入操作位置*/ scanf(%d,&i); printf(please input the node you want to insert:);/*请求输入需要插入的元素*/ scanf(%d,&x); L=insert(L,i,x);/*调用单链表插入函数*/ printf(the Linklist after inserted is:n); display(L);/*调用单链表元素输出(遍历)函数*/ printf(please input the node position you want to delete:); /*请求输入删除操作位置*/ scanf(%d,&i); L=delete(L,i); /*调用单链表删除函数*/ printf(the Linklist after deleted is:n); display(L); /*调用单链表元素输出(遍历)函数*/ printf(please input the position you want to search:); /*请求输入待查找元素的位置*/ scanf(%d,&i); x=search(L,i); /*调用单链表查找函数*/ if(x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(the %dth elem is %dn,i,x); else printf(the %dth elem is not exsitn);4运行结果参考如图2-1所示 图2-1 验证性实验运行结果七、设计性实验1编写一个程序，计算出带有头结点的单向链表中各结点数据域之和（1）实验要求 输出此单链表中的各个数据元素值； 计算出此单向链表中各结点数据域之和，并输出。2编程实现在双向循环链表上的插入、删除和查找操作（1）实验要求 输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。 在双向循环链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。 删除双向循环链表中第i个元素，并输出删除后的链表中各元素值。 在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。（2）核心算法提示双向循环链表采用的存储结构描述如下： typedef struct DULNODE Elemtype data; /*数据域*/ struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/ DULNODE,*DuLinklist; typedef int Elemtype;不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点： 凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。 单链表操作算法中的判断条件：p= =NULL 或p!=NULL，在循环链表的操作算法中则需改为：p!= L，其中L为链表的头指针。（3）核心算法描述void DuList_creat (DuLinklist &L,int n) /*输入n个整数（其中n为表长），将这些整数作为data域并用尾插法建立一个带头结点的双向循环链表的函数*/ L=( DuLinklist)malloc(sizeof(DULNODE);/*为头结点分配空间*/ L-next=L-prior=L;/*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/ r=L; /*尾指针初始指向头结点*/for (i=0;idata); /*从键盘输入值，并保存在新结点数据域中*/ p-next=r-next; /*新结点后继指针指向尾结点r的后继结点*/ p-prior=r; /*新结点的前驱指针指向尾结点r*/ r-next=p; /*尾结点的后继指针指向新结点*/ r=p; /*尾指针指向新结点，即新结点成为尾结点*/L-prior=r; /*使尾结点成为头结点的前驱结点*/status DuList_search(DuLinklist L, int i;Elemtype &e) /*在带头结点的双向循环链表L中查找第i个元素，如果查找成功则用e返回其值*/ p=L-next; /*使指针p指向第1个元素结点*/j=1; /*计数器赋初值为1*/ while (p!=L & jnext; j+;if (j!=i) return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/e=p-data; /*如果第i个元素存在，则将该元素值赋给e*/return OK; status DuList_insert(DuLinklist &L,int i;Elemtype x) /*在带头结点的双向循环链表L中第i个位置之前插入新元素x*/ p=L-next; j=1;while(p!=L &jnext; +j; if(j!=i) return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(DuLinklist)malloc(sizeof(DULNODE); /*为一个新结点s分配空间*/ s-data=x; /*为新结点数据域赋值*/ /*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s-next=p;p-prior-next=s; s-prior=p-prior;p-prior=s; return OK;status DuList_delete(DuLinklist &L,int i,Elemtype &x)/*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ p=L-next;j=1; while(p!=L&jnext; +j; if (j!=i) return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p; /*记下被删结点*/ p-prior-next=p-next; /*修改链使得p结点从链中脱离*/ p-next-prior=p-prior; x=q-data; printf(the delete data is:%dn,x); free(q); /释放被删结点空间return OK;提示: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。实验3：栈的操作实验一、实验名称和性质所属课程数据结构实验名称栈的操作实验学时2实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握栈的存储结构的表示和实现方法。2掌握栈的入栈和出栈等基本操作算法实现。3了解栈在解决实际问题中的简单应用。三、实验内容1建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。2建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC+6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序栈、链栈的基本操作算法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。（2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。2. 实验相关原理栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：#define MAXSIZE 100; /*顺序栈的最大长度*/typedef struct Selemtype base MAXSIZE; /*存储栈中数据元素的数组*/ int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ Sqstack;【核心算法提示】 （1）顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。（2）顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1，再将top所指示的栈顶元素用e返回其值，并使函数返回OK。【核心算法描述】status Push(Sqstack &S,Selemtype e)/*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ if (S.top =MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR; S.baseS.top+=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; status Pop(Sqstack &S,Selemtype &e)/*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ if (S.top=0) /*如果栈空，则函数返回ERROR*/ Return ERROR; e=S.base-S.top;/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; 3源程序代码参考#define MAXSIZE 100typedef struct int baseMAXSIZE; int top; /*top指示存储栈顶元素的下一存储单元*/ Sqstack; /*顺序栈的类型定义*/Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ if (S.top=MAXSIZE) printf(Stack is Overflown);else S.baseS.top+=e; return S; Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ if (S.top=0) printf(Stack is Emptyn);else *e=S.base-S.top; return S; void Stack_display(Sqstack S) /*顺序栈的输出函数*/ int i; for(i=0; iS.top;i+) /*依次输出栈中各元素的值，栈顶元素在表的尾部*/ printf(%4d, S.basei); printf(n); main() Sqstack S; int i,j,n,x,e; printf(please input the length:);/*请求输入顺序栈中元素个数*/ scanf(%d,&n); printf(please input the Value:n );/*请求输入顺序栈中各个元素值*/ for(i=0;idata=e; /*新结点的数据域赋值*/ p-next=top; /*修改链使新结点插入到链表的头部,并成为新的栈顶元素*/ top=p; return OK; status Pop(LinkStack &top,int &e) /*将链栈top中的栈顶元素从栈中删除，并用e返回其值*/ LinkStack q; if (!top) /*如果栈空，则函数返回ERROR*/ return ERROR; e=top-data; /*将被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/top=q-next; /*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/ free(q); /*释放被删结点的存储空间*/ return OK;实验4: 队列的操作实验一、实验名称和性质所属课程数据结构实验名称队列的操作实验学时2实验性质验证 综合 设计必做/选做必做 选做二、实验目的1掌握队列存储结构的表示和实现方法。2掌握队列的入队和出队等基本操作的算法实现。三、实验内容1建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作（验证性内容）。2建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC+6.0五、知识准备 前期要求熟练掌握了C语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。六、验证性实验1实验要求编程实现如下功能：（1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。（2）将数据元素e入队，并输出入队后的队列中各元素值。（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。2. 实验相关原理：队列是一种插入操作限制在表尾，而删除操作限