返回顶部

收藏

C++顺序表操作代码演示

更多
/*
*建立一个顺序表,插入n个元素并输出
*Author :CplusHua PurpleHua
*Date:2012-10-06
*/
#include<iostream>
#include "malloc.h"
#include <stdio.h>
#define ElemType int //宏定义
#define LIST_INT_SIZE 10 //改为1,改用ListInsert增加空间
using namespace std;
//定义一个顺序表
struct  SqList{
    ElemType * elem;
    int length;
    int listsize;
}L={NULL,0,0};
//返回状态定义
//这里修改了课本里的宏定义,全部在一个enum中定义完毕,
//让所有的函数返回一个枚举类型的结果
enum Status
{
    OK,FAILED,EMPTY,NOTINIT,OVERFLOW1//OVERFLOW在visual studio无法使用,改为OVERFLOW1
};
//初始化一个顺序表,成功返回OK,n是申请空间的大小
Status InitList_Sq(SqList &L,int n=LIST_INT_SIZE)
{
    if(L.elem) free(L.elem);//如果已经建立顺序表,则释放重新建立
    if(0==n)return FAILED;
    L.elem=(ElemType *)malloc(n*sizeof(ElemType));//为指针申请空间
    if(!L.elem) exit(OVERFLOW1);
    L.length=0;
    L.listsize=n;
    return OK;
}
//在线性表第i个元素之前插入一个元素
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{//如果LIST_INT_SIZE设置为100,则在此加入判断,L.lisesize>100时增加空间
    if(L.length<=0||i<=0)return FAILED;//空表,返回失败
    if(!L.elem) return NOTINIT;//顺序表未初始化
    if(i>L.length) return OVERFLOW1;//溢出,返回溢出(输入越界)
    if(L.length>=L.listsize)
    {
        //每插入一个元素重新申请增加空间
        ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+1)*sizeof(ElemType));
        L.elem=newbase;
        L.listsize++;
    }
    int *p,*q;
    p=L.elem+L.length;//最后一个位置
    q=L.elem+i-1;//要插入元素的位置
    for(;p>q;p--)
        *p=*(p-1);
    *q=e;
    L.length++;
