C++线性表通过结构体实现操作和结构体字符串快速…

2019-05-08 07:23:37来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

#include<iostream>
#include<string>
#define ml 10
using namespace std;
typedef struct{//定义Data数据项
 std::string name;
 long num;
}Data;
struct Link{//定义结构体
 Data data[ml+1];
 int length;
}L;
void initLink(Link *p){//初始化,即便有数据可以覆盖写入增加效率
 p->length=0;
}
int lengthlink(Link *p){//返回节点数
 return p->length;
}
int insertlink(Link *p ,int n,Data data){//指定位置插入
 if(n<0||n>ml-1){
  return 0;
 }
 for(int i=p->length+1;i>=n;i--){
  p->data[i+1]=p->data[i];
 }
 p->data[n]=data;
 p->length++;
 return 1;
}
int lastinsertlink(Link *p,Data data){///不指定位置插入使用
 if(p->length>=ml){
  return 0;
 }
 p->data[++p->length]=data;
 return 1;
}
int deletelink(Link *p,int n){
 if(n<0||n>p->length){
  return 0;
 }
 for(int i=n;i<=p->length;i++){
  p->data[i]=p->data[i+1];
 }
 p->length--;
 return 1;
}
void sortstring(Link *p,int left,int right){
 int l=left;
 int r=right;
 
 Data f=p->data[(l+r)/2];
 while(l<r){
  while(strcmp(p->data[l].name.c_str(),f.name.c_str())<0 && l<right){
   l++;
  }
  while(strcmp(p->data[r].name.c_str(),f.name.c_str())>0 && r>left){
   --r;
  }
  
  if(l<=r){
   Data temp;
   temp=p->data[l];
   p->data[l]=p->data[r];
   p->data[r]=temp;
   l++;
   --r;
  }
 }
 if(l==r){
  l++;
 }
 if(left<r){
  sortstring(p,left,l-1);
 }
 if(l<right){
  sortstring(p,r+1,right);
 }
}
void viewLink(Link *p){
 for(int i=1;i<=p->length;i++){//输出从1开始,避免输出0位置的地址项
  cout<<"数据项:第"<<i<<"位置是  "<<p->data[i].name<<" "<<p->data[i].num<<endl;
 }
 cout<<"节点长度为: "<<p->length<<endl;
}
void main(){
 Data data[3]={{"a",10001},{"b",10002},{"c",10003}};
 Link list;
 initLink(&list);
 for(int i=0;i<3;i++){
  lastinsertlink(&list,data[i]);//测试追加节点方法插入节点,优点是效率。
 }
 viewLink(&list);
 Data data1={"d",50001};
 insertlink(&list,2,data1);///测试指定位置插入节点
 viewLink(&list);
 Data data2[2]={{"e",90001},{"f",80001}};///测试插入多个节点
 for(int j=0;j<2;j++){
  int t=2;
  insertlink(&list,t,data2[j]);
  t++;
 }
 viewLink(&list);
 sortstring(&list,1,6);///测试字符串排序
 viewLink(&list);
 deletelink(&list,4);//测试删除指定节点
 viewLink(&list);
}

测试通过结构体实现线性表的操作,同时也实现对字符串的排序, 快速排序和shell排序的结合,有效提高排序效率,注意排序时两个哨兵的位置。

 

 

 

 

 


原文链接:https://www.cnblogs.com/xiaozhihu/p/10816946.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Codeforces 1156F Card Bag(概率DP)

下一篇:NOIP 2011 Mayan游戏 大暴搜