数据结构实验讲义(C语言版).doc

数据结构实验

计算机科学与技术系

复习

实验目的：1. 熟悉编程环境；
2. 复习C语言程序设计的基本内容。
实验内容：1.在一维数组的第i个元素之前插入一个元素；
2. 在一维数组中删除第i个元素。

实验一：线性表的顺序存储结构
实验目的：1.帮助学生熟练掌握线性表的操作在顺序存储结构上的实现。
2.使学生掌握顺序表的一些应用。
实验内容：该程序的功能是对元素类型为整型的顺序表进行一些操作。该程序包括顺序表结构类型的定义以及对顺序表操作的具体的函数定义和主函数
注意事项:在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。

程序源代码：
/* 定义ElemType为int类型 */
typedef int ElemType;

/*顺序表存储空间的总分配量*/
#define MAXSIZE 100
#define FALSE 0
#define TRUE 1

/* 顺序存储类型 */
typedef struct
{ElemType data[MAXSIZE]; /*存放线性表的数组*/
int length; /* length是顺序表的长度*/
}SeqList;

/* 初始化顺序表 */
SeqList SeqListInit( )
{SeqList L;
L.length=0;
return L;
}

/* 清空顺序表 */
SeqList ListClear(SeqList L)
{L.length=0;
return L;
}

/* 求顺序表长度 */
int ListLength(SeqList L)
{return(L.length);}

/* 检查顺序表是否为空 */
int ListEmpty(SeqList L)
{if(L.length) return(FALSE);
else return(TRUE);
}

/*检查顺序表是否为满 */
int ListFull(SeqList L)
{if(L.length==MAXSIZE) return(TRUE);
else return(FALSE);
}

/* 遍历顺序表 */
void ListTraverse(SeqList L)
{int i;
if(L.length<=0) printf("顺序表为空\n");
else {printf("当前顺序表中的元素为:\n");
for(i=1;i<=L.length;i++) printf("%d ",L.data[i-1]);
printf("\n");
}

}

/* 从顺序表中查找元素 */

ElemType ListGet(SeqList L ,int i)
{ElemType e;
e=L.data[i-1]; return(e);
}

/* 从顺序表中查找与给定元素值相同的元素在顺序表中的位置 */
int ListLocate(SeqList L, ElemType x)
{int i=0;
while(i<L.length && L.data[i]!=x)
i++;
if (i<L.length) return (i+1);
else return 0;
}

/* 向顺序表中插入元素 */
SeqList ListInsert(SeqList L,int i,ElemType x)
{int j;
if(L.length==MAXSIZE)
printf("表满,不能插入\n");
else if(i<1||i>L.length+1)
printf("插入位置不正确\n");
else { for(j=L.length-1;j>=i-1;j--)
L.data[j+1]=L.data[j];
L.data[i-1]=x;
L.length++;
}
return L;
}

/* 从顺序表中删除元素 */
SeqList ListDelete(SeqList L,int i)
{int j;ElemType x;
if (i<1||i>L.length)
printf("删除位置不正确\n");
else {x=L.data[i-1];
for(j=i;j<=L.length-1;j++)
L.data[j-1]=L.data[j];
L.length--;
printf("%d已被删除\n",x);
}
return L;
}

/*求顺序表中元素的前驱*/
ElemType SeqListPrior(SeqList L,ElemType e)
{int i=0;
while(i<L.length&&L.data[i]!=e)
i++;
if(i==0) {printf("第一个元素没有前驱\n");return 0;}
else if(i<=L.length-1) return(L.data[i-1]);
else {printf("不存在值为%d的元素\n",e);return 0;}
}

/*求顺序表中元素的后继*/
ElemType SeqListNext(SeqList L,ElemType e)
{int i=0;
while(i<L.length&&L.data[i]!=e)
i++;
if(i==L.length-1) {printf("最后一个元素没有后继\n");return 0;}
else if(i<L.length-1) return(L.data[i+1]);
else {printf("不存在值为%d的元素\n",e);return 0;}
}

