版本2和27间的区别 (跳过第25版)
于2006-02-22 21:08:22修订的的版本2
大小: 13709
编辑: czk
备注:
于2006-06-18 18:20:44修订的的版本27
大小: 10511
编辑: czk
备注:
删除的内容标记成这样。 加入的内容标记成这样。
行号 1: 行号 1:
线性表Linear List
线性表是一种典型的线性结构,是最简单且最常用的逻辑结构。
线性表是由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。
数据元素的个数n定义为表的长度(n=0时称为空表)。
将非空的线性表(n>0)记作:(a1,a2,…,an)
数据元素ai(1≤i≤n)只是个抽象符号,其具体含义在不同情况下可以不同。

线性表的逻辑结构特征
对于非空的线性表:
有且仅有一个开始结点a1,没有直接前趋,有且仅有一个直接后继a2
有且仅有一个终结结点an,没有直接后继,有且仅有一个直接前趋an-1
其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个ai+1。
例子
学生成绩表中,每个学生及其成绩是一个数据元素,其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。
英文字母表(A,B,…,Z)是线性表,表中每个字母是一个数据元素(结点)
一副扑克牌的点数(2,3,…,10,J,Q,K,A)也是一个线性表,其中数据元素是每张牌的点数
常见的线性表的基本运算
init_sequence_lis
t(L):构造一个空的线性表L,即表的初始化。
length_sequence_list(L):求线性表L中的结点个数,即求表长。
get_data_pos(L, i):取线性表L中的第i个结点,这里要求1≤i≤ListLength(L)
find_num_sequen
ce_list(L, x):在L中查找值为x 的结点,并返回该结点在L中的位置。若L中有多个结点的值和x 相同,则返回首次找到的结点位置;若L中没有结点的值为x ,则返回一个特殊值表示查找失败。
insert_pos_sequence_list(L,x,i):在线性表L的第i个位置上插入一个值为x 的新结点,使得原编号为i,i+1,…,n的结点变为编号为i+1,i+2,…,n+1的结点。这里1≤i≤n+1,而n是原表L的长度。插入后,表L的长度加1。
delete_p
os_sequence_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的线性函数。只要知道基地址和每个结点的大小,就可在相同时间内求出任一结点的存储地址,是一种可以随机访问的数据结构。
顺序表图示
顺序表实现
[[TableOfContents]]

== 线性表逻辑结构 ==

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

  
线性表是由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)是线性表,表中每个字母是一个数据元素(结点)
 * 一副扑克牌也是一个线性表,其中数据元素是每张牌的花色和点数

==
线性表的基本运算 ==
 * ini
t(L):构造一个空的线性表L,即表的初始化。
 * destroy(L):销毁线性表L
 * clear(L):将线性表L清空
 * is_empty(L):判断线性表L是否为空表
 *
length(L):求线性表L中的元素个数,即求表长。
 * get_data(L, i):取线性表L中的第i个结点,这里要求[[latex($$1\le i \le length\_ list(L)$$)]]
 * lo
cate(L, x):在L中查找值为x 的结点,并返回该结点在L中的位置。若L中有多个结点的值和x 相同,则返回首次找到的结点位置;若L中没有结点的值为x ,则返回一个特殊值表示查找失败。   * insert(L,i,x):在线性表L的第i个位置上插入一个值为x 的新结点,使得原编号为i,i+1,…,n的结点变为编号为i+1,i+2,…,n+1的结点。这里1≤i≤n+1,而n是原表L的长度。插入后,表L的长度加1。   * remove(L,i):删除线性表L的第i个结点,使得原编号为i+1,i+2,…,n的结点变成编号为i,i+1,…,n-1的结点。这里[[latex($$1\le i \le n$$)]],而n是原表L的长度。删除后表L的长度减1。 
对于实际问题中涉及的其它更为复杂的运算,可以用基本运算的组合来实现。   == 线性表的顺序存储(顺序表 Sequential List) ==

=== 顺序表的存储结构 ===
   
