#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);
}