线性表的基本操作

实验一线性表的基本操作

一、实验目的

学习掌握线性表的顺序存储结构、链式存储结构。设计顺序表的创建、插入、

删除等基本操作，设计单链表的建立、插入、删除等基本操作。

二、实验内容

L顺序表的实践

（1）顺序表的创建：基于顺序表的动态分配存储结构，创建一个顺序表S,

初始状态S=（l,2,3,4,5）o

（2）顺序表的遍历：依次输出顺序表的每个数据元素。

（3）顺序表的插入：在顺序表S=（l,2,3,4,5）的数据元素4和5之词插

入一个值为9的数据元素。

（4）顺序表的删除：顺序表S=（l,2,3,4,9,5）中删除指定位置（i=3）

的数据元素3。

（5）顺序表的按值查找：查找顺序表S中第1个值等于4的数据元素位序。

（6）顺序表的清空：释放顺序表的存储空间。

2.单链表的实践

（1）单链表的创建：创建一个包括头结点和4个元素结点的单链表L=（5,

4,2,Do

（2）单链表的遍历：依次输出顺序表的每个数据元素。

（3）单链表的取值：输出单链表中第i个（i=2）数据元素的值。

（4）单链表的插入：在已建好的单链表的指定位置（i=3）插入一个结点3。

（5）单链表的删除：在一个包括头结点和5个结点的单链表匕二（5,4,3,

2,1）中，删除指定位置（i=2）的结点，实现的基本操作。

（6）求单链表的表长：输出单链表的所有元素和表长。

（7）单链表的判空：判断单链表是否为空表。

（8）单链表的清空：释放单链表的存储空间。

三、程序源代码

1.线性表的基本操作

#include<ioslream>

#includc<stdlib.h>

usingnamespacestd;

#dcfineOK1

#defineOVERFLOW-2

#dcfineERROR0

#defineLIST_INIT_SIZE100

#dcfineLISTINCEREMENT10

typedefintStatus;

typedefintElemtype;

typedefElemtype"Triplet;

typedefstruct{〃定义结构体类型：顺序表

Elemtype*elem;

intlength;

intlistsize;

}Sqlist;

StatusInitlist(Sqlist&L){//

intn,i;

L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));

if(!L.elem){

return(OVERFLOW);

}

cout«”输入元素个数和各元素的值:"；

cin»n;

for(inti=0;i<n;i++){

cin»L.elem[i];

)

L.length=n;

L.listsize=LIST_INIT_SIZE;

returnOK;

)

