数据结构——单链表
//定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}Lnode,*linkList;
LinkList L; //声明一个指向单链表第一个节点的指针，并没有创建节点
//初始化（带头节点）
bool InitList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode)); //分配一个头节点
if(L==NULL) //内存不足，分配失败
return false;
L->next=NULL; //头节点之后无节点
return tire;
}
//判空
bool Empty(LinkList L){
return(L==NULL);
}
//在第i个位置插入元素e（带头节点）
bool ListInsert(LinkList &L,int I,ElemType e){
if(I<1)
return false;
LNode *p; //指针p指向当前扫描到的节点
int j=0; //当前p指向的事第几个节点
p=L; //L指向头节点，头节点是第0个节点（不存数据）
while (p!=NULL&&j<I-1){ //循环找到第i-1个节点
p=p->next;
j++;
}
//后续代码可使后插函数代替
//return InsertNextNode(p,e);
if(p==NULL) //i值不合法
return false;
LNode *s=(Lnode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //将节点s连接到p之后
p->next=s;
return ture; //插入成功
}
//不带头节点插入
bool ListInsert(LinkList &L,int I,ElemType e){
if(I<1)
return false;
if(I==1){ //插入第1个节点的操作不同
LNode *s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=L;
L=s; //头指针指向新节点
return tire;
}
LNode *p; //指针p指向当前扫描到的节点
int j=1; //当前p指向的事第几个节点
p=L; //L指向头节点，头节点是第0个节点（不存数据）
//后续逻辑和带头节点一样
while (p!=NULL&&j<I-1){ //循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
LNode *s=(Lnode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next; //将节点s连接到p之后
p->next=s;
return ture; //插入成功
}
//之后操作基于带头节点
平均时间复杂度O(n)
//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
if(p==NULL)
return false;
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL) //内存分配失败
return false;
s->data=e; //节点s保存数据元素e
s->next=p->next;
p->next=s; //节点s连接到p之后
return tire;
}
时间复杂度O(1)
//前插操作：在p节点之前插入元素e
bool InsertPriorNode(LNode *p, LNode *s){
if(p==NULL || s==NULL)
return false;
s->next=p->next;
p->next=s; //s连接到p之后
ElemType temp=p->data; //交换数据域部分
p->data=s->data;
s->data=temp;
return true;
}
时间复杂度O(1)
//按位序删除，删除表L中第i个位置的元素，用e返回
bool ListDelete(LinkList &L, int I, ElemType &e){
if(I<1)
return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL&&j<I-1){ //循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL) //i值不合法
return false;
if(p->next==NULL) //第i-1后无节点
return false;
LNode *q=p->next; //令q指向被删除节点
e=q->data; //用e返回元素的值
p->next=q->next; //将*q节点从链中“断开”
free(q):
return true;
}
最坏、平均时间复杂度O(n)
最好时间复杂度O(1)
//指定节点删除,删除指定节点p
bool DeleteNode(LNode *p){
if(p==NULL)
return false;
LNode *q=p->next; //令q指向*p的后继节点
p->data=p->next->data; //和后继节点交换数据
p->next=q->next; //将*q节点从链中“断开”
free(q);
return true;
}
时间复杂度O(1)
//按位查找，返回第i个元素
LNode *GetElem(LinkList L, int i){
int j=1;
LNode *p=L->next;
if(I==0)
return L;
if(I<1)
return NULL;
while(p!=Null&&j<i){
p=p->next;
j++;
}
return p;
}
//按值查找，找到数据位e的节点
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p:
}
//求表长
int Length(LinkList L){
int len=0;
LNode *p=L;
while(p->next!=NULL){
p=p->next;
len++;
}
return len;
}
时间复杂度O(n)
//尾插法
LinkList List_Taillnsert(linkList &L){ //正向建立单链表
int x;
L=(LinkList)malloc(sizeof(LNode)); //建立头节点
LNode *s,*r=L; //r为表尾指针
cin>>x; //输入插入的值
while(x!=9999){ //输入9999表示结束
s=(LNode *)malloc(sizeof(LNode)); //在r之后插入x
s->data=s;
r->next=s;
r=s; //r指向新的表尾节点
cin>>x;
}
r->next=NULL; //尾节点指针置空
return L;
}
输入序列：10，16，27，9999
链表：头->10->16->27->NULL
//头插法
LinkList List_Headlnsert(LinkList &L){
LNode *s;
int x;
L=(LinkList)malloc(sizeof(LNode));
cin>>x;
while(x!=9999){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L-.next;
L->next=s;
cin>>x;
}
return L;
}
输入：10，16，27，9999
链表：头->27->16->10->NULL
重要应用：链表的逆置