一起学习C++ 之 DataStruct

线性表 之 顺序表
#include <iostream>
using namespace std;
const int LIST_INIT_SIZE = 100;
const int LIST_INCREMENT_SIZE = 10;
typedef int elemtype;
typedef struct Sqlist
{
elemtype *elem;//存储数组元素的第一个地址
int length;//length当前数组有效元素的个数
int listsize;//能容纳的元素个数
int increentsize;//自动增加的元素个数
}Sqlist;
//初始化Initlist(&L, maxsize, incresize)，建立一个空的线性表
void InitSqlst_sq(Sqlist &L,int maxsize = LIST_INCREMENT_SIZE,int incresize = LIST_INCREMENT_SIZE)
{
L.elem = new elemtype[LIST_INCREMENT_SIZE];
L.length = 0;
L.listsize = maxsize;
L.increentsize = incresize;
}
//追加空间Increment(&L)，当线性表空间不足已满时，追加空间
void Increment_sq(Sqlist L)
{
elemtype *a = new elemtype[L.increentsize+L.listsize];
for (int i = 0; i < L.length; i++)
{
a[i] = L.elem[i];
}
delete L.elem;
L.elem = a;
L.listsize += L.increentsize;
}
//插入运算Insert(&L,i,e), 线性表L的第 i 个位置上插入一个新元素e
void IsertSqList_sq(Sqlist &L, int i, elemtype e)
{
if ((i<1) || (i>L.length + 1))
{
cout << "i 的值不合法！";
return;
}
if (L.length >= L.listsize)
Increment_sq(L);
if (L.length < L.listsize)
{
int *p = &(L.elem[i - 1]);
int *q = &(L.elem[L.length - 1]);
for (; q >= p; --q)
*(q + 1) = *q;
L.elem[i - 1] = e;
++L.length;
}
}
//删除运算Delete(&L,i,&e),线性表L中删除序号为i的数据元素
void DeleteSqlist_sq(Sqlist &L, int i, elemtype e)
{
int *p = &(L.elem[i - 1]);
int *q = &(L.elem[L.length - 1]);
e = L.elem[i - 1];
for (; p <= q; ++p)
*p = *(p + 1);
--L.length;
}
// 显示元素Display(L)，逐个显示线性表中元素的值
void Display_sq(Sqlist &L)
{
int *p = L.elem;
if (L.length == 0)
cout << "线性表为空！";
else
for (; p < &(L.elem[L.length]); ++p)
cout << *p << " ";
}
/*定位算法Locate(L,e),线性表L中查找值为e的数据元素，
其结果返回在L中首次出现的值为e的那个元素的序号或地址，称为查找成功;
否则，在L中未找到值为e的数据元素，返回0表示查找失败。 */
int Locate_sq(Sqlist L, elemtype &e)
{
int i = 0;
for (; i < L.length; ++i)
if (L.elem[i] == e)
return i + 1;
return 0;
}
//取元素Get(L,i),返回线性表L中序号为i的数据值
elemtype Get_sq(Sqlist L, int i)
{
if ((i<1) || (i>L.length)) return NULL;
else return L.elem[i - 1];
}
//求线性表的长度Length(L)
int Length_sq(Sqlist L)
{
return L.length;
}
int main()
{
Sqlist L;
elemtype e;
int i, j, k;
do
{
cout << ("\n\n\n\n");
cout << ("\t\t\t 线性表子系统\n");
cout << "\t\t*******************************\n";
cout << "\t\t* 1----初始化表　 　　*\n";
cout << "\t\t* 2----插入 *\n";
cout << "\t\t* 3----删　　除　　　　*\n";
cout << "\t\t* 4----定　　位　　　　*\n";
cout << "\t\t* 6----求 表 长　　　　*\n";
cout << "\t\t* 7----显　　示　　　　*\n";
cout << "\t\t* 0----返　　回　　　　*\n";
cout << "\t\t*******************************\n";
cout << "\t\t 请选择菜单项0－7：";
cin >> k;
switch (k)
{
case 1 :
InitSqlst_sq(L);
break;
case 2 :
cout << "\n 请输入插入的位置i:"; cin >> i;
cout << " 请输入数据e:"; cin >> e;
IsertSqList_sq(L,i,e);
break;
case 3 :
cout << "\n 请输入要删除元素的位置i:";
cin >> i;
DeleteSqlist_sq(L,i,e);
break;
case 4://在线性表中确定元素e的位置
cout << "\n 请输入要定位的元素e:";
cin >> e;
j = Locate_sq(L, e);
if (j != 0)
{
cout << "线性表";
Display_sq(L);
cout << "中e所在的位置是" << j;
}
else
cout << "线性表中无此元素!!\n";
break;
case 5://求线性表L中序号为i的数据值
cout << "\n 请输入要查找的序号i:";
cin >> i;
e = Get_sq(L, i);
if (e != 0)
{
cout << "线性表";
Display_sq(L);
cout << "中序号为" << i << "的元素是" << e;
}
else
cout << "i值不合法!\n";
break;
case 6://求表长
cout << "\n 线性表的表长是:" << Length_sq(L) << endl;
break;
case 7://输出线性表
cout << "\n线性表为：";
Display_sq(L);
break;
default:
break;
}
} while (k!=0);
return 0;
}