现在复习线性表:
一、概念就不说了。
【注意】线性表的特点是:只有一个第一个数据元素,也只有一个最后一个数据元素。只有一个直接前驱,也只有一个直接后继。
二、顺序表[线性表的顺序表示]
1.用计算机里地址连续的存储单元存储。[在逻辑结构上相邻的元素,在物理结构上亦是相邻的]
地址计算公式(1)LOC(ai) = LOC(a1) + (i-1)*L [L表示一个数据元素所占字节]
(2)LOC(ai+1) = LOC(ai) + L oudin
2.顺序表的基本运算/操作
(1)插入:线性表的插入是指在第i(1<i<n+1)个元素之前插入一个新的数据元素x,使长度为n的线性表(a1,... ,ai-1,ai,ai+1 ,...,an)变成长度为n+1的线
性表(a1,...,ai-1,x,ai,ai+1,...,an), 这时需将第i至第n共(n-i+1)个数据元素后移。
实现插入操作的核心C语言代码:for(j=n;j>=i;j--)
v[j]=v[j-1];
v[j]=x;
算法的时间复杂度:T(n)=O(n);[这个可以思考一下为什么,不解释]
(2)删除:线性表的删除是指将第i(1<i<n)个元素删除,使长度为n的线性表(a1,...,ai-1,ai,ai+1,...,an)变成长度为n-1的线性表
(a1,...,ai-1,ai+1,...,an),这时需将第i+1至第n共(n-i)个数据元素前移。
核心代码:for(j=i;j<n;j++) v[j-1]=v[j];
算法的时间复杂度:T(n)=O(n);
【综述】在一个有N个元素的顺序表中插入或删除一个元素,平均需要移动N/2个元素,且具体移动的元素个数与表长和该元素在表中的位置有关;
3.顺序表的优缺点:
优点:(1)采用顺序存储方式,便于直接获得某个特定的元素
(2)操作直观
缺点:(1)操作需要移动大量元素
(2)预先分配空间需要按最大空间分配,RAM利用不充分
4.顺序表在计算机中是借助一位数组表示的。
【顺序表与数组的区别】:(1)表的长度可变,而数组的长度是不变的(一旦定义后)
(2)表中的元素是可变的(dynamic),而数组中的元素是不变的(static)
三、链表[线性表的链式表示]
1.几个概念:结点,单链表,头指针与头结点
【头结点的作用】:(1)头指针的数据域可以存储额外信息,如表的长度等
(2)设置头结点后,头指针指向头结点,不论链表是否为空,头指针总是非空,即表示的一致性。
(3)头结点使得对链表的第一个元素的操作与其他元素无异,因为都在某一结点之后,即操作上的兼容性。
2.链表的基本运算/操作
(1)查找:核心代码:p=head->next;
while(p&&p->data!=x)
p=p->next;
return(p);
算法的时间复杂度:T(n)=O(n);
(2)插入:核心代码:s=(Node*)malloc(sizeof(Node));
s->data = x;
s->next = p->next;
p->next = s; //若该语句和上一条语句次序互换,则出错
算法的时间复杂度:T(n)=O(1);
(3)删除:核心代码:if(p){
q = p->next;
p->next = q->next;
free(q); }
算法的时间复杂度:如上
(4)动态链表的建立:核心代码:head = (Node *)malloc(sizeof(Node));
head->next = NULL;
for ( i = n; i > 0; i-- ) {
p = (Node *)malloc(sizeof(Node));
p->data = a[i-1];
p->next = head->next;
head->next = p; }
return head;
3.单链表的优缺点:
优点:(1)他是一种动态存储结构,不需要预先分配空间
(2)插入,删除操作简便
缺点:(1)指针占用额外存储空间(特别当元素本身信息量很少时不划算)
(2)顺序存取数据元素(不能随机存取),查找速度慢
一、概念就不说了。
【注意】线性表的特点是:只有一个第一个数据元素,也只有一个最后一个数据元素。只有一个直接前驱,也只有一个直接后继。
二、顺序表[线性表的顺序表示]
1.用计算机里地址连续的存储单元存储。[在逻辑结构上相邻的元素,在物理结构上亦是相邻的]
地址计算公式(1)LOC(ai) = LOC(a1) + (i-1)*L [L表示一个数据元素所占字节]
(2)LOC(ai+1) = LOC(ai) + L oudin
2.顺序表的基本运算/操作
(1)插入:线性表的插入是指在第i(1<i<n+1)个元素之前插入一个新的数据元素x,使长度为n的线性表(a1,... ,ai-1,ai,ai+1 ,...,an)变成长度为n+1的线
性表(a1,...,ai-1,x,ai,ai+1,...,an), 这时需将第i至第n共(n-i+1)个数据元素后移。
实现插入操作的核心C语言代码:for(j=n;j>=i;j--)
v[j]=v[j-1];
v[j]=x;
算法的时间复杂度:T(n)=O(n);[这个可以思考一下为什么,不解释]
(2)删除:线性表的删除是指将第i(1<i<n)个元素删除,使长度为n的线性表(a1,...,ai-1,ai,ai+1,...,an)变成长度为n-1的线性表
(a1,...,ai-1,ai+1,...,an),这时需将第i+1至第n共(n-i)个数据元素前移。
核心代码:for(j=i;j<n;j++) v[j-1]=v[j];
算法的时间复杂度:T(n)=O(n);
【综述】在一个有N个元素的顺序表中插入或删除一个元素,平均需要移动N/2个元素,且具体移动的元素个数与表长和该元素在表中的位置有关;
3.顺序表的优缺点:
优点:(1)采用顺序存储方式,便于直接获得某个特定的元素
(2)操作直观
缺点:(1)操作需要移动大量元素
(2)预先分配空间需要按最大空间分配,RAM利用不充分
4.顺序表在计算机中是借助一位数组表示的。
【顺序表与数组的区别】:(1)表的长度可变,而数组的长度是不变的(一旦定义后)
(2)表中的元素是可变的(dynamic),而数组中的元素是不变的(static)
三、链表[线性表的链式表示]
1.几个概念:结点,单链表,头指针与头结点
【头结点的作用】:(1)头指针的数据域可以存储额外信息,如表的长度等
(2)设置头结点后,头指针指向头结点,不论链表是否为空,头指针总是非空,即表示的一致性。
(3)头结点使得对链表的第一个元素的操作与其他元素无异,因为都在某一结点之后,即操作上的兼容性。
2.链表的基本运算/操作
(1)查找:核心代码:p=head->next;
while(p&&p->data!=x)
p=p->next;
return(p);
算法的时间复杂度:T(n)=O(n);
(2)插入:核心代码:s=(Node*)malloc(sizeof(Node));
s->data = x;
s->next = p->next;
p->next = s; //若该语句和上一条语句次序互换,则出错
算法的时间复杂度:T(n)=O(1);
(3)删除:核心代码:if(p){
q = p->next;
p->next = q->next;
free(q); }
算法的时间复杂度:如上
(4)动态链表的建立:核心代码:head = (Node *)malloc(sizeof(Node));
head->next = NULL;
for ( i = n; i > 0; i-- ) {
p = (Node *)malloc(sizeof(Node));
p->data = a[i-1];
p->next = head->next;
head->next = p; }
return head;
3.单链表的优缺点:
优点:(1)他是一种动态存储结构,不需要预先分配空间
(2)插入,删除操作简便
缺点:(1)指针占用额外存储空间(特别当元素本身信息量很少时不划算)
(2)顺序存取数据元素(不能随机存取),查找速度慢