线性表Linear List

线性表是一种典型的线性结构，是最简单且最常用的逻辑结构。

线性表是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。

数据元素的个数n定义为表的长度（n=0时称为空表）。

将非空的线性表（n＞0）记作：（a1，a2，…，an）

数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。

线性表的逻辑结构特征

对于非空的线性表:

• 有且仅有一个开始结点a1，没有直接前趋；
• 有且仅有一个终结结点an，没有直接后继；
• 其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个ai+1。

例子

学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。

英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素（结点）

一副扑克牌也是一个线性表，其中数据元素是每张牌的花色和点数

常见的线性表的基本运算

• init_list(L)：构造一个空的线性表L，即表的初始化。
• destroy_list(L)：销毁线性表L
• clear_list(L)：将线性表L清空
• empty_list(L)：判断线性表L是否为空表
• length_list(L)：求线性表L中的元素个数，即求表长。

• get_data(L, i)：取线性表L中的第i个结点，这里要求1≤i≤ListLength（L）

• locate_list(L, x)：在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。
• insert_list(L,i,x)：在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里1≤i≤n+1，而n是原表L的长度。插入后，表L的长度加1。
• delete_list(L,i)：删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1≤i≤n，而n是原表L的长度。删除后表L的长度减1。

对于实际问题中涉及的其它更为复杂的运算，可以用基本运算的组合来实现。

= 顺序表Sequential List = 采用顺序存储方式存储的线性表就称为顺序表。即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 线性表中所有结点的类型相同，每个结点所占用存储空间大小亦相同。假设表中每个结点占用len个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算： LOC(ai)=LOC(a1)+(i-1)*len 1≤i≤n 在顺序表中，每个结点的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，是一种可以随机访问的数据结构。 顺序表图示 顺序表的实现 #define MAXSIZE 100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int size; }sequence_list;

注意 用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。 存放线性表结点的向量空间的大小MAXSIZE应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。 由于C语言中向量的下标从0开始，所以若L是sequence_list类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在L.data[0]和L.Data[L.size-1]中。 若L是sequence_list类型的指针变量，则a1和an分别存储在L->data[0]和L->data[L->size-1]中。 初始化 void init_sequence_list( sequence_list * slt) { slt->size=0; }

顺序表后部进行插入操作 void insert_sequence_list(sequence_list * slt, datatype x) { if(slt->size==MAXSIZE) { printf("顺序表是满的!"); return; } slt->a[slt->size]=x; slt->size = slt->size+1; }

