数据结构 顺序表（静态分配内存）
文章目录
数据结构 顺序表（静态分配内存）
前言
一、顺序表
二、代码部分
1.头文件
2.预定义
3.定义存储结构
4.顺序表初始化
5.顺序表重置为空表
6.判断是否是空表
7.按位查找顺序表的元素，并返回第i个元素，传入e的引用来存储
8.按值查找顺序表的元素,并传入i的引用存储该元素的位置，若无则返回0
9.顺序表插入数据元素
10.顺序表删除数据元素
11.顺序表遍历
12.创建一个顺序表
13.主函数
总结



前言

数据结构要考试，写写代码复习复习

一、顺序表
顺序表有两种。一种为静态分配内存，另一种为动态分配内存。本文提供了一种静态分配内存的顺序表的简单实现。参考了数据结构（严蔚敏C语言版）教材。代码仅供参考，学习，

运行环境是Visual Studio 2019

有些判断输入是否合法的说明就跳过了
二、代码部分
1.头文件
建立是cpp文件，用c文件也可以，只是需要改变一下读写数据的操作。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
using namespace std;

2.预定义
预先定义一些内容，方便后续操作

这里追求方便，定义了ElemType为int类型，读者可以自己更改为其他类型
#define MAXSIZE 10
#define OK 1 //返回OK，代表操作成功
#define ERROR 0 //返回ERROR，代表操作失败
typedef int ElemType;  //之后出现的ElemType为int类型，本代码默认数据类型是int

3.定义存储结构
使用结构体定义了存储结构。使用了数组来存储数据
struct SqList
{
    ElemType data[MAXSIZE];  //用数组来存取元素
    int length;  //定义顺序表当前长度
};

4.顺序表初始化
初始化很简单，只需要将数组的元素全部设置为0，并将表长也设置为0就可以
int InitList(SqList& L)
{
    for (int i = 0; i < MAXSIZE; i++)
    {
        L.data[i] = 0; //数组元素初始化为0
    }
    L.length = 0;   //顺序表长度初始化为0
    cout << "已成功初始化顺序表" << endl;
    return OK;
}

5.顺序表重置为空表
顺序表的重置操作和初始化类似，不做多解释
int ClearList(SqList& L)
{
    for (int i = 0; i < MAXSIZE; i++)
    {
        L.data[i] = 0; //数组元素初始化为0
    }
    L.length = 0;   //顺序表长度初始化为0
    cout << "已成功重置顺序表" << endl;
    return OK; 
}


6.判断是否是空表
也很简单，只需要判断表长是否为0即可
bool ListEmpty(SqList L)
{   
    if (L.length == 0)
    {
        cout << "顺序表是空表" << endl;
        return true;
    }
    else
    {
        cout << "顺序表不是空表" << endl;
        return false;
    }
}

7.按位查找顺序表的元素，并返回第i个元素，传入e的引用来存储

输入参数为顺序表L，需要查找的位置，一个元素e的引用，用于保存数据元素e。
返回值为是否查找到，1为找到，0为没找到。
如果不需要用到这个元素，可以重载一下这个函数。
int GetElem(SqList L, int i,ElemType &e)
{
    if (i<1 || i>L.length)
    {
        cout << "请输入正确的元素位序" << endl;
        return ERROR;
    }
    else
    {
        e = L.data[i - 1];
        return OK;
    }
}

8.按值查找顺序表的元素,并传入i的引用存储该元素的位置，若无则返回0

输入参数为线性表L，需要查找的数据元素e，引用i用来记录该数据元素的位置
返回值为返回值为是否查找到，1为找到，0为没找到。
也可以重载函数为其他形式，方便操作。
这里按值查找本质上也是遍历了一遍这个顺序表，找到第一个等于e的元素就返回
int LocateElem(SqList L, ElemType e,int &i)
{
    for (int j = 0; j < L.length; j++)
    {
        if (L.data[j] == e)
        {
            i = j + 1;
            return OK;
        }
    }
    return ERROR;
}

