《数据结构》实验指导书（C语言版）（浦江学院）南京廖华答案网

《数据结构》实验指导书（C语言版）（浦江学院）下载本文

文章发布时间 : 2024/10/20 5:47:08星期日

实验1: 顺序表的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做二、实验目的

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 elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/

数据结构顺序表的操作 4 √验证 □综合 √设计 √必做 □选做 int length; /*顺序表的长度，即元素个数*/

}Sqlist; /*顺序表的类型*/ 【核心算法提示】

（1）顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

（2）顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。

（3）顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。【核心算法描述】

status Sqlist_insert(Sqlist &L,int i,Elemtype x)

/*在顺序表L中第i个元素前插入新元素x*/

{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW;

/*顺序表L中已放满元素，再做插入操作则溢出*/

for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; }

status Sqlist_delete(Sqlist &L,int i,Elemtype &e)

/*在顺序表L中删除第i个元素*/

{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK；

}

int Sqlist_search(Sqlist L,Elemtype x)

/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/

{ for (i=1;i<=L.length&&L.elem[i-1]!=x;i++);

/*从第一个元素开始依次将每个元素值与给定值x比较*/

if (i<=L.length) return i; else return o; }

3．源程序代码参考 #include

#define MAXLEN 50

typedef struct{int elem[MAXLEN]; int length;}Sqlist;

Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ {int j;

if(i<1||i>L.length+1) printf(\ else if(L.length>=MAXLEN) printf(\

else {for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

L.elem[i-1]=x; L.length++; } return L; }

Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ {int j;

if(i<1||i>L.length) printf(\

else {for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j]; L.length--; } return L; }

int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ { int i;

for(i=1;i<=L.length&&L.elem[i-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(\ printf(\}

void main() /*主函数 */ { Sqlist L; int i,x,j;

printf(\请求输入顺序表中元素个数*/ scanf(\

printf(\请求输入顺序表中各个元素*/ for(j=0;j<=L.length-1;j++)

scanf(\

printf(\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的新元素*/ scanf(\

L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(\ scanf(\

if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，

否则显示查找不成功*/

printf(\ else

printf(\ }

is success and %d is %d

position\\n\

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 100 typedef struct node {

int data[maxsize]; int last;

}seqList; int main() {

int i=0,j,k; seqList L;

scanf(\for (i=0;i

scanf(\

//核心算法代码

for (i=0;i

printf(\ return 0;

}

实验2: 链表的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做二、实验目的

1．掌握线性表的链式存储结构的表示和实现方法。 2．掌握链表基本操作的算法实现。三、实验内容

1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。

2．建立带有头结点的单向链表，并计算出该单向链表中各结点数据域之和（设计性内容）。 3．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的VC++6.0 使用的软件名称、版本号：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。

（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。

（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。 2. 实验相关原理

线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含一个指针的链表，则称单链表。单链表的存储结构描述如下：

数据结构链表的操作 4 √验证 □综合 √设计 √必做 □选做 Typedef struct Lnode {

Elemtype data;/*数据域*/ Struct Lnode *next;/*指针域*/

}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/

【核心算法提示】

（1）链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。

（2）链表查找操作的基本步骤：因链表是一种“顺序存取”的结构，则要在带头结点的链表中查找到第 i个元素，必须从头结点开始沿着后继指针依次“点数”，直到点到第i个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。

（3）链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。

（4）链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。【核心算法描述】

void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为

data域并用头插法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf(\

while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/

L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/

scanf(\}

}

void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data

域并用尾插法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/

scanf(\while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

scanf(\ } }

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&& j>i)

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&&j

即L中的第i-1个位置*/

{ p=p->next;

++j;

}

if(p==NULL||j>i-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||j>i-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 #include typedef 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(\请求输入线性表中各个元素，以0结束*/ scanf(\ while(node!=0)

{p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf(\ } 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||j>i-1)

printf(\ 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||j>i-1)

printf(\ else

{ q=p->next; p->next=q->next; x=q->data;

printf(\ 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&& j>i)

return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else

return(p->data); /*否则函数返回第i个元素的值*/ }

void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL)

{ printf(\ p=p->next; }

printf(\}

void main() /*主函数*/ {Linklist L=NULL; int i,x; L=creat(L);/*调用单链表建立函数*/ printf(\

display(L); /*调用单链表元素输出(遍历)函数*/

printf(\请求输入插入操作位置*/

scanf(\

printf(\请求输入需要插入的元素*/

scanf(\

L=insert(L,i,x);/*调用单链表插入函数*/ printf(\ display(L);/*调用单链表元素输出(遍历)函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=delete(L,i); /*调用单链表删除函数*/

printf(\ display(L); /*调用单链表元素输出(遍历)函数*/

printf(\请求输入待查找元素的位置*/ scanf(\

x=search(L,i); /*调用单链表查找函数*/

if(x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(\ else

printf(\}

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;i

{ p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf(\从键盘输入值，并保存在新结点数据域中*/ 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 &&j

i个结点*/

{ p=p->next;

++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(\

free(q); //释放被删结点空间 return OK; }

提示: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。

实验3：栈的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做二、实验目的

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后移一个存储

数据结构栈的操作 2 √验证 □综合 √设计 √必做 □选做单元位置，即将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.base[S.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 100 typedef struct

{ int base[MAXSIZE];

int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/

Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE)

printf(\

else

S.base[S.top++]=e;

return S; }

Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0)

printf(\

else

*e=S.base[--S.top];

return S; }

void Stack_display(Sqstack S) /*顺序栈的输出函数*/ { int i;

for(i=0; i

printf(\请求输入顺序栈中元素个数*/ scanf(\

printf(\请求输入顺序栈中各个元素值*/ for(i=0;i

scanf(\ S.top=n;

printf(\ Stack_display(S);

printf(\请求输入需要入栈的新元素*/ scanf(\ S=Push(S,x);

printf(\提示输出入栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ S=Pop(S,&e);

printf(\输出出栈元素的值*/

printf(\提示输出出栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ }

4．运行结果参考如图3-1所示

图3-1 验证性实验运行结果

七、设计性实验

1．编程实现链栈的入栈和出栈操作

（1）实验要求

① 根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。

② 将数据元素x入栈，并输出入栈后的链栈中各元素值。

③ 将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。（2）核心算法提示

采用链式存储结构的栈称为链栈，链栈的存储结构描述如下： typedef struct Snode

{ Selemtype data;/*数据域*/ struct Snode *next;/*指针域*/ }SNODE,* LinkStack;/*其中SNODE为链栈中的结点类型名, LinkStack为指向结点的指针类型名*/

如果栈中元素序列为{a1,a2，?,an}，则链栈的存储结构如下图3-2所示：

图3-2 链栈的存储结构示意图

top an an-1 an-2 … a1 ^

从图3-2可看出，栈的链式存储结构与单链表的存储结构相同，所有在链栈上进行入栈和出栈操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：

① 链栈中无需加头结点。

② 链栈中的指针是指向栈中元素序列的前驱结点。 ③ 链栈中的入栈和出栈操作都是在链表的表头进行。（3）核心算法描述

status Push(LinkStack &top,int e)

/*将数据元素e压入到链栈top中，使其成为新的栈项元素*/ { LinkStack p;

p=(LinkStack)malloc(sizeof(SNODE)); /*生成一个新的结点*/ if (!p) /*如果分配空间失败，则函数返回\ return OVERFLOW;

p->data=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: 队列的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做二、实验目的

1．掌握队列存储结构的表示和实现方法。 2．掌握队列的入队和出队等基本操作的算法实现。三、实验内容

1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作（验证性内容）。 2．建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的VC++6.0 使用的软件名称、版本号：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。

六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。

（2）将数据元素e入队，并输出入队后的队列中各元素值。

（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。 2. 实验相关原理：

队列是一种插入操作限制在表尾，而删除操作限制在表头进行的特殊线性表，它的操作具有“先进先出”的特性。采用顺序存储结构的队列称为顺序队列，顺序队列的存储结构描述如下：

#define MAXQSIZE 100 /*顺序循环队列的最大长度*/ typedef struct

{ Qelemtype base[MAXQSIZE]; /*存放队列元素的数组空间*/ int front; /*头指针，若队列不空，则指向队列头元素*/

int rear; /*尾指针，若队列不空，则指向队列尾元素的下一个存储单元*/ }Sqqueue;

数据结构队列的操作 2 √验证 □综合 √设计 √必做 □选做【核心算法提示】

（1）顺序循环队列入队操作的基本步骤：首先判断队列是否为满，如果队列满，则函数返回ERROR，否则将待入队的数据元素e存放在尾指针rear所指示的存储单元中，再使尾指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。

（2）顺序循环队列出队操作的基本步骤：首先判断队列是否为空，如果队列空，则函数返回ERROR，否则将头指针所指示的队首元素用e返回其值，再使头指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。【核心算法描述】

status enqueue(Sqqueue &Q,Qelemtype e)

/*在循环队列Q中，插入新元素使其成为队尾元素*/ { if ((Q.rear+1)%MAXQSIZE==Q.front)

return ERROR; /*若队列满，插入操作不能进行，函数返回ERROR*/

Q.base[Q.rear]=e; /*新元素成为队尾元素*/

Q.rear=(Q.rear+1)%MAXQSIZE;/*利用模运算,“尾指针”加1,使尾指针后移一个位置*/

return OK; }

status dequeue(Sqqueue &Q，Qelemtype &e) /*在循环队列Q中，删除Q的队首元素*/ { if (Q.front==Q.rear)

return ERROR;/*若队列空，删除操作不能进行，函数返回ERROR*/

e=Q.base[Q.front];/*将队首元素用e保存其值*/

Q.front=(Q.front+1)%MAXQSIZE; /*利用模运算,“头指针”加1，使头指针后移一个位置*/

return OK; }

3．源程序代码参考

#define MAXQSIZE 100 typedef struct { int base[MAXQSIZE]; int front; int rear; } Sqqueue;

Sqqueue enqueue(Sqqueue Q,int e)/*队列的入队函数*/ { if ((Q.rear+1)%MAXQSIZE==Q.front) printf(\ else

{Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE; } return Q; }

Sqqueue dequeue(Sqqueue Q,int *e)/*队列的出队函数*/ { int x;

if (Q.front==Q.rear) printf(\ else

{ *e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } return Q; }

void display(Sqqueue Q)/*队列元素输出函数*/ { int k,m;

k=Q.front;m=Q.rear; while(k!=m)

{ printf(\ k=(k+1)%MAXQSIZE;} printf(\ }

void main()/*主函数*/ { Sqqueue Q; int i,n,x,y,e;

Q.rear=Q.front=0; /*初始化顺序队列，使其成为空队列*/ printf(\请求输入队列的长度*/ scanf(\

printf(\请求输入队列中各个元素*/ for(i=1;i<=n;i++) {scanf(\

Q=enqueue(Q,x);}/*调用队列插入函数*/ printf(\

display(Q);/*调用队列元素输出函数*/

printf(\请求输入需要插入的元素*/ scanf(\

Q=enqueue(Q,y);/*调用队列插入函数*/

printf(\提示显示执行入队操作后的队列*/

display(Q);/*调用队列元素输出函数*/ Q=dequeue(Q,&e);/*调用队列删除函数*/

printf(\显示被删的队首元素值*/

printf(\提示显示执行出队操作后的队列*/ display(Q);/*调用队列元素输出函数*/ }

4．运行结果参考如图4-1所示

图4-1 验证性实验运行结果

七、设计性实验

1．编程实现对循环链队列的入队和出队操作。

（1）实验要求

① 根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。

② 将数据元素e入队，并输出入队后的队列中各元素值。

③ 将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。（2）核心算法分析

采用链式存储结构的队列称为链队列，链队列的存储结构描述如下： typedef struct CQNode {

Qelemtype data;/*数据域*/ struct CQNode *next;/*指针域*/ }CQNode,*CQLink;

如果队列中元素序列为{a1,a2，?,an}，则带头结点的循环链队列的存储结构如下图4-2

rear 所示：

图4-2 循环链队列的存储结构示意图

a1 a2 … an

从图4-2可看出，队列的循环链式存储结构与循环单链表的存储结构相同，所有在循环

链队列上进行入队和出队操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：

① 此循环链队列是通过一个指向队尾结点的指针rear来标识的，则rear指向队尾元素结点，rear->next指向队头结点，而rear->nexnt->next指向队首元素结点。

② 队列的入队操作是在链表的表尾（队尾）进行，而出队操作则在链表的表头（队首）进行。

③ 在出队操作时要注意：如果当链表中只有一个结点，即被删结点既是队首结点，又是队尾结点时，要进行尾指针的修改。

（3）核心算法描述

void InitCiQueue(CQLink &rear)

/*初始化用带头结点的循环链表表示的队列rear,其中rear指向队尾元素*/ { rear=( CQNode *)malloc(sizeof(CQNode)); /*产生一个头结点，并使队尾指针指向它*/

rear->next=rear; /*形成循环*/ } 入队操作：

status EnCiQueue(CQLink &rear, int x)

/*把元素x插入到用队尾指针rear表示的带头结点的循环链队列rear中*/ { p=( CQNode *)malloc(sizeof(CQNode)); if (!p)

return (OVERFLOW);

p->data=x; /*产生一个新结点p*/

p->next=rear->next; /*直接把p插入到rear的后面*/ rear->next=p;

rear=p; /*修改尾指针,使p成为新的队尾结点*/ return OK; }

status DeCiQueue(CQLink &rear, int &x)

/*从用队尾指针rear表示的带头结点的循环链队列中删除一个队首元素，并用x返回其数据域的值。*/

{ if(rear==rear->next) return ERROR; /*如果队列为空，则函数返回ERROR*/ p=rear->next->next;/*用p指针指向队首结点,也是待删结点*/ x=p->data; /* 用x保存待删队首结点的数据域的值*/

rear->next->next=p->next;/*修改链，使p的后继成为新的队首结点*/

if (rear==p) /*如果待删的结点p是队尾结点,则要使队尾指针指向原来队尾结点的

后继(头结点)*/

rear=rear->next;

free(p); /*释放待删结点的空间*/

return OK; }

实验5: 二叉树的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做二、实验目的

1．理解二叉树的类型定义与性质。

2．掌握二叉树的二叉链表存储结构的表示和实现方法。 3．掌握二叉树遍历操作的算法实现。 4．熟悉二叉树遍历操作的应用。三、实验内容

1．建立二叉树的二叉链表存储结构。

2．实现二叉树的先序、中序和后序三种遍历操作（验证性内容）。

3．应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作（设计性内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的VC++6.0 使用的软件名称、版本号：五、知识准备

前期要求掌握二叉树的二叉链表的存储结构表示和三种遍历操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）假设二叉树的结点值是字符，根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。

（2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。

（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种遍历操作。 2. 实验相关原理：

二叉树的形式定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

二叉树的二叉链表存储结构描述为： typedef char Telemtype; typedef struct Bitnode

{ Telemtype data;/*数据域*/

数据结构二叉树的操作 4 √验证 □综合 √设计 √必做 □选做 struct Bitnode *lchild, *rchild;

/*指针域,分别指向该结点的左、右孩子*/

}Bitnode,*Bitree;

【核心算法提示】

二叉树的遍历是指按某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。其中先序、中序和后序遍历操作步骤分别为：

? 先序遍历：若二叉树为空树，则空操作；否则先访问根结点，再先序遍历左子树，

最后先序遍历右子树。

? 先序遍历：若二叉树为空树，则空操作；否则先中序遍历左子树，再访问根结点，

最后中序遍历右子树。

? 先序遍历：若二叉树为空树，则空操作；否则先后序遍历左子树，再后序遍历右子

树，最后访问根结点。

注意：这里的“访问”的含义可以很广，几乎可以含盖对结点的任何一种操作。如：输出结点的信息、判断结点是否为叶子结点等等。

由于二叉树是一种递归定义，所以，要根据二叉树的某种遍历序列来实现建立一棵二叉树的二叉链表存储结构，则可以模仿对二叉树遍历的方法来加以实现。如：如果输入的是一棵二叉树的完整先序遍历序列，则可利用先序遍历方法先生成根结点，再用递归函数调用来实现左子树和右子树的建立。所谓完整的先序遍历序列就是在先序遍历序列中加入空树信息。

【核心算法描述】

void createbitree(Bitree &T)

/*根据输入的完整先序遍历序列建立一棵二叉树*/

{ scanf(\读取完整先序序列中的一个字符*/ if(x==‘#’) T=NULL; else

{ T=(Bitree)malloc(sizeof(Bitnode));/*生成根结点*/ T->data=x;

createbitree(T->lchild);/*递归建立左子树*/ createbitree(T->rchild); /*递归建立右子树*/ } }

void preorder(Bitree T) /*先序遍历二叉树*/ { if(T!=NULL)/*若二叉树非空*/ { visit(T->data); /*访问根结点*/

preorder(T->lchild); /*递归先序遍历左子树*/ preorder(T->rchild); /*递归先序遍历右子树*/ }

}

void inorder(Bitree T) /*中序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/

{ inorder(T->lchild); /*递归中序遍历左子树*/ visit(T->data); /*访问根结点*/

inorder(T->rchild); /*递归中序遍历右子树*/

}

void postorder(Bitree T) /*后序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/

{ postorder(T->lchild); /*递归后序遍历左子树*/ postorder(T->rchild); /*递归后序遍历右子树*/ visit(T->data); /*访问根结点*/ } }

3．源程序代码参考

#include typedef struct Bitnode {char data;

struct Bitnode *lchild,*rchild; }Bitnode,*Bitree;

Bitree creat(Bitree T)/*建立二叉树函数*/ { char x; scanf(\ if (x=='#') T=NULL; else

{T=(Bitree)malloc(sizeof(Bitnode)); if (!T)

{printf(\ exit(-1); } else

{T->data=x;

T->lchild=creat(T->lchild); T->rchild=creat(T->rchild); } } return T; }

Bitree preorder(Bitree T)/*先序遍历二叉树函数*/ { if (T!=NULL)

{ printf(\ preorder(T->lchild); preorder(T->rchild); } }

void midorder(Bitree T) /*中序遍历二叉树函数*/ { if (T!=NULL)

{ midorder(T->lchild); printf(\ midorder(T->rchild); } }

void backorder(Bitree T) /*后序遍历二叉树函数*/ { if (T!=NULL)

{ backorder(T->lchild); backorder(T->rchild); printf(\ } }

main()/*主函数*/

{ Bitree T=NULL; char x;

printf(\请求输入二叉树中各个元素*/ T=creat(T);/*调用建立二叉树函数*/ while(1)

{ printf(\ printf(\ printf(\ printf(\

printf(\请求选择遍历方式*/ scanf(\ switch(x)

{case 1: printf(\

preorder(T); /*调用先序遍历二叉树函数*/ break;

case 2: printf(\

midorder(T); /*调用中序遍历二叉树函数*/

break;

case 3: printf(\

backorder(T); /*调用后序遍历二叉树函数*/ break; case 4: return;

default:printf(\ }

printf(\ } }

4．运行结果参考如图5-1所示：

图5-1 验证性实验运行结果

说明：上述对应的二叉树如图5-2所示。

七、设计性实验

1．编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树，并判断这两棵

a b c e d 图5-2 建立的二叉树

f 二叉树是否相等。

（1）实验要求

① 假设二叉树的结点值是字符，请分别根据输入的两棵二叉树的先序遍历序列和中序遍历序列来建立二叉链表表示的两棵二叉树。

② 分别利用先序、中序和后序遍历方法来实现判断两棵二叉树是否相等的操作。 ③ 主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行利用哪一种遍历方法来判断两棵二叉树是否相等。

（2）核心算法提示 1）二叉树的建立

二叉树的先序遍历序列：

根左子树先序序列右子树先序序列二叉树的中序遍历序列：

左子树先序序列根右子树先序序列图5-3 二叉树的先序、中序遍历序列特征图

假设二叉树的先序遍历序列和中序遍历序列已经存储在数组Pre和Mid中，其序列分列具有如图5-3所示的特征。

根据此特征，建立二叉树的基本步骤可归纳为：

① 建立根结点，取先序先序遍历序列中的第一个字符作为根结点的数据域值； ② 在中序遍历序列中查找确定这个根结点在中序遍历序列中的位置，由此得到在根结点左边的序列即为此根结点左子树的中序遍历序列，而右边的序列即为此根结点右子树的中序遍历序列。

③ 根据左、右子树中序遍历序列中的字符个数再在先序遍历序列中确定左、右子树的先序遍历序列。

④ 根据②、③确定的左、右子树的先序和中序遍历序列采用递归调用的方法建立根结点的左、右子树。

2）判断两棵二叉树是否相等

假设T1和T2是两棵二叉树，如果两棵二叉树都是空树；或者两棵树的根结点的值相等，并且根结点的左、右子树分别也相等，则称二叉树T1与T2是相等的。所以，也可以利用先序、中序和后序遍历方法，采用递归函数来判断两棵树是否相等。假设两棵树相等，函数返回1，否则返回0。下面以用先序遍历方法为例，说明其基本操作步骤为：

① 如果两棵二叉树都为空，则函数返回1；

② 如果两棵二叉树都不为空，则先判断两棵树的根结点值是否相等，如果相等，则再采用递归调用的方法判断它的左、右子树是否相等，如果都相等则函数返回1；

③ 其它情况都返回0。（3）核心算法描述

char Pre[100],Mid[100]; /*存储先序和中序序列的字符数组，定义为全局变量*/

Bitree creat_sub(Bitree T,int Pre_start,int Pre_end,int Mid_start,int Mid_end) /*已知二叉树的先序序列和中序序列，建立此二叉树*/ { int i,ltreelen,rtreelen;

T=(Bitree)malloc(sizeof(Bitnode)); /*建立根结点*/

T->data=Pre[Pre_start]; /*取先序序列中的第一个字符作为根结点的数据域值*/

for(i=Mid_start;Mid[i]!=T->data;i++); /*在中序序列中查找根结点*/ ltreelen=i-Mid_start; /*计算左子树中结点个数*/ rtreelen=Mid_end-i; /*计算右子树中结点个数*/ if(ltreelen)

T->lchild=creat_sub(T,Pre_start+1,Pre_start+ltreelen,Mid_start,Mid_start+ltreelen-1) ; else

T->lchild=NULL; if(rtreelen)

T->rchild=creat_sub(T,Pre_end-rtreelen+1,Pre_end,Mid_end-rtreelen+1,Mid_end); else

T->rchild=NULL; return T; }

int precmp(Bitree T1,Bitree T2)

/*用先序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (T1->data==T2->data)

if (precmp(T1->lchild,T2->lchild)) if(precmp(T1->rchild,T2->rchild))

return 1; return 0; }

int midcmp(Bitree T1,Bitree T2)

/*用中序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (precmp(T1->lchild,T2->lchild)) if (T1->data==T2->data)

if(precmp(T1->rchild,T2->rchild))

return 1; return 0; }

int backcmp(Bitree T1,Bitree T2) /*用后序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)

if (precmp(T1->lchild,T2->lchild))

if(precmp(T1->rchild,T2->rchild)) if (T1->data==T2->data) return 1;

return 0; }

Word文档下载：《数据结构》实验指导书（C语言版）（浦江学院）.doc

搜索更多:《数据结构》实验指导书（C语言版）（浦江学院）