线性表
定义：线性表是最基本的一种数据结构，是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中除了首元素和尾元素之外，每一个元素都有唯一的前驱和唯一的后续线性表包括顺序表和链表，其中，可以将顺序表理解为数组链表：链表由各结点组成，每个结点至少包括数据域和指针域。  在上图中的链表里，head 为头结点(一般不存放数据)，5所在结点为尾结点且其指针域为NULL
物理与逻辑
物理上连续指的是数据元素在计算机内存中的地址是连续的逻辑上连续指的是人们想象中的元素相邻
链表的定义
1、首先，定义一个节点
struct node//定义结点类型
{
int data;//数据域,存放数据
struct node *next;//指针域:该指针指向下一个node结点的地址,故其类型为struct node
};
 2、结点类型定义完成之后需要定义一个结点变量并且给它申请空间
struct node *p;//定义结点变量p(指针)
p=new node;//动态申请空间(使指针指向一个地址)
链表的创建以及输出代码
#include
#include
using namespace std;
struct node//定义链表结点类型
{
int data;//数据域,存放数据
struct node *next;//指针域:该指针指向下一个node结点的地址,故其类型为struct node
};
typedef struct node * Node;//struct node * = Node
void create(Node &head)
//创建函数
//不加&是复制了一个副本，creat函数运行完释放，加&是对同一片空间进行操作(知识点：值传递与引用)
{
Node r,p;
int x;
cin >> x;
if (head == NULL) head = new node;//如果当前head为空(头指针空),就为其申请一个结点空间;注意是node而不是Node
r = head;//head和r指针指向同一个结点
while (x != -1)//创建链表,以-1结束
{
p = new node;
p -> data = x;
p -> next = NULL;
r -> next = p;
r = p;
cin >> x;
}
}
void output(Node head)//输出链表
{
if (head == NULL)
{
cout next = p -> next -> next;//删除操作
}
else
{
Node p = get(head,i - 1);//删除第i个位置的结点,需要先找到第i - 1个结点的位置(直接调用get函数更简单)
p -> next = p -> next -> next;
}
}
插入和删除的测试代码
#include
#include
using namespace std;
struct node//定义链表结点类型
{
int data;//数据域
struct node *next;//指针域
};
typedef struct node * Node;//struct node * = Node
void create(Node &head)//创建函数
{
Node r,p;
int x;
cin >> x;
if (head == NULL) head = new node;
r = head;//head和r指针指向同一个结点
while (x != -1)//创建链表,以-1结束
{
p = new node;
p -> data = x;
p -> next = NULL;
r -> next = p;
r = p;
cin >> x;
}
}
void output(Node head)//输出链表
{
if (head == NULL)
{
cout next = s;
}
else
{
Node p = get(head,i - 1);//在第二个位置插入结点,需要先找到第一个结点的位置
s -> next = p -> next;//插入
p -> next = s;
}
}
void delNode(Node &head,int i)//删除第i个位置的结点(注意&符号)
{
if (i == 1)//(请各位试一下如果此处不特判,会怎么样)
{
Node p = head;
p -> next = p -> next -> next;//删除操作
}
else
{
Node p = get(head,i - 1);//删除第i个位置的结点,需要先找到第i - 1个结点的位置(直接调用get函数更简单)
p -> next = p -> next -> next;
}
}
int main()
{
Node head = NULL;
create(head);//1 3 4
output(head);//1 3 4
cout next = NULL;
r -> next = p;
r = p;
cin >> x;
}
}
void output(Node head)//输出链表
{
if (head == NULL)
{
cout next = s;
}
else
{
Node p = get(head,i - 1);//在第二个位置插入结点,需要先找到第一个结点的位置
s -> next = p -> next;//插入
p -> next = s;
}
}
void delNode(Node &head,int i)//删除第i个位置的结点(注意&符号)
{
if (i == 1)//(请各位试一下如果此处不特判,会怎么样)
{
Node p = head;
p -> next = p -> next -> next;//删除操作
}
else
{
Node p = get(head,i - 1);//删除第i个位置的结点,需要先找到第i - 1个结点的位置(直接调用get函数更简单)
p -> next = p -> next -> next;
}
}
void len(Node head)
{
int length = 0;
Node p = head -> next;
while (p != NULL)
{
length++;
p = p -> next;
}
cout |