数组实现线性表-VS2015.zip

  • #11
    了解作者
  • Visual C++
    开发工具
  • 919KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 1
    下载次数
  • 2018-03-09 16:15
    上传日期
通过C++完成数组实现线性表,是数据结构入门学习之一
数组实现线性表-VS2015.zip
内容介绍
#include<stdio.h> #include "array.h" //下面是简单的数组操作,后边要交代用类实现数组,便于学生理解类的集成 //插入一个元素 //s数组名,arrayL数组空间大小,realL数组里实际元素个数,index插入位置,data插入数据 void insertNode(int s[], int arrayL, int realL, int index, int data) { //当插入的位置不正确时,返回 if (index<0 || index>realL || realL + 1>arrayL) return; for (int i = realL; i>index; i--) s[i] = s[i - 1]; s[index] = data; } //删除一个元素,让学生自己编 //s数组名,realL数组里实际元素个数,index删除位置 void deleteNode(int s[], int realL, int index) { //当删除的位置不正确时,返回 //元素移位 } //折半查找,必须是已排序,从小到大排序 //返回元素在数组中的下标,-1表示没找到 int binsearch(int s[], int count, int data) { int l, r, flag = -1;//-1代表不成功,其他代表成功且位置信息 l = 0; r = count; int k = 0;//代表一半那个位置,初始设置为0 while (l != r) { if ((l + r) / 2 == k) {//如果前后两次的l、r不变,则不成功,跳出循环 break; } k = (l + r) / 2; if (data>s[k]) l = k; else if (data<s[k]) r = k; else { flag = k;//成功 break; } } return flag; } //这个数据结构为了实现分块查找用的 struct indexTable { int maxKey;//块内关键字不超过最大值 int start;//块开始的位置 }; //直接插入排序,从小到大,方案1,一边向前看,一边向后移 void directInsertSort(int s[], int n) { int i, j, t; for (i = 1; i<n; i++) { t = s[i];//先保存数据 for (j = i - 1; j >= 0; j--) {//依次向前查看,每看到一个大于自己的数,就往后挪一个数据 if (t<s[j]) s[j + 1] = s[j]; else break; } s[j + 1] = t; } } //直接插入排序,从小到大,方案2,找到插入位置,将数据统一后移,插入 void directInsertSort2(int s[], int n) { int i, j, t, k; for (i = 1; i<n; i++) { for (j = i - 1; j >= 0; j--) {//先找到插入位置 if (s[i]>s[j]) break; } if (i != j + 1) {//说明s[i]需要向前插入 t = s[i];//保存s[i],其他的才可以后挪 for (k = i - 1; k >= j + 1; k--) { s[k + 1] = s[k]; } s[j + 1] = t;//挪出地方,插入 } } } //数组s,长度n,间隔interval进行插入排序 void directInsert_forShell(int s[], int n, int interval) { int i, j, t; for (i = interval; i<n; i+= interval) { t = s[i];//先保存数据 //向前每看到一个大于自己的数,就往后挪一个数据 for (j = (i - 1)*interval; j >= 0; j-= interval) { if (t<s[j]) s[(j + 1)*interval] = s[j*interval]; else break; } s[(j + 1)*interval] = t; } } //shell排序, void shellSort(int s[], int n) { int i, j, k; //i的间隔为5,3,1 for (i = 5; i >= 1; i -= 2) { //调用间隔为i的插入排序 for (j = 0; j < i; j++) directInsert_forShell(s + j, n - j, i); } } //快速排序,将轴值位置做第一个空闲,然后从两端向中间,检查空闲位置并移动数据 void quikSort(int s[], int left, int right) { if (right<= left)//左右下标重合时一次排序结束 return; int k = (left+right) / 2;//轴值位置 //分割前先将轴值存放在临时单元,将数组末端元素放在轴值位置 int tempt = s[k]; s[k] = s[right]; int l = left, r = right; while (r!=l) { //先从左端找小于轴值的位置 while (s[l] <= tempt&&l<r) l++; if(l<r){//放入空闲位置 s[r] = s[l]; r--; } //从右端找 while (s[r] > tempt&&r>l) r--; //放入空闲位置 if (r > l) { s[l] = s[r]; l++; } } //一趟排序结束,将轴值填入序列 s[l] = tempt; //递归调用左右两侧快速排序 quikSort(s, 0, l - 1); quikSort(s, r + 1, right); } //直接选择排序 void selectSort(int s[], int n) { int i, j, k,t; for (i = 0; i < n - 1; i++) { k = i;//找后边新的最小 for (j = i + 1; j < n; j++) if (s[k] > s[j]) k = j; if (k != i) {//互换 t = s[k]; s[k] = s[i]; s[i] = t; } } } //归并排序 void mergeSort(int s[], int left, int right) { if (left>= right)//终止递归 return; int middle = (left + right) / 2; mergeSort(s, left, middle);//递归对左侧部分排序 mergeSort(s, middle + 1, right);//递归对右侧部分排序 //左右已经排序的序列,合并 int i, j, k; int *tempS = new int[right-left+1];//申请临时数组,存放合并结果 i = left; j = middle + 1; k = 0; while (i <= middle && j <= right) { if (s[i] <= s[j]) { tempS[k] = s[i]; k++; i++; } else { tempS[k] = s[j]; k++; j++; } } while (i <= middle) {//剩余的左侧完全拷贝 tempS[k] = s[i]; k++; i++; } while (j <= right) {//剩余的右侧完全拷贝 tempS[k] = s[j]; k++; j++; } for (i = left; i <=right; i++)//结果拷贝回原数组,注意是从left到right s[i] = tempS[i-left]; delete[]tempS;//释放资源 } void main() { int s[10] = { 5,2,4,3,7,9,0 }; //sort(s,7); //directInsertSort2(s, 7); //shellSort(s, 7); //quikSort(s, 0, 6); //归并排序 mergeSort(s, 0, 3); for (int i = 0; i<4; i++) { printf("%3d", s[i]); } printf("\n"); int t; scanf_s("%d", &t); /* insertNode(s, 10, 7, 3,6); for(i=0;i<8;i++){ printf("%3d",s[i]); } printf("\n"); */ /* arrayLinearList abc; abc.inputData(); abc.display(); int k=abc.binsearch(3); printf("%d\n",k); abc.inputData(); k=abc.binsearch(3); printf("%d\n",k); */ //下面是分块查找 /* struct indexTable indexArray[4]={35,0,60,5,90,10};//存放索引表,3块,每块5个记录 int data[15]={9,22,12, 14, 35, 42, 44, 38, 48, 60, 77, 90, 80, 82,75 };//待排序的序列 int key=1;//待查关键字 int i, j; for(i=0;i<3;i++){//确定所在的块 if(key<=indexArray[i].maxKey) break; } if(i>=3) printf("查找失败\n"); else{//到具体块里顺序查找 for(j=0;j<5;j++){ if(key==data[indexArray[i].start+j]) break; } if(j<5) printf("待查元素在数组中的下标是:%d\n",indexArray[i].start+j); else printf("查找失败\n"); } */ }
评论
    相关推荐
    • C++ Primer
      C++经典教程,其内容是C++大师Stanley B. Lippman丰富的实践经验和C++标准委员会原负责人Josée Lajoie对C++标准深入理解的完美结合,已经帮助全球无数程序员学会了C++。 对C++基本概念和技术全面而且权威的阐述,对...
    • c++课件
      c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件c++课件
    • C++
      C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++C++
    • Effective C++
      学习c++的经典书籍!每一个学习c++的人有时间最好看看!你会获得很大收获!
    • C++ primer
      本文档具有C++ primer 以及 C++ primer 标准答案各一份,内容清晰充实!希望与热爱C++的学友们一起同舟共济,努力学习!
    • c++information
      c++c++c++c++c++c++c++c++c++c++c++c++
    • SourceStyler C++
      用DEV-C++写代码很方便,就是不能格式化有点郁闷 c++格式化的好工具 效率高
    • c++yuyanbiancheng
      这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!这是C和C++集成的编程环境!
    • effective C++
      有关C++编程方面的检验性介绍,对由C转向C++,和有C++编程基础的程序员有帮助,不过是英文版
    • C++ Primer
      本书是久负盛名的C++经典教程引,其内容是C++大师Stanley B. Lippman丰富的实践经验和C++标准委员会原负责人Josée Lajoie对C++标准深入理解的完美结合,已经帮助全球无数程序员学会了C++