StatusTraverList(SqlistL){

for(inti=();i<L.length;i++){

cout«L.elem[i]«"

cout«endl;

StatusListinsert(Sqlist&L,inti,Elemtypee){〃插入

Elcmtypc*ncwbasc,*p,*q;

if(i<l||i>L.length+l)returnERROR;//i不合法

if(L.length>=L.listsize){〃需要重新分配存储空间

newbase=(Elemtype*)reailoc(L.elem,(L.listsize+LISI'INCEREMEN1)

*sizeof(Elemtype));

if(!newbase)exit(OVERFLOW);//分配失败

L.elem=newbase;

L.listsize+二LISTINCEREMENT;

I

q=&(L.elem[i-ll);

for(p=&(L.clcm[L.length-1J);p>=q;—p)

*(p+l)=*p；

*q=e;

++L.length;

returnOK;

)

StatusListDclctc(Sqlist&L,inti,Elcmtypc&c){〃删除

Elemtype*p,*q;

if((i<1)||(i>L.length))returnERROR;

p=&(L.elem[i-l]);

e=*p;

q=L.elem+L.length-1;

for(++p；p<=q;++p)

*(p-l)=*p;

-L.length;

reluniOK;

)

StatusLocateElem(SqlistL,Elemtype&e){〃查找

inti;

Elemtype*p;

i=l；

p=L.elem;

while(i<=L.length&&*(p++)!=e)++i;

if(i<=L.length)returni;

elsereturn0;

StatusClearList(Sqlist&L){

frcc(L.clcm);

cout<<”该表已被清空！”；

returnOK;

)

intmain(){

SqlistL;

inti,z;

Elemtypee;

if(Initlist(L)==OVERFLOW){

cout«endl«"OVERFLOW”；

return0;

)

TraverList(L);

while(I){

cout«"-------------------"«endl;

coutvv"选择要执行的基本操作:n«endl«”1:插入元素"<<endl

«"2.删除元素"v<endl«”3.查找元素”<<endl

«“4.退出“vvendl;

cin»z;

switch(z){

case1:

cout«"输入要插入元素的位置和值："«endl;

cin»i»e;

if(ListInsert(L,i,e)==OK)

TidverLisl(L);

else

cout«"插入的位置不合法。"<<endl;

break;

case2:

cout«”输入要删除元素的位置："<<endl;

cin»i;

if(ListDelete(L,i,e)==OK){

TraverList(L);

cout«”删除的元素值为：”<ve«endl;

}else(

cout«”删除的位置不合法。“<<cndl;

}

break;

case3:

cout<<”输入要查找元素的值："<<endl;

cin»e;

if(LocateElem(L,e)){

cout«"该元素的位置是第"<<LocateElem(L,e)

<<"位"<vendl;

}else(

cout«"该元素不存在!n«cndl;

)

case4:

cout«”操作结束"<<endl;

ClearList(L);

exit(O);

default:

cout<<”选择有误，请重新选择！n«endl;

}

)

)

2.链表的基本操作

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<algorilhm>

#include<cstdio>

#defineOVERFLOW-2

#defineOK1

#defineERROR0

#defineTRUE1

#defineFALSE0

#defineINFEASIBLE-1

#defineLIST_INIT_SIZE100

#defineLISTINCREMENT10

usingnamespacestd;

typedefintStatus;

typcdcfintElcmTypc;

typedefstructLNode{

ElemTypedata;

structLNode*next;

}LNode,*LinkList;//LNode结构体类型别名，LinkList结构体指针别名

StatusInitLNode(LinkList&L){

〃初始化链表，n个元素，线性表长度为n

intn,i;

LinkListp,r;

L二(LinkList)malloc(sizeof(LNode));//动态申请一个结点(头节点)

if(!L)

returnOVERFLOW;

L->next=NULL;

r=L;

cout«”输入元素人数和各元素的值;

cin»n;

for(i=0;i<n;i++){

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

cin»p->data;

r->next=p;

尸P；

)

r->next=NULL;

returnOK;

}//InitLNode

voidLislDisp(LinkLislL){

//遍历单链表，依次输出各元素

LinkListp;

p=L->next;

cout«endl«"TheLinkListL:"«endl;

〃依次访问L的每一个结点，直到结尾

whi!e(p!=NULL){

cout«p->data«"

p=p->next;

cout«endl;

}//ListDisp

StatusGctElcm(LinkListL,inti,ElcmTypc&c){

〃单链表取值，用e返回L第i个元素的值

LinkListp;

intj=l;

p=L->next;//p指针初值：NULL取值指向第一个元素的值

while(p&&j<i){

p=p->next;

++j；

I

〃若p为空未找到，j>i(i值不合法)，取值错误返回ERROR

returnERROR;

e=p->data;

returnOK;

)//GetElem

StatusListInsert(LinkList&L,inti,ElemTypee){

〃往单链表L中第i个位置之前插入新的元素e

LinkListp,s;

intj=O;

P=L;

while(p&&j<i-l){

p=p->next;

++j；

)

reluniERROR;

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

s->data=e;

s->next=p->next;//1

p->next=s;〃2,顺序不能变

returnOK;

}//ListInsert

StatusListInse(LinkList&L,inli,ElemType&e){

//删除单链表L中第i个元素，用e返回其值

LinkListp,q;

intj;

p=L;

j=0；

while(p->next&&j<i-l){

p=p->next;

++j；

)

if(!(p->next)|[j>i-l)

returnERROR;

q=p->next;

p->next=q->next;

e=q->data;

frcc(q);

returnOK;

(//Listlnse

StatusListLength(LinkListL){

//求链表长度

LinkListp;

inti=0;

p=L->next;

while(p!=NULL){

i++；

p=p->next;

)

returni;

(//ListLength

StatusLNodeEmpty(LinkListL){

〃若单链表L为空表返回TRUE,否则返回FALSE

if(L->next=NULL)

returnTRUE;

else

returnFALSE;

}//LNodeEmpty

StatusClearList(LinkList&L){

〃清空单链表

LinkListp;

p=L->next;

while(p!=NULL){

L->next=p->next;

frcc(p);

p=L->next;

)

)//ClearList;

intmain(){

LinkListL;

inti,s;

ElemTypee;

InitLNode(L);

if(ListLength(L)==O){

ListDisp(L);

coutvv”表为空。"vvendl;

return0;

}

while(l){

cout«"-------------------"«endl;

cout<v”选择操作："<<endl<v"1:输出某个元素的值；n«endl

«"2.在某个元素之前插入一个元素v<endl

«"3.删除某个元素;”《endl

<<"4.输出链表中的元素及其长度;“<<endl«”5.退出“<<encU;

cin»s;

switch(s){

case1:

cout«”输入要查找元素的位置：”；

cin»i;

if(!GelElem(L,i,e))

cout<<"该元素不存在！endl;

else

cout«"第“vvi«”个元素的值是：°«e«endl;

break;

case2:

cout«”输入要插入元素的位置和值：“；

cin»i»e;

cout«"当前链表的所有元素为："<<endl;

if(LislJnsert(L,i,e)==OK)

ListDisp(L);

else

cout«"插入的位置不合法。"<<endl;

break;

case3:

cout<〈”输入耍删除元素的位置：”；

cin»i;

if(Listlnse(L,i,e)==OK){

cout«”删除的元素值为：”=e«endl;

coutv<”当前链表的所有元素为："<<endl;

ListDisp(L);

}else(

cout«"删除的位置不合法。"vvcndl;

)

break;

case4:

cout当前链表的所有元素为："vvendl;

ListDisp(L);

cout«”链表的长度为:"«ListLcngth(L)«cndl;

break;

case5:

cout«”操作结束!”vv”该表己被清空!u«endl;

ClcarList(L);

exit(O);

default:

coul<<"选择有误，请重新选择！"<<endl;

)

}

)

四、程序运行结果

1、顺序表的实践，运行结果如下:

■'DM）附码供通1.1RS52O3□

扇入兀素个数和各•兀4（的他:6

25769

25769

它扑夔执行的几本排作:

:插入元洲

,删除元素

.任找元太

.退出

渝入要插入元束的位置和他:

I2

>125769

£择要执行的疆本操作:

:插入元家

.删除元索

合找元不

.退出

确入要则除无求的位置:

63

212579

剂除的元索值为：6

当杆要执行的基本掾作:

:插入元水

.刷除元案

.传找无索

■O:\OM弋码供/1.1W«203出存exe

J.「HE兀东

I.退出

无拧仃俣.请麻新选拧!

要

抨

插

则

A/曲

ft曲

退

出

畲入要插入兀术的位置和值:

>6

*36866

选择要执行的几本撒作:

1:插入元上

2.捌除元本

3.件找元案

4.退出

案作结束

攵衣L1被清空!

exitedafter14.06secondswithreturnvalue0

2、单链表的实践，运行结果如下：

IF'D:\OHti5\55tt1.2nS203tt*W：.exe-□X

择

操

作

・

・

辎

米

的值

某

出4:

人

花

之

个

某

而

插

刑

术

某

除

;及

木

输

的

元

退fit

11出]

殆入变A我元东的位JE；5

谈元术小7"E!

选择操作：

1:输出某个元素的值:

2.住某个元案之赭捅入一个元索;

3.删除某个元素；

4.输出铳衣中的元素及其长收：