数据结构整理——线性链表

旧城等待， 2022-04-12 04:23 207阅读 0赞

# 线性表的链式表示和实现 #

## 1.线性表的链式表示 ##

总共有三种方式

> 1.线性链表  
> 2.双向链表  
> 3.循环链表

--------------------

### 1.1不同实现形式的优点 ###

#### 一、线性链表 ####

就是相当普通的链表，就不做过多的介绍。相较于数组，其存储不强调连续性，其存储的物理位置不要求紧邻。（因此不可以用上一个节点+1来表示下一节点 曾经看了好久的一个bug）有一个小技巧是你可以将这个链表的表头置为空，在在头节点之前加入元素的时候会异常方便（谁用谁知道）

#### 二、双向链表 ####

在检查每一个节点的前驱的时候如果我们按照普通的链表形式的话，只能从头开始去找，有时候会显得异常繁琐，所以这个时候就出现了双向链表，在节点的结构体中加入一个指针指向上一个节点。

#### 三、循环链表 ####

链表中最后一个节点的指针指向头节点，整个节点会形成一个环。在处理某些问题时会非常好用 (没错就是[约瑟夫环问题][Link 1])

## 2.最简单的实现形式的代码 ##

#include <stdio.h>
    #include "init.h"
    #include <stdlib.h>
    typedef int ElemType;
    typedef struct Node
    {
    	ElemType data;
    	struct Node* next;
    }Node,*pNode;
    
    typedef struct
    {
    	pNode head,tail;
    	int length;
    }LinkList;
    
    pNode GetHead(LinkList L)
    {
    	return L.head;
    }//获得链表头节点的置为
    
    pNode GetLast(LinkList L)
    {
    	return L.tail;
    }//获得尾节点
    
    pNode PriorPos(LinkList L,pNode p)
    {
    	pNode q=L.head;
    	while(q->next!=p)
    	{
    		q=q->next;
    	}
    	return q;
    }//求某个节点前驱的位置
    
    pNode NextPos(LinkList L,pNode p)
    {
    	return p->next;
    }//下一个位置
    
    Status LocatePos(LinkList L,int i,pNode &p)
    {
    	int count=0;
    	pNode q=L.head;
    	while(count<i)
    	{
    		q=q->next;
    		count++;
    	}
    	p=q;
    	return OK;
    }//定位第i个节点的位置
    
    pNode LocateElem(LinkList L,ElemType e)
    {
    	pNode p=L.head;
    	while(p)
    	{
    		if(p->data==e)
    		{
    			return p;
    		}
    		p=p->next;
    	}
    	return ERROR;
    }//获得第i个节点的位置
    
    Status MakeNode(pNode &p,ElemType e)
    {
    	p=(pNode)malloc(sizeof(ElemType));
    	if(!p)
    		return ERROR;
    	p->data=e;
    	return OK;
    }//初始化一个新的节点
    
    void FreeNode(pNode &p)
    {
    	free(p);
    	p=NULL;
    }//释放节点
    
    Status InitList(LinkList &L)
    {
    	L.length=0;
    	L.head=(pNode)malloc(sizeof(ElemType));
    	L.head=NULL;
    	L.tail=(pNode)malloc(sizeof(ElemType));
    	L.tail->next=NULL;
    	return OK;
    }//初始化队列
    
    Status DestoryList(LinkList &L)
    {
    	if(L.head==NULL)
    		return ERROR;
    	pNode p=L.head;
    	pNode q;
    	while(p)
    	{
    		q=p;
    		p=p->next;
    		FreeNode(q);
    	}
    	L.length=0;
    	return OK;
    }//摧毁一个雷诺
    
    Status ClearList(LinkList &L)
    {
    	if(L.head==NULL)
    	return ERROR;
    	pNode p=L.head->next;
    	pNode q;
    	while(p)
    	{
    		q=p;
    		p=p->next;
    		FreeNode(q);
    	}
    	L.length=0;
    	L.head->next=NULL;
    	return OK;
    }//清除队列
    
    Status InsFirst(pNode h,pNode s)
    {
    	s->next=h->next;
    	h->next=s;
    	return OK;
    }//在结点之前插入
    
    Status DelFirst(pNode h,pNode &q)
    {
    	q=h->next;
    	h->next=h->next->next;//这里我们也可以看出链表的方便之处
    	return OK;
    }//删除节点
    
    Status Append(LinkList &L,pNode s)
    {
    	L.tail->next=s;
    	int count=0;
    	while(s->next!=NULL)
    	{
    		s=s->next;
    		count++;
    	}
    	L.tail=s;
    	L.tail->next=NULL;
    	L.length+=count;
    	return OK;
    }//链接链表跟节点s
    
    Status Remove(LinkList &L,pNode &q)
    {
        pNode p;
    	p=L.head;
    	q=L.tail;
    	while(p->next!=L.tail)
    	{
    		p=p->next;
    	}
    	FreeNode(L.tail);
    	L.tail=p;
    	p->next=NULL;
    	L.length--;
    	return OK;
    }
    
    Status InsBefore(LinkList &L,pNode &p,pNode s)
    {
    	pNode q=PriorPos(L,p);
    	q->next=s;
    	p->next=s->next;
    	s->next=p;
    	L.length++;
    	return OK;
    }//节点之前插入
    
    Status InsAfter(LinkList &L,pNode &p,pNode s)
    {
    	s->next=p->next;
    	p->next=s;
    	L.length++;
    	return OK;
    }//节点之后插入
    
    Status SetCurElem(pNode &p,ElemType e)
    {
    	p->data=e;
    	return OK;
    }//更改节点中每某个节点的值
    
    Status Elem(pNode q)
    {
    	return q->data;
    }//得到该节点的值
    
    Status ListEmpty(LinkList L)
    {
    	if(L.length==0)
    	{
    		return true;
    	}
    	return false;
    }//判空
    
    int ListLength(LinkList L)
    {
    	return L.length;
    }//获得长度
    
    Status ListTraverse(LinkList L)
    {
    	pNode p=L.head;
    	while(p)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    	return OK;
    }//遍历链表
    
    Status CreatList(LinkList &L)
    {
        printf("please input the number of node:");
        int n;
        scanf("%d",&n);
        L.length+=n;
        pNode p,q;
        p=q=(pNode)malloc(sizeof(Node));
        int number;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&number);
            p->data=number;
            if(i==1)
            {
                L.head=p;
            }
            q=p;
            p=(pNode)malloc(sizeof(Node));
            q->next=p;
        }
        q->next=NULL;
        L.tail=q;
    }//创建链表
    
    int main()
    {
        LinkList L;
        InitList(L);
        CreatList(L);
        printf("%d\n",ListEmpty(L));
        ListTraverse(L);
        pNode p,q;
        MakeNode(q,3);
        MakeNode(p,4);
        InsAfter(L,p,q);
        InsBefore(L,p,q);
        ListTraverse(L);
        printf("%d\n",ListLength(L));
        SetCurElem(L.head,5);
        ListTraverse(L);
        return 0;
    }

--------------------

**略懒**只实现了第一种最简单的，日后有空再补上其他的吧

[Link 1]: https://baike.baidu.com/item/%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF/348830?fr=aladdin