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

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。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...
浙大数据结构：04-树7 二叉搜索树的操作集

浙大数据结构：04-树7 二叉搜索树的操作集

这道题答案都在PPT上，所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现，小就进左子树，大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo
阅读更多...
【数据结构入门】排序算法之交换排序与归并排序

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。 动画演示： 1.1.2 具体步
阅读更多...
数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]队列之顺序队列的类模板实现

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），允许删除的一端叫做队首（front）。 队列具有FIFO的性质 队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。 #i
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2