实验一线性表一．目的与要求本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。

要求仔细阅读并理解下列例题，上机通过，并观察其结果，然后独立完成后面的实习题。

二．例题问题描述:用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

输入:初始字符串，插入位置，插入字符，删除字符。

输出:已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

存储结构:采用链式存储结构算法的基本思想:建立链表当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各[运行情况]Input a linktable(a string):abcde↙Build link is :abcdePlease input a char you want to insert after:b↙Please input a char you want to insert:c↙After p insert y,link is:abccdePlease input a char you want to delete:e↙after delete p,link is:abccdOpsite result is :dccba如图显示：实习题：问题描述：设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。

输入：插入前的顺序表，插入的数，插入后的顺序表输出：插入前的顺序表，插入的数，插入后的顺序表存储结构：顺序表存储数据算法基本思想:其实这个题在学C语言时就已经写过了，这里采用顺序表来存储数据。

主要就是考虑插入的位置是不是在最后一个，如果不在最后一个，那么就要移动数据了，算法很简单就不再说了，这里的数据都看成是整型的。

源程序：#include<stdio.h>#include<stdlib.h>void Insert(int* p,int length,int n){int i,j;int flag=0;if(n>=p[length-1]){p[length]=n;flag=1;}else{for(i=length-2;i>=0;i--){if(n>=p[i]){for(j=length;j>=i+2;j--){p[j]=p[j-1]; }p[i+1]=n;flag=1;break;}}}if(flag==0){for(j=length;j>=1;j--){p[j]=p[j-1];}p[0]=n;}}int main(){int L[10]={2,5,8,11,14,17,20};int length=7;int i,x;printf("cha ru qian de shun xu biao wei ：\n");for(i=0;i<length;i++){printf("%4d",L[i]);}printf("\nqing shu ru yao cha ru de zheng shu：\n");scanf("%d",&x);Insert(L,length,x);//插入xprintf("charu%dhoudeshunxubiaowei：\n",x);for(i=0;i<=length;i++){printf("%4d",L[i]);}printf("\n");system("pause");return 0;}运行情况：cha ru qian1 3 6 8 9 10 15cha ru de shu3cha ru hou1 3 3 6 8 9 10 15如图显示：程序的优缺点：本程序可以快速的做完实验的问题，并且看是简单很明了，插入的位置如果是最后一个，如果不在最后一个，那么就要移动数据了实验二树一．目的与要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。

二．例题[问题描述]任意给定一棵二叉树。

试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。

[输入]一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照前序序列的顺序输入该结点的内容。

对下图，其输入序列为ABD..EH...CF.I..G..。

[输出]若为空二叉树，则输出：THIS IS A EMPTY BINARY TREE。

若二叉树不空，按后序序列输出，对上例，输出结果为：DHEBIFGCA。

[存储结构]采用二叉链表存储。

[算法的基本思想]采用递归方法建立和遍历二叉树。

首先建立二叉树的根结点，然后建立其左右子树，直到空子树为止。

后序遍历二叉树时，先遍历左子树，后遍历右子树，最后访问根结点。

运行情况：please input a tree:ABD..EH...CF.I..G..ABD..EH...CF.I..G..the result of post travese is:DHEBIFGCA如图显示：实习题问题描述：编写递归算法，计算二叉树中叶子结点的数目。

分析：这题主要是怎样计算叶子结点数目，其它的算法书上都有。

要注意叶子结点是指该结点既没有左孩子又没有右孩子，采用递归算法就很容易计算出其数目，详见源程序。

输入：按先序序列输入二叉树ABC..D..EF.G...输出：输出二叉树的个数为3存储结构：采用二叉链表存储。

源程序：}#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct node{char info;struct node *llink,*rlink;};typedef struct node NODE;NODE *creat(){char x;NODE *p;scanf("%c",&x);printf("%c",x);if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p->info=x;p->llink=creat();p->rlink=creat();}elsep=NULL;return p;}void countleaf(NODE*t,int &count){if(t){if((!t->llink)&&(!t->rlink))count++;countleaf(t->llink,count);countleaf(t->rlink,count);}}int main(){int e=0;NODE *T;printf("qing shu ru er cha shu ");T=creat();printf("\n");countleaf(T,e);printf("%d\n",e);system("PAUSE");}运行情况：an xian xu shu ru er cha shuABC..D..EF.G...chu ru er cha shu de ge shu 3如图显示：问题描述：编写递归算法，在二叉树中求位于先序序列中第K个位置的结点。

输入：按线序序列输入二叉树ABC..D..EF.G... 与K输出：按先序序列输出第K结点数C存储结构：采用二叉链表存储。

源程序：#include<stdio.h>#include<stdlib.h>#include<malloc.h>struct node{char info;struct node *llink,*rlink;};typedef struct node NODE;NODE *creat(){char x;NODE *p;scanf("%c",&x);printf("%c",x);if(x!='.'){p=(NODE*)malloc(sizeof(NODE));p->info=x;p->llink=creat();p->rlink=creat();}elsep=NULL;return p;}void run(NODE *t,int K){static int i=1;if(t){run(t->llink,K);run(t->rlink,K);if(i++==K)printf("%c",t->info);}}main(){NODE *T;int K;char e;printf("PLease input a tree:\n");T=creat();printf("\n");if(!T)printf("This is aempty binary tree.");else{printf("请输入序号");scanf("%d",&K);printf("The result of post travese is:\n");run(T,K);}printf("\n");system("PAUSE");}运行情况：an xian xu shu ru er cha shuABC..D..EF.G...shu ru K de zhixian xu xu lie di K jie dian shu C如图显示：程序优缺点：可以简单明了的运用，一目了然的看出。

但是必须要是先序序列输入才可以。

太原理工大学《数据结构》实验实验三图一．目的与要求熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。

二．例题[问题描述]给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的一条路径。

[输入]图的顶点个数N，图中顶点之间的关系及要找的路径的起点A和终点B。