/* 2005-03-04   -------------------------------------------------------
  实验内容：
   编写程序建立顺序存储的线性表L，其数据元素按非递减有序排列，插入一个
   元素X后，该线性表L仍保持有序。
  实验要求：
   L的存储结构为：
   #define LIST_INIT_SIZE 100  // 顺序表存储空间的初分配量
   #define LISTINCREMENT  10   // 顺序表存储空间的分配增量  
  struct   //线性表的结构
  {
   int *elem;    //存储空间的基地址
   int length;   //当前的长度
   int listsize; //当前分配的容量
  };
  测试数据：
      建立： 1,3,5,7,9
   插入： x=-1,6,10 
-----------------------------------------------------------------------*/  

#include
#include
#include
#include

#define LIST_INIT_SIZE 100  // 顺序表存储空间的初分配量
#define LISTINCREMENT  10   // 顺序表存储空间的分配增量

typedef struct   //线性表的结构
{
 int *elem;    //存储空间的基地址
 int length;   //当前的长度
 int listsize; //当前分配的容量
}SQLIST;

void Create(SQLIST &L)      //建立线性表
{
 L.elem =(int*)malloc(LIST_INIT_SIZE* sizeof(int));
 if(!L.elem)
  printf("为线性表分配空间失败!");

 L.length =0;
 L.listsize =LIST_INIT_SIZE;
}

 
void Insert(SQLIST &A,int x)     //实现有序的插入操作
{
 if(A.length ==A.listsize) printf("线性表错误!");

 if(x > A.elem[A.length-1])
  A.elem[A.length]=x;   //与最大的元素进行判断，以决定是否插在最后
 else
 {
  int i=0;
  while(x >= A.elem[i])
   i++;   //从第一个元素起，寻找正确的插入位置

  for(int j=A.length; j>=i; j--)
   A.elem[j+1]=A.elem[j];  //将所找位置后面的所有数据都向右移动一个位置

  A.elem[i]=x;  //插入新的数据
 }
 A.length++; //顺序表的长度加1
}

