• 静态分配

#define MAX 100
 ElemType elem[MAX];  //表
 int n;  //数据元素个数n<MAX

结构体

#define MAX 100
 typedef struct
 {
 ElemType elem[MAX];
 int length;
 }Sqlist;

• 动态存储

#define LIST_INIT_SIZE 100 //存储空间的初始分配量
#define LISTINCREMENT 10  //分配增量
 typedef struct
{
 ElemType *elem;  //存储区域的基址
 int length; //当前表的长度
 int listsize;//当前已分配的存储容量
}Sqlist;//顺序表的类型

• 构造一个空的顺序表L

Status InitList_Sq(SqList &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_Sq  时间复杂度为O(1)

• 销毁顺序表DestroyList_Sq(&L)释放L占用的内存空间

void DestroyList_Sq(SqList &L)
{
 free(L.elem);
 L.elem=NULL;
 L.length=0;
 L.listsize=0;

}

• 在顺序表L的第i个位置（1<=i<=L.length+1）前插入新元素e.

Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
 if(i<1||i>L.length+1) return ERROR;
 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;
 }
 for(int j=L.length;j>=i;j--)
 L.elem[j]=L.elem[j-1]; //元素后移（从最后一个元素开始） （数组下标跟位序不同）
 L.elem[i-1]=e;
 ++L.length;
 return OK;

} //最好时间复杂度O（1）表尾，最坏时间复杂度为O（n）表头,平均是O（n/2）

• 删除数据元素ListDelete_Sq(&L,i,&e),删除顺序表中的第i（1<=i<=L.length）个元素

Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
 if(i<1||i>L.length+1) return ERROR;
 e=L.elem[i-1];
 for( int j=i;j<L.length;j++)
 L.elem[j-1]=L.elem[j];
 --L.length;
 return OK;

}//平均时间复杂度为 O(n-1/2)

• 按位查找:获取表L中第i个位置的元素的值。

#define InitSize 10 //顺序表的初始长度
typedef struct{
 ElemType*data; //指示动态分配数组的指针
 int MaxSize;  //顺序表的最大容量
 int length;  //顺序表的当前长度

}SeqList;

ElemType GetElem(SeqList L,int i)
{
 return L.data[i-1];

} //O(1);

• 按值查找:在表中查找关键字值的元素

#define InitSize 10
typedef struct{
 ElemType*data;
 int MaxSize;
 int length;

}SeqList;

//在顺序表中查找第一个元素值等于e的元素，并返回其位序

int LocateElem(SeqList L,ElemType e)
{
 for(int i=0;i<L.length;i++)
 if(L.data[i]=e)
 return i+1;
 return 0;
} //时间复杂度为O(n+1/2)

• 定义单链表

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

//初始化一个空的单链表(不带头结点)

bool InitList(LinkList &L){
 L=NULL; //空表，暂时还没有任何结点
 return true;
}

//初始化一个的单链表（带头结点）

bool InitList(LinkList &L){
 L=(LNode*)malloc(sizeof(LNode)); //分配一个头结点
 if(L=NULL)
   return false;
 L->next=NULL;
 return true;
}

单链表按位序插入（带头结点）;插入操作。在表L中的第i个位置上插入指定元素e

status ListInsert(LinkList &L,int i,ElemType e)
{
 p=L; int j=0;
 while(j<i-1 && p!=NULL)
{
 j++;
 p=p->next;
}
 if(p==NULL || j>i-1) return ERROR;
 s=(LinkList)malloc(sizeof(LNode));  //创建新结点s
 if (s ==NULL)exit (OVERFLOW);  //存储分配失败
 s->data=e;
 s->next=p->next;  //将s插入到p之后
 p->next=s;
 return OK;
}//ListInter

不带头结点的插入操作

int ListInsert(LinkList &L,int i,ElemType e)
{
 if(i==1)
{
 s=(LinkList)malloc(sizeof(LNode));
 if (s ==NULL)exit (OVERFLOW);
 s->data=e;
 s->next=L;
 L=s; //修改头指针
}
else{ p=L;j=1;  } //与有头结点的类似
return OK;
}

单链表的删除（带头结点）ListDelete(&L,i,&e):删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。

int ListDelete(LinkList &L,int i,ElemType &e)
{
 int j=0; p=L;
 while (j<i-1 && p->next)
{
 j++;
 p=p->next;
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next; //q指向要删除的结点
e=q->data;  //用e将删除元素带回到主调函数中
p->next=q->next; //从单链表中删除q结点
free(q);  //释放q结点
return OK;
}

尾插法建立单链表

LinkList List_Taillnsert(LinkList &L){
 int x;
 L=(LinkList)malloc(sizeof(LNode));
 LNode *s,*r=L;
 scanf("%d",&x);
 while(x!=99999){
 s=(LinkList)malloc(sizeof(LNode));
 s->data=x;
 r->next=s;
 r=s;
 scanf("%d",&x);
}
 r->next=NULL;
 return L;
}

*头插法建立单链表

void CreateList(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带表头结构的单链表线性表L
 int i;
 LinkList p;
 printf("请输入%d个数据："，n);
 for(i=n;i>0;i++){
 p=(LinkList)malloc(sizeof(LNode));
 scanf("%d",&p->data);
 p->next=L->next;
 L->next=p;
 }
}