单链表
代码定义
typedef struct LNode
{
?ElemType data; //值域
?struct LNode *next; //定义域
}LNode,*LinkList;
?
//等价于
struct LNode{
? ?ElemType data;
? ?struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
//要表示一个单链表时，只需要申明一个头指针L,指向单链表的第一个节点
LNode *L //强调这是一个节点
LinkList L ? ==>二者等价 ?//强调这是一个链表
? ?
//初始化
? ?
//不带头节点
bool InitList(LinkList &L){
? ?L=NULL;
? ?return true;
}
?
//带头结点
bool InitList(LinkList &L){
? ?L=(LNode *)malloc(sizeof(LNode)); //分配一个头节点
? ?if(L==NULL) ?//分配失败
? ? ? ?return false;
? ?L->next=NULL: ?//头节点之后暂时没有节点
? ?return true;
}
?
void test(){
? ?LinkList L; //声明一个指向单链表的指针
? ?InitList(L); //初始化
}
单链表的插入与删除
带头节点的单链表插入
//带头节点的单链表插入
/*
在第i个位置进行插入一个数值，首先找到第i-1个节点，然后进行插入操作
*/
?
typedef struct LNode
{
?ElemType data; //值域
?struct LNode *next; //定义域
}LNode,*LinkList;
?
//在第i个位置插入元素e
bool ListInsert(LinkList &L,int i,ElemType e){
? ?//判断位置是否合理，i>=1
? ?if(i<1)
? ? ? ?return false;
? ?//声明一个指针指向头节点，与头指针一样
? ?LNode *p;
? ?p=L;
? ?//找到第i-1个节点
? ?int j=0; //记录当前位置
? ?while(p!=NULL && j<i-1){
? ? ? ?p-p->next;
? ? ? ?j++;
? }
? ?//if(p==NULL)
? ?// ? return false; //i值不合法
? ?//LNode *s=(LNode *)malloc(sizeof(LNode));
? ?//s->data=e;
? ?//s->next=p->next;
? ?//p->next=s;
? ?//return true;
? ?return InsertNextNode(p,e);
}
?
//平均时间复杂度 ? 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->next=p->next;
? ?p->next=s;
? ?return true;
}
//时间复杂度 ? O(1)
指定节点的前插操作
//思路：进行后插，交换节点里面的值
bool InsertPriorNode(LNode *p,ElemType e){
? ?if(p==NULL)
? ? ? ?return false;
? ?LNode *s=(LNode *)malloc(sizeof(LNode)); //申请一个节点
? ?if(s==NULL)
? ? ? ?return false; ?//申请失败
? ?//插入节点
? ?s->next=p->next;
? ?p->next=s;
? ?//交换数值
? ?s-data=p->data;
? ?p-data=e;
? ?return true;
}
//时间复杂度 O(1)
带头节点的单链表删除
//按位序删除
bool ListDelete(LinkList &L,int i,ElemType &e){
? ?if(i<1)
? ? ? ?return fasle;
? ?//找到第i-1个节点
? ?LNode *p;
? ?p=L;
? ?int j=0;
? ?while(p!=NULL && j<i-1){
? ? ? ?p=p->next;
? ? ? ?j++;
? }
? ?if(p==NULL)
? ? ? ?return false; //i不合法
? ?LNode *q=p->next;
? ?p->next=q->next;
? ?e=q->data;
? ?free(q);
? ?return true;
}
//平均时间复杂度 O(n)
?
//指定节点的删除
bool DeleteNode(LNode *p,ElemType e){
? ?//由于找前驱节点非常麻烦，所以找到后继节点，交换值，然后释放后继节点
? ?LNode *q=p->next;
? ?e=p->data;
? ?p->data=q->data;
? ?p->next=q->next;
? ?free(q);
? ?return true;
? ?
? ?//时间复杂度 O(1)
? ?
}
单链表的查找
按值查找 LocateElem(L,e)
//按值查找
LNode * LocateElem(LinkList L,ElemType e){
? ?LNode *p;
? ?p=L; //p指向头节点
? ?p=p->next;
? ?while(p!=NULL && p->data!=e){
? ? ? ?p=p->next;
? }
? ?return p;
}
?
//平均时间复杂度 ? O(n)
按位查找 GetElem(L,i)
//按位查找，返回第i个元素（带头结点）
LNode * GetElem(LinkList L,int i){
? ?if(i<0)
? ? ? ?return NULL;
? ?LNode *p; //表示当前扫描到的节点
? ?int j=0; //当前p指向第几个节点
? ?p=L;
? ?while(p!=NULL && j<i){
? ? ? ?p=p->next;
? ? ? ?j++;
? }
? ?return p;
}//时间复杂度 O(n)
单链表长度
//求单链表的长度
int Length(LinkList L){
? ?int len=0; //长度
? ?LNode *p=L;
? ?while(p->next!=NULL){
? ? ? ?p=p->next;
? ? ? ?len++;
? }
? ?return len;
}
//时间复杂度 ? O(n)
单链表的建立
you have many numbers,you should fix it in a LinkList
step 1:初始化一个单链表
step 2:每次取一个数据元素，插入到表头/尾
头插法
//插入表头
//每次对头节点进行后插操作
LinkList List_HeadInsert(LinkList &L){
? ?//建立头节点
? L=(LinkList)malloc(sizeof(LNode));
? ?L->next=NULL;
? ?int x;
? ?scanf("%d",&x);
? ?LNode *s=L; //指针指向头节点
? ?while(x!=9999){
? ? ? //s申请一个新的空间
? ? ?s=(LNode *)malloc(sizeof(LNode));
? ? ? ?s->data=x;
? ? ? ?s->next=L->next;
? ? ? ?L->next=s;
? ? ? ?scanf("%d",&x);
? }
? ?return L;
}
?
//时间复杂度 ? O(n)
尾插法
//尾插法建立单链表，带头结点
//思路：首先建立一张空表，然后建立两个指针r,s都指向头节点，s每次申请一个新节点进行插入，r始终指向尾部
LinkList List_TailInsert(LinkList &L){
? ?L=(LinkList)malloc(sizeof(LNode)); //头节点
? ?LNode *s,*r;
? ?r=s=L; //都指向头节点
? ?int x;
? ?scanf("%d",&x);
? ?while(x!=9999){
? ? ? ?//进行后插
? ? ? ?//s申请一个新的节点
? ? ? ?s=(LNode *)malloc(sizeof(LNode));
? ? ? ?s->data=x;
? ? ? ?r->next=s;
? ? ? ?r=s;
? ? ? ?scanf("%d",&x);
? }
? ?r->next=NULL;
? ?return L;
}
?
//时间复杂度 ? O(n)
|