线性表——链式存储

单链表（有头结点）

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{int data;        //数据域 struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 //初始化（有头结点），只分配一个头结点 
bool InitList(LinkList &L){            //LNode主要强调这是一个结点，而LinkList主要强调这是一个单链表，这里是对单链表进行初始化，所以参数最好使用LinkList L=(LNode *)malloc(sizeof(LNode));        //分配一个头结点的内存 if(L==NULL)        //内存不足，分配失败 return false;L->next=NULL;        //头结点后面暂时没有结点 return true; 
}//单链表的建立——尾插法
LinkList List_TailInsert(LinkList &L){//第一步：初始化一个单链表L=(LinkList)malloc(sizeof(LNode));    //建立头结点,注意这里强调是单链表，所以是LinkList类型 LNode *s,*r=L;        //s结点用于存储新元素，r结点为尾结点，永远指向最后一个结点int x;        //新元素scanf("%d",&x);        //输入新元素的值if(x!=999){            //当输入999时结束新元素插入 s=(LNode *)malloc(sizeof(LNode));        //为新节点分配内存if(s=NULL)        //内存分配失败 return NULL;s->data=x;r->next=s;r=s;scanf("%d",&x);        //输入新元素的值} r->next=NULL;        //注意不能忘记 return L;}//单链表的建立——头插法，与尾插法同理，只是不需要尾指针，因为头结点代替了他的作用
LinkList List_HeadInsert(LinkList &L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;LNode *s;int x;scanf("%d",&x);if(x!=999){s=(LNode *)malloc(sizeof(LNode));if(s=NULL)return NULL;s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);}return L;
} //指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败s->data=e;s->next=p->next;p->next=s;return true;
}//按位查找,查找第i个元素 
LNode * GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p;        //p指针用于指向当前扫描到的结点int j=0;         //j表示当前扫描到了第几个结点,开始是头结点——第0个结点p=L;            //p开始指向头结点 while(p!=NULL&&j<i){p=p->next;j++;} return p;
} //按值查找
LNode * LocateElem(LinkList L,int e){LNode *p=L->next;    //p指向第一个结点while(p!=NULL&&p->data!=e){p=p->next;} return p;} //插入,在位置i插入结点e ，采用封装思想 
bool ListInsert(LinkList &L,int i,int e){if(i<1)return false; //    LNode *p;        //p指针用于指向当前扫描到的结点
//    int j=0;        //j表示当前扫描到了第几个结点
//    p=L;        //p指针最初指向头结点 
//    if(p!=NULL&&j<i-1){        //找到并用p指向第i-1个结点 
//        p=p->next;
//        j++ ; 
//    } LNode *p=GetElem(L,i-1);         //找到第i-1个结点//    if(p==NULL)        //防止i>(链表长度+1) 
//        return false;
//        
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配一个结点的内存
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true; return InsertNextNode(p,e);            //再第i-1个结点后面插入e 
} //指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败/*因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 */s->next=p->next;p->next=s;s->data=p->data;p->data=e;return true;
}//按位删除，删除表L中第i个位置的元素，并用e返回删除元素的值 。核心：找到第i-1个元素 
bool ListDelete(LinkList &L,int i,int e){if(i<1)return false;LNode *p;    //指向当前扫描到的结点int j=0;        //当前扫描到第几个结点,头结点是第0个结点 p=L;        //p开始指向头结点（注意：头结点不存储数据）while(p!=NULL&&j<i-1){        //找第i-1个元素 p=p->next;j++;} if(p==NULL)return false;if(p->next==NULL)        //说明p是最后一个结点 return false;LNode *q=p->next;        //令q指向被删除的结点 e=q->data;                //用e返回删除元素的值p->next=q->next; free(q);return true;
} //删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){if(p=NULL)return false;LNode *q=p->next;p->data=p->next->data;p->next=q->next;free(q);return true;
} 
int main(){}

单链表（无头结点）

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{int data;        //数据域 struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 //初始化 （无头结点） 
bool InitList(LinkList &L){L=NULL;        //空表，暂时没有任何结点 return true; 
} //按位查找
LNode * GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p;int j=1;    //注意没有头结点所以初始值为1 p=L;while(p!=NULL&&j<i){p=p->next;j++; } return p;
} //按值查找
LNode * LocateElem(LinkList L,int e){LNode *p=L;    //p开始指向第一个结点 while(p!=NULL&&p->data!=e){p=p->next;}return p;
} //指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败s->data=e;s->next=p->next;p->next=s;return true;
}//插入，在位置i插入结点e 
bool ListInsert(LinkList &L,int i,int e){if(i<1)return false;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;        //p指向第一个结点，注意不是头结点 
//    
//    while(p!=NULL&&j<i-1){
//        p=p->next;
//        j++;
//    }LNode *p=GetElem(L,i-1);//    if(p=NULL)
//        return false;
//         
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //申请内存 
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true;return InsertNextNode(L,e);
} //指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败/*因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 */s->next=p->next;p->next=s;s->data=p->data;p->data=e;return true;
}//删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){if(p=NULL)return false;LNode *q=p->next;p->data=p->next->data;p->next=q->next;free(q);return true;
} 
int main(){}

双链表

