计算机专业基础课
,数据结构,
教师：邵定宏序
,数据结构,是计算机程序设计的重要理论技术基础，它主要研究在计算机上有效地组织数据和处理数据的方法，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。
在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题,
(1) 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构,
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,
即数据的 存储结构,
(3)对各种数据结构进行的 运算,
通过本课程的学习，使我们能够系统地掌握表、栈、队列、
树和图等数据结构的基本特征和在计算机上实现的技术；学会怎样对处理的数据建立抽象数据类型，利用抽象数据类型进行程序设计的方法；从而培养我们 软件设计和编程能力。
第一章：绪论 （ 2学时）
什么是数据结构
基本概念和术语
算法和算法分析
1.1 什么是数据结构
计算机解题的步骤提出问题（目标函数） → 建模 → 设计算法 → 编程 → 调试 → 结果
建模的实质提取操作对象 → 找出对象间的关系 → 数学语言描述例,数值计算问题圆的面积（函数）
应力分析 （线性方程组）
人口增长预报（微分方程）
例,非数值计算问题书目检索自动化（表）
人机对弈（树）
交通灯管理（图）
什么是数据结构数据结构是一门研究 非数值计算 的程序设计中计算机的 操作对象 以及它们之间的 关系 和 操作 等的学科。
1.2 基本概念和术语
数据,符号的总称（数、串、图象和声音等）。
数据元素,数据的基本单位（一本书、一个学生、一个班级、一个年级和一个学校等）。
数据对象,性质相同的数据元素的集合（整数集、字母集等）
数据结构,相互间存在某种特定关系的数据元素的集合，这种数据元素之间的关系称为结构。
四种基本结构：
集合（松散）、线性（一对一）、
树型（一对 多）、图状或网状（多对多）。
形式定义,Data_Structure=(D,S)
其中,D是数据元素的有限集。
S是 D上关系的有限集。
1.2 基本概念和术语例,复数,Complex=(C,R)
课题小组,Group=(P,R)
逻辑结构,关系存储结构,表示 (映象 )
(在高级语言层次上 )
顺序,位置相邻 (一维数组 )
链式,指针 (指针或数组 )
计算设计,取决于选定的逻辑结构算法实现,依赖于采用的存储结构
1.2 基本概念和术语
数据类型,刻画了操作对象的特性规定,值的集合和一组操作
(整数的范围,(16位 ) -32768～ 32767
操作,+,-,*,DIV,%）
抽象数据类型（ ADT）,数学模型和一组操作。
（? 抽象? 的定义在于数据类型的数学抽象特性）
分类,原子类型,100整数。
固定聚合类型：复数（ C1,C2）。
可变聚合类型：有序整数类型。
抽象数据类型的形式定义：
ADT=（ D,S,P）
其中,D是数据对象； S是 D上的关系集； P是对 D的基本操作集。
（用类 C作为描述工具，来讨论数据结构及其算法）
1.3 算法和算法分析
算法,解题步骤的描述，指令的有限序列。
算法的特性,有穷性、确定性、可行性、输入、输出。
算法评价标准,可读性、健壮性、效率（时间、空间）
（前提：正确性,（ 1）无语法错误
（ 2）随意数据
（ 3）刻意数据
（ 4）一切合法数据）
算法效率的度量,
（ 1）事后统计法
（ 2）事前估算法（最大语句频度）
1.3 算法和算法分析
时间复杂度,T（ n） =O（ f（ n））
例,for ( i=1; i<=n; i++) n+1
for ( j=1; j<=n; j++) n*(n+1)
{ c[i][j]=0; n*n
for (k=1; k<=n; k++) n*n*(n+1)
c[i][j]+=a[i][k]*b[k][j]; n*n*n
}
T(n)=2n3+3n2+2n+1=O( n3)
（ 渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度）
空间复杂度,S（ n） =O（ f（ n））
练习题
1,下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（ 1） A=（ K,R） 其中,K={a,b,c,d,e}； R={r}；
r={<a,b>,<b,c>,<c,d>,<d,e>}
（ 2） C=( K,R ) 其中,K={1,2,3,4}; R={r};
r={(1,2),(1,3),(2,4),(3,4)}
2,指出下列各算法的时间复杂度。
（ 1） i=1;
while (i<=n)
i=i*3;
（ 2） fact(int n)
{ if (n<=1) return(1);
else return(n*fact(n-1));
}
参考答案：
1,(1) a b c d
(2) ①
② ③
④
2,Log3 n
3,T(n)=O(1)+T(n-1) =2*O(1)+T(n-2)
……
=(n-1)*O(1)+T(1)
=n*O(1)=O(n)
第二章 线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示和相加
2.1 线性表的类型定义
线性结构的特点：
除第一个元素没有直接前驱和最后一个元素没有直接后继之外，其它元素只有一个直接前驱和只有一个后继。
例：线性表、栈和队列、串。
线性表,n个数据元素的有限序列。
（ a1,a2,a3,……,a n）
其中,ai可以是数、字符和记录等。
抽象数据结构类型线性表的定义
（除上述 11种基本操作之外，还可是：合并、拆分和复制等）
例,A=（ 1,2,3） B=（ 2,3,4,5）
A∪ B=（ 2,3）
2.2 线性表的顺序表示和实现
线性表的顺序表示,是指用一组地址连续的存储单元依次存放数据元素。
元素的存储位置关系式,
Loc(ai)=Loc(a1)+(i-1)*l
由公式可见，线性表的顺序存储结构是一种随机存取的存储结构。
由于数组类型具有上述特性，所以，通常用数组来描述顺序存储结构。
线性表的基本操作,
插入,前,（ a1,a2,…,ai-1,ai,…,an） 表长,n
后,（ a1,a2,…,ai-1,x,ai,…,an ） 表长,n+1
（向后移动数据元素，以保证? 位置相邻? 来体现数据元素的顺序关系。）
2.2 线性表的顺序表示和实现
顺序表的存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef struct
{ ElemType *elem;
int length;
int listsize;
} SqList;
2.2 线性表的顺序表示和实现
Status ListInsert_sq(Sqlist &L,int i,ElemType e)
{ if (i<1 || i>L.length+1) return ERROR;
if (L.length>=L.listsize)
{ newbase=(ElemType *) realloc(L.elem,
( L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (! newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]); p>=q; --p) *(p+1)=*p;
*q=e; ++L.length; return OK;
}
2.2 线性表的顺序表示和实现删除,前：（ a1,a2,…,ai-1,ai,…,an） 表长,n
后：（ a1,a2,…,ai-1,ai+1,…,an ） 表长,n-1
（向前移动数据元素，以保证? 位置相邻? 来体现数据元素的顺序关系。）
Status ListDelete_sq(Sqlist &L,int i,ElemType &e)
{ if ((i<1) || (i>L.length)) return ERROR;
p=&(L.elem[i-1] );
e=*p;
q=L.elem+L.length-1;
for (++p; p<=q; ++p ) *(p-1)=*p;
--L.length; return OK;
}
2.2 线性表的顺序表示和实现
查找：
int LocateElem_sq(SqList L,ElemType e,
Status (*compare)(ElemType,ElemType))
{ i=1;
p=L.elem;
while((i<=L.length) && !(*compare)(*p++,e))
++i;
if (i<=L.length) return i;
else return 0;
}
2.2 线性表的顺序表示和实现
公式,(移动数据元素的平均次数 )
Eins=1/(n+1)*(n+(n-1)+… +2+1+0)=n/2
Edel=1/n*((n-1)+(n-2)+… +2+1+0)=(n-1)/2
在顺序存储结构的线性表中插入和删除一个数据元素，平均移动表中一半元素。
若表长为 n，则算法 ListInsert_sq和 ListDelete_sq的时间复杂度为 O（ n）。
特点：
优点：直观、随机存取。
缺点：插入、删除时，需大量移动数据元素。
2.3 线性表的链式表示和实现为弥补上述存储结构的不足，引入链式存储结构。
线性表的链式表示,用一组任意的存储单元存放数据元素。
链表,动态链表：用指针来实现（单链表、双链表、
循环链表等）。
静态链表：用数组来实现。
单链表,建立、查找、插入和删除。
双链表,插入、删除。
循环链表,合并。
2.3 线性表的链式表示和实现
单链表的结构
data next
L ∧ L a1 a2 … a n ∧
（带头结点的空表） （带头结点的非空表）
头结点的作用,对空表和非空表、第一元素和非第一元素作统一处理。
typedef struct Lnode
{ ElemType data;
struct Lnode *next;
} Lnode,*LinkList;
2.3 线性表的链式表示和实现
单链表的建立
Void CreateList_L(LinkList &L,int n)
{ L=(LinkList) malloc (sizeof(Lnode));
L->next=NULL;
for (i=n; i>0; --i)
{ p=(LinkList) malloc (sizeof(Lnode));
scanf(&p->data);
p->next=L->next; L->next=p;
}
}
2.3 线性表的链式表示和实现
单链表的查找
Status Getelem_L(LinkList L,int i,ElemType &e)
{ p=L->next; j=1;
while (p && j<i)
{ p=p->next; ++j; }
if (!p || j>i) return ERROR;
e=p->data;
return OK;
}
(练习,查找结点数据为 e的结点位置 i)
2.3 线性表的链式表示和实现
单链表的插入
p a b
② ①
s e
s=(LinkList) malloc (sizeof(Lnode));
s->data=e;
① s->next=p->next;
② p->next=s (思考题,① ② 顺序颠倒会怎样？ )
2.3 线性表的链式表示和实现
单链表的删除
q
… p a b c …
q=p->next;
p->next=q->next;
e=q->data;
free (q)
练习题,
1、编写一算法，实现在单链表中删除多余值相同的结点。
Void Delval_L (LinkList &L)
{ p=L;
while (p<>NULL && p->next<>NULL)
{ q=p; r=p->next;
while (r<>NULL)
{ if (p->data=r->data) { q->next=r->next; free(r);
r=q->next; }
else { q=r; r=r->next;}
}
p=p->next;
}
}
练习题,
2、编写一算法,将带头结点的单链表倒置,
Void InvertLinkList_L (LinkList &L)
{ p=L->next; L->next=NULL;
while (p) { s=p;
p=p->next;
s->next=L->next;
L->next=s;
}
}
2.3 线性表的链式表示和实现
双链表的插入
p
… a b …
① ② ④ ③
s e
s=(DLinkList) malloc (sizeof (DLnode));
s->data=e;
① s->prior=p->prior; ② p->prior->next=s;
③ s->next=p; ④ p->prior=s;
2.3 线性表的链式表示和实现
双链表的插入 (在 p的后面插入 )
s=(DLinkList) malloc (sizeof (DLnode));
s->data=e;
① s->prior=p; ② s->next=p->next;
③ p->next->prior=s; ④ p->next=s;
2.3 线性表的链式表示和实现
双链表的删除
① p
… a b c …
②
e=p->data;
① p->prior->next=p->next;
② p->next->prior=p->prior;
free (p);
2.3 线性表的链式表示和实现
循环链表的合并
… A
p
… B
A
p=A->next;
A->next=B->next->next;
B->next=p;
A=B;
2.3 线性表的链式表示和实现
静态链表：用数组描述的链表。 one data cur
0 1
#define MAXSIZE 100 1 a 2
typedefine struct 2 b 3
{ ElemType data; 3 c NULL
int cur; two 4 x 5
} compoment,SLinkList[MAXSIZE] ; 5 y 6
6 m 7
注,one是个带头结点的单链表 7 n 4
two是个单循环链表,
2.4 一元多项式的表示和相加
一元多项式的数学表示：
pn(x)=p0+p1x+p2x2+…+p nxn
一元多项式的线性表表示：
p=( p0,p1,p2,…,p n)
其中：每一项的指数 i隐含在系数 pi的序号里。
一元多项式的存储结构
（可采用顺序结构或链式结构）
2.4 一元多项式的表示和相加
利用线性链表的基本操作来实现一元多项式的运算
A -1 7 0 3 1 9 8 5 17∧
B -1 8 1 22 7 -9 8 ∧
C -1 7 0 11 1 22 7 5 17 ∧
上机实习题
一元多项式的相加（单链表表示）。
约瑟夫问题,（用循环链表做）
n 个人围成一圈，从第 s个开始数 1,2,3,…,数到
m个则退出。然后从下一个重新开始数，依次重复，直到最后一个人退出为止。
将上面两个练习题上机验证一下。
第 3章 栈和队列
栈
栈的应用举例
栈与递归的实现
队列
3.1 栈
栈的定义是限定仅在表尾进行插入或删除操作的线性表，又称为后进先出 (Last In First Out,LIFO)的线性表。
出栈 进栈栈顶 an
…
栈底 a1
栈的表示和实现顺序栈,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top指示栈顶元素在顺序栈中的位置,
3.1 栈
顺序栈的存储结构
#define STACK_INIT_SIZE 100
#define STACKINCRAMENT 10
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
例,栈空,栈满,top
E
D
C
B
top base A
base
注,若 base的值为 NULL，则表明栈结构不存在。若 top=base可作为栈空的标志。通常，插入新的栈顶元素时，指针 top增 1,删除栈顶元素时，指针 top减 1。因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
3.1 栈
进栈：
status push (sqstack &s,selemtype e )
{ if (s.top-s.base>=s.stacksize)
{ s.base=(elemtype *) realloc(s.base,
(s.stacksize+stackincrement)+sizeof(elemtype));
if (!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e; return(OK );
}
3.1 栈
出栈：
Status pop (sqstack &s,selemtype &e)
{ if (s.top==s.base) return ERROR;
e=*--s.top;
return OK;
}
链栈,用链式存储结构来表示栈。
top
…
∧
3.2 栈的应用举例
数制转换
表达式求值例,(25)10=(31)8
Void conversion( )
{ Initstack(s);
scanf(“%d”,&n);
while (n) top 3
{ Push(s,n%8); n=n/8; } top 1 1 top
while (! Stackempty) (a) (b) (c)
{ Pop(s,e); printf(“%d”,e); }
}
3.2 栈的应用举例例：计算 3*（ 7-2）
步骤 OPTR栈 OPND栈 输入字符 主要操作
1 # 3*（ 7-2） # PUSH（ OPND，‘ 3?）
2 # 3 *（ 7-2） # PUSH（ OPTR，‘ *’）
3 # * 3 （ 7-2） # PUSH（ OPTR，‘（’）
4 # *（ 3 7-2） # PUSH（ OPND，‘ 7?）
5 # *（ 3 7 -2） # PUSH（ OPTR，‘ -?）
6 # *（ - 3 7 2） # PUSH（ OPND，‘ 2?）
7 # *（ - 3 7 2 ） # operate (?7?,?-?,?2? )
8 # * ( 3 5 ) # POP ( OPTR )
9 # * 3 5 # operate (?3?,?*?,?5? )
10 # 15 # return ( GETTOP(OPND))
3.2 栈的应用举例
Operandtype evaluateexpression( )
{ Initstack (OPTR); Push (OPTR,?#?);
Initstack (OPND); c=getchar( );
while (c!=?#? || Gettop(optr!=?#?))
{ if ( ! In(c,OP)) { Push(OPND,c); c=getchar( );}
else switch ( Precede( Gettop(OPTR),c))
{ case?<?,Push(OPTR,c); c=getchar( ); break;
case?=?,Pop(OPTR,x); c=getchar( ); break;
case?>?,Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b)); break;
}
}
return Gettop(OPND);
}
3.3 栈与递归的实现
递归的定义,一个函数、过程或数据结构（如广义表、树等），
若在它们定义的内部又出现有本身的应用，则称它们是递归的，
或者是递归定义的。
例,自然数的集合
（ 1） 1是自然数
（ 2）一个自然数的后继是一个自然数。
递归的条件,复杂 简单终结例,1 n=0
n!=
n*(n-1)! n>0
3.3 栈与递归的实现
n!的递归程序及内部实现
main( )
Void fact1(int n,int &r) { …
① { if ( n==0) fact1(3,f)
② r=1; i,…
③ else { fact1(n-1,w); }
④ r=n*w;}
⑤ }
3.3 栈与递归的实现执行语句标号 运行栈的状态（返址,n,r,w）
0 1 ( i 3 &f - )
1,3 2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,3 3 ( 4 1 &w2 - )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,3 4 ( 4 0 &w3 - )
3 ( 4 1 &w2 - )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,2 3 ( 4 1 &w2 1 )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
4,5 2 ( 4 2 &w1 1 )
1 ( i 3 &f - )
4,5 1 ( i 3 &f 2 )
3.3 栈与递归的实现
递归与非递归的转换
void fact2( int n,int &r)
{ top=1; st[1]=n;
while ( st[top]>1)
{ top++; st[top]=st[top-1]-1; }
r=1;
while (top>0)
{ r=st[top]*r; top--; }
}
练习题,
一个栈的入栈序列是 a,b,c,d,e,，则栈的不可能序列是：
(A) edcba (B) decba
(C) dceab (D) abcde
判定一个栈 ST（最多元素为 m0）为空的条件是？为满的条件是？
栈空的条件,ST->top=0
栈满的条件,ST->top=m0
练习题,
指出下列程序的功能
void reverse( )
{ scanf(“%c”,&ch);
if(ch!=?.?) { reverse;
printf(“%c”,ch); }
}
练习题,
McCathy函数定义如下：
M(x)= x-10 x>100
M(M(x+11)) x≤100
（ 1）编写一个递归函数计算给定 x的 M(x)值。
（ 2）编写一个非递归函数计算给定 x的 M(x)值。
int m(int x)
{ int y;
if(x>100) return(x-10);
else { y=m(x+11);
return(m(y));}
}
int m1(int x)
{ int level=1,y;
if(x>100) return(x-10);
else { level++; y=x+11; }
while(level>0)
{ if(y>100) { level--; y=y-10; }
else { level++; y=y+11; }
}
return(y);
}
3.4 队列
队列的定义：
是一种先进先出 (First In First Out,FIFO)的线性表，只允许在表的一端进行插入，而在另一端删除元素。
队列的表示和实现出队列 a1 a2 a3 … a n 入队列队头 队尾顺序队列,用一维数组表示的队列。
链队列,用链表表示的队列。
循环队列,将顺序队列臆造为一个环状的空间。
3.4 队列
data next
Q.front 头结点队头
…
Q.rear ^ 队尾单链队列的存储结构：
Typedef struct Qnode typedef struct
{ Qelemtype data; { Queueptr front;
struct Qnode *next; Queueptr rear;
} Qnode,*Queueptr; } Linkqueue;
链队列：
入队：
Status Enqueue(Linkqueue &Q,Qelemtype e)
{ p=(Queueptr) malloc (sizeof(Qnode));
if (! p) exit (OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p; Q.rear=p;
return OK;
}
出队：
Status Dequeue(LinkQueue &Q,Qelemtype &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next; e=p->data;
Q.front->next=p->next;
if (Q.rear==p) Q.rear=Q.front;
free(p); return OK;
}
3.4 队列循环队列：
maxsize-1
… 0
Q,rear … 1
Q.front
队空,Q.front=Q.rear
队满,(Q.rear+1) % maxsize=Q.front
3.4 队列循环队列的顺序存储结构：
#define MAXSIZE 100
typedef struct
{ Qelemtype *base;
int front; int rear;
} SeQueue;
入队：
Status Enqueue(SeQueue &Q,Qelemtype e)
{ if ((Q.rear+1) % MAXSIZE==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1) % MAXSIZE;
return OK;
}
出队：
Status Dequeue(SeQueue &Q,Qelemtype &e)
{ if (Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXSIZE ;
return OK;
}
练习题,
上机实习题
迷宫求解
八皇后问题迷宫求解
基本思路,从迷宫入口点 (1,1)出发，向四周搜索，记下所有能一步通达的坐标点，依次进行下去，直至到达迷宫出口点 (m,n)为止。这样就找到了从入口到出口的一条最短路径。
需要解决的几个问题：
（ 1）如何表示迷宫？（二维数组,0：表示通； 1：表示不通）
（ 2）如何从某一坐标点出发搜索其四周的邻点？（ v:8个方向）
i=x+move[v].x
y=y+move[v].y
（ 3）如何存储搜索路径？（队列）
(北 )
(x-1,y-1) (x-1,y) (x-1,y+1)
(西 ) (x,y-1) (x,y) (x,y+1) (东 )
(x+1,y-1) (x+1,y) (x+1,y+1)
(南 )
Sq[i],x y pre
1 1 1 0
2 2 2 1 (1,1)
front 3 3 3 2
4 3 1 2 (2,2) (2,4)
5 3 4 3
rear 6 2 4 3 (3,1) (3,3) (3,4)
…
#include <stdio.h>
#define m 8
#define n 10
Struct sqtype
{ int x,y,pre;
} sq[ 200];
int mg[m+1][n+1];
Struct mtype
{ int x; int y;
} move[8];
Void print( int rear)
{ int i; i=rear;
do { printf(“%d,%d”,sq[i].x,sq[i].y);
i=sq[i].rear;
} while(i !=0)
}
Void mglj( )
{ int i,j,x,y,k,front,rear,find;
sq[1].x=1; sq[1].y=1; sq[1].pre=0;
find=0;
front=1; rear=1; mg[1][1]=-1;
While(front<=rear && !find)
{ x=sq[front].x; y=sq[front].y;
for(k=1; k<=8; k++)
{ i=x+move[k].x;
j=y+mov[k].y;
if(mg[i][j]==0)
{ rear++; sq[rear].x=i;
sq[rear].y=j; sq[rear].pre=front;
mg[i][j]=-1;}
if (i==m && j==n)
{ print(rear); find=1; }
}
front++;
}
if (! find) printf(“不存在路径,\n”);
}
第四章 串
串及其运算
串的存储结构
串基本运算的实现
串的应用
4.1 串及其运算
串是一种特殊的线性表，它的结点仅有一个字符组成。它在文字编辑、词法扫描、符号处理和定理证明等领域有广泛的应用。
串的定义串,是由零个或多个字符组成的有限序列。
一般记为,S=?a1,a2,…,a n? n≥0
串名 串值其中,ai可以是字母、数字或其它字符。
长度,串中字符的数目。
空串,长度为零的串。 例：‘’
空格串,由一个或多个空格组成的串。 例：‘ ’
主串,包含子串的串。 例：‘ abcde?
子串,主串中的任意个连续的字符组成的子序列。例：‘ bcd?
4.1 串及其运算位置,字符在序列中的序号。
串相等,当且仅当这两个串的值相等。（长度相等；各个对应位置的字符相等。）
(在程序中通常使用的有串常量和串变量 )
4.1 串及其运算
串的一般表示
（大写字母表示串 S；小写字母表示组成串的字符）
例,S1=?a1,a2,…,a m?
S2=?b1,b2,…,b n?
串的基本运算
⑴ 赋值（ =或 ASSIGN(S,T)）：
例,S=?abc? S=T
⑵ 联接 ( + 或 concat(S,T) )
例,S1+S2=?a1,a2,…,a m b1,b2,…,b n?
concat(S1,S2)
4.1 串及其运算
串的基本运算
⑶ 求串长 ( Length(S) )
例,Length(S1)=m Length(?abc?)=3
Length()=0 Length()=1
⑷ 求子串 ( Substr(S,i,j) )
例,Substr( S1,i,j )=?ai,ai+1,…,a i+j-1?
⑸ 串比较 ( Strcmp(S,T) )
S<T -1
S=T 0
S>T 1
4.1 串及其运算
串插入 ( Insert(S1,i,S2) )
Inseert(S1,i,S2)
=Substr(S1,1,i)+S2+Substr(S1,i+1,Length(S1)-i )
串删除 ( Delete(S1,i,j) )
Delete(S1,i,j)
= Substr(S1,1,i-1)+Substr(S1,i+j,Length(S1)-(i+j-1) )
求子串位置 ( Index(S1,S2) )
Index(?abcdef?,?cde?)=3
串置换 ( Replace(S1,i,j,S2) )
Replace(S1,i,j,S2)
=Substr(S1,1,i-1)+S2+Substr(S1,i+j,Length(S1)-(i+j-1) )
4.2 串的存储结构
串的三种机内表示顺序存储,用一组地址连续的存储单元存储串值的字符序列。
（在做插入、置换和联接操作时，可能产生超界。）
堆分配存储,仍以一组地址连续的存储单元存储串值的字符序列。但它们的存储空间是在程序执行过程中动态分配而得。
（较好的克服上述弊病。）
块链存储,用链式方式存储串值。除设头指针外，
还设一个尾指针，并给出当前串的长度。
4.3 串基本运算的实现
串联接,(顺序存储 )
Status concat(Sstring &T,Sstring S1,Sstring S2)
{ if(S1[0]+S2[0]<=MAXSTRLEN)
{ T[1..s1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]; uncut=TRUE;
}
else if(S1[0]<MAXSTRSIZE)
{ T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN; uncut=FALSE;
}
else { T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE; } return uncut;
}
4.3 串基本运算的实现
求子串,（顺序存储）
Status SubString(Sstring &Sub,Sstring S,int pos,int len)
{ if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
return ERROR;
Sub[1..len]=S[pos..pos+len-1];
Sub[0]=len; return OK;
}
4.3 串基本运算的实现
串联接,（堆分配存储）
Status Concat (Hstring &T,HString S1,Hstring S2)
{ if (T.ch) free(T.ch);
if (! (T.ch=(char *) malloc ((S1.length+S2.length)
* sizeof(char))))
exit (OVERFLOW);
T.ch[0..s1.length-1]=S1.ch[0..s1.length-1];
T.length=S1.length+S2.length;
T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];
return OK;
}
4.3 串基本运算的实现
求子串：（堆分配存储）
Status SubString (Hstring &Sub,Hstring S,int pos,int len)
{ if (pos<1 || pos>S.length || len<0 || len>S.length-pos+1)
return ERROR;
if (Sub.ch) free(Sub.ch);
if (! len) { Sub.ch=NULL; Sub.length=0; }
else { Sub.ch=(char *) malloc (len*sizeof(char));
Sub.ch[0..len-1]=S[pos-1..pos+len-2];
Sub.length=len;
} return OK;
}
4.3 串基本运算的实现
模式匹配算法模式匹配,子串的定位操作。 （其中子串 T为模式串））
传统匹配方法,从主串 S的第一个字符起和模式串 T的第一个字符比较之，若相等，则继续逐个比较后续字符。否则从主串的第二个字符起再重新和模式串的字符比较，依次类推，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等。
(p80—图 4.3)
4.3 串基本运算的实现
int index(Sstring S,Sstring T,int pos )
{ i=pos; j=1;
while (i<=s[0] && j<=T[0])
{ if (S[i]==T[j]) {++i; ++j;}
else {i=i-j+2; j=1;}
}
if (j>T[0]) return i-T[0];
else return 0; 注,S[0],T[0]分别为 S,T串的长度。
} pos初始值为 1。
4.3 串基本运算的实现
KMP匹配方法（无回朔）,每当一趟匹配过程中出现字符不等时，
不需回朔 i指针，而是利用已经得到的?部分匹配?结果将模式向右?滑动?尽可能远的一段距离后，继续进行比较。 (该法由克努特 -莫里斯 -普拉特同时发现，所以称为 KMP方法。 )
Next函数的计算
0 当 j=1 时
Next[j]= Max{ k|1<k<j 且 ’ p1…p k-1?=?p j-k+1…p j-1?}
1 其它情况例,a b a a b
0 1 1 2 2
(p80—图 4.5)
练习题,
根据模式串的 next函数的定义，推出下列模式串的 next[i]函数值。
例,aaabcd
若 S和 T是用结点大小为 1的单链表存储的两个串，设计一个算法将串 S中首次与串 T匹配的子串逆置。
参考答案：
0 1 1 3 1 1
inverseLink(LinkList &S,LinkList T)
{ ps=qs=S->next; rs=S; pt=T;
while(ps && pt)
{ if(ps->data==pt->data) {ps=ps->next; pt=pt->nexty;}
else { rs=qs; qs=qs->next;
ps=qs; pt=T; }
if (pt==NULL ) { p=qs;
while(p !=ps) { q=p; p=p->next;
q->next=rs->next;
rs->next=q; }
qs->next=ps;
}
}
}
上机实习题
建立词索引表（词典有序），并将生成的词索引表输出。
基本要求,直接输入关键词和书号，生成词索引表。
生成词索引表后，输入一关键词，则输出其有关书号。
较高要求,从书目文件中生成词索引表，并输出到文件中和屏幕上。生成词索引表后，输入一关键词，
则输出其有关书号。（判断关键词，必须与常用词表中的常用词进行比较，不是常用词（ an,a,of,the,to
等），则为关键词。）
第五章 数组和广义表
多维数组
矩阵的压缩存储
广义表
（ 多维数组和广义表则是一种复杂的非线性结构，
它的逻辑特征是一个数据元素可能有多个直接前驱和直接后继。）
5.1 多维数组
多维数组是向量的推广。对于二维数组，可以看成是由 m
个行向量组成的向量，也可以看成是由 n个列向量组成的向量。
a11 a12 … a 1n
A m*n= a21 a22 … a 2n
…
am1 am2… a mn
（二维数组中的每个元素 aij均属于两个向量，第 i行的行向量和第 j列的列向量。）
5.1 多维数组
数组的操作通常有两种,（ 1）给定一组下标，存取相应的数组元素。
（ 2）给定一组下标，修改相应数据元素的某一个或几个数据项的值。
数组的顺序存储结构由于计算机内存结构是一维的，因此，用一维的内存来存放多维数组的数据元素，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。
通常有两种顺序存储方式：
（ 1）按行优先,a11,a12,…,a 1n,a21,a22,…,a mm
（ 2）按列优先,a11,a21,…,a m1,a12,a22,…,a mm
5.1 多维数组
二维数组按行优先顺序存储的数组元素地址的计算函数：
Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*d
其中：
⑴ 开始结点的存放地址（基地址）。
⑵ 维数。
⑶ 每维的上、下界。
⑷ 每个数组元素所占用的单元数。
5.2 矩阵的压缩存储
压缩存储,为多个相同的非零元素只分配一个存储空间，对零元素不分配存储空间。
特殊矩阵的压缩存储特殊矩阵,是指非零元素或零元素的分布是有一定规律的矩阵。
对称矩阵,满足下列性质的方阵：
a ij=a ji 1≤i,j≤ n
1 5 1 3 a11
5 0 8 0 a21 a22
1 8 9 2 a31 a32 a33
3 0 2 5 4*4 a41 a42 a43 a44
5.2 矩阵的压缩存储
对称矩阵的计算公式：
k= i(i-1)/2+j j≤i
j(j-1)/2+i j > i
5.2 矩阵的压缩存储三角矩阵下三角矩阵,是指上三角（不包括主对角线）中的元素均为常数 C或零。
上三角矩阵,是指下三角（不包括主对角线）中的元素均为常数 C或零。
a11 a12 … a 1n a11 C … C
C a22 … a 2n a21 a22 … C
… …
C C … a mm am1 am2… a mm
(上三角矩阵 ) (下三角矩阵 )
5.2 矩阵的压缩存储
上三角矩阵的计算公式：
k= j(j-1)/2+i j≥i
n(n+1)/2+1 j < i
下三角矩阵的计算公式：
k= (2n-j+2)(j-1)/2+(i-j+1) i≤j
n(n+1)/2+1 i > j
5.2 矩阵的压缩存储
稀疏矩阵的压缩存储是指矩阵中的非零元素远远少于零元素,
稀疏矩阵的压缩存储的压缩存储方法三元组表,若将表示稀疏矩阵的非零元素的三元组按行优先 (或按列优先 )的顺序排列,则得到一个结点均是三元组的线性表,则称该线性表为三元组表,
十字链表,将稀疏矩阵中的非零元素处于行循环链表和列循环链表的十字交叉路口上,则称为十字链表,
5.2 矩阵的压缩存储
三元组表,是稀疏矩阵的一种顺序存储结构。
例,A= 0 5 0 0 8 B= 0 1 0 6
1 0 3 0 0 5 0 -2 0
0 -2 0 0 0 0 3 0 0
6 0 0 0 0 0 0 0 0
按列转置,i j v 8 0 0 0
1 1 2 5 1 2 1
2 1 5 8 1 4 6
3 2 1 1 2 1 5
4 2 3 3 2 3 -2
5 3 2 -2 3 2 3
6 4 1 6 5 1 8
5.2 矩阵的压缩存储
Status Transmatrix(TSMatrix M,TSMatrix &T )
{ T.mu=M.nu; T.nu=M.nu; T.tu=M.tu;
if(T.tu) { q=1;
for(col=1; col<=M.nu; ++col)
for(p=1; p<=M.tu; ++p)
if(M.data[p].j==col)
{ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++q;
}
}
return OK;
}
5.2 矩阵的压缩存储
按 A的行序进行转置
cpot[1]=1
cpot[col]=cpot[col-1]+num[col] 2≤col≤a.nu
cpot的值：
col 1 2 3 4 5
num[col] 2 2 1 0 1
cpot[col] 1 3 5 6 6
5.2 矩阵的压缩存储
Status transmatrix1(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.nu; T.tu=M.tu;
if(T.tu) { for(col=1; col<=M.nu; ++col) num[col]=0;
for(t=1; t<=M.tu; ++t) ++num[M.data[t].j];
cpot[1]=1;
for(col=2; col<=M.nu; ++col)
cpot[col]=cpot[col-1]=num[col-1];
for(p=1; p<=M.tu; ++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
十字链表,
当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组表，而采用链式存储结构表示三元组的线性表更为恰当。
5.2 矩阵的压缩存储
5.3 广义表
广义表的定义是线性表的推广，是 n≥0 个元素 a1,a2,…,an的有限序列，其中 ai或者是原子，或者是广义表。
通常可记作：
LS= （ a1,a2,…,a n） 广义表是递归定义例,E=( ) 长度为 0，空表
L=(a,b) 长度为 2，两个原子
A=(x,L)=(x,(a,b)) 长度为 2，一个原子，一个子表
B=(A,y)=((x,(a,b)),y) 长度为 2，一个子表，一个原子
C=(A,B)=((x,(a,b)),((x,(a,b)),y)) 长度为 2，两个列表
D=(a,D)=(a,(a,(a,(…)))) 长度为 2，是无限列表
5.3 广义表表头,若广义表 LS非空，则 a1是 LS的表头。
表尾,其余元素组成的表 （ a1,a2,…,a n） 称为 LS的表尾。
例,head(L)=a tail(L)=(b)
head(B)=A tail(B)=(y)
head(tail(L))=b tail(tail(L))=( )
注,( )和 (( ))不同,前者是空表,长度为 0;后者是有一个元素的空表,长度为 1
表的深度,是指表展开后所含号的层次,
例如,表 A的深度为 2,表 D的深度为 ∞.
5.3 广义表
三个重要结论：
（ 1）列表的元素可以是子表，而列表的元素还可以是子表,… 。
（ 2）列表可为其它列表所共享。
（ 3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。
5.3 广义表
广义表的存储结构
（通常采用链式存储结构：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。）
参见,p109-图 5.9、图 5.11
5.3 广义表
广义表的递归算法求广义表的深度广义表 LS的深度 DEPTH（ LS） 的递归定义：
基本项：
DEPTH（ LS） =1 当 LS为空表时
DEPTH（ LS） =0 当 LS为原子时归纳项：
DEPTH（ LS） =1+Max{ DEPTH(a i)} n≥1
1≤i≤n
（参见,P114）
5.3 广义表
复制广义表
,数据结构,
教师：邵定宏序
,数据结构,是计算机程序设计的重要理论技术基础，它主要研究在计算机上有效地组织数据和处理数据的方法，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。
在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题,
(1) 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构,
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,
即数据的 存储结构,
(3)对各种数据结构进行的 运算,
通过本课程的学习，使我们能够系统地掌握表、栈、队列、
树和图等数据结构的基本特征和在计算机上实现的技术；学会怎样对处理的数据建立抽象数据类型，利用抽象数据类型进行程序设计的方法；从而培养我们 软件设计和编程能力。
第一章：绪论 （ 2学时）
什么是数据结构
基本概念和术语
算法和算法分析
1.1 什么是数据结构
计算机解题的步骤提出问题（目标函数） → 建模 → 设计算法 → 编程 → 调试 → 结果
建模的实质提取操作对象 → 找出对象间的关系 → 数学语言描述例,数值计算问题圆的面积（函数）
应力分析 （线性方程组）
人口增长预报（微分方程）
例,非数值计算问题书目检索自动化（表）
人机对弈（树）
交通灯管理（图）
什么是数据结构数据结构是一门研究 非数值计算 的程序设计中计算机的 操作对象 以及它们之间的 关系 和 操作 等的学科。
1.2 基本概念和术语
数据,符号的总称（数、串、图象和声音等）。
数据元素,数据的基本单位（一本书、一个学生、一个班级、一个年级和一个学校等）。
数据对象,性质相同的数据元素的集合（整数集、字母集等）
数据结构,相互间存在某种特定关系的数据元素的集合，这种数据元素之间的关系称为结构。
四种基本结构：
集合（松散）、线性（一对一）、
树型（一对 多）、图状或网状（多对多）。
形式定义,Data_Structure=(D,S)
其中,D是数据元素的有限集。
S是 D上关系的有限集。
1.2 基本概念和术语例,复数,Complex=(C,R)
课题小组,Group=(P,R)
逻辑结构,关系存储结构,表示 (映象 )
(在高级语言层次上 )
顺序,位置相邻 (一维数组 )
链式,指针 (指针或数组 )
计算设计,取决于选定的逻辑结构算法实现,依赖于采用的存储结构
1.2 基本概念和术语
数据类型,刻画了操作对象的特性规定,值的集合和一组操作
(整数的范围,(16位 ) -32768～ 32767
操作,+,-,*,DIV,%）
抽象数据类型（ ADT）,数学模型和一组操作。
（? 抽象? 的定义在于数据类型的数学抽象特性）
分类,原子类型,100整数。
固定聚合类型：复数（ C1,C2）。
可变聚合类型：有序整数类型。
抽象数据类型的形式定义：
ADT=（ D,S,P）
其中,D是数据对象； S是 D上的关系集； P是对 D的基本操作集。
（用类 C作为描述工具，来讨论数据结构及其算法）
1.3 算法和算法分析
算法,解题步骤的描述，指令的有限序列。
算法的特性,有穷性、确定性、可行性、输入、输出。
算法评价标准,可读性、健壮性、效率（时间、空间）
（前提：正确性,（ 1）无语法错误
（ 2）随意数据
（ 3）刻意数据
（ 4）一切合法数据）
算法效率的度量,
（ 1）事后统计法
（ 2）事前估算法（最大语句频度）
1.3 算法和算法分析
时间复杂度,T（ n） =O（ f（ n））
例,for ( i=1; i<=n; i++) n+1
for ( j=1; j<=n; j++) n*(n+1)
{ c[i][j]=0; n*n
for (k=1; k<=n; k++) n*n*(n+1)
c[i][j]+=a[i][k]*b[k][j]; n*n*n
}
T(n)=2n3+3n2+2n+1=O( n3)
（ 渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度）
空间复杂度,S（ n） =O（ f（ n））
练习题
1,下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。
（ 1） A=（ K,R） 其中,K={a,b,c,d,e}； R={r}；
r={<a,b>,<b,c>,<c,d>,<d,e>}
（ 2） C=( K,R ) 其中,K={1,2,3,4}; R={r};
r={(1,2),(1,3),(2,4),(3,4)}
2,指出下列各算法的时间复杂度。
（ 1） i=1;
while (i<=n)
i=i*3;
（ 2） fact(int n)
{ if (n<=1) return(1);
else return(n*fact(n-1));
}
参考答案：
1,(1) a b c d
(2) ①
② ③
④
2,Log3 n
3,T(n)=O(1)+T(n-1) =2*O(1)+T(n-2)
……
=(n-1)*O(1)+T(1)
=n*O(1)=O(n)
第二章 线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示和相加
2.1 线性表的类型定义
线性结构的特点：
除第一个元素没有直接前驱和最后一个元素没有直接后继之外，其它元素只有一个直接前驱和只有一个后继。
例：线性表、栈和队列、串。
线性表,n个数据元素的有限序列。
（ a1,a2,a3,……,a n）
其中,ai可以是数、字符和记录等。
抽象数据结构类型线性表的定义
（除上述 11种基本操作之外，还可是：合并、拆分和复制等）
例,A=（ 1,2,3） B=（ 2,3,4,5）
A∪ B=（ 2,3）
2.2 线性表的顺序表示和实现
线性表的顺序表示,是指用一组地址连续的存储单元依次存放数据元素。
元素的存储位置关系式,
Loc(ai)=Loc(a1)+(i-1)*l
由公式可见，线性表的顺序存储结构是一种随机存取的存储结构。
由于数组类型具有上述特性，所以，通常用数组来描述顺序存储结构。
线性表的基本操作,
插入,前,（ a1,a2,…,ai-1,ai,…,an） 表长,n
后,（ a1,a2,…,ai-1,x,ai,…,an ） 表长,n+1
（向后移动数据元素，以保证? 位置相邻? 来体现数据元素的顺序关系。）
2.2 线性表的顺序表示和实现
顺序表的存储结构
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
typedef struct
{ ElemType *elem;
int length;
int listsize;
} SqList;
2.2 线性表的顺序表示和实现
Status ListInsert_sq(Sqlist &L,int i,ElemType e)
{ if (i<1 || i>L.length+1) return ERROR;
if (L.length>=L.listsize)
{ newbase=(ElemType *) realloc(L.elem,
( L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (! newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]); p>=q; --p) *(p+1)=*p;
*q=e; ++L.length; return OK;
}
2.2 线性表的顺序表示和实现删除,前：（ a1,a2,…,ai-1,ai,…,an） 表长,n
后：（ a1,a2,…,ai-1,ai+1,…,an ） 表长,n-1
（向前移动数据元素，以保证? 位置相邻? 来体现数据元素的顺序关系。）
Status ListDelete_sq(Sqlist &L,int i,ElemType &e)
{ if ((i<1) || (i>L.length)) return ERROR;
p=&(L.elem[i-1] );
e=*p;
q=L.elem+L.length-1;
for (++p; p<=q; ++p ) *(p-1)=*p;
--L.length; return OK;
}
2.2 线性表的顺序表示和实现
查找：
int LocateElem_sq(SqList L,ElemType e,
Status (*compare)(ElemType,ElemType))
{ i=1;
p=L.elem;
while((i<=L.length) && !(*compare)(*p++,e))
++i;
if (i<=L.length) return i;
else return 0;
}
2.2 线性表的顺序表示和实现
公式,(移动数据元素的平均次数 )
Eins=1/(n+1)*(n+(n-1)+… +2+1+0)=n/2
Edel=1/n*((n-1)+(n-2)+… +2+1+0)=(n-1)/2
在顺序存储结构的线性表中插入和删除一个数据元素，平均移动表中一半元素。
若表长为 n，则算法 ListInsert_sq和 ListDelete_sq的时间复杂度为 O（ n）。
特点：
优点：直观、随机存取。
缺点：插入、删除时，需大量移动数据元素。
2.3 线性表的链式表示和实现为弥补上述存储结构的不足，引入链式存储结构。
线性表的链式表示,用一组任意的存储单元存放数据元素。
链表,动态链表：用指针来实现（单链表、双链表、
循环链表等）。
静态链表：用数组来实现。
单链表,建立、查找、插入和删除。
双链表,插入、删除。
循环链表,合并。
2.3 线性表的链式表示和实现
单链表的结构
data next
L ∧ L a1 a2 … a n ∧
（带头结点的空表） （带头结点的非空表）
头结点的作用,对空表和非空表、第一元素和非第一元素作统一处理。
typedef struct Lnode
{ ElemType data;
struct Lnode *next;
} Lnode,*LinkList;
2.3 线性表的链式表示和实现
单链表的建立
Void CreateList_L(LinkList &L,int n)
{ L=(LinkList) malloc (sizeof(Lnode));
L->next=NULL;
for (i=n; i>0; --i)
{ p=(LinkList) malloc (sizeof(Lnode));
scanf(&p->data);
p->next=L->next; L->next=p;
}
}
2.3 线性表的链式表示和实现
单链表的查找
Status Getelem_L(LinkList L,int i,ElemType &e)
{ p=L->next; j=1;
while (p && j<i)
{ p=p->next; ++j; }
if (!p || j>i) return ERROR;
e=p->data;
return OK;
}
(练习,查找结点数据为 e的结点位置 i)
2.3 线性表的链式表示和实现
单链表的插入
p a b
② ①
s e
s=(LinkList) malloc (sizeof(Lnode));
s->data=e;
① s->next=p->next;
② p->next=s (思考题,① ② 顺序颠倒会怎样？ )
2.3 线性表的链式表示和实现
单链表的删除
q
… p a b c …
q=p->next;
p->next=q->next;
e=q->data;
free (q)
练习题,
1、编写一算法，实现在单链表中删除多余值相同的结点。
Void Delval_L (LinkList &L)
{ p=L;
while (p<>NULL && p->next<>NULL)
{ q=p; r=p->next;
while (r<>NULL)
{ if (p->data=r->data) { q->next=r->next; free(r);
r=q->next; }
else { q=r; r=r->next;}
}
p=p->next;
}
}
练习题,
2、编写一算法,将带头结点的单链表倒置,
Void InvertLinkList_L (LinkList &L)
{ p=L->next; L->next=NULL;
while (p) { s=p;
p=p->next;
s->next=L->next;
L->next=s;
}
}
2.3 线性表的链式表示和实现
双链表的插入
p
… a b …
① ② ④ ③
s e
s=(DLinkList) malloc (sizeof (DLnode));
s->data=e;
① s->prior=p->prior; ② p->prior->next=s;
③ s->next=p; ④ p->prior=s;
2.3 线性表的链式表示和实现
双链表的插入 (在 p的后面插入 )
s=(DLinkList) malloc (sizeof (DLnode));
s->data=e;
① s->prior=p; ② s->next=p->next;
③ p->next->prior=s; ④ p->next=s;
2.3 线性表的链式表示和实现
双链表的删除
① p
… a b c …
②
e=p->data;
① p->prior->next=p->next;
② p->next->prior=p->prior;
free (p);
2.3 线性表的链式表示和实现
循环链表的合并
… A
p
… B
A
p=A->next;
A->next=B->next->next;
B->next=p;
A=B;
2.3 线性表的链式表示和实现
静态链表：用数组描述的链表。 one data cur
0 1
#define MAXSIZE 100 1 a 2
typedefine struct 2 b 3
{ ElemType data; 3 c NULL
int cur; two 4 x 5
} compoment,SLinkList[MAXSIZE] ; 5 y 6
6 m 7
注,one是个带头结点的单链表 7 n 4
two是个单循环链表,
2.4 一元多项式的表示和相加
一元多项式的数学表示：
pn(x)=p0+p1x+p2x2+…+p nxn
一元多项式的线性表表示：
p=( p0,p1,p2,…,p n)
其中：每一项的指数 i隐含在系数 pi的序号里。
一元多项式的存储结构
（可采用顺序结构或链式结构）
2.4 一元多项式的表示和相加
利用线性链表的基本操作来实现一元多项式的运算
A -1 7 0 3 1 9 8 5 17∧
B -1 8 1 22 7 -9 8 ∧
C -1 7 0 11 1 22 7 5 17 ∧
上机实习题
一元多项式的相加（单链表表示）。
约瑟夫问题,（用循环链表做）
n 个人围成一圈，从第 s个开始数 1,2,3,…,数到
m个则退出。然后从下一个重新开始数，依次重复，直到最后一个人退出为止。
将上面两个练习题上机验证一下。
第 3章 栈和队列
栈
栈的应用举例
栈与递归的实现
队列
3.1 栈
栈的定义是限定仅在表尾进行插入或删除操作的线性表，又称为后进先出 (Last In First Out,LIFO)的线性表。
出栈 进栈栈顶 an
…
栈底 a1
栈的表示和实现顺序栈,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top指示栈顶元素在顺序栈中的位置,
3.1 栈
顺序栈的存储结构
#define STACK_INIT_SIZE 100
#define STACKINCRAMENT 10
typedef struct
{ SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
例,栈空,栈满,top
E
D
C
B
top base A
base
注,若 base的值为 NULL，则表明栈结构不存在。若 top=base可作为栈空的标志。通常，插入新的栈顶元素时，指针 top增 1,删除栈顶元素时，指针 top减 1。因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
3.1 栈
进栈：
status push (sqstack &s,selemtype e )
{ if (s.top-s.base>=s.stacksize)
{ s.base=(elemtype *) realloc(s.base,
(s.stacksize+stackincrement)+sizeof(elemtype));
if (!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=stackincrement;
}
*s.top++=e; return(OK );
}
3.1 栈
出栈：
Status pop (sqstack &s,selemtype &e)
{ if (s.top==s.base) return ERROR;
e=*--s.top;
return OK;
}
链栈,用链式存储结构来表示栈。
top
…
∧
3.2 栈的应用举例
数制转换
表达式求值例,(25)10=(31)8
Void conversion( )
{ Initstack(s);
scanf(“%d”,&n);
while (n) top 3
{ Push(s,n%8); n=n/8; } top 1 1 top
while (! Stackempty) (a) (b) (c)
{ Pop(s,e); printf(“%d”,e); }
}
3.2 栈的应用举例例：计算 3*（ 7-2）
步骤 OPTR栈 OPND栈 输入字符 主要操作
1 # 3*（ 7-2） # PUSH（ OPND，‘ 3?）
2 # 3 *（ 7-2） # PUSH（ OPTR，‘ *’）
3 # * 3 （ 7-2） # PUSH（ OPTR，‘（’）
4 # *（ 3 7-2） # PUSH（ OPND，‘ 7?）
5 # *（ 3 7 -2） # PUSH（ OPTR，‘ -?）
6 # *（ - 3 7 2） # PUSH（ OPND，‘ 2?）
7 # *（ - 3 7 2 ） # operate (?7?,?-?,?2? )
8 # * ( 3 5 ) # POP ( OPTR )
9 # * 3 5 # operate (?3?,?*?,?5? )
10 # 15 # return ( GETTOP(OPND))
3.2 栈的应用举例
Operandtype evaluateexpression( )
{ Initstack (OPTR); Push (OPTR,?#?);
Initstack (OPND); c=getchar( );
while (c!=?#? || Gettop(optr!=?#?))
{ if ( ! In(c,OP)) { Push(OPND,c); c=getchar( );}
else switch ( Precede( Gettop(OPTR),c))
{ case?<?,Push(OPTR,c); c=getchar( ); break;
case?=?,Pop(OPTR,x); c=getchar( ); break;
case?>?,Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b)); break;
}
}
return Gettop(OPND);
}
3.3 栈与递归的实现
递归的定义,一个函数、过程或数据结构（如广义表、树等），
若在它们定义的内部又出现有本身的应用，则称它们是递归的，
或者是递归定义的。
例,自然数的集合
（ 1） 1是自然数
（ 2）一个自然数的后继是一个自然数。
递归的条件,复杂 简单终结例,1 n=0
n!=
n*(n-1)! n>0
3.3 栈与递归的实现
n!的递归程序及内部实现
main( )
Void fact1(int n,int &r) { …
① { if ( n==0) fact1(3,f)
② r=1; i,…
③ else { fact1(n-1,w); }
④ r=n*w;}
⑤ }
3.3 栈与递归的实现执行语句标号 运行栈的状态（返址,n,r,w）
0 1 ( i 3 &f - )
1,3 2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,3 3 ( 4 1 &w2 - )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,3 4 ( 4 0 &w3 - )
3 ( 4 1 &w2 - )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
1,2 3 ( 4 1 &w2 1 )
2 ( 4 2 &w1 - )
1 ( i 3 &f - )
4,5 2 ( 4 2 &w1 1 )
1 ( i 3 &f - )
4,5 1 ( i 3 &f 2 )
3.3 栈与递归的实现
递归与非递归的转换
void fact2( int n,int &r)
{ top=1; st[1]=n;
while ( st[top]>1)
{ top++; st[top]=st[top-1]-1; }
r=1;
while (top>0)
{ r=st[top]*r; top--; }
}
练习题,
一个栈的入栈序列是 a,b,c,d,e,，则栈的不可能序列是：
(A) edcba (B) decba
(C) dceab (D) abcde
判定一个栈 ST（最多元素为 m0）为空的条件是？为满的条件是？
栈空的条件,ST->top=0
栈满的条件,ST->top=m0
练习题,
指出下列程序的功能
void reverse( )
{ scanf(“%c”,&ch);
if(ch!=?.?) { reverse;
printf(“%c”,ch); }
}
练习题,
McCathy函数定义如下：
M(x)= x-10 x>100
M(M(x+11)) x≤100
（ 1）编写一个递归函数计算给定 x的 M(x)值。
（ 2）编写一个非递归函数计算给定 x的 M(x)值。
int m(int x)
{ int y;
if(x>100) return(x-10);
else { y=m(x+11);
return(m(y));}
}
int m1(int x)
{ int level=1,y;
if(x>100) return(x-10);
else { level++; y=x+11; }
while(level>0)
{ if(y>100) { level--; y=y-10; }
else { level++; y=y+11; }
}
return(y);
}
3.4 队列
队列的定义：
是一种先进先出 (First In First Out,FIFO)的线性表，只允许在表的一端进行插入，而在另一端删除元素。
队列的表示和实现出队列 a1 a2 a3 … a n 入队列队头 队尾顺序队列,用一维数组表示的队列。
链队列,用链表表示的队列。
循环队列,将顺序队列臆造为一个环状的空间。
3.4 队列
data next
Q.front 头结点队头
…
Q.rear ^ 队尾单链队列的存储结构：
Typedef struct Qnode typedef struct
{ Qelemtype data; { Queueptr front;
struct Qnode *next; Queueptr rear;
} Qnode,*Queueptr; } Linkqueue;
链队列：
入队：
Status Enqueue(Linkqueue &Q,Qelemtype e)
{ p=(Queueptr) malloc (sizeof(Qnode));
if (! p) exit (OVERFLOW);
p->data=e; p->next=NULL;
Q.rear->next=p; Q.rear=p;
return OK;
}
出队：
Status Dequeue(LinkQueue &Q,Qelemtype &e)
{ if (Q.front==Q.rear) return ERROR;
p=Q.front->next; e=p->data;
Q.front->next=p->next;
if (Q.rear==p) Q.rear=Q.front;
free(p); return OK;
}
3.4 队列循环队列：
maxsize-1
… 0
Q,rear … 1
Q.front
队空,Q.front=Q.rear
队满,(Q.rear+1) % maxsize=Q.front
3.4 队列循环队列的顺序存储结构：
#define MAXSIZE 100
typedef struct
{ Qelemtype *base;
int front; int rear;
} SeQueue;
入队：
Status Enqueue(SeQueue &Q,Qelemtype e)
{ if ((Q.rear+1) % MAXSIZE==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1) % MAXSIZE;
return OK;
}
出队：
Status Dequeue(SeQueue &Q,Qelemtype &e)
{ if (Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1) % MAXSIZE ;
return OK;
}
练习题,
上机实习题
迷宫求解
八皇后问题迷宫求解
基本思路,从迷宫入口点 (1,1)出发，向四周搜索，记下所有能一步通达的坐标点，依次进行下去，直至到达迷宫出口点 (m,n)为止。这样就找到了从入口到出口的一条最短路径。
需要解决的几个问题：
（ 1）如何表示迷宫？（二维数组,0：表示通； 1：表示不通）
（ 2）如何从某一坐标点出发搜索其四周的邻点？（ v:8个方向）
i=x+move[v].x
y=y+move[v].y
（ 3）如何存储搜索路径？（队列）
(北 )
(x-1,y-1) (x-1,y) (x-1,y+1)
(西 ) (x,y-1) (x,y) (x,y+1) (东 )
(x+1,y-1) (x+1,y) (x+1,y+1)
(南 )
Sq[i],x y pre
1 1 1 0
2 2 2 1 (1,1)
front 3 3 3 2
4 3 1 2 (2,2) (2,4)
5 3 4 3
rear 6 2 4 3 (3,1) (3,3) (3,4)
…
#include <stdio.h>
#define m 8
#define n 10
Struct sqtype
{ int x,y,pre;
} sq[ 200];
int mg[m+1][n+1];
Struct mtype
{ int x; int y;
} move[8];
Void print( int rear)
{ int i; i=rear;
do { printf(“%d,%d”,sq[i].x,sq[i].y);
i=sq[i].rear;
} while(i !=0)
}
Void mglj( )
{ int i,j,x,y,k,front,rear,find;
sq[1].x=1; sq[1].y=1; sq[1].pre=0;
find=0;
front=1; rear=1; mg[1][1]=-1;
While(front<=rear && !find)
{ x=sq[front].x; y=sq[front].y;
for(k=1; k<=8; k++)
{ i=x+move[k].x;
j=y+mov[k].y;
if(mg[i][j]==0)
{ rear++; sq[rear].x=i;
sq[rear].y=j; sq[rear].pre=front;
mg[i][j]=-1;}
if (i==m && j==n)
{ print(rear); find=1; }
}
front++;
}
if (! find) printf(“不存在路径,\n”);
}
第四章 串
串及其运算
串的存储结构
串基本运算的实现
串的应用
4.1 串及其运算
串是一种特殊的线性表，它的结点仅有一个字符组成。它在文字编辑、词法扫描、符号处理和定理证明等领域有广泛的应用。
串的定义串,是由零个或多个字符组成的有限序列。
一般记为,S=?a1,a2,…,a n? n≥0
串名 串值其中,ai可以是字母、数字或其它字符。
长度,串中字符的数目。
空串,长度为零的串。 例：‘’
空格串,由一个或多个空格组成的串。 例：‘ ’
主串,包含子串的串。 例：‘ abcde?
子串,主串中的任意个连续的字符组成的子序列。例：‘ bcd?
4.1 串及其运算位置,字符在序列中的序号。
串相等,当且仅当这两个串的值相等。（长度相等；各个对应位置的字符相等。）
(在程序中通常使用的有串常量和串变量 )
4.1 串及其运算
串的一般表示
（大写字母表示串 S；小写字母表示组成串的字符）
例,S1=?a1,a2,…,a m?
S2=?b1,b2,…,b n?
串的基本运算
⑴ 赋值（ =或 ASSIGN(S,T)）：
例,S=?abc? S=T
⑵ 联接 ( + 或 concat(S,T) )
例,S1+S2=?a1,a2,…,a m b1,b2,…,b n?
concat(S1,S2)
4.1 串及其运算
串的基本运算
⑶ 求串长 ( Length(S) )
例,Length(S1)=m Length(?abc?)=3
Length()=0 Length()=1
⑷ 求子串 ( Substr(S,i,j) )
例,Substr( S1,i,j )=?ai,ai+1,…,a i+j-1?
⑸ 串比较 ( Strcmp(S,T) )
S<T -1
S=T 0
S>T 1
4.1 串及其运算
串插入 ( Insert(S1,i,S2) )
Inseert(S1,i,S2)
=Substr(S1,1,i)+S2+Substr(S1,i+1,Length(S1)-i )
串删除 ( Delete(S1,i,j) )
Delete(S1,i,j)
= Substr(S1,1,i-1)+Substr(S1,i+j,Length(S1)-(i+j-1) )
求子串位置 ( Index(S1,S2) )
Index(?abcdef?,?cde?)=3
串置换 ( Replace(S1,i,j,S2) )
Replace(S1,i,j,S2)
=Substr(S1,1,i-1)+S2+Substr(S1,i+j,Length(S1)-(i+j-1) )
4.2 串的存储结构
串的三种机内表示顺序存储,用一组地址连续的存储单元存储串值的字符序列。
（在做插入、置换和联接操作时，可能产生超界。）
堆分配存储,仍以一组地址连续的存储单元存储串值的字符序列。但它们的存储空间是在程序执行过程中动态分配而得。
（较好的克服上述弊病。）
块链存储,用链式方式存储串值。除设头指针外，
还设一个尾指针，并给出当前串的长度。
4.3 串基本运算的实现
串联接,(顺序存储 )
Status concat(Sstring &T,Sstring S1,Sstring S2)
{ if(S1[0]+S2[0]<=MAXSTRLEN)
{ T[1..s1[0]]=S1[1..S1[0]];
T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];
T[0]=S1[0]+S2[0]; uncut=TRUE;
}
else if(S1[0]<MAXSTRSIZE)
{ T[1..S1[0]]=S1[1..S1[0]];
T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];
T[0]=MAXSTRLEN; uncut=FALSE;
}
else { T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];
uncut=FALSE; } return uncut;
}
4.3 串基本运算的实现
求子串,（顺序存储）
Status SubString(Sstring &Sub,Sstring S,int pos,int len)
{ if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
return ERROR;
Sub[1..len]=S[pos..pos+len-1];
Sub[0]=len; return OK;
}
4.3 串基本运算的实现
串联接,（堆分配存储）
Status Concat (Hstring &T,HString S1,Hstring S2)
{ if (T.ch) free(T.ch);
if (! (T.ch=(char *) malloc ((S1.length+S2.length)
* sizeof(char))))
exit (OVERFLOW);
T.ch[0..s1.length-1]=S1.ch[0..s1.length-1];
T.length=S1.length+S2.length;
T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];
return OK;
}
4.3 串基本运算的实现
求子串：（堆分配存储）
Status SubString (Hstring &Sub,Hstring S,int pos,int len)
{ if (pos<1 || pos>S.length || len<0 || len>S.length-pos+1)
return ERROR;
if (Sub.ch) free(Sub.ch);
if (! len) { Sub.ch=NULL; Sub.length=0; }
else { Sub.ch=(char *) malloc (len*sizeof(char));
Sub.ch[0..len-1]=S[pos-1..pos+len-2];
Sub.length=len;
} return OK;
}
4.3 串基本运算的实现
模式匹配算法模式匹配,子串的定位操作。 （其中子串 T为模式串））
传统匹配方法,从主串 S的第一个字符起和模式串 T的第一个字符比较之，若相等，则继续逐个比较后续字符。否则从主串的第二个字符起再重新和模式串的字符比较，依次类推，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等。
(p80—图 4.3)
4.3 串基本运算的实现
int index(Sstring S,Sstring T,int pos )
{ i=pos; j=1;
while (i<=s[0] && j<=T[0])
{ if (S[i]==T[j]) {++i; ++j;}
else {i=i-j+2; j=1;}
}
if (j>T[0]) return i-T[0];
else return 0; 注,S[0],T[0]分别为 S,T串的长度。
} pos初始值为 1。
4.3 串基本运算的实现
KMP匹配方法（无回朔）,每当一趟匹配过程中出现字符不等时，
不需回朔 i指针，而是利用已经得到的?部分匹配?结果将模式向右?滑动?尽可能远的一段距离后，继续进行比较。 (该法由克努特 -莫里斯 -普拉特同时发现，所以称为 KMP方法。 )
Next函数的计算
0 当 j=1 时
Next[j]= Max{ k|1<k<j 且 ’ p1…p k-1?=?p j-k+1…p j-1?}
1 其它情况例,a b a a b
0 1 1 2 2
(p80—图 4.5)
练习题,
根据模式串的 next函数的定义，推出下列模式串的 next[i]函数值。
例,aaabcd
若 S和 T是用结点大小为 1的单链表存储的两个串，设计一个算法将串 S中首次与串 T匹配的子串逆置。
参考答案：
0 1 1 3 1 1
inverseLink(LinkList &S,LinkList T)
{ ps=qs=S->next; rs=S; pt=T;
while(ps && pt)
{ if(ps->data==pt->data) {ps=ps->next; pt=pt->nexty;}
else { rs=qs; qs=qs->next;
ps=qs; pt=T; }
if (pt==NULL ) { p=qs;
while(p !=ps) { q=p; p=p->next;
q->next=rs->next;
rs->next=q; }
qs->next=ps;
}
}
}
上机实习题
建立词索引表（词典有序），并将生成的词索引表输出。
基本要求,直接输入关键词和书号，生成词索引表。
生成词索引表后，输入一关键词，则输出其有关书号。
较高要求,从书目文件中生成词索引表，并输出到文件中和屏幕上。生成词索引表后，输入一关键词，
则输出其有关书号。（判断关键词，必须与常用词表中的常用词进行比较，不是常用词（ an,a,of,the,to
等），则为关键词。）
第五章 数组和广义表
多维数组
矩阵的压缩存储
广义表
（ 多维数组和广义表则是一种复杂的非线性结构，
它的逻辑特征是一个数据元素可能有多个直接前驱和直接后继。）
5.1 多维数组
多维数组是向量的推广。对于二维数组，可以看成是由 m
个行向量组成的向量，也可以看成是由 n个列向量组成的向量。
a11 a12 … a 1n
A m*n= a21 a22 … a 2n
…
am1 am2… a mn
（二维数组中的每个元素 aij均属于两个向量，第 i行的行向量和第 j列的列向量。）
5.1 多维数组
数组的操作通常有两种,（ 1）给定一组下标，存取相应的数组元素。
（ 2）给定一组下标，修改相应数据元素的某一个或几个数据项的值。
数组的顺序存储结构由于计算机内存结构是一维的，因此，用一维的内存来存放多维数组的数据元素，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中。
通常有两种顺序存储方式：
（ 1）按行优先,a11,a12,…,a 1n,a21,a22,…,a mm
（ 2）按列优先,a11,a21,…,a m1,a12,a22,…,a mm
5.1 多维数组
二维数组按行优先顺序存储的数组元素地址的计算函数：
Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*d
其中：
⑴ 开始结点的存放地址（基地址）。
⑵ 维数。
⑶ 每维的上、下界。
⑷ 每个数组元素所占用的单元数。
5.2 矩阵的压缩存储
压缩存储,为多个相同的非零元素只分配一个存储空间，对零元素不分配存储空间。
特殊矩阵的压缩存储特殊矩阵,是指非零元素或零元素的分布是有一定规律的矩阵。
对称矩阵,满足下列性质的方阵：
a ij=a ji 1≤i,j≤ n
1 5 1 3 a11
5 0 8 0 a21 a22
1 8 9 2 a31 a32 a33
3 0 2 5 4*4 a41 a42 a43 a44
5.2 矩阵的压缩存储
对称矩阵的计算公式：
k= i(i-1)/2+j j≤i
j(j-1)/2+i j > i
5.2 矩阵的压缩存储三角矩阵下三角矩阵,是指上三角（不包括主对角线）中的元素均为常数 C或零。
上三角矩阵,是指下三角（不包括主对角线）中的元素均为常数 C或零。
a11 a12 … a 1n a11 C … C
C a22 … a 2n a21 a22 … C
… …
C C … a mm am1 am2… a mm
(上三角矩阵 ) (下三角矩阵 )
5.2 矩阵的压缩存储
上三角矩阵的计算公式：
k= j(j-1)/2+i j≥i
n(n+1)/2+1 j < i
下三角矩阵的计算公式：
k= (2n-j+2)(j-1)/2+(i-j+1) i≤j
n(n+1)/2+1 i > j
5.2 矩阵的压缩存储
稀疏矩阵的压缩存储是指矩阵中的非零元素远远少于零元素,
稀疏矩阵的压缩存储的压缩存储方法三元组表,若将表示稀疏矩阵的非零元素的三元组按行优先 (或按列优先 )的顺序排列,则得到一个结点均是三元组的线性表,则称该线性表为三元组表,
十字链表,将稀疏矩阵中的非零元素处于行循环链表和列循环链表的十字交叉路口上,则称为十字链表,
5.2 矩阵的压缩存储
三元组表,是稀疏矩阵的一种顺序存储结构。
例,A= 0 5 0 0 8 B= 0 1 0 6
1 0 3 0 0 5 0 -2 0
0 -2 0 0 0 0 3 0 0
6 0 0 0 0 0 0 0 0
按列转置,i j v 8 0 0 0
1 1 2 5 1 2 1
2 1 5 8 1 4 6
3 2 1 1 2 1 5
4 2 3 3 2 3 -2
5 3 2 -2 3 2 3
6 4 1 6 5 1 8
5.2 矩阵的压缩存储
Status Transmatrix(TSMatrix M,TSMatrix &T )
{ T.mu=M.nu; T.nu=M.nu; T.tu=M.tu;
if(T.tu) { q=1;
for(col=1; col<=M.nu; ++col)
for(p=1; p<=M.tu; ++p)
if(M.data[p].j==col)
{ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++q;
}
}
return OK;
}
5.2 矩阵的压缩存储
按 A的行序进行转置
cpot[1]=1
cpot[col]=cpot[col-1]+num[col] 2≤col≤a.nu
cpot的值：
col 1 2 3 4 5
num[col] 2 2 1 0 1
cpot[col] 1 3 5 6 6
5.2 矩阵的压缩存储
Status transmatrix1(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.nu; T.tu=M.tu;
if(T.tu) { for(col=1; col<=M.nu; ++col) num[col]=0;
for(t=1; t<=M.tu; ++t) ++num[M.data[t].j];
cpot[1]=1;
for(col=2; col<=M.nu; ++col)
cpot[col]=cpot[col-1]=num[col-1];
for(p=1; p<=M.tu; ++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
十字链表,
当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组表，而采用链式存储结构表示三元组的线性表更为恰当。
5.2 矩阵的压缩存储
5.3 广义表
广义表的定义是线性表的推广，是 n≥0 个元素 a1,a2,…,an的有限序列，其中 ai或者是原子，或者是广义表。
通常可记作：
LS= （ a1,a2,…,a n） 广义表是递归定义例,E=( ) 长度为 0，空表
L=(a,b) 长度为 2，两个原子
A=(x,L)=(x,(a,b)) 长度为 2，一个原子，一个子表
B=(A,y)=((x,(a,b)),y) 长度为 2，一个子表，一个原子
C=(A,B)=((x,(a,b)),((x,(a,b)),y)) 长度为 2，两个列表
D=(a,D)=(a,(a,(a,(…)))) 长度为 2，是无限列表
5.3 广义表表头,若广义表 LS非空，则 a1是 LS的表头。
表尾,其余元素组成的表 （ a1,a2,…,a n） 称为 LS的表尾。
例,head(L)=a tail(L)=(b)
head(B)=A tail(B)=(y)
head(tail(L))=b tail(tail(L))=( )
注,( )和 (( ))不同,前者是空表,长度为 0;后者是有一个元素的空表,长度为 1
表的深度,是指表展开后所含号的层次,
例如,表 A的深度为 2,表 D的深度为 ∞.
5.3 广义表
三个重要结论：
（ 1）列表的元素可以是子表，而列表的元素还可以是子表,… 。
（ 2）列表可为其它列表所共享。
（ 3）列表可以是一个递归的表，即列表也可以是其本身的一个子表。
5.3 广义表
广义表的存储结构
（通常采用链式存储结构：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。）
参见,p109-图 5.9、图 5.11
5.3 广义表
广义表的递归算法求广义表的深度广义表 LS的深度 DEPTH（ LS） 的递归定义：
基本项：
DEPTH（ LS） =1 当 LS为空表时
DEPTH（ LS） =0 当 LS为原子时归纳项：
DEPTH（ LS） =1+Max{ DEPTH(a i)} n≥1
1≤i≤n
（参见,P114）
5.3 广义表
复制广义表
