内容提要
? 3.1 线形表的基本概念
? 存储结构,顺序存储结构 (顺序表 )和 链式存储结构 (链表 )
? 3.2 顺序表
? 顺序表的定义
? 顺序表的数据类型定义
? 顺序表的基本操作
? 3.3 链表
? 单链表
? 静态链表
? 循环链表
? 双向链表
? 3.4 广义表
3.1 线性表的基本概念
? 线性表,B=(A,R),A={ai|i=1,2,..,n},
R={<ai-1,ai>|i=2,3,…,n}
起始元素,a1
终止元素,an
数据元素的位序,i
线性表的长度,n
空表,n为 0时的线性表
? 常见的操作：
? 存储结构：顺序存储结构 (顺序表 )
链式存储结构 (链表 )
访问元素 删除元素 插入元素
查找元素 排序 合并拆分
3.2 顺序表
顺序表,用一组地址连续的存储单元按线性表的元
素间的逻辑顺序一次存放数据元素。它是一种随即存取
结构。
顺序表的数据类型定义,
数据元素的逻辑顺序与在内存中的存储顺序完全一致，
必需要额外存储数据元素之间的关系
#define MAXSIZE 100 /*顺序表的最大长度 */
typedef struct {
elemtype elem[MAXSIZE];
/*elemtype可以根据实际需要而定 */
int len; /*顺序表当前的长度 */
}SQLIST;
顺序表 (cont’d)
1、顺序表的基本操作 (创建 )
void createsqlist(SQLIST *L)
{
int i;
printf("请输入元素个数 \n");
scanf("%d",&L?len);
printf("请输入 %d个元素 \n");
for(i=0;i<L?len;i++)
scanf("%d",&L?elem[i].key);
/*略去了其他数据项的输入 */
}
(1) 线性表的创建 时间复杂度,O(n)
顺序表 (cont’d)
int Sqsearch(SQLIST L,int aidkey)
{
int j;
for(j=0;j<L.len;j++)
if(L.elem[j].key==aidkey)
return j;
return -1;
}
(2) 顺序查找 时间复杂度,O(n)
1、顺序表的基本操作 (查找 )
顺序表 (cont’d)
1、顺序表的基本操作 (删除 )
void Sqdel(SQLIST *L,int i)
{
int j;
for(j=i+1;j<L?len;j++)
L?elem[j-1]=L?elem[j];
/*上面语句从第 i+1个元素开始，一次前移 */
L?len--;
}
(3) 删除第 i个元素 时间复杂度,O(n)
顺序表 (cont’d)
1、顺序表的基本操作 (插入 )
(4) 在第 i个元素后插入 时间复杂度,O(n)
int Sqins(SQLIST *L,int i,elemtype x)
{ int j;
if(L?len==MAXSIZE)
return -1; /*插入失败 */
for(j=L?len-1;j>=i+1;j--)
L?elem[j+1]=L?elem[j];
L?elem[i+1]=x;
L?len++;
return i+1;
}
顺序表 (cont’d)
2、顺序表的操作实例
【 例 】 线性表的合并 时间复杂度,O(n+m)
void Sqmerge(SQLIST La,SQLIST Lb,
SQLIST *Lc)
{ int i=0,j=0,k=0,m,n;
n=La.len;m=Lb.len;Lc?len=m+n;
while(i<n&&j<m)
if(La.elem[i].key<=Lb.elem[j].key)
Lc?elem[k++]=La.elem[i++];
else Lc?elem[k++]=Lb.elem[j++];
while(i<n)Lc?elem[k++]=La.elem[i++];
while(j<m)Lc?elem[k++]=Lb.elem[j++];
}
将 La或 Lb中
的剩余部分
续接到 Lc
依次将 La,Lb
中的较小者
续接到 Lc中
顺序表 (cont’d)
2、顺序表的操作实例
【 例 】 线性表的合并
例如，设
LA = (3,5,8,11) ? i
LB = (2,6,8,9,11,15,20) ? j
则
LC = (2,3,5,6,8,8,9,11,11,15,20) ? k
3.3 链表 之 单链表
1、单链表定义
? 结点,数据元素与指向后继的指针存储在一起称为结点
? 数据域,结点中存放数据元素的部分
? 指针域,结点中存放指针的部分
? 单链表,结点中只有一个指针的链表
链表需要有个指向首结点的指针来标识；
或者用头结点来标识
a1 a2 a3 an ^
head
a1 a2 a3 an ^L
头结点
链表 之 单链表 (cont’d)
2、单链表的数据类型定义：
typedef struct node
{
elemtype data; /*数据域，存放数据元素 */
struct node *next; /*指针域，指向后继元素 */
}NODE,*NODEPTR,* LINKLIST;
/*同时定义结点和指向结
点的指针 */
#define LEN sizeof(NODE)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (创建 )
LINKLIST createlinklist()
{ LINKLIST L;
NODEPTR p,q;int i,n;elemtype e;
L=(NODEPTR)malloc(LEN);
L?next=NULL;
q=L; scanf("%d",&n);
for(i=1;i<=n;i++)
{ p=(NODEPTR)malloc(LEN);
getelem(&e); p?data=e;
q?next=p;q=p; } //for
q?next=NULL;
return L; }
(1) 线性表的创建 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (遍历 )
void travlist(LINKLIST L)
{ /* L带有头结点 */
NODEPTR p;
p=L?next; /*指向首结点 */
while(p)
{ /*沿着 next链依次访问结点 */
printf("%3d",p?data.key);
p=p?next;
}
printf("\n");
}
(2) 线性表的遍历 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (定位 )
NODEPTR getelemi(LINKLIST L,int i,
NODEPTR *pre) /*L带有头结点 */
{NODEPTR p,q;int j;
if(i<=0)return NULL;
q=L; *pre=NULL;
p=L?next;j=1; /* p指向了第 j个元素 */
while(p&&j<i) /*只要 p不空，向后数 */
{ q=p;
p=p?next;++j; } /*记下 p的前驱 */
if(p) *pre=q;
return p;
}
(3) 定位第 i个元素 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作（定位）
(4)、定位结点 p的前驱 时间复杂度,O(n)
NODEPTR preelem(LINKLIST L,
NODEPTR p)
{
NODEPTR q;
q=L;
while(q&&q->next!=p)
q=q->next;
return q;
}
链表 之 单链表 (cont’d)
3、单链表的基本操作 (删除 )
(5)、删除第 i个结点 时间复杂度,O(n)
int delelem(LINKLIST L,int i)
{
NODEPTR p,pre;
p=getelem(L,i,&pre);
if(p){pre?next=p?next;free(p);return 1;}
else return 0;
}
pre p p
int inselem(LINKLIST L,int i,elemtype e,
int mark) /*mark表示在第 i个结点的前或后 */
{ NODEPTR p,s,pre;
p=getelemi(L,I,&pre);
if(p)
{ s=(NODEPTR)malloc(LEN); s?data=e;
if(mark==1)
{s?next=p?next;p?next=s;}
else {s?next=p;pre?next=s;}
return 1;
}
else return 0; }
链表 之 单链表 (cont’d)
3、单链表的基本操作 (插入 )
(6)、在第 i个结点处插入 时间复杂度,O(n)
pre p
s ①
②
pre p
s ①
②
LINKLIST LkMerge(LINKLIST La,
LINKLIST Lb) /*La,Lb没有头结点 */
{NODEPTR pa,pb,tail; LINKLIST head;
pa=La;pb=Lb;
/*下面 if语句定位新链表的首结点 */
if(pa?data.key<=pb?data.key)
{head=tail=pa;pa=pa?next;}
else {head=tail=pb;pb=pb?next;}
链表 之 单链表 (cont’d)
4、单链表的操作实例
线性表的合并 时间复杂度,O(n+m)
while(pa&&pb)
if(pa->data.key<=pb->data.key)
{tail->next=pa;tail=pa;pa=pa->next;}
else
{tail->next=pb;tail=pb;pb=pb->next;}
tail->next=pa?pa:pb;
/*如果 pa,pb哪个未空,直接续接到 tail后面 */
return head;
}
链表 之 单链表 (cont’d)
随机访问 插入操作 删除操作 内存空间
顺序表
Y es
O (1)
O (n) O (n) 受限
链表
No
O (n)
O (1) O (1) 不受限
5、链表与顺序表对比单
链表 之 静态链表
1、静态链表：用一维数组存放的线性链表
2、静态链表的数据类型定义,
#define MAXSIZE 100
typedef struct node
{
elemtype data;
int next; /*指向后继结点的下标 */
}SLKNODE,SLKLIST[MAXSIZE];
静态链表的结点所占空间一开始就分配
了，结点指针域是个下标值
链表 之 静态链表 (cont’d)
3、静态链表的实例,(用－ 1表示后继是空 )
i 0 1 2 3 4 5 6 7 8 9
S[ i].d ata 88 92 77 54 26 18 74 53 68
S[ i].n ext
2 -1 1 9 8 5 3 4 7
18 26 53 54 68 74
77 88 92 ^
试着按照下面的逻辑关系填写上面的静态链表内存映像
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (初始化 )：
(1)、初始化
void init(SLKLIST s)
{ /*将所有的数组单元连接成空闲结点链
表，头结点的下标是 0*/
int i;
for(i=0;i<MAXSIZE-1;i++)
s[i].next=i+1;
s[MAXSIZE-1].next=0;
/*尾结点的 next值是 0，指向头结点 */
}
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (分配 )：
(2)、结点分配
int mymalloc(SLKLIST s)
{
int i;
i=s[0].next; /*摘取空闲链表的首结点 */
if(i)
s[0].next=s[i].next;
return i;
}
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (回收 )：
(3)、结点回收
void myfree(SLKLIST s,int i)
{
/*将下标是 i的结点插入空闲结点链表
的头结点后面 */
s[i].next=s[0].next;
s[0].next=i;
}
链表 之 静态链表 (cont’d)
5、静态链表的操作实例：
int insort(SLKLIST s)
{ int head,p,q,r,item;
init(s); /*初始化静态链表 */
p=mymalloc(s); /*分配头结点 */
head=p;
s[p].next=0;
while(1)
{ scanf("%d",&item);
if(!item)return head;
r=mymalloc(s);
if(!r)return 0;
s[r].data=item;
q=head;p=s[q].next;
/*开始查找插入位置,p一开
始指向首结点,q指向 p的前
驱 */
while(p&&item>s[p].data)
{ /*应该插到 p的后面，要继续
向后找 */
q=p;p=s[p].next; }
s[r].next=s[q].next; [q].next=r;
}//while
}
将下面输入的整数升序
存放到一个静态链表中 (输
入 0表示结束 )：
88,92,77,54,26,
18,74,53,68
链表 之 循环链表和双向链表
1、循环链表：表尾结点的 next指针指向表头结点的
链表。
2、双向链表：结点存在两个指针域，一个指向后继
结点，另一个指向前驱结点。
3、双向循环链表：
^
^
链表 之 循环链表和双向链表 (cont’d)
4、双向链表的数据类型定义,
typedef struct dbnode
{
elemtype data;
struct dbnode *prior;
struct dbnode *next;
}DBNODE,*DBNODEPTR,*DBLINKLIST;
链表 之 循环链表和双向链表 (cont’d)
双向循环链表的
结点插入算法
int inselem(DBNODEPTR p,elemtype e)
{ /* p指向某双向循环链表中的某个结点,将 e
结点插入到 p的后面 */
DBNODEPTR s,r;
s=(DBNODEPTR)malloc(sizeof(DBNODE));
if(!s)return 0;
s?data=e; /*建立新的结点 */
r=p ? next;
s?next=r; r?prior=s;
p?next=s; s?prior=p;
}
p r
s
链表 之 循环链表和双向链表 (cont’d)
双向循环链表的
结点删除算法
void delelem(DBNODEPTR p)
{ /*p指向某双向循环链表某结点，这个算法
将其从链表中摘除 */
DBNODEPTR q,r;
q=p?prior; r=p?next;
q?next=r; r?prior=q;
/*也可以这样操作：
p?prior?next=p?next;
p?next?prior=p?prior;
*/
}
q p r
3.4 广义表
1、广义表,线性表的推广，当线性表中的数据元素也
可以是个线性表时，这个线性表就是广义表。
原子,广义表中本身不是表的数据元素，用小写字
母表示
子表,广义表中本身也是广义表的数据元素，表名
用大写字母表示
2、广义表的表示方法, 表名 =(item,item….,item)
3、广义表的实例,
A=( )
B=(e)
C=(a,(b,c,d))
D=(A,B,C,f)
广义表 (cont’d)
4、广义表的数据类型定义：
typedef struct glnode
{int tag; /*用于区分原子项还是子表项 */
union
{elemtype data; /*存放原子项的数据元素 */
struct glnode *head; /*指向子表的表头指针 */
}item;
struct glnode *next; /*指向后继结点 */
}*GLIST;
O V E R
,数据结构,
第二章 线性表
? 3.1 线形表的基本概念
? 存储结构,顺序存储结构 (顺序表 )和 链式存储结构 (链表 )
? 3.2 顺序表
? 顺序表的定义
? 顺序表的数据类型定义
? 顺序表的基本操作
? 3.3 链表
? 单链表
? 静态链表
? 循环链表
? 双向链表
? 3.4 广义表
3.1 线性表的基本概念
? 线性表,B=(A,R),A={ai|i=1,2,..,n},
R={<ai-1,ai>|i=2,3,…,n}
起始元素,a1
终止元素,an
数据元素的位序,i
线性表的长度,n
空表,n为 0时的线性表
? 常见的操作：
? 存储结构：顺序存储结构 (顺序表 )
链式存储结构 (链表 )
访问元素 删除元素 插入元素
查找元素 排序 合并拆分
3.2 顺序表
顺序表,用一组地址连续的存储单元按线性表的元
素间的逻辑顺序一次存放数据元素。它是一种随即存取
结构。
顺序表的数据类型定义,
数据元素的逻辑顺序与在内存中的存储顺序完全一致，
必需要额外存储数据元素之间的关系
#define MAXSIZE 100 /*顺序表的最大长度 */
typedef struct {
elemtype elem[MAXSIZE];
/*elemtype可以根据实际需要而定 */
int len; /*顺序表当前的长度 */
}SQLIST;
顺序表 (cont’d)
1、顺序表的基本操作 (创建 )
void createsqlist(SQLIST *L)
{
int i;
printf("请输入元素个数 \n");
scanf("%d",&L?len);
printf("请输入 %d个元素 \n");
for(i=0;i<L?len;i++)
scanf("%d",&L?elem[i].key);
/*略去了其他数据项的输入 */
}
(1) 线性表的创建 时间复杂度,O(n)
顺序表 (cont’d)
int Sqsearch(SQLIST L,int aidkey)
{
int j;
for(j=0;j<L.len;j++)
if(L.elem[j].key==aidkey)
return j;
return -1;
}
(2) 顺序查找 时间复杂度,O(n)
1、顺序表的基本操作 (查找 )
顺序表 (cont’d)
1、顺序表的基本操作 (删除 )
void Sqdel(SQLIST *L,int i)
{
int j;
for(j=i+1;j<L?len;j++)
L?elem[j-1]=L?elem[j];
/*上面语句从第 i+1个元素开始，一次前移 */
L?len--;
}
(3) 删除第 i个元素 时间复杂度,O(n)
顺序表 (cont’d)
1、顺序表的基本操作 (插入 )
(4) 在第 i个元素后插入 时间复杂度,O(n)
int Sqins(SQLIST *L,int i,elemtype x)
{ int j;
if(L?len==MAXSIZE)
return -1; /*插入失败 */
for(j=L?len-1;j>=i+1;j--)
L?elem[j+1]=L?elem[j];
L?elem[i+1]=x;
L?len++;
return i+1;
}
顺序表 (cont’d)
2、顺序表的操作实例
【 例 】 线性表的合并 时间复杂度,O(n+m)
void Sqmerge(SQLIST La,SQLIST Lb,
SQLIST *Lc)
{ int i=0,j=0,k=0,m,n;
n=La.len;m=Lb.len;Lc?len=m+n;
while(i<n&&j<m)
if(La.elem[i].key<=Lb.elem[j].key)
Lc?elem[k++]=La.elem[i++];
else Lc?elem[k++]=Lb.elem[j++];
while(i<n)Lc?elem[k++]=La.elem[i++];
while(j<m)Lc?elem[k++]=Lb.elem[j++];
}
将 La或 Lb中
的剩余部分
续接到 Lc
依次将 La,Lb
中的较小者
续接到 Lc中
顺序表 (cont’d)
2、顺序表的操作实例
【 例 】 线性表的合并
例如，设
LA = (3,5,8,11) ? i
LB = (2,6,8,9,11,15,20) ? j
则
LC = (2,3,5,6,8,8,9,11,11,15,20) ? k
3.3 链表 之 单链表
1、单链表定义
? 结点,数据元素与指向后继的指针存储在一起称为结点
? 数据域,结点中存放数据元素的部分
? 指针域,结点中存放指针的部分
? 单链表,结点中只有一个指针的链表
链表需要有个指向首结点的指针来标识；
或者用头结点来标识
a1 a2 a3 an ^
head
a1 a2 a3 an ^L
头结点
链表 之 单链表 (cont’d)
2、单链表的数据类型定义：
typedef struct node
{
elemtype data; /*数据域，存放数据元素 */
struct node *next; /*指针域，指向后继元素 */
}NODE,*NODEPTR,* LINKLIST;
/*同时定义结点和指向结
点的指针 */
#define LEN sizeof(NODE)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (创建 )
LINKLIST createlinklist()
{ LINKLIST L;
NODEPTR p,q;int i,n;elemtype e;
L=(NODEPTR)malloc(LEN);
L?next=NULL;
q=L; scanf("%d",&n);
for(i=1;i<=n;i++)
{ p=(NODEPTR)malloc(LEN);
getelem(&e); p?data=e;
q?next=p;q=p; } //for
q?next=NULL;
return L; }
(1) 线性表的创建 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (遍历 )
void travlist(LINKLIST L)
{ /* L带有头结点 */
NODEPTR p;
p=L?next; /*指向首结点 */
while(p)
{ /*沿着 next链依次访问结点 */
printf("%3d",p?data.key);
p=p?next;
}
printf("\n");
}
(2) 线性表的遍历 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作 (定位 )
NODEPTR getelemi(LINKLIST L,int i,
NODEPTR *pre) /*L带有头结点 */
{NODEPTR p,q;int j;
if(i<=0)return NULL;
q=L; *pre=NULL;
p=L?next;j=1; /* p指向了第 j个元素 */
while(p&&j<i) /*只要 p不空，向后数 */
{ q=p;
p=p?next;++j; } /*记下 p的前驱 */
if(p) *pre=q;
return p;
}
(3) 定位第 i个元素 时间复杂度,O(n)
链表 之 单链表 (cont’d)
3、单链表的基本操作（定位）
(4)、定位结点 p的前驱 时间复杂度,O(n)
NODEPTR preelem(LINKLIST L,
NODEPTR p)
{
NODEPTR q;
q=L;
while(q&&q->next!=p)
q=q->next;
return q;
}
链表 之 单链表 (cont’d)
3、单链表的基本操作 (删除 )
(5)、删除第 i个结点 时间复杂度,O(n)
int delelem(LINKLIST L,int i)
{
NODEPTR p,pre;
p=getelem(L,i,&pre);
if(p){pre?next=p?next;free(p);return 1;}
else return 0;
}
pre p p
int inselem(LINKLIST L,int i,elemtype e,
int mark) /*mark表示在第 i个结点的前或后 */
{ NODEPTR p,s,pre;
p=getelemi(L,I,&pre);
if(p)
{ s=(NODEPTR)malloc(LEN); s?data=e;
if(mark==1)
{s?next=p?next;p?next=s;}
else {s?next=p;pre?next=s;}
return 1;
}
else return 0; }
链表 之 单链表 (cont’d)
3、单链表的基本操作 (插入 )
(6)、在第 i个结点处插入 时间复杂度,O(n)
pre p
s ①
②
pre p
s ①
②
LINKLIST LkMerge(LINKLIST La,
LINKLIST Lb) /*La,Lb没有头结点 */
{NODEPTR pa,pb,tail; LINKLIST head;
pa=La;pb=Lb;
/*下面 if语句定位新链表的首结点 */
if(pa?data.key<=pb?data.key)
{head=tail=pa;pa=pa?next;}
else {head=tail=pb;pb=pb?next;}
链表 之 单链表 (cont’d)
4、单链表的操作实例
线性表的合并 时间复杂度,O(n+m)
while(pa&&pb)
if(pa->data.key<=pb->data.key)
{tail->next=pa;tail=pa;pa=pa->next;}
else
{tail->next=pb;tail=pb;pb=pb->next;}
tail->next=pa?pa:pb;
/*如果 pa,pb哪个未空,直接续接到 tail后面 */
return head;
}
链表 之 单链表 (cont’d)
随机访问 插入操作 删除操作 内存空间
顺序表
Y es
O (1)
O (n) O (n) 受限
链表
No
O (n)
O (1) O (1) 不受限
5、链表与顺序表对比单
链表 之 静态链表
1、静态链表：用一维数组存放的线性链表
2、静态链表的数据类型定义,
#define MAXSIZE 100
typedef struct node
{
elemtype data;
int next; /*指向后继结点的下标 */
}SLKNODE,SLKLIST[MAXSIZE];
静态链表的结点所占空间一开始就分配
了，结点指针域是个下标值
链表 之 静态链表 (cont’d)
3、静态链表的实例,(用－ 1表示后继是空 )
i 0 1 2 3 4 5 6 7 8 9
S[ i].d ata 88 92 77 54 26 18 74 53 68
S[ i].n ext
2 -1 1 9 8 5 3 4 7
18 26 53 54 68 74
77 88 92 ^
试着按照下面的逻辑关系填写上面的静态链表内存映像
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (初始化 )：
(1)、初始化
void init(SLKLIST s)
{ /*将所有的数组单元连接成空闲结点链
表，头结点的下标是 0*/
int i;
for(i=0;i<MAXSIZE-1;i++)
s[i].next=i+1;
s[MAXSIZE-1].next=0;
/*尾结点的 next值是 0，指向头结点 */
}
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (分配 )：
(2)、结点分配
int mymalloc(SLKLIST s)
{
int i;
i=s[0].next; /*摘取空闲链表的首结点 */
if(i)
s[0].next=s[i].next;
return i;
}
链表 之 静态链表 (cont’d)
4、静态链表的管理算法 (回收 )：
(3)、结点回收
void myfree(SLKLIST s,int i)
{
/*将下标是 i的结点插入空闲结点链表
的头结点后面 */
s[i].next=s[0].next;
s[0].next=i;
}
链表 之 静态链表 (cont’d)
5、静态链表的操作实例：
int insort(SLKLIST s)
{ int head,p,q,r,item;
init(s); /*初始化静态链表 */
p=mymalloc(s); /*分配头结点 */
head=p;
s[p].next=0;
while(1)
{ scanf("%d",&item);
if(!item)return head;
r=mymalloc(s);
if(!r)return 0;
s[r].data=item;
q=head;p=s[q].next;
/*开始查找插入位置,p一开
始指向首结点,q指向 p的前
驱 */
while(p&&item>s[p].data)
{ /*应该插到 p的后面，要继续
向后找 */
q=p;p=s[p].next; }
s[r].next=s[q].next; [q].next=r;
}//while
}
将下面输入的整数升序
存放到一个静态链表中 (输
入 0表示结束 )：
88,92,77,54,26,
18,74,53,68
链表 之 循环链表和双向链表
1、循环链表：表尾结点的 next指针指向表头结点的
链表。
2、双向链表：结点存在两个指针域，一个指向后继
结点，另一个指向前驱结点。
3、双向循环链表：
^
^
链表 之 循环链表和双向链表 (cont’d)
4、双向链表的数据类型定义,
typedef struct dbnode
{
elemtype data;
struct dbnode *prior;
struct dbnode *next;
}DBNODE,*DBNODEPTR,*DBLINKLIST;
链表 之 循环链表和双向链表 (cont’d)
双向循环链表的
结点插入算法
int inselem(DBNODEPTR p,elemtype e)
{ /* p指向某双向循环链表中的某个结点,将 e
结点插入到 p的后面 */
DBNODEPTR s,r;
s=(DBNODEPTR)malloc(sizeof(DBNODE));
if(!s)return 0;
s?data=e; /*建立新的结点 */
r=p ? next;
s?next=r; r?prior=s;
p?next=s; s?prior=p;
}
p r
s
链表 之 循环链表和双向链表 (cont’d)
双向循环链表的
结点删除算法
void delelem(DBNODEPTR p)
{ /*p指向某双向循环链表某结点，这个算法
将其从链表中摘除 */
DBNODEPTR q,r;
q=p?prior; r=p?next;
q?next=r; r?prior=q;
/*也可以这样操作：
p?prior?next=p?next;
p?next?prior=p?prior;
*/
}
q p r
3.4 广义表
1、广义表,线性表的推广，当线性表中的数据元素也
可以是个线性表时，这个线性表就是广义表。
原子,广义表中本身不是表的数据元素，用小写字
母表示
子表,广义表中本身也是广义表的数据元素，表名
用大写字母表示
2、广义表的表示方法, 表名 =(item,item….,item)
3、广义表的实例,
A=( )
B=(e)
C=(a,(b,c,d))
D=(A,B,C,f)
广义表 (cont’d)
4、广义表的数据类型定义：
typedef struct glnode
{int tag; /*用于区分原子项还是子表项 */
union
{elemtype data; /*存放原子项的数据元素 */
struct glnode *head; /*指向子表的表头指针 */
}item;
struct glnode *next; /*指向后继结点 */
}*GLIST;
O V E R
,数据结构,
第二章 线性表
