数据结构学习笔记day007

一、单链表的基本操作

1、头插法建立单链表

• 头插法建表图示：
  
• 头插法建表代码：

LinkList List_HeadInsert (LinkList &L){
	LNode *s;
    int data;
	L = (LinkList)malloc(sizeof(LNode));	//给头结点分配空间，L头指针指向头结点
	L->next = NULL;	//头结点的下一个结点为空
	do{
        scanf("%d",&data);	//插入的数据
		s = (LNode*)malloc(sizeof(LNode));	//为插入的结点申请空间
		s->data = data;
		s->next = L->next;
		L->next = s;
	}while(data!=9999);
	return L;
}

时间复杂度为O(n)

---

2、尾插法建立单链表（借助尾指针）

• 尾插法图示：
  
• 尾插法建表代码：

LinkList List_TailInsert(LinkList &L){
	LNode *r;	//尾指针
	LNode *s;	//插入的结点
	int data;	//插入的数据
	L = (LinkList)malloc(sizeof(LNode));	//为头结点申请空间，L指向头结点
	r = L;	//尾指针指向头结点（此时头结点就是尾结点）
	do{
		scanf("%d",&data);
        s = (LNode*)malloc(sizeof(LNode));
		s->data = data;
		r->next = s;
		r = s;
	}while(data!=9999);
    r->next = NULL;
	return L;
}

时间复杂度为O(n)

---

3、单链表的查找

• 按序号查找

1. 因为链表不能像顺序表一样随机存储，所以链表按序号 查找和按值查找都需要遍历链表
2. 代码：

LNode *GetElemByIndex(LinkList L,int i){
	LNode *p = L->next;
    int j=1;
    if(i==0)
        return L;
    if(i<1)
        return NULL;
	while(p&&j<i){
        p = p->next;
        j++;
    }
	return p;
}

• 按值查找

LNode *GetElemByValue(LinkList L,ElemType e){
	LNode *p = L->next;
	while(p&&p->data!=e){
		p = p->next;
	}
	return p;
}

---

4、插入节点

• 带头结点单链表插入节点图示：
  
• 前插法和后插法的区别：

1. 前插法是插在第i个结点前面，后插法是插在第i个结点后面；
2. 前插法需要按序号查找第i-1个结点的地址，需要O(n)的时间复杂度；
3. 后插法因为已经知道了第i个结点的地址，所以不用查找第i-1个结点的地址，时间复杂度为O(1)。

• 不带头结点单链表插入结点图示：
  

---

5、删除结点

• 删除结点图示：
  
• 删除给定结点：

由于删除第p个结点需要遍历查找第p-1个结点的位置，所以时间复杂度为O(n)，所以我们可以采取先交换第 p个结点和第 p+1个结点，再删除第p+1个结点的方式（可通过第p个结点查找到第p+1个结点），这样就可以达到时间复杂度为O(1)。

• 图示：

6、求表长

• 图示：
  

---

7、判表空

1. 带头结点的单链表：

• 代码：

return head->next == NULL;

2. 不带头结点的单链表：

• 代码：

return head == NULL;

---

二、特殊链表

1、双链表

为弥补单链表不能方便查找一个结点的前驱结点的不足实现的结点，每个结点除了有一个指向直接后继的指针之外，还有一个指向直接前驱的指针。

• 图示
  
• 结点定义：

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

• 插入操作

• 图示：

• 代码：

s->next = p->next;	//s的next指向p的next
p->next->prior = s;	//p的next的prior指向s
s->prior = p;		//s的prior指向p

​ 时间复杂度为O(1)；

​ 注：在表头和表尾插入操作和在其他地方不同

• 删除操作

• 图示：

• 代码：

p->next = q->next;	//q是要删除的结点
q->next->prior = p;
free(q);

​ 时间复杂度为O(1)。

---

2、循环链表

1. 当我们只知道一个单链表的尾指针而不知道一个链表的头指针的时候，我们是没办法对一个单链表进行操作的，所以引入了循环链表的概念。循环单链表中最后一个结点的next指向了第一个结点（也就是头指针）。
2. 循环双链表，最后一个结点的next指向第一个结点，同时第一个结点的prior指向最后一个结点。

• 空表判断：

• 循环单链表：

• 图示

• 循环双链表：

• 图示

---

3、静态链表

使用数组实现链表结构，将单链表里的指针改成了数组下标。

• 图示

• 结点定义：

#define MaxSize 50
typrdef struct DNode{
	ElemType data;
	int next;
}SLinkList[MaxSize];

---

---

三、顺序表vs链表

1、存取方式

• 单链表：

只能顺序存取

寻找每个元素的地址都需要遍历

图示：

• 顺序表：

顺序存取和随机存取

只要知道第一个元素的地址就可以按照地推公式知道每个元素的地址

图示：

---

2、逻辑结构和物理结构

