Question

1、 建立一个顺序存储的线性表，实现线性表的插入、删除操作

Answer 1

// 顺序存储结构线性表基本操作 C语言实现 // // a simple example of Sq_List by C language // // by wangweinoo1[PG] //--------------------------------------------------------- /////////////////////////////////////////////////////////// #include <stdio.h> //以下为函数运行结果状态代码 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间分配增量 typedef int Status; //函数类型，其值为为函数结果状态代码 typedef int ElemType; //假设数据元素为整型 typedef struct { ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList; //实现线性表的顺序存储结构的类型定义 //函数声明开始 Status InitList_Sq(SqList &L); void DestroyList_Sq(SqList &L); void ClearList_Sq(SqList &L); void ListEmpty_Sq(SqList L); Status GetElem_Sq(SqList L,i,&e); int LocateElem_Sq(SqList L,e,compare()); Status PriorElem_Sq(SqList L,cur_e,&pre_e); Status NextElem_Sq(SqList L,cur_e,&next_e); Status ListInsert_Sq(SqList &L,i,e); Status ListDelete_Sq(SqList &L,i,&e); ListTravel_Sq(SqList L,visit()); //函数声明结束 int main(void) { return 0; } //函数定义开始 /////////////////////////////////////// //函数名：InitList_Sq() //参数：SqList *L //初始条件：无 //功能：构造一个空线性表 //返回值：存储分配失败：OVERFLOW // 存储分配成功：OK /////////////////////////////////////// Status InitList_Sq(SqList *L) { L.elem=(ElemType*)malloc((LIST_INIT_SIZE *sizeof(ElemType)); //分配空间 if(!L.elem) exit(OVERFLOW); //若存储分配失败，返回OVERFLOW L.length=0; //空表，长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; } /////////////////////////////////////// //函数名：DestroyList_Sq() //参数：SqList *L //初始条件：线性表L已存在 //功能：销毁线性表 //返回值：无 /////////////////////////////////////// void DestroyList_Sq(SqList *L) { if (L->elem) free(L->elem); //释放线性表占据的所有存储空间 } /////////////////////////////////////// //函数名：ClearList_Sq() //参数：SqList *L //初始条件：线性表L已存在 //功能：清空线性表 //返回值：无 /////////////////////////////////////// void ClearList_Sq(SqList *L) { L->length=0; //将线性表的长度置为0 } /////////////////////////////////////// //函数名：ListEmpty_Sq() //参数：SqList L //初始条件：线性表L已存在 //功能：判断线性表是否为空 //返回值：空：TRUE // 非空：FALSE /////////////////////////////////////// Status ListEmpty_Sq(SqList L) { if (L.length==0) return TRUE; else return FALSE; } /////////////////////////////////////// //函数名：ListLength_Sq() //参数：SqList L //初始条件：线性表L已存在 //功能：返回线性表长度 //返回值：线性表长度(L.length) /////////////////////////////////////// Status ListLength_Sq(SqList L) { return (L.length); } /////////////////////////////////////// //函数名：GetElem_Sq() //参数：SqList L,int i,ElemType *e //初始条件：线性表L已存在，1<=i<=ListLength(L) //功能：用e返回线性表中第i个元素的值 //返回值：(i<1)||(i>ListLength(L))：ERROR // 1<=i<=ListLength(L)：OK /////////////////////////////////////// Status GetElem_Sq(SqList L,int i,ElemType *e) { if (i<1||i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR *e=L.elem[i-1]; //数组中第i-1的单元存储着线性表中第i个数据元素的内容 return OK; } /////////////////////////////////////// //函数名：LocateElem_Sq() //参数：L,e,compare(ElemType1,ElemType2) //初始条件：线性表L已存在，compare()为数据元素判定函数 //功能：返回顺序表L中第1个与e满足关系 compare( ) 的数据元素的位序 //返回值：若在L中存在于e满足关系compare()的元素：其位序 // 若在L中不存在于e满足关系compare()的元素：0 /////////////////////////////////////// int LocateElem_Sq(SqList L,e,compare(ElemType1,ElemType2)) { 　　int i = 1; // i 的初值为第1元素的位序 　　int p = L.elem; // p 的初值为第1元素的存储位置 　　while (i <= L.length && !(*compare)(*p++,e)) 　　　++i; // 依次进行判定 　　if (i <= L.length) return i; // 找到满足判定条件的数据元素为第 i 个元素 　　else return 0; // 该线性表中不存在满足判定的数据元素 } Status PriorElem_Sq(SqList L,cur_e,&pre_e); //见Status NextElem_Sq(SqList L,cur_e,&next_e); Status NextElem_Sq(SqList L,cur_e,&next_e); //我的思路是先用LocateElem_Sq()搜索cur_e的位序， //再看是否大于等于length， //若是，则返回OVERFLOW；否则返回后继 //这样也许有点麻烦？所以希望大家能够补充方案 //by wangweinoo1 /////////////////////////////////////// //函数名：ListInsert_Sq() //参数：SqList *L,int i,ElemType e //初始条件：线性表L已存在，1<=i<=ListLength(L)+1 //功能：在线性表中第i个数据元素之前插入数据元素e //返回值：失败：ERROR // 成功：OK /////////////////////////////////////// Status ListInsert_Sq(SqList *L,int i,ElemType e) { ElemType *j; if (L->length==LIST_MAX_LENGTH) return ERROR; //检查是否有剩余空间 if (i<1||i>L->length+1) return ERROR; //检查i值是否合理 //将线性表第i个元素之后的所有元素向后移动 for (j=L->length-1;j>=i-1;i++) L->elem[j+1]=L->elem[j]; L->elem[i-1]=e; //将新元素的内容放入线性表的第i个位置， L->length++; return OK; } /////////////////////////////////////// //函数名：ListDelete_Sq() //参数：SqList *L,int i,Elemtype *e //初始条件：线性表L已存在，1<=i<=ListLength(L) //功能：将线性表L中第i个数据元素删除 //返回值：失败：ERROR // 成功：OK /////////////////////////////////////// int ListDelete_Sq(SqList *L,int i,Elemtype *e) { if (IsEmpty(L)) return ERROR; //检测线性表是否为空 if (i<1||i>L->length) return ERROR; //检查i值是否合理 *e=L->elem[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中 //将线性表第i+1个元素之后的所有元素向前移动 for (j=i;j<=L->length-1;j++) L->elem[j-1]=L->elem[j]; L->length--; return OK; } //函数定义结束
转自 http://hi.baidu.com/klarkzby/blog/item/4b429655a11ba0173b2935a8.html