9.顺序表插入数据元素

输入参数线性表L，插入的位置i，插入的元素e。
若在i位置插入，对应数组的下表为i-1，需要让i位置之后的元素都往后移动一个位置。表长+1
int ListInsert(SqList& L, int i, ElemType e)
{
    if (i<1 || i>L.length)
    {
        cout << "请输入正确的元素位序" << endl;
        return ERROR;
    }
    if (L.length + 1 > MAXSIZE)
    {
        cout << "存储空间不足" << endl;
        return ERROR;
    }
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return OK;
}

10.顺序表删除数据元素

输入参数线性表L，删除的位置i，引用e用来记录删除的元素
若删除i位置元素，需要让i位置之后的元素都往前移动一个位置。表长-1
int ListDelete(SqList& L, int i, ElemType &e)
{
    if (i<1 || i>L.length)
    {
        cout << "请输入正确的元素位序" << endl;
        return ERROR;
    }
    e = L.data[i - 1];
    for (int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return OK;
}

11.顺序表遍历

很简单，不过多解释
int TraverseList(SqList L)
{
    if (L.length == 0)
    {
        cout << "顺序表是空表" << endl;
        return ERROR;
    }
    else
    {
        cout << "该顺序表中的数据元素如下" << endl;
        for (int i = 0; i < L.length; i++)
        {
            if (i == 0)
            {
                cout << L.data[i];
            }
            else
            {
                cout << " " << L.data[i];
            }
        }
        cout << endl;
        return OK;
    }
}

12.创建一个顺序表
 
方便创建顺序表的一个函数。
int CreateList(SqList &L)
{
    cout << "请输入顺序表中元素的个数" << endl;
    cin >> L.length;
    cout << "请输入顺序表中的数据元素，以空格分隔" << endl;
    for (int i = 0; i < L.length; i++)
    {
        cin >> L.data[i];
    }
    return OK;
}

13.主函数
 
主函数就可以看读者需求来测试了
int main()
{
    SqList L;
    return 0;
}

总结
数据结构还是得多写代码。

数据结构 顺序表（动态分配内存）
文章目录
数据结构 顺序表（动态分配内存）
前言
一、顺序表
二、代码部分
1.头文件
2.预定义
3.定义存储结构
4.顺序表初始化
5.创建顺序表
6.遍历顺序表
7.销毁顺序表
8.重置顺序表
9.判断顺序表是否为空
10.按位查找顺序表
11.按值查找顺序表
12.顺序表某一位置插入元素
13.顺序表删除某一位置元素
14.主函数
总结



前言
刚刚写了个静态分配内存的顺序表，再写个动态分配内存的顺序表对比

前一篇文章，静态分配内存的顺序表

一、顺序表
顺序表有两种。一种为静态分配内存，另一种为动态分配内存。本文提供了一种动态分配内存的顺序表的简单实现。参考了数据结构（严蔚敏C语言版）教材。代码仅供参考，学习，

运行环境是Visual Studio 2019

有些判断输入是否合法的说明就跳过了，代码中可能没有体现，读者可以自行补充，
二、代码部分
1.头文件
建立是cpp文件，用c文件也可以，只是需要改变一下读写数据的操作。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
using namespace std;

2.预定义
预先定义一些内容，方便后续操作

这里追求方便，定义了ElemType为int类型，读者可以自己更改为其他类型

其中INITSIZE是初始的顺序表大小

LISTINCREMENT 是每次新增加的大小
#define OK 1 //返回OK，代表操作成功
#define ERROR 0 //返回ERROR，代表操作失败
#define INITSIZE 10
#define LISTINCREMENT 5
typedef int ElemType;  //之后出现的ElemType为int类型，本代码默认数据类型是int

3.定义存储结构
使用结构体定义了存储结构
struct SqList
{
    ElemType* data;  //定义存储空间的基地址
    int length;   //定义顺序表当前长度
    int listsize; //定义顺序表的最大存储容量
};

4.顺序表初始化
初始化需要动态分配内存，使用的c语言的malloc函数，注意malloc的返回值需要强制类型转换。
int InitList(SqList& L)
{
    L.data = (ElemType*)malloc(INITSIZE * sizeof(ElemType));
    if (!L.data)
    {
        cout << "存储空间分配失败" << endl;
        return ERROR;
    }
    L.length = 0;
    L.listsize = INITSIZE;  
    cout << "顺序表已经构建成功" << endl;
    return OK;
}


5.创建顺序表
线性表创建时用到了realloc函数，用于重新分配内存空间

realloc()函数：重新分配空间

参数：原空间基址，现需空间大小

返回值：1. 成功：新空间地址(本质上是一个数值) 2. 失败：NULL

当我们在输入线性表元素个数大于构造空线性表给线性表分配初始容量时，要一直开辟新空间，直到开辟的空间大于需要的空间为止。
int CreateList(SqList& L)
{
    cout << "请输入顺序表中元素的个数" << endl;
    cin >> L.length;
    while (L.length>L.listsize)
    {
        L.data = (ElemType*)realloc(L.data, (L.length + LISTINCREMENT) * sizeof(ElemType));
        L.listsize = L.length + LISTINCREMENT;
    }
    cout << "请输入顺序表中的数据元素，以空格分隔" << endl;
    for (int i = 0; i < L.length; i++)
    {
        cin >> L.data[i];
    }
    return OK;
}

6.遍历顺序表
很简单，不多做说明
int TraverseList(SqList L)
{
    if (L.length == 0)
    {
        cout << "顺序表是空表" << endl;
        return ERROR;
    }
    else
    {
        cout << "该顺序表中的数据元素如下" << endl;
        for (int i = 0; i < L.length; i++)
        {
            if (i == 0)
            {
                cout << L.data[i];
            }
            else
            {
                cout << " " << L.data[i];
            }
        }
        cout << endl;
        return OK;
    }
}

7.销毁顺序表
利用free()函数释放内存空间

并且将L.data指向NULL防止出现野指针
int DistoryList(SqList& L)
{
    if (!L.data)
    {
        cout << "未建立线性表" << endl;
        return ERROR;
    }
    free(L.data);
    L.length = 0;
    L.listsize = 0;
    L.data = NULL; //防止出现野指针
    cout << "线性表已经销毁" << endl;
    return OK;
}

8.重置顺序表
很简单就不多说了
int ClearList(SqList& L) 
{
    if (!L.data)
    {
        cout << "未建立线性表" << endl;
        return ERROR;
    }
    L.length = 0;
    L.listsize = INITSIZE;
    free(L.data);
    L.data = (ElemType*)malloc(INITSIZE * sizeof(ElemType));
    return OK;
}

9.判断顺序表是否为空
也很简单
bool ListEmpty(SqList L)
{
    if (L.length == 0)
    {
        cout << "线性表是空表" << endl;
        return false;
    }
    else
    {
        cout<< "线性表不是空表" << endl;
        return true;
    }
}

10.按位查找顺序表

输入参数为线性表L，查找的位置index
很简单，和静态分配的类似
有需求可以自行重载或者改写函数
int GetElem(SqList L, int index)
{
    if (index < 1 || index > L.length) 
    {
        cout << "请输入正确的元素位序" << endl;
        return ERROR;
    }
    else
    {
        cout << "第" << index << "个位置的元素为：" << L.data[index - 1] << endl;
    }
    return OK;
}

11.按值查找顺序表

输入参数为线性表L，查找的元素e
很简单，和静态分配的类似
有需求可以自行重载或者改写函数
int LocateElem(SqList L, ElemType e)
{
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
        {
            cout << "该元素是该顺序表中的第" << i + 1 << "个元素" << endl;
            return OK;
        }
    }
    return ERROR;
}

