数据结构 - 图文

[例l.2-1]下面是一个实现上述算法的完整程序 int insq(int i, int x,int V[ ],int M,int *p) {

/*函数定义部分如上，在此省略，以节省篇幅 */ }

void main() {

int M=10, n=4; /* M是数组的大小，n是表中元素个数，即表长 */ int result, k;

static int V[10]={3,5,7,10}; /* 静态数组可以赋初值 */

result=insq(2, 4,V,M,&n);/* 函数调用，在第2个元素前插入4这个新元素 */ if(result==1)

{ printf(\

for(k=0;k

else printf(\}

程序运行结果： SUCCESS ! 3 4 5 7 10

(5) 顺序表删除操作的算法

int delsq(int i, int V[ ], int *p)

{ /*在顺序表中删除第i个元素 */ int n, j; n=*p;

if((i<1)||(i>n))

{ printf(\return (0); } else {

for(j=i;j

3. 线性表顺序存储结构的优缺点

线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。顺序存储结构便于随机存取表中的任一个数据元素,适用于需要频繁查找操作的线性表。但插入和删除操作需要移动

将近一半的元素，尤其当线性表很大时，移动元素导致插入和删除操作效率很低。

另外，顺序存储结构是静态分配的，无法实现动态分配和扩展存储空间。当表中元素是动态变化时，需留出足够空间，这很可能造成浪费，若空间不够会造成表的上溢，导致对表的操作失败。

4. 线性表的链式存储结构

若线性表的总数基本稳定，且很少进行插入和删除，但需要频繁查找操作时，采用顺序存储结构非常方便。但在很多情况下，线性表是动态的，且需要大量的插入或删除操作，就不宜采用顺序存储结构。

例如旅店服务系统的旅客信息管理问题，客流量是动态的，来客人时需把客人信息插入到旅客表中，旅客退房时，需把客人信息从旅客表中删除。对这样的问题应采用下面介绍的链式存储结构。

每个数据元素对应内存一个存储空间，叫存储结点，简称结点。如图1-8所示。

数据域 指针域

图1-8 存储结点示意图 结点可以是两个部分构成，如存放数据的数据域和存放指针的指针域。其中指针域是存放逻辑上相邻的下一个数据元素的物理地址。当然结点也可以是由多哥部分组成的。

线性表的链式存储结构的含义是指逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。例如，线性表为｛ａ，ｂ，ｃ，ｄ｝，则把它们以链式存储结构存储，所对应的存储空间可能为图1-9所示。

物理地址 存储内容 物理地址

1345 a 1400

1346 d ?

…. …

1400 b 1536

… …

c 1346 1536

图1-9 链式存储结构示意图

线性表的链式存储结构可以形象地表示成链表，如图1-10。链表中的每个结点包含数据域和指针域两部分，数据域存放线性表的一个元素，指针域存放其后继结点的地址，最后一个结点的指针为空指针（用∧表示）。具有链式存储结构的线性表也被称为线性链表或单链表。不带头结点的线性链表的逻辑状态如图1-10所示，头指针变量L指向链表中的第一个结点。

d ? c a b L

图1-10不带头结点的线性链表的逻辑示意图

带头结点的线性链表的逻辑状态如图1-11所示，头指针变量L指向链表中的头结点，头结点的指针域指向链表中的第一个结点。头结点的数据域可以根据需要存放有关信息。

d ? c a b L

图1-11带头结点的线性链表的逻辑示意图

5. 链式存储结构的分配方式

线性表的存储空间可以在程序运行期间动态分配，因此在表长不确定时采用链式存储结构较好。如需要往线性表中插入一个数据元素，只需动态地申请一个存储结点，存放有关信息，并把新申请的结点插入到链表的适当位置上。删除一个结点意味着结点将被系统回收，增加到可利用空间的管理区。

在C语言中，malloc函数用来动态申请结点，free函数用来动态回收结点。

6. 线性链表的基本运算

链表的一个重要特点是插入、删除运算灵活方便，不需要移动结点，只要改变结点中指针域的值即可，因此提高了插入和删除运算的效率。链表的查找只能从头指针开始顺序查找，查找时间复杂度为O(n)。

线性链表中结点的类型可用C语言中的“结构指针”来描述： #define NULL 0 /*定义NULL是空地址*/ typedef struct node {

int data;

struct node *link; }JD;

（1）建立链表

建立链表的程序采用动态申请结点的方法，从键盘上输入结点的数据，当学号输入为零时将结束链表的建立。下面的例子显示如何建立学生成绩链表。

[例l.2-2] 建立学生成绩链表 #include “stdio.h” #include “malloc.h” typedef struct student {

int num; float score;

struct student *link; }stu;

stu *creat() {

stu *head; stu *p1,*p2; int n=0;

p1=p2=(stu *)malloc(sizeof(stu)); printf(\

scanf(\ head=NULL;

while(p1->num!=0) {

n=n+1;

if(n==1) head=p1; else p2->link=p1; p2=p1;

p1=(stu *)malloc(sizeof(stu));

scanf(\

}

p2->link=NULL; return(head); }

（2） 线性链表的插入操作

假设要在单链表中的两个数据元素a和b之间插入一个数据元素x，首先将指针p指向结点a，然后生成一个新结点，使其数据域为x，令结点a中的指针域指向新结点x，x的指针域则指向结点b，即完成插入操作。插入结点时指针变化状况如图1-12所示。

void lbcr(JD *p, int x)

{ /* 在指针变量p所指向的结点之后插入新结点*/ JD *s; /*定义指向结点类型的指针*/

s=(JD*)malloc(sizeof(JD)); /* 申请新结点，其地址存到指针变量s中 */ s->data=x;

s->link=p->link; /* 修改s结点指针域 */ p->link=s; /* 修改p结点指针域 */ } (a) 插入前 (b) 插入后

图1-12 线性链表的插入操作示意图

（3）线性链表的删除操作

在如图1-13所示的单链表中删除结点b的操作，只需将结点a的指针域指向结点c即可。

图1-13在单链表中删除结点时指针变化示意图

void lbsc(JD *p ) {

JD *q;

if(p->link!=NULL) {

q=p->link; /* q将指向p的后继结点*/ p->link=q->link; /*修改p结点的指针域*/ free(q); /* 回收删除的结点 */ }

} /*删除p结点的直接后继结点*/