Linklist *t,*p;
p = (Linklist*)malloc(sizeof(Linklist)); p->data = x; t = head;
while(t->next != NULL && t->next->data < x) t = t->next; if(t == head){
p->next = head->next; head->next = p;
}else if(t->next == NULL){ t->next = p; p->next = NULL; }else{
p->next = t->next; t->next = p; } }
（3）删除
void dele(Linklist *head){ Linklist p ,q; p=head;
while (p->next !=NULL){
if (p->data !=p->next->data) p=p->next; else
{ q=p->next; p->next=q->next; free(q);} } }
（4）逆置
void reverse(Linklist *head){ Linklist *s,*t,*p; p = head; s = p->next;
while(s->next != NULL) { t = s->next; s->next = p; p = s; s = t; }
s->next = p;
head->next->next = NULL; head->next = s; }
5 / 62
2.3 例题
例1：一个一维数组M，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素M[O]的第一个字节的地址是98，则M[3]的第一个字节的地址是 113 。 例2：在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动n-i+1 个元素（或删除第i个元素，需要向前移动 n-i 个元素）。
例3：在单链表中，若*p结点不是末尾结点，在其前或后插入*s结点或删除结点的操作是？
解：在其前插入*s结点：s->next= p->next ; p->next=s; t=p->data; p->data=s->data ; s->data= t ;
在其后插入*s结点：s->next=p->next; p->next=s; 删除其前结点：需要利用遍历
删除其后结点：q = p->next; p->next=q->next; free(q);
删除自身接结点：q=p->next; p->data= q->data ; p->next=q->next ; free(q);
例4：在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是 顺序结构 。
第三章 栈和队列
3.1栈和队列的基本概念
1.栈的概念
栈是只允许在同一端进行插入和删除操作的线性表。允许进行插入和删除的一端叫栈顶(top)，另一端叫栈底(bottum) ，栈中无数据元素时，称为空栈。具有先进后出（FILO）或后进先出（LIFO）的特点。
2.栈的定义
（1）顺序栈
typedef int datatype; # define MAXSIZE 100 typedef struct{
datatype data[MAXSIZE];
int top; } seqstack; seqstack *s;
（2）链栈
typedef int datatype; typedef struct node{
datatype data;
struct node * next; } linkstack; linkstack * top;
top 是栈顶指针，它唯一地确定一个链栈。top=NULL时，该链栈为空栈。链栈中的结点是动态产生的，无需考虑上溢问题。
3.顺序栈操作
（1）判断栈空
int EMPTY(seqstack *s) { return(!s–>top>=0);
6 / 62
}
（2）置空栈
void SETNULL(seqstack *s) {
s–>top=-1;
}
（3）判断栈满
int FULL(seqstack *s) {
return(s–>top==MAXSIZE-1);
} （4）进栈
seqstack * PUSH(seqstack *s，datatype x) {
if (FULL(s))
{ printf(“stack overflow”); return NULL; } s–>top++; s–>data[s–>top]=x;
return s; } （5）出栈
datatype POP(seqstack *s) {
if (EMPTY(s)) {
printf(“stack underflow”); return NULL;
}
s–>top--;
return(s–>data[s–>top+1]);
}
（6）取栈顶
datatype TOP(seqstack *s) {
if (EMPTY(s)) {
printf(“stack is empty”); return NULL;
}
return (s–>data[s–>top]);
}
4.链栈操作
（1）进栈
linkstack *PUSHLSTACK(linkstack *top, datatype x) {
linkstack *p;
p＝(linkstack *)malloc(sizeof(linkstack)); p->data＝x; p->next＝top;
return p; /*返回新栈顶指针*/
} （2）出栈
linkstack *POPLSTACK(linkstack *top, datatype *datap) {
7 / 62
}
linkstack *p; if (top==NULL)
{ printf(“under flow”); return NULL;} datap＝top->data; /*栈顶结点数据存入*datap */ p=top;
top＝ top->next; free(p);
return top; /*返回新栈顶指针*/
5.队列的概念
队列(Queue)也是一种运算受限的线性表。只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。具有先进先出（FIFO）的特点。
6.队列的定义
（1）顺序队列
#define MAXSIZE 100
typedef struct{
datatype data[MAXSIZE]; int front; int rear; }sequeue;
sequeue * sq;
（2）链式队列
typedef struct queuenode{ datatype data;
struct queuenode *next; }QueueNode; typedef struct{
QueueNode *front; QueueNode *rear; }LinkQueue;
7.循环队列
（1）假上溢
在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作，该现象称为假上溢。 （2）循环队列
为了解决假上溢问题，引入了循环队列的概念。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界( MaxSize-1 )时，其加1操作的结果是指向向量的下界0。
（3）队空队满问题
入队时：尾指针向前追赶头指针，出队时：头指针向前追赶尾指针，故队空和队满时头尾指针均相等，无法通过 sq->front= =sq-> rear 来判断队列“空”还是“满”。
解决此问题的方法至少有两种：
1、另设一个布尔变量以区别队列的空和满；
2、少用一个元素空间为代价，入队前，测试尾指针 sq-> rear+1==sq->front ，若相等则认为队满。 （4）常用操作
队空判断： sq->front == sq-> rear
队满判断： sq-> front ==(sq-> rear + 1) % maxSize 入队： sq-> rear = (sq-> rear + 1) % maxSize
8 / 62