c/c++ 线性表底缘序表

线性表底缘序表

囤在连续的内存空间,和数组一样。
下的代码,最先河定义了一个能存8个元素的顺序表,当跨越8单因素的时段,会重复添开辟空间(函数:reInit)。
贯彻了以下效率:

函数 功能描述
push_back 从最后插入
push_front 从最前插入
show_list 打印出顺序表里的元素
pop_back 从最后删除
pop_front 从最前删除
insert_pos 从指定位置插入
find 查找指定的元素,返回其在顺序表中的下标
length 返回顺序表的长度
delete_pos 从指定位置删除
delete_val 删除指定的值的元素
sort1 按升序排序
sort2 按降序排序
resver 反转顺序表中的元素
clear 清除顺序表中的元素
destroy 释放顺序表所占用的内存空间

SeqList.h

#ifndef __SEQLIST__
#define __SEQLIST__

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>

#define SEQLIST_INIT_SIZE 8
typedef int ElemType;

typedef struct SeqList{
  int cap;//顺序表所能容纳的最大元素数量
  int size;//当前顺序表中元素的数量
  ElemType *base;//指向顺序表开始位置的指针
}SeqList;

void init(SeqList*);
void push_back(SeqList*, ElemType);
void show_list(SeqList*);
void push_front(SeqList*, ElemType);
void pop_back(SeqList*);
void pop_front(SeqList*);
void insert_pos(SeqList*, ElemType, int);
int find(SeqList*, ElemType);
int length(SeqList*);
void delete_pos(SeqList*, int);
void delete_val(SeqList*, int);
void sort1(SeqList*);
void sort2(SeqList*);
void resver(SeqList*);
void clear(SeqList*);
void destroy(SeqList*);
#endif

SeqList.c

#include "SeqList.h"

bool reInit(SeqList* seq){
  //容量已满,所以重新开辟空间
  ElemType* newp = (ElemType*)realloc(seq->base,(seq->size+1)*sizeof(ElemType));
  if(NULL == newp){
    return true;
  }
  //如果重新开辟的空间的地址和原来空间的地址不相同
  //就需要把原来内存空间里的值,复制到新的内存空间中。
  if(seq->base != newp){
    memmove(seq->base, newp, sizeof(ElemType)*seq->size);
    seq->base = newp;
  }
  seq->cap++;
  return false;
}
void init(SeqList* seq){
  //开辟能容纳8个元素的内存空间
  seq->base = (ElemType*)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
  assert(NULL != seq->base);
  seq->cap = SEQLIST_INIT_SIZE;
  seq->size = 0;
}
void push_back(SeqList* seq, ElemType x){
  if(seq->size >= seq->cap && reInit(seq)){
    printf("线性表已满\n");
    return;
  }
  seq->base[seq->size] = x;
  seq->size++;
}
void push_front(SeqList* seq, ElemType x){
  if(seq->size >= seq->cap && reInit(seq)){
    printf("线性表已满\n");
    return;
  }
  //往后移动一个元素的距离
  memmove(seq->base+1, seq->base,seq->size * sizeof(ElemType));
  seq->base[0] = x;
  seq->size++;
}
void pop_back(SeqList* seq){
  if(seq->size <= 0){
    printf("线性表以空\n");
    return;
  }
  seq->size--;
}
void pop_front(SeqList* seq){
  if(seq->size <= 0){
    printf("线性表以空\n");
    return;
  }
  //往前移动一个元素的距离
  memmove(seq->base, seq->base+1,seq->size * sizeof(ElemType));
  seq->size--;
}
void insert_pos(SeqList* seq, ElemType x, int index){
  if(seq->size >= seq->cap && reInit(seq)){
    printf("线性表已满\n");
    return;
  }
  if(index < 0 || index > seq->size){
    printf("given index is error\n");
    return;
  }
  //在指定的位置往后移动一个元素的距离
  memmove(seq->base+index+1,seq->base+index,(seq->size-index)*sizeof(ElemType));
  seq->base[index] = x;
  seq->size++;
}
int find(SeqList* seq, ElemType x){
  for(int i = 0; i < seq->size; ++i){
    if(x == seq->base[i]){
      return i;
    }
  }
  return -1;
}
int length(SeqList* seq){
  return seq->size;
}
void delete_pos(SeqList* seq, int index){
  if(seq->size <= 0){
    printf("线性表以空\n");
    return;
  }
  if(index < 0 || index > seq->size - 1){
    printf("given index is error\n");
    return;
  }
  //在指定的位置往前移动一个元素的距离
  memmove(seq->base+index,seq->base+index+1,(seq->size-index-1)*sizeof(ElemType));
  seq->size--;
}
void delete_val(SeqList* seq, int value){
  int pos = find(seq, value);
  if(pos == -1){
    printf("The enter value is not exist");
    return;
  }
  delete_pos(seq, pos);

}
void sort1(SeqList* seq){
  for(int i = 0; i < seq->size-1; ++i){
    for(int j = 0; j < seq->size-i-1; ++j){
      if(seq->base[j] > seq->base[j+1]){
    ElemType tmp = seq->base[j];
    seq->base[j] = seq->base[j+1];
    seq->base[j+1] = tmp;
      }
    }
  }
}
void sort2(SeqList* seq){
  for(int i = 0; i < seq->size-1; ++i){
    for(int j = 0; j < seq->size-1-i; ++j){
      if(seq->base[j] < seq->base[j+1]){
    seq->base[j] = seq->base[j] + seq->base[j+1];
    seq->base[j+1] = seq->base[j] - seq->base[j+1];
    seq->base[j] = seq->base[j] - seq->base[j+1];
      }
    }
  }
}
void resver(SeqList* seq){
  //如果seq->size是偶数就会被整除,如果是奇数就会舍掉小数位,不进1
  for(int i = 0; i < seq->size / 2; ++i){
    ElemType tmp = seq->base[i];
    seq->base[i] = seq->base[seq->size-i-1];
    seq->base[seq->size-i-1] = tmp;
  }
}
void clear(SeqList* seq){
  seq->size = 0;
}
void destroy(SeqList* seq){
  free(seq->base);
  seq->base = NULL;
  seq->cap = 0;
  seq->size = 0;
}
void show_list(SeqList* seq){
  for(int i = 0; i < seq->size; ++i){
    printf("%d ", seq->base[i]);
  }
  printf("\n");
}

