数据结构及数据库实验报告2015年00121076张德良电工二.doc

专业资料整理分享
实验1 ADT表的编程与实现

电工二
姓名：张德良
学号：201400121076
实验目的：加深对抽象数据类型ADT表的理解；

实验原理：参照课本p.44-49，及Figure3.6-3.13.

实验内容：编写程序实现ADT表的定义，及常用操作：
1）、判断表是否为空；
源程序
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"

// 定义链表中的节点
typedef struct node
{
int member; // 节点中的元素
struct node *pNext; // 指向下一个节点的指针
}Node,*pNode;

// 函数声明
pNode CreateList(); // 创建链表函数
void TraverseList(pNode ); // 遍历链表函数
bool Is_Empty(pNode); // 判断链表是否为空

int main()
{
pNode pHead = NULL; // 定义初始化头节点
struct Node *pHead == NULL
int flag; // 存放链表是否为空的标志，
int Len;
pHead = CreateList(); // 创建一个非循环单链表，并将该链表的头结点的地址付给pHead
TraverseList(pHead); // 调用遍历链表函数
if (Is_Empty(pHead) == true) // 判断列表是否为空
{
return 0;
}

return 0;
}

// 创建链表函数
pNode CreateList()
{
int i;
int len;
int val;
pNode pHead = (pNode)malloc(sizeof(Node));
pNode pTail = pHead;
pTail->pNext = NULL;
printf("请输入节点个数：");
scanf("%d",&len);
for(i = 0; i < len; i++)
{
printf("第 %d 个节点的数值：",i+1);
scanf("%d",&val);
pNode pNew = (pNode)malloc(sizeof(Node));
pNew->member = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;

}

// 遍历链表函数
void TraverseList(pNode pHead)
{
pNode p = pHead->pNext;
while(NULL != p)
{
printf("%d ",p->member);
p = p->pNext;
}
printf("\n");
return ;
}

// 判断链表是否为空
bool Is_Empty(pNode pHead)
{
if (NULL == pHead->pNext)
{
printf ("链表为空！\n");
return true;
}
else
{
return false;
}
}
运行结果
输入节点个数及各节点数值如下

2）获取第i个节点的内容
源程序
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define maxsize 50
typedef struct
{
int data[maxsize];
int last;
}Sequenlist;

Sequenlist * InitList () //创建顺序表
{
Sequenlist * L ;
L= (Sequenlist *) malloc( sizeof(Sequenlist) );
L->last =0;
return(L);
}

Sequenlist * creat() //创建一个有具体内容的顺序表
{
Sequenlist * L; int i=1,n;
L=InitList( );
printf("请输入数据,以0结束\n");
scanf("%d",&n);
while(n!=0 && L->last<maxsize)
{
L->data[i]=n;
i=i++;
L->last++;
scanf("%d",&n);
}
return(L);
}

int GetData (Sequenlist * L, int i ) //获取第i个元素
{
if ( i >=1 && i <=L->last)
return (L->data[i]);
else
{
printf ("参数 i 不合理！\n");
return 0;
}
}

void main()
{
int length,i;
int value,number,location;
int j,k;
int flag;

Sequenlist * L ;
L=creat();

printf("Please input the location\n");
scanf("%d",&location);
value=GetData(L,location);
printf("The number is %d\n",value);
}
运行程序
依次输入链表元素的值，以0结束
‚输入要查找元素的位置

3）链表删除元素
源程序
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
typedef int ElemType;
typedef void Status;
typedef struct Node
{
ElemType data;
struct Node *next;
}
LNode, *LinkList;
Status CreatList(int ,LinkList );
Status Traverse(LinkList );
Status FreeList(LinkList );
ElemType DelElem(LinkList ,ElemType );
int main()
{
int Length; ElemType e;
LinkList L;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("Input the Length of List:\n");
scanf("%d",&Length);
CreatList(Length,L);
printf("Travers the List :\n");
Traverse(L);
while(1)
{
printf("请输入要删除的元素：\n");
scanf("%d",&e); if(DelElem(L,e))//在L中将元素e删除
{
printf("删除%d后：\n",e);break;
}
printf("未找到该元素，删除失败\n");
}
Traverse(L);
FreeList(L);
printf("List release Success!\n");
return 0;
}
Status CreatList(int Length,LinkList L)
{
int i;
LinkList Body=NULL,p=L;
for (i=0;i<Length;i++)
{
Body=(LinkList)malloc(sizeof(LNode));
p->next=Body;
printf("Input the %dth num:\n",i+1);
scanf("%d",&(Body->data));
p=Body;
}
Body->next=NULL;
}
Status FreeList(LinkList L)
{
LinkList temp=NULL,p=L;
while (p)
{
temp=p->next;
free(p);
p=temp;
}
}
Status Traverse(LinkList L)
{
LinkList p=L;
p=p->next;
while(p)//while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
ElemType DelElem(LinkList L,ElemType e)
{
LinkList p,q;
q=p=L;
p=p->next;//p指向头结点后第一个元素
while(p)
{
if(p->data==e)
{
q->next=p->next;
free(p);
return 1;
}
else
{
q=p;//q始终指向p上一个结点
p=p->next;
}
} //没有执行上个return,说明没找到
return 0;
}
运行结果：
输入节点个数
依次输入各个节点的数值
输入要删除的元素

4）链表插入元素。
源程序
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#define N 5
typedef int elemtype;
typedef struct node
{
elemtype data;
struct node *next;
}linklist;

linklist *Creatlist(linklist*L){
L=(linklist*)malloc(sizeof(linklist));
L->next=NULL;
return L;
}
int Judge(linklist *L){
if(L->next==NULL)
{
printf("建表成功...\n");
}
else
printf("建表失败.\n");
return 0;
}
int Input(linklist *L,int x,linklist *r){
int i;
linklist *p;
p=(linklist*)malloc(sizeof(linklist));
p->data=x;
p->next=NULL;
r->next=p;
printf("%d ",p->data);
return 0;
}
int Insert1(linklist *L,int i){
linklist *p,*q,*r,*t;
int j=1,item;
p=L->next;
q=L;
r=L;
if(L->next==NULL)
{
printf("表空.\n");
return 0;
}
else
{
while(p!=NULL&&j<i)
{
q=p;
p=p->next;
j++;
}
if(p==NULL)
{
printf("%d不在表的范围内.\n");
return 0;
}
else
{
t=(linklist*)malloc(sizeof(linklist));
t->next=NULL;
printf("请输入item:");
scanf("%d",&item);
t->data=item;
t->next=p;
q->next=t;
}
printf("在第%d位上插入值为%d的节点后的所有数据为\n",i,item);
for(j=0;j<N+1;j++)
{
r=r->next;
printf("%d ",r->data);
}
printf("\n");
return 1;
}
}
int main()
{
int i,item,k;
linklist *L,*r;
printf("单向链表的创建（包括初始化）与输出\n");
L=Creatlist(L);
Judge(L);
printf("表中的数据为：");
r=L;
Input(L,5,r);
r=r->next;
Input(L,32,r);
r=r->next;
Input(L,67,r);
r=r->next;
Input(L,56,r);
r=r->next;
Input(L,9,r);
r=r->next;
printf("\n");
printf("在给定的单链表的第i位上插入值为item的节点\n");
printf("请输入i:");
scanf("%d",&i);
Insert1(L,i);
return 0;
}
运行结果：
输入要节点的位置
‚输入要插入节点的数值

5）、实验心得：
课上讲的ADT表的各种实现通过这次试验使我对课堂知识有了更深刻的理解。
完美WORD格式编辑