顺序表的基本操作.doc

顺序表的基本操作
/*sqList.h 文件*/
#define LIST_INIT_SIZE 50 /*初始分配的顺序表长度*/
#define INCREM 10 /*溢出时，顺序表长度的增量*/
#define OVERFLOW 1
#define OK 0
#define ERROR -1

typedef int ElemType; /*定义表元素的类型*/
typedef struct SqList{
ElemType *elem; /*存储空间的基地址*/
int length; /*顺序表的当前长度*/
int listsize; /*当前分配的存储空间*/
}SqList;

/*sqListOp.h 文件*/
#include "Sqlist.h"

int InitList_sq(SqList &L); //顺序表创建函数定义

void FreeList_sq(SqList &L); //顺序表销毁函数定义

int ListInsert_sq(SqList &L, int i, ElemType e); //在顺序表的位置i插入元素e

void PrintList_sq(SqList &L); //遍历并输出顺序表所有元素

int ListDelete_sq(SqList &L, int i,ElemType &e); //删除顺序表第i个元素的

bool ListEmpty(SqList &L); //判断顺序表是否为空

int 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 <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include "sqlistOp.h"

//创建顺序表
int InitList_sq(SqList &L) {
L.elem = (ElemType*)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(SqList &L, int i, ElemType e){
int k;
if (i<1 || i>L.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--){ /*插入位置之后元素后移*/
L.elem[k + 1] = L.elem[k];
}
L.elem[i - 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]元素= [%d]\n", i, L.elem[i]);
}

//删除顺序表第i个位置的元素
int ListDelete_sq(SqList &L, int i,ElemType &e){
int k;
if (i<1 || i>L.length) return ERROR; /*删除位置不合法*/
e = L.elem[i-1];
for (k = i - 1; k<L.length - 1; k++) /*元素前移*/
L.elem[k] = L.elem[k + 1];
L.length--; /*顺序表长度减1*/
return OK;
}

//在顺序表里查找出第1个与e相等的数据元素位置
int LocateElem_sq(SqList L,ElemType e){
int i = 0;
while(i<=L.length){
if(L.elem[i] == e)
break;
else
i++;
}
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; //书上合并的算法采用指针方式，这里采用简单点的方法
int k =0; //i指向La的当前位置，j指向Lb当前位置，k指向Lc当前位置
while(i<La.length && j<Lb.length){ //归并
if(La.elem[i]<Lb.elem[j]){
Lc.elem[k] = La.elem[i];
i++;
}
else{
Lc.elem[k] = Lb.elem[j];
j++;
}
k++;
}
while(i<La.length) Lc.elem[k++] = La.elem[i++];
while(j<La.length) Lc.elem[k++] = Lb.elem[j++];

}//MergeList_sq

bool ListEmpty(SqList &L){ //判断顺序表是否为空
if(L.length > 0)
return 1;
else
return 0;
}

/* main.cpp 文件*/
#include <stdio.h>
#include <malloc.h>

#include "sqlistOp.h"

void main(){

SqList L;
printf("准备创建顺序表\n");
if (OK != InitList_sq(L)){
printf("顺序表创建出错\n");
}
if(ListEmpty(L))
printf("表不为空\n");
else
printf("表为空\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;
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");
else
printf("元素在顺序表的位置 = %d\n",i);

printf("创建另一个顺序表\n");
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);
FreeList_sq(Lb);
FreeList_sq(Lc);
getchar();
}

// 单链表的操作
/*linkList.h 文件*/
#define INIT_SIZE 50 /*初始分配的顺序表长度*/
#define INCREM 10 /*溢出时，顺序表长度的增量*/

enum Status {
OK,
ERROR
};

typedef int ElemType; /*定义表元素的类型*/

typedef struct LNode{
ElemType data; /*结点的数据域*/
struct LNode *next; /*结点的指针域*/
}LNode, *LinkList;

/*linkListOp.h 文件*/
#include "linkList.h"

LinkList InitList_L(); //创建单链表头结点

void CreateList_L(LinkList &L,int n); //创建单链表头结点和n个元素结点

Status ListInsert_L(LinkList &L, int i, ElemType e); //在单链表的第i个位置之前插入新元素x

void 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个与e相等的数据元素位置

void ListConvert_L(LinkList &L); //单链表翻转

void FreeList_L(LinkList L); //销毁单链表

/*linkListOp.cpp文件 */
#include <malloc.h>
#include <stdio.h>
#include "linklistOp.h"

//初始化线性单表，即创建一个头结点
LinkList InitList_L() {
LinkList H = (LinkList)malloc(sizeof(LNode)); /*申请一个头结点*/
if (!H) return NULL; /*申请失败*/
H->next = NULL; /*头结点的指针域置空*/
return H;
}

//创建n个结点的单链表，包括所有链表节点
void CreateList_L(LinkList &L,int n){
//逆位序输入n个元素的值，建立带表头结点的单链表L
L = (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相等的数据元素位置
int LocateElem_L(LinkList L,ElemType e){
int i = 1;
LinkList p = L->next;
while(p){
if(p->data == e)
break;
else{
p = 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 p = L;
int j = 0;
while(p && j<i-1){ //寻找第i-1个结点
p = p->next;
++j;
}
if(!p || j>i) 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]元素= [%d]\n", 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 && j<i){
p = p->next;
++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 && j<i-1){ //寻找第i个结点，并令p指向其前驱
p = p->next;
++j;
}
if(!p->next || j>i-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 <stdio.h>
#include <malloc.h>

#include "linklistOp.h"

void main(){

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("删除的元素值 = %d\n",e);
getchar();

printf("获取第10个元素\n");
GetElem_L(L,10,e);
printf("获取到的元素值e = %d\n",e);
getchar();

printf("查找数据元素14在单链表的位置\n");
int idx = LocateElem_L(L,14);
printf("14在单链表的位置 = %d\n",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 INCREMENT 10

//typedef int ElemType;
typedef char ElemType;
typedef struct SqStack {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;

enum Status{
OK,
ERROR,
OVERFLOW
};

/*sqStackOp.h文件 */
#include "sqStack.h"

Status InitStack(SqStack &S) ;
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
bool StackEmpty(SqStack &S);

/*sqStackOp.cpp文件 */
#include <malloc.h>
#include <stdlib.h>
#include "sqStackOp.h"

Status InitStack(SqStack &S) {
//构造一个空的栈
S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(! S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base;
S.stacksize=INIT_SIZE;
return OK;
} //InitStack

Status 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 *)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;
} //Push

Status 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;
else
return false;

}

/*main.cpp文件 */
#include <stdio.h>
#include <stdlib.h>
#include "sqStackOp.h"

void main()
{
printf("Hellow stack \n");
SqStack S; //定义顺序栈S

if(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("出栈元素 = %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 INCREMENT 10

typedef int ElemType;
typedef struct SqStack {
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;

enum Status{
OK,
ERROR,
OVERFLOW
};

/*sqStackOp.h文件 */
#include "sqStack.h"

Status InitStack(SqStack &S) ;
Status GetTop(SqStack S,ElemType &e);
Status Push(SqStack &S,ElemType e);
Status Pop(SqStack &S,ElemType &e);
bool StackEmpty(SqStack &S);

/*sqStackOp.cpp文件 */
#include <malloc.h>
#include <stdlib.h>
#include "sqStackOp.h"

Status InitStack(SqStack &S) {
//构造一个空的栈
S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(! S.base) exit(OVERFLOW); //存储分配失败
S.top=S.base;
S.stacksize=INIT_SIZE;
return OK;
} //InitStack

Status 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 *)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;
} //Push

Status 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;
else
return false;

}

/*main.cpp文件 */
#include <stdio.h>
#include <stdlib.h>
#include "sqStackOp.h"

void 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");
getchar();
}

实验内容（3）参考程序
/*sqQueue.h 文件*/
#define MAXQSIZE 100
typedef int QElemType;

typedef struct SqQueue {
QElemType *base;
int front;
int rear;
}SqQueue;

enum Status{
OK,
ERROR,
OVERFLOW
};

/*sqQueueOp.h 文件*/
#include "sqQueue.h"

Status InitQueue (SqQueue &Q) ;
Status EnQueue (SqQueue &Q, QElemType e);
Status DeQueue (SqQueue &Q, QElemType &e) ;
bool QueueEmpty(SqQueue &Q);
int QueueLength(SqQueue Q);

/*sqQueueOp.cpp 文件*/
#include <malloc.h>
#include <stdlib.h>
#include "sqQueueOp.h"

Status InitQueue (SqQueue &Q) {
// 构造一个空队列Q
Q.base = (QElemType *) malloc
(MAXQSIZE *sizeof (QElemType));
if (!Q.base) exit (OVERFLOW);
// 存储分配失败
Q.front = Q.rear = 0;
return OK;
}

Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素
if ((Q.rear+1) % MAXQSIZE == Q.front)
return ERROR; //队列满
Q.base[Q.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) return ERROR;
e = Q.base[Q.front];
Q.front = (Q.front+1) % MAXQSIZE;
return OK;
}

//判断队列是否为空
bool QueueEmpty(SqQueue &Q){
if(Q.front== Q.rear)
return true;
else
return false;
}

//计算循环队列长度
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

/*main.cpp 文件*/
#include <stdio.h>
#include <stdlib.h>
#include "sqQueueOp.h"

void main()
{
printf("Hello Queue \n");
SqQueue Q; //定义顺序队列Q
QElemType 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出队，当前队列长度=%d\n",e,QueueLength(Q));

EnQueue(Q,9);
EnQueue(Q,11);

while(!QueueEmpty(Q)){
DeQueue(Q,e);
prin