SeqListMain.c

#include "SeqList.h"

int main(){
  SeqList list;
  init(&list);
  int select = 1;
  ElemType item;
  int index;
  while(select){
    printf("*****************************************\n");
    printf("*** [1]   push_back   [2]  push_front ***\n");
    printf("*** [3]   show_list   [4]  pop_back   ***\n");
    printf("*** [5]   pop_front   [6]  insert_pos ***\n");
    printf("*** [7]   find        [8]  length     ***\n");
    printf("*** [9]   delete_pos  [10] delete_val ***\n");
    printf("*** [11]  sort1       [12] resver     ***\n");
    printf("*** [13]  clear       [14*] destroy    ***\n");
    printf("*** [0]   quit        [15] sort2      ***\n");
    printf("*****************************************\n");
    printf("请选择:>");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("请输入要插入的数据,以-1结束>\n");
      while(scanf("%d",&item),item != -1){
    push_back(&list, item); 
      }
      show_list(&list);
      break;
    case 2:
      printf("请输入要插入的数据,以-1结束>\n");
      while(scanf("%d",&item),item != -1){
    push_front(&list, item);    
      }
      show_list(&list);
      break;
    case 3:
      show_list(&list);
      break;
    case 4:
      pop_back(&list);
      show_list(&list);
      break;
    case 5:
      pop_front(&list);
      show_list(&list);
      break;
    case 6:
      printf("请输入要插入的数据>\n");
      scanf("%d",&item);
      printf("请输入要插入的index>\n");
      scanf("%d",&index);
      insert_pos(&list, item, index);
      show_list(&list);
      break;
    case 7:
      printf("please enter what you shoule find out>\n");
      scanf("%d",&item);
      index = find(&list, item);
      if(index == -1){
    printf("can not find %d \n", item);
      }else{
    printf("find %d at position %d\n", item, index);
      }
      show_list(&list);
      break;
    case 8:
      printf("length is %d\n", length(&list));
      show_list(&list);
      break;
    case 9:
      printf("please enter the index that you shoule delete>\n");
      scanf("%d", &index);
      delete_pos(&list, index);
      show_list(&list);
      break;
    case 10:
      printf("please enter the value what you shoule delete >\n");
      scanf("%d", &item);
      delete_val(&list, item);
      show_list(&list);
      break;
    case 11:
      sort1(&list);
      show_list(&list);
      break;
    case 12:
      resver(&list);
      show_list(&list);
      break;
    case 13:
      clear(&list);
      show_list(&list);
      break;
    case 15:
      sort2(&list);
      show_list(&list);
      break;
    default:
      printf("输入的选择错误,请重新选择\n");
      break;
    }
  }
  destroy(&list);
}

线性表的相继表C++实现,线性顺序

线性表的缘序表

一、头文件:SeqList.h

//顺序线性表的腔文件
#include<iostream>

