数据结构单链表实验报告.doc

洛阳理工学院实验报告
系别
计算机系
班级

学号

姓名

课程名称
数据结构
实验日期
11.7
实验名称
链表的基本操作
成绩

实验目的：
熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。
实验条件：
计算机一台，Visual C++6.0
实验内容：
1. 问题描述
以单链表为存储结构实现以下基本操作：
(1) 在第i个元素前插入一个新元素。
(2) 查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。
(3) 删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。
2. 数据结构类型定义
typedef struct LinkNode
{
int Value;
struct LinkNode * Next;
}Node,*LinkList;
3. 模块划分
（1）初始化链表：void InitList(LinkList * L);
（2）创建链表:尾插法：int CreateFromTail(LinkList L);
（3）在指定位置插入元素：int InsList(LinkList L,int i,int e);
（4）在指定位置删除元素：int DelList(LinkList L,int i,int *e);
返回值说明：返回ERROR插入失败，返回OK插入成功;
（5）按位置查找链表元素：int GetList(LinkList L,int i,int *e);
4. 详细设计
void init_linklist(LinkList *l)/*对单链表进行初始化*/{
*l=(LinkList)malloc(sizeof(Node)); /*申请结点空间*/
(*l)->next=NULL; /*置为空表*/
}
void CreateFromHead(LinkList L)
{
Node *s;
char c;
int flag=1;
while(flag) /* flag初值为1，当输入"$"时，置flag为0，建表结束*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/
s->data=c;
s->next=L->next;/*将s结点插入表头*/
L->next=s;
}
else
flag=0;
}
}
void CreateFromTail(LinkList L)
{
Node *r, *s;
char c;
int flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/
}
}
}

Node * Get (LinkList L, int i)
/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/
{
int j;
Node *p;
p=L;
j=0; /*从头结点开始扫描*/
while ((p->next!=NULL)&&(j<i))
{
p=p->next; /* 扫描下一结点*/
j++; /* 已扫描结点计数器 */
}
if(i == j)
return p; /* 找到了第i个结点 */
else
return NULL; /* 找不到，i≤0或i>n */
}

Node *Locate( LinkList L,ElemType key)
/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/
{
Node *p;
p=L->next; /*从表中第一个结点开始 */
while (p!=NULL)
{
if (p->data!=key)
p=p->next;
else
break; /*找到结点值=key时退出循环 */
}
return p;
}
int InsList(LinkList L,int i,ElemType e)
/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/
{
Node *pre,*s;
int k;
pre=L;
k=0; /*从"头"开始，查找第i-1个结点*/
while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1结点*/
if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/
{
printf("插入位置不合理!");
return ERROR;
}
s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点S */
s->data=e; /*值e置入s的数据域*/
s->next=pre->next; /*修改指针，完成插入操作*/
pre->next=s;
return OK;
}
int DelList(LinkList L,int i,ElemType *e)
/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/
{
Node *pre,*r;
int k;
pre=L;
k=0;
while(pre->next!=NULL && k<i-1) /*寻找被删除结点i的前驱结点i-1使p指向它*/
{
pre=pre->next;
k=k+1;
} /*查找第i-1个结点*/
if(!(pre->next)) /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/
{
printf("删除结点的位置i不合理!");
return ERROR;
}
r=pre->next;
pre->next=pre->next->next; /*修改指针，删除结点r*/
*e = r->data;
free(r); /*释放被删除的结点所占的内存空间*/
printf("成功删除结点!");
return OK;
}
int ListLength(LinkList L)
/*求带头结点的单链表L的长度*/
{
Node *p;
int j;
p=L->next;
j=0; /*用来存放单链表的长度*/
while(p!=NULL)
{
p=p->next;
j++;
}
return j; /*j为求得的单链表长度*/
}
5.测试数据及结果

实验总结：
在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试，发现错误所在，并且更改。

