线性表顺序表示、链式表示实现方法及其异同点
线性表顺序表示、链式表示实现方法及其异同点
线性表是最常用且最简单的一种数据结构，按存储单元排列可分为顺序表示和链式表示两种方式。
本文采用C++实现两种表示方法。
目录
顺序表示和链式表示的区别：
创建方式：
时间复杂度：
顺序表示和链式表示的相同点：
删除内存空间：
代码实现：
顺序表示方法：
结构体定义
初始化
增加元素
删除元素
销毁列表
链式表示方法
结构体定义
初始化
增加节点
删除节点
显示链表
销毁链表
顺序表示和链式表示的区别：
创建方式：
顺序表示方法单次创建多个存储单元，相邻的元素存放在连续的存储空间之中。
（PS：内存空间申请请参考https://blog.csdn.net/Baimax1/article/details/105954552）
链式表示方法单次创建单个存储单元，存储单元之间地址不一定连续。存储单元包括数据部分和地址部分，数据部分存放需要保存的数据，地址部分保存下一个存储单元的地址（单链表，双向链表的地址部分同时也存放上一个存储单元的地址）。
时间复杂度：
增加 / 删除元素操作：顺序表示方法 O(n)；链式表示方法O(1);（PS:在未知位置的元素前 / 后操作）
增加 / 删除元素操作：顺序表示方法 O(n)；链式表示方法O(n);（PS:在已知位置的元素前 / 后操作）
PS:顺序表示需要将元素一一后移，链式存储结构需要查找该元素的位置。
修改 元素操作：顺序表示方法 O(1)；链式表示方法O(n);
查询 元素操作：顺序表示方法 O(n)；链式表示方法O(n);
顺序表示和链式表示的相同点：
删除内存空间：
内存空间的删除都需要对每一个存储单元单独释放空间。
代码实现：
顺序表示方法：
结构体定义
typedef struct {
ElemType * elem;
int length; // 线性表的现有长度
int listSize; // 线性表的最大长度
}SqList;
初始化
void InitList(SqList *L){
L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)) ;
if(!L->elem) {
cout<<"申请空间失败！\n";
DestoryList(L);
}
L->length = 0;
L->listSize = LIST_INIT_SIZE;
cout<<"线性表初始化完成！\n";
}
增加元素
void ListAdd(SqList *L, ElemType e){ //在末尾直接增加元素
if(L->length>=L->listSize){
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
if(!L->elem){
cout<<"增加空间失败！"<<endl;
DestoryList(L);
}
}
* (L->elem+L->length) = e;
L->length ++;
}
void ListAddBefor(SqList *L, ElemType e,int e_where){ //在某位置前增加元素
int i;
L->length++;
for(i=L->length;i>=e_where;i--){
if(L->length>L->listSize){
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
if(!L->elem){
cout<<"增加空间失败！"<<endl;
DestoryList(L);
}
}
*(L->elem+i+1) = *(L->elem+i);
}
*(L->elem+e_where)=e;
cout<<"增加后的线性表如下："<<endl;
ListShow(L);
}
void ListAddAfter(SqList *L, ElemType e,int e_where){ //在某位置后增加元素
int i;
L->length++;
for(i=L->length;i>e_where;i--){
if(L->length>L->listSize){
L->elem = (ElemType *)realloc(L->elem,(L->listSize+LISTINCREMENT)*sizeof(ElemType));
if(!L->elem){
cout<<"增加空间失败！"<<endl;
DestoryList(L);
}
}
*(L->elem+i+1) = *(L->elem+i);
}
*(L->elem+e_where+1)=e;
cout<<"增加后的线性表如下："<<endl;
ListShow(L);
}
删除元素
void ListDelete(SqList *L, int e_where){ //删除某位置元素
L->length--;
for(int i=e_where;i<=L->length;i++){
*(L->elem+i-1)=*(L->elem+i);
}
cout<<"删除后的线性表如下："<<endl;
ListShow(L);
}
销毁列表
void DestoryList(SqList *L){
int i=0;
for(i=0;i<L->listSize;i++){
free(L->elem);
L->elem++;
}
exit(0);
}
链式表示方法
结构体定义
typedef struct L_Node{
ElemType data;
struct L_Node *next;
//struct L_Node *last; //增加可变成双向节点
}LNode;
初始化
void LinearNode::InitLNode(){
HeadList = (LNode *)malloc(sizeof(LNode));
if(!HeadList){
cout << "初始化链表失败！" << endl;
exit(0);
}
EndList=HeadList;
HeadList->next = NULL;
cout<< "初始化链表成功！ 初始地址为：" << HeadList << endl;
Length = 0;
e_where= 0;
}
增加节点
void LinearNode::AddNodeHead(ElemType num){ //头插法
node = (LNode *)malloc(sizeof(LNode));
if(!node){
cout << "新建节点失败！" << endl;
return;
}
node->data = num;
cout << node->data <<" ";
if(NULL==HeadList->next){
node->next = NULL;
HeadList->next = node;
EndList=node;
}
else{
node->next = HeadList->next;
HeadList->next=node;
}
Length++;
}
void LinearNode::AddNodeEnd(ElemType num){ //尾插法
node = (LNode *)malloc(sizeof(LNode));
if(!node){
cout << "新建节点失败！" << endl;
return;
}
node->data = num;
cout << node->data <<" ";
node->next = NULL;
EndList->next = node;
EndList = node;
Length++;
}
删除节点
void LinearNode::DeleteNode(ElemType elem){
if(NULL==(HeadList->next)){
cout<< "无节点"<<endl;
return;
}
Node_cur = HeadList;
while(NULL!=Node_cur->next){
Node_temp = Node_cur->next;
if(elem == Node_temp->data){
Node_cur->next=Node_temp->next;
free(Node_temp);
}
if(NULL!=Node_cur->next)
Node_cur=Node_cur->next;
}
cout<< elem <<" 元素已删除！"<<endl;
}
显示链表
void LinearNode::ShowLNode(){
if(NULL==(HeadList->next)){
cout<< "无节点"<<endl;
return;
}
Node_cur = HeadList->next;
while(NULL!=(Node_cur->next)){
cout<< Node_cur->data << " ";
Node_cur = Node_cur->next;
}
cout<< Node_cur->data << " ";
cout<<"链表中的数据已显示！！"<<endl;
}
销毁链表
void LinearNode::DestoryLNode(){
Node_cur = HeadList->next;
while(NULL!=(Node_cur->next)){
Node_temp = Node_cur->next;
free(Node_cur);
Node_cur = Node_temp;
}
free(Node_temp);
cout << "数据节点已完全释放！"<<endl;
free(HeadList); // 释放头节点
cout << "头节点已释放！"<<endl;
————————————————
版权声明：本文为CSDN博主「星河有鱼」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Baimax1/article/details/106036286
页:
[1]