采用顺序存储方式存储的线性表就称为顺序表。

   
即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。      线性表中所有结点的类型相同,每个结点所占用存储空间大小亦相同。

   
假设表中每个结点占用len个存储单元,其中第一个单元的存储地址则是该结点的存储地址,并设表中开始结点a1的存储地址(简称为基地址)是loc(a1),那么结点ai的存储地址loc(ai)可通过下式计算:[[latex($$loc(a_i)=loc(a_1)+(i-1)\times len,1\le i \le n$$)]]

   
在顺序表中,每个结点的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小,就可在相同时间内求出任一结点的存储地址,是一种可以随机访问的数据结构。      顺序表图示

   
顺序表用固定长度的数组实现
{{{#!cplusplus
行号 33: 行号 55:
typedef int datatype; typedef int elem_type;
行号 35: 行号 57:
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++;
}
    elem_type elem[MAXSIZE];
    int size; //表示数组中元素个数
}seq_list;
}}}
   elem_type是为了描述统一而自定义的,实际使用中,可以定义为需要的类型。

   由于C语言中数组的下标从0开始,所以线性表的开始结点a1在线性表中的序号为1,对应的数组下标为0,ai在线性表中的序号为i,对应的数组下标为i-1。

   除了用数组存储线性表的元素外,顺序表还需要用一个变量来表示线性表的长度属性或者最后一个元素的位置,因此用结构类型来定义顺序表类型。

   存放线性表结点的数组空间的大小MAXSIZE应仔细选值,使其既能满足表结点的数目动态增加的需求,又不致于预先定义过大而浪费存储空间。

=== 初始化 ===
{{{#!cplusplus
void init( seq_list * slt) {
    slt->size=0;
}
}}}

=== 遍历 ===
{{{#!cplusplus
void print(seq_list *slt)
{
   int i;
   for( i=0; i < slt->size; i++)
        printf("%5d", slt->elem[i]);
}
}}}

=== 判断是否为空 ===
{{{#!cplusplus
int is_empty( seq_list *slt ) {
     return slt->size==0;
}
}}}
=== 查找值为x的结点位置 ===
{{{#!cplusplus
int locate(seq_list *slt, elem_type x)
{
    int i=0;
    while(i < slt->size && slt->elem[i]!=x)
        i++;
    return i<=slt->last? i+1:-1;
}
}}}

=== 取得第i个结点的值 ===
{{{#!cplusplus
elem_type get_data(seq_list *slt, int position) {
    return slt->elem[position-1];
}}}
=== 任意位置插入 ===
{{{#!cplusplus
void insert(seq_list *slt, int position, elem_type x) {
    int i;
    position--;
    for(i = slt->size; i > position; i--)
        slt->elem[i] = slt->elem[i-1];
    slt->elem[position]=x;
    slt->size++;
}
}}}
行号 112: 行号 121:
平均移动元素的个数:



渐近时间复杂度: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--;
}

=== 任意位置
元素删除 ===
{{{
void remove(seq_list *slt, int position) {
    int i;
    position--;
    for(i=position; i<slt->size-1; i++) 
        slt->elem[i]=slt->elem[i+1];
    slt->size--;
}
}}}
行号 132: 行号 134:
平均移动的元素个数:



时间复杂度:O(n)
顺序表的用法

=== 顺序表的用法举例 ===
{{{
行号 139: 行号 138:
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);
}
}
    seq_list sqlist;
    init_list(&sqlist);
    insert_list(&sqlist, 1, 1);
    print_list(&sqlist);
    printf("%d", locate_list(&sqlist, 10));
    printf("%d", locate_list(&sqlist, 11));
    while(!empty_list(&sqlist))
        delete_list(&sqlist, sqlist.size);
    print_list(&sqlist);
}
}}}

== 线性表的链式存储(带头结点的单链表) ==

=== 链表的存储结构 ===

   数据结构的存储方式必须体现它的逻辑关系。在链式存储方式下,除存放一个结点的信息外,还需附设指针,用指针体现结点之间的逻辑关系。

   如果一个结点有多个后继或多个前驱,那么可以附设相应个数的指针,一个结点附设的指针指向的是这个结点的某个前驱或后继。

   线性结构的链式存储被称为链表。链表中可以只附设一个指针指向它的后继结点的存放位置;也可以设两个指针,一个指向前驱一个指向后继。

   单链表是线性表链式存储的一种形式。其中的结点一般含有两个域,一个是存放数据信息的域,另一个是存放该结点的后继结点的地址的指针域。一个单链表必须有一个首指针指向单链表中的第一个结点。

   带头节点的单链表存储结构:普通单链表的缺点:特殊情况太多,处理起来太麻烦

   改进办法:增设头结点,头结点不存放任何数据

   单链表存储结构实现
{{{#!cplusplus
typedef int elem_type;
struct node{
   elem_type data;
   struct node *next;
};
typedef struct node node;
typedef struct node *link_list;
}}}