12.顺序表某一位置插入元素
 注意插入元素后是否会导致超出内存，要判断是否需要进一步动态分布新的内存空间。

其余操作和静态分配类似
int ListInsert(SqList& L, int i, ElemType e)
{
    if (i < 1 || i > L.length + 1)        
    {
        cout << "插入位置不合法" << endl;
        return ERROR;
    }
    if (L.length + 1 > L.listsize)
    {
        L.data = (ElemType*)realloc(L.data, (L.length + LISTINCREMENT) * sizeof(ElemType));
        L.listsize = L.length + LISTINCREMENT;
    }
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return OK;
}

13.顺序表删除某一位置元素
 操作和静态分配类似
int ListDelete(SqList& L, int i)
{
    if (i<1 || i>L.length)
    {
        cout << "删除位置不合法" << endl;
        return ERROR;
    }
    cout << "删除的元素为" << L.data[i - 1] << endl;
    for (int j = i; j < L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return OK;
}

14.主函数
 测试用的
int main()
{
    SqList L;
    InitList(L);
    CreateList(L);
    TraverseList(L);
    ListInsert(L,1,2);
    TraverseList(L);
    ListDelete(L, 2);
    TraverseList(L);
    return 0;
}

总结
主要是需要注意如何动态分配内存，这里使用了realloc()函数。

整体而言和静态分配内存的顺序表类似

C语言 算法与数据结构 顺序表 基本操作及实验案例
实验要求：
1．(80%)完成顺序表的基本运算：初始化、显示、求长度、判空、判满、插入、删除、取元素等，并编写主函数测试算法。

2.(90%)设计算法：将一个元素插入到有序的顺序表中，使顺序表仍有序，并编写主函数测试算法。

3.（100%）设A和B两个顺序表，其元素按从小到大的顺序排列。编写一个A和B中所有元素组成一个新的从小到大的有序顺序表C的算法，并编写主函数测试算法。

提示：（1）算法：有序表合并。

（2）有序表的产生，可以人为输入，也可以调用内容2的算法实现。
//包含实验三个实验内容，part 1,2,3
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>	//采用非阻塞式输入，方便选项跳转
#include<time.h>	//用于产生随机数模拟有序数列

#define MAXSIZE 1000	//设置最大数列大小

typedef int elemtype;	//定义元素类型

typedef struct	//定义结构体数列
{
	elemtype data[MAXSIZE];
	int last;
} datalist;
//函数声明区
//-----------------------------------------------------------------------
//第一部分
int part1(void);
//选择菜单
char choiceitem();
//初始化数列
datalist * defaultlist(void);
//追加元素到列表
int addinfo(datalist * pl,int times);
//从列表删除元素
int deleteinfo(datalist * pl,int space);
//检查列表是否为空，空返回1否则0
int ifempty(datalist * pl);
//检查列表是否已满，满返回1否则0
int iffull(datalist * pl);
//改变元素的值
int changeinfo(datalist * pl,int space,int change);
//输出列表
void outputlist(datalist * pl);
//返回列表长度
int lenthlist(datalist * pl);
//插入元素到列表
int insertinfo(datalist * pl,int space,int num);
//清空列表
void deletelist(datalist * pl);
//-----------------------------------------------------------------------
//第二部分
int part2(void);
//产生一个随机有序数列
void rulenummade(datalist * pl);
//计算插入值应该插入的位置
int findspace(datalist * pl,int num);
//-----------------------------------------------------------------------
//第三部分
int part3(void);
//顺序表合并到新表
datalist * doublerulelistcontact(datalist * pc,datalist * pa,datalist * pb);

int main(void)
{
	system("color f0");
	system("title Main 功能选择 dev: Ice2Faith");
    char sel;
	do	//直到用户需要退出程序退出循环结束程序
	{
		printf("\twelcome here\n\n");
		printf("\t算法与数据结构 顺序表\n\n");//功能提示输出和获取进去功能版块
        printf("---------------------------------\n");
		printf("请选择功能:\n");
		printf("\t1.第一部分\n");
		printf("\t2.第二部分\n");
		printf("\t3.第三部分\n");
		printf("\t0.退出程序\n/> ");
		do	//直到获取到正确的选项值退出循环
		sel=getch();
		while(sel<'0'||sel>'3');
		system("cls");	//清屏进入功能版块
		switch(sel)
		{
			case '1':
				part1();
				break;
			case '2':
				part2();
				break;
			case '3':
				part3();
				break;
			case '0':
				break;
		}
	}while(sel!='0');


	return 0;
}

//第一部分
int part1(void)
{
	system("title Part 1 常规顺序表操作 dev: Ice2Faith");
	datalist * pl=defaultlist();	//初始化数列
	char chioce;
	do	//直到用户需要退出该循环为止退出循环
    {
        chioce=choiceitem();	//调用选择方法获得选择项的值
        switch(chioce)	//进入选择项跳转
        {
        case '1':
            outputlist(pl);	//输出数列
            break;
        case '2':
            {
                int times;	//追加数列
                fflush(stdin);
                printf("请问您需要添加几个元素:\n/> ");
                scanf("%d",&times);
                printf("请输入 %d 个元素:\n/> ",times);
                if(addinfo(pl,times)==-1)
					printf("操作失败，元素个数将会超出\n\n");
                break;
            }

        case '3':
            {
                int space;	//删除元素
                fflush(stdin);
                printf("您想删除第几个元素:\n/> ");
                scanf("%d",&space);
                if(deleteinfo(pl,space)==-1)
					printf("操作失败，该位置不合法\n\n");
                break;
            }

        case '4':
            {
                int space1,change;	//改变元素的值
                fflush(stdin);
                printf("您要改变第几个元素:\n/> ");
                scanf("%d",&space1);
                fflush(stdin);
                printf("要将它改变为多少:\n/> ");
                scanf("%d",&change);
                if(changeinfo(pl,space1,change)==-1)
					printf("操作失败，该位置不合法\n\n");
                break;
            }
        case '5':
            {
                int space2,num;	//插入元素
                fflush(stdin);
                printf("您想插入到第几个位置:\n/> ");
                scanf("%d",&space2);
                fflush(stdin);
                printf("请输入您要插入的值:\n/> ");
                scanf("%d",&num);
                if(insertinfo(pl,space2,num)==-1)
					printf("操作失败，该位置不合法\n\n");
                break;
            }
        case '6':
            deletelist(pl);	//清空数列
            break;
        case '7':
            system("cls");	//清屏
            break;
        case '8':
            system("mode con cols=55 lines=40");	//设置合适窗口大小
            break;
        }
        if(chioce=='0')	//退出版块提示
            printf("您这样做将会失去我!\n");
        if(chioce!='7'&&chioce!='8')	//控制下一选项前的暂停
        {
            printf("\n");
            system("pause");
        }
    }while(chioce!='0');
    free(pl);	//释放pl空间
    system("cls");
	return 0;
}

//选择菜单
char choiceitem()
{
	char choice;
	printf("\twelcome here\n\n");	//输出选择项和说明
	printf("请选择:\n\n");
	printf("---------------------------------\n");
	printf("\t1.查看顺序表\n");
	printf("\t2.添加元素\n");
	printf("\t3.删除元素\n");
	printf("\t4.改变元素\n");
	printf("\t5.插入元素\n");
	printf("\t6.清空顺序表\n");
	printf("\t7.清屏\n");
	printf("\t8.调整窗口到建议大小\n");
	printf("\t0.退出本部分\n\n");
	printf("---------------------------------\n/> ");
	do	//获取选择项，直到选择项合法为止并输出选择项
	{
	   choice=getch();
	}
	while(choice<'0'||choice>'8');
	printf("%c\n",choice);
	return choice;
}

//初始化数列
datalist * defaultlist(void)
{
	datalist * pl;
	pl=(datalist *)malloc(sizeof(datalist));	//申请并初始化一个datalist型空间且返回空间地址
	pl->last=0;
	return pl;
}

//追加元素到列表
int addinfo(datalist * pl,int times)
{
	//check whether more than maxsize
	if(pl->last+times>MAXSIZE-1)	//检测追加元素会不会溢出，不会则进行添加操作，长度增加
		return -1;
	for(int i=0;i<times;i++)
	{
		scanf("%d",&(pl->data[pl->last+i]));
	}
	pl->last+=times;
	return 1;
}

//从列表删除元素
int deleteinfo(datalist * pl,int space)
{
	space-=1;
	if(space<0 ||space>=pl->last)	//检查删除元素是否合法，合法则进行移位覆盖删除，长度-1
		return -1;
	for(int i=space;i<=pl->last;i++)
		pl->data[i]=pl->data[i+1];
	pl->last--;
	return 1;
}

//检查列表是否为空，空返回1否则0
int ifempty(datalist * pl)
{
	return pl->last==0?1:0;	//检查数列是否为空，空则返回1否则返回0
}

//检查列表是否已满，满返回1否则0
int iffull(datalist * pl)
{
	return pl->last==MAXSIZE-1?1:0;	//检查数列是否已满，满则返回1否则返回0
}

//改变元素的值
int changeinfo(datalist * pl,int space,int change)
{
	space-=1;
	if(space<0 ||space>pl->last-1)	//如果改变值部分合法则进行修改
		return -1;
	pl->data[space]=change;
	return 1;
}

//输出列表
void outputlist(datalist * pl)
{
    printf(">>> \t");
	if(pl->last==0)	//判断长度是否为空，并提示
		printf("此处为空，请添加！！");
	for(int i=0;i<pl->last;i++)	//格式化输出数列并换行
		printf("[%d]\t",pl->data[i]);
	printf("\n");
}

//返回列表长度
int lenthlist(datalist * pl)
{
	return pl->last;	//返回数列长度
}

//插入元素到列表
int insertinfo(datalist * pl,int space,int num)
{
	space-=1;
	if(space<0 ||space>pl->last)	//检查插入位置是否合法
		return -1;
	for(int i=pl->last;i>space;i--)	//将插入位置以后的数列向后移动一位
		pl->data[i]=pl->data[i-1];
    pl->data[space]=num;	//插入需要插入的值，数列长度+1
	pl->last++;
	return 1;
}

//清空列表
void deletelist(datalist * pl)
{
    pl->last=0;	//重置数列长度
}

//-----------------------------------------------------------------------
//第二部分
int part2(void)
{
    system("title Part 2 插入元素到有序顺序表 dev: Ice2Faith");
	datalist * pl;	//为pl数列申请空间做初始化
	pl=defaultlist();
	char con='c';
    rulenummade(pl);	//调用方法得到一个有序数列
	do	//直到用户需要退出（输入q）该部分
    {
        printf("已为您准备好一切，开始:\n\n");
        printf("---------------------------------\n");
        printf("这是您的默认有序列表\n\n");	//输出初始有序数列
        outputlist(pl);
        printf("---------------------------------\n");
        printf("请输入需要插入的值:\n/> ");	//获得用户需要插入的值并进行调用方法插入
        int num;
        fflush(stdin);
        scanf("%d",&num);
        insertinfo(pl,findspace(pl,num),num);
        printf("这是您插入值之后的结果\n\n");
        outputlist(pl);
        printf("---------------------------------\n");
        printf("如果您想退出第二部分, 请输入 \'Q\',否则继续:\n/> ");	//获得用户是否需要退出该部分
        fflush(stdin);
        con=getch();
        if(con!='Q'||con!='q')
            system("cls");
    }while(con!='Q'&&con!='q');
    free(pl);
    return 0;
}
//产生一个随机有序数列
void rulenummade(datalist * pl)
{
	srand((unsigned)time+rand());
	int lenth=rand()%300+10;	//决定所产生的随机有序数列的元素个数
	int before=rand()%20+1;		//决定初始随机数大小及后面进行迭代存储
	for(int i=0;i<=lenth;i++)	//循环lenth次，传入一个有序数列，每个元素在之前元素基础上随机加一个整数
	{
		srand((unsigned)time+rand());
		pl->data[i]=before;
		before+=rand()%8;
	}
	pl->last=lenth+1;	//记录数列长度
}
//计算插入值应该插入的位置
int findspace(datalist * pl,int num)
{
    int i=0;	//遍历找到应该插入的位置
    while(num>pl->data[i]&&i<pl->last)
        i++;
    return i>pl->last?pl->last:++i;	//如果遍历结束还没有找到位置，则应插入到最后位置，否则返回找到的位置
}

//-----------------------------------------------------------------------
//第三部分
int part3(void)
{
    system("title Part 3 两个有序数列的整合合并 dev: Ice2Faith");
	datalist * pl;	//申请并初始化两个数列pl,pk
	pl=defaultlist();
	datalist * pk;
	pk=defaultlist();
	datalist * pc;
	pc=defaultlist();
	char con='c';
	do 		//用户不退出则继续循环
    {
       	rulenummade(pl); 	//调用方法产生两个随机有序数列
        rulenummade(pk);
        printf("已为您准备好一切，开始:\n\n");
        printf("---------------------------------\n");
        printf("您的默认有序数列:\n\n");	//输出初始的随机有序数列
        outputlist(pl);
        printf("---------------------------------\n");
        outputlist(pk);
        printf("---------------------------------\n");
        printf("请继续，即将开始合并：\n");
        system("pause");
        printf("合并之后的有序数列:\n\n");	//输出合并后的有序数列一pl
        outputlist(doublerulelistcontact(pc,pl,pk));    //调用合并方法合并数列到pc返回给输出函数输出结果
        printf("---------------------------------\n");
        printf("如果您想退出第三部分, 请输入 \'Q\',否则继续:\n/> ");	//提示用户选择是否退出第三部分，输入‘q'退出
        fflush(stdin);
        con=getch();
        if(con!='Q'||con!='q')
            system("cls");
    }while(con!='Q'&&con!='q');
    free(pl);	//释放pl,pk的空间
    free(pk);
    free(pc);
    return 0;
}

//顺序表合并到新表
datalist * doublerulelistcontact(datalist * pc,datalist * pa,datalist * pb)
{
	int i,j,k;
	i=0;
	j=0;
	k=0;
	while(pa->last>i && pb->last>j) //循环到两数列其中一个结束并排序到存储数列中
	{
		if(pa->data[i]<pb->data[j])
			pc->data[k++]=pa->data[i++];
		else
			pc->data[k++]=pb->data[j++];
	}
	while(pa->last>i)   //两个循环将剩下一个未结束的数列复制到存储数列中
		pc->data[k++]=pa->data[i++];
	while(pb->last>j)
		pc->data[k++]=pb->data[j++];
	pc->last=pa->last+pb->last; //更改存储数列的长度
	return pc;  //返回结果数列
}

一、实验目的

1、熟练掌握线性表的结构特点，掌握顺序表的基本操作。
2、巩固 C++相关的程序设计方法与技术。
3、学会使用顺序表解决实际问题。 

二、实验内容

1、顺序表的建立与操作实现

建立n个元素的顺序表（n的大小和表里数据自己确定），实现相关的操作：输出，插

入，删除，查找等功能。编写完整程序实现，程序语言不限定，使用技术形式不定。

2、实际问题的解决（*）

使用顺序表来实现约瑟夫环问题。
三、实验步骤

1、依据实验内容分别说明实验程序中用到的数据类型的定义；

2、相关操作的算法表达；

3、完整程序；

4、总结、运行结果和分析。

5、总体收获和不足，疑问等。
四、代码实现
1、设计模板类   "list.h"

const int Size = 100;
template <class Type>        //定义模板类SeqList  
class SeqList
{
public:
	SeqList() { length = 0; }            //无参构造函数，建立空顺序表  
	SeqList(Type a[], int n);       //有参构造函数，建立长度为n的顺序表  
	~SeqList() { }                   //析构函数  
	int Length() { return length; }        //求线性表的长度  
	Type Get(int i);               //按位查找，在表中查找第i个元素  
	int Locate(Type x);           //按值查找，在表中查找值为x的元素序号  
	void Insert(int i, Type x);       //插入操作，在表中第i个位置插入值为x的元素  
	Type Delete(int i);              //删除操作，删除表的第i个元素  
	void PrintList();                     //遍历操作，按序号依次输出各元素  
private:
	Type data[Size];           //存放数据元素的数组  
	int length;                        //线性表的长度  
};
2、函数实现代码  "list.cpp"
#include "list.h"  

template <class Type>
SeqList<Type> ::SeqList(Type a[], int n)
{
	if (n > Size) throw "错误";
	for (int i = 0; i < n; i++)
	{
		data[i] = a[i];
	}
	length = n;
}

template <class Type>
Type SeqList<Type>::Get(int i)
{
	if (i < 1 && i > length) throw "查找位置非法";
	else return data[i - 1];
}

template <class Type>
int SeqList<Type> ::Locate(Type x)
{
	for (int i = 0; i < length; i++)
	{
		if (data[i] == x) return i + 1;
	}
	return 0;                           
}

template <class Type>
void SeqList<Type> ::Insert(int i, Type x)
{
	if (length >= Size) throw "上溢错误";
	if (i < 1 || i > length + 1) throw "位置";
	for (int j = length; j >= i; j--)
	{
		data[j] = data[j - 1];             //注意第j个元素存在数组下标为j-1处
	}
	data[i - 1] = x;
	length++;
}

template <class Type>
Type SeqList<Type> ::Delete(int i)
{
	if (length == 0) throw "下溢";
	if (i < 1 || i > length) throw "位置";
	Type x = data[i - 1];              //取出位置i的数据 
	for (int j = i; j < length; j++)
		data[j - 1] = data[j];        //注意此处j已经是元素所在的数组下标  
	length--;
	return x;
}

template <class Type>
void SeqList<Type> ::PrintList()
{
	for (int i = 0; i < length; i++)
	{
		cout << data[i]<<' ';                   //遍历输出数据  
	}
	cout << endl << endl;
}

3、主函数  "listmain.cpp"
#include <iostream>            
using namespace std;
#include "list.cpp"          
void main()
{
	int student[7] = { 11,22,33,44,55,66,77 };
	SeqList<int> ScoreList(student, 7);
	cout << ">>>插入前数据为：" << endl;
	ScoreList.PrintList();              
	try
	{
		ScoreList.Insert(1, 88);
	}
	catch (char *s)
	{
		cout << s << endl;
	}
	cout << ">>>插入后数据为：" << endl;
	ScoreList.PrintList();              
	cout << ">>>值为33的元素位置为:";
	cout << ScoreList.Locate(33) << endl<<endl; 
	cout << ">>>第二个元素的值为：" ;
	cout << ScoreList.Get(2) << endl<<endl;
	cout << ">>>删除第2个元素，删除前数据为：" << endl;
	ScoreList.PrintList();             
	try
	{
		ScoreList.Delete(2);                
	}
	catch (char *s)
	{
		cout << s << endl;
	}
	cout << ">>>删除后数据为：" << endl;
	ScoreList.PrintList();              
}

五、实验结果


六、问题分析
1、对于C++面向对象的熟练程度不够；
2、算法分析不足，元素所在数组下标分析容易出现错误；
七、实验总结
在编写过程中，由于许久没有用到C++进行编程，在代码实现过程中总不太熟练，所以应先温习C++面向对象，能使代码编写流畅，在分析问题中总有不足，应加强对算法的分析。