int scan()
{int d;
printf("请选择所要进行的操作\n");
printf("1.初始化 2.清空3.求顺序表长度4.检查顺序表是否为空\n");
printf("5.检查顺序表是否为满 6.遍历顺序表 7.从顺序表中查找元素\n");
printf("8.从顺序表中查找与给定元素值相同的元素在顺序表中的位置\n");
printf("9.向顺序表中插入元素10. 从顺序表中删除元素\n");
printf("11.求元素的前驱 12.求元素的后继\n");
printf("其他键退出......\n");
scanf("%d",&d);
return(d);
}

main()
{int quit=0;
int i,location;
ElemType e,prior,next;
SeqList L;
printf("第一次操作需选择初始化\n");
while(!quit)
switch(scan())
{case 1:L=SeqListInit();break;
case 2:ListClear(L);break;
case 3:printf("顺序表的长度为%d\n",ListLength(L));break;
case 4:if(ListEmpty(L))printf("顺序表为空\n");else printf("顺序表不为空\n");break;
case 5:if(ListFull(L))printf("顺序表满\n");else printf("顺序表不满\n");break;
case 6:ListTraverse(L);
break;
case 7:printf("请输入要查找的元素的位置\n");
scanf("%d",&i);
if(L.length==0) printf("顺序表已空\n");
else if(i<=0||i>L.length) printf("查找的位置不正确\n");
else
printf("顺序表中第%d个元素的值为:%d\n",i,ListGet(L,i));
break;
case 8:printf("请输入要查找的元素的值\n");
scanf("%d",&e);
if(L.length==0) printf("顺序表已空\n");
else
{location=ListLocate(L,e);
if(location==0) printf("顺序表中不存在值为%d的元素\n",e);
else printf("顺序表中%d的位置是:%d\n",e,ListLocate(L,e));
}
break;
case 9:printf("请输入要插入的元素的位置和其值:\n");
scanf("%d%d",&i,&e);
L=ListInsert(L,i,e);
break;
case 10:printf("请输入要删除的元素的位置:\n");
scanf("%d",&i);
L=ListDelete(L,i);
break;
case 11:scanf("%d",&e);
prior=SeqListPrior(L,e);
if(prior) printf("%d的前驱是:%d\n",e,prior);break;
case 12:scanf("%d",&e);
next=SeqListNext(L,e);
if(next) printf("%d的后继是:%d\n",e,next);break;
default:quit=1;}
}

实验二：线性表的链式存储结构
实验目的：1.熟悉链表结构；
2.掌握链表结构上的各种操作；
3.学会运用链表结构求解问题。
实验内容：建立一个单链表,在此单链表上实现以下几种操作:
1、求此单链表的长度；
2、在此单链表的第i个元素结点之前插入一个结点；
3、删除此单链表的第i个元素结点。
程序源代码：
/* 定义ElemType为int类型 */
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define NULL 0
#define flag -1

/* 单链表的结点类型 */
typedef struct LNode
{ElemType data;
struct LNode *next;
} LNode,*LinkedList;

/* 初始化单链表 */
LinkedList LinkedListInit()
{LinkedList L;
L=(LinkedList)malloc(sizeof(LNode));
L->next=NULL;
return L;
}

/* 清空单链表 */
void LinkedListClear(LinkedList L)
{L->next=NULL;
printf("链表已经清空\n");
}

/* 检查单链表是否为空 */
int LinkedListEmpty(LinkedList L)
{if(L->next==NULL) return TRUE;
else return FALSE;
}

/* 遍历单链表 */
void LinkedListTraverse(LinkedList L)
{LinkedList p;
p=L->next;
if(p==NULL) printf("单链表为空表\n");
else
{printf("链表中的元素为:\n");
while(p!=NULL)
{printf("%d ",p->data); p=p->next;}
}
printf("\n");
}

int LinkedListLength (LinkedList L)
{LinkedList p;
int j;
p=L->next;
j=0;
while(p!=NULL)
{ j++;p=p->next; }
return j;
}

