数据结构：第2讲：线性表-编程实验室

1.线性表的定义和特点

（1）定义：
由 n（n>=0）个数据特性相同的元素构成的有限序列（有限即数量有限，序列理解为集合），称为线性表。

（2）特点：
线性表中元素的个数 n（n>=0）定义为线性表的长度，当 n=0 时称之为空表。对于非空的线性表，其特点是：

存在唯一的一个被称作“第一个”的数据元素。
存在唯一的一个被称作“最后一个”的数据元素。
除第一个元素之外，结构中的每个数据元素均只有一个前驱（前一个元素叫前驱）。
除最后一个元素外，结构中的每个数据元素均只有一个后继（后一个元素）。

2.顺序表

（1）定义：
用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。

（2）存储结构：

简单来说，该结构体里有一个数组，还有一个 length，length 的值为几，就说明数组中有几个元素。

（3）初始化：

数组不需要去初始化，因为只要写了，就已经在内存中开辟了100个位置的连续空间了，故数组默认已经有了，只用对 length 初始化。

（4）在尾部添加元素

（5）遍历

（6）插入元素

intinsertElem(Seqlist*L,intpos,ElemType e)//pos 是位置，不是数组下标{if(L->length>=MAXSIZE){printf("表已经满了\n");return0;}if(pos<1||pos>L->length){printf("插入位置错误\n");return0;}if(pos<=L->length){for(inti=L->length-1;i>=pos-1;i--){L->data[i+1]=L->data[i];}L->data[pos-1]=e;L->length++;}return1;}

注：
往第一个位置插需要 n 次，往最后一个位置插需要 1 次。所以顺序表插入数据的最好时间复杂度是 O(1)，最坏时间复杂度是 O(n)。

（7）删除元素

本质是覆盖。

ElemType *e 的作用是用来储存被删除的数据，便于后续观察。

（8）查找（在当前顺序表中查找有没有自己想要的元素）

（9）动态分配内存地址初始化

3.链表

（1）链表存储结构的特点：
用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

（2）

（3）存储结构：

注：顺序表是有一个结构体能完整的表示一个顺序表，而链表是用一个结构体来表达一个节点。

（4）单链表（单一方向的链表）

单链表的初始化

单链表的初始化是去创建一个头节点。

注：头节点（不存有效数据的头节点）不算链表的有效节点，真正链表从 head -> next 开始，所以 head ->next 的位置才是1。

头插法

每一次插入新数据的时候，都把新数据放在头节点的后面。所以头插法的插入顺序和 printf 输出的排列顺序是相反的。

L 是头节点，也可以说是一条链表。

遍历

尾插法

要先获得尾节点地址：

再进行尾插法：

在指定位置插入数据

要先把 70 的 next 赋值给 new 的 next，再把 new 的地址赋值给 70 的 next。new 插入后的位置是 2，不是 3。

删除节点

找到要删除节点的前置节点 p，用指针 q 记录要删除的节点，通过改变 p 的后继节点来实现删除，释放被删除节点的空间。

intdeleteNode(Node*L,intpos){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}if(p->next==NULL){printf("要删除的位置错误\n");return0;}Node*q=p->next;p->next=q->next;free(q);return1;}

获取链表长度

该长度包括了头节点。

释放链表

除了头节点以外的所有节点，都要给它删除掉。

思路：让指针 p 指向头节点后的第一个节点，判断指针 p 是否指向空节点，如果 p 不为空，用指针 q 记录指针 p 的后继节点，然后释放指针 p 指向的节点，把指针 q 赋值给指针 q ，让指针 p 和指针 q 指向同一节点，循环上面操作，最后再把头节点的 next 置空。

4.线性表的应用

（1）单链表应用1

①思路（快慢指针）：

假设要找倒数第三个节点。

声明两个指针，都指向头节点后的这个节点。

因为要找倒数第三个节点，所以让快指针先走三步。

快慢指针同时走，快指针指向空的时候，慢指针就找到了倒数第三个节点。

②代码实现

intfindNodeFS(Node*L,intk){for(inti=0;i<k;i++){fast=fast->next;}while(fast!=NULL){fast=fast->next;slow=slow->next;}printf("倒数第%d个节点值为：%d\n",k,slow->data);return1;}

（2）单链表应用2

①思路：

先分别求出两条链表的长度 m 和 n。
fast 指针指向较长的链表，先走 m-n 或 n-m 步。

同步移动指针，判断它们是否指向同一个节点。

②代码实现

Node*findIntersectionNode(Node*headA,Node*headB){if(headA==NULL||headB==NULL){returnNULL;}Node*p=headA;intlenA=0;intlenB=0;while(p!=NULL){p=p->next;lenA++;}p=headB;while(p!=NULL){p=p->next;lenB++;}Node*m;Node*n;intstep;if(lenA>lenB){step=lenA-lenB;m=headA;n=headB;}else{step=lenB-lenA;m=headB;n=headA;}for(inti=0;i<step;i++){m=m->next;}while(m!=n){m=m->next;n=n->next;}returnm;}

