链表的基本操作(数据结构)

单链表

#include <stdlib.h>
#include <iostream>
#include <stdio.h>
typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;打印链表 
void PrintList(LNode *p)
{LNode *temp;temp = p->next;printf("链表的顺序:");while(temp!=NULL){printf("%d ",temp->data);temp = temp->next;}printf("\n");
}//头插法
LinkList HeadInsert(LinkList &L){LNode *s;int x;L = (LinkList)malloc(sizeof(LNode));L->next=NULL;printf("请输入数字:");scanf("%d",&x);while(x!=000){s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;printf("请输入数字:");scanf("%d",&x);}return L;
} //尾插法
LinkList TailInsert(LinkList &L){int x;L = (LinkList)malloc(sizeof(LNode));LNode *s,*r=L;printf("请输入数字:");scanf("%d",&x);while(x!=000){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;printf("请输入数字:");scanf("%d",&x);}r->next=NULL;return L;
} //按序号查找结点
LNode *GetElem(LinkList L){int i;printf("请输入要查找的节点:"); scanf("%d",&i);if(i<1) return NULL;int j=1;LNode *p = L->next;while(p!=NULL&&j<i){p=p->next;j++;}return p;
} //按照值来查找 
int LocateElem(LinkList &L){int x;int i=0;printf("请输入你要查询的数字:");scanf("%d",&x);LNode *p = L->next;while(p!=NULL&&p->data!=x){p = p->next;i++;}return i+1;
}//前插入节点
LinkList ListInsert(LinkList L,int i,int n)//插入一个数(后插法) 
{if(i<1) return L;LNode *p;int j=0;p=L->next;while(p!=NULL&&j<i-2){p=p->next;j++;}if(p==NULL)     //i值不合适 return L;LNode *s = (LNode*)malloc(sizeof(LNode));s->data = n;s->next = p->next;p->next = s;printf("success\n"); return L;
} //后插入节点
LinkList ListNextInsert(LinkList &L,int i,int n){if(i<1) return L;LNode *p;int j=0;p=L->next;while(p!=NULL&&j<i-1){p=p->next;j++;}if(L==NULL) return L;LNode *s = (LNode*)malloc(sizeof(LNode));if(s==NULL) return L;s->data= n;s->next = p->next;p->next = s;printf("success\n"); return L;
} int main(){LinkList L;HeadInsert(L);PrintList(L);TailInsert(L);PrintList(L);//按序号查找LNode *p;p = GetElem(L);printf("查找出来值为:%d\n",p->data);//按值查找int i;i = LocateElem(L);printf("找出位置:%d\n",i);//前插入printf("插入(L,2,99)");ListInsert(L,2,99);PrintList(L); //后插入printf("插入(L,3,99)");ListNextInsert(L,3,100);PrintList(L);return 0;
}

双链表

#include <stdlib.h>
#include <iostream>
#include <stdio.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->prior = NULL;//头节点的prior永远指向NULL L->next = NULL;//头节点之后暂时还没有节点 return true;
} //判断双链表是否为空(头节点)
bool Empty(DLinkList L){if(L->next==NULL){return true;}else{return false;}
} //双链表的插入 
bool InserNextDNode(DNode *p,DNode *s){if(p==NULL || s==NULL){return false;}s->next = p->next;if(p->next!=NULL){//如果p结点有后继节点 p->next->prior = s;}s->prior = p;p->next = s;return true;
}//双链表的删除
bool DeleteNextDNode(DNode *p){if(p==NULL) return false;DNode *q = p->next; //找到p的后继节点if(q==NULL) return false;//p没有后继节点p->next = q->next;if(q->next!=NULL){q->next->prior = p;} free(q);return true;} //销毁双链表
void DestoryList(DLinkList &L){//循环释放各个数据结点while(L->next!=NULL){DeleteNextDNode(L);} free(L);L=NULL;
}

循环单链表

#include <stdlib.h>
#include <iostream>
#include <stdio.h>
typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//初始化一个循环单链表
bool InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode));if(L==NULL) return false;L->next = L //头节点next指向头节点return true; 
} //判断循环单链表是否为空
bool Empty(LinkList L){if(L->next==L) return true;else return false;
} //判断节点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p){if(p->next == L) return true;else return false;
}

循环双链表

#include <stdlib.h>
#include <iostream>
#include <stdio.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->prior = L;L->next = L;return true;
}//判断循环双链表是否为空
bool Empty(DLinkList L){if(L->next==L) return true;else return false;
} //判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList &L,DNode *p){if(p->next==L) return true;else return false;
}