当前位置：文档之家› 中国石油大学数据结构上机实验2

中国石油大学数据结构上机实验2

《数据结构》实验报告

学号2015011512 姓名胡明禹专业数学与应用数学时间2018320

一、实验题目

实验2单链表基本操作

二、实验目的

1.熟练掌握线性表的顺序存储方式下，基本操作的实现算法，巩固和

体会单链表操作特点；

2.理解体会动态内存申请与释放；

3.通过本次实验，熟练掌握C语言指针的使用

三、算法设计分析

(一)实验内容

1.创建一个空的带头结点的单链表

2.采用头插法在单链表中插入n个元素

3.删除单链表中第i个元素

4.实现单链表按关键字查找操作

5.计算单链表的表长并输出单链表

6.销毁单链表

(二)总体设计

此处给出主要函数功能、及函数间调用关系的的描述。例如：

1.构造一个空的单链表的函数；

2.插入函数；

3.删除函数

4.查找函数；

5.计算并输出函数；

6.销毁函数。

其功能描述如下：

(1 )主函数：统筹调用各个函数以实现相应功能

void mai n()

(2)

①构造一个空的单链表的函数

Status In itList_L(Li nkList &L)

{

L=(LinkList)malloc(sizeof(LNode));// 构造一个空的线性表L f(!L) exit (OVERFLOW);// 存储分配失败

L->next=NULL;〃空表长度为Osystem("cls");〃清空屏幕printf("\n\n 初始化成功\n\n\n"); system("PAUSE");〃按任意键继续

return OK;

}

void CreateList_L(LinkList &L)

{// 创建一个新表

int i,count;

LinkList p;

system("cls");// 清屏

printf("\n 输入总结点数:");

scanf("%d",&count);

printf("\n 输入各个结点数值，每输一个按下回车：\n");

for(i = count; i > 0; i--)

{

p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data);

p->next = L->next;

L-> next = p;〃赋值

}

system("cls");// 清屏

printf("\n 录入成功\n");

}

②插入函数

Status ListInsert_L(LinkList &L, int i, int newnode)

{// 在顺序线性表L 中第i 个位置之前插入新的元素

LinkList p = L;

LinkList s;

int j = 0;

while(p&&j

{

p = p->next;

++j;

}

if(!p||j>i-1)//i 插入的位置不合法

{

printf("error\n");

}

s = (LinkList)malloc(sizeof(LNode));

s->data = newnode;

s->next = p->next;// 将p 的后继结点给s 的后继结点p->next = s;// 将s 给p 的后继结点return OK;

}

③删除函数

Status ListDelete_L(LinkList &L, int i)

{//在顺序线性表L中删除第i个元素，并用e返回其值

LinkList p=L;

LinkList q;

int j=0;

while(p->next&&j

{

p = p->next;

++j;

}

if(!(p->next)||j>i-1) return ERROR;// 删除位置非法q= p->next;// 将p 的后继结点给q

p->next = q->next;// 将q 的后继结点给p 的后继结点printf("\n\n 删除成功\n\n 被删除的结点是：%d\n",q->data); free(q);

return OK;

}

④查找函数

Status FindElemList_L(LinkList &L)

{// 单链表按照关键字查询

LinkList p;

int i=1,NUMBER;

int n=0;

p = L->next;

printf("\n 输入查询数字：");

scanf("%d",&NUMBER);

while(p)

{

if(p->data==NUMBER)

{printf("\n 查询成功！该数字位于结点%d\n",i);

n++;

}

p = p->next;

i++;

}

if(!n)

{printf("\n 查询失败！未找到该元素！\n");

}

return OK;

}

⑤计算并输出函数

Status PrintList_L(LinkList &L)

{// 输出链表

m=0;

LinkList p;

p=L;

printf("\n");

while(p->next!=NULL)// 当链表非空

{

p=p->next;

printf("%d: %d\n",++m,p->data);// 输出

}

printf("\n");

return OK;

}

⑥销毁函数

Status DestroyList_L(LinkList &L) // 销毁单链表{ LinkList p, q;

p=L;

while(p)

{

q=p;

p=p->next;

free(q); // 释放

}

if(p==NULL)

printf("\n 成功，请退出\n\n");

else

printf （” 失败 \n"）;

return OK;

}

四、实验测试结果及结果分析

（一）测试结果（此处给出程序运行截图）

'D:\Microsoft Visual Studio\Common\MSDev98\Bin\Debug\hmy_3 27nexe'

入成功

希

W'.

羊

.:-*;

辛

吊

fi:

单

—

c*i3

冷

】

2默#欲譎

值：9

?'O A IA^OW H Vnual Stu4?o\Com?i^rAM$0?vW^rAD<^u9\hn?yJ.2?.ex,

■ ' ?WMcp'S V HIO I JwdoXQnvrcrAMSO^v^VBAQ^bvgfmy,

業单

?<>

歩

兀

奠

单

屢

—

年％去的去长为，7 请祐儀泄注???1

J 1

5 门7 ￡ 4Z 人

人障

2r 4

u *j 6x a ? ? ?0\Mig5e 々、“2 女u￡*OE?M \M5De*^2"d>e0jaE

谓捜衽苜槌熨冬??? 7 6 L

4 9 2

匝内，诵怎出

清馬任社情辭紈?■

!? ■D H \ME M H 七畔叽|细6占说“血射衬翻、伯e 翱诃津《jwbuqmb 」￡T ?Ee"

（二）结杲分析成功完成了题冃所要求的插入，删除，查找等基本操作。

五、实验总结

附录实验程序代码（该部分请加注释）

#in elude "stdio.h" #inelude "stdlib.h"

#in elude "malloe.h"

#defi ne MAX 1000

#defi ne OVERFLOW -2

#defi ne OK 1

#defi ne ERROR 0 int m=0;，

蹙

匸匕

”甲」

?if-X-“呼.'F L2-.3.

也5.

ft.7.d 9

如 ■ 'UrMc -usp+l 'Vrs.uJ SludH^'^irrni-icr- MbOrWBi _'>UrtiJU hhT ：. -■-

mH?.诗

仁

宁

1!.1!已卞k'-: 亠尢

-r r1T -:l ?K.*

事.* LLz 4-r ■ 6 ? .D.

typedef int ElemType;

typedef int Status;

typedef struct LNode

{

ElemType data; struct LNode *next;

}LNode, *LinkList;

Status InitList_L(LinkList &L)

{

L=(LinkList)malloc(sizeof(LNode));// 构造一个空的线性表L if(!L) exit (OVERFLOW);// 存储分配失败

L->next=NULL;// 空表长度为0 system("cls");// 清空屏幕printf("\n\n 初始化成功\n\n\n");

system("PAUSE");〃按任意键继续

return OK;

}

void CreateList_L(LinkList &L)

{// 创建一个新表

int i,count;

LinkList p;

system("cls");// 清屏printf("\n 输入总结点数:");

scanf("%d",&count);

printf("\n 输入各个结点数值，每输一个按下回车：\n"); for(i = count;

i > 0; i--)// 循环嵌套

p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next =

L->next;

L->next = p;// 赋值

} system("cls");// 清屏printf("\n 录入成功\n");

}

