数据结构实验报告(3)

2019-01-10 12:44

ListInsert(&L,1,0);

printf(\在L的表头插入0后：*L.elem=\

for(j=1;j<=ListLength(L);j++) printf(\为元素个数 */ printf(\

printf(\有可能改变) L.length=%d(改变) L.listsize=%d(改变)\\n\ GetElem(L,5,&e);

printf(\第5个元素的值为：%d\\n\ for(j=3;j<=4;j++)

{ k=LocateElem(L,j,comp);

if(k) printf(\第%d个元素的值为%d的平方\\n\ else printf(\没有值为%d的平方的元素\\n\ }

for(j=1;j<=2;j++) /* 测试头两个数据 */

{ GetElem(L,j,&e0); /* 把第j个数据赋给e0 */ i=PriorElem(L,e0,&e); /* 求e0的前驱 */

if(i==INFEASIBLE) printf(\元素%d无前驱\\n\ else printf(\元素%d的前驱为：%d\\n\ }

for(j=ListLength(L)-1;j<=ListLength(L);j++) /* 最后两个数据 */ { GetElem(L,j,&e0); /* 把第j个数据赋给e0 */ i=NextElem(L,e0,&e); /* 求e0的后继 */

if(i==INFEASIBLE) printf(\元素%d无后继\\n\ else printf(\元素%d的后继为：%d\\n\ }

k=ListLength(L); /* k为表长 */ for(j=k+1;j>=k;j--)

{ i=ListDelete(&L,j,&e); /* 删除第j个数据 */

if(i==ERROR) printf(\删除第%d个数据失败\\n\ else printf(\删除的元素值为：%d\\n\ }

printf(\依次输出L的元素：\

ListTraverse(L,visit); /* 依次对元素调用visit()，输出元素的值 */ printf(\的元素值加倍后：\

ListTraverse(L,dbl); /* 依次对元素调用dbl()，元素值乘2 */ ListTraverse(L,visit); DestroyList(&L);

printf(\销毁L后：L.elem=%u L.length=%d L.listsize=%d\\n\ getch(); }

五、实验报告要求

1、认真阅读和掌握本实验内容所给的程序。 2、将本实验上机运行。

3、结合运行结果，对程序进行分析。

实验三线性表的基本操作（2）--链表

一、实验目的

1、了解数据的逻辑结构和数据的存储结构之间的区别与联系； 2、掌握线性表的链式表示和实现方法，特别是插入、删除操作。 3、掌握运用C语言上机调试线性表的基本方法。

二、实验内容

1、建立一个类型为整型链接表的头文件和基本操作，特别是初始化操作、插入操作、删除操作、查找操作、遍历操作等。

2、创建有10个元素的线性链接表，验证插入、删除、查找操作的结果

三、实验步骤

在微型计算机上调试编写的程序，记录运行结果。

四、参考算法

#include #include

#define OVERFLOW -2 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0

#define INFEASIBLE -1

/* 定义ElemType为int类型 */ typedef int ElemType; typedef int Status;

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

struct LNode *next; }LNode,*LinkList;

void InitList(LinkList *L); /* 初始化单链表 */ void DestroyList(LinkList *L); /* 销毁单链表 */ void ClearList(LinkList L); /* 清空单链表 */

Status ListEmpty(LinkList L); /* 检查单链表是否为空 */

void ListTraverse(LinkList L,void(*vi)(ElemType)); /* 遍历单链表 */ int ListLength(LinkList L); /* 求单链表的长度 */

Status GetElem(LinkList L,int i,ElemType *e); /* 从单链表表中查找元素 */ /* 从单链表表中查找与给定元素值相同的元素在链表中的位置 */ int LocateElem(LinkList L,ElemType e);

Status ListInsert(LinkList L,int i,ElemType e); /* 向单链表中插入元素 */ Status ListDelete(LinkList L,int i,ElemType *e); /* 从单链表中删除元素 */

void InitList(LinkList *L)

{ /* 操作结果：構造一个空的線性表L */

*L=(LinkList)malloc(sizeof(struct LNode)); /* 產生头结點，並使L指向此头结點 */ if(!*L) /* 存儲分配失敗 */ exit(OVERFLOW);

(*L)->next=NULL; /* 指针域為空 */ }

void DestroyList(LinkList *L)

{ /* 初始條件：線性表L已存在。操作结果：销毁線性表L */ LinkList q; while(*L) {

q=(*L)->next; free(*L); *L=q; } }

void ClearList(LinkList L) /* 不改变L */

{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */ LinkList p,q;

p=L->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ {

q=p->next; free(p); p=q; }

L->next=NULL; /* 头结点指针域为空 */ }

Status ListEmpty(LinkList L)

{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */ if(L->next) /* 非空 */ return FALSE; else

return TRUE; }

int ListLength(LinkList L)

{ /* 初始条件：线性表L已存在。操作结果：返回L中数据元素个数 */ int i=0;

LinkList p=L->next; /* p指向第一个结点 */ while(p) /* 没到表尾 */ {

i++;

p=p->next; }

return i; }

Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */ int j=1; /* j为计数器 */

LinkList p=L->next; /* p指向第一个结点 */

while(p&&j < i) /* 顺指针向后查找，直到p指向第i个元素或p为空 */ {

p=p->next; j++; }

if(!p||j>i) /* 第i个元素不存在 */ return ERROR;

*e=p->data; /* 取第i个元素 */ return OK; }

int LocateElem(LinkList L,ElemType e) { /* 初始条件: 线性表L已存在 */

/* 操作结果: 返回L中第1个与e相等的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0 */ LinkList p=L->next; int j=1;

while(p->data!=e&&p->next) { p=p->next; j++; } }

Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) { /* 初始条件: 线性表L已存在 */

/* 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， /* 返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE */ LinkList q,p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ {

q=p->next; /* q为p的后继 */ if(q->data==cur_e) {

*pre_e=p->data; return OK; }

p=q; /* p向后移 */ }

return INFEASIBLE;

}

Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) { /* 初始条件：线性表L已存在 */

/* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */ /* 返回OK;否则操作失败，next_e无定义，返回INFEASIBLE */ LinkList p=L->next; /* p指向第一个结点 */ while(p->next) /* p所指结点有后继 */ { if(p->data==cur_e)

{ *next_e=p->next->data; return OK; }

p=p->next; }

return INFEASIBLE; }

Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改变L */ { /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j=0;

LinkList p=L,s;

while(p&&jnext; j++; }

if(!p||j>i-1) return ERROR;/* i小于1或者大于表长 */

s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */ s->data=e; /* 插入L中 */ s->next=p->next; p->next=s; return OK; }

Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改变L */ { /* 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 */ int j=0;

LinkList p=L,q;

while(p->next&&j< i-1) /* 寻找第i个结点，并令p指向其前岖 */ { p=p->next; j++; }

if(!p->next||j>i-1) /* 删除位置不合理 */ return ERROR;

q=p->next; /* 删除并释放结点 */ p->next=q->next; e=q->data; free(q);

共7页:

数据结构实验报告(3).doc 将本文的Word文档下载到电脑下载失败或者文档不完整，请联系客服人员解决！

下载这篇word文档