青岛数据结构实训时 写的 一些代码

插入排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXL 10000

void InsertSort(int a[],int n)
{
    int i,j,temp;
    for(i=0; i<n; i++)
    {
      temp=a[i];
      j=i-1;
      while(j>=0&&temp<a[j])
      {
        a[j+1]=a[j];
        j--;
      }
      a[j+1]=temp;
    }
    for(i=0; i<n; i++)
    cout<<a[i]<<" "; 
    cout<<endl;
}
int main()
{
     int n,i,a[MAXL];
     cin>>n;
     for(i=0; i<n; i++)
         cin>>a[i];
     InsertSort(a,n);
    return 0;
}

冒泡排序

//冒泡排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXL 10000

int BubbleSort(int a[],int n)
{
    int i,j,t;
    for(i=0; i<=n-2; i++)
        for(j=0; j<=n-i-2; j++)
            if(a[j+1]<a[j])
            {
                t=a[j]; a[j]=a[j+1]; a[j+1]=t;
            }
            
            for(i=0; i<n; i++)
                cout<<a[i]<<" ";
            cout<<endl;
            return 0;
}
int main()
{
     int i,n,a[MAXL];
     cin>>n;
    for(i=0; i<n; i++)
        cin>>a[i];
    BubbleSort(a,n);
    return 0;
}

选择排序

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXL 10000

int a[MAXL];
void SelectSort(int a[],int n)
{
   int i,j,k,x;
   for(i=1; i<n; i++)
   {
     k=i-1;
     for(j=i; j<n; j++)
     {
       if(a[j]<a[k])
           k=j;
     }
     x=a[i-1];
     a[i-1]=a[k];
     a[k]=x;
   }
}

int main()
{
    int n,i;
    cin>>n;
    for(i=0; i<n; i++)
    {
      cin>>a[i];
    }
    SelectSort(a,n);
    for(i=0; i<n; i++)
       cout<<a[i]<<" ";
   cout<<endl;
    return 0;
}

练习1

#include <stdio.h>
#include <string.h>
#define MAXSIZE 10000
typedef struct node
{
    int elem[MAXSIZE];
    int last;
}Sqlist;
Sqlist list;

void show(Sqlist * Last)
{
    int i;
   for(i=0; i<(*Last).last; i++)
   printf("%d ",(*Last).elem[i]);
   printf("
");
}

int Sinsert(Sqlist &Last,int e,int loc)
{
    int i;
    if(loc<0||loc>=MAXSIZE)
    return 0;
    else
    {
     for(i=Last.last-1; i>=loc; i--)
     Last.elem[i+1]=Last.elem[i];
     Last.elem[loc]=e;
     Last.last++;
     return 1;
    }
}

int del(Sqlist &Last,int loc,int e)
{

   int i;
   if(loc<0||loc>=MAXSIZE)
       return 0;
   else
   {
     e=Last.elem[loc];
     for(i=loc; i<Last.last-1; i++)
     Last.elem[i]=Last.elem[i+1];
     Last.last--;
     return 1;
   }
}

int main()
{
  int i;
  int e,x;
  scanf("%d",&list.last);
  for(i=0; i<list.last; i++)
  scanf("%d",&list.elem[i]);
  scanf("%d%d",&e,&x);
  Sinsert(list,e,x);
  scanf("%d",&x);
  del(list,x,e);
  show(&list);
  return 0;
}

练习2

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXL 10000

typedef struct node
{
   char key;
   int data;
}Nodetype;
typedef Nodetype Sqlist[MAXL];    

int Seqsearch(Sqlist R,int n,char k)
{
   int i=0;
   while(i<n&&R[i].key!=k) ++i;
   if(i>=n)
   return -1;
   else
   return R[i].data;
}
int main()
{
    Sqlist R;
    int i,n,f;
    char k;
    cin>>n;
    cin>>k;
    for(i=0; i<n; i++)
    cin>>R[i].key>>R[i].data;
    f=Seqsearch(R,n,k);
    if(f==1)
    cout<<f<<endl;
    else
    cout<<"NO!"<<endl;
    return 0;
}

作业1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct node
{
    int data;
    struct node *next;
}Sqlist;

Sqlist *creat(int n)
{
    int i;
    Sqlist *head,*tail,*p;
    head = new Sqlist;
    head->next=NULL;
    tail=head;
    
    for(i=0; i<n; i++)
    {
      p=new Sqlist;
      cin>>p->data;
      p->next=NULL;
      tail->next=p;
      tail=p;
    }
    return head;
}

int locate(Sqlist *List, int loc)
{
    int sum=0;
    Sqlist *p;
    p=List;
    while(p->next!=NULL)
    {
      sum++;
      if(sum==loc)
      return p->next->data;
      p=p->next;
    }
    return -1;
}
int main()
{
    int n,loc;
    Sqlist *head;
    cin>>n;
    head=creat(n);
    cin>>loc;
    cout<<locate(head,loc)<<endl;
    /*r=head;
    while(r->next!=NULL)
    {
      cout<<r->next->data<<" ";
      r=r->next;
    }
    cout<<endl;*/
    return 0;
}

作业2

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXL 10000
int a[MAXL],n;

void QSort(int low,int high)
{
    if(low<high)
    {
        int x,l,h;
        l=low,h=high;
        x=a[low];
        while(low<high)
        {
            while(low<high&&a[high]>=x)  --high;
            a[low]=a[high];
            while(low<high&&a[low]<=x) ++low;
            a[high]=a[low];
        }
        a[low]=x;
        QSort(l,low-1);
        QSort(low+1,h);
    }
}

void show()
{
   int i;
   for(i=0; i<n; i++)
   {
       if(i!=n-1)
       printf("%d ",a[i]);
       else
       printf("%d
",a[i]);
   }
}
int main()
{
   printf("请在运行前在D盘建一个文件名为data,
属性为txt的文本文档,并在里面输入一些整型数据!

");
   system("pause");
   FILE *fp;
   int i;
   n=-1;
   fp=fopen("D:\data.txt","rt");
   while(~fscanf(fp,"%d",&a[++n]))
   {}
   fclose(fp);
   printf("排序前的顺序为:
");
   show();
   QSort(0,n-1);
   printf("排序后的顺序为:
");
   show();
   fp=fopen("D:\data.txt","at+");
   fprintf(fp,"排序后的顺序为:
");
   for(i=0; i<n; i++)
   {
       if(i!=n-1)
       fprintf(fp,"%d ",a[i]);
       else
       fprintf(fp,"%d
",a[i]);
   }
   fclose(fp);
   return 0;
}