顺序表的遍历 void print_sequence_list (sequence_list *slt) { int i; if(slt->size == 0) printf(“顺序表是空的!\n"); else for( i=0; i < slt->size; i++) printf("%5d", slt->a[i]); }

判断顺序表是否为空 int is_empty_sequence_list ( sequence_list *slt ) { return slt->size==0; }

查找顺序表中值为x的结点位置 int find_num_sequence_list ( sequence_list *slt, datatype x) { int i=0; while( slt->a[i]!=x && i<slt->size) i++; return (i<slt->size? i:-1); } 取得顺序表中第i个结点的值 datatype get_data_pos ( sequence_list *slt, int i) { if(i < 0 || i >= slt->size){ printf( "指定位置的结点不存在!“ ); return ; } else return slt->a[i]; } 顺序表任意位置插入 顺序表任意位置插入算法 void insert_pos_sequence_list(sequence_list *slt, int position, datatype x) { int i; if(slt->size == MAXSIZE){ printf("顺序表是满的!没法插入!"); exit(1); } if(position < 0 || position > slt->size) { printf("指定的插入位置不存在!"); exit(1); } for(i = slt->size; i>position; i--) slt->a[i] = slt->a[i-1]; slt->a[position]=x; slt->size++; }

插入算法时间性能分析 平均移动元素的个数：

渐近时间复杂度：O(n) 删除顺序表中任意元素 删除算法 void delete_pos_sequence_list(sequence_list *slt, int position) { int i; if(slt->size==0) { printf("顺序表是空的!");exit(1); } if(position<0 || position >= slt->size) { printf("指定的删除位置不存在!");exit(1); } for(i=position; i<slt->size-1; i++) slt->a[i]=slt->a[i+1]; slt->size--; } 删除算法时间效率 平均移动的元素个数：

时间复杂度：O(n) 顺序表的用法 int main() { sequence_list sqlist; init_sequence_list(&sqlist); insert_sequence_list(&sqlist, 10); insert_pos_sequence_list(&sqlist, 0, 1); print_sequence_list(&sqlist); printf(“%d”, find_num_sequence_list(&sqlist, 10)); printf(“%d”, find_num_sequence_list(&sqlist, 11)); while(!is_empty_sequence_list(&sqlist)) delete_pos_sequence_list(&sqlist, sqlist.size-1); print_sequence_list(&sqlist); } 提纲 线性结构的顺序实现 线性表的顺序实现：顺序表 栈的顺序实现：顺序栈 队列的顺序实现：顺序队列和循环队列 栈Stack 栈是一种特殊的线性表。对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行。 进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。 栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。 实例： 一叠饭碗

栈的操作 init_stack(st) （顺序存储）初始化 is_empty_stack(st)判断栈（顺序存储）是否为空 print_stack(st) 打印栈（顺序存储）的结点值 get_top(st) 取得栈顶（顺序存储）结点值 push(st, x) 栈（顺序存储）的插入操作 pop(st) 栈（顺序存储）的删除操作 栈的顺序存储方式实现 栈的顺序存储方式实现又称作顺序栈 栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。 顺序栈的图示 顺序栈的实现 #define MAXSIZE 100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int top; }sequence_stack; 顺序栈的初始化 void init_stack ( sequence_stack * st ) { st->top=0; }

判断顺序栈是否空 int is_empty_stack ( sequence_stack *st ) { return st->top==0; }

获取顺序栈栈顶元素 datatype get_top(sequence_stack *st) { if (is_empty_stack(st)) { printf("栈是空的!"); exit(1); } else return st->a[st->top-1]; } 打印栈 void print_stack (sequence_stack *st) { int i; if(st->top == 0) printf(“栈是空的!"); else for( i=0; i < st->top; i++) printf("%5d", st->a[i]); } 入栈 void push(sequence_stack *st, datatype x) { if(st->top==MAXSIZE) { printf(“顺序栈已满!"); exit(1); } st->a[st->top]=x; st->top++; }

出栈 void pop(sequence_stack *st) { if(is_empty_stack(st)) { printf(“顺序栈是空的!"); exit(1); } st->top--; }

栈的应用 括号匹配 算术表达式求值 递归算法改非递归算法 括号匹配问题 设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下： ([]{}) 正确的 ([()]) 正确的 {([])} 正确的 {[(])} 不正确的 {(}[]) 不正确的

括号匹配的思路 自左向右扫描一个表达式，当遇到的开括号（或称左括号）都期待后面有一个和它对应的闭括号（或称右括号）与之匹配。我们将所遇到的开括号存放入一个栈中，等待匹配。 当遇到一个闭括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的。 如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。 括号匹配 int match_kuohao (char *c) { int i; sequence_stack s; init_stack(&s); for(i = 0; c[i]!='#’; i++) { switch (c[i]) { case '{': case '[': case '(': push(&s, c[i]); break; 括号匹配 case '}': if(!is_empty_stack(&s)&&get_top(&s)==‘{‘) { pop(&s);break; } else return 0; case ']': if(!is_empty_stack(&s)&&get_top(&s)==‘[‘) { pop(&s);break; } else return 0; case ')': if(!is_empty_stack(&s)&&get_top(&s)==‘(‘) { pop(&s);break; } else return 0; } } return is_empty_stack(&s); } 提纲 线性结构的顺序实现 线性表的顺序实现：顺序表 栈的顺序实现：顺序栈 队列的顺序实现：顺序队列和循环队列 队列Queue 队列是一种特殊的线性表，它的特殊性在于队列的插入和删除操作分别在表的两端进行。 插入的那一端称为队尾，删除的那一端称为队首。队列的插入操作和删除操作也分别简称进队和出队。 队列是具有“先进先出”（FIFO, First In First Out）特点的线性结构

实例 食堂排队买菜 队列的操作 init_queue(q)：队列初始化 is_empty_queue(q)：判断队列是否空 print_queue(q)：打印队列所有元素 get_first(q)：获得队列队首元素 insert_queue(q,x)：在队列中插入元素 delete_queue(q)：在队列中删除元素 顺序队列 队列的一种顺序实现方式

图示 顺序队列的实现 #define MAXSIZE 100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int front; int rear; }sequence_queue; 顺序队列初始化 void init_queue ( sequence_queue * sq ) { sq->front = sq->rear = 0; }

判断顺序队列是否空 int is_empty_queue (sequence_queue *sq) { return sq->front==sq->rear; }

打印顺序队列中所有元素 void print_queue(sequence_queue * sq) { int i; if( is_empty_queue(sq) ) { printf("顺序队列是空的!"); } else for(i=sq->front;i< sq->rear;i++) printf("%5d",sq->a[i]); }

获得队列的队首元素 datatype get_first(sequence_queue *sq) { if(is_empty_queue(sq)) { printf(“队列是空的”); exit(1); } return sq->a[sq->front]; } 顺序队列的入队算法 void insert_queue( sequence_queue *sq, datatype x) { int i; if(sq->rear==MAXSIZE) { printf("队列是满的!"); exit(1); } sq->a[sq->rear]=x; sq->rear = sq->rear+1; } 顺序队列的出队算法 void delete_queue(sequence_queue *sq) { if(is_empty(sq)) { printf("顺序队列是空的！"); exit(1); } sq->front++; } 循环队列 为了有效利用空间，可以将顺序存储的队列想象成环状，数组的最前和最后两个元素看作相邻的。这就是循环队列。 判断空满的条件 在（b）状态中，如果再插入一个新的结点，则数组空间将被全部占用，队列已满，且rear==front，而在（c）状态中，若删除一个结点队列成为空队列，此时也有rear==front。 判断空满的解决办法 解决办法：牺牲一个数组元素的空间 若数组的大小是MAXSIZE，则该数组所表示的循环队列最多允许存储MAXSIZE-1个结点。这样，满的条件是(rear+1)%MAXSIZE==front；空的条件是 rear==front 循环队列入队算法 void insert_queue (sequence_queue *sq, datatype x) { int i; if((sq->rear+1)%MAXSIZE==sq->front) { printf(“顺序循环队列是满的！无法入队！"); exit(1); } sq->a[sq->rear]=x; sq->rear=(sq->rear+1)%MAXSIZE; }

循环队列出队算法 void delete_queue (sequence_queue *sq) { if(is_empty_queue(sq)) { printf(“队列是空的！"); exit(1); } sq->front=(sq->front+1)%MAXSIZE; }

打印循环队列中所有元素 void print_queue(sequence_queue * sq) { int i; if( is_empty_queue(sq)) { printf("队列是空的!"); } else { for(i=sq->front; i!=sq->rear; i=(i+1)%MAXSIZE) printf("%5d", sq->a[i]); } }

队列的用法 int main() { sequence_queue queue; init_queue(&queue); insert_queue(&queue, 10); insert_queue(&queue, 11); print_queue(&queue); while(!is_empty_queue(&queue)) { printf(“%d”, get_first(queue)); delete_queue(&queue); } }