数据结构上机第一次_1顺序表/单链表14个基本操作
题目
1．编程实现书P12 ADT List 基本操作14个：
（1） 用顺序存储结构实现； （2）用链式存储结构实现；
代码
（1）用顺序存储结构实现
//顺序存储结构14个基本操作
#include<iostream>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define PARA_ERROR 0
#define OVERFLOW -2
#define LISTINITSIZE 256 //初次分配空间大小
#define LISTINCREMENT 128 //空间分配增量大小
typedef int ElemType;
typedef int Status;
typedef struct Seqlist
{
ElemType *pdata; //动态存储空间的基地址
int length; //存储数据元素的个数
int size; //当前已分配的存储空间大小
}Seqlist;
//初始化、建立、销毁和清空操作
Status InitList(Seqlist &L)
{
//初始化顺序表
L.pdata=(ElemType*) malloc (LISTINITSIZE*sizeof(ElemType)); //申请存储空间
if(L.pdata==NULL)
exit (OVERFLOW); //存储空间申请失败
L.size=LISTINITSIZE;
L.length=0;
cout<<"初始化成功！"<<endl;
return OK;
}
Status CreateList(Seqlist &L)
{
//创建顺序表
cout<<"请输入顺序表长度：";
cin>>L.length;
cout<<"请输入顺序表元素：";
for(int i=0;i<L.length;i++)
{
cin>>L.pdata[i];
}
cout<<"顺序表建立成功！"<<endl;
return OK;
}
Status DestroyList(Seqlist &L)
{
//销毁顺序表
if(L.pdata!=NULL)
{
free (L.pdata);
L.pdata=NULL;
}
L.size=0;
L.length=0;
return OK;
}
Status ClearList(Seqlist &L)
{
//清空顺序表
L.length=0;
cout<<"清空完成！"<<endl;
return OK;
}
//访问型操作
bool ListEmpty(Seqlist L)
{
//空表返回TRUE
if(L.length==0)
{
cout<<"是空表"<<endl;
return true;
}
else
{
cout<<"不是空表"<<endl;
return false;
}
}
Status ListLength(Seqlist L)
{
//返回顺序表L的元素个数
return(L.length);
}
Status GetElem(Seqlist L, int i, ElemType &e)
{
//用参数e返回顺序表L中第i个元素的值
if(i<1||i>L.length) //参数检查
return PARA_ERROR;
e=L.pdata[i-1];
return OK;
}
Status LocateElem(Seqlist L, ElemType e)
{
//返回顺序表L中第一个与参数e相同的数据元素的位置
int flag=0;
for(int i=0;i<L.length;i++)
{
if(L.pdata[i]==e)
{
flag=1;
return i+1;
}
}
if(flag==0)
{
return 0; //查找失败
}
}
Status PriorElem(Seqlist L, ElemType cur_e, ElemType &pre_e)
{
//用pre_e返回cur_e的前驱元素
int location=0; //记录元素cur_e的位置
pre_e=-1;
location=LocateElem(L, cur_e);
while(location==0)
{
cout<<"该元素不存在！"<<endl;
break;
}
while(location==1)
{
cout<<"该元素是第一个元素"<<endl;
break;
}
while(location!=0&&location!=1)
{
pre_e=L.pdata[location-2];
return OK;
}
}
Status NextElem(Seqlist L, ElemType cur_e, ElemType &next_e)
{
//用next_e返回cur_e的后继元素
int location=0; //记录元素cur_e的位置
next_e=-1;
location=LocateElem(L, cur_e);
while(location==0)
{
cout<<"该元素不存在！"<<endl;
break;
}
while(location==L.length)
{
cout<<"该元素是最后一个元素"<<endl;
break;
}
while(location!=0&&location!=L.length)
{
next_e=L.pdata[location];
return OK;
}
}
Status ListTraverse(Seqlist L)
{
//遍历顺序表并依次输出其数据元素
for(int i=0; i<L.length; i++)
{
cout<<L.pdata[i]<<" ";
}
cout<<endl;
return 0;
}
//加工型操作
Status SetElem(Seqlist &L, int i, ElemType &e)
{
//将第i个元素的值用e替换，并将旧值用参数e返回
int t;
if(i<1||i>L.length+1)
return PARA_ERROR;
else
{
t=L.pdata[i-1];
L.pdata[i-1]=e;
e=t;
}
return e;
}
Status InsertElem(Seqlist &L, int i, ElemType e)
{
//在顺序表第i个位置上插入数据元素e
if(i<1||i>L.length+1)
return PARA_ERROR;
if(L.length==L.size) //当前存储空间已满，需增加存储空间
{
int*newbase=(ElemType*)realloc(L.pdata, (L.size+LISTINCREMENT)*sizeof(ElemType));
if(newbase==NULL)
exit(OVERFLOW);
L.pdata=newbase;
L.size+=LISTINCREMENT;
}
//从最后一个元素开始，直到下标为i-1的元素，依次向后挪一个位置
for(int j=L.length-1;j>=i-1;j--)
{
L.pdata[j+1]=L.pdata[j];
}
L.pdata[i-1]=e;
L.length+=1;
return OK;
}
Status DeleteElem(Seqlist &L, int i, ElemType &e)
{
//将顺序表第i个元素删除，并用e返回
if(i<1||i>L.length)
{
cout<<"不存在该位置！"<<endl;
return (0);
}
else
{
e=L.pdata[i-1];
//从第i个位置开始到最后一个元素，依次向前挪一个位置
for(int j=i; j<=L.length-1; j++)
{
L.pdata[j-1]=L.pdata[j];
}
L.length-=1;
return (1);
}
}
void menu()
{
//菜单
cout<<"1.初始化 2.建立"<<endl;
cout<<"3.销毁 4.清空"<<endl;
cout<<"5.判断空表 6.元素个数"<<endl;
cout<<"7.第i个元素值 8.找相同元素位置"<<endl;
cout<<"9.前驱 10.后继"<<endl;
cout<<"11.遍历输出 12.替换元素"<<endl;
cout<<"13.插入元素 14.删除元素"<<endl;
}
int main()
{
Seqlist L;
int choice;
int e,cur_e,pre_e,next_e,i=0;
while(1)
{
menu();
cout<<"请选择："<<endl;
cin>>choice;
switch(choice)
{
case(1):InitList(L);break;
case(2):CreateList(L);break;
case(3):DestroyList(L);break;
case(4):ClearList(L);break;
case(5):ListEmpty(L);break;
case(6):cout<<"顺序表长度为"<<ListLength(L)<<endl;break;
case(7):cout<<"要输出第几个元素的值？"<<endl;
cin>>i;
GetElem(L, i, e);
if(!GetElem(L, i, e))
cout<<"顺序表不存在第"<<i<<"个元素！"<<endl;
else
cout<<"第"<<i<<"个元素的值为"<<e<<endl;
break;
case(8):cout<<"请输入参数e:";
cin>>e;
if(LocateElem(L, e)==0)
{
cout<<"该元素不在顺序表内！"<<endl;
}
else if(LocateElem(L, e)!=0) cout<<"参数e的位置为"<<LocateElem(L, e)<<endl;
break;
case(9):cout<<"请输入参数e:";
cin>>cur_e;
PriorElem(L, cur_e, pre_e);
while(pre_e!=-1)
{
cout<<"e的前一个元素为"<<pre_e<<endl;
break;
}
break;
case(10):cout<<"请输入参数e:";
cin>>cur_e;
NextElem(L, cur_e, next_e);
while(next_e!=-1)
{
cout<<"e的后一个元素为"<<next_e<<endl;
break;
}
break;
case(11):ListTraverse(L);break;
case(12):cout<<"请输入要替换的元素位置:";
cin>>i;
cout<<"请输入新的元素值:";
cin>>e;
cout<<"替换成功！原元素值为"<<SetElem(L, i, e)<<endl;
break;
case(13):cout<<"请输入要插入的位置:";
cin>>i;
cout<<"请输入元素值:";
cin>>e;
InsertElem(L, i, e);
cout<<"插入成功！"<<endl;
break;
case(14):cout<<"请输入要删除的元素位置:";
cin>>i;
while(DeleteElem(L, i, e))
{
cout<<"删除成功！被删除的元素值为"<<e<<endl;
break;
}
break;
}
}
}
（2）用链式存储结构实现
//链式存储结构14个基本操作
#include<iostream>
#include<stdlib.h>
#include<malloc.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define PARA_ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
Status InitList(LinkList &L)
{
//1初始化单链表
L=(LNode*) malloc (sizeof(LNode)); //申请头结点存储空间
if(L==NULL) exit(OVERFLOW); //存储空间申请失败
L->next=NULL;
cout<<"初始化成功！"<<endl;
return OK;
}
Status ListLength(LinkList L)
{
//6单链表长度
int n=0;
LNode *p;
p=L->next;
while (p)
{
n++;
p=p->next;
}
return(n);
}
Status InsertElem(LinkList &L, int i, ElemType e)
{
//13在第i个位置插入e
LNode *s=(LNode*)malloc(sizeof(LNode)); //申请新的节点s
if(s==NULL) exit(OVERFLOW); //申请节点失败
s->data=e;
LNode *p;
p=L->next;
if(i==1)
{
s->next=p;
L->next=s;
}
else if(i>1&&i<=ListLength(L))
{
for(int j=0;j<i-2;j++)
{
p=p->next;
}
s->next=p->next;
p->next=s;
//ListLength(L)=ListLength(L)+1; ??????????????
}
else if(i==ListLength(L)+1)
{
for(int j=0;j<i-2;j++)
{
p=p->next;
}
p->next=s;
s->next=NULL;
}
else
{
cout<<"表中没有该位置！"<<endl;
}
return OK;
}
Status CreateList(LinkList &L)
{
//2建立单链表
int i,len=0;
ElemType e;
cout<<"请输入单链表长度:";
cin>>len;
cout<<"请输入单链表元素数据:";
for(i=1;i<len+1;i++)
{
cin>>e;
InsertElem(L,i,e);
}
return OK;
}
Status DestroyList(LinkList &L)
{
//3销毁单链表
LNode *p;
while(L->next!=NULL)
{
p=L->next;
L->next=p->next;
free(p); //从头结点开始逐个释放链表中的节点
}
free(L);
L=NULL;
return OK;
}
Status ClearList(LinkList &L)
{
//4清空单链表
LNode *p,*q;
p=L->next;
L->next=NULL; //跨过中间指向最后
while (p) //消除中间
{
q=p->next;
free(p);
p=q;
}
cout<<"清空完成!"<<endl;
}
bool ListEmpty(LinkList L)
{
//5判断空表
if(L->next==NULL)
return TRUE;
else return FALSE;
}
/*Status ListLength(LinkList L)
{
//6单链表长度
int n=0;
LNode *p;
p=L->next;
while (p)
{
n++;
p=p->next;
}
return(n);
}*/
Status GetElem(LinkList L, int i, ElemType &e)
{
//7获取单链表第i个数据元素
if(i<1||i>ListLength(L))
return PARA_ERROR;
LNode *p;
p=L->next;
for(int j=1;j<i;j++)
{
p=p->next;
}
e=p->data;
return OK;
}
Status LocateElem(LinkList L, ElemType e)
{
//8返回与e相同的元素位置
int i=0; //记录p的位置
LNode *p;
p=L->next;
while(p&&p->data!=e)
{
p=p->next;
i++;
}
if(i>=0&&i<ListLength(L))
return i+1; //返回实际位置
else if(i==ListLength(L)) return 0; //查找失败
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
//9返回前驱元素
int i=LocateElem(L, cur_e);
while(i==0)
{
cout<<"该元素不存在！"<<endl;
return ERROR;
//break;
}
while(i==1)
{
cout<<"该元素是第一个元素"<<endl;
return ERROR;
//break;
}
while(i!=0&&i!=1)
{
LNode *p;
p=L->next;
for(int j=0;j<i-2;j++)
{
p=p->next;
}
pre_e=p->data;
return OK;
}
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
//10返回后继元素
int i=LocateElem(L, cur_e);
if(i==0)
{
cout<<"该元素不存在！"<<endl;
return 0;
}
else if(i==ListLength(L))
{
cout<<"该元素是最后一个元素"<<endl;
return 0;
}
else
{
LNode *p;
p=L->next;
for(int j=0;j<i;j++)
{
p=p->next;
}
next_e=p->data;
return OK;
}
}
Status ListTraverse(LinkList L)
{
//11遍历单链表
LNode *p;
p=L->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
return OK;
}
Status SetElem(LinkList &L, int i, ElemType &e)
{
//12将第i个参数替换
if(i<1||i>ListLength(L))
return PARA_ERROR;
else
{
LNode *p;
p=L->next;
for(int j=0;j<i-1;j++)
{
p=p->next;
}
int t;
t=p->data;
p->data=e;
e=t;
}
return e;
}
/*Status InsertElem(LinkList &L, int i, ElemType e)
{
//13在第i个位置插入e
LNode *s=(LNode*)malloc(sizeof(LNode)); //申请新的节点s
if(s==NULL) exit(OVERFLOW); //申请节点失败
s->data=e;
LNode *p;
p=L->next;
if(i==1)
{
s->next=p;
L->next=s;
}
else if(i>1&&i<=ListLength(L))
{
for(int j=0;j<i-2;j++)
{
p=p->next;
}
s->next=p->next;
p->next=s;
//ListLength(L)=ListLength(L)+1; ??????????????
}
else if(i==ListLength(L)+1)
{
for(int j=0;j<i-2;j++)
{
p=p->next;
}
p->next=s;
s->next=NULL;
}
else
{
cout<<"表中没有该位置！"<<endl;
}
return OK;
}*/
Status DeleteElem(LinkList &L, int i, ElemType &e)
{
//14删除指定位置元素
if(i<1||i>ListLength(L))
{
cout<<"表中不存在该位置！"<<endl;
return(0);
}
LNode *p;
p=L->next;
if(i==1) //要删除第一个节点
{
e=p->data;
L->next=p->next;
free(p);
return(1);
}
else
{
for(int j=0;j<i-2;j++)
{
p=p->next;
}
LNode *q=p->next;
e=q->data;
p->next=q->next;
free(q);
return(1);
}
}
void menu()
{
//菜单
cout<<"1.初始化 2.建立"<<endl;
cout<<"3.销毁 4.清空"<<endl;
cout<<"5.判断空表 6.元素个数"<<endl;
cout<<"7.第i个元素值 8.找相同元素位置"<<endl;
cout<<"9.前驱 10.后继"<<endl;
cout<<"11.遍历输出 12.替换元素"<<endl;
cout<<"13.插入元素 14.删除元素"<<endl;
}
int main()
{
LinkList L;
int choice;
int e,cur_e,pre_e,next_e,i=0;
while(1)
{
menu();
cout<<"请选择："<<endl;
cin>>choice;
switch(choice)
{
case(1):InitList(L);break;
case(2):CreateList(L);break;
case(3):DestroyList(L);break;
case(4):ClearList(L);break;
case(5):if(ListEmpty(L)) cout<<"是空表"<<endl;
else cout<<"不是空表"<<endl;
break;
case(6):cout<<"单链表长度为"<<ListLength(L)<<endl;break;
case(7):cout<<"要输出第几个元素的值？"<<endl;
cin>>i;
GetElem(L, i, e);
if(!GetElem(L, i, e))
cout<<"单链表不存在第"<<i<<"个元素！"<<endl;
else
cout<<"第"<<i<<"个元素的值为"<<e<<endl;
break;
case(8):cout<<"请输入参数e:";
cin>>e;
if(LocateElem(L, e)==0)
{
cout<<"该元素不在单链表内！"<<endl;
}
else if(LocateElem(L, e)!=0) cout<<"参数e的位置为"<<LocateElem(L, e)<<endl;
break;
case(9):cout<<"请输入参数e:";
cin>>cur_e;
//PriorElem(L, cur_e, pre_e);
while(PriorElem(L, cur_e, pre_e))
{
cout<<"e的前一个元素为"<<pre_e<<endl;
break;
}
break;
case(10):cout<<"请输入参数e:";
cin>>cur_e;
//NextElem(L, cur_e, next_e);
while(NextElem(L, cur_e, next_e))
{
cout<<"e的后一个元素为"<<next_e<<endl;
break;
}
break;
case(11):ListTraverse(L);break;
case(12):cout<<"请输入要替换的元素位置:";
cin>>i;
cout<<"请输入新的元素值:";
cin>>e;
cout<<"替换成功！原元素值为"<<SetElem(L, i, e)<<endl;
break;
case(13):cout<<"请输入要插入的位置:";
cin>>i;
cout<<"请输入元素值:";
cin>>e;
InsertElem(L, i, e);
cout<<"插入成功！"<<endl;
break;
case(14):cout<<"请输入要删除的元素位置:";
cin>>i;
while(DeleteElem(L, i, e))
{
cout<<"删除成功！被删除的元素值为"<<e<<endl;
break;
}
break;
}
}
}