第三章 线性结构 线性表

1、顺序表（线性表的顺序存储结构）
#include<stdio.h> #include<stdlib.h> const int N = 1000; typedef int Position;
// 数组下标 typedef struct LNode *PtrToLNode; // PtrToLNode是结构体指针，指向结构体类型 struct
LNode // 节点表示的东西 { int Data[N]; // 数据 Position Last; // 位置 }; typedef
PtrToLNode List; List L; // 定义顺序表（线性表） //初始化 List init() { List L; L =
(List)malloc(sizeof(struct LNode)); L->Last = -1; return L; } //创建表 void
create(List L) { int n; scanf("%d",&n); L->Last = n - 1; for(int i = 0 ; i <=
L->Last ; i ++) scanf("%d",&L->Data[i]); } //查找 //last表示(n -
1),线性表的长度可以通过L->Last + 1得到 Position Find(List L, int x) // 从线性表L中找x { Position
i = 0; // 下标为i的元素可以通过L->Data[i]访问 while(i <= L->Last && L->Data[i] != x) i ++;
if(i > L->Last) return -1; else return i; // 返回下标 } //插入
//在L的指定位序i前插入一个新元素X;位序i元素的数组位置下标是i-1 bool Insert( List L, int x, int i ) {
Position j; //表满 if ( L->Last == N - 1) return false;
//检查插入位序的合法性：是否在1~n+1。n为当前元素个数，即Last+1 if ( i<1 || i>L->Last+2 ) return false;
//将位序i及以后的元素顺序向后移动 for(j = L->Last ; j >= i - 1 ; j --) L->Data[j + 1] =
L->Data[j]; L->Data[i - 1] = x; // 新元素插入第i位序，其数组下标为i-1 L->Last ++; //
使Last仍指向最后元素 return true; } // 删除元素 bool Delete( List L, int i ) { /*
从L中删除指定位序i的元素,该元素数组下标为i-1 */ Position j; //不合理 if( i < 1 || i > L->Last + 1 )
return false; //将位序i+1及以后的元素顺序向前移动 for(j = i ; j <= L->Last ; j ++) L->Data[j -
1] = L->Data[j]; L->Last --; //使Last仍指向最后元素 return true; } //输出表 void
Printf(List L) { for(int i = 0 ; i <= L->Last ; i ++) printf("%d ",L->Data[i]);
} int main() { List l; l = init(); create(l); Printf(l); return 0; }

2、单链表（线性表的链式存储结构）

写在前面：

1、指针
int a; // 定义一个整形变量a int *p; // 定义一个整型指针变量p

（1）定义：

定义一个指针，只需要在变量前面加一个*号就OK啦。

（2）作用：

存储一个地址。确切地说是存储一个内存空间的地址，比如说整型变量a的地址。严格地说这里地指针p也只能存放”一个存放整数地内存空间“的地址，因为在定义的时候我们已经限制了这一（即定义的时候*p的前面是int）。

（3）如何存储地址：
p = &a;
这样整型指针p就获得了（存储了）整型变量a的地址，我们可以形象地理解整型指针p指向了整型变量a。

2、动态分配内存函数：malloc（）

        回想一下，我们想在程序中存储一个整数10，除了使用int a；这种方式在内存中申请一块区域来存储，还有另一种动态存储方法。
malloc(4);
       
malloc函数的作用就是从内存中申请分配指定字节大小的内存空间。上面这行代码就申请了4个字节。如果你不知道int类型是4个字节的，还可以使用sizeof（int）获取int类型所占的字节数，如下：
malloc(sizeof(int));
       
哦现在你已经成功地从内存中申请了4个字节地空间来准备存放一个整数，可是如何来队这个空间操作呢？这里我们就需要用一个指针来指向这个空间，即存储这个空间的首地址。
int *p; p = (int *)malloc(sizeof(int));
        需要注意，malloc函数的放回类型的是void *类型。void *表示未确定类型的指针。在C和C++中，void