void main()
{
 printf("程序说明:\n");
 printf("    建立顺序存储的单链表，其数据元素按元素值非递减有序排列，插入一个数据元素后，该线性表仍保持有序\n\n");

 SQLIST s;
 Create(s);    //为线性表分配空间

 s.elem[0]=1;  //建表
 s.elem[1]=3;
 s.elem[2]=5;
 s.elem[3]=7;
 s.elem[4]=9;
 s.length=5;
 printf("\n\n已建立的顺序表为：\n");
 for(int i=0; i  printf("%d ",s.elem[i]);

 printf("\n\n请输入要插入的数据:\n ");
 int tmp;
 scanf("%d",&tmp);
 
 Insert(s,tmp);
 
 printf("\n\n插入数据后的顺序表为：\n");
 for(i=0; i  printf("%d ",s.elem[i]);

 _getch(); //如果不加如该句，则执行用Visual C++编译后的exe文件，控制台窗口会一闪而过，看不请执行结果:)
}

/*2005-03-02  ----------------------------------------------------------- 
  题目要求：
    用单链表实现如下内容：建立有多个学生的成绩档案（以学号为0为结束标志），
    每个学生包括学号、成绩，并实现新成员的加如和旧成员的删除。
--------------------------------------------------------------------------*/

#include
#include

typedef struct student     //单链表的存储结构
{
 long num;
 float score;
 struct student* next;
}LINK;

int n;   //定义一个全局变量(链表的结点个数)

LINK* Create()   //建立
{
 LINK* head;
 LINK* p1,*p2;
 n=0;
 p1=p2=(LINK*)malloc(sizeof(LINK));
 scanf("%ld,%f",&p1->num,&p1->score);
 head=NULL;
 while(p1->num !=0)
 {
  n=n+1;
  if(n==1)
   head=p1;
  else                  //p1指向新开的结点,p2指向链表中的最后一个结点
   p2->next=p1;      //把p1所指的结点连在p2所指结点的后面
  p2=p1;      //p2指向链表中的最后一个结点  
  p1=(LINK*)malloc(sizeof(LINK));
  scanf("%ld,%f",&p1->num,&p1->score);
 }
 p2->next=NULL;

 return head;
}

LINK* Insert(LINK *head,LINK *stud) //插入
{
 LINK *p0,*p1,*p2;
 p1=head;   //p1指向第一个结点
 p0=stud;   //p0指向待插入的结点
 if(head==NULL)
 {
  head=p0;
  p0->next=NULL;
 }
 else
 {
  while((p0->num > p1->num) && (p1->next !=NULL))
  {
   p2=p1;  //p2指向p1刚才所指的结点
   p1=p1->next;
  }
  if(p0->num < p1->num)
  {
   if(head==p1) head=p0;
   else
    p2->next=p0;
   p0->next=p1;
  }
  else
  {
   p1->next=p0;
   p0->next=NULL;
  }
 }
 n=n+1;
 return head;
}

LINK* Delete(LINK*head,long num)   //删除
{
 LINK *p1,*p2;
 if(head==NULL)
 {
  printf("链表为空!\n\n");
  return(head);
 }
 p1=head; // p1指向第一个结点
 while(num !=p1->num && p1->next !=NULL)  //如果要删除的不是第一个接点，
 {
  p2=p1;        //将p1赋给p2，使p2指向刚才检查过的结点
  p1=p1->next;  //p1指向下一个结点
 }
 if(num==p1->num)  //如果删除的是第一个结点
 {
  if(p1==head)
   head=p1->next;  //head指向原来的第2个结点
  else
   p2->next=p1->next;
  
  printf("删除了:%ld",num);
  n=n-1;
 }
 else
  printf("没有找到%ld",num);

 return(head);
}

void print(LINK *head)                //输出
{
 LINK* p;
 printf("现在链表中的%d个记录是:\n",n);
 p=head;
 if(head !=NULL)
  do
  {
   printf("%ld %5.1f\n",p->num,p->score);
   p=p->next;
  }while(p!=NULL);
}

void main()
{
 printf("\n---------------------单链表的操作--------------------------\n\n");
 LINK *head,*stu;
 long Delete_num;
 printf("请输入记录(学号,成绩),输入学号为0则结束:\n");

 head=Create();                        //建立操作
 print(head);

 printf("请输入要插入的记录:\n");      //插入操作
 stu=(LINK*)malloc(sizeof(LINK));
 scanf("%ld,%f",&stu->num,&stu->score);
 while(stu->num !=0)
 {
  head=Insert(head,stu);
  print(head);  
  printf("请输入要插入的记录:\n");
  stu=(LINK*)malloc(sizeof(LINK));
  scanf("%ld,%f",&stu->num,&stu->score);
 }
 

 printf("请输入要删除的数据:\n");      //删除操作
 scanf("%ld",&Delete_num);
 while(Delete_num !=0)
 {
  head=Delete(head,Delete_num);
  print(head);
  printf("请输入要删除的数据:\n");
  scanf("%ld",&Delete_num);
 }
}

/*  2005-03-2  -----------------------------------------------
实验内容：
       有n个字符的字符串，判断字符串是否中心对称。
    如: xyzzyx和xyzyx都是中心对称的字符串
实验要求：
    字符串放在单链表中，内容1由栈实现（存储结构自定）
    并实现利用栈的入栈和出栈完成判断。
-------------------------------------------------------------*/

#include
#include
#include

#define max 100

//////////////////定义单链表的结点类型////////////////////
typedef struct node
{
 char data;
 struct node* next;
}LinkList;

/////////////////根据输入的字符(存储在字数组中)建立一个不带结点的单链表/////////////
LinkList* create(char s[])  //函数返回的类型为指针
{
 LinkList *head,   //头指针
       *newNode, //newNode始终指向新开的结点
    *tail;    //tail始终指向链表中的最后一个结点
 
 for(int i=0;s[i]!=@#\0@#;i++)
 {
  newNode=(LinkList*)malloc(sizeof(LinkList));  //新开一个结点
  newNode->data=s[i];
  newNode->next=NULL;

  if(i==0)      //如果只输入了一个字符
  {
   head=newNode;
   tail=head;
  }
  else
  {
   tail->next=newNode;  //把新开的结点连接到链表的最后一个结点上
   tail=newNode;
  }
 }
 return head;
}

////////////////////定义栈的存储类型//////////////////////////
typedef struct
{
 char *base;   //栈顶指针（始终指向栈顶元素的下一个位置）
 char *top;    //栈底指针（始终指向栈底）
}stack;

void InitStack(stack &s)      //栈的初始化
{
 s.base=(char*)malloc(max*sizeof(char));
 s.top=s.base;
}
void push(stack &s,char e)   //进栈函数
{
 *s.top++=e;
}
char pop(stack &s,char &e)   //出栈函数
{
 e=*--s.top ;
 return e;
}

///////////////判断以单链表存储的字符串是否对称的函数////////////////
int judge(LinkList *head)
{
 stack s;
 char e;
 InitStack(s);  //定义一个栈并初始化
 
 LinkList* p=head;  //把头指针赋给p,即让p指向第一个结点
 while(p !=NULL)
 {
  push(s,p->data);
  p=p->next;
 }
 p=head;
 while(p!=NULL)   //将栈中的元素弹出，逐个与链表中的元素比较（可以看成是把链表换个方向，然后与原来的链表比较）
 {
  if(p->data == pop(s,e))
   p=p->next;
  else
   break;  //如果不相等，说明不是对称，调处循环
 }
 if(p==NULL) return 1;
 else return 0;
}

void main()
{
 printf("程序说明:\n");
 printf("目的：判断字符串是否关于中心对称.\n");
 printf("方法：字符串用单链表实现，将字符串全部入栈然后比较\n\n");

 char str[max]; //定义一个字符数组，用来存储输入的字符
 LinkList *h;
 while(1)
 {
  printf("\n\n请输入字符串(输入cls清屏,exit退出):");
  gets(str);
  if(strcmp(str,"exit")==0)   break;
  if(strcmp(str,"cls")==0) system("cls");
  
  switch(judge(create(str)))  //根据输入的字符串(存储在字符数组中)建立单链表然后进行判断
  {
  case 1:
   printf("\n   ●%s是中心对称的的字符串\n",str);
   break;
  case 0:
   printf("\n   ◆%s不是关于中心对称的\n",str);
   break;
  }
 }
}

/* 2005-03-04  ------------------------------------------------
  算法分析:

  1.单词的个数由空格出现的次数决定(连续的空格作出现一次);
  2. 若当前字符不是空格,而它前面的字符是空格,则令num++;
  3. 若当前字符不是空格,前面字符也不是空格,是原单词继续,num不加1
  4.用word表示前一个字符是否为空格
 是 word=0
 不是 word=1
 5.用for 语句对输入的一行字符串,逐一检查
 Y 未出现新单词,使word=0,num不累加
 当前字符=空格
 前一字符为空格(word=0),num++, word=1
 N 前一字符不是空格(word=1),num不加1
---------------------------------------------------------------*/

#include
#include
#include

void main()
{
 printf("-------------------统计单词个数-----------------\n\n");
 printf("1.测试\n");
 printf("2.输入\n");
 printf("3.退出\n");
 
 char string[80];
 int num=0,   //用于统计单词个数
  word=0;  //word作为判断是否单词的标志,word=0表示前一个字符为空格
 char c;
 
 char cSel=getch();
 if(cSel==@#1@#)
 {
  strcpy(string,"so  before   you     go out   you should  discuss");
  printf("%s\n",string);
 }
 if(cSel==@#2@#)
 {
  printf("请输入一行文本: \n");
  gets(string);
 }
 if(cSel==@#3@#)
  return;  
 
 for(int i=0;(c=string[i])!=@#\0@#;i++)
 {
  if(c==@# @#)  word=0;
  else if(word==0)
  {
   word=1;
   num++;
  }
 }
 printf("单词的个数是:%d \n",num);
 _getch();
} 

/*  2005-03-04   -----------------------------------------------
    给定一棵二叉树，求出二叉树的深度。 测试如下的二叉数：
                           A
     / \
    B   D
   / \
         E   C
          \
    F
   / \
         G   H     该二叉树应该这样输入 ABE##C#FG##H##D##
---------------------------------------------------------------*/

#include
#include
#include

#define MAX 20
#define NULL 0

typedef struct BiTNode   //二叉树的二叉链表存储表示
{
    char data; 
    struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree;

void CreateBiTree(BiTree *T)   //建立二叉树
{ 
 char ch; 
 ch=getchar();
 
 if (ch==@##@#) (*T)=NULL;                    // #代表空指针 
 else
 {
  
  (*T)=(BiTree) malloc(sizeof(BiTNode));//申请结点     
  (*T)->data=ch;                        //生成根结点    
  CreateBiTree(&(*T)->lchild) ;         //构造左子树    
  CreateBiTree(&(*T)->rchild) ;         //构造右子树    
 }
}

void PreOrder(BiTree T)    // 先序遍历二叉树递归算法
{
 if (T)
 {
  printf("%2c",T->data);    //访问根结点，此处简化为输出根结点的数据值
  PreOrder(T->lchild);      //先序遍历左子树
  PreOrder(T->rchild);      //先序遍历右子树
 }
}

int depth(BiTree T  )   //求二叉树的深度
{ 
 int dep1,dep2; 

 if (T==NULL)
  return 0; 
 else
 {
  dep1=depth(T->lchild); 
  dep2=depth(T->rchild); 
  return dep1 > dep2? dep1+1 : dep2+1; 
 }
}

void main()
{ 
 BiTree T=NULL; 
 printf("\n请输入数据来建立一棵二叉树：\n");
 printf("\n输入规则：\n");
 printf("    如果二叉树为空，则直接输入#回车。否则，按先序顺序输入各个结点的值，如果结点的左子树或右子树为空，则输入#。(如：ABE##C#FG##H##D##)\n");
 
 CreateBiTree(&T); 

 printf("\n该二叉树的先序遍历顺序为:\n"); 
 PreOrder(T);  
   
 printf("\n该二叉树的深度为：%d", depth(T));

 _getch();
}

/* 2005-03-05 ---------------------------------------------------------------------
  实验内容：
   针对某个集体（比如所在班级）中的人名设计一个哈希表，使的平均查找的长度不超过2
   完成相应的建表和查表的程序
  实验要求：
      假设人名为姓名的汉语拼音形式，待填入哈希表的人名工有30个，取平均查找长度的上限
   为2。哈希函数用除留余数法构造，用伪散列探测再散列法处理冲突。
  测试数据
      自定义。
-----------------------------------------------------------------------------------*/

#include
#include
#include
//#include

#define HASH_LEN 50                     //哈希表的长度        
#define M 47                           
#define NAME_NO 30                     //人名的个数       

typedef struct NAME      
{
 char *py;   //名字的拼音
 int k;      //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];                

typedef struct  hterm    //哈希表
{
 char *py;  //名字的拼音
 int k;     //拼音所对应的整数
 int si;    //查找长度
}HASH;
HASH HashList[HASH_LEN];                           

/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()              
{
 NameList[0].py="chenghongxiu";
 NameList[1].py="yuanhao";
 NameList[2].py="yangyang";
 NameList[3].py="zhanghen";
 NameList[4].py="chenghongxiu";
 NameList[5].py="xiaokai";
 NameList[6].py="liupeng";
 NameList[7].py="shenyonghai";
 NameList[8].py="chengdaoquan";
 NameList[9].py="ludaoqing";
 NameList[10].py="gongyunxiang";
 NameList[11].py="sunzhenxing";
 NameList[12].py="sunrongfei";
 NameList[13].py="sunminglong";
 NameList[14].py="zhanghao";
 NameList[15].py="tianmiao";
 NameList[16].py="yaojianzhong";
 NameList[17].py="yaojianqing";
 NameList[18].py="yaojianhua";
 NameList[19].py="yaohaifeng";
 NameList[20].py="chengyanhao";
 NameList[21].py="yaoqiufeng";
 NameList[22].py="qianpengcheng";
 NameList[23].py="yaohaifeng";
 NameList[24].py="bianyan";
 NameList[25].py="linglei";
 NameList[26].py="fuzhonghui";
 NameList[27].py="huanhaiyan";
 NameList[28].py="liudianqin";
 NameList[29].py="wangbinnian";
 
 char *f;
 int r,s0;
 
 for (int i=0;i {
  s0=0;
  f=NameList[i].py;
  
  for (r=0;*(f+r) != @#\0@#;r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
   s0=*(f+r)+s0;
  
  NameList[i].k=s0;
 } 
}

/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()   
{
 for (int i=0; i {
  HashList[i].py="";
  HashList[i].k=0;
  HashList[i].si=0;
 }
 
 for (i=0;  i {
  int sum=0;
  int adr=(NameList[i].k) % M;    //哈希函数
  int d=adr;
  if(HashList[adr].si==0)        //如果不冲突
  {
   HashList[adr].k=NameList[i].k;
   HashList[adr].py=NameList[i].py;
   HashList[adr].si=1;
  }
  else   //冲突  
  {
   do
   {
    d=(d+((NameList[i].k))%10+1)%M;  //伪散列    
    sum=sum+1;  //查找次数加1    
   }while (HashList[d].k!=0);
   
   HashList[d].k=NameList[i].k;
   HashList[d].py=NameList[i].py;
   HashList[d].si=sum+1;
  }
 }
}

/*-------------------------------------查找------------------------------------*/
void  FindList()    
{ 
 printf("\n\n请输入姓名的拼音:   ");    //输入姓名
 char name[20]={0}; 
 scanf("%s",name); 
 
 int s0=0;
 for (int r=0;r<20;r++)    //求出姓名的拼音所对应的整数(关键字)
  s0+=name[r]; 
 
 int sum=1;
 int adr=s0 % M;  //使用哈希函数
 int d=adr;
 
 if(HashList[adr].k==s0)         //分3种情况进行判断
  printf("\n姓名:%s  关键字:%d  查找长度为: 1",HashList[d].py,s0); 
 else if (HashList[adr].k==0)
  printf("无该记录!");
 else
 {
  int g=0;
  do
  {
   d=(d+s0%10+1)%M;      //伪散列                      
   sum=sum+1;
   if (HashList[d].k==0)
   {
    printf("无记录! ");  
    g=1;     
   }
   if (HashList[d].k==s0)
   {    
    printf("\n姓名:%s  关键字:%d  查找长度为:%d",HashList[d].py,s0,sum); 
    g=1;  
   }
  }while(g==0);   
 }  
}

/*--------------------------------显示哈希表----------------------------*/
void  Display()        
{
   printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式

 for(int i=0; i<15; i++)
 {
  printf("%d ",i); 
  printf("\t%d ",HashList[i].k);
  printf("\t\t%d ",HashList[i].si);
  printf("\t\t%d ",(HashList[i].k)%M);
  printf("\t %s ",HashList[i].py);
  printf("\n");
 }

 printf("按任意键继续显示...\n");  //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
 getch();
 for( i=15; i<30; i++)
 {
  printf("%d ",i); 
  printf("\t%d ",HashList[i].k);
  printf("\t\t%d ",HashList[i].si);
  printf("\t\t%d ",(HashList[i].k)%M);
  printf("\t %s ",HashList[i].py);
  printf("\n");
 }

 printf("按任意键继续显示...\n");
 getch();
 for( i=30; i<40; i++)
 {
  printf("%d ",i); 
  printf("\t%d ",HashList[i].k);
  printf("\t\t%d ",HashList[i].si);
  printf("\t\t%d ",(HashList[i].k)%M);
  printf("\t %s ",HashList[i].py);
  printf("\n");
 }

 printf("按任意键继续显示...\n");
 getch();
 for( i=40; i<50; i++)
 {
  printf("%d ",i); 
  printf("\t%d ",HashList[i].k);
  printf("\t\t%d ",HashList[i].si);
  printf("\t\t%d ",(HashList[i].k)%M);
  printf("\t %s ",HashList[i].py);
  printf("\n");
 }
 
 float average=0;
 for (i=0;i  average+=HashList[i].si; 
 average/=NAME_NO;
 printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average); 
}

/*--------------------------------主函数----------------------------*/
void main()
{
/*  ::SetConsoleTitle("哈希表操作");       //Windows API函数,设置控制台窗口的标题
 HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
 ::SetConsoleTextAttribute(hCon, 10|0);   //设置文本颜色
*/
 printf("\n------------------------哈希表的建立和查找----------------------");
 InitNameList();                               
 CreateHashList ();                       
 
 while(1)
 {
  printf("\n\n");
  printf("    1. 显示哈希表\n"); 
  printf("    2. 查找\n"); 
  printf("    3. 退出\n");
  
err:  
  char ch1=getch();
  if (ch1==@#1@#)  
   Display();  
  else if (ch1==@#2@#) 
   FindList();
  else if (ch1==@#3@#) 
   return;
  else
  {
   printf("\n请输入正确的选择!");
   goto err;
  }
 }
}

/*  输入若干个国家名，按照字典顺序将这写国名排序
    要求：
      所有国名全用大写或小写，要求用Shell排序算法
    测试数据 ：SINGAPORE  SWEDEN KOREA NETHRLANDS CHINA BRITAIN POLAN    */

#include
#include
#include

void main()
{
 printf("----------------用Shell排序对字符串按字典顺序排序(2005/03/04)------------------\n\n\n");
 char a[7][20]={  "SINGAPORE",
      "SWEDEN",
      "KOREA",
      "NETHERLANDS",
      "CHINA",
      "BRITAIN",
      "POLAND"      };   //定义一个二维数组，用来保存要比较的几个单词

 printf("排序前的几个单词是：\n");   //输出
 for(int i=0; i<7; i++)
  printf("\t%s\n",a[i]);
 printf("\n\n");

/*-------------------Shell排序---------------------------------------*/
 int n=7;      //单词的个数
 int h=n/2;
 char temp[20];
 while(h >= 1)
 {
  for(int i=h; i  {
   strcpy(temp,a[i]);
   
   int j=i;
   while(j >= h   &&   strcmp(temp, a[j-h]) < 0 )
   {
    strcpy(a[j],a[j-h]);
    j-=h;
   }
   strcpy(a[j],temp);
  }
  h/=2;
 }
/*-------------------Shell排序---------------------------------------*/

 printf("按字典顺序排序以后的几个单词是：\n");  //输出
 for(i=0; i<7; i++)
  printf("\t%s\n",a[i]);

 _getch();
}