1.1 线性表常用函数

InitList(&L):初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定的元素e。
ListDelete(&L,I,&e):删除操作。删除表L中第i个位置的元素，并用e反回删除元素的值。
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值得元素。
GetElem(L,i):按位查找操作。获取表L中第i个位置得元素的值。
Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L):输出操作。按前后顺序输出线性表L中所有元素的值。
Empty(L):判空操作。若L为空表，则返回true,否则返回false。

1.2 顺序表

1.2.1 顺序表的实现——静态分配

  1. #define MaxSize  10               //定义最大长度
  2. typedef  struct{                  
  3.          ElemType data[MaxSize];  //用静态数组存放数据元素
  4.          int length;              //顺序表当长度
  5. }SqList;                          //顺序表的类型定义（静态分配方式）
  6. //初始化顺序表
  7. void InitList(SqList &L){
  8.     for(int i=0;i<MaxSize;i++)
  9.          L.data[i]=0;
  10.     L.length=0;
  11. }

1.2.2 顺序表的实现——动态分配<br />

  1. #define InitSize  10    //顺序表的初始长度
  2. typedef struct{
  3. Elemtype  *data;     //指示动态分配数组的指针
  4. int MaxSize;         //顺序表的最大容量
  5. int length;          //顺序表当前长度
  6. }SeqList;                  //(动态分配)
  7. //备注：malloc 和 free 需要的头文件#include<stdlib.h>
  8. void InitList(SqList &L){
  9. L.data=(int )malloc(InitSizesizeof(int));
  10. L.length=0;
  11. L.MaxSize=InitSize;
  12. }
  13. //增加动态数组的长度
  14. void IncreaseSize(SqList &L,int len){
  15. int *p=L.data;
  16. L.data=(int )malloc((L.MaxSize+len)sizeof(int));
  17. for(int i=0;i<L.length;i++){
  18. L.data[i]=p[i];
  19. }
  20. L.MaxSize+=len;
  21. free(p);
  22. }

1.2.3 顺序表的插入和删除

  1. bool ListInsert(SqList &L,int i,int e){
  2. if(i<1 || i>L.length+1)
  3. return false;
  4. if(L.length>=MaXSize)
  5. return false;
  6. for(int j=L.length;j>=i;j--)
  7. L.data[j]=L.data[j-1];
  8. L.data[i-1]=e;
  9. L.length++;
  10. return true;
  11. }
  12. bool ListDelete(SqList &L,int i,int &e){
  13. if(i<1 && i>L.length)
  14. return false;
  15. e=L.data[i-1];
  16. for(int j=i;j<L.length;j++){
  17. L.data[j-1]=L.data[j];
  18. L.length--;
  19. return true;
  20. }
  21. }

