创建链表和链表操作实验报告

数据结构实验报告

报告名称 创建链表和链表操作 专 业 网络工程 班 级 1001 学 号 201003120129 姓 名 张剑 指导教师 陈淑红 李珍辉 黄哲

2012 年 5月 4日

一、实验目的：

掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、实验内容与基本要求：

实验内容：

1. 创建单链表

2．在链表上进行插入、删除操作；

3．设计一个程序，用两个单链表分别表示两个集合，并求出这两个集合的并集。

实验要求：

1． 在上机前写出全部源程序； 2． 能在机器上正确运行程序； 3． 用户界面友好；

三、概要设计：

1.单链表的存储结构： teypedef struct LNode{ ElemType date;

struct LNond *next; }LNode *LinkList;

2.单链表的插入操作：

Status ListTnsert-L(LinkLIst &L, int i, ElemType e ){

//再带头结点的单链线性表L中的第i个位置之前插入元素e P=l; j=0;

While(p&&jnext;++j;

}//寻找第i-1个结点

if(!p||j>i-1) return ERROR; //i小小于1或者大于表长+1 s=(LinkList) malloc (sizeof(LNode)); //生成新结点 s->date=e; s->next=p->next; //插入L中 p->next=s; return ok;

}//ListTnsert L

3.单链表的删除操作：

Status ListDelete-L(LinkLIst &L, int i, ElemType &e ){

//在带头结点单链线性表L中，删除低i个元素，并由e 返回其值 p=l; j=0;

while(p->next&&jnext; ++j; }

if(!(p->next)||j>i-1)

return ERROR; //删除位置不合理

q=p->next ; p->next=q->next; //删除并释放结点 e=q->date free(q); return OK;

} //ListDelete-L

4.链表的合并操作：

void MergeList-L(LinkList &La, LinkList &Lb, LinkList &Lc){ // 已知单链表La和Lb的元素值

//合并单链表La和Lb，得到新的单链表Lc pa=La->next; pb=Lb->next;

lc=pc=La; //用La的头结点作为Lc的 头结点 while(pa&&pb){ if(pa->date<=pb->date){

pc->next =pa; pc=pa; pa=pa->next; }

else {pc->next=pb;pc=pb;pb=pb->next;} }

Pc->next=pa? pa:pb; //插入剩余段 free(Lb); //释放Lb 头结点

} //MergeList-L 四、详细设计：

#include #include #include #include typedef int status;

typedef char ElemType; typedef struct Lnode {ElemType data;

//定义链表结点类型

struct Lnode *next; }Lnode,*Linklist;

status initlist(Linklist *L) { //单链表的初始化 *L=(Lnode *)malloc(sizeof(Lnode)); //创建头结点 (*L)->next=NULL; return 1; }

status Createlist(Linklist L) { Lnode *p,*q; int i,j=1,n;

ElemType m,M; q=L;

printf(\请输入你要输入单链中元素的个数\\n\ scanf(\ scanf(\ for(i=n;i>0;i--)

{p=(Lnode *)malloc(sizeof(Lnode)); printf(\请输入%2.1d个元素:\ scanf(\ scanf(\ p->data=M;

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

return 1; }

status Listinsert(Linklist L,int i,ElemType e) { int j=0;

Lnode *p=L,*s; while(p&&jnext; ++j; }

if(!p||j>i-1){printf(\输入错误!\\n\ return 0; }

s=(Lnode *)malloc(sizeof(Lnode)); s->data=e;

//创建自己规定长度的单链表 //回车缓冲区 //回车缓冲区 //向单链表指定位置插入一个元素 s->next=p->next; p->next=s; return 1; }

status Listdelete(Linklist L,int i,ElemType *e) { //删除单链表指定位置的元素,返回删除后的。链表元素 Lnode *p,*q; int j=0; p=L;

while(p->next&&jnext; j++; }

if(!(p->next)||j>i-1){printf(\输入错误!\\n\ return 0; } q=p->next;

p->next=q->next; *e=q->data; free(q); return 1; }

void print(Linklist L) { //输出单链表中的元素 Linklist p; p=L->next;

printf(\输出单链表：\\n\ while(p!=NULL)

{printf(\ p=p->next; }

printf(\ }

struct Lnode * inter_link(struct Lnode * chain1, int a, struct Lnode * chain2, int b) { //单链表的合并 int temp;

struct Lnode *head, *p1, *p2, *p3; //判断a，b大小并合并 if (a >= b) {

head = p1 = chain1; p2 = chain2; }