今天和大家分享一下顺序表的基本操作
 
编写一个完整的程序，实现顺序表的建立、插入、删除、输出等基本运算。
 （1） 建立一个顺序表，含有n个数据元素。
 （2） 输出顺序表及顺序表的长度。
 （3） 在顺序表中删除值为x的结点或者删除给定位置i的结点。
 （4） 将顺序表就地逆置，即利用原表的存储空间将线性表（a1,a2,...,an）逆置为（an,an-1,...,a1）。
 （5） 将顺序表按升序排序。
 （6） 设顺序表中的数据元素递增有序，将x插入到顺序表的适当位置上，以保持该表的有序性。
 （7） 在主函数中设计一个简单的菜单，分别测试上述算法。
 
 
根据上题，我写了一个完整的程序，包括三个头文件，一个源程序。
 
头文件1（包括一些库文件）：
 

#include <iostream>
#include <stdlib.h>
using namespace std;
头文件2（一些基本定义）：
 

#define INIT_SIZE 100
#define INCRE 20
#define ERROR 0
#define OK 1

typedef int Status;
typedef int ElemType;
typedef struct SqList
{
	ElemType *elem;//顺序表头,
	int length;//顺序表中含有数据的个数
	int listsize;//顺序表的长度(注意与length的区别)
};
头文件3（一些基本函数的实现），我将分别将每个函数列出来，因为有一些需要注意的点。

 创建顺序表：
 