return OK;
}
//删除顺序表中的元素
Status ListDelete_Sq(SqList &L,int i,ElemType *e=0)
{
    if(L.length<0||i>L.length||i<=0) return FAILED;
    if(!L.elem) return NOTINIT;//顺序表未初始化
    if(0==L.length) return EMPTY;
    int *p;
    p=L.elem+i-1;//定位到要删除的元素位置
    if(e)
        *e=*p;//返回要删除元素的值
    for(;p<=L.elem+L.length;p++)
    {
        *p=*(p+1);
    }
    L.length--;
    return OK;

}
//要输入元素的线性表L,要输入的元素个数n
Status ListInput_Sq(SqList &L,int n)
{
    int *p=L.elem;
    for(int i=0;i<n;i++)
    {
        cin>>*(p++);
        L.length++;
    }
    return OK;
}
//顺序输出顺序表中的元素
Status ListOutput_Sq(SqList &L)
{
    if(!L.elem) return NOTINIT;//顺序表未初始化
    int *p;
    p=L.elem;
    cout<<"顺序表中的元素为:";
    for(int i=0;i<L.length;i++)
    {
        cout<<*(p++)<<" ";
    }
    cout<<endl;
    return OK;
}
//查找最大元素
Status ListMax_Sq(SqList &L,ElemType *e)
{
    if(!L.elem) return NOTINIT;//顺序表未初始化
    int max;
    int *p;
    p=L.elem;
    max=*p;
    for(int i=0;i<L.length;i++)
    {
        if(max<*p)
            max=*p;
        p++;//最后溢出了会怎样?
    }
    *e=max;
    return OK;
}
//升序排序
Status ListSort_Sq(SqList &L)
{
    if(!L.elem) return NOTINIT;//顺序表未初始化
    int tmp;
    int i,j;
    int *p;
    p=L.elem;
    for(i=0;i<L.length-1;i++)
    {
        for(j=0;j<L.length-i-1;j++)
        {
            if(*(p+j)>*(p+j+1))
            {
                tmp=*(p+j);
                *(p+j)=*(p+j+1);
                *(p+j+1)=tmp;
            }
        }
    }
    return OK;
}
//逆序(使用一个暂存空间)
Status ListRevorder_Sq(SqList &L)
{
    if(!L.elem) return NOTINIT;//顺序表未初始化
    int tmp;
    int *p;
    p=L.elem;
    for(int i=0;i<L.length/2;i++)
    {
        tmp=*(p+i);
        *(p+i)=*(p+L.length-i-1);
        *(p+L.length-i-1)=tmp;
    }
    return OK;
}
//逆序(不使用暂存空间)
Status ListRevorder1_Sq(SqList &L)
{
    if(!L.elem) return NOTINIT;//顺序表未初始化
    int *p;
    p=L.elem;
    for(int i=0;i<L.length/2;i++)
    {
        *(p+i)=(*(p+L.length-i-1))^(*(p+i));
        *(p+L.length-i-1)=(*(p+L.length-i-1))^(*(p+i));
        *(p+i)=(*(p+L.length-i-1))^(*(p+i));
    }
    return OK;
}
//主函数
int main()
{
    int opt;
   // SqList L;
   // L.elem=NULL;//初始化
    int i,res,e,n;
    n=0;
    while(1)
    {

        if(n)
        {
            while(getchar()!='\n'&&getchar()!=' ');
            while(getchar()!='\n'&&getchar()!=' ');
        }
        cout<<"************请输入您要进行的操作的编号************"<<endl<<endl;
        cout<<"1.建立一个顺序表,输入n个数字元素并输出"<<endl;
        cout<<"2.查找线性表中的最大元素并输出"<<endl;
        cout<<"3.在线性表的第i个元素前插入一个正整数x"<<endl;
        cout<<"4.删除线性表中的第j个元素"<<endl;
        cout<<"5.将线性表中的元素按升序排列"<<endl;
        cout<<"6.将线性表中的元素就地逆序(只允许用一个暂存单元)"<<endl;
        cout<<"7.将线性表中的元素就地逆序(不使用暂存单元)"<<endl;
        cout<<"8.退出"<<endl<<endl;
        cout<<"***************************************************"<<endl;
        cin>>opt;
        switch (opt)
        {
            case 1:
            cout<<"***************请输入要输入元素的个数**************"<<endl;
            cin>>n;
            InitList_Sq(L,n);//建立顺序表
            cout<<"*****************请输入线性表元素******************"<<endl;
            ListInput_Sq(L,n);//进入输入元素的函数
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 2:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            ListMax_Sq(L,&e);
            cout<<"最大元素为:"<<e<<endl;
            break;
            case 3:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            cout<<"请分别输入要插入的元素和要插入元素的位置"<<endl;
            cout<<"元素:";
            cin>>e;
            cout<<"位置:";
            cin>>i;
            ListInsert_Sq(L,i,e);
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 4:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            cout<<"请输入要删除的元素的位置"<<endl;

            cin>>i;//位置
            ListDelete_Sq(L,i,&res);
            cout<<"删除的元素为:"<<res<<endl;
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 5:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            ListSort_Sq(L);//升序排序
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 6:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            ListRevorder_Sq(L);//使用一个暂存空间逆序
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 7:
            if(!L.elem)
            {
                cout<<"顺序表未初始化,请初始化顺序表!"<<endl<<endl;
                break;
            }
            ListRevorder1_Sq(L);//不使用暂存空间逆序
            ListOutput_Sq(L);//输出顺序表中的元素
            break;
            case 8:
                return 0;
            default:
                cout<<"ERROR"<<endl;
        }
    }
    return 0;
}

标签:顺序表,C++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2012-12-06 21:23:15c++大数阶乘算法 by zetaliang
  2. 2012-12-20 13:30:20伪造硬币问题 by 傅小黑
  3. 2014-04-05 14:40:50C++算法之可变参数 by 童学芬
  4. 2014-05-18 11:40:55KMP字符串匹配算法 by 童学芬
  5. 2014-05-19 15:46:15高效素数筛法 by lucasli
  6. 2014-05-20 12:48:01线性表之顺序表 by 千万不要郁闷
  7. 2014-05-22 13:29:39递归题改为非递归题实例 by lucasli
  8. 2014-05-27 11:43:40广度优先遍历 by aiheng1988
  9. 2014-06-04 11:01:43阶乘之和 by 小项
  10. 2014-06-10 11:19:27使用二维数组排列组合实现倒计时 by sxgkwei
  11. 2019-06-17 21:18:10PHP+jQuery.photoClip.js图片裁剪上传实例 by 素材火官网

发表评论