数据结构2——链表

太过爱你忘了你带给我的痛 2023-02-24 11:25 15阅读 0赞

### 一，单链表： ###

1，为什么引入链表？

由于顺序表的插入，删除需要移动大量的元素，影响了运行效率。因此引入了线性表链式存储。逻辑上相邻的元素不要求物理地址也相邻，通过链来建立数据元素之间的关系

2，链表的定义

typedef int Elemtype;
    typedef struct LNode{
        Elemtype data;//存储本节点的数据 
        struct LNode *next;//存储下一个节点的地址 
    }LNode,*LinkList;//结构体的变量

3，链表头插入法解读

LinkList CreatList_H(LinkList &L){
        LNode *s;
        int x;
        L = (LinkList)malloc(sizeof(LNode));//创建初始头节点
        L->next=NULL;//L->的形式调用结构体成员，因为L是指针类型，当然也可以(*L).next进行调用，这是把*L看成变量 
        scanf("%d",&x);
        while(x!=9999){//输入9999表示停止输入 
            s=(LNode*)malloc(sizeof(LNode));//创建新节点 
            s->data=x;//为节点赋值 
            s->next=L->next;//将节点插入链表，L为头指针 
            L->next=s;
            scanf("%d",&x);
        }
        return L;
    }

4，链表尾插入法解读

LinkList CreatList_R(LinkList &L){
        int x;
        L = (LinkList)malloc(sizeof(LNode));//创建初始头节点
        LNode *s,*r=L;//r是表尾指针 
        scanf("%d",&x);
        while(x!=9999){//输入9999表示停止输入 
            s=(LNode*)malloc(sizeof(LNode));
            s->data=x;
            r->next=s;//将s插到链表尾指针r的后面 
            r=s;//r是一个暂时存放尾指针的变量，将新链表的尾指针地址s存到r上 
            scanf("%d",&x);
        } 
        r->next=NULL;
        return L;
    }

5，按顺序查找第i个节点

LNode *GetElem(LinkList &L,int i){
    	int j=1;//用来计数
    	LNode *p=L->next;
    	if(i==0)//返回头节点 
    	return L;
    	if(i<1)//i无效，返回NULL 
    		return NULL;
    	while(p&&j<i){//当前节点的指针域不为空，说明有下个节点。并且j<i时执行 
    		p=p->next;//当j=i-1时，p存储的是i节点的地址 
    		j++;
    	}
    	return p;
    }

6，按值查找节点

LNode *GetElem2(LinlList &L,Elemtype value){
    	LNode *p=L->next;//p为头结点 
    	while(p){//下一个节点存在
    	 	if(p->data==value )
    	 		return p
    	 	else
    			p=p->next;//遍历下一节点 
    	}
    	return NULL;
    }

7，在链表pos插入节点value

bool Insert_Front(LinkList &L,int pos,Elemtype value){
    	LNode *p=GetElem(L,pos-1);//获取到pos的前一个节点
    	if(p==NULL){//如果插入位置的前一节点不存在。 
    		printf("插入位置不合法");
    		return false; 
    	}
    	LNode *newNode=(LNode*)malloc(sizeof(LNode));//为新节点分配存储空间 
    	newNode->data=value;//为新节点赋值 
    	newNode->next=p->next;//插入到链表中 
    	p->next=newNode;
    	return true;
    }

8，删除pos位置的值

bool Delete_Node(LinkList &L,int pos){
    	LNode *p=GetElem(L,pos-1);//获取到pos的前一个节点
    	LNode *q=p->next;//待删除的节点 
    	if(p==NULL){//如果插入位置的前一节点不存在。 
    		printf("待删除的节点位置不存在");
    		return false; 
    	}
    	p->next=q->next;
    	free(q);
    	printf("删除成功\n"); 
    	return true;
    }

9，求表长

int length(LinkList &L){
    	LNode *p=L->next;
    	int length=0; 
    	while(p){
    		length++;
    		p=p->next;
    	}
    	printf("表长为%d\n",length);
    	return length;
    	 
    }

二，双链表

1，为什么要引入双链表？

因为单链表中，只有后继节点的指针，这使单链表只能只能从头节点依次遍历链表。当我们需要访问某个节点的前驱节点时，就只能从头遍历，很不方便。这样访问后继节点的时间复杂度为O(1)，访问前驱节点的时间复杂度为O(n)。为了克服这个缺点我们在结构体中再加入前驱节点的指针域，这就是双链表

优势：

*  插入删除不需要移动元素外，可以原地插入删除
 *  可以双向遍历

2，双链表定义

typedef struct Dnode{
    	Elemtype data;
    	struct Dnode *prior,*next;
    }DNode,*DLinkList;

3，在p后插入s操作的核心

s->next=p->next;
    p->next-prior=s;
    p->next=s;
    s->prior=p;

4，删除p后面的q操作的核心

p->next=q->next;
    q->next->prior=p;
    free(q);

### 三，顺序表和链表的比较： ###

1，存取方式：

顺序表可以顺序存取，也可以随机存取。链表只能从表头顺序存取元素

2，逻辑结构与物理结构：

采用顺序存储，逻辑上相邻的元素，物理存储位置也相邻。链表存储，逻辑上相邻的元素，物理存储位置不一定相邻。

3，查找，插入和删除操作

*  查找：按值查找，当顺序表无序时，顺序表的查找与链表的查找时间复杂度都为O(n)。当顺序表有序时，可以采用折半查找，时间复杂度为O(log2n）。如果是按序号查找顺序表的时间复杂度为O(1)，链表的时间复杂度为O(n)。
 *  插入删除：顺序表需要移动半个表长的元素，链表只需修改相邻节点的指针域即可。

4，空间分配：

*  链表因为每个节点需要带有指针域，所以占用的存储空间大于顺讯存储的
 *  顺序存储在静态分配的情况下，一旦存储空间满了会发生溢出，为防止溢出分配大空间会造成浪费。动态分配情况下可以实现存储空间的扩充，但需要移动大量的元素，导致操作效率降低，如果内存中无大块的连续存储空间可能导致分配失败。链式存储只在需要的时候进行分配内存，操作灵活，高效。

### 四，实际应用过程中如何选取存储结构？ ###

1，基于存储考虑：

当线性表长度或者存储规模难以估计时，采用链表

2，基于运算考虑：

按序查找，顺序表时间复杂度为O(1)，链表为O(n)，如果经常使用按序查找考虑使用顺序存储

当数据元素的信息量很大时，又会频繁地对表进行插入，删除操作，因为顺序存储平均需要移动半个表的元素，因此考虑使用链表