数据结构探险（三）—— 线性表

2023-12-28 19:58
文章标签 数据结构 线性表 探险

本文主要是介绍数据结构探险（三）—— 线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 线性表是n个数据元素的有限序列
  • 线性表分为：
  1. 顺序表（数组）：特点是访问速度快，搜索能力强
  2. 链表：静态链表，单链表，循环链表，双向链表
  • 应用场景：通讯录；一元多项式；

线性表

c语言表示：
在这里插入图片描述

#ifndef LIST_H
#define LIST_H
typedef int Elem;
class List
{
public:List(int size); //构造函数~List(); //析构函数void ClearList();bool ListEmpty();//在c中没有bool类型，需要用宏定义定义BOOLint ListLength();bool GetElem(int i,Elem *e);//将下标为i的元素用e指针所指向的内存获取int LocateElem(Elem *e);bool PriorElem(Elem *currentElem, Elem *preElem);bool NextElem(Elem *currentElem, Elem *nextElem);void ListTraverse();bool ListInsert(int i,Elem *e);bool ListDelete(int i,Elem *e);private:int *m_pList; //指向一块内存int m_iSize; //内存多大int m_iLength;//线性表长度
};#endif

#include"List.h"
#include<iostream>
using namespace std;List::List(int size)
{m_iSize=size;m_pList = new int[m_iSize];m_iLength = 0;
}List::~List()
{delete []m_pList;//释放数组m_pList=NULL;
}void List::ClearList()
{m_iLength=0;
}bool List::ListEmpty()
{if(m_iLength==0){return true;}else{return false;}//return m_iLenght==0?true:false;
}int List::ListLength()
{return m_iLength;
}bool List::GetElem(int i,Elem *e)
{if(i<0||i>=m_iSize){return false;}*e =m_pList[i];return true;
}int List::LocateElem(Elem *e)
{for(int i=0;i<m_iLength;i++){if(m_pList[i] ==*e){return i;}}return -1;
}bool List::PriorElem(Elem *currentElem, Elem *preElem)
{int temp= LocateElem(currentElem);if(temp==-1){return false;}else{if(temp==0)//第一个位置没有前驱{return false;}else{*preElem = m_pList[temp-1];return true;}}
}bool List::NextElem(Elem *currentElem, Elem *nextElem)
{int temp= LocateElem(currentElem);if(temp==-1){return false;}else{if(temp==m_iLength-1)//最后一个元素没有后继{return false;}else{*nextElem = m_pList[temp+1];return true;}}
}void  List::ListTraverse()
{for(int i=0;i<m_iLength;i++){cout<<m_pList[i]<<endl;}
}bool List::ListInsert(int i,Elem *e)
{if(i<0||i>m_iLength) // i=m_iLength即在线性表最后一个位置,不需要移动任何元素，直接插入即可{return false;}for(int k=m_iLength-1;k>=i;k--)//从后到前移动{m_pList[k+1]=m_pList[k];}m_pList[i]=*e;m_iLength++;return true;
}bool List::ListDelete(int i,Elem *e)
{if(i<0||i>=m_iLength)//与上述有区别注意{return false;}*e= m_pList[i];for(int k=i+1;k<m_iLength;k++)//从前到后移动{m_pList[k-1]=m_pList[k];}m_iLength--;return true;
}

使线性表适用于其他类型，例如coordinate类型

  • 对于list的函数声明，把数据类型改为coordinate类即可 int LocateElem(Coordinate *e);
  • 需要修改的函数体：
  1. 遍历函数： 遍历时输出coordinate类型得元素，使用cout输出要提前重载操作符
    void  List::ListTraverse(){for(int i=0;i<m_iLength;i++){cout<<m_pList[i]<<endl;//能否这样输出取决于是否重载了操作符//这样也可以：m_pLit[i].printCoordinate()}}
  1. 比较查找元素函数 ：对于coordinate的==操作要重载
    int List::LocateElem(Coordinate *e){for(int i=0;i<m_iLength;i++){if(m_pList[i] ==*e)//需要堆coordiane做比较==运算符的重载{return i;}}return -1;}
  • 其他函数体不变
  • 如何重载？：
class Coordinate
{
public:friend ostream &operator<<(ostream &out,Coordinate &coor);Coordinate(int x=0, int y=0);//默认构造函数void printCoordinate();bool operator==(Coordinate &coor);private:int m_iX;int m_iY;
};

#include"Coordinate.h"
#include<iostream>using namespace std;Coordinate::Coordinate(int x,int y)
{m_iX=x;m_iY=y;
}void Coordinate::printCoordinate()
{cout<<"("<<m_iX<<","<<m_iY<<")";
}ostream &operator<<(ostream &out,Coordinate &coor)
{out<<"("<<coor.m_iX<<","<<coor.m_iY<<")";return out;
}bool Coordinate::operator==(Coordinate &coor)
{if(this->m_iX==coor.m_iX&&this->m_iY==coor.m_iY){return true;}else{return false;}
}
  • 测试：
// 线性表 顺序表
#include<iostream>
#include<stdlib.h>
#include"List.h"
using namespace std;int main()
{//3 5 7 2 9 1 8Coordinate e1(3,5),e2=(5,7),e3=(6,8);List *list1=new List(10);list1->ListInsert(0,&e1);list1->ListInsert(1,&e2);list1->ListInsert(2,&e3);Coordinate temp;list1->ListTraverse();delete list1;system("pause");return 0;
}

在这里插入图片描述

链表

  1. 单链表：结点有指针域数据域
  2. 循环链表：最后一个结点指针域又指向头结点
  3. 双向链表：结点有数据域，两个指针域
  4. 静态链表：没有指针的情况下用数组完成
单链表实现：
#ifndef NODE_H
#define NODE_Hclass Node
{
public:int data;Node *next;void printNode();
};void Node::printNode()
{cout<<data<<endl;
}
#endif // NODE_H

#ifndef LIST_H
#define LIST_H#include"Node.h"class List
{
public:List();~List();void ClearList();bool ListEmpty();int ListLength();bool GetElem(int i,Node *pNode);int LocateElem(Node *pNode);bool PriorElem(Node *pcurrentNode, Node *pPreNode);bool NextElem(Node *pcurrentNode, Node *pNextNode);void ListTraverse();bool ListInsert(int i,Node *pNode);//指定位置插入bool ListDelete(int i,Node *pNode);bool ListInsertHead(Node *pNode);bool ListInsertTail(Node *pNode);private:Node *m_pList; //指向一块内存int m_iLength;//线性表长度
};
List::List()
{//定义一个头结点，通过头结点操控整个链表m_pList = new Node;m_pList->data = 0;m_pList->next=NULL;m_iLength=0;//该头结点置空，不算在链表长度之中
}List::~List()
{//清除所有节点（包括头结点）ClearList();delete m_pList;m_pList=NULL;
}void List::ClearList()
{//清除除了头结点所有节点,不断找下线删除Node *currentNode= m_pList->next;while(currentNode!=NULL){Node *temp = currentNode->next;delete currentNode;currentNode=temp;}m_pList->next=NULL;
}bool List::ListEmpty()
{if(m_iLength==0){return true;}else{return false;}
}int List::ListLength()
{return m_iLength;
}bool List::ListInsertHead(Node *pNode)
{Node *temp =m_pList->next;Node *newNode =new Node;//从堆中申请内存，从栈中申请函数执行完后内存会被回收掉，所以一定要从堆中申请内存if(newNode==NULL){return false;}newNode->data=pNode->data;m_pList->next = newNode;//insertnewNode->next=temp;m_iLength++;return true;
}bool List::ListInsertTail(Node *pNode)
{Node *currentNode= m_pList;while(currentNode->next!=NULL){currentNode=currentNode->next;}Node *newNode =new Node;//从堆中申请内存，从栈中申请函数执行完后内存会被回收掉，所以一定要从堆中申请内存if(newNode==NULL){return false;}newNode->data=pNode->data;newNode->next=NULL;currentNode->next=newNode;m_iLength++;return true;
}bool List::ListInsert(int i,Node *pNode)
{if(i<0||i>m_iLength){return false;}Node *currentNode= m_pList;for(int k=0;k<i;k++){currentNode=currentNode->next;}Node *newNode =new Node;if(newNode==NULL){return false;}newNode->data=pNode->data;newNode->next=currentNode->next;currentNode->next=newNode;return true;
}bool List::ListDelete(int i,Node *pNode)
{if(i<0||i>=m_iLength){return false;}Node *currentNode=m_pList;Node *currentNodeBefore =NULL;for(int k=0;k<=i;k++){currentNodeBefore=currentNode;currentNode=currentNode->next;}currentNodeBefore->next=currentNode->next;pNode->data=currentNode->data;delete currentNode;currentNode=NULL;m_iLength--;return true;
}bool List::GetElem(int i,Node *pNode){if(i<0||i>=m_iLength){return false;}Node *currentNode=m_pList;Node *currentNodeBefore =NULL;for(int k=0;k<=i;k++){currentNodeBefore=currentNode;currentNode=currentNode->next;//找到第i个节点}pNode->data=currentNode->data;return true;}int List::LocateElem(Node *pNode)
{Node *currentNode = m_pList;int count=0;//计数变量while(currentNode->next!=NULL){currentNode=currentNode->next;if(currentNode->data==pNode->data){return count;//若count为0就return即返回的是头结点后的第一个结点}count++;}return -1;
}bool List::PriorElem(Node *pcurrentNode, Node *pPreNode)
{Node *currentNode = m_pList;Node *tempNode = NULL;while(currentNode->next!=NULL){tempNode=currentNode;currentNode=currentNode->next;if(currentNode->data==pcurrentNode->data){if(tempNode==m_pList)//如果前驱就是头结点，认定找不到该节点的前驱{return false;}pPreNode->data=tempNode->data;return true;}}return false;
}bool List::NextElem(Node *pcurrentNode, Node *pNextNode)
{Node *currentNode = m_pList;while(currentNode->next!=NULL){currentNode=currentNode->next;if(currentNode->data==pcurrentNode->data){if(currentNode->next==NULL)//找到的当前结点已经是最后一个结点{return false;}pNextNode->data=currentNode->next->data;return true;}}return false;
}void List::ListTraverse()
{Node *currentNode=m_pList;while(currentNode->next!=NULL){currentNode=currentNode->next;currentNode->printNode();}
}
#endif
测试：
// ÏßÐÔ±í ˳Ðò±í
#include<iostream>
#include<stdlib.h>
#include"List.h"
using namespace std;int main()
{Node node1,node2,node3,node4;node1.data=3;node2.data=4;node3.data=5;node4.data=6;Node node5;node5.data=7;List *pList = new List();//    pList->ListInsertHead(&node1);
//    pList->ListInsertHead(&node2);
//    pList->ListInsertHead(&node3);
//    pList->ListInsertHead(&node4); //遍历后输出结果为 6 5 4 3pList->ListInsertTail(&node1);pList->ListInsertTail(&node2);pList->ListInsertTail(&node3);pList->ListInsertTail(&node4); //遍历后输出结果为 3 4 5 6pList->ListInsert(1,&node5);Node temp;//pList->ListDelete(1,&temp);pList->NextElem(&node5,&temp);pList->ListTraverse();cout<<"temp:"<<temp.data<<endl;delete pList;pList=NULL;system("pause");return 0;
}

在这里插入图片描述

链表应用——通讯录

  • 结点Node的data是person类型
  • newNode->data=pNode->data;对于这样data的赋值操作，要重载
  • f(currentNode->data==pNode->data)对于data之间的比较操作，要重载
  • void Node::printNode() { cout<<data<<endl; }对于打印节点操作，要重载cout

person.h

#ifndef PERSON_H_INCLUDED
#define PERSON_H_INCLUDED#include<string>
#include<ostream>using namespace std;class Person
{friend ostream &operator<<(ostream &out,Person &person);
public:string name;string phone;Person &operator = (Person &person);bool operator ==(Person &person);
};ostream &operator<<(ostream &out,Person &person)
{out<<person.name<<"----" <<person.phone<<endl;return out;
}Person &Person::operator = (Person &person)
{this ->name = person.name;this->phone=person.phone;return *this;
}bool Person::operator==(Person &person)
{if(this->name==person.name&&this->phone==person.phone){return true;}return false;
}#endif // PERSON_H_INCLUDED
测试
#include<iostream>
#include<stdlib.h>
#include"List.h"
using namespace std;int main()
{Node node1;node1.data.name="sss";node1.data.phone="123456";Node node2;node2.data.name="sjx";node2.data.phone="238956";List *pList= new List();pList->ListInsertTail(&node1);pList->ListInsertTail(&node2);pList->ListTraverse();delete pList;pList=NULL;system("pause");return 0;
}

在这里插入图片描述

一切就绪之后，开始编写通讯录代码

通讯录.cpp


#include<iostream>
#include<stdlib.h>
#include"List.h"
using namespace std;int menu()
{//显示通讯录功能菜单cout<<"功能菜单"<<endl;cout<<"1.新建联系人"<<endl;cout<<"2.删除联系人"<<endl;cout<<"3.浏览通讯录"<<endl;cout<<"4.退出通讯录"<<endl;cout<<"请输入:"<<endl;int order=0;cin>>order;return order;
}void createPerson(List *pList)
{Node node ;Person person;cout<<"请输入姓名 :";cin>>person.name;cout<<"请输入电话 :";cin>>person.phone;node.data=person;pList->ListInsertTail(&node);
}
void deletePerson(List *pList,Node *temp)
{Node node;cout << "请输入要删除的联系人的姓名:" << endl;cin >> node.data.name;cout << "请输入要删除的联系人的电话:" << endl;cin >> node.data.phone;int locate = pList->LocateElem(&node);//先查找联系人的位置if(locate == -1){cout << "没找到此联系人" << endl;return;}pList->ListDelete(locate,temp);//删除联系人cout << "成功删除联系人" << endl;
}int main()
{int userOrder = 0;List *pList= new List();while(userOrder!=4){userOrder = menu();Node temp;switch(userOrder){case 1:cout<<"用户指令---->>新建联系人"<<endl;createPerson(pList);break;case 2:cout<<"用户指令---->>删除联系人"<<endl;deletePerson(pList,&temp);break;case 3:cout<<"用户指令---->>浏览通讯录"<<endl;pList->ListTraverse();break;case 4:cout<<"用户指令---->>退出通讯录"<<endl;break;}}delete pList;pList=NULL;return 0;
}

在这里插入图片描述

对于课程布置的删除作业，可参考https://www.imooc.com/qadetail/163402

这篇关于数据结构探险（三）—— 线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/547114。

相关文章

【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
算法与数据结构面试宝典——回溯算法详解（C#，C++）

算法与数据结构面试宝典——回溯算法详解（C#，C++）

文章目录 1. 回溯算法的定义及应用场景2. 回溯算法的基本思想3. 递推关系式与回溯算法的建立4. 状态转移方法5. 边界条件与结束条件6. 算法的具体实现过程7. 回溯算法在C#，C++中的实际应用案例C#示例C++示例 8. 总结回溯算法的主要特点与应用价值 回溯算法是一种通过尝试各种可能的组合来找到所有解的算法。这种算法通常用于解决组合问题，如排列、组合、棋盘游
阅读更多...
嵌入式学习——数据结构（哈希、排序）——day50

嵌入式学习——数据结构（哈希、排序）——day50

1. 查找二叉树、搜索二叉树、平衡二叉树 2. 哈希表——人的身份证——哈希函数 3. 哈希冲突、哈希矛盾 4. 哈希代码 4.1 创建哈希表 4.2  5. 算法设计 5.1 正确性 5.2 可读性（高内聚、低耦合） 5.3 健壮性 5.4 高效率（时间复杂度）时间复杂度越低，效率越高， 5.5 低储存（空间复杂度）空间复杂度越低，存储空间越少 6.排序算法 6.1 冒
阅读更多...
【数据结构与算法 经典例题】使用队列实现栈（图文详解）

【数据结构与算法 经典例题】使用队列实现栈（图文详解）

💓 博客主页：倔强的石头的CSDN主页               📝Gitee主页：倔强的石头的gitee主页    ⏩ 文章专栏：《数据结构与算法 经典例题》C语言                                   期待您的关注 ​​ 目录  一、问题描述 二、前置知识 三、解题思路 四、C语言实现代码 🍃队列实现代码：
阅读更多...
数据结构：二叉树详解 c++信息学奥赛基础知识讲解

数据结构：二叉树详解 c++信息学奥赛基础知识讲解

目录 一、二叉树的定义 二、二叉树的形态 三、二叉树的性质 四、二叉树的存储 五、二叉树的创建与遍历（递归） 六、二叉树实现 创建二叉树 展示二叉树 1、计算数的高度 2、计算数的叶子数量 3、计算数的宽度 4、层次遍历 5、前序遍历 递归写法 非递归写法 6、中序遍历 递归写法 非递归写法 7、后序遍历 递归写法 非递归写法 8、输出根节点到所有叶
阅读更多...
Java数据结构4-链表

Java数据结构4-链表

1. ArrayList的缺陷 由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。 2. 链表 2.1 链表的概念及结构 链表是一种物理存储结构上非连续存储结构，数据元素
阅读更多...
大学生自救数据结构与算法（py实现）——01递归

大学生自救数据结构与算法（py实现）——01递归

目录 目录 递归 基本概念 工作原理 基本要素 优点 缺点 实现技巧 实例解析：计算阶乘 斐波那契数列 高效的斐波那契数列 python中的最大递归深度 二分查找 基本原理 性能分析 优化与变体 线性递归  元素序列的递归求和 二路递归 二路递归的基本概念 典型应用 工作原理 多重递归  示例：计算卡特兰数（Catalan Number） 尾递
阅读更多...
数据结构和算法(1) ---- Queue 的原理和实现

数据结构和算法(1) ---- Queue 的原理和实现

Queue 的定义和结构 队列(Queue) 是只允许在一端进行插入，在另一端进行删除的线性表 队列是一种先进先出(First In First Out)的线性表，简称 FIFO(First IN First OUT), 允许插入的一端称为队尾, 允许删除的一端称为队列头 队列的基本结构如下图所示： Queue 的抽象数据类型 队列也有线性表的各种操作,不同的是插入元素只能在队列尾,删除
阅读更多...
从零开始学数据结构系列之第三章《平衡二叉树基础概念》

从零开始学数据结构系列之第三章《平衡二叉树基础概念》

文章目录 前言什么是平衡二叉树往期回顾 前言 ​   在前面的学习过程中，我们了解到二叉排序树可以在一定程度上提高查找（搜索）的效率，但仍然会出现特殊情况，让二叉排序树失效。例如，将序列{1,2,3,4,5,6}中的元素依次插入到二叉排序树中，会得到右斜树，这就相当于一个单链表了，搜索效率降低为O(n)。   于是在 1962 年，一个姓 AV 的大佬（G. M. Ade
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2