• 单链表

1. 逻辑结构为线性表（除第一个元素每个元素都有且仅有一个直接前驱，除了最后一个元素，每个元素都有一个直接后继），物理结构采用链式存储，所有元素都不一定相邻，而是随机存储在内存中的空位置，并且使用一个指向下一个节点的指针实现将各个数据元素链接起来；
2. 逻辑相邻物理不一定相邻，通过指针表示逻辑。

• 顺序表

1. 逻辑结构为线性表，物理结构采用顺序存储，即所有元素都存储在一片连续的内存空间里；
2. 逻辑相邻物理也相邻。

---

3、基本操作

• 顺序表

1. 插入删除元素

• 每次插入或删除都需要将操作位置之后的所有元素向后或向前移动，时间复杂度为O(n)

2. 查找

• 按值查找（无序）：遍历数组，时间复杂度为O(n)
• 按序号查找：通过数组下标直接获取，时间复杂度为O(1)

• 单链表

1. 插入删除元素

• 插入删除只需将操作位置的前驱和后继结点的指针指向改变即可，不需移动元素,时间复杂度为O(1)（结点指针已知），O(n)（结点指针未知）

2. 查找

• 按值查找：遍历单链表，时间复杂度为O(n)
• 按序号查找：同样需要遍历单链表，时间复杂度为O(n)

---

4、内存空间

• 顺序存储

无论静态分配还是非静态分配都需要 预先分配何使的内存空间，静态分配时预分配空间太大会造成浪费，太小会造成溢出，动态分配时虽不会溢出然是扩充需要移动大量元素，操作效率低

• 链式存储

在需要时分配结点空间即可，高效方便，但指针要使用额外空间

---

5、怎样选择线性表的存储结构？

• 图示：

---

6、三个常用操作

• 最值

• 顺序表

遍历数组，首先将第一个元素设置为最大值和最小值，往后遍历，若当前元素大于最大值则将最大值替换为当前元素，若当前元素小于最小值，则把最小值替换为当前元素。

• 图示

• 代码：

int min = L[0];
int max = L[0];
for(int i = 0;i < L.length;i++){
	if(min > L[i])
		min = L[i];
	if(max < L[i])
		max = L[i];
}

时间复杂度为O(n)。

• 单链表

方法与顺序表相似。

• 代码：

LNode *p = L;
int min = p->next->data;
int max = p->next->data;
while(p!=NULL){
    if(min > p->data)
        min = p->data;
    if(max < p->data)
        max = p->data;
    p = p->next;
}

时间复杂度为O(n)。

• 逆置

• 顺序表

• 代码：

int i = 0;
int j = L.length;
int temp;
while(i<j){
    temp = L[i];
    L[i] = L[j];
    L[j] = temp;
    i++;
    j--;
}

时间复杂度为O(n)；

空间复杂度为O(1)。

• 单链表

需要两个指针，指向头节点的指针p，指向尾结点的指针r。遍历链表，每次把p->next移动到r->next。

• 代码：

while(p->next != r){
    temp = p->next;
    p->next = temp->next;
    temp->next = r->next;
    r->next = temp;
}

时间复杂度为O(n)；

空间复杂度为O(1)。

• 归并

• 顺序表

同时遍历两个顺序表，每次遍历对比两个元素，将最小的那个放入归并后的顺序表。

• 代码：

int i = 0,j = 0;	//i,j用于遍历两个待归并顺序表
int k = 0;	//k用于插入归并后的顺序表
while(i < L1.length&&j < L2.length){
   if(L1[i] < L2[j])
       L[k++] = L1[i++];
   else
       L[k++] = L2[j++];
}
//将遍历剩下的元素依次插入即可
while(i < L1.length)
   L[k++] = L1[i++];
while(j < L2.length)
   L[k++] = L2[j++];

时间复杂度为O(n)；

空间复杂度为O(n)。

• 单链表

和顺序表类似。

• 代码：

while(p->next!=NULL&&q->next!=NULL){
	if(p-next->data<q->next->data){
        r->next = p->next;	//尾插法
        p->next = p->next->next;
         r= r->next;
    }
    else{
        r->next = q->next;
        q->next = q->next->next;
        r = r->next;
    }
}
if(p->next!=NULL)
    r->next = p->next;
if(q->next!=NULL)
    r->next = q->next;
free(p);
free(q);

时间复杂度为O(n);

注：单链表的归并操作不常用

L&&q->next!=NULL){

if(p-next->data<q->next->data){
    r->next = p->next;	//尾插法
    p->next = p->next->next;
     r= r->next;
}
else{
    r->next = q->next;
    q->next = q->next->next;
    r = r->next;
}

}
if(p->next!=NULL)
r->next = p->next;
if(q->next!=NULL)
r->next = q->next;
free§;
free(q);

时间复杂度为O(n);

***注：单链表的归并操作不常用***