=== 初始化 ===
{{{#!cplusplus
void init(link_list *list) {
   *list = (link_list)malloc(sizeof(node));
   (*list)->next = NULL;
}
}}}

=== 插入 ===
基本插入算法
{{{#!cplusplus
void insert(node *q, elem_type x)
{
   p = (node*)malloc(sizeof(node));
   p->data = x;
   p->next = q->next;
   q->next = p;
}
}}}

插入特定位置
{{{#!cplusplus
void insert_pos(link_list node, int pos, elem_type x)
{
   while(pos > 1) {
        node = node->next;
        pos--;
   }
   insert(node, x);
}
}}}
=== 删除 ===
基本删除算法
{{{#!cplusplus
void remove(node *pre)
{
   node *p = pre->next;
   pre->next=p->next;
   free(p);
}
}}}
删除特定位置元素算法
{{{#!cplusplus
void remove_pos(Node *node, int pos)
{
   while(pos > 1) {
      node = node->next;
      pos--;
   }
   remove(head);
}
}}}
删除特定值的元素算法
{{{#!cplusplus
void remove_x(node *head, elem_type x)
{
   node *pre = head;
   while(pre->next!= NULL &&
      pre->next->data != x)
   {
      pre=pre->next;
   }
   remove(pre);
}
}}}
=== 查找算法 ===
{{{#!cplusplus
node *get_data(node *head, int pos)
{
   while(pos > 0) {
      head = head->next;
      pos--;
   }
   return head;
}
}}}

{{{#!cplusplus
node *find_x(node *head, elem_type x)
{
   head = head->next;
   while(head!=NULL && head->data != x)
   {
      head=head->next;
   }
   return head;
}
}}}
=== 思考 ===
如何实现:
 * 打印链表的每一个元素的值
 * 求链表的长度
 * 合并两个有序的单链表,使他们依然有序

== 不带头结点的单链表 ==

   不设开始的头结点,head指针直接指向第一个元素。

   插入、删除操作比较繁琐

== 循环单链表 ==

   如果希望从表中的任意一个结点开始,都能访问到表中的所有其它结点,可以设置表中最后一个结点的指针域指向表中的第一个结点,这种链表称为循环单链表(或单循环链表)

=== 循环单链表与单链表的不同 ===

 * 单链表中某个结点p是表中最后一个结点的特征是p->next==NULL。
 * 对于循环单链表,若首指针为head,表中的某个结点p是最后一个结点的特征应该是p->next==head。
 * 判断单链表为空的条件是head->next==NULL
 * 判断循环单链表为空的条件是head->next == head

=== 循环单链表插入 ===

=== 循环单链表的删除 ===

=== 只设尾指针的循环单链表 ===

在循环单链表中,常常只设一个尾指针不设头指针。

=== 例子:合并两个循环单链表 ===

== 双链表 ==
=== 双链表存储结构 ===
{{{#!cplusplus
struct double_node{
   elem_type data;
   double_node *next;
};
typedef struct double_node double_node;
typedef struct double_node *double_list;
}}}

=== 双链表的插入 ===

=== 双链表的删除 ===

== 练习 ==

 1. 设计一个算法,求顺序表中值为x的元素的个数。
 1. 设计一个算法,将顺序表倒置。
 1. 已知一个顺序表中的各结点的值是从小到大有序的,设计一个算法,插入一个值为x的结点,使顺序表中的结点仍然是从小到大有序的。

TableOfContents