实验一、单链表的插入和删除
一、目的
了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
二、要求：
建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。
三、程序源代码
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"ctype.h"
typedef struct node //定义结点
{
char data[10]; //结点的数据域为字符串
struct node *next; //结点的指针域
}ListNode;
typedef ListNode * LinkList; // 自定义LinkList单链表类型
LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表
ListNode *LocateNode(); //函数，按值查找结点
void DeleteList(); //函数，删除指定值的结点
void printlist(); //函数，打印链表中的所有值
void DeleteAll(); //函数，删除所有结点，释放内存
//==========主函数==============
void main()
{
char ch[10],num[10];
LinkList head;
head=CreatListR1(); //用尾插入法建立单链表，返回头指针
printlist(head); //遍历链表输出其值
printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点
scanf("%s",num);
if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){
printf("Please input Delete_data:");
scanf("%s",ch); //输入要删除的字符串
DeleteList(head,ch);
printlist(head);
}
DeleteAll(head); //删除所有结点，释放内存
}
//==========用尾插入法建立带头结点的单链表===========
LinkList CreatListR1(void)
{
char ch[10];
LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点
ListNode *s,*r,*pp;
r=head;
r->next=NULL;
printf("Input # to end "); //输入“#”代表输入结束
printf("Please input Node_data:");
scanf("%s",ch); //输入各结点的字符串
while(strcmp(ch,"#")!=0) {
pp=LocateNode(head,ch); //按值查找结点，返回结点指针
if(pp==NULL) { //没有重复的字符串，插入到链表中
s=(ListNode *)malloc(sizeof(ListNode));
strcpy(s->data,ch);
r->next=s;
r=s;
r->next=NULL;
}
printf("Input # to end ");
printf("Please input Node_data:");
scanf("%s",ch);
}
return head; //返回头指针
}
//==========按值查找结点，找到则返回该结点的位置，否则返回NULL==========
ListNode *LocateNode(LinkList head, char *key)
{
ListNode *p=head->next; //从开始结点比较
while(p&&strcmp(p->data,key)!=0 ) //直到p为NULL或p->data为key止
p=p->next; //扫描下一个结点
return p; //若p=NULL则查找失败，否则p指向找到的值key的结点
}
//==========删除带头结点的单链表中的指定结点=======
void DeleteList(LinkList head,char *key)
{
ListNode *p,*r,*q=head;
p=LocateNode(head,key); //按key值查找结点的
if(p==NULL ) { //若没有找到结点，退出
printf("position error");
exit(0);
}
while(q->next!=p) //p为要删除的结点，q为p的前结点
q=q->next;
r=q->next;
q->next=r->next;
free(r); //释放结点
}
//===========打印链表=======
void printlist(LinkList head)
{
ListNode *p=head->next; //从开始结点打印
while(p){
printf("%s, ",p->data);
p=p->next;
}
printf("\n");
}
//==========删除所有结点，释放空间===========
void DeleteAll(LinkList head)
{
ListNode *p=head,*r;
while(p->next){
r=p->next;
free(p);
p=r;
}
free(p);
}
运行结果：

加的添加结点的代码：
int Insert(ListNode *head) // the insert function
{
ListNode *in,*p,*q;
int wh;
printf("input the insert node:");

in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL;
p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL;
q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL;
if(!in)
return 0;
scanf("%s",in->data);
printf("input the place where you want to insert you data:");
scanf("%d",&wh);
for(p=head;wh>0;p=p->next,wh--);
q=p->next;
p->next=in;
in->next=q;
return 1;
}

运行结果：

最后提示为OK 添加成功。

实验心得：这个实验中 主要修改的是ch 和 num 把它们由指针改成数组 因为不改的话在后面delect函数中会出现没有地址的情况 找不到地址就不能执行功能 然后把locate函数的判断语句改一下 避免矛盾的出现。

实验二、二叉树操作
一、 目的
掌握二叉树的定义、性质及存储方式，各种遍历算法。

二、 要求
采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
三、 程序源代码
#include"stdio.h"
#include"string.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点“#”以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); // 生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用“先进先出”（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:");//输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
执行程序
1. 先序遍历

2. 中序遍历

3. 后序遍历

4. 结点数 叶子数 高度

5..层次遍历

自己设计的：
abdhl##m##i##e#jn###cf#ko###g##
1.预计先序遍历结果：abdhlmiejncfkog
2.预计中序遍历结果：lhmdibenjafokcg
3.预计后序遍历结果：lmhidnjebokfgca
4.结点数 15 高度5 叶子数 6

实际结果：

实验心得：这次实验主要是要让我们熟练树及其相关知识 熟练掌握先序中序后序遍历，层次遍历 然后我们自己画一个图 会实现以上功能 以及叶子数 结点数还有高度的计算 程序里面大量运用了递归以及队的应用，

实验三、图的遍历操作

一、 目的
掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。
二、 要求
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。
三、 DFS和BFS 的基本思想
深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。
广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。
四、 程序源代码
1． 邻接矩阵作为存储结构的程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k<G->e;k++) { //读入e条边，建立邻接矩阵
scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵
int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;j<G->n;j++) //依次搜索Vi的邻接点
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点
}
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //标志向量初始化
for(i=0;i<G->n;i++)
cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { //队非空则执行
i=cq[f]; f=f+1; //Vf出队
for(j=0;j<G->n;j++) //依次Vi的邻接点Vj
if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问
printf("%c",G->vexs[j]); //访问Vj
visited[j]=TRUE; r=r+1; cq[r]=j; //访问过Vj入队
}
}
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序号为3的顶点开始广度优先遍历
printf("\n");
}

调试结果：

自己画的图：

1对应顶点下标0 以此类推 9对应下标8
预计运行结果：
DFS:012345678
BFS:324105687

对应我这个图：
DFS：123456789
BFS：435216798

实验心得：图在数据结构中是相当重要的一部分 联系很多现实问题 图的根本就是顶点和边 通过顶点和边建立邻接矩阵以及邻接链表 广度搜索和深度搜索是此算法着重关注的地方。要学会自己画图 然后写出这两种搜索的结果，程序中用了队的算法 是亮点 通过TRUE和FAUSE来标记顶点是否以及访问 避免重复

实验四、排序
一、 目的
掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。
二、 要求
实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。
三、 程序示例
#include"stdio.h"
#include"stdlib.h"
#define Max 100 //假设文件长度
typedef struct{ //定义记录类型
int key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
int n; //顺序表实际的长度

1、 直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。
//==========直接插入排序法======