分销赏收藏举报申诉 / 56

立即下载开通VIP

当前位置：首页 > 包罗万象 > 大杂烩 > 顺序表的基本操作.doc

顺序表的基本操作.doc

上传人：人****来

文档编号：3061656

上传时间：2024-06-14

格式：DOC

页数：56

大小：90KB

《顺序表的基本操作.doc》由会员分享，可在线阅读，更多相关《顺序表的基本操作.doc（56页珍藏版）》请在咨信网上搜索。

1、顺序表的基本操作/*sqList.h 文件*/#define LIST_INIT_SIZE 50 /*初始分配的顺序表长度*/#define INCREM 10 /*溢出时，顺序表长度的增量*/#define OVERFLOW 1#define OK 0#define ERROR -1typedef int ElemType; /*定义表元素的类型*/typedef struct SqListElemType *elem; /*存储空间的基地址*/int length; /*顺序表的当前长度*/int listsize; /*当前分配的存储空间*/SqList;/*sqListOp.h 文件*

2、/#include Sqlist.hint InitList_sq(SqList &L); /顺序表创建函数定义void FreeList_sq(SqList &L); /顺序表销毁函数定义int ListInsert_sq(SqList &L, int i, ElemType e); /在顺序表的位置i插入元素evoid PrintList_sq(SqList &L); /遍历并输出顺序表所有元素int ListDelete_sq(SqList &L, int i,ElemType &e); /删除顺序表第i个元素的bool ListEmpty(SqList &L); /判断顺序表是否为空i

3、nt LocateElem_sq(SqList L,ElemType e); /在顺序表里查找出第1个与e相等的数据元素位置/已知线性表La和Lb的元素按值非递减排列/归并后的La和Lb得到新的顺序线性表Lc，Lc的元素也是按值非递减排列void MergeList_sq(SqList La,SqList Lb, SqList &Lc);/*sqListOp.cpp文件*/#include #include #include #include sqlistOp.h/创建顺序表int InitList_sq(SqList &L) L.elem = (ElemType*)malloc(LIST_I