LinkedList LinkedListGet(LinkedList L,int i)
{LinkedList p;int j;
p=L->next; j=1;
while (p!=NULL && j<i )
{p=p->next; j++; }
if (j==i) return p;
else return NULL;
}

int LinkedListLocate ( LinkedList L, ElemType x)
{LinkedList p;int j;
p=L->next; j=1;
while ( p!=NULL && p->data != x)
{p=p->next;j++;}
if(p) return j;
else return 0;
}

void LinkedListInsert(LinkedList L, int i, ElemType x)
{LinkedList p,s;
int j;
j=1;p=L;
while(p&&j<i)
{p=p->next;j++;}
if(p==NULL||j>i)
printf("插入位置不正确\n");
else {s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=p->next;
p->next=s;
printf("%d已插入到链表中\n",x);
}
}

void LinkedListDel(LinkedList L,int i)
{ LinkedList p,q;
int j;
j=1;p=L;
while(p->next&&j<i)
{p=p->next;j++;}
if(p->next==NULL)
printf("删除位置不正确\n");
else {q=p->next;p->next=q->next;free(q);
printf("第%d个元素已从链表中删除\n",i);
}
}

LinkedList LinkedListCreat( )
{ LinkedList L=LinkedListInit(),p,r;
ElemType x;
r=L;
printf("请依次输入链表中的元素,输入-1结束\n");
scanf("%d",&x);
while (x!=flag)
{p=(LinkedList)malloc(sizeof(LNode));
p->data=x;
r->next=p;
r=p;
scanf("%d",&x);
}
r->next=NULL;
return L;
}

int scan()
{int d;
printf("请选择要进行的操作\n");
printf("1.初始化 2.清空3.求链表长度4.检查链表是否为空\n");
printf("5.遍历链表 6.从链表中查找元素\n");
printf("7.从链表中查找与给定元素值相同的元素在顺序表中的位置\n");
printf("8.向链表中插入元素9. 从链表中删除元素\n");
printf("其他键退出。。。。。\n");
scanf("%d",&d);
return(d);
}

main()
{int quit=0;
int i,locate;
ElemType e;
LinkedList L,p;
while(!quit)
switch(scan())
{case 1:L=LinkedListInit();printf("\n");break;
case 2:LinkedListClear(L);printf("\n");break;
case 3:printf("链表的长度为 %d\n",LinkedListLength(L));break;
case 4:if(LinkedListEmpty(L))printf("链表为空\n");else printf("链表非空\n");break;
case 5:LinkedListTraverse(L);
break;
case 6:printf("请输入待查询元素在链表中的位置:");
scanf("%d",&i);
p=LinkedListGet(L,i);
if(p) printf("链表中第%d个元素的值为:%d\n",i,p->data);
else printf("查询位置不正确\n");
break;
case 7:printf("请输入待查询元素的值:");
scanf("%d",&e);
locate=LinkedListLocate(L,e);
if(locate)
printf("%d在链表中的位置是:%d\n",e,locate);
else printf("链表中没有值为%d的元素\n",e);
break;
case 8:printf("请输入插入元素的位置和值(中间以空格或回车分隔):\n");
scanf("%d%d",&i,&e);
LinkedListInsert(L,i,e);
break;
case 9:if(LinkedListLength(L)==0)
printf("链表已经为空,不能删除\n");
else {printf("请输入待删除元素的位置:\n");
scanf("%d",&i);
LinkedListDel(L,i);}
break;
case 10:L=LinkedListCreat();
printf("\n");break;
default:quit=1;}
}
实验三：栈和队列
实验目的：1.熟悉栈和队列结构；
2.掌握栈和队列结构上的各种操作；
3.学会运用栈和队列结构求解问题。
实验内容：1.建立一个链队列，在建立好的队列中实现以下操作
①makenull：将队列置成空队列；
②get：返回队列的第一个元素；
③enqueue：把元素x插入到队列的后端；
④dequeue：删除队列的第一个元素；
⑤empty：判定队列是否为空。
2.栈的基本操作实现。