#include<stdio.h>
#include<stdlib.h>
//只有涉及到参数中有结点就需要判断结点是否为空 
//定义
typedef struct DNode{int data;struct DNode *prior,*next;
}DNode,*DLinklist;//初始化
bool InitDLinkList(DLinklist &L){L=(DNode *)malloc(sizeof(DNode));if(L==NULL)return false;L->next=NULL;L->prior=NULL;return true;
}
//插入
bool InsertNextDNode(DNode *p,DNode *e){if(p==NULL||e==NULL)return false;e->next=p->next;if(p->next!=NULL)p->next->prior=e;e->prior=p;p->next=e;return true;}
//删除,删除p的后继结点
bool DeleteNextDNode(DNode *p){if(p==NULL)        return false;DNode *q=p->next;if(q==NULL)return false;p->next=q->next;if(q->next!=NULL)q->next->prior=p;free(q);return true;} //遍历 int main(){} 

循环单链表

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{int data;        //数据域 struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 //初始化（有头结点），只分配一个头结点 
bool InitList(LinkList &L){            //LNode主要强调这是一个结点，而LinkList主要强调这是一个单链表，这里是对单链表进行初始化，所以参数最好使用LinkList L=(LNode *)malloc(sizeof(LNode));        //分配一个头结点的内存 if(L==NULL)        //内存不足，分配失败 return false;L->next=L;        //头结点后面暂时没有结点 return true; 
}//单链表的建立——尾插法
LinkList List_TailInsert(LinkList &L){//第一步：初始化一个单链表L=(LinkList)malloc(sizeof(LNode));    //建立头结点,注意这里强调是单链表，所以是LinkList类型 LNode *s,*r=L;        //s结点用于存储新元素，r结点为尾结点，永远指向最后一个结点int x;        //新元素scanf("%d",&x);        //输入新元素的值if(x!=999){            //当输入999时结束新元素插入 s=(LNode *)malloc(sizeof(LNode));        //为新节点分配内存if(s=NULL)        //内存分配失败 return NULL;s->data=x;r->next=s;r=s;scanf("%d",&x);        //输入新元素的值} r->next=NULL;        //注意不能忘记 return L;}//单链表的建立——头插法，与尾插法同理，只是不需要尾指针，因为头结点代替了他的作用
LinkList List_HeadInsert(LinkList &L){L=(LinkList)malloc(sizeof(LNode));L->next=L;LNode *s;int x;scanf("%d",&x);if(x!=999){s=(LNode *)malloc(sizeof(LNode));if(s=NULL)return NULL;s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);}return L;
} //指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败s->data=e;s->next=p->next;p->next=s;return true;
}//按位查找,查找第i个元素 
LNode * GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p;        //p指针用于指向当前扫描到的结点int j=0;         //j表示当前扫描到了第几个结点,开始是头结点——第0个结点p=L;            //p开始指向头结点 while(p!=NULL&&j<i){p=p->next;j++;} return p;
} //按值查找
LNode * LocateElem(LinkList L,int e){LNode *p=L->next;    //p指向第一个结点while(p!=NULL&&p->data!=e){p=p->next;} return p;} //插入,在位置i插入结点e ，采用封装思想 
bool ListInsert(LinkList &L,int i,int e){if(i<1)return false; //    LNode *p;        //p指针用于指向当前扫描到的结点
//    int j=0;        //j表示当前扫描到了第几个结点
//    p=L;        //p指针最初指向头结点 
//    if(p!=NULL&&j<i-1){        //找到并用p指向第i-1个结点 
//        p=p->next;
//        j++ ; 
//    } LNode *p=GetElem(L,i-1);         //找到第i-1个结点//    if(p==NULL)        //防止i>(链表长度+1) 
//        return false;
//        
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配一个结点的内存
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true; return InsertNextNode(p,e);            //再第i-1个结点后面插入e 
} //指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 if(s==NULL)return false;        //内存分配失败/*因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 */s->next=p->next;p->next=s;s->data=p->data;p->data=e;return true;
}//按位删除，删除表L中第i个位置的元素，并用e返回删除元素的值 。核心：找到第i-1个元素 
bool ListDelete(LinkList &L,int i,int e){if(i<1)return false;LNode *p;    //指向当前扫描到的结点int j=0;        //当前扫描到第几个结点,头结点是第0个结点 p=L;        //p开始指向头结点（注意：头结点不存储数据）while(p!=NULL&&j<i-1){        //找第i-1个元素 p=p->next;j++;} if(p==NULL)return false;if(p->next==L)        //说明p是最后一个结点 return false;LNode *q=p->next;        //令q指向被删除的结点 e=q->data;                //用e返回删除元素的值p->next=q->next; free(q);return true;
} //删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){if(p=NULL)return false;LNode *q=p->next;p->data=p->next->data;p->next=q->next;free(q);return true;
} 
int main(){}

循环双链表

#include<stdio.h>
#include<stdlib.h>
//只有涉及到参数中有结点就需要判断结点是否为空 
//定义
typedef struct DNode{int data;struct DNode *prior,*next;
}DNode,*DLinklist;//初始化
bool InitDLinkList(DLinklist &L){L=(DNode *)malloc(sizeof(DNode));if(L==NULL)        //分配内存失败 return false;L->next=L;L->prior=L;return true;
}
//插入
bool InsertNextDNode(DNode *p,DNode *e){if(p==NULL||e==NULL)return false;e->next=p->next;p->next->prior=e;e->prior=p;p->next=e;return true;}
//删除,删除p的后继结点
bool DeleteNextDNode(DLinklist &L,DNode *p){if(p==NULL)        return false;DNode *q=p->next;if(q==L)return false;p->next=q->next;q->next->prior=p;free(q);return true;} //遍历 int main(){}