const int MaxSize = 100;
//定义顺序表SeqList的模板类
template<class DataType>
class SeqList{
public:
  //顺序表无参构造器(成立一个空的顺序表)
  SeqList(){ length = 0 }
  //顺序表有参构造器(创建一个长短为n的顺序表)
  SeqList(DataType array[], int n);
  //顺序表析构函数
  ~SeqList(){}
  //求顺序表的尺寸
  int GetLength(){ return length; }
  //顺序表按位查找,重返i地方的因素
  DataType GetElement(int i);
  //顺序表按值查找,再次来到该因素所于的职位
  int GetLocal(DataType x);
  //顺序表在指定的职插入指定的要素
  void Insert(int i, DataType x);
  //顺序表删除元素,重回去的素
  DataType Delete(int i);
  //输出顺序表中的要素
  void PrintSeqList();
private:
  //一维数组,存放数据元素
  DataType data[MaxSize];
  //顺序表的长短
  int length;
};

//实现顺序表出参构造器
template<class DataType>
SeqList<DataType>::SeqList(DataType array[], int n)
{
  if (n > MaxSize)
  {
    throw “传入的逐条表长度过长”;
  }
  //给顺序表的积存元素的数组赋值
  for (int i = 0; i < n; i++)
  {
    data[i] = array[i];
  }
  //给顺序表的长度赋值
  length = n;
}

//实现顺序表按位查找
template<class DataType>
DataType SeqList<DataType>::GetElement(int i)
{
  //判断是迟早的职是不是成立
  if (i < 1 || i >length)
  {
    throw “地方暴发无意”;
  }
  else
  {
    //重回指定地点的因素
    return data[i – 1];
  }
}

//实现顺序表按值查找,重回该因素所于的职务
template<class DataType>
int SeqList<DataType>::GetLocal(DataType x)
{
  //遍历顺序表的因素
  for (int i = 0; i < length; i++)
  {
    //判断指定的元素是否以逐一表中
    if (data[i] == x)
    {
      //重临指定元素于逐个表中的职务
      return (i + 1);
    }
  }
  //如果指定的元素不在依次表中,则回地方为0
  return 0;
}

//实现顺序表插入元素
template<class DataType>
void SeqList<DataType>::Insert(int index, DataType x)
{
  //判断插入的职位是不是站得住
  if (length >= MaxSize)
  {
    throw “顺序表已存放满”;
  }
  if (index<1 || index>length + 1)
  {
    throw “插入元素的职务来无意”;
  }
  //如何插入的地点合理,则拿各样表中于最后地点到指定插地点的素全部以后运动一个岗位
  for (int j = length; j >= index; j–)
  {
    data[j] = data[j – 1];
  }
  //给插入的职位放入指定的元素
  data[index – 1] = x;
  length++;
}

//实现顺序表删除指定地方的因素
template<class DataType>
DataType SeqList<DataType>::Delete(int index)
{
  //声明要取有的元素
  DataType x;
  //判断要去的职是不是站得住
  if (index<1 || index>length)
  {
    throw “删除的职务有无意”;
  }
  else
  {
    //取出指定地点的因素
    x = data[index-1];
    //将指定地方后的元素全体且上前移动一个职务
    for (int i = index; i < length; i++)
    {
      data[i – 1] = data[i];
    }
    //删除顺序表中的要素后,其长度减1
    length–;
  }
  return x;
}

//顺序输出顺序表中的因素
template<class DataType>
void SeqList<DataType>::PrintSeqList()
{
  if (length < 1)
  {
    throw “顺序表中并未元素”;
  }
  else
  {
    //顺序输出顺序表元素
    for (int i = 0; i < length; i++)
    {
       cout << data[i] << ” “;
    }
    cout << endl;
  }
}

 二、测试线性表之缘序表:TestSeqList.cpp

 

#include<iostream>
#include”SeqList.h”
using namespace std;
void show()
{
  cout << “—————————————” <<
endl;
}
int main()
{
  int array[10] = {1,3,4,2,5,6,8,7,9,10};
  SeqList<int> seqList = SeqList<int>(array,10);
  cout << “顺序表为:” << endl;
  seqList.PrintSeqList();
  show();
  cout << “顺序表的尺寸为:” <<
seqList.GetLength()<< endl;
  cout << “第四只岗位的元素是:” << seqList.GetElement(3)
<< endl;
  cout << “元素3的岗位是:” << seqList.GetLocal(3)
<< endl;
  show();
  cout << “在第5独岗位插入元素22” << endl;
  seqList.Insert(5, 22);
  cout << “顺序表为:” << endl;
  seqList.PrintSeqList();
  cout << “顺序表的长也:” << seqList.GetLength()<< endl;
  show();
  cout << “删除第5单职位的要素” << endl;
  seqList.Delete(5);
  cout << “顺序表为:” << endl;
  seqList.PrintSeqList();
  cout << “顺序表的尺寸为:” << seqList.GetLength()<< endl;
  show();
  return 0;
}

 

http://www.bkjia.com/cjjc/1204322.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1204322.htmlTechArticle线性表之顺序表C++实现,线性顺序 线性表底相继表
一、头文件:SeqList.h //顺序线性表的峰文件 #includeiostream const int
马克斯(Max)Size = 100; //定义顺序…

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图