题目：编程实现书P12 ADT List 基本操作14个：
（1）用顺序存储结构实现；
（2）用链式存储结构实现；
算法思想：
用顺序存储结构实现ADT List基本操作；
运用动态储存，初始化，销毁和清空；进行访问型操作；加工型操作，在增加和删除数据元素时需要移动顺序表内的相应元素，在移动元素时需注意移动的顺序及是否有足够的空间。
用链式存储结构实现ADT List基本操作；
初始化，销毁和清空；访问型操作，序号需要与逻辑描述保持一致；加工型操作，增加和删除数据元素时将新的结点接入单链表或取下。
（1）用顺序存储结构实现；

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
using namespace std;

#define LISTINITSIZE   256
#define LISTINCREMENT  128

typedef int Status;
typedef int ElemType;
typedef struct SeqList
{
	ElemType *pData;
	int length;
	int size;
}SeqList;

Status CreatList(SeqList &L)
{
	int n,x;
	cout<<"-请输入顺序表的长度-"<<endl;
	cin>>n;
	cout<<"-请逐个输入顺序表的数据元素-"<<endl;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		L.pData[i-1]=x;
		L.length ++;
	} 
	return 0;
}

Status InitList(SeqList &L)
{
	L.pData = (ElemType*)malloc(LISTINITSIZE*sizeof(ElemType));
	if(L.pData == NULL ) exit(EOVERFLOW);
	L.size = LISTINITSIZE;
	L.length  = 0;
	return 0;
}

Status DestroyList(SeqList &L)
{
	if(L.pData != NULL)
	{
		free(L.pData );
		L.pData = NULL;
		L.length = 0;
		L.size = 0;
	}
	return 0;
}

Status ClearList(SeqList &L)
{
	L.length = 0;
	return 0;
}

bool ListEmpty(SeqList L)
{
	if(!L.pData )
		return true;
	else 
		return false; 
}

Status ListLength(SeqList L)
{
	if(L.length )
		return L.length ;
	else
		return 0;
}

Status GetElem(SeqList L,int i, ElemType &e)
{
	if(i<1||i>L.length )
	{
		cout<<"ERROR"<<endl; 
		return 0;
	}
	e = L.pData [i-1];
	return e;
}

Status LocateElem(SeqList L,ElemType &e)
{
	for(int i=0;i<L.length ;i++)
	{
		if(L.pData [i]==e)
			return i+1;
	}
	return 0;
}

Status PriorElem(SeqList L,ElemType cur_e, ElemType &pre_e)
{
	for(int i=0;i<L.length ;i++)
	{
		if(i!=0&&cur_e==L.pData [i])
		{
			pre_e=L.pData [i-1];
			return pre_e;
		}

	}
	return 0;
}

Status NextElem(SeqList L,ElemType cur_e,ElemType &next_e)
{
	for(int i=0;i<L.length ;i++)
	{
		if(i!=0&&cur_e==L.pData [i])
		{
			next_e=L.pData [i+1];
			return next_e;
		}

	}
	return 0;
}


Status ListTraverse(SeqList L)
{
	ElemType e; 
	for(int i=1;i<L.length+1 ;i++)
	{
		if(i<1||i>L.length )
			return 0;
		else
		{
			e=L.pData [i-1];
			printf("%d",e);
		}
	}
	return 0;
}

Status SetElem(SeqList &L,int i, ElemType &e)
{
	if(i<1||i>L.length)
	{
		cout<<"ERROR"<<endl; 
		return 0;
	}
	ElemType f;
	f=L.pData [i-1];
	L.pData [i-1]=e;
	return f;
}

Status InsertElem(SeqList &L,int i,ElemType &e)
{
	if(i<1||i>L.length +1)
	{
		cout<<"ERROR"<<endl; 
		return 0;
	}
	if(L.length >=L.size )
	{
		ElemType *newbase;
		newbase = (ElemType*)realloc(L.pData ,(L.size +LISTINCREMENT)*sizeof(ElemType));
		if(newbase == NULL)
			exit(EOVERFLOW);
		L.pData = newbase;
		L.size += LISTINCREMENT;
	}
	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 0;
}

Status DeleteElem(SeqList &L,int i,ElemType &e)
{
	if(i<1||i>L.length +1)
	{
		cout<<"ERROR"<<endl; 
		return 0;
	}
	e=L.pData [i-1];
	for(int j=i;j<=L.length -1;j++)
	{
		L.pData [j-1] = L.pData [j];
	}
	L.length -= 1;
	return e;
}

