数据结构总复习资料(完整版) 下载本文

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