一、实验目的 通过该实验,深入理解顺序表的逻辑结构、物理结构等概念,掌握顺序表基本操作的编程实现,注意顺序表插入、删除等操作过程中数据元素的移动现象,培养学生编写程序时,要考虑程序的强壮性,熟练掌握通过函数参数返回函数结果的办法。 二、实验内容 编程实现顺序表的基本操作,最好用菜单形式对应各个操作,使其编成一个完整的小软件。 三、主要源代码
#include <iostream> #include <stdlib.h> using namespace std; #define list_insize 100 #define listincrase 10 typedef struct{ int *p;//存储空间基址 int len;//当前长度 int lstsize;//当前分配的存储容量 }_list; void xianshi(int i,string text);//界面格式化输出函数 int creatlist(_list &l);//初始化线性表 int destroylist(_list &l);//销毁线性表 int clearlist(_list &l);//清空线性表 int panduan(_list &l);//判断线性表是否为空 int get_list_length(_list &l);//获取线性表的长度 int get_list_select_value(_list &l,int q);//获取指定位置的值 int get_list_select_posization(_list &l,int q);//获取输入值的位置 int get_list_top(_list &l,int q);//前驱 int get_list_next(_list &l,int q);//后继 int insert_list_select_posization(_list &l,int i,int q);//在指定位置插入 int delete_lis_select_value(_list &l,int i);//删除指定位置元素 int view_list(_list &l);//读取线性表的所有值 int hebinglist(_list &l1,_list &l2,_list &l3);//合并两个任意的非递减顺序的线性表 int main() { int n=0,i=1; _list a[1000]; xianshi(1,"初始化一个线性表"); xianshi(2,"销毁线性表"); xianshi(3,"清空线性表"); xianshi(4,"判断线性表是否为空"); xianshi(5,"求取线性表长度"); xianshi(6,"获取线性表中指定位置的元素"); xianshi(7,"获取线性表元素的位置"); xianshi(8,"求前驱"); xianshi(9,"求后继"); xianshi(10,"在线性表指定位置插入元素"); xianshi(11,"删除线性表指定位置的元素"); xianshi(12,"显示线性表"); xianshi(13,"合并两个非递减有序的线性表"); cout<<" 退出输入一个负数"<<endl; cout<<"请输入操作代码:"<<endl; bool continuedo=false;//定义一个波尔函数,用来控制未初始化一个线性表无法执行操作 do { cin>>n; if(n<0) { return 0; } else { switch(n) { case 1: { if(creatlist(a[i])==1) { cout<<"初始化线性表成功!线性表为:a"<<i<<endl; i++; continuedo=true; } else { cout<<"初始化线性表失败!"<<endl; } break; } case 2:{ if(continuedo==true) { cout<<"请输入要销毁的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { destroylist(a[m]); cout<<"已经销毁线性表a"<<m<<endl; } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 3: { if(continuedo==true) { cout<<"请输入要清空的线性表序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { clearlist(a[m]); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 4: { if(continuedo==true) { cout<<"请输入要判断的线性表序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { if(panduan(a[m])==1) { cout<<"该线性表为空!"<<endl; } else { cout<<"该线性表不为空!"<<endl; } } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 5: { if(continuedo==true) { cout<<"请输入要测量的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { cout<<get_list_length(a[m])<<endl; } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 6: { if(continuedo==true) { cout<<"请输入要查找的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { int q=0; cout<<"请输入要查找的元素序号:"<<endl; cin>>q; get_list_select_value(a[m],q); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 7: { if(continuedo==true) { cout<<"请输入要查找的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { cout<<"请输入要查询的元素:"<<endl; int q=0; cin>>q; get_list_select_posization(a[m],q); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 8:{ if(continuedo==true) { cout<<"请输入要查找的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { cout<<"请输入要查询的位置:"<<endl; int q=0; cin>>q; get_list_top(a[m],q); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 9:{ if(continuedo==true) { cout<<"请输入要查找的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { cout<<"请输入要查询的位置:"<<endl; int q=0; cin>>q; get_list_next(a[m],q); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 10:{ if(continuedo==true) { cout<<"请输入要插入的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { char mm='y'; do { cout<<"请输入要插入的位置:"<<endl; int qq=0; cin>>qq; cout<<"请输入要插入的元素:"<<endl; int q=0; cin>>q; insert_list_select_posization(a[m],qq,q); cout<<"输入n退出!,输入y继续!"<<endl; cin>>mm; if(mm=='n') { break; } }while(true); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 11:{ if(continuedo==true) { cout<<"请输入要删除的元素所在线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { cout<<"请输入要删除元素的位置:"<<endl; int qq=0; cin>>qq; cout<<"删除的元素为:"<<delete_lis_select_value(a[m],qq)<<endl; } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 12:{ if(continuedo==true) { cout<<"请输入要查看的线性表的序号:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; } else { view_list(a[m]); } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } case 13:{ _list aa; creatlist(aa); if(continuedo==true) { cout<<"请输入要合并线性表的序号1:"<<endl; int m=0; cin>>m; if(m>i) { cout<<"不存在!"<<endl; break; } else { cout<<"请输入要合并线性表的序号2"<<endl; int qq=0; cin>>qq; if(qq>i) { cout<<"不存在!"<<endl; break; } else { hebinglist(a[m],a[qq],aa); view_list(aa); } } } else { cout<<"还未初始化线性表,请先初始化一个线性表。"<<endl; } break; } default:{ cout<<"输入不合法!"<<endl; } } } cout<<" 退出输入一个负数"<<endl; cout<<"请输入操作代码:"<<endl; }while(true); return 0; } void xianshi(int i,string text) { if(i<10) { cout<<i<<"----"<<text<<endl; } if(i>=10) { cout<<i<<"---"<<text<<endl; } } int creatlist(_list &l) { l.p=(int *)malloc(list_insize*sizeof(int)); if(!l.p) { exit(-2); } l.len=0; l.lstsize=list_insize; return 1; } int destroylist(_list &l) { free(l.p); l.p=NULL; l.len=0; l.lstsize=0; return 1; } int clearlist(_list &l) { l.len=0; return 0; } int panduan(_list &l) { if(l.len==0) { return 1; } else { return -1; } } int get_list_length(_list &l) { return l.len; } int get_list_select_value(_list &l,int q) { int *pt=l.p; if(q>l.len) { cout<<"输入数据大于线性表长度!"<<endl; } else { for(int i=1;i<q;i++) { pt++; } cout<<"要查找的元素为:"<<*pt<<endl; } return 1; } int get_list_select_posization(_list &l,int q) { int *pt=l.p; bool _find=false; for(int i=0;i<l.len;i++) { if(*pt==q) { cout<<"当前元素位置为:"<<i+1<<endl; _find=true; } pt++; } if(_find==false) { cout<<"未找到该元素。"<<endl; } return 1; } int get_list_top(_list &l,int q) { int *pt=l.p; if(q==1) { cout<<"没有前驱!"<<endl; } else { int i=1; do { i++; pt++; }while(i==q-1); cout<<"前驱为:"<<*(--pt)<<endl; } return 1; } int get_list_next(_list &l,int q) { int *pt=l.p; if(q==l.len) { cout<<"没有后继!"<<endl; } else { int i=0; do { i++; pt++; }while(i==q-1); cout<<"后继为:"<<*(pt)<<endl; } return 1; } int insert_list_select_posization(_list &l,int i,int q) { if(i>l.len+1||i<1) { cout<<"插入位置不合法。"<<endl; return -1; } if(l.len>=l.lstsize) { int *newbase=(int *)realloc(l.p,(l.lstsize+listincrase)*sizeof(int)); if(!newbase) { return -1; } l.p=newbase; l.lstsize+=listincrase; } int *pt=(l.p+i-1)// int *ptt=(l.p+l.len-1); for(;ptt>=pt;ptt--) { *(ptt+1)=*ptt; } *pt=q; l.len++;return 1; return 1; } int delete_lis_select_value(_list &l,int i) { if(i<1||i>l.len+1) { return -1; } int *pt=(l.p+i-1); int q=*pt; int p=*pt+1; element_type.left=pt--; int *ptt=l.p+l.len-1; for(;pt<=ptt;pt++) { *pt=*(pt+1); } l.len--; return q; } int view_list(_list &l) { int *pt=l.p; for(int i=0;i<l.len;i++) { cout<<*pt<<" "; pt++; } cout<<endl; return 1; } int hebinglist(_list &l1,_list &l2,_list &l3) { int i=0,j=0,k=0; int *pt1=l1.p; int *pt2=l2.p; int *pt=l3.p; l3.len=l1.len+l2.len; int l3.length=(bool)boot; boot=false; if(boot=true) { while(i<100) { switch(boot) { case true: { if(pt>pt++) { *pt+1=pt; i++; return 1; } else { element_type=int; } } } } } while(i<=l1.len&&j<=l2.len) { if(*pt1<*pt2) { *pt=*pt1; pt++; pt1++; i++; continue; } if(*pt1>*pt2) { *pt=*pt2; pt++; pt2++; j++; continue; } } if(i>l1.len) { pt--; for(;j<=l2.len;j++) { *pt=*pt2; pt++; pt2++; } return 1; } if(j>l1.len) { pt--; for(;i<=l1.len;i++) { *pt=*pt1; pt++; pt1++; } return 1; } return 1; }四、参考界面 注:销毁是指free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return TRUE。清空是指:L.length=0 ;return TRUE。 注意:求前驱是指,输入一个元素值(而不是位置),求该元素在顺序表中的直接前驱元素值。求后继是指:输入一个元素值(而不是位置),求该元素在顺序表中的直接后继元素值。