【数据结构 C++和Python实现】线性表

C++ 线性表

#include<iostream>
#define MaxSize 100
typedef int ElemType;
typedef struct {
ElemType* elem; // 顺序表的基地址
int length; // 顺序表的长度
}Sqlist;

/*******************************************************************************/
/*顺序表初始化*/
/*******************************************************************************/
bool InitList(Sqlist& L) {
L.elem = new int[MaxSize]; // 为顺序表动态分配Maxsize个空间
if (!L.elem) return false; // 分配空间失败
L.length = 0;
return true;
}

/*******************************************************************************/
/*顺序表创建*/
/*******************************************************************************/
bool CreateList(Sqlist& L) {
int x, i = 0;
std::cout << "输入顺序表数据元素（输入-1结束）："<<std::endl;
std::cin >> x;
while (x!=-1) // 输入-1时结束
{
if (L.length == MaxSize) {
std::cout << "顺序表已满";
return false;
}
L.elem[i++] = x; // 将数据存入第i个位置
L.length++; // 顺序表长度加1
std::cin >> x; // 输入一个数据元素
}
return true;
}

/*******************************************************************************/
/*顺序表按下标取值*/
/*******************************************************************************/
bool GetElem(Sqlist L, int i, int& e) {
if (i<1 || i>L.length) return false;
e = L.elem[i - 1]; // 第i-1个单元存储着第i个数据
return true;
}

/*******************************************************************************/
/*顺序表查找*/
/*******************************************************************************/
int LocateElem(Sqlist L, int e) {
for (int i = 0; i < L.length; i++) {
if (L.elem[i] == e) return i + 1; // 下标为i，实际为第i+1个元素
}
return -1; // 没找到，返回-1
}

/*******************************************************************************/
/*顺序表插入*/
/*******************************************************************************/
bool ListInsert_Sq(Sqlist& L, int i, int e) {
if (i<1 || i>L.length + 1) return false; // i不合法
if (L.length == MaxSize) return false; // 存储空间已满
// 从最后一个元素开始后移，直到第i个元素后移
for (int j = L.length - 1; j >= i - 1; j--) {
L.elem[j + 1] = L.elem[j];
}
L.elem[i - 1] = e; //将新元素e放入第i个位置
L.length++;
return true;
}

/*******************************************************************************/
/*顺序表删除*/
/*******************************************************************************/
bool ListDeleta_Sq(Sqlist& L, int i, int& e) {
if (i<1 || i>L.length) return false;
e = L.elem[i - 1]; //将欲删除的元素保存在e中
// 被删除元素之后的元素前移
for (int j = i; j <= L.length - 1; j++) {
L.elem[j - 1] = L.elem[j];
}
L.length--;
return true;
}

/*******************************************************************************/
/*顺序表遍历*/
/*******************************************************************************/
bool ListTraverse(Sqlist& L) {
if (L.length == 0) return false;
for (int i = 0; i < L.length; i++) {
std::cout << L.elem[i] << " ";
}
std::cout << std::endl;
return true;
}

/*******************************************************************************/
/*顺序表销毁*/
/*******************************************************************************/
void DestroyList(Sqlist& L) {
delete L.elem;
L.length = 0;
}
/*******************************************************************************/
/*主函数*/
/*******************************************************************************/
int main(){
ElemType e;
Sqlist L;
std::cout << "初始化顺序表"<<std::endl;
InitList(L);
std::cout << "顺序表创建" << std::endl;
CreateList(L);
std::cout << "顺序表遍历" << std::endl;
ListTraverse(L);
std::cout << "查找第2个元素并存储到变量e" << std::endl;
GetElem(L, 2, e);
std::cout << "查找的元素为：" << e << std::endl;
std::cout << "在第二个位置插入5" << std::endl;
ListInsert_Sq(L, 2, 5);
std::cout << "顺序表遍历" << std::endl;
ListTraverse(L);
std::cout << "删除第二个元素并存储到变量e中" << std::endl;
ListDeleta_Sq(L, 2, e);
std::cout << "删除的元素为：" << e << std::endl;
std::cout << "顺序表遍历" << std::endl;
ListTraverse(L);
std::cout << "顺序表销毁" << std::endl;
DestroyList(L);
}

运行结果：

python 线性表

class SeqList(object):
# 初始化顺序表
def __init__(self):
self.SeqList = []

# 创建顺序表
def CreateSequenceList(self):
print('请输入数据后按回车键确定，若想结束请输入“#”')
element = input("请输入元素:")
while element != '#':
self.SeqList.append(element)
element = input("请输入元素:")

# 查找元值函数
def FindElement(self):
key = input('请输入想要查找的元素值：')
if key in self.SeqList:
ipos = self.SeqList.index(key)
print('查找成功！值为：', self.SeqList[ipos], "的元素，位于当前顺序表的第", ipos + 1, "个位置。")
else:
print('查找失败，顺序表不存在该值')

# 指定位置插入元素
def InsertElement(self):
ipos = int(input("请输入待插入元素的位置："))
element = input('请输入待插入元素值：')
self.SeqList.insert(ipos, element)
print("插入元素后，当前顺序表为：\n", self.SeqList)

# 指定位置删除元素
def DeleteElement(self):
dpos = int(input('请输入待删除元素的位置：'))
self.SeqList.remove(self.SeqList[dpos-1])
print('删除后顺序表为', self.SeqList)

# 遍历顺序表
def TraverseElement(self):
SeqListLen = len(self.SeqList)
for i in range(0, SeqListLen):
print("第", i + 1, "个元素的值为", self.SeqList[i])


if __name__ == '__main__':
L = SeqList()
L.CreateSequenceList()
L.FindElement()
L.InsertElement()
L.DeleteElement()
L.TraverseElement()

[1] 数据结构：Python语言描述。作者：张光河

[2] 趣学数据结构 作者：陈小玉