实验四 单链表及其应用(参考程序)_实验四单链表
实验四 单链表及其应用(参考程序)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验四单链表”。
实验四 单链表的建立
一、实验目的1.掌握线性表的链式存储结构——单链表的定义及C语言实现。2.掌握线性表在链式存储结构——单链表中的各种基本操作。
二、实验内容
1.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据分别按尾插入法和头插法来建立相应单链表。【知识要点】
为了便于实现各种运算，通常在单链表的第一个结点前增设一个附加结点，称为头结点，它的结构与表结点相同，其数据域可不存储信息，也可存储表长等附加信息，具体如下图。
【实验提示】
单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下：
typedef int datatype;
/* 线性表中存放整型元素 */ typedef struct LNode
/ * 结点类型定义 * /
{
datatype data;
/ * 数据域 * /
struct node *next;
/ * 指针域 * / }Linklist；
/* Linklist为单链表类型*/
注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：
p=(strcut LNode *)malloc(sizeof(Linklist));该语句的功能是申请分配一个类型为Linklist的结点的地址空间，并将首地址存入指针变量p中(或p=new(struct LNode);即生成新结点)。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。【程序提示】
#include typedef struct LNode{
//补充实现表节点类型的定义； } Linklist;
Linklist * creatlist(){ int x;Linklist *head, *p;// head为单链表的头指针，p指向新建的结点
//补充实现单链表的建立；
return(head);
// 函数返回链表头指针head }
void output(Linklist *HeadL){ if(HeadL->next==NULL)printf(“空链表!n”);else { printf(“链表为：n”);Linklist *P;P=HeadL->next;while(P!=NULL){
printf(“%d->”,P->data);P=P->next;} printf(“n”);}
}
void main(void){ Linklist *List;List=creatlist();output(List);} 【参考程序】
1、尾插法
#include typedef struct LNode{ int data;struct LNode *next;} Linklist;
Linklist * creatlist(){ int x;
Linklist *head, *p,*r;/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
r=head;
/* 尾指针的初值为头结点head */
printf(“请随机输入互不相同的正整数以0作为结束符:n”);
scanf(“%d”, &x);
/* 读入第一个结点的值 */
while(x!=0)
/* 输入数据，以0为结束符 */ { p=new(struct LNode);/* 生成新结点 */
p->data=x;
/* 给新结点的数据域赋值 */
r->next=p;
/* 新结点插入到表尾*rear之后 */
r=p;
/* 将尾指针rear指向新的尾结点 */
head->data++;
/* 链表长度计数 */
scanf(“%d”, &x);
/* 输入下一个结点的数据 */
}
r->next=NULL;
/* 将链表最后一个结点rear指针域置空 */
return(head);/* 函数返回链表头指针head */ }
void output(Linklist *HeadL){
if(HeadL->next==NULL)printf(“空链表!n”);else {
printf(“链表为：n”);
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
printf(“%d->”,P->data);
P=P->next;
}
printf(“n”);}
} void main(void){
Linklist *List;List=creatlist();output(List);}
2、头插法
#include typedef struct LNode{ int data;struct LNode *next;} Linklist;
Linklist * creatlist(){ int x;
Linklist *head, *p;/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
head->next=NULL;
printf(“n请随机输入一组正整数以0结束输入:n”);
scanf(“%d”,&x);
/* 输入第一个结点数据值 */
while(x!=0)
/* 输入数据，以0为结束符 */
{ p=new(struct LNode);/* 生成新结点 */
p->data=x;/* 给新结点的数据域赋值 */
p->next=head->next;
/* 将新结点插入表头结点head之后 */
head->next=p;
head->data++;
/* 链表长度计数 */
scanf(“%d”,&x);
/* 输入下一个结点的值 */
}
return(head);/* 函数返回链表头指针head */ }
void output(Linklist *HeadL){
} void main(void){
Linklist *List;List=creatlist();output(List);}
方法二 void main(void){
} 2.在第一题的基础上，增加单链表的查找，插入，删除子程序。#include #include“stdlib.h”
typedef struct LNode{ int data;struct LNode *next;Linklist *head,*p;head=creatlist();printf(“output the list:n”);p=head->next;while(p){ } printf(“%d ”,p->data);p=p->next;} Linklist;
Linklist * creatlist(){ int x;
Linklist *head, *p;
/* head为头指针 */
head=new(struct LNode);
head->data=0;
/* 表头结点数据域赋值 */
head->next=NULL;
cout
cin>>x;/* 输入第一个结点数据值 */
while(x!=0)
/* 输入数据，以0为结束符 */
{ p=new(struct LNode);/* 生成新结点 */
p->data=x;/* 给新结点的数据域赋值 */
p->next=head->next;
/* 将新结点插入表头结点head之后 */
head->next=p;
head->data++;
/* 链表长度计数 */
cin>>x;
}
return(head);} void output(Linklist *HeadL){
if(HeadL->next==NULL)cout
cout
Linklist *P;
P=HeadL->next;
while(P!=NULL)
{
coutdata";/* 函数返回链表头指针head */ /* 输入下一个结点的值 */
P=P->next;
}
cout
Linklist *p;int j;
p=head->next;
j=1;
/* 从首结点开始扫描 */
while((p!=NULL)&&(j
{ p=p->next;
/* 扫描下一个结点 */
j++;
}
if(i==j)return(p);
else return(NULL);
/* 若找不到，则返回空指针 */ } Linklist *data_insert(Linklist *head, Linklist *p, int x){
Linklist *s;
s =new(struct LNode);/* 建立新结点 */
s->data=x;
/* 将x值赋给s→data */
/* 统计已扫描结点的个数 */
s->next=p->next;/* 新结点s后继指向原p结点后继 */
p->next=s;
/* p结点的后继指向新结点s */
return(head);
/* 返回带头结点的单链表头指针*/ } Linklist *key_delete(Linklist *head, int x){
Linklist *p, *q;
/* p是被删除结点，q是p的前驱结点 */
p=head;
while((p!=NULL)&&(p->data!=x))
{
q=p;
p=p->next;
}
if(p!=NULL)
{
q->next=p->next;
/* 修改p前驱结点q指针域 */
/* 释放结点空间 */
/* 若该结点存在，则删除之 */
free(p);
return(head);
}
/* 函数返回链表头指针*/
else
{
cout
return(NULL);
} }
void main(void){
Linklist *List,*chazhao;List=creatlist();output(List);chazhao=no_search(List,2);//查找第二个节点，并输出数据域信息 coutdata;List=data_insert(List,chazhao,50);//在第二个节点后插入数据为50的节点 cout
output(List);List=key_delete(List,50);//删除数据为50的节点 cout
output(List);}
