单链表的基本操作

单链表的基本操作

实验一线性表的基本操作及其应用一、实验目的

1、帮助读者复习C语言程序设计中的知识。

、熟悉线性表的逻辑结构。2

3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操

作为侧重点。

二、实验内容

本次实验提供3个题目，每个题目都标有难度系数，*越多难度越大，学生

可以根据自己的情况任选一个〜

题目一:单链表的基本操作(*)

［问题描述］

实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等

单链表的基本操作。

［基本要求］

(1)依次从键盘读入数据，建立带头结点的单链表；

(2)输出单链表中的数据元素

(3)求单链表的长度；

(4)根据指定条件能够取元素和修改元素；

(5)实现在指定位置插入和删除元素的功能。【程序调试】

#include<malloc.h>/*malloc()等*/

#includo<stdio.h>/*scanf(),NULL*/#include<stdlib.h>/*free()

#include<conio.h>/*getch()*/

/*函数结果状态代码*/

#defineOK1

^defineERROR0

typedefintStatus;

typcdcfintElcmType;

typedefstructLNode

{

ElcinTypcdata;

structLNode*next;

}LNode,*LinkList;

voidCreateList(LinkList*L,intn)/*算法2.11*/

{/*逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L

inti;

LinkListp;

*L=(LinkList)malloc(sizeof(structLNode));

(*L)->next=NULL;/*先建立一个带头结点的单链表*/

printf(“请输入%d个数据\n”,n);

for(i=n;i>0;—i)

(

p=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/

scanf(，，%d/，,&p->data);/*输入元素值*/

p->next=(*L)->next;/率插入到表头*/

(*L)->next=p;

)

)

voidCreateList2(LinkList*L,intm)

{/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表L

inti;

LinkListp,q;

*L=(LinkList)malloc(sizcof(structLNode));/*生成头结点*/

(*L)->next=NULL;

q=*L；

printf("请输入%d个数据\n〃,m);

for(i=l;i<=m;i++)

(

p二(LinkList)malloc(sizeof(structLNode));

scanf&p->data);

q->next=p;

q=q->next;

}

p->next=NULL;

)

voidPrint1inklist(LinkListL)

LNode*p;

p=L->next;

while(p)

{printfp->data);

if(p->next)printf(*一>");

p=p->next;

)

printf(〃\n");

}

StatusListInsert(LinkListL,inti,ElemTypcc)/*算法2.9。不改变L

{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/

int尸0;

LinkListp=L,s;

while(p&&j<i-l)/*寻找第i-1个结点*/

(

p=p->next;

j++；

}

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

returnERROR;

s=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/

s->data=e;/*插入L中*/

s->next=p->next;

p->next=s;

returnOK;

}

StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改变

L*/

{/*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/

intj=0;

LinkListp=L,q;

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

(

p=p->next;

j++；

)

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

returnERROR;

q=p->next;/*删除并释放结点*/

p->next=q->next;

*e=q->data;

free(q);

returnOK;

}

intListlength(LinkList*L)//求链表长度{

LNode*p;〃链表的单个元素指针,而不能用链表intj=0;

p二L;〃将其指向链表的第一个元素

while(p->next!=NULL){

++j；

p=p->next;

)

returnj;

)

intGctElem(LinkListL,inti)

(

intj,e;

LinkListp=NULL;

if(i<l|i>Listlength(L))

(

prinlf(〃输入的位置不合法〜〜〜\n");

return;

}

p=L->next;

J=1；

while(j<i)

(

p=p->next;

j++；

)

e=p->data;

printf("第％d位的数据元素为%d\n〃，i,e);

voidmain()

inti,n,m,v,z;

LinkListLa,Lb;

ElemTypeel,e2;

printf(〃头插法逆位序建表\n〃)；

printf(〃请输入n值(即是链表长度)：〃);

scanf&n);

CreatcList(&La,n);/*逆位序输入n个元素的值*/

printf("La=〃)；/*输出链表La的内容*/

Printlinklist(La);

printf(〃\n");

printf(〃按尾插法正序建表：\n〃)；

printf("请输入m值(即是链表长度);

scanf&m);

CreateList2(&Lb,m);/*逆位序输入n个元素的值*/

printf(*Lb=");/*输出链表Lb的内容*/

Printlinklist(Lb);

printf(〃\n");

printf("输入在第一个链表插入的位置i=");

scanf("%d〃,&i);

printf(〃\n〃)；

printf(〃输入在第一个链表插入的元素el二〃)；

scanf(飞d”,&el);

printfC\nz,);

Listinsert(La,i,el);

printf(〃在第一个链表插入后La二〃)；/*输出链表La的内容*/

Printlinklist(La);

printf(〃\n〃)；

printf(〃按任意整数求第一个链表表长〃)；

scanf&v);

Listlength(La);

printf(〃第一个链表的长度为%d〃，Listlength(La));

printf(〃\n〃);

printf(〃在第一个链表中，请输入要取出的数的位置数〃)；

scanf("%d",&z);

GetElem(La,z);

printf("\n");

printf(〃在第一个链表中，输入删除的位置i二〃)；

scanf("机T,&i);

printf(〃\n");

ListDelete(La,i,&e2);

printf(〃删除后La=〃)；/*输出链表La的内容*/

Printlinklist(La);

printf(〃\n〃)；

printf("在第一个链表中,被删除的元素的值e2=%d\n',e2);

Listlength(La);

whiled);

)

【运行结果】

《胃”厅，>飞

*玷，6代<却石足&士传>4

i$>3A数显

2:怀719S24

尸2Sm->?«—>34>12

受总存叁型柠林&》;、

转入5不数据

9R4S3n6，

36一X、->23—>«

、在第一彳秘去香、的也5U-3

.不布一个3*.啬\内兀*7•5G

学4E八径入\J2、一》八一KG-