要交作业了
Odsqlist.h文件：#define LIST_INIT_SIZE 8 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
#define OVERFLOW -2
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList; // 俗称 顺序表
typedef SqList OdSqList; //有序顺序表
Status InitList(OdSqList&); // 结构初始化
void Destroy(OdSqList&); //销毁有序顺序表
void ClearList(OdSqList&);//清空有序表
Status ListEmpty(OdSqList);//判有序表为空
int ListLength(OdSqList);//求表长
int LocateElem(OdSqList,ElemType); // 查找
void ListInsert(OdSqList&,ElemType); // 插入元素
Status ListDelete(OdSqList&, int,ElemType& ); // 删除元素
int ListDeletem(OdSqList&L, ElemType e); // 删除所有值为e的元素,返回删除的元素个数
int ListDeletemn(OdSqList&, ElemType, ElemType ); // 删除所有值界于mink~maxk的元素，并返回删除的元素个数
void ListTraverse(OdSqList);//遍历非递减有序线性表
odsqlist.cpp文件：
#include<stdio.h>
#include<stdlib.h>
#include "odsqlist.h"
Status InitList( OdSqList& L ){
// 构造一个空的线性表
L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
} // InitList
void ListTraverse(OdSqList L){
//遍历线性表
int i;
printf("listsize is %d.\n",L.listsize);
printf("listlength is %d.\n",L.length);
printf("the list is:(");
for(i=1;i<=L.length;i++)
printf("%d ",L.elem[i-1]);
printf(")\n");
}
int LocateElem(OdSqList L, ElemType e){
// 在顺序表中查询第一个满足判定条件的数据元素，若存在，则返回它的位序，否则返回 0
int i;
i = 1; // i 的初值为第 1 元素的位序
ElemType *p;
p = L.elem; // p 的初值为第 1 元素的存储位置
while (i <= L.length && *p++!=e) ++i;
if (i <= L.length) return i;
else return 0;
}
void ListInsert(OdSqList &L, ElemType e) {
// 在顺序表L中保序插入新的元素e
ElemType *newbase,*p,*q;
if (L.length >= L.listsize) { // 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) exit(OVERFLOW);// 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
q = &(L.elem[0]); // q 指示第1个元素位置
for (p = &(L.elem[L.length-1]);p>=q&&*p>e; --p)
*(p+1) = *p; // 插入位置及之后的元素右移
*(p+1) = e; // 插入e
++L.length; // 表长增1
}
Status ListDelete(OdSqList &L, int i, ElemType &e) {
ElemType *p,*q;
if ((i < 1) || (i > L.length)) return ERROR;// 删除位置不合法
p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p <= q; ++p) *(p-1) = *p;
// 被删除元素之后的元素左移
--L.length; // 表长减1
return OK;
}
void Destroy(OdSqList& L){
//销毁有序顺序表
free(L.elem);
}
void ClearList(OdSqList& L){
//清空有序表
L.length=0;
}
Status ListEmpty(OdSqList L){
//判有序表为空
if(L.length==0)
return TRUE;
else return FALSE;
}
int ListLength(OdSqList L){
//求表长
return L.length;
}
int ListDeletem(OdSqList& L, ElemType e){
// 删除所有值为e的元素,返回删除的元素个数
ElemType *p,*q,*r;
int i=0;//删除的元素个数
p=&L.elem[0];//扫描指针
for(q=&L.elem[L.length-1];*p<e&&p<=q;p++);
if(p<=q&&*p==e){
i++;
for(r=p+1;*r==e&&r<=q;r++,i++);
if(r<=q)
for(;r<=q;r++,p++)
*p=*r;
}
L.length-=i;
return i;
}
int ListDeletemn(OdSqList& L, ElemType mink, ElemType maxk){
// 删除所有值界于mink~maxk的元素，并返回删除的元素个数
ElemType *p,*q,*r,temp;
int i=0;
if(maxk<mink){
temp=maxk;
maxk=mink;
mink=temp;
}
p=&L.elem[0];
for(q=&L.elem[L.length-1];*p<mink&&p<=q;p++);//p指针指向第1个大于等于mink的元素
if(p<=q&&*p<=maxk){//若*p小于等于maxk
i++;
for(r=p+1;*r<=maxk&&r<=q;r++,i++);//r指针指向第1个大于maxk的元素
if(r<=q)
for(;r<=q;r++,p++)
*p=*r;
}
L.length-=i;
return i;
}
app.cpp文件:
#include<stdio.h>
#include<stdlib.h>
#include "odsqlist.h"
void main(){
OdSqList L;
int k;
char i;
ElemType e,mink,maxk;
printf("OdSqList is init……\n");
i=InitList(L);
ListTraverse(L);
while(1){
printf("\n\nplease select:\n");
printf("1------insert\n");
printf("2------traverse\n");
printf("3------deletei\n");
printf("4------deletek\n");
printf("5------deletemink-maxk\n");
printf("6------locate\n");
printf("7------isempty\n");
printf("8------length\n");
printf("9------clearlist\n");
printf("0------quit\n");
scanf("%d",&k);
switch(k){
case 1:
printf("please input e:");
scanf("%d",&e);
ListInsert(L,e);
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 2:
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 3:
while(1){
printf("please input delete i:");
scanf("%d",&i);
if(ListDelete(L,i,e)==ERROR)
printf("delete positon is error!\n");
else {
printf("Deleted elem is %d\n",e);
break;
}
}
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 4:
printf("please input delete e:");
scanf("%d",&e);
ListTraverse(L);
printf("%d elem is deleted.\n",ListDeletem(L,e));
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 5:
printf("please input delete mink and maxk:");
scanf("%d%d",&mink,&maxk);
ListTraverse(L);
printf("%d elem is deleted.\n",ListDeletemn(L,mink,maxk));
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 6:
printf("please input locate e:");
scanf("%d",&e);
i=LocateElem(L,e);
if(i==0)
printf("locate Defaulted!\n");
else
printf("located no. is %d\n",i);
ListTraverse(L);
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 7:
if(ListEmpty(L))
printf("the orderlist is empty!\n");
else
printf("the orderlist is not empty!\n");
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 8:
printf("length is %d.\n",ListLength(L));
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 9:
ClearList(L);
printf("the orderlist is empty!\n");
scanf("%c",&i);
printf("please press any key to continue……");
scanf("%c",&i);
break;
case 0:
Destroy(L);
exit(1);
break;
}
}
}老师要求用单链表实验以上功能，不会搞啊
