设计一个静态链表（或称为数组链表）

2024-03-20 21:58
文章标签 设计 数组 链表 静态 称为

本文主要是介绍设计一个静态链表（或称为数组链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

设计一个静态链表（或称为数组链表），该链表储存的数据类型为string，请实现以下的功能。
public:
List(); //构造函数
List(int size); //含参构造函数-创建最大长度为size的静态链表
int Size() const; //返回链表的长度
bool IsFull() const; //返回链表是否已满
bool IsEmpty()const; //返回链表是否已空
void Clear(); //清空链表
int Retrieve( int position, string &x ) const; //获取链表第position位置的元素到x，成功返回0，否则返回-1
int Replace( int position, const string &x ); //将链表第position位置的元素换为x，成功返回0，否则返回-1
int Remove( int position, string &x ); //获取并删除链表第position位置的元素，成功返回0，否则返回-1
int Insert(int position, const string &x ); //将元素x插入到链表第position位置，成功返回0，否则返回-1

要求：
在实现要求的结构的基础上，需在main函数中编写下面所述的简单测试程序，请使用屏幕输入输出。
（1）按输入序列：Jan、Feb、Mar、Apr、May 建立初始链表。
（2）在Feb 之前，May 之后，先后插入Jun、Oct。
（3）先后删除Mar 和 Jan 。
（4）在Apr之前插入Dec。
在每一步执行后，输出链表状态。链表的状态请按照position：content：index输出。并输出当前链表。
注释：1. 第一个元素的Position的index为0；
2.插入元素操作Insert为在指定位置之前插入；

代码如下：

#include<iostream>
#include<string>
using namespace std;
typedef int index;
const int max_list=11;
class Node
{
public:
 string entry;
 index next;
};
class List
{
public:
    List(); //构造函数
 List(int size);//含参构造-创建最大长度为size的静态链表
    int Size() ; //返回链表的长度
    bool IsFull() const; //返回链表是否已满
    bool IsEmpty() const; //返回链表是否已空
    void Clear(); //清空链表
    int Retrieve( int position, string &x ) ; //获取链表第position位置的元素到x，成功返回0，否则返回-1
    int Replace( int position, const string &x ); //将链表第position位置的元素换为x，成功返回0，否则返回-1
    int Remove( int position, string &x ); //获取并删除链表第position位置的元素，成功返回0，否则返回-1
    int Insert( int position, const string &x ); //将元素x插入到链表第position位置，成功返回0，否则返回-1
 
 void Print();
    void PrintElement();
protected:
    Node workspace[max_list]; 
 index avaliable,last_used,head;
 int count;
 index new_node();
 void delete_node(index n);
 int current_position(index n)const;
 index set_position(int position)const;
};

index List::new_node()
{
  index new_index;
  if(avaliable!=-1)
  {
    new_index=avaliable;
    avaliable=workspace[avaliable].next;
  }
  else if(last_used<max_list-1)
  {
   new_index=++last_used;
  }
  else return -1;
  workspace[new_index].next=-1;
  return new_index;
}

void List::delete_node(index old_index)
{
   index previous;
   if (old_index == head) head = workspace[old_index].next;
   else
   {
      previous = set_position(current_position(old_index) - 1);
      workspace[previous].next = workspace[old_index].next;
   }
   workspace[old_index].next = avaliable;
   avaliable = old_index;
}

int List::current_position(index n) const
{  
 index newindex=head;
 int position=0;
 for(;newindex!=-1;newindex=workspace[newindex].next)
 {
     if(newindex==n)
  {
  return position;
  }
  position++;
 }  
 return -1;
}

index List::set_position(int position) const
{
 index current=head;
 if(position<0||position>count)
 {
  return -1;
 }
  for(int ix=0;ix!=position;ix++)
  {
    current=workspace[current].next;
  }
   return current;
}

 

List::List()
{
head=-1;
avaliable=-1;
last_used=-1;
count=0;
}

