数学建模社区-数学中国

标题: 线性表顺序表示、链式表示实现方法及其异同点 [打印本页]

作者: 杨利霞 时间: 2020-5-10 16:11
标题: 线性表顺序表示、链式表示实现方法及其异同点

线性表顺序表示、链式表示实现方法及其异同点
线性表是最常用且最简单的一种数据结构，按存储单元排列可分为顺序表示和链式表示两种方式。

本文采用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:

eleteNode(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:

estoryLNode(){
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

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)