1.2.4 顺序表的查找
ElemType GetElem(SqList L,int i){
return L.data[i-1];
}
int LocateElem(SqList L,ElemType e){
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
1.3.1 单链表的定义
//struct LNode ``_ p=struct(LNode _``) malloc(sizeof(struct LNode));
typedef struct LNode{
ElemType data;
struct LNode * next;
}LNode,*LinKList;

//
LNode * GetElem(LinkList L,int i){
int j=1;
LNode *p=L->next;
if(i``0)<br />return L;<br />if(i<1)<br />return NULL;<br />while(p!=NULL && j<i){<br />p=p->next;<br />j++;<br />}<br />return p;<br />}<br />//初始化不带头结点得单链表<br />bool InitList(LinkList &L){<br />L=NULL;<br />return true;<br />}<br />//判断单链表是否为空<br />bool Empty(LinkList L){<br />return (L``NULL);
}
//初始化一个单链表（带头结点得单链表）
bool InitList(LinkList &L){
L=(LNode *) malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next=NULL;
return true;
}
1.3.2 单链表的插入和删除
按位序插入（带头结点）
bool ListInsert(LinkList &L,int i,ElemType){
if(i<1)
return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i-1){
p=p->next;
j++;
}
if(p``null)<br />return fasle;<br />LNode _ s=(LNode _)malloc(sizeof(LNode));<br />s->data=e;<br />s->next=p->next;<br />p->next=s;<br />return true;<br />}<br />//按位序插入（不带头结点）<br />bool ListInsert(LinkList &L,int i,ElemType e){<br />if(i<1)<br />retrun false;<br />if(i``1){
LNode ``_s=(LNode _``)malloc (sizeof(LNode));
s->data=e;
s->next=L;
L=s;
return true;
}
LNode *p;
int j=1;
p=L;
int j=1;
p=L;
while(p!=NULL && j<=i-1){
p=p->next;
j++;
}
if(p``NULL)<br />return false;<br />LNode _s=(LNode _)malloc(sizeof(LNode));<br />s->data=e;<br />s->next=p->next;<br />p->next=s;<br />return true;<br />}<br />//指定结点的后插操作<br />bool InsertNextNode(LNode *p,ElemType e){<br />if(p``NULL)
return false;
LNode ``_s=(LNode _``)malloc(sizeof(LNode));
if(s``NULL)<br />return false;<br />s->data=e;<br />s->next=p->next;<br />p->next=s;<br />return true;<br />}<br />//前插：在p结点之前插入结点s<br />bool InsertPriorNode(LNode *p,ElemType){<br />if(p``NULL)
return false;
LNode ``_s=(LNode _``)malloc(sizeof(LNode));
if(s``NULL)<br />return false;<br />s->next=p->next;<br />p->next=s;<br />s->data=p->data;<br />p->data=e;<br />}<br />//按位序删除（带头结点）<br />bool ListDelete(LinkList &L,int i,ElemType &e){<br />if(i<1)<br />retrun false;<br />LNode * p;<br />int j=0;<br />p=L;<br />while(p!=NULL && j<i-1){<br />p=p->next;<br />j++;<br />}<br />if(p=NULL)<br />return false;<br />if(p->next``NULL){
retrun false;
}
LNode * q=p->next;
e=q->data;
p->next=q->next;
free(q);
retrun true;
}
bool DeleteNode(LNode *p){
if(p==NULL)
retrun false;
LNode *q=p->next;
p->data=p->next->data;
p->next=q->next;
free(q);
return true;
}
1.3.3 单链表的查找
LNode * GetElem(LinkList L,int i){
if(i<0)
return NULL;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i){
p=p->next;
j++;
}
return p;
}
//按值查找
LNode * LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL && p->data !=e){
p=p->next;
}
return p;
}
1.3.4 单链表的建立
//插入操作
bool InsertNextNode(LNode *p,ElemType e){
if(p``NULL)<br />return fasle;<br />LNode _s=(LNode _)malloc(sizeof(LNode));<br />if(s``NULL)
return fasle;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
1.4.1 双链表
//定义双链表
typedef struct DNode{
ElemType data;
struct DNode ``_ prior,_``next;
}DNode,*DLinkList;
//初始化双链表(带头结点的)
bool InitDLinkList(DLinkList &L){
L=(DLinkList *)malloc(sizeof(DNode));
if(L``NULL)<br />return false;<br />L->prior=NULL;<br />L->next=NULL;<br />return true;<br />}<br />//判断双链表是否为空（带头结点）<br />bool Empty(DLinklist L){<br />if(L->next``NULL)
return true;
else
return false;
}
//双链表的插入(在p结点之后插入s结点)
bool InsertNextDNode(DNode ``_p,DNode _``s){
if(p``NULL || S``NULL)
return false;
s->next=p->next;
if(p->next!=NULL)
p->next->prior=s;
s->prior=p;
p->next=s;
}
//双链表的删除（删除p继结点的后接结点）
bool DeleteNextNode(DNode *p){
if(p``NULL) return false;<br />DNode *q=p->next;<br />if(q``NULL) retrun false;
p->next=q->next;
if(q->next!=NULL)
q->next->prior=p;
free(q);
retrun true;
}
//销毁双链表
void DestroyList(DLinkList &L){
while(L->next!=NULL)
DeleteNextDNode(L);
free(L);
L=NULL;
}
1.5.1 循环单链表
//循环单链表的定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//初始化一个循环单链表
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode));
if(L``NULL)<br />return fasle;<br />L->next=L;<br />return true;<br />}<br />//判断循环单链表是否为空<br />bool Empty(LinkList L){<br />if(L->next``L)
return true;
else
return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){
if(p->next==L)
return true;
else
return fasle;
}
1.5.2 循环双链表
//定义循环双链表
typedef struct DNode{
ElemType data;
struct DNode ``_ prior,_``next;
}DNode,*DLinkList;
//初始化空的循环双链表
bool InitDLinkList(DLinkList &L){
L=(DNode *)malloc(sizeof(DLNode));
if(L``NULL)<br />return fasle;<br />L->prior=L;<br />L->next=L;<br />return true;<br />}<br />//判断循环双链表是否为空<br />bool Empty(DLinkList L){<br />if(L->next``L)
return true;
else
return fasle;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L,DNode *p){
if(p->next==L)
return true;
else
return fasle;
}
//双链表的插入（在p结点之后插入s结点）
bool InsertNextDNode(DNode ``_p,DNode _``s){
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
}
//删除p的后继结点q