（3）单链表应用3

①思路：

找到链表中绝对值最大的数，假如是21，然后创建一个长度为22的数组（保证数组下标有21），并将数组中每个元素置0。

开始去遍历链表，先拿到了21，然后把21当成下标，将数组下标为21的元素置1。同理，遇到-15，将数组下标为15的元素置1。
又遇到了-15，去找数组下标为15的元素，发现不是0而是1，说明之前已经见过绝对值为15的值了，将此节点删除，并释放内存。
后面同理。

②代码实现

voidremoveNode(Node*L,intn)//L是头节点，n是链表中绝对值最大的数的绝对值{NOde*p=L;intindex;int*q=(int*)malloc(sizeof(int)*(n+1));for(inti=0;i<n+1;i++){*(q+i)=0;}while(p->next!=NULL){index=abs(p->next->data);if(*(q+index)==0){*(q+index)=1;p=p->next;}else{Node*temp=p->next;p->next=temp->next;free(temp);}}free(q);}

（4）单链表应用4

反转链表

①思路：

先准备三个指针

把 first 赋值给 second 的 next

把三个指针往后挪，即把second赋值给first，把third赋值给second，并将third指向second的next。

再将first赋值给second的next。

后面同理，直到second指向NULL，循环结束。

最后再加个头节点。

②代码实现

Node*reverseList(Node*head){Node*first=NULL;Node*second=head->next;Node*third;while(second!=NULL){third=second->next;second->next=first;first=second;second=third;}Node*hd=initList();hd->next=first;returnhd;}

该代码与上面思路略有不同，把 third 往后走一步放到了循环的最前面。

（5）单链表应用5

删除链表中间节点

①思路：

利用快慢指针

让快指针指向1，慢指针指向头节点。

每次让慢指针走一步，快指针走两步。即可找到中间节点的前驱节点，即可删除中间节点。

②代码实现

intdelMiddleNode(Node*head){Node*fast=head->next;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}Node*q=slow->next;slow->next=q->next;free(q);return1;}

（6）单链表应用6

①思路：

将456翻转

见缝插针

q1放p1后面，q2放p2后面，以此类推。

②代码实现

voidreOrderList(Node*head){Node*fast=head->next;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;}Node*first=NULL;Node*second=slow->next;slow->next=NULL;Node*third=NULL;while(second!=NULL){third=second->next;second->next=first;first=second;second=third;}Node*p1=head->next;Node*q1=first;Node*p2,q2;while(p1!=NULL&&q1!=NULL){p2=p1->next;q2=q1->next;p1->next=q1;q1->next=p2;p1=p2;q1=q2;}}

5.单向循环链表

（1）特点：

表中最后一个节点的指针域指向头节点，整个链表形成一个环。

6.判断链表是否有环

（1）判断是否有环
①题目意思解析：

比如此链表，写出一个程序判断该链表是否有环（不一定是循环链表，头尾相连）。

②思路：

利用快慢指针

快指针每次比慢指针多走一步，如果链表中有环，则二者一定会相遇（生活中的例子：两人在操场跑圈，只要一个人始终比另一个人跑的快，则两人一定会相遇）。

③代码实现

intisCycle(Node*head){Node*fast=head;Node*slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow){return1;}}return0;}

7.双向链表

（1）在双向链表的节点中有两个指针域，一个直接指向后继，另一个直接指向前驱。

（2）组成：

（3）初始化：

Node*initList(){Node*head=(Node*)malloc(sizeof(Node));head->data=0;head->prev=NULL;head->next=NULL;returnhead;}

（4）头插法：

intinsertHead(Node*L,ElemType e){Node*p=(Node*)malloc(sizeof(Node));p->data=e;p->prev=L;p->next=L->next;if(L->next!=NULL){L->next->prev=p;}L->next=p;return1;}

（5）尾插法：

Node*insertTail(Node*tail,ElemType e){Node*p=(Node*)malloc(sizeof(Node));p->data=e;p->prev=tail;tail->next=p;p->next=NULL;returnp;}

注：使用尾插法要先获得尾部节点：

Node*get_tail(Node*L){Node*p=L;while(p->next!=NULL){p=p->next;}returnp;}

（6）指定位置插入：

intinsertNode(Node*L,intpos,ElemType e){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}Node*q=(Node*)malloc(sizeof(Node));q->prev=p;q->next=p->next;p->next->prev=q;p->next=q;return1;}

（7）删除节点：

intdeletNode(Node*L,intpos){Node*p=L;inti=0;while(i<pos-1){p=p->next;i++;if(p==NULL){return0;}}if(p->next==NULL){printf("要删除的位置错误\n");return0;}Node*q=p->next;p->next=q->next;q->next->prev=p;free(q);return1;}