[数据结构与算法]2.2线性表——单链表基本操作的实现

注意：以下内容均省略思路，只有代码和时间复杂度。此内容为本人学习过程中的一些学习记录，如有错误，恳请各位指正、建议，末学将感激不尽！

目录

用结构指针描述单链表

初始化链表

判断空表

销毁单链表

清空单链表

求单链表的表长

读取表中指定元素的值

按值查找

单链表中指定位置插入节点

单链表中删除指定位置节点

建立链表——头插法

建立链表——尾插法

1. 用结构指针描述单链表

   typedef struct Node
     {
   	ElemType data;// 数据域
   	struct Node* Next; //指针域 
     } Node;
     typedef struct Node* LinkList//(相当于指向结点的指针)

2. 初始化链表

   Status InitList(LinkList L)
    {
    	L=(LinkList)malloc(sizeof(Node));
    	L-next=NULL;
    } 

3. 判断空表

   int ListEmpty(LinkList L)
     {
   	if(L->next)
   	{
   		return 0;
   	}
   	else
   	{
   		return 1;
   	}
     } 

4. 销毁单链表

   Status DestoryList(LinkList L)
     {
   	LinkList p;
   	while(L)
   	{
   	p=L;
   	L=L->next;
   	free(p);
   	}
   	return OK;
     } 

5. 清空单链表

   Status ClearList(LinkList L) 
     {
   	LinkList p,q;
   	p=L->next;
   	while(p)
   	{
   		q=p->next;
   		free(p);
   		p=q;	
   	}
   	L-next=NULL;
   	return OK;
     }

6. 求单链表的表长

   int ListLength(LinkList L)
     {
   	LinkList p;
   	int j=0;//计数器 
   	p=L->next;
   	while(p)
   	{
   		p=p->next;
   		j++;
   	}
   	return j;
     } 

7. 读取表中指定元素的值

   Status GetElem(LinkList L,int i,Elemtype *e)
    {
    	int j=1;
    	LinkList p;
    	p=L->next;
    	while(j<i&&p)
    	{
    		p=p->next;
    		j++;
   	}
   	while(j>i||p=NULL)
   	{
   		return ERROR;
   	}
   	*e=p->data;
   	return OK;
   
   } 

8. 按值查找

   //返回找到值的指针 
     Lnode *LocateElem(LinkList L,Elemtype e )
     {
     	p=L->next;
     	for(p&&p->data!=e)
     	{
     		p-p->next;
   	}
   	if(!p) return Error;
   	return p;
     }
     //返回找到值的位置序号
     int  LocateElem(LinkList,Elemtype e)
     {
     	p=L->next;
     	int j=1;
     	while(p&&p->data!=e)
     	{
     		p=p->next;
   		  j++;
   	}
   	if(!p) return 0;
   	if(p) return j;
     }

   时间复杂度：O(n)

9. 单链表中指定位置插入节点

   status InsertList(LinkList L,int i,Elemtype e)
     {
     	p=L->next;
     	int j=1;
     	while(p&&j<i-1)
   	  {
     		p=p->next;
     		j++;
   	  }
   	  if(!p||i<j) return ERROR;
   	  LinkList s;
   	  s=(LinkList)malloc(sizeof(LNode));
   	  s->data=e; 
   	  s->next=p->next;
   	  p->next=s;
   	  return OK;
     } 

   时间复杂度：O(n)

10. 单链表中删除指定位置节点

    status DeleteList(LinkList L,int i,Elemtype e)
       {
       	LinkList p,q;
       	p=L;
       	int j=0;
       	while(p->next&&j<i-1)
       	 {
       		p=p->next;
       		j++;
    	  }
       	if(!(p->next)||i=<j) return ERROR;
    	q=p->next;
    	p->next=p->next->next;
    	free(q);
    	return OK;
    	} 

    时间复杂度：O(n)

11. 建立链表——头插法

    void CreateList_H(LinkList L,int n)
    	{
    		L=(LinkList)malloc(sizeof(LNode));
    		L->next=NULL;
    		int i;
    		for(i=1;i<=n;i++)
    		{
    			p=(LinkList)malloc(sizeof(LNode));
    			scanf(&p->data);
    			p->next=L->next;
    			L->next=p;
    		}
    	 }

    时间复杂度：O(n)

12. 建立链表——尾插法

    void CreateList_T(LinkList L,int n)
       {
    	 	int i;
    	 	L=(LinkList)malloc(sizeof(LNode));
    	 	L->next=NULL;
    	 	r=L;
    	 	for(i=1;i<=n;i++)
    	 	{
    	 		p=(LinkList)malloc(sizeof(LNode));
    	 		scanf(&p->data);
    	 		p->next=NULL;
    	 		r->next=p;
    	 		r=p;	
    		}
    	} 

    时间复杂度：O(n)?

    ---

    以上就是文章的全部内容了，针对以上内容我还会继续改进和完善，希望大家能多给我提一些建议哦！