线性表逻辑结构

  • 线性表是一种典型的线性结构,是最简单且最常用的逻辑结构。 线性表是由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(L):构造一个空的线性表L,即表的初始化。
  • destroy(L):销毁线性表L
  • clear(L):将线性表L清空
  • is_empty(L):判断线性表L是否为空表
  • length(L):求线性表L中的元素个数,即求表长。
  • get_data(L, i):取线性表L中的第i个结点,这里要求latex($$1\le i \le length\_ list(L)$$)

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

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

线性表的顺序存储(顺序表 Sequential List)

1. 顺序表的存储结构

  • 采用顺序存储方式存储的线性表就称为顺序表。 即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 线性表中所有结点的类型相同,每个结点所占用存储空间大小亦相同。

    假设表中每个结点占用len个存储单元,其中第一个单元的存储地址则是该结点的存储地址,并设表中开始结点a1的存储地址(简称为基地址)是loc(a1),那么结点ai的存储地址loc(ai)可通过下式计算:latex($$loc(a_i)=loc(a_1)+(i-1)\times len,1\le i \le n$$) 在顺序表中,每个结点的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小,就可在相同时间内求出任一结点的存储地址,是一种可以随机访问的数据结构。 顺序表图示: 顺序表用固定长度的数组实现:

   1 #define MAXSIZE 100
   2 typedef int elem_type;
   3 typedef struct{
   4     elem_type  elem[MAXSIZE];
   5     int size; //表示数组中元素个数
   6 }seq_list;
  • elem_type是为了描述统一而自定义的,实际使用中,可以定义为需要的类型。 由于C语言中数组的下标从0开始,所以线性表的开始结点a1在线性表中的序号为1,对应的数组下标为0,ai在线性表中的序号为i,对应的数组下标为i-1。 除了用数组存储线性表的元素外,顺序表还需要用一个变量来表示线性表的长度属性或者最后一个元素的位置,因此用结构类型来定义顺序表类型。 存放线性表结点的数组空间的大小MAXSIZE应仔细选值,使其既能满足表结点的数目动态增加的需求,又不致于预先定义过大而浪费存储空间。

2. 初始化

   1 void init( seq_list * slt) {
   2     slt->size=0;
   3 }

3. 遍历

   1 void print(seq_list  *slt)
   2 {
   3    int i;
   4    for( i=0; i < slt->size; i++) 
   5         printf("%5d", slt->elem[i]);
   6 }

4. 判断是否为空

   1 int is_empty( seq_list  *slt ) {
   2      return  slt->size==0;
   3 }

5. 查找值为x的结点位置

   1 int locate(seq_list *slt, elem_type x)
   2 {
   3     int i=0;
   4     while(i < slt->size && slt->elem[i]!=x) 
   5         i++;
   6     return i<=slt->last? i+1:-1;
   7 }