1、程序清单：
#define null 0
struct node
{int data;
struct node *next;
};
struct node *rear;
struct node *creat(void)
{struct node *p,*front;
int i,n;
scanf("%d",&n);
front=(struct node *)malloc(2);
front->next=null;
for (i=1;i<=n;i++)
{ p=(struct node *)malloc(2);
scanf("%d",&p->data);
p->next=front->next;
front->next=p;
}
rear=front;
while (rear->next!=null)
rear=rear->next;
return(front);
}
struct node *makenull(struct node *front)
{ rear=front;
front->next=null;
return(front);
}
int get(struct node *front)
{ int x;
x=front->next->data;
return(x);
}
struct node *enqueue(struct node *front ,int x)
{struct node *s;
s=(struct node *)malloc(2);
s->data=x;
s->next=rear->next;
rear->next=s ;
rear=s;
return(front);
}
struct node *dequeue(struct node *front)
{struct node *q;
q=front->next;
front->next=front->next->next;
free(q);
return(front);
}
int empty(struct node *front)
{if (front==rear)
return(1);
else
return(0);
}
void print(struct node *front)
{ struct node *p;
p=front;
while(p->next!=null)
{p=p->next;printf("%d",p->data);}
}
main()
{int x,e,y;
struct node *front;
front=creat();
print(front);
e=get(front);
printf(“%d”,e);
scanf("%d",&x);
front=enqueue(front,x);
print(front);
front=dequeue(front);
print(front);
y=empty(front);
printf("%d",y);
makenull(front);
y=empty(front);
printf("%d",y);
}

2、程序清单：
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define False 0
#define True 1

typedef struct
{char elem[MAX];
int top;
}SqStack;
char ch;
SqStack S;
void Initial(void)
{S.top=-1;
}

int Push(char ch)
{
if(S.top>=MAX-1) return False;
else {S.top++;
S.elem[S.top]=ch;
return True;
}
}

int Pop(void)
{
if(S.top<=-1) return False;
else {S.top--;
ch=S.elem[S.top+1];
return True;
}
}

int Gettop(void)
{
if(S.top<=-1)
return False;
else {ch=S.elem[S.top];
return True;
}
}

void SqStackPrint(void)
{
int i;
if(S.top<=-1) printf("stack empty!\n");
else {printf("stack all elem is:\n");
for(i=0;i<=S.top;i++)
printf("%c ",S.elem[i]);
printf("\n");
}
}

void main()
{
int j,flag=1;

int temp;
textbackground(3);
textcolor(15);
clrscr();

printf("本程序实现顺序结构的堆栈的操作。\n");
printf("可以进行入栈，出栈，取栈顶元素等操作。\n");

Initial();

while(flag)
{ printf("pleate slect:\n");
printf("1.disp stack all elem \n");
printf("2.push \n");
printf("3.pop \n");
printf("4.read top \n");
printf("5.exit \n");
scanf("%d",&j);
switch(j)
{case 1:SqStackPrint();
break;
case 2:printf("pleate input push stack elem(a char):");
scanf(" %c",&ch);
temp=Push(ch);
if(temp==False) printf("stack full! error!\n");
else {printf("PUSH OK!\n");
SqStackPrint();
}
break;
case 3:temp=Pop();
if(temp==False) printf("stack empty!\n");
else {printf("POP OK:%c\n",ch);
SqStackPrint();
}
break;
case 4:temp=Gettop();
if(temp==False) printf("stack empty!\n");
else printf("stack top elem is:%c\n",ch);
break;
default:flag=0;printf("exit !\n");
}
}
getchar();
}

