数据结构2——链表_在链表中有r->next=newnode->next,r=newnode

一，单链表：

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)，如果经常使用按序查找考虑使用顺序存储

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