*类型可以强制转换为任何其他类型的指针。上面代码中我们将其强制转化为整型指针，以便告诉计算机这里的4个字节作为一个整体用来存放整数。还记得我们之前遗留了一个问题：指针是用来存储内存地址的，为什么要分不同类型的指针呢？因为指针变量存储的是一个内存空间的首地址（第一个字节的地址），但是这个空间占用了多少个字节，用来存储什么类型的数，则是由指针的类型来标明的。这样系统才知道应该取多少个连续内存作为一个数据。

       OK，现在我们可以通过指针p对刚才申请的4个字节的空间进行操作了，例如我们向这个空间中存入整数10，如下：
*p = 10;
       完整代码如下：
#include<bits/stdc++.h> using namespace std; int main() { int *p; // 定义一个指针p p
= (int *)malloc(sizeof(int)); // 指针p获取动态分配的内存空间地址 *p = 10; // 向指针p所指向的内存空间中存入10
printf("%d",*p); return 0; }
       
到这里你可能要问：为什么要用这么复杂的办法来存储数据呢？因为之前的方法，我们必须预先准确地知道所需变量地个数，也就是我们必须所有的变量。比如我们定义了100个整型变量，那么程序就只能存储100个整数，如果现在的实际情况是需要存储101个，那必须修改程序才可以。如果有一天你写的软件已经发布或者交付使用，却发现要存储1000个数才行，那就不得不再次修改程序，重新编译程序，发布一个新版本来代替原来的。而有了malloc函数我们便可以在程序运行的过程中根据实际情况申请空间。

3、链表的创建

     
每一个结点都由两个部分组成。左边的部分用来存放具体的数值，那么用一个整型变量就可以；右边的部分需要存储下一个结点的地址，可以用指针来实现（也称为后继指针）。

这里我们定义一个结构体类型来存储这个结点，如下：
struct node { int data; struct node *next; };

      
上面代码中，我们定义了一个叫做node的结构体类型，这个结构体类型有两个成员。第一个成员是整型data，用来存储具体的数值；第二个成员是一个指针，用来存储下一个结点的地址。因为下一个结点的类型也是struct
node，所以这个指针的类型也必须是struct node *p类型的指针。

         如何建立链表呢？首先我们需要一个头指针head指向链表的最开始。当链表还没有建立的时候头指针head为空（也可以理解为指向空结点）。
struct node *head; head = NULL; // 头指针初始为空
         现在我们来创建第一个结点，并用临时指针p指向这个结点。
struct node *p; // 定义一个临时指针 p = (struct node *)malloc(sizeof(struct node)); //
动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
         接下来分别设置新创建的第一个结点的左半部分和右半部分。
scanf("%d", &a); p -> data = a; // 将数据存储到当前结点的data域中 p -> next = NULL; //
设置当前的后继指针指向空，也就是当前结点的下一个结点为空
       下面来设置头指针并设置新创建结点的 *next指向空。头指针的作用是方便以后从头遍历整个链表。
if(head == NULL) head = p; // 如果这是第一个创建的结点，则将头指针指向这个结点 else q -> next = p; //
如果不是第一个创建的结点，则将上一个结点的后继指针，则将上一个结点的后继指针指向当前结点
         如果这是第一个创建的结点，则将头指针指向这个结点。

          如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点。

最后要将指针q也指向当前结点，因为待会儿临时指针p将会指向新创建的结点

完整代码如下：
#include<bits/stdc++.h> using namespace std; // 这里创建一个结构体用来表示链表的结点类型 struct
node { int data; struct node *next; }; int main() { int n; scanf("%d",&n);
struct node *head; head = NULL; // 头指针初试为空,代表还没建表 for(int i = 1 ; i <= n ; i
++) { int a; scanf("%d",&a); struct node *q; struct node *p; // 定义临时指针p p =
(struct node *)malloc(sizeof(struct node)); // 动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p -> data = a; p -> next = NULL; // 设置当前结点的后继指针指向空，也就是当前的下一个结点为空 if(head ==
NULL) // 头指针是初试状态，代表还没建结点 { head = p; // 如果这是第一个创建的结点，则将头指针指向这个结点 } else { q ->
next = p; // 如果不是第一个创建的结点，则将上一个结点的后继指针指向结点 } q = p; // q也指向当前结点，因为临时指针p会往后移动 }
// 输出链表的所有数 struct node *t; t = head; while(t != NULL) { printf("%d ",t ->
data); t = t -> next; } return 0; } //输入8 1 2 3 4 5 7 8 9 //输出 1 2 3 4 5 7 8 9