6. 取得第i个结点的值

   1 elem_type get_data(seq_list *slt, int position) {
   2     return slt->elem[position-1];

7. 任意位置插入

   1 void insert(seq_list *slt, int position, elem_type x) { 
   2     int i;
   3     position--;
   4     for(i = slt->size; i > position; i--) 
   5         slt->elem[i] = slt->elem[i-1];
   6     slt->elem[position]=x;
   7     slt->size++;
   8 }

插入算法时间性能分析

8. 任意位置元素删除

void remove(seq_list *slt, int position) {
    int i;
    position--;
    for(i=position; i<slt->size-1; i++) 
        slt->elem[i]=slt->elem[i+1];
    slt->size--;
}

删除算法时间效率

9. 顺序表的用法举例

int main() {
    seq_list  sqlist;
    init_list(&sqlist);
    insert_list(&sqlist, 1, 1);
    print_list(&sqlist);
    printf("%d", locate_list(&sqlist, 10));
    printf("%d", locate_list(&sqlist, 11));
    while(!empty_list(&sqlist))
        delete_list(&sqlist, sqlist.size);
    print_list(&sqlist);
}

线性表的链式存储(带头结点的单链表)

1. 链表的存储结构

  • 数据结构的存储方式必须体现它的逻辑关系。在链式存储方式下,除存放一个结点的信息外,还需附设指针,用指针体现结点之间的逻辑关系。 如果一个结点有多个后继或多个前驱,那么可以附设相应个数的指针,一个结点附设的指针指向的是这个结点的某个前驱或后继。 线性结构的链式存储被称为链表。链表中可以只附设一个指针指向它的后继结点的存放位置;也可以设两个指针,一个指向前驱一个指向后继。 单链表是线性表链式存储的一种形式。其中的结点一般含有两个域,一个是存放数据信息的域,另一个是存放该结点的后继结点的地址的指针域。一个单链表必须有一个首指针指向单链表中的第一个结点。 带头节点的单链表存储结构:普通单链表的缺点:特殊情况太多,处理起来太麻烦 改进办法:增设头结点,头结点不存放任何数据 单链表存储结构实现

   1 typedef int elem_type;
   2 struct node{
   3    elem_type data;
   4    struct node *next;
   5 };
   6 typedef struct node node;
   7 typedef struct node *link_list; 

2. 初始化

   1 void init(link_list *list) {
   2    *list = (link_list)malloc(sizeof(node));
   3    (*list)->next = NULL;
   4 }

3. 插入

基本插入算法

   1 void insert(node *q, elem_type x) 
   2 {
   3    p = (node*)malloc(sizeof(node));
   4    p->data = x;
   5    p->next = q->next;
   6    q->next = p;
   7 }

插入特定位置

   1 void insert_pos(link_list node, int pos, elem_type x) 
   2 {
   3    while(pos > 1) {
   4         node = node->next;
   5         pos--;
   6    }
   7    insert(node, x);
   8 }

4. 删除

基本删除算法

   1 void remove(node *pre) 
   2 {
   3    node *p = pre->next;
   4    pre->next=p->next;
   5    free(p);
   6 }

删除特定位置元素算法

   1 void remove_pos(Node *node, int pos) 
   2 {
   3    while(pos > 1) {
   4       node = node->next;
   5       pos--;
   6    }
   7    remove(head);
   8 }

删除特定值的元素算法

   1 void remove_x(node *head, elem_type x) 
   2 {
   3    node *pre = head;
   4    while(pre->next!= NULL && 
   5       pre->next->data != x) 
   6    {
   7       pre=pre->next;
   8    }
   9    remove(pre);
  10 }

5. 查找算法

   1 node *get_data(node *head, int pos) 
   2 {
   3    while(pos > 0) {
   4       head = head->next;
   5       pos--;
   6    }
   7    return head;
   8 }

   1 node *find_x(node *head, elem_type x) 
   2 {
   3    head = head->next;
   4    while(head!=NULL && head->data != x) 
   5    {
   6       head=head->next;
   7    }
   8    return head;
   9 }

6. 思考

如何实现:

  • 打印链表的每一个元素的值
  • 求链表的长度
  • 合并两个有序的单链表,使他们依然有序

不带头结点的单链表

  • 不设开始的头结点,head指针直接指向第一个元素。 插入、删除操作比较繁琐

循环单链表

  • 如果希望从表中的任意一个结点开始,都能访问到表中的所有其它结点,可以设置表中最后一个结点的指针域指向表中的第一个结点,这种链表称为循环单链表(或单循环链表)

1. 循环单链表与单链表的不同

  • 单链表中某个结点p是表中最后一个结点的特征是p->next==NULL。

  • 对于循环单链表,若首指针为head,表中的某个结点p是最后一个结点的特征应该是p->next==head。

  • 判断单链表为空的条件是head->next==NULL

  • 判断循环单链表为空的条件是head->next == head

2. 循环单链表插入

3. 循环单链表的删除

4. 只设尾指针的循环单链表

在循环单链表中,常常只设一个尾指针不设头指针。

5. 例子:合并两个循环单链表

双链表

1. 双链表存储结构

   1 struct double_node{
   2    elem_type data;
   3    double_node *next;   
   4 };
   5 typedef struct double_node double_node;
   6 typedef struct double_node *double_list;

2. 双链表的插入

3. 双链表的删除

练习

  1. 设计一个算法,求顺序表中值为x的元素的个数。
  2. 设计一个算法,将顺序表倒置。
  3. 已知一个顺序表中的各结点的值是从小到大有序的,设计一个算法,插入一个值为x的结点,使顺序表中的结点仍然是从小到大有序的。

线性表 (2008-02-23 15:36:38由localhost编辑)

ch3n2k.com | Copyright (c) 2004-2020 czk.