|
实现顺序表的结构定义基本操作并进行测试。
基本操作为：
初始化，在某编号节点插入元素，删除编号为某节点的元素并返回该元素，取某编号节点，遍历顺序表，清空顺序表，销毁顺序表，顺序表中查找某个值的元素的编号，
------------------
要求：
main中：
1）声明一个顺序表，初始化
2）在该顺序表中插入1,2,3,4,5，每次均在编号1处
3）遍历
4）在编号6插入6
5）分别查找并打印5,6，2这三个元素及其位置
6）在编号2插入7,8,9,10，11
7）遍历
8）删除第一个位置的元素，并打印该元素
9）删除第一个位置的元素，并打印该元素
10）遍历
11）删除第编号为9的元素，并打印该元素，打印此时顺序表长度
12）遍历
13）清空顺序表并打印顺序表长度
14）在第2编号处插入10，结果插入成功，打印“成功插入”，否则打印“插入不成功”
15）依次插入1,2,3,4,5，每次均在最后一个结点的后一个位置处
16）遍历
17）销毁顺序表
#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
#define MAXSIZE 100
#define INITSIZE 100
#define OK 1
#define ERROR 0
typedef struct {
ElemType* elem; //存储空间的基地址
int length; //当前长度
int listsize;
} SqList; //顺序表的结构类型为SqList
Status InitList(SqList& L) {//分配
L.elem = new ElemType[INITSIZE];
if (!L.elem) {
cout << "存储分配失败!" << endl;
exit(1);
return ERROR;
}
L.length = 0; L.listsize = INITSIZE;
}
Status Listinsert(SqList& L, int i, ElemType e){//插入函数
if (i < 1 || i > L.length + 1) return ERROR;
if (L.length >= L.listsize) return ERROR;//老师说ListExtend()可以先不写
//移动元素，对i=L.length+1，无须移动
for (int j = L.length - 1; j >= i - 1; j--)
L.elem[j + 1] = L.elem[j];
L.elem[i - 1] = e; //实际插在数组第i-1个位置
L.length++;
return OK;
}
Status ListDelete(SqList& L, int i) {//删除函数
int e;
if ((i < 1) || (i > L.length)) {
return ERROR; //i值不合法
}
e = L.elem[i - 1];
for (int j = i; j <= L.length - 1; j++) {
L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
}
printf("被删除的元素为%d\n", e);
--L.length; //表长减 1
return OK;
}
Status printList(SqList L)//遍历打印
{
if (L.length == 0)
{
printf("线性表为空\n");
return 0;
}
int i;
for (i = 0; i < L.length; i++)
{
printf("编号为%d,元素值:elem[%d]=%d\n",i+1, i,L.elem[i]);
}
printf("\n");
return OK;
}
Status LocateELem(SqList L, ElemType e) {
//在顺序表中查找值为e的数据元素， 返回其序号
for (int i = 0; i < L.length; i++) {
if (L.elem[i] == e){
return i + 1; //查找成功， 返回序号 i+l
}
}
return ERROR; //查找失败， 返回 0
}
void ClearList(SqList& L) //清空线性表
{
L.length = 0;
}
Status Getlength(SqList L){
return L.length;
}
void DestroyList_Sq(SqList& L) //销毁线性表
{
free(L.elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
}
int main() {
SqList lists;
InitList(lists);//1）声明一个顺序表，初始化
for (int i = 1; i <= 6; i++) {//2）在该顺序表中插入1,2,3,4,5，每次均在编号1处
Listinsert(lists, 1, i);
}
printList(lists);//3）遍历
Listinsert(lists, 6, 6);//4）在编号6插入6
printf("元素 5 的位置是%d\n",LocateELem(lists, 5));//5）分别查找并打印5,6，2这三个元素及其位置
printf("元素 6 的位置是%d\n",LocateELem(lists, 6));
printf("元素 2 的位置是%d\n",LocateELem(lists, 2));
for (int i = 7; i <= 11; i++) {//6）在编号2插入7,8,9,10，11
Listinsert(lists, 2, i);
}
printList(lists);//7)遍历
ListDelete(lists, 1);//8）删除第一个位置的元素，并打印该元素
ListDelete(lists, 1);//9）删除第一个位置的元素，并打印该元素
printList(lists);//遍历
ListDelete(lists, 9);//11）删除第编号为9的元素，并打印该元素，
printf("此时表的长度为%d\n",Getlength(lists));//打印此时顺序表长度
printList(lists);//12)遍历
ClearList(lists); //13）清空顺序表
printf("此时表的长度为%d\n", Getlength(lists));//13）并打印顺序表长度
if (Listinsert(lists, 2, 10)) {//14）在第2编号处插入10，结果插入成功，打印“成功插入”，否则打印“插入不成功”
printf("成功插入\n");//结果插入成功，打印“成功插入”
}
else {
printf("插入不成功\n");//否则打印“插入不成功
}
for (int i = 1; i <= 5; i++) {//15）依次插入1,2,3,4,5，每次均在最后一个结点的后一个位置处
Listinsert(lists, Getlength(lists)+1, i);
}
printList(lists);//16）遍历
DestroyList_Sq(lists);//17）销毁顺序表
printf("线性表已销毁！");
}
|