int List::Size()
{
   index newindex=head;
   index current;
   while(workspace[newindex].next!=-1)
   {
    current=workspace[newindex].next;
    workspace[newindex]=workspace[current];
       count++;
   }
   return count;
}
bool List::IsFull()const
{
   if(workspace[avaliable].next==-1&&last_used==max_list-1)
 {
 return true;
 }
 else
 {
   return false;
 }
}

bool List::IsEmpty() const
{
 if(workspace[head].next==-1)
 {
 return true;
 }
 else
 {
 return false;
 }
}
void List::Clear()
{
  workspace[0].next=-1;
  int i = 1;
   for (; i < max_list-1; i++)
   {
    workspace[i].entry="/0";
    workspace[i].next=i+1;
   }
   workspace[i+1].entry="/0";
   workspace[i+1].next=-1;
}
int List::Retrieve( int position, string &x )
{
      if(position<0||position>count-1)
        return -1;
    else
     {
   index newindex=set_position(position);
         x=workspace[newindex].entry;
      return 0;
      }
}

int List::Replace( int position, const string &x )
{
   if(position<0||position>count)
   return -1;
   else
    {
    index newindex=set_position(position);
   workspace[newindex].entry=x;
   return 0;
    }
}

int List::Remove( int position, string &x )
{     index following;index previous;
      if(position<0||position>count-1)
  return -1;
   if(position>0)
   {
    previous=set_position(position-1);   ///?????
    following=workspace[workspace[previous].next].next;
   }
 
   x=workspace[previous].entry;
   workspace[previous].entry="/0";
   delete_node(previous);
  
   workspace[previous].next=following;
   count--;
   return 0;
}

int List::Insert(int position,const string &x)
{
  index new_index,previous,following;
  if(position<0||position>count)
   return -1;
  if(position>0)
  {
  previous=set_position(position-1);
  following=workspace[previous].next;
  }
  else following=head;
  if((new_index=new_node())==-1)
   return -1;
  workspace[new_index].entry=x;
  workspace[new_index].next=following;
  if(position==0)
   head=new_index;
  else
   workspace[previous].next=new_index;
      count++;
   return 0;
}

void List::Print()
{
   for (int i = 0; i <count; i++)
    {   cout<<i<<":" <<(workspace[i].entry =="/0" ?"N/A": workspace[i].entry )<<":"<<workspace[i].next<<"    ";
  if(i%3==2||i==count-1)
  cout<<endl;
 }
}

void List::PrintElement()
{
  index newindex=head;
  cout<<"当前链表为： ";
  while(workspace[newindex].next!=-1)
   {
   cout<<workspace[newindex].entry<<" ";
 newindex=workspace[newindex].next; 
   }
  cout<<workspace[newindex].entry<<endl;
}
int main()
{
    List lis;
 cout<<"1)按输入序列：Jan、Feb、Mar、Apr、May 建立初始链表。"<<endl;
 lis.Insert(0,"/0");
    lis.Insert(1,"/0");
 lis.Insert(2,"Jan");
    lis.Insert(3,"Feb");
 lis.Insert(4,"Mar");
 lis.Insert(5,"Apr");
 lis.Insert(6,"May");
 cout<<endl;
 lis.Print();
 cout<<endl;
 lis.PrintElement();
     cout<<endl;


 cout<<"2)在Feb之前，May之后先后插入Jun,Oct"<<endl;
 lis.Insert(7,"Jun");
 lis.Insert(8,"Oct");
 cout<<endl;
 lis.Print();
 cout<<endl;
 lis.PrintElement();
 cout<<endl;

 cout<<"3)先后删除Mar和Jan"<<endl;
 string a,b;
 lis.Remove(5,a);
 lis.Remove(3,b);
 //cout<<a<<endl;     //输出要删的单词
 cout<<endl;
 lis.Print();
 cout<<endl;
 lis.PrintElement();
 cout<<endl;

 cout<<"4)在Apr之前插入Dec"<<endl;
 lis.Insert(3,"Dec");
 cout<<endl;
 lis.Print();
 cout<<endl;
 lis.PrintElement();
 cout<<endl;
  return 0;
}
 

这篇关于设计一个静态链表（或称为数组链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
怎么让1台电脑共享给7人同时流畅设计

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
基于51单片机的自动转向修复系统的设计与实现

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2