顺序表的基本操作精品

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); /判断顺序表是否为空in

3、t 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 = (Ele

4、mType*)malloc(LIST_INIT_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(S

5、qList &L, int i, ElemType 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;

6、 k-)/* 插入位置之后元素后移*/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

7、i,ElemType &e)int k;if (iL.length) 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+;-可编辑修改 -_

8、if(i=L.length) return i;return -1;/已知线性表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;/

9、书上合并的算法采用指针方式，这里采用简单点的方法int k =0;/i 指向 La 的当前位置，j 指向 Lb 当前位置， 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 #incl

10、ude sqlistOp.hvoid main()SqList L;printf( 准备创建顺序表n);if (OK != InitList_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

11、_sq(L, 10, 99);PrintList_sq(L);getchar();printf( 删除第 10 个元素后再遍历输出顺序表n);ElemType e;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);

12、SqList Lb;if (OK != InitList_sq(Lb)printf( 顺序表创建出错n);for (i = 1; i = 10; i+)ListInsert_sq(Lb, 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);F

13、reeList_sq(Lb);FreeList_sq(Lc);getchar();-可编辑修改 -_/ 单链表的操作/*linkList.h文件 */#define INIT_SIZE 50/* 初始分配的顺序表长度*/#define INCREM 10/*溢出时，顺序表长度的增量*/enum Status OK,ERROR;typedef int ElemType; /*定义表元素的类型*/typedefstructLNodeElemTypedata;/* 结点的数据域 */structLNode*next;/* 结点的指针域*/LNode, *LinkList;/*linkListOp.h

14、文件 */#include linkList.hLinkList InitList_L();/ 创建单链表头结点void CreateList_L(LinkList &L,int n);/ 创建单链表头结点和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 个位

15、置的元素Status GetElem_L(LinkList L,int i,ElemType &e);/获取单链表第i 个位置的元素int LocateElem_L(LinkList L,ElemType e); /查找出第1 个与 e 相等的数据元素位置void ListConvert_L(LinkList &L); /单链表翻转void FreeList_L(LinkList L);/销毁单链表/*linkListOp.cpp文件*/#include #include #include linklistOp.h/初始化线性单表，即创建一个头结点LinkList InitList_L() L

16、inkList H = (LinkList)malloc(sizeof(LNode);/*申请一个头结点*/if (!H)return NULL;/*申请失败 */H-next = NULL;/*头结点的指针域置空*/return 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 = (

17、LinkList)malloc(sizeof(LNode); /生成新结点p-data = 2*i;/ 输入元素值p-next = L-next;/ 插入到表头L-next = p;-可编辑修改 -_/在顺序表里查找出第1 个与 e 相等的数据元素位置int 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)L

18、inkList p = L;while (p)L = L-next;free(p);p = L;/在单链表的第i 个位置之前插入新元素Status ListInsert_L(LinkList &L, int i, ElemType e)LinkList 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;/遍历并输出单链表所有元

19、素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 GetElem_L(LinkList L,int i,ElemType &e)/L 为带头结点的单链表的头指针/当第 i 个元素存在，其值赋给 e 并返回 OK ，否则饭否 ERROR LinkList p = L-next;int j = 1;while(p & jnext;+j;if(!p) return ERROR;/第

20、 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;+j;if(!p-next | ji-1) return ERROR;/删除位置不合理LinkList q = p-next;p-next = q-next;e = q-data;free(q);return OK;/单链表翻转，不增加额外的存储空间void ListConv

21、ert_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()-可编辑修改 -_printf( 准备创建单链表n);LinkList L;CreateList_L(L,20);printf( 准备遍历并输出单链表n);PrintList_L(L);getchar();printf( 在第 10 个位置插入值为99 的元素后再遍历输出单链表n

22、);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);GetElem_L(L,10,e);printf( 获取到的元素值e = %dn,e);getchar();printf( 查找数据元素14 在单链表的位置n);int idx = LocateElem_L(L,14);printf(

23、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);getchar();/*sqStack.h 文件 */#define INIT_SIZE 100#define INCREMENT10-可编辑修改 -_/typedef int ElemType;typedef ch

24、ar ElemType;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件*/#include sqStack.hStatusInitStack(SqStack&S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);-可编辑修改 -_bool S

25、tackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include #include #include sqStackOp.hStatusInitStack(SqStack&S)/ 构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(! S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;returnOK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用

26、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)*sizeof(ElemType);if(!S.base)exit(OVERFLOW); /存储分配失败S.top=

27、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)if(S.top = S.base)return true;elsereturn false;/*main.c

28、pp文件*/#include #include #include sqStackOp.h-可编辑修改 -_void 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( 出栈元素= %d n,e);Push(S,4);Push(S,5);while(!StackEmpty(S)-可编辑修改 -_Pop(S, e);printf( 出栈元素=

29、 %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 ）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT10-可编辑修改 -_typedef int ElemTy

30、pe;typedef struct SqStack ElemType *base;ElemType *top;int stacksize;SqStack;enum StatusOK,ERROR,OVERFLOW;/*sqStackOp.h文件*/#include sqStack.hStatusInitStack(SqStack&S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack

31、&S);-可编辑修改 -_/*sqStackOp.cpp文件*/#include #include #include sqStackOp.hStatusInitStack(SqStack&S)/ 构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(! S.base)exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;returnOK; /InitStackStatus GetTop(SqStack S,ElemType &e)/若栈不空，则用e 返回 S 的栈

32、顶元素，并返回OK ；否则返回ERRORif(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)*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 ；否则返回ERRORif(S.top=S.base) return ERROR;-可编辑修改 -_e=*(-S.top);return O