Status ListInsert_L(LinkList &L, int i, int newnode)

{// 在顺序线性表L 中第i 个位置之前插入新的元素LinkList p = L; LinkList s;

int j = 0; while(p&&jnext;

++j;

} if(!p||j>i-1)//i 插入的位置不合法

{ printf("error\n");

}

s = (LinkList)malloc(sizeof(LNode)); s->data = newnode;

s->next = p->next;// 将p 的后继结点给s 的后继结点p->next = s;// 将s 给p 的后继结点return OK;

}

Status ListDelete_L(LinkList &L, int i)

{//在顺序线性表L中删除第i个元素，并用e返回其值

LinkList p=L;

LinkList q;

int j=0;

while(p->next&&j

{

p = p->next;

++j;

}

if(!(p->next)||j>i-1) return ERROR;// 删除位置非法

q= p->next;// 将p 的后继结点给q

p->next = q->next;// 将q 的后继结点给p 的后继结点printf("\n\n 删除

成功\n\n 被删除的结点是：%d\n",q->data); free(q); return OK;

}

Status FindElemList_L(LinkList &L)

{// 单链表按照关键字查询

LinkList p;

int i=1,NUMBER;

int n=0;

p = L->next;

printf("\n 输入查询数字：");

scanf("%d",&NUMBER);

while(p)

{

if(p->data==NUMBER)

{printf("\n 查询成功！该数字位于结点%d\n",i);

n++;

p = p->next;

i++;

}

if(!n)

{printf("\n 查询失败！未找到该元素！\n");

}

return OK;

}

Status PrintList_L(LinkList &L)

{// 输出链表

m=0;

LinkList p;

p=L;

printf("\n");

while(p->next!=NULL)// 当链表非空

{

p=p->next;

printf("%d: %d\n",++m,p->data);// 输出

}

printf("\n");

return OK;

}

Status DestroyList_L(LinkList &L) // 销毁单链表{

LinkList p, q;

p=L;

while(p)

{

q=p;

p=p->next;

free(q); // 释放

}

if(p==NULL)

printf("\n 成功，请退出\n\n");

else

printf(" 失败\n");

return OK;

}

void mainmenu() // 输出菜单

{

printf(" \n 菜单");

printf(" \n ***********************\n\n") ;

printf(" * 1.建立单链表 *\n"); printf(" * 2.录入新元素 *\n"); printf(" * 3.插入新元素 *\n"); printf(" * 4.删除已有元素 *\n"); printf(" * 5.查找元素 *\n"); printf(" * 6.输出单链表 *\n"); printf(" * 7.销毁线性表 *\n"); printf(" * 0.退出 *\n"); printf("\n ***********************\n");

} void main() int choose,location,value;

LinkList L;

while(1)

{

mainmenu();

printf("\n 输入选择： "); scanf("%d",&choose); switch(choose)

{

case 1:

InitList_L(L);

system("cls");

break;

case 2:

CreateList_L(L);

PrintList_L(L); system("PAUSE"); system("cls"); break;

case 3:

system("cls");

PrintList_L(L);

printf(" 请输入插入位置 :"); scanf("%d", &location);

printf(" 请输入要插入的数值 :"); scanf("%d", &value); system("cls");

ListInsert_L(L,location,value);

PrintList_L(L); system("PAUSE"); system("cls"); break;

default:

printf("\n 输入错误，重新输入！\n"); case 4: system("cls");

PrintList_L(L);

printf("\n 请输入删除结点位置:"); scanf("%d",&location);

ListDelete_L(L,location);

PrintList_L(L); system("PAUSE"); system("cls"); break;

case 5: system("cls");

FindElemList_L(L);

PrintList_L(L); system("PAUSE"); system("cls"); break;

case 6: system("cls");

m=0;

PrintList_L(L);

printf("\n 单链表的表长为：%d\n\n",m); m=0;

system("PAUSE"); system("cls"); break;

case 7: system("cls"); DestroyList_L(L); system("PAUSE"); system("cls"); break;

case 0:

exit(0);

break;

}//case

}//while

}