删除单链上数据域值最小的节点_数据结构考研笔记（十）线性表之双链表、循环链表、静态链表、单链表和顺序表的区别以及最值、合并、逆置操作。...

文字：独木

排版：独木

图片：独木

— 往期回顾 —

数据结构考研学习笔记(二)---顺序表应用

数据结构考研学习笔记(一)—顺序表基本操作：插入 查询 删除

数据结构考研学习笔记之线性表应用题

数据结构考研笔记之线性表

数据结构考研学习笔记(九)---树、森林

线性表

• 1. 双链表

  • 1.1 插入操作

  • 1.2 删除操作

• 2. 循环链表

  • 2.1 循环单链表

  • 2.2 循环双链表

  • 2.3 循环链表判空

    • 2.3.1 循环单链表

    • 2.3.2 循环双链表

• 3. 静态链表

• 4. 顺序表与链表比较

  • 4.1 存取方式

  • 4.2 逻辑结构、物理结构

  • 4.3 基本操作

  • 4.4 内存空间

  • 总结

  • 4.5 怎样选择线性表的存储结构

  • 4.6 三个常用操作

    • 4.6.1 最值：

      • 4.6.1.1 顺序表

      • 4.6.1.2 单链表

    • 4.6.2 逆置

      • 4.6.2.1 顺序表：

      • 4.6.2.2 单链表

    • 4.6.3 合并

      • 4.6.3.1 顺序表

      • 4.6.3.2 单链表

1. 双链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

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

1.1 插入操作

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

1.2 删除操作

准备删除的结点q的后继节点赋给p的后继节点，q结点的下一个结点的前驱结点指向 p

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

2. 循环链表

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

2.1 循环单链表

2.2 循环双链表

2.3 循环链表判空

2.3.1 循环单链表

L->next == L;

2.3.2 循环双链表

L->next ==L;L->prior == L;

3. 静态链表

静态链表和单链表的区别
静态链表：把地址改成数组下标，下一个结点地址改为下一个结点的下标

#define Maxsize 50typedef struct DNode{ElemType data;int next;SLinkList[Maxsize] ;

4. 顺序表与链表比较

4.1 存取方式

单链表只能顺序存取，顺序表可以通过计算得到相应的数据元素地址从而达到随机存取。

4.2 逻辑结构、物理结构

单链表：数据元素存放位置可能相邻可能不相邻
顺序表：一定相邻

4.3 基本操作

插入：
单链表：修改指针即可
顺序表：依次向后移位
删除:
顺序表：依次向前移位
单链表：修改结点的指针
查找：
1.按值查
顺序表：依次遍历，O(n)
单链表：依次遍历，O(n)
2.按序号查：
顺序表：数组下标直接查找
单链表：依次遍历

4.4 内存空间

顺序存储：无论静态分配还是非静态都需要预先分配合适的内存空间
静态分配时预分配空间太大会造成浪费，太小会造成溢出
动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低
链式存储：在需要时分配结点空间即可，高效方便，但指针要使用额外空间

总结

4.5 怎样选择线性表的存储结构

4.6 三个常用操作

4.6.1 最值：

4.6.1.1 顺序表

顺序表:变量：min、max ，遍历数组分别与最大值最小值比较，如果比最大值大或比最小值小就替换预设变量。时间复杂度：O(n)

int min = L[O];int max = L[O];for(int i = o;i < n;i++){if(min > L[O])		min = L[O];if(max<L[O])		max = L[0];

4.6.1.2 单链表

单链表：设变量，遍历链表，时间复杂度：O(n)

int min = p-> next ->data;int max = p -> next ->data;for( ; p != NULL; p = p ->next){if(min > p ->data)		min = p ->data;if(max< p ->data)		max = p ->data;

4.6.2 逆置

4.6.2.1 顺序表：

设置标志i、j，分别放到数组的最后和最前，ij的元素交换，i向后移，j向前移。一直到j=i；时间复杂度O(n)

inti= o;int j = n-1;while(i< j){	temp =L[i];	L[i]= L[j];	L[j]= temp;}

4.6.2.2 单链表

单链表：头结点指针、尾结点指针。头结点插入尾结点，一直到r只向头结点

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

4.6.3 合并

4.6.3.1 顺序表

两个数组依次比较，最小的放入新数组，并且依次后移

int i= 0,j = O;int k = O;for( ; i<L1_Size &&j <L2_Size; k++){if(L1[i]<L2[j]		L[k]=L1[i++];else		L[k]= L2[j++];}while(i<L1_Size)	L[k++]=L1[i++];while(j<L2_Size)	L[k++]=L1[i++];

4.6.3.2 单链表

单链表：两个链表循环比较，移动指针。

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 ->nefree(p); free(a);

这里与顺序表不同，当一个链表的为空后，只需将下一个链表的指针指向新表，不需要再次循环。

End

1

发现更多精彩

关注公众号