实验四：串
实验目的：使学生熟练掌握串的一些基本操作。
实验内容：已知有一串s，完成下面操作：
1、 在s串的第i个字符之前插入一个串t;
2、从串s中删除一个子串，子串由起始位置i和长度j决定。
程序清单：int n1,n2;
void inser(char s[],int i,char t[])
{int k;
for(k=n1;k>=i;k--)
s[k+n2]=s[k];
for(k=1;k<=n2;k++)
s[k+i-1]=t[k];
n1=n1+n2;
for(k=1;k<=n1;k++)
printf("%c",s[k]);
}
void delete(char s[],int i,int j)
{int k;
for(k=i+j;k<=n1;k++)
s[k-j]=s[k];
n1=n1-j;
for(k=1;k<=n1;k++)
printf("%c",s[k]);
}
main()
{char s[10],t[10];
int i,j,k;
scanf("%d%d",&n1,&n2);
for (k=1;k<=n1;k++)
scanf("%c",&s[k]);
for (k=1;k<=n2;k++)
scanf("%c",&t[k]);
scanf("%d",&i);
insert(s,i,t);
scanf("%d%d",&i,&j);
delete(s,i,j);
}

实验五：树
实验目的：1、使学生熟练掌握二叉树的结构特性。
2、使学生熟练掌握二叉树遍历的几种方法。
实验内容：利用先序遍历的思想建立一棵二叉树，对其进行如下操作：
1、先序遍历；
2、中序遍历；
3、后序遍历；
4、求深度；
5、求结点个数。
程序清单：#include"stdio.h"
#define null 0
typedef struct node{
char data;
struct node *Lchild;
struct node *Rchild;
}node,*Btree;
Btree create( )
{ char c;
Btree T;
scanf("%c",&c);
if(c=='#')
T=NULL;
else
{ T=(Btree)malloc(sizeof(node));
T->data=c;
T->Lchild=create();
T->Rchild=create();
}
return T;
}
void preorder(Btree T)
{ if(T)
{ printf("%c ",T->data);
preorder(T->Lchild);
preorder(T->Rchild);
}
}
void inorder(Btree T)
{if(T)
{inorder(T->Lchild);
printf("%c ",T->data);
inorder(T->Rchild);
}
}
void postorder(Btree T)
{if(T)
{postorder(T->Lchild);
postorder(T->Rchild);
printf("%c ",T->data);
}
}
int depth(Btree T)
{int dep1,dep2;
if(T==null)
return (0);
else
{dep1=depth(T->Lchild);
dep2=depth(T->Rchild);
if (dep1>dep2) return (dep1+1);
else return (dep2+1);
}
}
int nodesum(Btree T)
{ if(T==null)
return (0);
else
return (nodesum(T->Lchild)+nodesum(T->Rchild)+1);
}
main()
{ Btree T;
T=create();
preorder(T);
printf("\n");
inorder(T);
printf("\n");
postorder(T);
printf("\n%d",depth(T));
printf("\n%d\n",nodesum(T));
}

实验六：查找
实验目的：1.使学生熟练掌握顺序查找算法；
2.使学生熟练掌握折半查找算法。
实验内容：1.编写顺序查找和折半查找算法。
2.(选做) 建立一棵二叉排序树，实现在其中进行查找操作。
程序清单：1.int n;
int search_seq(int a[],int key)
{int i=n;
a[0]=key;
while(a[i]!=key)
i--;
return(i);
}
int search_bin(int a[],int key)
{int l,h,m;
l=0;h=n-1;
while(l<=h)
{m=(l+h)/2;
if(key<a[m]) h=m-1;
else if(key==a[m]) return(m);
else l=m+1;
}
return(-1);
}
main()
{int i,key,a[20],b[20];
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&key);
printf("%d",search_seq(a,key));
scanf("%d",&n);
for(i=0;i<=n-1;i++)
scanf("%d",&b[i]);
scanf("%d",&key);
printf("%d",search_bin(b,key));
}
2.#include"stdio.h"
#define null 0
typedef struct node{
char data;
struct node *Lchild;
struct node *Rchild;
}node,*Btree;
Btree create( )
{ char c;
Btree T;
scanf("%c",&c);
if(c=='#')
T=NULL;
else
{ T=(Btree)malloc(sizeof(node));
T->data=c;
T->Lchild=create();
T->Rchild=create();
}
return T;
}
char search(char key,Btree T)
{Btree p;
p=T;
while(p!=null)
{if(p->data==key)
return(p->data);
else if(key<p->data)
p=p->Lchild;
else
p=p->Rchild;
}
re