Status Init(SqList &L)//
{
	int i;
	ElemType value;
	L.elem = (ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
	if (!L.elem)
	{
		cout<<"分配内存失败！！！！！"<<endl;
		return ERROR;
	}
	L.listsize = INIT_SIZE;//表创建成功了，一定要记得将表长置为INIT_SIZE
	cout<<"提示：下面你可以开始输入数据了，输入-1表示输入结束"<<endl;
	cin>>value;
	for (i = 0;value != -1;i++)
	{
		L.elem[i] = value;
		cin>>value;
	}
	cout<<"提示：输入结束"<<endl;
	L.length = i;//表中的数据个数正好是此时的i
	return OK;
}
打印顺序表：
 
我这里使用一个length变量来接受表的长度
 

Status PrintList(SqList L,int &length)
{
	int i;
	for (i = 0;i<L.length;i++)
	{
		cout<<L.elem[i]<<endl;
	}
	length = L.length;
	cout<<"表长为"<<length<<endl;
	return OK;
}

 删除数据：
 
根据题目，我这里写了两种删除数据的方式，值得一提的是，在第二种删除数据方式中，最好是采用二分法来确定被删除数据的位置，这样在一些比较大型的数据中，可以大大的提升效率。
 

Status Del(SqList &L)
{
	if (L.length == 0)//先判断表是否为空
	{
		cout<<"该表为空，不能进行删除操作"<<endl;
		return ERROR;
	}
	int choice;
	cout<<"你将要进行删除操作，请选择下一步操作内容："<<endl;
	cout<<"1.删除表中某一位置的元素"<<endl;
	cout<<"2.删除表中指定的值"<<endl;
	cout<<"输入你的选择："<<endl;
	cin>>choice;
	switch (choice)
	{
	case 1:
		int pos,i;
		cout<<"输入一个位置："<<endl;
		cin>>pos;
		if (pos<1||pos>L.length)
		{
			cout<<"这个位置没有数据！"<<endl;
			return ERROR;
		}
		for (i = pos-1;i<L.length-1;i++)
		{
			L.elem[i] = L.elem[i+1];
		}
		L.length--;   //表中数据减一
		return OK;
		break;
	case 2:
		int value;
		cout<<"输入一个值："<<endl;
		cin>>value;
		for (i = 0;i<L.length;i++)
		{
			if (value == L.elem[i])
			{
				pos = i;//记录下这个i值,我们只删除第一个匹配的
				break;
			}
		}
		for (i = pos;i<L.length-1;i++)//从pos位置开始，将后面的所有数据依次向前移动一位
		{
			L.elem[i] = L.elem[i+1];
		}
		L.length--;   //表中数据减一
		return OK;
		break;
	default:
		cout<<"没有这个选项"<<endl;
		return ERROR;
	}
}

 颠倒顺序表：
 
颠倒的方式很多，但是我想这是比较简单的一种，还有一些其他的方式，例如再开辟一个数组，但这样很麻烦。
 

Status Reverse(SqList &L)
{
	if (L.length ==0) return ERROR;
	ElemType temp;
	int i;
	for (i = 0;i<(L.length)/2;i++)//直接将首尾数据交换，同时i++
	{
		temp = L.elem[i];
		L.elem[i] = L.elem[L.length-1-i];
		L.elem[L.length-1-i] = temp;
	}
	return OK;
}

 排序函数：
 
这里只实现了升序排列，而且用的是效率一般的冒泡排序，大家可以试试快速排序。
 

Status Sort(SqList &L)
{
	if (L.length ==0) return ERROR;
	int i,j;
	ElemType temp,min;
	for(i = 0;i<L.length-1;i++)//冒泡排序
	{
		for (j = 0;j<L.length-i-1;j++)
		{
			if (L.elem[j]>L.elem[j+1])
			{
				temp = L.elem[j];
				L.elem[j] = L.elem[j+1];
				L.elem[j+1] = temp;
			}
		}
	}
	return OK;
}
 

 
 插入数据： 
根据题目要求，这里只实现了在有序表中的插入操作，而不是指定位置插入。建议大家也可以实践一下，
 
注意：所有的插入操作与删除操作都要注意对length的改变，还有就是当表满了的时候listsize也要变化。
 

Status Insert(SqList &L)
{
	ElemType value;
	int i = 0,pos;
	cout<<"提示：请确保出入之前顺序表有序，否则插入操作可能出错"<<endl;
	cout<<"输入要插入的数据"<<endl;
	cin>>value;
	if  (L.length>=L.listsize)//顺序表已满
	{
		ElemType *newbase;
		newbase = (ElemType*)realloc(L.elem,(INIT_SIZE+INCRE)*sizeof(ElemType));
		if (!newbase)
		{
			cout<<"重分配内存失败"<<endl;
			return ERROR;
		}
		L.elem = newbase;
		L.listsize = INIT_SIZE+INCRE;
	}
	while (value >= L.elem[i])
	{
		i++;
	}
	pos = i;
	for(i = L.length;i>=pos;i--)
	{
		L.elem[i+1] = L.elem[i]; 
	}
	L.elem[pos] = value;
	L.length++;
	return OK;
}

 

 

 
每天进步一点点

 

 
 

 

 /*
 *Copyright (c) 2016, 烟台大学计算机学院
 *All rights reserved.
 *文件名称：main.cpp
 *作者：张旺华
 *完成日期： 2016 年 7 月 1 日
 *版本号：v1.0
 *问题描述：编写一个程序实现顺序表的各种基本运算（假设顺序表的元数基本类型为Char）
 *
 */

#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;
typedef char ElemType;
#define Maxsize 50
typedef struct
{
    ElemType data[Maxsize];
    int length;
}SqList;
void InitList(SqList *&L)  //初始化线性表
{
    L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
    L->length=0;                        //置空线性表长度为0
}
void DestroyList(SqList *L)  //销毁线性表
{
    free(L);
}
bool ListEmpty(SqList *L) //判断线性表是否为空
{
    return (L->length==0);
}
int ListLength(SqList *L) //求线性表的长度
{
    return (L->length);
}
void DispList(SqList *L) //输出线性表
{
    int i;
    if(L->length==0) return;
    for(i=0;i<L->length;i++)
        printf("%c ",L->data[i]);
    printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)  //求线性表中某个元数的值
{
    if(i<1||i>L->length)
        return false;
    e=L->data[i];
    return true;
}
int LocateElem (SqList *L,ElemType e)  //按元素值查找
{
    int i=0;
    while(i<L->length&&L->data[i]!=e)
        i++;
    if(i>=L->length)
        return 0;
    else
        return i+1 ;
}
bool ListInsert(SqList *L,int i,ElemType e)  //插入数据元素
{
    int j;
    if(i<1||i>L->length)
        return false;
    i--;
    for(j=L->length;j>i;j--)
        L->data[j]=L->data[j-1];
    L->data[i]=e;
    L->length++;
    return true;
}
bool ListDelete(SqList *L,int i,ElemType e)
{
    //int j;
    if(i<1||i>L->length)
        return false;
    i--;
    e=L->data[i];
    for(;i<L->length-1;i++)
    {
        L->data[i]=L->data[i+1];
    }
    L->length--;
    return true;
}
int main()
{
    SqList *h;
    ElemType e;
    cout<<"顺序表的基本运算如下："<<endl;
    cout<<"(1)初始化顺序表h："<<endl;
    InitList(h);
    cout<<"(2)依此采用尾插法插入a,b,c,d,e元素："<<endl;
    ListInsert(h,1,'a');
    ListInsert(h,2,'b');
    ListInsert(h,3,'c');
    ListInsert(h,4,'d');
    ListInsert(h,5,'e');
    cout<<"(3)输出顺序表h："<<endl;
    DispList(h);
    cout<<"(4)顺序表h长度为："<<ListLength(h)<<endl;
    printf("(5)顺序表h为%s\n",(ListEmpty(h)?"空":"非空"));
    GetElem(h,3,e);
    cout<<"(6)顺序表h的第3个元素是："<<e<<endl;
    cout<<"(7)元素a的位置："<<LocateElem(h,'a')<<endl;
    cout<<"(8)在第四个元素位置上插入f元素："<<endl;
    ListInsert(h,4,'f');
    cout<<"(9)输出顺序表h:"<<endl;
    DispList(h);
    cout<<"(10)删除h的第3个元素："<<endl;
    ListDelete(h,3,e);
    cout<<"(11)输出顺序表h："<<endl;
    DispList(h);
    cout<<"(12)释放顺序表h："<<endl;
    DestroyList(h);
}
 
运行结果：
 

 
 
学习心得：数据结构实践操作第一题。

#include <stdio.h>
#include<stdlib.h>
#define maxsize 50
typedef struct
{
    int data[maxsize];
    int last;
}Sequenlist;

Sequenlist * InitList () //创建顺序表
{ 
    Sequenlist * L ;
 L= (Sequenlist *) malloc( sizeof(Sequenlist) );
 L->last =0;
 return(L);
}

Sequenlist * creat() //创建一个有具体内容的顺序表
{ 
    Sequenlist * L; int i=1,n;
    L=InitList( );
    printf("请插入数据,以0结束\n");
    scanf("%d",&n);
    while(n!=0 && L->last<maxsize)
    {
        L->data[i]=n; 
        i=i++; 
        L->last++;
        scanf("%d",&n);
    }
    return(L);
}
int Length (Sequenlist * L) //求表的长度 
{
 return (L->last); 
}

int GetData (Sequenlist * L, int i ) //获取第i个元素
{
 if ( i >=1 && i <=L->last)
 return (L->data[i]);
 else 
    {
    printf ("参数 i 不合理！\n");
    return 0;
    }

} 
int Find (Sequenlist *L, int x ) // 查找元素x
{
 int i=1;
 while ( i <=L->last && L->data[i] != x )
 i++;
 if ( i <=L->last ) 
 return (i);
 else 
 return (0);
}
int Insert ( Sequenlist * L, int x, int i ) //在某一位置插入数据
 {
    int j;
 //在表中第 i 个位置插入新元素 x 
 if (i < 1|| i > L->last +1|| L->last == maxsize)
 return 0; //插入不成功 
 else {
    for ( j=L->last; j >=i; j-- )
 { L->data[j+1] = L->data[j]; } 
 L->data[i] = x; L->last++; 
 return 1; //插入成功 
 }
 }
int Delete ( Sequenlist *L, int i ) //删除某一位置的数据
 {
 //在表中删除节点i
    int j;
 if ( i <1 || i >L->last) return 0;
 for ( j=i+1; j <=L->last; j++ ) 
 L->data[j-1] =L->data[j];
 L->last=L->last -1;
 return 1; //成功删除 

 }
void print(Sequenlist *L) //打印函数
{
    int i;
    for(i=1;i<=L->last;i++)
    printf("%d\n",L->data[i]);
}
void main()
{
    int length,i;
    int value,number,location;
    int j,k;
    int flag;

    Sequenlist * L ;
    L=creat();
    length=Length(L);
    printf("The length is %d\n",length);
    printf("Please input the location\n");
    scanf("%d",&location);
    value=GetData(L,location);
    printf("The number is %d\n",value);

    printf("Which number do you want to find?\n"); //查找功能
    scanf("%d",&i);
    value=Find(L,i+1);
    if(value!=0)
    printf("The location is %d\n",value);
    else
    printf("There is no such number!\n");

    printf("Which place do you want to insert?\n"); //插入功能
    scanf("%d",&j);
    printf("Please input the number\n");
    scanf("%d",&number);
    flag=Insert(L,number,j);
    if(flag==0)
    printf("Failing to insert!\n");
    else
    { printf("Done!\n");
    print(L);
    }

    printf("Which place do you want to delete?\n"); //删除功能
    scanf("%d",&k);
    flag=Delete(L,k);
    if(flag==0)
    printf("Failing to delete!\n");
    else
    { printf("Done!\n");
    print(L);
    }
} 

#include<stdio.h>
 #include<stdlib.h>
 #define maxsize 30
 
typedef int datatype;
 typedef struct seqlist{
 datatype data[maxsize];
 int n;
 }seqlist;
 struct seqlist L;
 
//顺序表初始化1-20
 void Stu() {
 printf("\n顺序表正在初始化…\n\n顺序表能储存的数据最多为30个\n\n\n"); 
 int temp=0,n=0;
 for(temp=0;temp<20;temp++){
 L.data[temp]=temp+1;
 n++; 
 }//自定义1-20的数据方便检测程序
 L.n=n;//改变顺序表长度
 };
 
//输出顺序表当前储存的数据
 void Show(){
 int temp;
 printf("\n\n顺序表当前储存的数据:\n “);
 for(temp=0;temp<L.n;temp++){//利用长度输出已储存的数据
 printf(” %d “,L.data[temp]); 
 }
 printf(”\n"); 
 }
 
//在顺序表中输入数据
 void inList(){
 int newn,temp;
 reset1:
 printf("\n请输入需要储存的数据个数：\n");
 scanf("%d",&newn);
 if(newn>maxsize){
 printf("\n顺序表最多储存%d个数据！\n",maxsize);
 goto reset1;
 }
 printf("\n请输入你需要储存的数据：\n");
 for(temp=0;temp<newn;temp++){
 scanf("%d",&L.data[temp]);
 }//输入\更改数据
 for(temp=newn;temp<L.n;temp++){
 L.data[temp]=0;
 }//将不需要储存的数据置零
 L.n=newn;//更新顺序表长度
 printf("\n你插入的数据为：");
 for(temp=0;temp<newn;temp++){
 printf("%d\t",L.data[temp]);
 } 
 }
 
//在顺序表中查找某一个逻辑位置的数据并输出
 void search1(){
 int x;
 reset2://判断输入的逻辑位置
 printf("\n请输入你需要在顺序表中查找的逻辑位置：\n");
 scanf("%d",&x);
 if(x<1||x>maxsize){
 printf("\n逻辑位置最低为1,最高为30!\n");
 goto reset2;
 }
 int temp;
 for(temp=0;temp<L.n;temp++){
 if(x==(temp+1)){
 printf("\n顺序表中这个位置的数据为%d\n",L.data[temp]);
 return ;
 }
 }
 printf(“顺序表中的这个逻辑位置未储存数据！\n”); 
 }
 
//在顺序表中查找数据输入它的逻辑位置
 void search2(){
 int x;
 printf("\n请输入你需要在顺序表中查找的数据：\n");
 scanf("%d",&x);
 int temp;
 for(temp=0;temp<L.n;temp++){
 if(L.data[temp]==x){
 printf("\n查找成功！\n它在顺序表中的逻辑位置为%d\n",temp+1);
 return ;
 }
 }
 printf(“在顺序表中未找到这个数据！”);
 }
 
//在顺序表中插入数据
 void insert(){
 if(L.nmaxsize){//表满则无法插入
 printf(“当前顺序表已储存了30个数据，无法插入!\n”);
 return;
 }
 if(L.n0){//表空则无法插入
 printf(“当前顺序表没有储存数据，无法插入!\n”);
 return;
 }
 int p,x,temp1;
 reset3://判断输入的逻辑位置
 printf("\n请输入你在顺序表中需要插入数据的逻辑位置：\n");
 scanf("%d",&p);
 if(p<1||p>L.n){//插入的逻辑位置不能是顺序表的前驱和最后的后继
 printf("\n插入的逻辑位置最小为1,最高为%d!\n",L.n);
 goto reset3;
 }
 printf("\n请输入该数据：\n");//提示输入并输入
 scanf("%d",&x);
 for(temp1=L.n;temp1>=p;temp1–){
 L.data[temp1+1]=L.data[temp1];
 }
 L.data[p]=x;
 L.n++;
 printf("\n插入数据后变为：");
 for(temp1=0;temp1<L.n;temp1++){
 printf("%d\t",L.data[temp1]);
 }
 }
 
//删除顺序表中的某个位置的数据
 int deletel(){
 if(L.n==0){//表空无法删除
 printf(“当前顺序表没有储存数据，无法删除!\n”);
 return;
 }
 int p,temp;
 reset4:
 printf("\n请输入你在顺序表中需要删除的数据的逻辑位置：\n");
 scanf("%d",&p);
 if(p<1||p>L.n){
 printf(“该逻辑位置没有储存数据!”);
 goto reset4; 
 }
 L.n–;
 for(temp=p;temp<=L.n;temp++){
 L.data[temp-1]=L.data[temp];
 }
 printf(“删除数据后变为：”);
 for(temp=0;temp<L.n;temp++){
 printf("%d\t",L.data[temp]);
 }
 }
 
main(){
 Stu();//顺序表初始化1-20
 inList();//输出顺序表当前储存的数据
 search1();//在顺序表中查找某一个逻辑位置的数据并输出
 search2();//在顺序表中查找数据输入它的逻辑位置
 insert();//在顺序表中插入数据，并输出
 deletel();//删除顺序表中的某个位置的数据，并输出其他的元素
 return 0; 
 }