单链表的常见基础算法（一）

女爷i 2023-05-29 13:18 9阅读 0赞

**单链表的定义**

typeded struct{
        
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;

**双链表的定义**

typedef struct{
        
    	ElemType data;
    	struct DNode *next, *piror;
    }DNode, *DLinkList;

*  **头插法建立单链表**

LinkList Create(LinkList &L){
        
    	ElemType x;
    	LNode *s;
    	L=(LinkList)malloc(SizeOf(LNode));//申请头结点所需空间
    	L->next=NULL;
    	cin>>x;
    	while(x!=9999){
        
    		s=(LNode)malloc(SizeOf(LNode));
    		s->data=x;
    		s->next=L->next; //将新节点插入
    		L->next=s;
    		cin>>x;
    	}
    	return L;
    }

*  **尾插法建立单链表**

//需要设置尾指针
    LinkList Create(LinkList &L){
        
    	LNode *r, *s;
    	ElemType x;
    	L=(LinkList)malloc(SizeOf(LNode));
    	r=L;
    	cin>>x;
    	while(x!=9999){
        
    		s=(LNode)malloc(SizeOf(LNode));
    		s->data=x;
    		r-next=s;
    		r=s;
    		cin>>x
    	}
    	r-next=NULL;//将尾指针置为空
    	return L;
    }

*  **按序号查找结点值——在单链表L中查找第i个结点**

//在单链表L中查找第i个结点
    LNode *GetElem(LinkList L,int i){
        
    	LNode *p=L->next;//p为工作指针，指向单链表中第一个元素
    	int j;
    	if(i==0) return L;
    	if(i<1) return NULL;
    	for(j=1;p!=NULL&&j<i;j++){
        
    		p=p->next;
    	}
    	return p;
    }

*  **按值查找结点值——在单链表L 中查找值为e的结点**

LNode *GetElem(LinkList L,ElemType e){
        
    	LNode *p=L->next;
    	for(;p!=NULL;p=p->next){
        
    		if(p->data==e)
    			return p;//找到元素e.返回指向元素e的指针
    	}
    	return p;//返回空指针
    }

*  **在单链表L的第i个位置上插入某一结点x**

//方法一：通过找到待插入位置的前一个结点的位置，将其插入
    LinkList Insert(LinkList &L,int i,ElemType x){
        
    	LNode *p=GetElem(L,i-1);//找到待插入位置的前一个结点的位置；
    	LNode *s=(LNode)malloc(SizeOf(LNode));
    	s->data=x;
    	s-next=p->next;
    	p->next=s;
    	return L;
    }
    //扩展：若已知p结点的位置，要在p结点之前插入一个结点，可以将s插入到p之后，然后将其结点的值域部分交换位置
    	s->next=p-next;
    	p->next=s;
    	//交换值域部分
    	temp=s->data;
    	s->data=p->data;
    	p->data=temp;

*  **删除单链表L的第i个位置上的结点**

LinkList Delete(LinkList &L,int i){
        
    	LNode *p=GetElem(L.i-1);
    	LNode *q=p->next;
    	p->next=q->next;
    	free(q);//释放删除结点的空间
    	return L;
    }
    //扩展：若已知p结点，删除p结点之后的一个结点，可通过删除删除其后继结点实现
    	q=p->next;
    	p->data=q->data;
    	p->next=q->next;//删除后继结点
    	free(q);

*  **将单链表L中值为x的结点删除**

LinkList Delete(LinkList &L,ElemType x){
        
    	//查找值为x的结点
    	LNode *p=L->next;
    	for(;p!=NULL;p=p->next){
        
    		if(p->data==x)
    			break;
    	}
    	if(p==NULL) return L;
    	//将结点p删除
    	LNode *q=p->next;
    	p->data=q->data;
    	p->next=q->next;
    	free(q);
    	return L;
    }

*  **求单链表L的表长**

int GetLength(LinkList L){
        
    	LNode *p=L->next;
    	for(int i=0;p!=NULL;i++,p=p->next)
    	return i;
    }