4、NIT_SIZE*sizeof(ElemType);if (!L.elem) exit(OVERFLOW); /*初始化失败，返回0*/L.length = 0; /*置空表长度为0*/L.listsize = LIST_INIT_SIZE; /*置初始空间容量*/return OK; /*初始化成功，返回1*/*InitList*/销毁顺序表void FreeList_sq(SqList &L)if (L.elem)free(L.elem);printf(完成链表内存销毁n);/在顺序表的第i个位置之前插入新元素int ListInsert_sq(SqList &L, int i, Elem

5、Type e)int k;if (iL.length + 1) return ERROR; /*插入位置不合法*/if (L.length = L.listsize) /*存储空间满，重新分配空间*/L.elem = (ElemType*)realloc(L.elem, (LIST_INIT_SIZE + INCREM)*sizeof(ElemType);if (!L.elem) return OVERFLOW; /*存储分配失败*/L.listsize += INCREM; /*修改存储空间大小*/for (k = L.length - 1; k = i - 1; k-) /*插入位置之后元

6、素后移*/L.elemk + 1 = L.elemk;L.elemi - 1 = e; /*插入元素*/L.length+; /*顺序表长度加1*/return OK;/*ListInsert*/遍历并输出顺序表所有元素void PrintList_sq(SqList &L)if (!L.elem)return;int i = 0;for (i = 0; i L.length; i+)printf(第%d元素= %dn, i, L.elemi);/删除顺序表第i个位置的元素int ListDelete_sq(SqList &L, int i,ElemType &e)int k;if (iL.l

7、ength) return ERROR; /*删除位置不合法*/e = L.elemi-1;for (k = i - 1; kL.length - 1; k+) /*元素前移*/L.elemk = L.elemk + 1;L.length-; /*顺序表长度减1*/return OK;/在顺序表里查找出第1个与e相等的数据元素位置int LocateElem_sq(SqList L,ElemType e)int i = 0;while(i=L.length)if(L.elemi = e) break;elsei+;if(i=L.length) return i;return -1;/已知线性表

8、La和Lb的元素按值非递减排列/归并后的La和Lb得到新的顺序线性表Lc，Lc的元素也是按值非递减排列void MergeList_sq(SqList La,SqList Lb, SqList &Lc)ElemType *pa = La.elem;ElemType *pb = Lb.elem;Lc.listsize = Lc.length = La.length + Lb.length;if(!Lc.elem) exit(OVERFLOW); /存储分配失败int i = 0,j = 0; /书上合并的算法采用指针方式，这里采用简单点的方法int k =0; /i指向La的当前位置，j指向Lb

9、当前位置，k指向Lc当前位置while(iLa.length & jLb.length) /归并if(La.elemiLb.elemj) Lc.elemk = La.elemi;i+;elseLc.elemk = Lb.elemj;j+;k+;while(iLa.length) Lc.elemk+ = La.elemi+;while(j 0)return 1;elsereturn 0;/* main.cpp 文件*/#include #include #include sqlistOp.hvoid main()SqList L;printf(准备创建顺序表n);if (OK != InitLi

10、st_sq(L)printf(顺序表创建出错n);if(ListEmpty(L)printf(表不为空n);elseprintf(表为空n);int i = 0;for (i = 1; i = 20; i+)ListInsert_sq(L, i, 2 * i);printf(准备遍历并输出顺序表n);PrintList_sq(L);getchar();printf(在第10个位置插入值为99的元素后再遍历输出顺序表n);ListInsert_sq(L, 10, 99);PrintList_sq(L);getchar();printf(删除第10个元素后再遍历输出顺序表n);ElemType e

11、;ListDelete_sq(L,10,e);PrintList_sq(L);printf(删除的数据元素值 = %d n,e);getchar();printf(查找出一个数据元素的在顺序表中的位置n);i = LocateElem_sq(L,20);if(-1 = i)printf(顺序表不包含这个数据元素n);elseprintf(元素在顺序表的位置 = %dn,i);printf(创建另一个顺序表n);SqList Lb;if (OK != InitList_sq(Lb)printf(顺序表创建出错n);for (i = 1; i = 10; i+)ListInsert_sq(Lb,

12、i, 2 * i-1);printf(准备遍历并输出顺序表n);PrintList_sq(Lb);SqList Lc;if (OK != InitList_sq(Lc)printf(顺序表创建出错n);printf(将两个顺序表合并打印合并后的顺序表n);MergeList_sq(L, Lb, Lc);PrintList_sq(Lc);printf(准备销毁顺序表n);FreeList_sq(L);FreeList_sq(Lb);FreeList_sq(Lc);getchar();/ 单链表的操作/*linkList.h 文件*/#define INIT_SIZE 50 /*初始分配的顺序表长

13、度*/#define INCREM 10 /*溢出时，顺序表长度的增量*/enum Status OK,ERROR;typedef int ElemType; /*定义表元素的类型*/typedef struct LNodeElemType data; /*结点的数据域*/struct LNode *next; /*结点的指针域*/LNode, *LinkList;/*linkListOp.h 文件*/#include linkList.hLinkList InitList_L(); /创建单链表头结点void CreateList_L(LinkList &L,int n); /创建单链表头结

14、点和n个元素结点Status ListInsert_L(LinkList &L, int i, ElemType e); /在单链表的第i个位置之前插入新元素xvoid PrintList_L(LinkList L); /遍历并输出单链表所有元素Status ListDelete_L(LinkList &L, int i, ElemType &e);/删除单链表第i个位置的元素Status GetElem_L(LinkList L,int i,ElemType &e);/获取单链表第i个位置的元素int LocateElem_L(LinkList L,ElemType e); /查找出第1个与

15、e相等的数据元素位置void ListConvert_L(LinkList &L); /单链表翻转void FreeList_L(LinkList L); /销毁单链表/*linkListOp.cpp文件 */#include #include #include linklistOp.h/初始化线性单表，即创建一个头结点LinkList InitList_L() LinkList H = (LinkList)malloc(sizeof(LNode); /*申请一个头结点*/if (!H) return NULL; /*申请失败*/H-next = NULL; /*头结点的指针域置空*/retu

16、rn H;/创建n个结点的单链表，包括所有链表节点void CreateList_L(LinkList &L,int n)/逆位序输入n个元素的值，建立带表头结点的单链表LL = (LinkList)malloc(sizeof(LNode);L-next = NULL; /建立一个带头结点的单链表for(int i= n; i 0; i-)LinkList p = (LinkList)malloc(sizeof(LNode); /生成新结点p-data = 2*i; /输入元素值p-next = L-next; /插入到表头L-next = p;/在顺序表里查找出第1个与e相等的数据元素位置i

17、nt LocateElem_L(LinkList L,ElemType e)int i = 1;LinkList p = L-next;while(p)if(p-data = e) break;elsep = p-next;i+;if(p) return i;return 0;/销毁单链表表void FreeList_L(LinkList L)LinkList p = L;while (p)L = L-next;free(p);p = L;/在单链表的第i个位置之前插入新元素Status ListInsert_L(LinkList &L, int i, ElemType e)LinkList

18、p = L; int j = 0;while(p & jnext;+j;if(!p | ji) return ERROR;LinkList s = (LinkList)malloc(sizeof(LNode);s-data = e;s-next = p-next;p-next = s;return OK;/遍历并输出单链表所有元素void PrintList_L(LinkList L)int i = 0;LinkList p = L-next;while (p)printf(第%d元素= %dn, i+, p-data);p = p-next;/获取单链表第i个位置的元素Status GetE

19、lem_L(LinkList L,int i,ElemType &e)/L为带头结点的单链表的头指针/当第i个元素存在，其值赋给e并返回OK，否则饭否ERRORLinkList p = L-next;int j = 1;while(p & jnext;+j;if(!p) return ERROR;/第i个元素不存在e = p-data;return OK;/删除单链表第i个位置的元素,并由e返回其值Status ListDelete_L(LinkList &L, int i, ElemType &e)LinkList p = L; int j = 0;while(p-next & jnext;

20、+j;if(!p-next | ji-1) return ERROR; /删除位置不合理LinkList q = p-next;p-next = q-next;e = q-data;free(q);return OK;/单链表翻转，不增加额外的存储空间void ListConvert_L(LinkList &L)LinkList p,q;p=L-next;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;/*main.cpp文件 */#include #include #include linklistOp.hvoid main()

21、printf(准备创建单链表n);LinkList L;CreateList_L(L,20);printf(准备遍历并输出单链表n);PrintList_L(L);getchar();printf(在第10个位置插入值为99的元素后再遍历输出单链表n);ListInsert_L(L, 10, 99);PrintList_L(L);getchar();printf(删除第10个元素后再遍历输出单链表n);ElemType e;ListDelete_L(L,10,e);PrintList_L(L);printf(删除的元素值 = %dn,e);getchar();printf(获取第10个元素n)

22、;GetElem_L(L,10,e);printf(获取到的元素值e = %dn,e);getchar();printf(查找数据元素14在单链表的位置n);int idx = LocateElem_L(L,14);printf(14在单链表的位置 = %dn,idx);getchar();printf(单链表翻转操作n);ListConvert_L(L);PrintList_L(L);getchar();printf(单链表翻转操作n);ListConvert_L(L);PrintList_L(L);getchar();printf(准备销毁单链表n);FreeList_L(L);getch

23、ar();/*sqStack.h文件 */#define INIT_SIZE 100#define INCREMENT 10/typedef int ElemType;typedef char ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件 */#include sqStack.hStatus InitStack(SqStack &S) ;Status GetTop(SqStack S,E

24、lemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S); /*sqStackOp.cpp文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /构造一个空的栈 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW); /存储分配失败 S.t

25、op=S.base; S.stacksize=INIT_SIZE; return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTop Status Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(ElemType *)real

26、loc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType); if(!S.base)exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e; return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); return OK; /Push/判

27、断栈是否为空bool StackEmpty(SqStack &S)if(S.top = S.base) return true;elsereturn false;/*main.cpp文件 */#include #include #include sqStackOp.hvoid main()printf(Hellow stack n);SqStack S; /定义顺序栈Sif(OK != InitStack(S) printf(顺序栈初始化出错，退出.n);exit(-1);Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);printf(出栈元素 =

28、%d n,e);Push(S,4);Push(S,5);while(!StackEmpty(S)Pop(S, e);printf(出栈元素 = %d n,e);/*SqStack S; char x,y; InitStack(S); x=c;y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); Pop(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y);printf(%c ,y); ; printf(%c ,x);*/getchar();实验内容（2）参考程序/*sq

29、Stack.h文件 */#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件 */#include sqStack.hStatus InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack

30、&S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件 */#include #include #include sqStackOp.hStatus InitStack(SqStack &S) /构造一个空的栈 S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(! S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base; S.stacksize=INIT_SIZE;

31、 return OK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTopStatus Push(SqStack &S,ElemType e)/插入元素e为新的栈顶元素 if(S.top-S.base=S.stacksize) /栈满，追加存储空间 S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)

32、*sizeof(ElemType); if(!S.base)exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=INCREMENT; *S.top+=e; return OK; /PushStatus Pop(SqStack &S,ElemType &e)/若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top=S.base) return ERROR; e=*(-S.top); return OK; /Push/判断栈是否为空bool StackEmpty(SqStack &S)i

33、f(S.top = S.base) return true;elsereturn false;/*main.cpp文件 */#include #include #include sqStackOp.hvoid main()SqStack s;int x;InitStack(s);scanf(%d,&x); /%d-十进制输入；%O-八进制输入； %x-十六进制输入/修改这里输入进制和下面整除和余数计算，就可以获得其他进制的转换while(x!=0)Push(s,x%8); x=x/8; while(!StackEmpty(s) Pop(s,x); printf(%d ,x); printf(n

34、);getchar();实验内容（3）参考程序/*sqQueue.h 文件*/#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue QElemType *base;int front;int rear;SqQueue;enum StatusOK,ERROR,OVERFLOW;/*sqQueueOp.h 文件*/#include sqQueue.hStatus InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (

35、SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件*/#include #include #include sqQueueOp.h Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear =

36、 0; return OK; Status EnQueue (SqQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) re

37、turn ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;/判断队列是否为空bool QueueEmpty(SqQueue &Q)if(Q.front= Q.rear) return true;elsereturn false;/计算循环队列长度int QueueLength(SqQueue Q)return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;/*main.cpp 文件*/#include #include #include sqQueueOp.hvoid

38、 main()printf(Hello Queue n);SqQueue Q; /定义顺序队列QQElemType e;if(OK != InitQueue(Q) printf(顺序队列初始化出错，退出.n);exit(-1);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);printf(当前队列长度 = %d n,QueueLength(Q);DeQueue(Q,e);printf(队首元素%d出队，当前队列长度=%dn,e,QueueLength(Q);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)DeQueue(Q,e);prin

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档保存到电脑，查找使用更方便

12 金币 0人已下载

申诉本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请申请举报、认领或删除 立即下载

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 顺序基本操作

咨信网温馨提示：
1、咨信平台为文档C2C交易模式，即用户上传的文档直接被用户下载，收益归上传人（含作者）所有；本站仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿，我们不确定上传用户享有完全著作权，根据《信息网络传播权保护条例》，如果侵犯了您的版权、权益或隐私，请联系我们，核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确)，网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据，个别因单元格分列造成显示页码不一将协商解决，平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺，下载前须认真查看，确认无误后再购买，务必慎重购买；若有违法违纪将进行移交司法处理，若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传，付费前请自行鉴别，如您付费，意味着您已接受本站规则且自行承担风险，本站不进行额外附加服务，虚拟产品一经售出概不退款（未进行购买下载可退充值款），文档一经付费（服务费）、不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印，是因预览和防盗链等技术需要对页面进行转换压缩成图而已，我们并不对上传的文档进行任何编辑或修改，文档下载后都不会有水印标识（原文档上传前个别存留的除外），下载后原文更清晰；试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓；PPT和DOC文档可被视为“模板”，允许上传人保留章节、目录结构的情况下删减部份的内容；PDF文档不管是原文档转换或图片扫描而得，本站不作要求视为允许，下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用；网站提供的党政主题相关内容(国旗、国徽、党徽－－等)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
6、文档遇到问题，请及时私信或留言给本站上传会员【人****来】，需本站解决可联系【微信客服】、【 QQ客服】，若有其他问题请点击或扫码反馈【服务填表】；文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“【版权申诉】”（推荐），意见反馈和侵权处理邮箱：1219186828@qq.com；也可以拔打客服电话：4008-655-100；投诉/维权电话：4009-655-100。

关于本文

本文标题：顺序表的基本操作.doc
链接地址：https://www.zixin.com.cn/doc/3061656.html

人****来

内容提供者

实名认证

查看上传人更多文档

部分上传会员的收益排行 01、路***（￥15400+），
02、曲****（￥15300+），
03、wei****016（￥13200+）,
04、大***流（￥12600+），
05、Fis****915（￥4200+），
06、h****i（￥4100+），
07、Q**（￥3400+），
08、自******点（￥2400+），
09、h*****x（￥1400+），
10、c****e（￥1100+）,
11、be*****ha（￥800+），
12、13********8（￥800+）。

相似文档

自信AI助手