数据结构实验

算法与数据结构实验

实验一 有序单链表的合并

一、 实验目的

1. 掌握单链表的原理与基本操作方法。

2. 掌握线性表的基本操作：插入、删除、查找等在链式

存储结构上的运算。

二、 实验要求

1. 认真设计本实验的程序。上机调试运行本程序。

2. 保存和打印出程序的运行结果，并结合程序进行分析。

三、 实验内容

1. 建立两个已排序的线性链表。

2. 将两个链表合并为一个新的有序的线性链表。

选作实验：一元多项式加法

#include #include #include struct Link {int data;

struct Link *next;

};//建立链表的函数，参数为：链表的头指针、尾指针、数据。 void CreateLink(struct Link **h,struct Link **t,int d) {struct Link *p;

p=(struct Link *)malloc(sizeof(struct Link)); p->data=d;

if((*h)==NULL) {

(*h)=p;

(*t)=p; } else {

(*t)->next=p; (*t)=p; }

(*t)->next=NULL; }//合并链表函数

struct Link *MergeLink(struct Link *Ah,struct Link *Bh) {struct Link *Ch=NULL,*Ct=NULL,*A=NULL,*B=NULL; A=Ah; B=Bh;

while(A!=NULL && B!=NULL)

{if(A->datadata) //若此时A链表的数据比B链表的小，则将A的数据放到C链表中，并将A链表向后移一位 {CreateLink(&Ch,&Ct,A->data); A=A->next; }

else //否则将B中数据放到C链表中，并将B链表向后移一位 {CreateLink(&Ch,&Ct,B->data); B=B->next; } }

if(A) Ct->next=A; //若上面的while循环结束后，A里面还有数据，就直接将A接在C链表后面

if(B) Ct->next=B; //若上面的while循环结束后，B里面还有数据，就直接将B接在C链表后面 return Ch; //返回合并后的链表 }

//输出链表函数

void PrintLink(struct Link *h) {struct Link *p; p=h;

while(p!=NULL)

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

printf(\}

void main() {int d;

struct Link *Ah=NULL,*At=NULL; struct Link *Bh=NULL,*Bt=NULL; struct Link *Ch=NULL; //建立A链表

printf(\输入链表A的数据,以输入111结束输入:\\n\while(1)

{scanf(\if(d==111) break;

CreateLink(&Ah,&At,d); }

//建立B链表

printf(\输入链表B的数据,以输入111结束输入:\\n\while(1)

{scanf(\if(d==111) break;

CreateLink(&Bh,&Bt,d); }printf(\链表合并结果:\\n\

Ch=MergeLink(Ah,Bh); //调用合并函数，并将合并的结果返回给Ch

PrintLink(Ch); //输出链表 }

运行结果：

实验二 栈的基本操作和应用

一 实验目的

1． 掌握串、堆栈的原理、表示及实现方法。

2． 掌握堆栈的基本操作，判断堆栈空、满，入栈和出栈操作。

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 用键盘输入一字符序列，存入一字符数组中。 2． 利用堆栈判断其是否中心对称（回文数据），并输出结果。

选作实验：算数表达式求值

1. 输入一算数表达式（数据自定）。 2. 利用堆栈实现该算数表达式求值。 #include #include

char s[100]; //栈空间

int top=-1; //栈为空的标志

//判断栈是否为空 int isEmpty() {

if(top==-1) return 1; else return 0; }

//进栈

void push(char c) {

s[top++]=c; }

//出栈 char pop() {

return s[--top];

}

//检验是否回文的函数 int check() {

int i=0,len;

char str[100],ch;

//如果直接用scanf(\也行，但是所输入的字符序列中不能有空格 //若用ch=getchar())!='\\n'，则输入的字符序列没有限制 while((ch=getchar())!='\\n') {

str[i++]=ch; }

len=i; //len是字符序列str的长度

for(i=0;i

//从栈顶取一个字符，和str中的字符进行对比。原理就是 //进栈的序列和出栈的序列是相反的，【只要进栈和出栈的序列一样的话，那么他就是回文序列】 if(pop()!=str[i]) return 0; if(!isEmpty()) return 0; return 1; }

void main() {

if(check()) printf(\回文\\n\

else printf(\不回文\\n\}

实验三 二叉树的建立和层次遍历

一 实验目的

1． 掌握二叉树的原理、表示及实现方法。

2． 掌握二叉树的基本操作，二叉树的建立、遍历方法。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构实验在线全文阅读。