建表的方式：

（1）头插法建表：

代码：
#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int a[N];
int n; // 元素数量 typedef struct LNode *PtrToLNode; struct LNode { int data;
PtrToLNode next; }; typedef PtrToLNode Position; // 这里的位置是结点的地址 typedef
PtrToLNode List; // 头插法建表 List CreateFromHead() { List L; Position s; // 临时指针s
L = (List)malloc(sizeof(struct LNode)); // 头指针L指向一块结点空间（头节点） L -> next = NULL;
scanf("%d",&n); for(int i = 0 ; i < n ; i ++) { s = (PtrToLNode)malloc(sizeof
(struct LNode)); scanf("%d",&a[i]); s -> data = a[i]; s -> next = L -> next; L
-> next = s; } return L; } int lengthL(List L) { Position p; int cnt = 0; //
计数器 p = L -> next; // 头节点不存数据，算第0个结点，从第一个结点开始算 while(p != NULL) { p = p ->
next; cnt ++; // 当前p指向的是第cnt个结点 } return cnt; } // 输出链表 void printfL(List L) {
Position p; p = L -> next; // 头结点不存数据，从第一个结点开始遍历，头节点是相当于是第0个结点 while(p != NULL)
{ printf("%d ",p -> data); p = p -> next; } } int main() { List l; //
可以用List定义具体的表头结点指针，该指针就代表了一个链式表 // 建表 l = CreateFromHead(); // 输出表的长度 int len =
lengthL(l); printf("%d\n",len); // 输出刚刚建的表 printfL(l); return 0; }
运行结果：

（2）正向建表（尾插法，下面有注释，能懂）

代码：
#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int a[N];
int n; // 元素数量 typedef struct LNode *PtrToLNode; struct LNode { int data;
PtrToLNode next; }; typedef PtrToLNode Position; // 这里的位置是结点的地址 typedef
PtrToLNode List; // 头插法建表 List CreateFromHead() { List L; Position s; // 临时指针s
L = (List)malloc(sizeof(struct LNode)); // 头指针L指向一块结点空间（头节点） L -> next = NULL;
scanf("%d",&n); for(int i = 0 ; i < n ; i ++) { s = (PtrToLNode)malloc(sizeof
(struct LNode)); scanf("%d",&a[i]); s -> data = a[i]; s -> next = L -> next; L
-> next = s; } return L; } // 尾插法建表 List CreateFromTail() /*尾插法建表*/ { List L;
Position r,s; char c; int flag = 1; // 输入结束标志 L =
(List)malloc(sizeof(LNode));//为头结点分配存储空间 L->next = NULL; r = L;
//r指针始终动态指向链表的当前表尾，尾插法插入很方便，只需要修改一个指针 printf("请输入数字，以-1结束：\n"); while(flag ==
1) //flag为标志，初值为1。输入“$”时flag为0，建表结束 { int x; scanf("%d",&x); if(x != -1) { s =
(PtrToLNode)malloc(sizeof(LNode)); s->data = x; r->next = s; // 尾插法只需要修改一个指针 r
= s; // 更新尾结点，为下一次插入做准备 } else { flag = 0; r->next = NULL; } } return L; } int
lengthL(List L) { Position p; int cnt = 0; // 计数器 p = L -> next; //
头节点不存数据，算第0个结点，从第一个结点开始算 while(p != NULL) { p = p -> next; cnt ++; //
当前p指向的是第cnt个结点 } return cnt; } // 输出链表 void printfL(List L) { Position p; p = L
-> next; // 头结点不存数据，从第一个结点开始遍历，头节点是相当于是第0个结点 while(p != NULL) { printf("%d ",p
-> data); p = p -> next; } } int main() { List l; //
可以用List定义具体的表头结点指针，该指针就代表了一个链式表 // 建表 l = CreateFromTail(); // 输出表的长度 int len =
lengthL(l); printf("%d\n",len); // 输出刚刚建的表 printfL(l); return 0; }

       

• « 上一篇：30 个 DevOps 面试问题和答案
• » 下一篇：开发一个系统软件开发大概需要多少资金钱呢