int main()
{
	SeqList L;
	int i, n, x;
	int &e=x ;
	
	cout<<"-进行初始化操作-"<<endl;		
	InitList(L);					
	CreatList(L);
	if( ListEmpty(L) == true )						
		cout<<"顺序表为空表"<<endl;
	else
		cout<<"顺序表不是空表"<<endl;
	cout<<"输出顺序表如下："<<endl;
	ListTraverse(L);								
	cout<<endl;
	
	cout<<"顺序表长度为：";
	cout<<ListLength(L);						
	cout<<endl;
	
	i = 2;
	cout<<"第"<<i<<"个数据元素为：";
	cout<<GetElem(L, i, e);							
	cout<<endl;
	
	x=3;
	e=x;
	cout<<"元素"<<e<<"所在的位置：";
	cout<<LocateElem(L, e);							
	cout<<endl;
	

	cout<<"元素"<<e<<"的前驱元素为：";
	cout<<PriorElem(L, e, e);					
	cout<<endl;
	cout<<"元素"<<e<<"的后继元素为：";
	cout<<NextElem(L, e, e);					
	cout<<endl;
	
	n = 4;
	e = 7;
	cout<<"第"<<n<<"个元素被"<<e<<"替换前的旧值为："; 
	cout<<SetElem(L, n, e);						
	cout<<endl;
	cout<<"输出顺序表如下："<<endl;
	ListTraverse(L);
	cout<<endl;
	
	i=4;
	cout<<"将要删除的第"<<i<<"个元素为：";
	cout<<DeleteElem(L, i, e);						
	cout<<endl;
	cout<<"输出顺序表如下："<<endl;
	ListTraverse(L); 
	cout<<endl;
	
	cout<<"-进行清空操作-"<<endl;
	ClearList(L);								
	if( ListEmpty(L) == true )						
		cout<<"顺序表为空表"<<endl;
	else
		cout<<"顺序表不是空表"<<endl;
	cout<<endl;
	
	cout<<"-进行销毁操作-"<<endl;
	DestroyList(L);									
	if( ListEmpty(L) == true )							
		cout<<"顺序表为空表"<<endl;
	else
		cout<<"顺序表不是空表"<<endl;

}

（2）用链式存储结构实现；

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
using namespace std;

typedef int ElemType;
typedef struct LNode
{
	ElemType  data;
	struct LNode *next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
	L=(LNode*)malloc(sizeof(LNode));
	L->next =NULL;
}

void CreatList(LinkList &L)
{
	int n,x;
	LNode *p,*q;
	p=L;
	cout<<"-请输入单链表的长度-"<<endl;
	scanf("%d",&n);
	cout<<"-请逐个输入单链表的数据元素-"<<endl;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		q=(LNode*)malloc(sizeof(LNode));
		q->data =x;
		p->next =q;
		p=q;	
	}
	p->next =NULL;	
} 

void DestroyList(LinkList &L)
{
	LNode *p;
	p=L->next ;
	while(p)
	{
		L->next =p->next;
		free(p);
		p=L->next ;
	}
}

void ClearList(LinkList &L)
{
	LNode *p;
	p=L->next ;
	while(p)
	{
		p->data=NULL;
		p=p->next ; 
	}
}

bool ListEmpty(LinkList L)
{
	if(L->next ==NULL)
		return true;
	else
		return false;
}

int ListLength(LinkList L)
{
	LNode *p;
	p=L->next ;
	int length=0;
	while(p)
	{
		p=p->next ;
		length++;
	}
	return length;
}

int GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p;
	int j=0;
	p=L->next ;
	while(p)
	{
		p=p->next ;
		j++;
		if(i==j)
		{
			e=p->data ;
			return e; 
		}
	}
	if(j>i)
	{
		printf("ERROR");
		return 0;
	}
	return 0;
}

int LocateElem(LinkList L,ElemType &e)
{
	LNode *p;
	p=L->next ;
	int i=1;
	while(p)
	{
		if(p->data ==e)
			return e;
		else
		{
			p=p->next ;
			i++;
		}
	}
	return 0;
}

int PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
{
	LNode *p,*q;
	p=L->next ;
	q=p->next ;
	while(q)
	{
		if(q->data==cur_e)
		{
			pre_e=p->data ;
			return pre_e;
		}
		else
		{
			p=q;
			q=p->next ;
		}
	}
	printf("ERROR"); 
	return 0;
}

int NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
{
	LNode *p,*q;
	p=L->next ;
	q=p->next ;
	while(q)
	{
		if(p->data==cur_e)
		{
			next_e=q->data ;
			return next_e;
		}
		else
		{
			p=q;
			q=p->next ;
		}
	}
	printf("ERROR"); 
	return 0;	
}

int ListTraverse(LinkList L)
{
	LNode *p;
	p=L->next ;
	while(p)
	{
		printf("%d",p->data );
		p=p->next ;
	}
	return 0;
}

int SetElem(LinkList &L,int i,ElemType &e)
{
	LNode *p;
	ElemType f;
	f=e;
	p=L->next ;
	int j=1;
	while(p)
	{
		if(i==j)
		{
			e=p->data ;
			p->data =f;
			return e;
		}
		else
		{
			p=p->next;
			j++; 		
		}
	}
	printf("ERROR"); 
	return 0;
}

int InsertElem(LinkList &L,int i,ElemType &e)
{
	LNode *p,*q;
	int j=1;
	LNode *s; 
	s=(LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		exit(EOVERFLOW);
	s->data=e;
	q=L;
	p=L->next ;
	while(p)
	{
		if(j==i)
		{
			q->next =s;
			s->next=p;
			return 0;
		}
		else
		{
			q=p;
			p=p->next ;
		}
	}
	return 0;
}

int DeleteElem(LinkList &L,int i,ElemType &e)
{
	LNode *p,*q;
	int j=1;
	q=L;
	p=L->next ;
	while(p)
	{
		if(j==i)
		{
			e=p->data ;
			q->next =p->next ;
			free(p);
			return e;
		}
		else
		{
			q=p;
			p=p->next ;
			j++; 
		}
	}
	return 0;
}

int main()
{
	LinkList L;
	int i, n, x;
	int &e=x ;
	
	cout<<"-进行初始化操作-"<<endl;		
	InitList(L);					
	CreatList(L);
	if( ListEmpty(L) == true )						
		cout<<"单链表为空表"<<endl;
	else
		cout<<"单链表不是空表"<<endl;
	cout<<"单链顺序表如下："<<endl;
	ListTraverse(L);								
	cout<<endl;
	
	cout<<"单链表长度为：";
	cout<<ListLength(L);						
	cout<<endl;
	
	i = 2;
	cout<<"第"<<i<<"个数据元素为：";
	cout<<GetElem(L, i, e);							
	cout<<endl;
	
	x=3;
	e=x;
	cout<<"元素"<<e<<"所在的位置：";
	cout<<LocateElem(L, e);							
	cout<<endl;
	

	cout<<"元素"<<e<<"的前驱元素为：";
	cout<<PriorElem(L, e, e);					
	cout<<endl;
	cout<<"元素"<<e<<"的后继元素为：";
	cout<<NextElem(L, e, e);					
	cout<<endl;
	
	n = 4;
	e = 7;
	cout<<"第"<<n<<"个元素被"<<e<<"替换前的旧值为："; 
	cout<<SetElem(L, n, e);						
	cout<<endl;
	cout<<"输出顺序表如下："<<endl;
	ListTraverse(L);
	cout<<endl;
	
	i=4;
	cout<<"将要删除的第"<<i<<"个元素为：";
	cout<<DeleteElem(L, i, e);						
	cout<<endl;
	cout<<"输出顺序表如下："<<endl;
	ListTraverse(L); 
	cout<<endl;
	
	cout<<"-进行清空操作-"<<endl;
	ClearList(L);								
	if( ListEmpty(L) == true )						
		cout<<"单链表为空表"<<endl;
	else
		cout<<"单链表不是空表"<<endl;
	cout<<endl;
	
	cout<<"-进行销毁操作-"<<endl;
	DestroyList(L);									
	if( ListEmpty(L) == true )							
		cout<<"单链表为空表"<<endl;
	else
		cout<<"单链表不是空表"<<endl;

}
# 数据结构 # list
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR巡检哪家好，和浪潮比哪家方案更成熟

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区
cover

瑞丰宝丽在AR巡检领域排名

avatar 乐奇 Rokid 开放社区