单链表
链表定义
typedef struct node
{
int data;
struct node * next;
}LinkNode,*LinkList;初始化链表
带头结点
bool InitList(LinkList &L)
{
L = (LinkNode*)malloc(sizeof(LinkNode));
if(L == NULL)
return false; //内存不足，分配失败
L->next = NULL;
return true;
}不带头节点
bool InitList(LinkList &L)
{
L=NULL;
return true;
}建立链表
头插法
带头结点
LinkList head_insert(LinkList &L)
{
int x;
L = (LinkNode*)malloc(sizeof(LinkNode));
L->next = NULL;
LinkNode *p;
while(cin>>x)
{
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = x;
p->next = L->next;
L->next = p;
}
return L;
}尾插法
正向建立链表
带头节点
LinkList tail_insert(LinkList &L)
{
int x;
L = (LinkNode*)malloc(sizeof(LinkNode));
LinkNode *p，*tail=L;
while(cin>>x)
{
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = x;
tail->next = p;
tail = p;
}
tail->next = NULL;
return L;
}插入操作
第i个位置插入
有头节点
bool insert(LinkList &L,int i,ElemType data)
{
if(i < 1)//输入i值不合法
return false;
LinkNode *p = L;
int j = 0;
while(p != NULL&&j < i-1)//找到第i-1个节点
{
p=p->next;
j++;
}
if(p == NULL)//输入i值不合法
return false;
LinkNode *e = (LinkNode*)malloc(sizeof(LinkNode));
e->data = data;
e->next = p->next;
p->next = e;
}最好时间复杂度O(1)，向第一个位置插入节点
平均时间复杂度O(n)，一共有n+1个位置，每个位置被插入的概率为，第一个位置到第n+1个位置的操作次数分别为,1,2,3...,n.平均操作次数为
最差时间复杂度O(n)，向最后一个位置插入节点
无头节点
bool insert(LinkList &L,int i,ElemType data)
{
if(i < 1)
return false;
if(i == 1)
{
LinkNode * s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = data;
s->next = L;
L = s;
return true;
}
LinkNode *p = L;
int j = 1;
while(p != NULL && j < i-1)
{
p = p->next;
j++;
}
if(p==NULL)
return false;
LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode))
s->data = data;
s->next = p->next;
p->next = s->next;
return true;
}复杂度与有头节点相同
※给定指针，在指针前插节点
带头结点
可以在给定指针后插入一个新节点，然后将新节点的值与当前指针指向节点的值互换，这样就起到了前插节点的作用。
bool InsertPriorNode(LinkNode *p,ElemType data)
{
if(p == NULL)
return false;
LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = p->data;
p->data = data;
s->next = p->next;
p->next = s;
return true;
}?最优、最差、平均时间复杂度均为O(1)
删除操作
删除链表中第i个位置的元素
带头节点
bool Delete(LinkList &L,int i,ElemType &e)
{
if(i<1)
return false;
LinkNode *p = L;
int j = 0;
while(p != NULL && j < i-1)
{
p=p->next;
j++;
}
if(p == NULL)
return false;
if(p->next == NULL)
return false;
LinkNode * s = p->next;
p->next = s->next;
e = s->data;
free(s);
return true;
}最好时间复杂度为O(1)
最差时间复杂度为O(n)
平均时间复杂度为O(n)：有n个节点，每个节点被删除的概率为，所以共需操作
次
删除给定指针指向的节点
当要删除的是最后一个节点时，无法使用这种方法
bool DeleteNode(LinkNode *p)
{
if(p==NULL)
return false;
LinkNode *s = p->next;
p->data = s->data;
p->next = s->next;
free(s);
return false;
}时间复杂度为O(1)
查找操作
按位查找
LinkNode *GetElem(LinkList &L,int i)
{
if(i<0)
return false;
LinkNode *p = L;
int j = 0;
while(p != NULL && j < i)
{
p=p->next;
j++;
}
return p;
}最优时间复杂度为O(1)
最差和平均时间复杂度为O(n)
按值查找
LinkNode *GetElem(LinkList &L,ElemType e)
{
LinkNode *p = L;
while(p != NULL && p->data != e)
{
p=p->next;
}
return p;
}最优时间复杂度为O(1)
最差和平均时间复杂度为O(n)
双链表
双链表的定义
typedef struct node
{
int data;
struct node * next,*prior;
}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 isEmpty(DLinkList &L)
{
if(L->next == NULL)
return true;
return false;
}指定指针后插入节点
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;
return true;
}删除指定指针的后继节点
bool DeleteNextDNode(DNode *p)
{
if(p==NULL)
return false;
if(p->next == NULL)
return false;
DNode *s = p->next;
p->next = s->next;
if(s->next != NULL)
s->next->prior = p;
free(s);
return true;
}循环单链表
定义与单链表一样，只是链表初始化时，头节点的指针指向头节点本身，此外，如果链表不空，那么链表中最后一个节点总是指向头节点。
初始化
bool InitLinkList(LinkList &L)
{
L = (LNode*)malloc(sizeof(LNode));
if(L==NULL)
return false;
L->next = L;
return true;
}很多时候，对链表的操作都是针对表头和表尾进行的，如果L指向头节点，那么操作表尾的时间复杂度为O(n).因为时循环单链表，所以可以让L指向尾节点。
循环双链表
初始化
bool InitLinkList(LinkList &L)
{
L = (DNode*)malloc(sizeof(DNode));
if(L==NULL)
return false;
L->next = L;
L->next = L;
return true;
}静态链表
定义
typedef struct Node
{
ElemType data;//存储数据元素
int next; //下一个元素的数组下标
}SLinkLIst[MaxSize];