补充重点：
1.每个存储结点都包含两部分：数据域和指针域(链域) 2.在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。 3.在链表中设置头结点有什么好处？
头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。 4.如何表示空表？
（1）无头结点时，当头指针的值为空时表示空表； （2）有头结点时，当头结点的指针域为空时表示空表。
5.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？
因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。 6.sizeof(x)—— 计算变量x的长度（字节数）；
malloc(m) — 开辟m字节长度的地址空间，并返回这段空间的首地址； free(p) —— 释放指针p所指变量的存储空间，即彻底删除一个变量。 7.链表的运算效率分析： （1）查找
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 （2） 插入和删除
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。
但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。
例：在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间复杂度为 O（n）
8. 顺序存储和链式存储的区别和优缺点？
顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。 ◆ 顺序表适宜于做查找这样的静态操作； ◆ 链表宜于做插入、删除这样的动态操作。
◆ 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
◆ 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 9. 判断：“数组的处理比其它复杂的结构要简单”，对吗？ 答：对的。因为——
① 数组中各元素具有统一的类型；
② 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。
③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。
10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、列下标 和 元素值 。
11.写出右图所示稀疏矩阵的压缩存储形式。 解：介绍3种存储形式。 法1：用线性表表示：
（( 1,2,12) ，(1,3,9)， (3,1,-3)， (3,5,14)， (4,3,24)， (5,2,18) ，(6,1,15)， (6,4,-7)） 法2：用十字链表表示
用途：方便稀疏矩阵的加减运算 方法：每个非0元素占用5个域
法3：用三元组矩阵表示：
稀疏矩阵压缩存储的缺点：将失去随机存取功能
代码：
1.用数组V来存放26个英文字母组成的线性表（a，b，c，?，z），写出在顺序结构上生成和显示该表的C语言程序。
char V[30];
void build() //字母线性表的生成，即建表操作 {
int i; V[0]='a';
for( i=1; i<=n-1; i++ ) V[i]=V[i-1]+1; }
void display( ) //字母线性表的显示，即读表操作 {
int i;
for( i=0; i<=n-1; i++ ) printf( \ v[i] ); printf( \}
void main(void) //主函数，字母线性表的生成和输出 {
n=26; // n是表长，是数据元素的个数，而不是V的实际下标 build( ); display( ); }
第三章 栈和队列 内容提要：
◆ 从数据结构角度来讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。
◆ 栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。 插入元素到栈顶的操作，称为入栈。
从栈顶删除最后一个元素的操作，称为出栈。 对于向上生成的堆栈:
入栈口诀：堆栈指针top “先压后加” : S[top++]=an+1 出栈口诀：堆栈指针top “先减后弹” : e=S[--top]
◆ 栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。
顺序栈入栈函数PUSH（） status Push(ElemType e) { if(top>M){上溢} else s[top++]=e; }
顺序栈出栈函数POP() status Pop( )
{ if(top=L) { 下溢 }
else { e=s[--top]; return(e);} }
◆ 队列的定义及操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两种存储结构中，都需要队头和队尾两个指针。
队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 链队列
结点类型定义：
typedef Struct QNode{
QElemType data; //元素
Struct QNode *next; //指向下一结点的指针 }Qnode , * QueuePtr ; 链队列类型定义： typedef struct {
QueuePtr front ; //队首指针 QueuePtr rear ; //队尾指针 } LinkQueue; 链队示意图：
① 空链队的特征：front=rear
② 链队会满吗？一般不会，因为删除时有free动作。除非内存不足！ ③ 入队（尾部插入）：rear->next=S; rear=S; 出队（头部删除）：front->next=p->next; 2.顺序队
顺序队类型定义：
#define QUEUE-MAXSIZE 100 //最大队列长度 typedef struct {
QElemType *base; //队列的基址
int front; //队首指针 int rear; //队尾指针 }SqQueue 建队核心语句：
q . base=(QElemType *)malloc(sizeof (QElemType ） * QUEUE_MAXSIZE; //分配空间 顺序队示意图：
循环队列：
队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度（即数据元素个数）：L=（N＋rear－front）% N 1）初始化一个空队列
Status InitQueue ( SqQueue &q ) //初始化空循环队列 q {
q . base=(QElemType *)malloc(sizeof(QElemType） * QUEUE_MAXSIZE); //分配空间
if (!q.base) exit(OVERFLOW);//内存分配失败，退出程序 q.front =q.rear=0; //置空队列 return OK; } //InitQueue;
2）入队操作
Status EnQueue(SqQueue &q, QElemType e) {//向循环队列 q 的队尾加入一个元素 e
if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front )
return ERROR ; //队满则上溢，无法再入队 q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; q.base [ q.rear ] = e; //新元素e入队 return OK; }// EnQueue;
3）出队操作
Status DeQueue ( SqQueue &q, QElemType &e) {//若队列不空，删除循环队列q的队头元素， //由 e 返回其值，并返回OK
if ( q.front = = q.rear ) return ERROR;//队列空 q.front=(q.front+1) % QUEUE_MAXSIZE ; e = q.base [ q.front ] ; return OK; }// DeQueue
◆ 链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。