《数据结构（C语言版）》严蔚敏代码实现———顺序表
一、前言
最近在重新学习数据结构啦，网上说这本书挺不错哒，于是我开始啃这本书咯…有一说一，严奶奶的书挺好的，就是有点大量使用指针。。。需要沉下心来，看一看画一画才能懂，我自己手敲了一遍书上代码，加上了自己的理解，希望大家也能更清楚的看明白~
好啦废话不多说，下面就上代码！💁
二、代码
严奶奶的书中预定义了一些预定义常量和类型，大家可以新建一个y.h文件粘贴以下内容，然后再去复制代码哦。
y.h文件内容：
/*** 严奶奶书中的预定义常量和类型**///函数结果状态代码#define TRUE 1//成功#define FALSE 0 //失败#define OK 1 //成功#define ERROR 0 //错误#define INFEASIBLE -1 //不可实行#define OVERFLOW -2//溢出//Status 是函数的类型，其值是函数结果状态代码typedef int Status;
顺序表SqList.cpp:
#include "y.h"#include <iostream>#include <cstdlib>#include <cstdio>using namespace std;typedef int ElemType;/*** 严奶奶顺序表的实现* by 熊子q .1.28**/#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量//强悍如斯的严奶奶，强悍如斯的顺序表typedef struct {ElemType *elem;//存储空间基址int length; //当前长度int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//顺序表初始化Status InitList_Sq(SqList &L){//构造一个空的线性表L，动态分配空间L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);//存储空间分配失败L.length = 0; //空表长度为0L.listsize = LIST_INIT_SIZE; //初始存储容量return OK;}//销毁线性表,基本操作，书上没有，自己写的void DestoryList_Sq(SqList &L){free(L.elem);//释放后的无效指针必须置为空，不然会导致内存泄漏L.elem = NULL;L.length=0;L.listsize=0;}//清空线性表,基本操作，书上没有，自己写的void ClearList_Sq(SqList &L){L.length = 0;}//判断线性表是否为空,基本操作，书上没有，自己写的Status ListEmpty_Sq(SqList L){if(L.length == 0) return TRUE;else return FALSE;}//获取顺序表的长度,基本操作，书上没有，自己写的int ListLength_Sq(SqList L){return L.length;}//获取元素,基本操作，书上没有，自己写的Status GetElem_Sq(SqList L, int i, ElemType &e){//获取顺序表L中第i个位置的元素e//i的合法值为1<=i<=ListLength_Sq(L)if(i<1 || i>ListLength_Sq(L)) return ERROR;e = L.elem[i-1];return OK;}//获取前驱元素,基本操作，书上没有，自己写的Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e){//获取顺序表L中元素值为cur_e的前驱元素next_e//成功返回OK，pre_e为前驱，失败返回FALSE，pre_e为随机值//双指针p,pre操作；p为遍历元素的指针，pre指针永远指向p指针的前一个地址，即pre_eElemType *pre;for(ElemType *p = L.elem;p<=&(L.elem[L.length-1]);p++){if(*p == cur_e){pre_e = *pre;return OK;}pre=p;}return FALSE;}//获取后继元素,基本操作，书上没有，自己写的Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e){//获取顺序表L中元素值为cur_e的后继元素next_e//成功返回OK，next_e为后继，失败返回FALSE，next_e为随机值//双指针p,nxt操作；p为遍历元素的指针，nxt指针永远指向p指针的后一个地址，即next_eElemType *nxt = L.elem+1;for(ElemType *p = L.elem;p<&(L.elem[L.length-1]);p++,nxt++){if(*p == cur_e){next_e = *nxt;return OK;}}return FALSE;}//顺序表插入，时间复杂度为O(n)Status ListInsert_Sq(SqList &L, int i, ElemType e){//在顺序表L中第i个位置之前插入新的元素e//i的合法值为1<=i<=ListLength_Sq(L)+1if(i<1||i>ListLength_Sq(L)+1) return ERROR;//i值不合法if(L.length >= L.listsize){//当前存储空间已满，增加分配ElemType *newbase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(OVERFLOW);//存储分配失败L.elem = newbase; //新基址L.listsize += LISTINCREMENT;//增加存储容量}ElemType *q = &(L.elem[i-1]); //q为插入位置//插入位置及之后的元素右移for(ElemType *p = &(L.elem[L.length-1]);p>=q;--p)*(p+1) = *p;*q = e; //插入e++L.length; //表长增1return OK;}//顺序表删除，时间复杂度为O(n)Status ListDelete_Sq(SqList &L, int i, ElemType &e){//在顺序表L中删除第i个元素，并用e返回其值//i的合法值为1<=i<=ListLength_Sq(L)if(i<1 || i>ListLength_Sq(L)) return ERROR; //i值不合法ElemType *p = &(L.elem[i-1]); //p为被删除元素的位置e = *p; //被删除元素的值赋给eElemType *q = L.elem + L.length - 1; //表尾元素的位置for(++p;p<=q;++p) *(p-1) = *p;//被删除元素之后的元素左移--L.length;return OK;}//顺序表的查找int LocateElem_Sq(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)){//在顺序表L中查找第1个值与e满足compare()的元素的位序//若找到，则返回其在L中的位序，否则返回0//第三个参数是一个函数指针，该函数的必须符合以下2点要求：//1.返回值为Status。2.有两个参数，且类型为ElemTypeint i = 1; //位序i的初值为1ElemType *p = L.elem; //p的初值为第一个元素的存储位置//遍历顺序表while(i <= L.length && !(*compare)(*p++ ,e)) ++i;if(i <= L.length) return i;else return 0;}//顺序表的合并，时间复杂度为O(La.length+Lb.length)void MergeList_Sq(SqList La, SqList Lb, SqList &Lc){//已知顺序表La和Lb的元素按值非递减排列（递增排列）//归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列（递增排列）//pa和pb指针是遍历La和Lb每一个元素的指针，pc指针永远指向Lc的待插入元素位置ElemType *pa = La.elem,*pb = Lb.elem;Lc.listsize = Lc.length = La.length + Lb.length;ElemType *pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem) exit(OVERFLOW);//存储分配失败//pa_last和pb_last指针是指向La和Lb最后一个元素的指针，pa<=pa_last即遍历La中每一个元素，Lb同理ElemType* pa_last = La.elem + La.length - 1;ElemType* pb_last = Lb.elem + Lb.length - 1;while(pa <= pa_last && pb <= pb_last){//归并/*** 判断pa和pb所指向的元素谁大，取其中较小的数添加到Lc中，然后两个指针后移 * *pc++ =*pa++;相当于以下三条语句：* *pc = *pa; //将pa所指向的元素值赋值给pc所指向的元素值* pc++;pa++; //pc和pa指针后移**/ if(*pa <= *pb) *pc++ =*pa++;else *pc++ = *pb++;}//以下两个while只会进入一个，因为上个while遍历的结束条件就是La或Lb遍历完毕while(pa <= pa_last) *pc++ = *pa++; //插入La的剩余元素while(pb <= pb_last) *pc++ = *pb++; //插入Lb的剩余元素}//顺序表的输出void Display_Sq(SqList L){printf("马上就输出这个叫L的线性表啦~\n");printf("顺序表的内容：");for(int i=0;i<ListLength_Sq(L);i++){if(i!=0) printf(" ");printf("%d",L.elem[i]);}printf("\n");}Status cmp(ElemType a,ElemType b){if(a>b) return OK;else return FALSE;}int main(){SqList L;InitList_Sq(L); //初始化线性表int a[5] = {4,2,1,3,5};for(int i=0;i<5;i++){//插入元素到线性表LListInsert_Sq(L,i+1,a[i]);}Display_Sq(L); //输出线性表printf("线性表为空？%s\n\n",ListEmpty_Sq(L)==TRUE?"TRUE":"FALSE");//判断线性表是否为空printf("顺序表的长度：%d\n\n",ListLength_Sq(L));//输出线性表长度int tmp; //临时变量，方便下面方法使用GetElem_Sq(L,2,tmp); //获取指定元素printf("第2个元素是：%d\n\n",tmp);PriorElem_Sq(L,5,tmp);//获取前驱printf("5的前驱元素为：%d\n\n",tmp); NextElem_Sq(L,2,tmp); //获取后继printf("2的后继元素为：%d\n\n",tmp);ListDelete_Sq(L,3,tmp); //删除元素printf("删除第3个元素后：\n");Display_Sq(L);tmp = LocateElem_Sq(L,3,cmp); //查找第1个值与e满足cmp的元素的位序printf("\n第一个比3小的元素下标为：%d\n\n",tmp);printf("清空线性表咯~\n"); //清空线性表ClearList_Sq(L);Display_Sq(L);DestoryList_Sq(L); //删除线性表return 0;}
