形式一(动态分配)
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct{
int *pBase;
int len;//线性表的最大长度
int cnt;//表示线性表的当前长度
}SqList;
void InitList(SqList *L)//初始化操作，建立一个空的线性表L
{
L->pBase = (int *)malloc(sizeof(int)*MAXSIZE);
if(L->pBase==NULL){
printf("内存分配失败");
exit(-1);
}
L->cnt = 0;
L->len = MAXSIZE;
}
bool ListEmpty(SqList L)//判断线性表L是否为空
{
if(L.cnt == 0){
return true;
}else{
return false;
}
}
void ClearList(SqList *L)//将线性表L清空
{
L->cnt = 0;
}
void DestoryList(SqList *L)//将线性表L销毁
{
free(L->pBase);
L->pBase = NULL;
L->cnt = 0;
L->len = 0;
}
void GetElem(SqList L,int i,int *e)//将线性表L中的第i个位置元素值返回给e
{
if(i<1||i>L.cnt){
printf("查找的位置不存在\n");
exit(-1);
}
*e = *(L.pBase+i-1);
}
int LocateElem(SqList L,int e)//查找线性表L中元素值为e的元素的位置
{
int i=0;
while(i<L.cnt){
if(L.pBase[i]==e)
{
return i+1;
}
i++;
}
return -1;//表示查询无果
}
void PriorElem(SqList L,int aim,int *e)//获取线性表中的元素aim的前一个元素
{
int k=LocateElem(L,aim);
if(k==-1 || k==1){
printf("%d元素不存在或者aim本身就是第一个元素\n",aim);
exit(-1);
}
*e = L.pBase[k-2];
}
void NextElem(SqList L,int aim,int* e)//获取线性表中的元素aim的后一个元素
{
int k=LocateElem(L,aim);
if(k==-1 || k==L.cnt){
printf("%d元素不存在或者aim本身就是最后一个元素\n",aim);
exit(-1);
}
*e = L.pBase[k];
}
void ListInsert(SqList *L,int i,int e)//在线性表L的第i个位置插入元素e
{
int *newBase,*p,*q;
if(i<1||i>L->cnt+1){
printf("插入的位置不存在\n");
exit(-1);
}
if(L->cnt>=L->len){//表示可插入的位置已满，需要重新扩展空间
newBase = (int *)realloc(L->pBase,(L->len+MAXSIZE)*sizeof(int));
if(newBase==NULL){
printf("内存分配失败\n");
exit(-1);
}
L->pBase = newBase;
L->len += MAXSIZE;
}
q = L->pBase+i-1;//q表示当前要插入的位置的地址
for(p=L->pBase+L->cnt;p>q;p--){
*p = *(p-1);
}
*p = e;
L->cnt++;
}
void ListDelete(SqList *L,int i,int *e)//删除线性表L第i个位置上的元素，并把元素保存在e中
{
int *q;
if(i<1||i>L->cnt){
printf("删除的位置不存在\n");
}
q = L->pBase+i-1;//要删除元素位置的地址
*e = *q;
while(q<L->pBase+L->cnt-1){
*q = *(q+1);
q++;
}
}
int ListLength(SqList L)//返回线性表L中当前元素的个数
{
return L.cnt;
}
void ListTraverse(SqList L)//遍历线性表L
{
int i = 0;
while(i<ListLength(L)){
printf("%d ",L.pBase[i]);
i++;
}
printf("\n");
}
int main()
{
SqList L;
int i,e;
InitList(&L);//初始化线性表
for(i=1;i<=19;i++){//循环往线性表插入元素
ListInsert(&L,i,i);
}
printf("执行插入操作之后结果如下：\n");
ListTraverse(L);
if(LocateElem(L,17)==-1){
printf("未能在线性表L中找到待查询的元素\n");
}else{
printf("值为17的元素位置:%d\n",LocateElem(L,17));
}
GetElem(L,6,&e);
printf("第6个位置上的元素为：%d\n",e);
ListDelete(&L,4,&e);
printf("执行删除操作之后结果如下：\n");
ListTraverse(L);
PriorElem(L,7,&e);//获取aim的前一个元素
printf("aim的前一个元素是:%d\n",e);
NextElem(L,7,&e);//获取aim的后一个元素
printf("aim的后一个元素是:%d\n",e);
return 0;
}
形式二（静态分配）
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct{
int pBase[MAXSIZE];
int cnt;//表示线性表的当前长度
}SqList;
void InitList(SqList *L)//初始化操作，建立一个空的线性表L
{
L->cnt = 0;
}
bool ListEmpty(SqList L)//判断线性表L是否为空
{
if(L.cnt == 0){
return true;
}else{
return false;
}
}
void ClearList(SqList *L)//将线性表L清空
{
L->cnt = 0;
}
int LocateElem(SqList L,int e)//查找线性表L中元素值为e的元素的位置
{
int i=0;
while(i<L.cnt){
if(L.pBase[i]==e)
{
return i+1;
}
i++;
}
return -1;//表示查询无果
}
void PriorElem(SqList L,int aim,int *e)//获取线性表中的元素aim的前一个元素
{
int k=LocateElem(L,aim);
if(k==-1 || k==1){
printf("%d元素不存在或者aim本身就是第一个元素\n",aim);
exit(-1);
}
*e = L.pBase[k-2];
}
void NextElem(SqList L,int aim,int* e)//获取线性表中的元素aim的后一个元素
{
int k=LocateElem(L,aim);
if(k==-1 || k==L.cnt){
printf("%d元素不存在或者aim本身就是最后一个元素\n",aim);
exit(-1);
}
*e = L.pBase[k];
}
void GetElem(SqList L,int i,int *e)//将线性表L中的第i个位置元素值返回给e
{
if(i<1||i>L.cnt){
printf("查找的位置不存在\n");
exit(-1);
}
*e = *(L.pBase+i-1);
}
void ListInsert(SqList *L,int i,int e)//在线性表L的第i个位置插入元素e
{
int k;
if (i<1 || i>L->cnt+1 || L->cnt==MAXSIZE){
printf("插入的位置无效或数组已满\n");
exit(-1);
}
for(k=L->cnt;k>i-1;k--){
L->pBase[k] = L->pBase[k-1];
}
L->pBase[k] = e;
L->cnt++;
}
void ListDelete(SqList *L,int i,int *e)//删除线性表L第i个位置上的元素，并把元素保存在e中
{
int k;
if (i<1 || i>L->cnt){
printf("删除的位置无效\n");
exit(-1);
}
*e = L->pBase[i-1];
for(k=i-1;k<L->cnt-1;k++){
L->pBase[k] = L->pBase[k+1];
}
L->cnt--;
}
int ListLength(SqList L)//返回线性表L中当前元素的个数
{
return L.cnt;
}
void ListTraverse(SqList L)//遍历线性表L
{
int i = 0;
while(i<ListLength(L)){
printf("%d ",L.pBase[i]);
i++;
}
printf("\n");
}
int main()
{
SqList L;
int i,e;
InitList(&L);//初始化线性表
for(i=1;i<=19;i++){//循环往线性表插入元素
ListInsert(&L,i,i);
}
printf("执行插入操作之后结果如下：\n");
ListTraverse(L);
if(LocateElem(L,17)==-1){
printf("未能在线性表L中找到待查询的元素\n");
}else{
printf("值为17的元素位置:%d\n",LocateElem(L,17));
}
GetElem(L,6,&e);
printf("第6个位置上的元素为：%d\n",e);
ListDelete(&L,4,&e);
printf("执行删除操作之后结果如下：\n");
ListTraverse(L);
PriorElem(L,7,&e);//获取aim的前一个元素
printf("aim的前一个元素是:%d\n",e);
NextElem(L,7,&e);//获取aim的后一个元素
printf("aim的后一个元素是:%d\n",e);
return 0;
}
网友评论