当前位置：文档之家› 实验三、线性表的链式存储

实验三、线性表的链式存储

实验二线性表的链式存储

实验目的：

●掌握线性表的链式存储结构的定义及C语言实现

●掌握单链表中的各种基本操作（单链表的建立、合并、删除等）实验内容：

1、单链表的建立及输出(插入)

参考代码：

/*保存在头文件Linklist.h*/

#include

#define NULL 0

typedef int Elemtype;

typedef struct Lnode{

Elemtype data;

struct Lnode *next;

}Lnode,*Linklist;

//使用尾插法创建单链表

void creatlist_L(Linklist L,int n)

{

int i;

Linklist p,q;

q=L;

for(i=1;i<=n;i++)

{

p=(Linklist)malloc(sizeof(Lnode)); printf("输入线性表的第%d个元素：",i); scanf("%d",&p->data);

p->next=q->next;

q->next=p;

q=q->next;

}

//使用头插法创建单链表

void creatlist_L(Linklist L,int n)

{

int i;

Linklist p;

p=L;

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

{

p=(Linklist)malloc(sizeof(Lnode));

printf("输入线性表的第%d个元素：",i);

scanf("%d",&p->data);

p->next=L->next;

L->next=p;

}

void traverlist_L(Linklist head)

{

Linklist p;

printf("以head 为头指针的单链表中的元素为："); p=head->next;

while(p!=NULL)

{

printf("%5d ",p->data);

p=p->next;

}

printf("\n");

}

#include

void main()

{

Linklist head;

int n;

printf("********建立一个单链表中的操作******\n");

printf("输入要建立链表的长度：");

scanf("%d",&n);

head=(Linklist)malloc(sizeof(Lnode));

head->next=NULL;

creatlist_L(head,n);

printf("\n********输出单链表中元素*****\n");

traverlist_L(head);

}

2、单链表的查找

创建一个单链表，编写单链表的查找函数，实现单链表的查找。

int Getelem(Linklist L,int i,Elemtype &e)

{

int j;

Linklist p;

p=L->next;

j=1;

while(p&&j

{

p=p->next;

++j;

}

if (!p||j>i)

return NULL;

e=p->data;

return e;

}//按序查找

void Getelem(Linklist L,Elemtype e)

{

Linklist p;

p=L->next;

while(p && p->data!=e)

{

p=p->next;

printf("\n查找成功！\n");

}

if (!p)

printf("\n查找失败！\n");

}

//按值查找

3、单链表的删除

创建一个单链表，编写函数实现单链表的删除操作。

void Listdelete(Linklist &L,int i)

{

Linklist p,q;

p=L;

int j=0;

while((p->next)&&(j

{

p=p->next;

++j;

}

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

printf("删除位置不合理，操作失败！");

else

{

q=p->next;

p->next=q->next;

delete q;

printf("删除成功！");

}

//删除指定位置的元素

4、有序单链表的合并

建立两个带头结点的有序单链表La，Lb（单调递增），利用La，Lb的结点空间，将La和Lb合并成一个按元素值递增的有序单链表Lc。

参考代码：

#include

void mergelist_L(Linklist La,Linklist Lb,Linklist &Lc)

{

InList(Lc);

int i,j,k,La_len,Lb_len,e,ai,bj;

i=j=1;

k=0;

La_len=ListLength(La);

Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len))

{

ai=GetElem(La,i,ai);

bj=GetElem(Lb,j,bj);

if(ai<=bj)

{

ListInsert(Lc,++k,ai);

++i;

}

else

{

ListInsert(Lc,++k,bj);

++j;

}

while(i<=La_len)

{

ai=GetElem(La,i++,ai);

ListInsert(Lc,++k,ai);

}

while(j<=Lb_len)

{

bj=GetElem(Lb,j++,bj);

ListInsert(Lc,++k,bj);

}

void main()

{

Linklist La,Lb,Lc;

int n1,n2;

La=(Linklist)malloc(sizeof(Lnode));

La->next=NULL;

printf("******两个单链表的合并操作******\n");

printf("\n请输入要建立的链表La的长度：");

scanf("%d",&n1);

creatlist_L(La,n1);

printf("\n******输出链表La中元素******\n");

traverlist_L(La);

Lb=(Linklist)malloc(sizeof(Lnode));

Lb->next=NULL;

printf("******两个单链表的合并操作******\n");

printf("\n请输入要建立的链表Lb的长度：");

scanf("%d",&n2);

creatlist_L(Lb,n2);

printf("\n******输出链表Lb中元素******\n");

traverlist_L(Lb);

printf("\n******下面执行合并操作******\n");

Lc=La;

mergelist_L(La,Lb,Lc);

printf("\n******输出由链表La和Lb归并所得新的链表Lc中的元

素******\n");

traverlist_L(Lc);

}

5、已知带头结点的单链表L中的结点是按整数值递增排列。试写一个算法，将

值为x的结点插入到表L中，使得L仍然有序。分析算法的时间复杂度。

void Insert(Linklist L,int x)

{

Linklist p,q;

p=L->next;

q=L;

while(p&&p->data

{

q=p;

p=p->next;

}

p=(Linklist)malloc(sizeof(Lnode));

p->data=x;

p->next=q->next;

q->next=p;

}

6、线性表的合并

有两个集合A 和B 分别用线性表LA 和LB 表示，即：线性表中的数据元素为集合中的成员。现求一个新的集合A＝A∪B。（线性表任选一种存储方式）

void Union(Linklist &La,Linklist Lb)

{

int i,La_len,Lb_len,e;

La_len=ListLength(La);

Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++)

{

e=GetElem(Lb,i,e);

Insert(La,e);

}

实验总结：

1.头插法创建单链表

2.单链表的查找

3.单链表的删除

4.有序表中插入元素

5.（4-5）有序链表的合并和两个集合的合并

数据结构实验报告实验一线性表链式存储运算的算法实现

昆明理工大学信息工程与自动化学院学生实验报告（201 —201 学年第一学期）课程名称：数据结构开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称线性表链式存储运算的算法实现指导教师教师评语教师签名：年月日一.实验内容：线性表链式存储运算的算法实现，实现链表的建立、链表的数据插入、链表的数据删除、链表的数据输出。二.实验目的： 1.掌握线性表链式存储结构的C语言描述及运算算法的实现； 2.分析算法的空间复杂度和插入和删除的时间复杂度； 3.总结比较线性表顺序存储存储与链式存储的各自特点。三.主要程序代码分析： LinkList creatListR1() //用尾插入法建立带头结点的单链表 { char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode)); //生成头结点*head ListNode *s,*r,*pp; r=head; //尾指针初值指向头结点 r->next=NULL; scanf("%s",ch); //读入第一个结点的值 while(strcmp(ch,"#")!=0) { //输入#结束

pp=LocateNode(head,ch); if(pp==NULL) { s=(ListNode *)malloc(sizeof(ListNode)); //生成新的结点*s strcpy(s->data,ch); r->next=s; //新结点插入表尾 r=s; //尾指针r指向新的表尾 r->next=NULL; } scanf("%s",ch); //读入下一个结点的值 } return head; //返回表头指针 } int Insert(ListNode *head) //链表的插入 { ListNode *in,*p,*q; int wh; in=(ListNode *)malloc(sizeof(ListNode));in->next=NULL; //生成新结点p=(ListNode *)malloc(sizeof(ListNode));p->next=NULL; q=(ListNode *)malloc(sizeof(ListNode));q->next=NULL; scanf("%s",in->data); //输入插入的数据 scanf("%d",&wh); //输入插入数据的位置 for(p=head;wh>0;p=p->next,wh--); q=p->next; p->next=in; in->next=q; } void DeleteList(LinkList head,char *key) //链表的删除 { ListNode *p,*r,*q=head; p=LocateNode(head,key); //按key值查找结点的 if(p==NULL) exit(0); //若没有找到结点，退出 while(q->next!=p) //p为要删除的结点，q为p的前结点q=q->next; r=q->next; q->next=r->next; free(r); //释放结点*r } 四.程序运行结果：

线性表实验报告：针对链式或顺序存储的线性表实现指定的操作(二份)

、格式已经给出，请同学们参考书写。其中，第一项可补充，第二、三项不修改，第四项为可选项，第六项为参考程序，第五、七、八项需自己上机调试程序书写。注意：红色字体为提示内容，大家不要往实验报告上抄。实验一:线性表的顺序存储结构的表示和实验 ——学生成绩管理系统一、实验目的：通过上机调试程序，充分理解和掌握有关线性表的定义、实现及操作。二、实验环境 Win2003/win xp +Visual C++ 三、基本要求：利用顺序表来制作一个学生成绩表 1、建立头文件，包含数据类型定义和基本操作。 2、建立程序文件利用顺序表表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。四、简要的需求分析与概要设计（本项为可选项，选作时参考课

五、详细的算法描述：六、实验步骤（以下为参考程序，已经调试运行通过）#include #include using namespace std; const int LISTINITSIZE=100; const int LISTINCREMENT=10; struct student { char no[20];

char name[20]; int english; int math; }; typedef student elemtype; struct sqlist { elemtype *elem; int length; int listsize; int incrementsize; }; //初始化顺序表l void initlist(sqlist &l,int maxsize=LISTINITSIZE,int incresize=LISTINCREMENT) { l.elem=new elemtype[maxsize]; l.length=0; l.listsize=maxsize; l.incrementsize=incresize;