数据结构与算法 顺序表、链表总结

线性表（List）：零个或多个数据元素的有限序列。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

顺序表

1、顺序表的基本概念

概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

特点：逻辑上相邻的数据元素，物理次序也是相邻的。

链表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NpMMu49F-1678256000198)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20230301091717476.png)]

1 简介

链表概念

• 链表是一种随机存储在内存中的节点对象集合。
• 节点包含两个字段，即存储在该地址的数据和包含下一个节点地址的指针。
• 链表的最后一个节点包含指向null的指针。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VhHZYb70-1678256000199)(image/2021-03-12-21-00-33.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SclxGWqi-1678256000199)(image/2021-03-12-21-01-53.png)]

链表特点

• 链表不需要连续存在于存储器中。节点可以是存储器中的任何位置并链接在一起以形成链表。这实现了空间的优化利用。
• 链表大小仅限于内存大小，不需要提前声明。
• 空节点不能出现在链表中。
• 在单链表中存储基元类型或对象的值。

链表与数组的对比

• 数组有以下限制：

  • 在程序中使用数组之前，必须事先知道数组的大小。
  • 增加数组的大小是一个耗时的过程。在运行时几乎不可能扩展数组的大小。
  • 数组中的所有元素都需要连续存储在内存中。在数组中插入任何元素都需要移动元素之前所有的数据。

• 链表是可以克服数组所有限制的数据结构。 链表是非常有用的，因为，

  • 它动态分配内存。链表的所有节点都是非连续存储在存储器中，并使用指针链接在一起。
  • 大小调整不再是问题，因为不需要在声明时定义大小。链表根据程序的需求增长，并且仅限于可用的内存空间。

2 链表的类型

分类

• 单链表
• 双链表
• 循环单链表
• 循环双链表

链表

链式存储设计时，各个不同结点的存储空间可以不连续，但是结点内的存储单元地址则必须连续。

typedef struct LNode {int value; // value中存放结点值域，默认是int型struct Lnode *next;//指向后继结点的指针
}LNode; // 定义单链表结点类型
1234

上述定义了一个结构体，包括两部分，一是值域，二是指针域；每当定义一个结点都会产生这两个区域。
这个value与next域必须是挨着的，称这个结点为内部。

假如我们定义若干个不同的结点，把它们连接起来成为一个单链表。

value区域，箭头区域则是指针域指向逻辑上相链接的下一个结点，但是它们在空间上不一定连续。
而对于它们的结点内部一定是连续的。若第一个结点占用两个地址，那么value域的起始地址是1，则指针域的地址就是2。同理若第二个结点的value地址是10，则next域就是11。

因此，在进行链式存储设计时，各个不同结点完全可以存储在不连续的空间上，而对于同一个结点内部，不论划分多少个区域，两个也好，三个也罢，总之内部的单元存储地址是连续的

循环单向链表

1 简介

概念

• 在循环单链表中，链表的最后一个节点包含指向链表的第一个节点的指针。可以有循环单向链表以及循环双链表。
• 遍历一个循环单链表，直到到达开始的同一个节点。循环单链表类似于链表，但它没有开始也没有结束。任何节点的下一部分都不存在NULL值。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4jLx1utk-1678256055499)(image/循环单向链表.png)]

2 数据存储和实现

数据存储

链表的最后一个节点包含链表的第一个节点的地址。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sgXy3iXl-1678256055501)(image/2021-03-12-21-21-07.png)]

数据实现

• 链表通过结构体和指针实现

struct node   
{  int data;   struct node *next;  
};  
struct node *head, *ptr;   
ptr = (struct node *)malloc(sizeof(struct node *));

• C++ STL提供了链表的实现

#include<list>list<int> li;
forward_list<int> li;

3 操作

基本操作

• 创建
• 遍历、搜索
• 插入
• 删除

实现

#include<stdio.h>  
#include<stdlib.h>  
struct node
{int data;struct node *next;
};
struct node *head;void beginsert();
void lastinsert();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
int main()
{int choice = 0;while (choice != 7){printf("*********Main Menu*********\n");printf("Choose one option from the following list ...\n");printf("===============================================\n");printf("1.Insert in begining\n2.Insert at last\n");printf("3.Delete from Beginning\n4.Delete from last\n");printf("5.Search for an element\n6.Show\n7.Exit\n");printf("Enter your choice?\n");scanf("%d", &choice);switch (choice){case 1:beginsert();break;case 2:lastinsert();break;case 3:begin_delete();break;case 4:last_delete();break;case 5:search();break;case 6:display();break;case 7:exit(0);break;default:printf("Please enter valid choice..");}}
}
void beginsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW");}else{printf("Enter the node data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head)temp = temp->next;ptr->next = head;temp->next = ptr;head = ptr;}printf("node inserted\n");}}
void lastinsert()
{struct node *ptr, *temp;int item;ptr = (struct node *)malloc(sizeof(struct node));if (ptr == NULL){printf("OVERFLOW\n");}else{printf("Enter Data?");scanf("%d", &item);ptr->data = item;if (head == NULL){head = ptr;ptr->next = head;}else{temp = head;while (temp->next != head){temp = temp->next;}temp->next = ptr;ptr->next = head;}printf("node inserted\n");}}void begin_delete()
{struct node *ptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head)ptr = ptr->next;ptr->next = head->next;free(head);head = ptr->next;printf("node deleted\n");}
}
void last_delete()
{struct node *ptr, *preptr;if (head == NULL){printf("UNDERFLOW");}else if (head->next == head){head = NULL;free(head);printf("node deleted\n");}else{ptr = head;while (ptr->next != head){preptr = ptr;ptr = ptr->next;}preptr->next = ptr->next;free(ptr);printf("node deleted\n");}
}void search()
{struct node *ptr;int item, i = 0, flag = 1;ptr = head;if (ptr == NULL){printf("Empty List\n");}else{printf("Enter item which you want to search?\n");scanf("%d", &item);if (head->data == item){printf("item found at location %d", i + 1);flag = 0;}else{while (ptr->next != head){if (ptr->data == item){printf("item found at location %d ", i + 1);flag = 0;break;}else{flag = 1;}i++;ptr = ptr->next;}}if (flag != 0){printf("Item not found\n");}}}void display()
{struct node *ptr;ptr = head;if (head == NULL){printf("nothing to print");}else{printf("printing values ... \n");while (ptr->next != head){printf("%d\n", ptr->data);ptr = ptr->next;}printf("%d\n", ptr->data);}}