第二章 线性表
线性表
顺序表
链表
顺序表与链表的比较
2.1 线性表的概念及运算
线性表的逻辑结构
线性表的抽象数据类型定义
2.1.1 线性表的逻辑结构定义,n（?0） 个数据元素的有限序列，记作
（ a1,… ai-1,ai,ai+1,…,an）
其中,ai是表中数据元素,n 是表长度。
特点,
同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
2.1.2 线性表的抽象数据类型定义
ADT LinearList{
数据元素,D={ai| ai∈ D0,i=1,2,…,n,n≥0,D0为某一数据对象 }
关系,Ｓ＝ {<ai,ai+1> | ai,ai+1∈ D0,i=1,2,…,n -1}
基本操作：
（ 1） InitList（ L
（ 2） DestroyList(L)
（ 3） ClearList(L)
（ 4） EmptyList（ L
（ 5） ListLength（ L
（ 6） Locate(L,e)
（ 7） GetData(L,i)
（ 8） InsList(L,i,e)
（ 9） DelList(L,i,&e)
} ADT LinearList
操作 操作前提 操作结果
InitList（ L L为未初始化线性表 将 L初始化为空表
DestroyList(L) 线性表 L已存在 将 L销毁
ClearList(L) 线性表 L已存在 将表 L置为空表
EmptyList（ L） 线性表 L已存在 如果 L为空表则返回真,否则返回假
ListLength（ L） 线性表 L已存在 如果 L为空表则返回 0,否则返回表中的元素个数
Locate(L,e) 表 L已存在,e为合法元素值如果 L中存在元素 e,则将“当前指针”指向元素 e所在位置并返回真，
否则返回假
GetData(L,i) 表 L存在,且 i值合法，即1≤i≤ListLength （ L） 返回线性表 L中第 i个元素的值
InsList(L,i,e) 表 L已存在,e为合法元素值且 1≤i≤ListLength(L)+1 在 L中第 i个位置插入新的数据元素 e,L的长度加 1
DelList(L,i,&e) 表 L已存在且非空，1≤i≤ListLength(L) 删除 L的第 i个数据元素,并用 e返回其值,L的长度减 1
2.2 线性表的顺序存储
线性表的顺序存储结构
线性表顺序存储结构上的基本运算
2.2.1 线性表的顺序存储结构定义,用一组地址连续的存储单元依次存储线性表中的各个元素。
存储结构,数组。
特点,线性表的顺序存储方式。
存取方式,顺序存取
45 89 90 67 40 78
0 1 2 3 4 5
顺序存储结构示意图内存中连续分布相同大小的存储单元，依靠存储位置的物理相邻来体现线性表元素的逻辑关系顺序表顺序表的存储方式：
LOC(a i+1) = LOC( a i ) + l
LOC(a i) = LOC(a1) + (i-1) * l
a1 a2 … a i … … … an
1 2 … i … … … n
a a+l … a+(i -1)*l … … … a+(n -1)*l idle
l 为每个元素所占存储空间大小顺序表（ SeqList） 的类型定义
#define MAXSIZE 100 //最大允许长度
typedef int ElemType;
typedef struct {
ElemType elem[MAXSIZE]; //存储空间
int last; //记录线性表中最后一个元素在数组
//elem[]中的位置（下标值），空表置为 -1
}SeqList;
2.2.2 线性表顺序存储结构上的基本运算
初始化
查找
插入
删除
求长度
void InitList ( SeqList *pL ) {
pL->last = -1;
}
初始化
InitList（ L
操作前提,L为未初始化线性表。
操作结果,将 L初始化为空表。
SeqList L;
InitList（ &L
按序号查找,取线性表中第 i个元素，若存在则返回该元素值，否则返回 -1
ElemType GetData ( SeqList *pL,int i )
{
if( i>0 && i<=pL->last+1)
return pL->elem[i-1];
else
return -1;
}
查找
按值查找,找 e 在表中的位置，若查找成功，返回表项的位置，否则返回 -1
int Locate ( SeqList *pL,ElemType e )
{
int i = 0;
while ( i <= pL->last && pL->elem[i] != e )
i++;
if ( i <= pL->last )
return i;
else
return -1;
}
查找按值查找,判断 e是否在表中
int IsIn ( SeqList *pL,ElemType e )
{
int i = 0,found=0;
while ( i <= pL->last && !found )
if(pL->elem[i] != e )
i++;
else
found=1;
return found;
}
按值查找,寻找 x的后继
int Next ( SeqList *pL,ElemType x )
{
int i = Locate(pL,x);
if ( i >=0 && i < pL->last ) return i+1;
else return -1;
}
寻找 x的前驱
int Precursor ( SeqList *pL,ElemType x )
{
int i = Locate(pL,x);
if ( i >0 && i <= pL->last ) return i-1;
else return -1;
}
求表的长度
int Length ( SeqList *pL ) {
return pL->last+1;
}
插入
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
顺序表插入时，平均数据移动次数 AMN在各表项插入概率相等时
Average Move Number
顺序表的插入
int InsList ( SeqList *pL,ElemType x,int i )
{
//在表中第 i 个位置插入新元素 x
if (i < 0 || i > pL->last+1 || pL->last == MAXSIZE-1)
return 0; //插入不成功
else {
for ( int j = pL->last+1; j > i; j-- )
pL->elem[j] = pL->elem[j -1];
pL->elem [i] = x; pL->last++;
return 1; //插入成功
}
}
注意：此算法中假设插入位置 i从 0到 pL->last+1为合法
删除
1
0
2
1
2
1)(11)(1=
n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 6316
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
顺序表删除平均数据移动次数 AMN在各表项删除概率相等时
顺序表的删除
int DelList ( SeqList *pL,int i,ElemType *px )
{
//在表中删除已有的第 i个元素
if( (i<1) || (i>pL->last+1) ) //判断位置是否正确
return 0;
for ( int j = i; j <= pL->last; j++ )
pL->elem[j-1] = pL->elem[j];
pL->last--;
return 1; //成功删除
}
注意：此算法中假设删除位置 i从 1到 pL->last+1为合法例 2-1
有两个顺序表 LA和 LB,其元素均为非递减有序排列,编写一个算法,将它们合并成一个顺序表 LC,要求 LC也是非递减有序排列 。 例如 LA=(2,2,3),LB=(1,3,3,4),则 LC=(1,2,2,3,3,
3,4)。
算法思想,设表 LC是一个空表,为使 LC也是非递减有序排列,可设两个指针 i,j分别指向表 LA和 LB中的元素,若
LA.elem［ i］ >LB.elem［ j］,则当前先将 LB.elem［ j］ 插入到表 LC中 ; 若 LA.elem［ i］ ≤LB.elem［ j］,则当前先将 LA.elem
［ i］ 插入到表 LC中,如此进行下去,直到其中一个表被扫描完毕,然后再将未扫描完的表中剩余的所有元素放到表 LC中 。
void merge(SeqList *LA,SeqList *LB,SeqList *LC)
{
int i,j,k;
i=0; j=0; k=0;
while(i<=LA->last&&j<=LB->last)
if(LA->elem［ i］ <=LB->elem［ j］ )
{ LC->elem［ k］ =LA->elem［ i］ ; i++; k++; }
else
{ LC->elem［ k］ =LB->elem［ j］ ; j++; k++; }
while (i<=LA->last) /* 当表 LA比表 LB长时,则将表 LA余下的元素赋给表 LC */
{
LC->elem［ k］ =LA->elem［ i］ ; i++; k++;
}
while(j<=LB->last) /* 当表 LB比表 LA长时,则将表 LB余下的元素赋给表 LC */
{
LC->elem［ k］ =LB->elem［ j］ ; j++; k++;
}
LC->last=LA->last + LB->last + 1;
}
顺序表的应用,集合的“并”运算
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
集合的“交”运算
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
2.3 线性表的链式存储链表是线性表的链接存储表示
单链表
静态链表
循环链表
双向链表
2.3.1 单链表 (Singly Linked List)
定义,用一组 地址任意 的存储单元存放线性表中的数据元素。
数据域 指针域
ZHANG 13
WANG 1
LI null
ZHAO 37
WU 7
ZHOU 19
SUN 25
存储地址
1
7
13
19
25
31
37
31
头指针每个元素由结点 (Node)构成,它包括两个域,数据域 Data和指针域 Next
data next
存储结构,链式存储结构特点,存储单元可以不连续。
存取方式,顺序存取。
Node
单链表结构带 表头结点 的单链表
表头结点 位于表的最前端，本身不带数据，仅标志表头。
设置表头结点的目的,
简化链表操作的实现。
非空表 空表
^ana1first first ^
单链表的类型定义
typedef char ElemType;
typedef struct node { //链表结点
ElemType data; //结点数据域
struct node * next; //结点链域
} Node,*LinkList; // LinkList为结点指针类型
插入（三种情况，不带头结点）
第一种情况：在第一个结点前插入
newnode->next = first ;
first = newnode;
头插法
first
newnode newnode
first
（插入前） （插入后）
2.3.2 单链表的基本运算
第二种情况：在链表中间插入
newnode->next = p->next;
p->next = newnode；
(插入前 ) (插入后 )
newnode
p
newnode
p
第三种情况：在链表末尾插入
newnode->next = p->next;
p->next = newnode；
p
(插入前 ) (插入后 )
newnode newnode
p
尾插法算法描述
int Insert ( LinkList *first,int x,int i )
{ //在链表第 i 个结点处插入新元素 x
Node * p = *first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->next; k++; } //找第 i-1个结点
if ( p == NULL && *first != NULL ) {
printf (,无效的插入位置 !\n” ); //终止插入
return 0;
}
Node * newnode = (Node *) malloc ( sizeof (Node) ); //创建新结点
newnode->data = x;
if ( *first == NULL || i == 1 ) { //插入空表或非空表第一个结点之前
newnode->next = *first;
*first = newnode; //新结点成为第一个结点
}
else { //插在表中间或末尾
newnode->next = p->next;
p->next = newnode;
}
return 1;
}
插入
q->next = p->next;
p->next = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
插入前 插入后 插在表头带头结点链表插入
q q
插入p p
插在表中或表尾
int Insert (LinkList first,ElemType x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
Node * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
Node * newnode = //创建新结点
(Node *) malloc (sizeof (Node) );
newnode->data = x;
newnode->next = p->next; //链入
p->next = newnode;
return 1;
}
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; Node *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (Node));
head->next = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (Node *) malloc (sizeof(Node));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
算法 2.5Linklist CreateFromHead(){
LinkList L;
Node *s;
char c;
int flag=1;
/* 设置一个标志变量 flag，初值为 1，当输入,$”时，将 flag置为 0，建表结束 */
L=(LinkList)malloc(sizeof(Node)); /* 为头结点分配存储空间 */
L->next=NULL;
while(flag)
{ c=getchar();
if(c! =′$′)
{
s=(Node*)malloc(sizeof(Node)); /* 为读入的字符分配存储空间 */
s->data=c;
s->next=L->next;
L->next=s;
}
else flag=0;
}
return L;
}
后插法建立单链表
每次将新结点加在链表的表尾；
尾指针 r,总是指向表中最后一个结点，新结点插在它的后面；
^
q
first ^
r
^first ^
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (Node));
Node *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (Node *) malloc (sizeof(Node));
q->data = ch; //建立新结点
r ->next = q; r =q; //插入到表末端
}
r ->next = NULL;
return head;
}
算法 2.6LinkList CreateFromTail(){ /*将新增的字符追加到链表的末尾 */
LinkList L;
Node *r,*s;
char c;
int flag=1;/*设置一个标志，初值为 1，当输入,$”时,flag为 0，建表结束 */
L=(Node*)malloc(sizeof(Node)); /*为头结点分配存储空间 */
L->next=NULL;
r=L;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点 */
while(flag)
{
c=getchar();
if(c!='$') {
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else{
flag=0;
r->next=NULL;/*将最后一个结点的 next链域置为空，表示链表的结束 */
}
}
return L;
}
删除在单链表中删除 ai结点
q = p->link;
p->link = q->link;
删除前删除后?ai-1 ai ai+1
p q
p
ai-1 ai+1ai
first 如果要删除单链表的第一个结点，则指针 first的值必须改变。
int Delete ( LinkList *first,int i )
{ //在链表中删除第 i 个结点
Node *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = *first; *first = (*first)->next; }
else
{ p = *first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->next; k++; } //找第 i-1个结点
if ( p == NULL || p->next == NULL ) {//找不到第 i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->next;
p->next = q->next;
}
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
删除 q = p->link;
p->link = q->link;
delete q;
删除前
first
(非空表） (空表）
first
^
first
p q
^
p q
first
删除后带头结点的单链表
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
Node * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->next == NULL)
return 0;//i值不合理或空表
q = p->next;
p->next = q->next; //删除结点
free ( q ); //释放
return 1;
}
单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
Node *q;
while ( first->next != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->next; first->next = q->next;
free( q ); //释放
}
}
计算单链表长度
int Length ( LinkList first ) {
Node *p = first->next; //指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->next; count++;
}
return count;
}
按值查找
Node * Find ( LinkList first,ElemType value ) {
//在链表中从头搜索其数据值为 value的结点
Node * p = first->next;
//指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->next;
return p;
}
按序号查找（定位）
Node * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL;
Node * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->next; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
2.3.3 循环链表 (Circular List)
特点,最后一个结点的 link 指针不为 NULL，而是指向头结点。只要已知表中某一结点的地址，
就可搜寻所有结点的地址 。
存储结构,链式存储结构带表头结点的循环链表
an-1first a1a0
first
(空表 )
(非空表 )
循环链表的插入约瑟夫问题
用循环链表求解约瑟夫问题
n 个人围成一个圆圈，首先第 2个人从 1开始一个人一个人顺时针报数,报到第 m个人，令其出列。然后再从下一个人开始，从 1顺时针报数，
报到第 m个人，再令其出列,…,如此下去,
直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 3 m = 8
约瑟夫问题的解法
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
2.3.4 双向链表 (Doubly Linked List)
双向链表结点结构,
prior data next
指向直接前驱 指向直接 后继非空表 空表
firstfirst
双向循环链表的定义
typedef int ListData;
typedef struct dnode {
ListData data;
struct dnode * prior,* next;
} DblNode;
typedef DblNode * DblList;
建立空的双向循环链表
void CreateDblList ( DblList *first ) {
*first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ printf (,存储分配错 !\n” ); exit (1); }
*first->prior = *first->next = *first;
//表头结点的链指针指向自己
}
计算双向循环链表的长度
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
双向循环链表的插入 (非空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
在结点 *p 后插入 25
first
first
31 48 15
p
p
31 48 25 15
q
双向循环链表的插入 (空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
在结点 *p 后插入 25
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
(非空表 )
删除 48
first
first
31 48 15
p
31 15
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
first31
p删除 31
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//删除结点 p
free ( p ); //释放
return 1;
}
1
ZHANG 2
WANG 6
LI 5
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
修改前 （插入 chen,删除 zhao)修改后用一维数组描述线性链表静态链表
定义
#define MaxSize 100 //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
链表空间初始化
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = 1;
SL.newptr = 1; //当前可分配空间从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1; //构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
在静态链表中查找具有给定值的结点
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link; //指针 p 指向链表第一个结点
while ( p != -1 )//逐个查找有给定值的结点
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
return p;
}
在静态链表中查找第 i 个结点
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1;//参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {//循环查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
在静态链表第 i 个结点处插入一个新结点
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
在静态链表中释放第 i 个结点
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
2.4 一元多项式的表示及其相加
多项式的链表
struct Polynode
{
int coef;
int exp;
struct Polynode *next;
} Polynode,* Polylist;
优点是：
– 多项式的项数可以动态地增长，不存在存储溢出问题。
– 插入、删除方便，不移动元素。
通过键盘输入一组多项式的系数和指数,以输入系数 0为结束标志,并约定建立多项式链表时,总是按指数从大到小的顺序排列 。
算法描述,从键盘接受输入的系数和指数； 用尾插法建立一元多项式的链表 。
Polylist polycreate( )
{
Polynode *head,*rear,*s;
int c,e;
h=(Polynode*)malloc(sizeof(Polynode)); /*建立多项式的头结点 */
rear=head; /* rear 始终指向单链表的尾,便于尾插法建表 */
scanf(″%d,%d″,&c,&e); /*键入多项式的系数和指数项 */
while(c! =0) /*若 c=0,则代表多项式的输入结束 */
{ s=(Polynode*)malloc(sizeof(Polynode)); /*申请新的结点 */
s->coef=c ;
s->exp=e ;
rear->next=s ; /*在当前表尾做插入 */
rear=s;
scanf(″%d,%d″,&c,&e);
}
rear->next=NULL; /*将表的最后一个结点的 next置 NULL,以示表结束 */
return(head);
}
多项式链表的相加多项式 A(x)=7+3x+9x8+5x17 多项式 B(x)=8x+22x7-9x8
－ 1 7 0 3 1 9 8 5 17p o l y a
－ 1 8 1 22 7 － 9 8p o l y b － 1 7 0 11 1 9 8 5 17p o l y a
－ 1 8 1 22 7 － 9 8
因 3x ＋ 8x ＝ 1 1 x而得因 9x
8
＋ ( － 9 ) x
8
＝ 0 而被删除并释放合并后释放
p o l y b 的头结点因 3x ＋ 8x ＝ 1 1 x 被并到
p o l y a 中,该结点被删除并释放
void polyadd(Polylist polya; Polylist polyb)
/*此函数用于将两个多项式相加,然后将和多项式存放在多项式 polya中,
并将多项式 ployb删除 */
{
Polynode *p,*q,*pre; *temp;
int sum;
p=polya->next ; // 令 p和 q分别指向 polya和 polyb多项式链表中
q=polyb->next ; //的第一个结点 */
pre=polya; /* pre指向和多项式的尾结点 */
while（ p! =NULL && q! =NULL） /* 当两个多项式均未扫描结束时 */
{ if （ p->exp< q->exp）
{ pre->next=p; pre=pre->next; p=p->next；
}
else if ( p->exp==q->exp） /*若指数相等,则相应的系数相加 */
{ sum=p->coef + q->coef ;
if (sum!=0)
{ p->coef=sum; pre->next=p; pre=pre->next;
p=p->next; temp=q->next; free(q); q=temp ;
}
else
{ temp=p->next ; free(p); p=temp ;
temp=q->next; free(q); q=temp ;
}
}
//如果 p指向的多项式项的指数小于 q的指数,将 p结点加入到和多项式中
/* 若系数和为零,则删除结点 p与 q,并将指针指向下一个结点 */
else
{ pre->next=q; pre=pre->next; /* 将 q结点加入到和多项式中 */
q =q->next;
} // if
} // while结束
if(p! =NULL) /* 多项式 A中还有剩余,则将剩余的结点加入到和多项式中 */
pre->next=p;
else /* 否则,将 B中的结点加入到和多项式中 */
pre->next=q;
}
//如果 p指向的多项式项的指数大于 q的指数,将 q结点加入到和多项式中顺序表与链表的比较基于空间的比较
存储分配的方式
顺序表的存储空间是静态分配的
链表的存储空间是动态分配的
存储密度 = 结点数据本身所占的存储量 /结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表是顺序存取的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针结 束
线性表
顺序表
链表
顺序表与链表的比较
2.1 线性表的概念及运算
线性表的逻辑结构
线性表的抽象数据类型定义
2.1.1 线性表的逻辑结构定义,n（?0） 个数据元素的有限序列，记作
（ a1,… ai-1,ai,ai+1,…,an）
其中,ai是表中数据元素,n 是表长度。
特点,
同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。
除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。
2.1.2 线性表的抽象数据类型定义
ADT LinearList{
数据元素,D={ai| ai∈ D0,i=1,2,…,n,n≥0,D0为某一数据对象 }
关系,Ｓ＝ {<ai,ai+1> | ai,ai+1∈ D0,i=1,2,…,n -1}
基本操作：
（ 1） InitList（ L
（ 2） DestroyList(L)
（ 3） ClearList(L)
（ 4） EmptyList（ L
（ 5） ListLength（ L
（ 6） Locate(L,e)
（ 7） GetData(L,i)
（ 8） InsList(L,i,e)
（ 9） DelList(L,i,&e)
} ADT LinearList
操作 操作前提 操作结果
InitList（ L L为未初始化线性表 将 L初始化为空表
DestroyList(L) 线性表 L已存在 将 L销毁
ClearList(L) 线性表 L已存在 将表 L置为空表
EmptyList（ L） 线性表 L已存在 如果 L为空表则返回真,否则返回假
ListLength（ L） 线性表 L已存在 如果 L为空表则返回 0,否则返回表中的元素个数
Locate(L,e) 表 L已存在,e为合法元素值如果 L中存在元素 e,则将“当前指针”指向元素 e所在位置并返回真，
否则返回假
GetData(L,i) 表 L存在,且 i值合法，即1≤i≤ListLength （ L） 返回线性表 L中第 i个元素的值
InsList(L,i,e) 表 L已存在,e为合法元素值且 1≤i≤ListLength(L)+1 在 L中第 i个位置插入新的数据元素 e,L的长度加 1
DelList(L,i,&e) 表 L已存在且非空，1≤i≤ListLength(L) 删除 L的第 i个数据元素,并用 e返回其值,L的长度减 1
2.2 线性表的顺序存储
线性表的顺序存储结构
线性表顺序存储结构上的基本运算
2.2.1 线性表的顺序存储结构定义,用一组地址连续的存储单元依次存储线性表中的各个元素。
存储结构,数组。
特点,线性表的顺序存储方式。
存取方式,顺序存取
45 89 90 67 40 78
0 1 2 3 4 5
顺序存储结构示意图内存中连续分布相同大小的存储单元，依靠存储位置的物理相邻来体现线性表元素的逻辑关系顺序表顺序表的存储方式：
LOC(a i+1) = LOC( a i ) + l
LOC(a i) = LOC(a1) + (i-1) * l
a1 a2 … a i … … … an
1 2 … i … … … n
a a+l … a+(i -1)*l … … … a+(n -1)*l idle
l 为每个元素所占存储空间大小顺序表（ SeqList） 的类型定义
#define MAXSIZE 100 //最大允许长度
typedef int ElemType;
typedef struct {
ElemType elem[MAXSIZE]; //存储空间
int last; //记录线性表中最后一个元素在数组
//elem[]中的位置（下标值），空表置为 -1
}SeqList;
2.2.2 线性表顺序存储结构上的基本运算
初始化
查找
插入
删除
求长度
void InitList ( SeqList *pL ) {
pL->last = -1;
}
初始化
InitList（ L
操作前提,L为未初始化线性表。
操作结果,将 L初始化为空表。
SeqList L;
InitList（ &L
按序号查找,取线性表中第 i个元素，若存在则返回该元素值，否则返回 -1
ElemType GetData ( SeqList *pL,int i )
{
if( i>0 && i<=pL->last+1)
return pL->elem[i-1];
else
return -1;
}
查找
按值查找,找 e 在表中的位置，若查找成功，返回表项的位置，否则返回 -1
int Locate ( SeqList *pL,ElemType e )
{
int i = 0;
while ( i <= pL->last && pL->elem[i] != e )
i++;
if ( i <= pL->last )
return i;
else
return -1;
}
查找按值查找,判断 e是否在表中
int IsIn ( SeqList *pL,ElemType e )
{
int i = 0,found=0;
while ( i <= pL->last && !found )
if(pL->elem[i] != e )
i++;
else
found=1;
return found;
}
按值查找,寻找 x的后继
int Next ( SeqList *pL,ElemType x )
{
int i = Locate(pL,x);
if ( i >=0 && i < pL->last ) return i+1;
else return -1;
}
寻找 x的前驱
int Precursor ( SeqList *pL,ElemType x )
{
int i = Locate(pL,x);
if ( i >0 && i <= pL->last ) return i-1;
else return -1;
}
求表的长度
int Length ( SeqList *pL ) {
return pL->last+1;
}
插入
22
1)(
1)(
1
0)1(
0 1
1
)(
1
1
=
nnn
n
n
n
i n
in
n
A M N
25 34 57 16 48 09 63
0 1 2 3 4 5 6 7
50插入 x
25 34 57 50 16 48 09 63
0 1 2 3 4 5 6 7
50
i
顺序表插入时，平均数据移动次数 AMN在各表项插入概率相等时
Average Move Number
顺序表的插入
int InsList ( SeqList *pL,ElemType x,int i )
{
//在表中第 i 个位置插入新元素 x
if (i < 0 || i > pL->last+1 || pL->last == MAXSIZE-1)
return 0; //插入不成功
else {
for ( int j = pL->last+1; j > i; j-- )
pL->elem[j] = pL->elem[j -1];
pL->elem [i] = x; pL->last++;
return 1; //插入成功
}
}
注意：此算法中假设插入位置 i从 0到 pL->last+1为合法
删除
1
0
2
1
2
1)(11)(1=
n
i
nnn
n
in
n
A M N
25 34 57 50 16 48 09 6316
删除 x
25 34 57 50 48 09 63
0 1 2 3 4 5 6 7
顺序表删除平均数据移动次数 AMN在各表项删除概率相等时
顺序表的删除
int DelList ( SeqList *pL,int i,ElemType *px )
{
//在表中删除已有的第 i个元素
if( (i<1) || (i>pL->last+1) ) //判断位置是否正确
return 0;
for ( int j = i; j <= pL->last; j++ )
pL->elem[j-1] = pL->elem[j];
pL->last--;
return 1; //成功删除
}
注意：此算法中假设删除位置 i从 1到 pL->last+1为合法例 2-1
有两个顺序表 LA和 LB,其元素均为非递减有序排列,编写一个算法,将它们合并成一个顺序表 LC,要求 LC也是非递减有序排列 。 例如 LA=(2,2,3),LB=(1,3,3,4),则 LC=(1,2,2,3,3,
3,4)。
算法思想,设表 LC是一个空表,为使 LC也是非递减有序排列,可设两个指针 i,j分别指向表 LA和 LB中的元素,若
LA.elem［ i］ >LB.elem［ j］,则当前先将 LB.elem［ j］ 插入到表 LC中 ; 若 LA.elem［ i］ ≤LB.elem［ j］,则当前先将 LA.elem
［ i］ 插入到表 LC中,如此进行下去,直到其中一个表被扫描完毕,然后再将未扫描完的表中剩余的所有元素放到表 LC中 。
void merge(SeqList *LA,SeqList *LB,SeqList *LC)
{
int i,j,k;
i=0; j=0; k=0;
while(i<=LA->last&&j<=LB->last)
if(LA->elem［ i］ <=LB->elem［ j］ )
{ LC->elem［ k］ =LA->elem［ i］ ; i++; k++; }
else
{ LC->elem［ k］ =LB->elem［ j］ ; j++; k++; }
while (i<=LA->last) /* 当表 LA比表 LB长时,则将表 LA余下的元素赋给表 LC */
{
LC->elem［ k］ =LA->elem［ i］ ; i++; k++;
}
while(j<=LB->last) /* 当表 LB比表 LA长时,则将表 LB余下的元素赋给表 LC */
{
LC->elem［ k］ =LB->elem［ j］ ; j++; k++;
}
LC->last=LA->last + LB->last + 1;
}
顺序表的应用,集合的“并”运算
void Union ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
for ( int i = 0; i < m; i++ ) {
int x = GetData ( B,i ); //在 B中取一元素
int k = Find (A,x); //在 A中查找它
if ( k == -1 ) //若未找到插入它
{ Insert ( A,x,n ); n++; }
}
}
集合的“交”运算
void Intersection ( SeqList &A,SeqList &B ) {
int n = Length ( A );
int m = Length ( B );
int i = 0;
while ( i < n ) {
int x = GetData ( A,i ); //在 A中取一元素
int k = Find ( B,x ); //在 B中查找它
if ( k == -1 ) { Delete ( A,i ); n--; }
else i++; //未找到在 A中删除它
}
}
2.3 线性表的链式存储链表是线性表的链接存储表示
单链表
静态链表
循环链表
双向链表
2.3.1 单链表 (Singly Linked List)
定义,用一组 地址任意 的存储单元存放线性表中的数据元素。
数据域 指针域
ZHANG 13
WANG 1
LI null
ZHAO 37
WU 7
ZHOU 19
SUN 25
存储地址
1
7
13
19
25
31
37
31
头指针每个元素由结点 (Node)构成,它包括两个域,数据域 Data和指针域 Next
data next
存储结构,链式存储结构特点,存储单元可以不连续。
存取方式,顺序存取。
Node
单链表结构带 表头结点 的单链表
表头结点 位于表的最前端，本身不带数据，仅标志表头。
设置表头结点的目的,
简化链表操作的实现。
非空表 空表
^ana1first first ^
单链表的类型定义
typedef char ElemType;
typedef struct node { //链表结点
ElemType data; //结点数据域
struct node * next; //结点链域
} Node,*LinkList; // LinkList为结点指针类型
插入（三种情况，不带头结点）
第一种情况：在第一个结点前插入
newnode->next = first ;
first = newnode;
头插法
first
newnode newnode
first
（插入前） （插入后）
2.3.2 单链表的基本运算
第二种情况：在链表中间插入
newnode->next = p->next;
p->next = newnode；
(插入前 ) (插入后 )
newnode
p
newnode
p
第三种情况：在链表末尾插入
newnode->next = p->next;
p->next = newnode；
p
(插入前 ) (插入后 )
newnode newnode
p
尾插法算法描述
int Insert ( LinkList *first,int x,int i )
{ //在链表第 i 个结点处插入新元素 x
Node * p = *first; int k = 0;
while ( p != NULL && k < i -1 )
{ p = p->next; k++; } //找第 i-1个结点
if ( p == NULL && *first != NULL ) {
printf (,无效的插入位置 !\n” ); //终止插入
return 0;
}
Node * newnode = (Node *) malloc ( sizeof (Node) ); //创建新结点
newnode->data = x;
if ( *first == NULL || i == 1 ) { //插入空表或非空表第一个结点之前
newnode->next = *first;
*first = newnode; //新结点成为第一个结点
}
else { //插在表中间或末尾
newnode->next = p->next;
p->next = newnode;
}
return 1;
}
插入
q->next = p->next;
p->next = q;
first
q
first
q
first
q
^ first
q ^
p p
p p
插入前 插入后 插在表头带头结点链表插入
q q
插入p p
插在表中或表尾
int Insert (LinkList first,ElemType x,int i ) {
//将新元素 x 插入在链表中第 i 号结点位置
Node * p = Locate ( first,i-1 );
if ( p == NULL ) return 0; //参数 i值不合理返回 0
Node * newnode = //创建新结点
(Node *) malloc (sizeof (Node) );
newnode->data = x;
newnode->next = p->next; //链入
p->next = newnode;
return 1;
}
前插法建立单链表
从一个空表开始，重复读入数据：
生成新结点
将读入数据存放到新结点的数据域中
将该新结点插入到链表的前端
直到读入结束符为止。
first
q
first
q
^
^
LinkList createListF ( void ) {
char ch; Node *q;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (Node));
head->next = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (Node *) malloc (sizeof(Node));
q->data = ch; //建立新结点
q->link = head->link; //插入到表前端
head->link = q;
}
return head;
}
算法 2.5Linklist CreateFromHead(){
LinkList L;
Node *s;
char c;
int flag=1;
/* 设置一个标志变量 flag，初值为 1，当输入,$”时，将 flag置为 0，建表结束 */
L=(LinkList)malloc(sizeof(Node)); /* 为头结点分配存储空间 */
L->next=NULL;
while(flag)
{ c=getchar();
if(c! =′$′)
{
s=(Node*)malloc(sizeof(Node)); /* 为读入的字符分配存储空间 */
s->data=c;
s->next=L->next;
L->next=s;
}
else flag=0;
}
return L;
}
后插法建立单链表
每次将新结点加在链表的表尾；
尾指针 r,总是指向表中最后一个结点，新结点插在它的后面；
^
q
first ^
r
^first ^
r
LinkList createListR ( void ) {
char ch;
LinkList head = //建立表头结点
(LinkList) malloc (sizeof (Node));
Node *q,*r = NULL;
while ( (ch = getchar( ) ) !=?\n? ) {
q = (Node *) malloc (sizeof(Node));
q->data = ch; //建立新结点
r ->next = q; r =q; //插入到表末端
}
r ->next = NULL;
return head;
}
算法 2.6LinkList CreateFromTail(){ /*将新增的字符追加到链表的末尾 */
LinkList L;
Node *r,*s;
char c;
int flag=1;/*设置一个标志，初值为 1，当输入,$”时,flag为 0，建表结束 */
L=(Node*)malloc(sizeof(Node)); /*为头结点分配存储空间 */
L->next=NULL;
r=L;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点 */
while(flag)
{
c=getchar();
if(c!='$') {
s=(Node*)malloc(sizeof(Node));
s->data=c;
r->next=s;
r=s;
}
else{
flag=0;
r->next=NULL;/*将最后一个结点的 next链域置为空，表示链表的结束 */
}
}
return L;
}
删除在单链表中删除 ai结点
q = p->link;
p->link = q->link;
删除前删除后?ai-1 ai ai+1
p q
p
ai-1 ai+1ai
first 如果要删除单链表的第一个结点，则指针 first的值必须改变。
int Delete ( LinkList *first,int i )
{ //在链表中删除第 i 个结点
Node *p,*q;
if ( i == 0 ) //删除表中第 1 个结点
{ q = *first; *first = (*first)->next; }
else
{ p = *first; int k = 0;
while ( p != NULL && k < i-1 )
{ p = p->next; k++; } //找第 i-1个结点
if ( p == NULL || p->next == NULL ) {//找不到第 i-1个结点
printf (,无效的删除位置 !\n” );
return 0;
}
else {//删除中间结点或尾结点元素
q = p->next;
p->next = q->next;
}
k= q->data; free ( q ); return k; //取出被删结点数据并释放 q
}
}
删除 q = p->link;
p->link = q->link;
delete q;
删除前
first
(非空表） (空表）
first
^
first
p q
^
p q
first
删除后带头结点的单链表
int delete ( LinkList first,int i ) {
//将链表第 i 号元素删去
Node * p,* q
p = Locate ( first,i-1 ); //寻找第 i-1个 结点
if ( p == NULL || p->next == NULL)
return 0;//i值不合理或空表
q = p->next;
p->next = q->next; //删除结点
free ( q ); //释放
return 1;
}
单链表清空
void makeEmpty ( LinkList first ) {
//删去链表中除表头结点外的所有其它结点
Node *q;
while ( first->next != NULL ) {//当链不空时，循环逐个删去所有结点
q = first->next; first->next = q->next;
free( q ); //释放
}
}
计算单链表长度
int Length ( LinkList first ) {
Node *p = first->next; //指针 p 指示第一个结点
int count = 0;
while ( p != NULL ) { //逐个结点检测
p = p->next; count++;
}
return count;
}
按值查找
Node * Find ( LinkList first,ElemType value ) {
//在链表中从头搜索其数据值为 value的结点
Node * p = first->next;
//指针 p 指示第一个结点
while ( p != NULL && p->data != value )
p = p->next;
return p;
}
按序号查找（定位）
Node * Locate ( LinkList first,int i ) {
//返回表中第 i 个元素的地址
if ( i < 0 ) return NULL;
Node * p = first; int k = 0;
while ( p != NULL && k < i )
{ p = p->next; k++; } //找第 i 个结点
if ( k == i ) return p; //返回第 i 个结点地址
else return NULL;
}
2.3.3 循环链表 (Circular List)
特点,最后一个结点的 link 指针不为 NULL，而是指向头结点。只要已知表中某一结点的地址，
就可搜寻所有结点的地址 。
存储结构,链式存储结构带表头结点的循环链表
an-1first a1a0
first
(空表 )
(非空表 )
循环链表的插入约瑟夫问题
用循环链表求解约瑟夫问题
n 个人围成一个圆圈，首先第 2个人从 1开始一个人一个人顺时针报数,报到第 m个人，令其出列。然后再从下一个人开始，从 1顺时针报数，
报到第 m个人，再令其出列,…,如此下去,
直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 3 m = 8
约瑟夫问题的解法
#include <iostream.h>
#include,CircList.h”
void Josephus ( int n,int m ) {
for ( int i=0; i<n-1; i++ ) { //执行 n-1次
for ( int j=0; j<m-1; j++ ) Next ( );
cout <<,Delete person,<<
getData ( ) << endl; //数 m-1个人
Remove ( ); //删去
}
}
void main ( ) {
CircList<int> clist;
int n,m;
cout <<,Enter the Number of Contestants?”;
cin >> n >> m;
for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约瑟夫环
clist.Josephus (n,m); //解决约瑟夫问题
}
2.3.4 双向链表 (Doubly Linked List)
双向链表结点结构,
prior data next
指向直接前驱 指向直接 后继非空表 空表
firstfirst
双向循环链表的定义
typedef int ListData;
typedef struct dnode {
ListData data;
struct dnode * prior,* next;
} DblNode;
typedef DblNode * DblList;
建立空的双向循环链表
void CreateDblList ( DblList *first ) {
*first = ( DblNode * ) malloc
( sizeof ( DblNode ) );
if ( first == NULL )
{ printf (,存储分配错 !\n” ); exit (1); }
*first->prior = *first->next = *first;
//表头结点的链指针指向自己
}
计算双向循环链表的长度
int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度
DblNode * p = first->next;
int count = 0;
while ( p != first )
{ p = p->next; count++; }
return count;
}
双向循环链表的插入 (非空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
在结点 *p 后插入 25
first
first
31 48 15
p
p
31 48 25 15
q
双向循环链表的插入 (空表 )
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
p q
first 25first
p
在结点 *p 后插入 25
int Insert ( DblList first,int i,ListData x ) {
DblNode * p = Locate ( first,i-1 );
//指针定位于插入位置
if ( p == first && i != 1) return 0;
DblNode * q = ( DblNode * ) malloc
( sizeof ( DblNode ) ); //分配结点
q->data = x;
q->prior = p; p->next->prior = q;
//在前驱方向链入新结点
q->next = p->next; p->next = q;
//在后继方向链入新结点
return 1;
}
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
(非空表 )
删除 48
first
first
31 48 15
p
31 15
双向循环链表的删除
p->next->prior = p->prior;
p->prior->next = p->next;
first31
p删除 31
int Remove ( DblList first,int i ) {
DblNode * p = Locate ( first,i );
//指针定位于删除结点位置
if ( p == first ) return 0;
p->next->prior = p->prior;
p->prior->next = p->next;
//删除结点 p
free ( p ); //释放
return 1;
}
1
ZHANG 2
WANG 6
LI 5
ZHAO 5
WU -1
CHEN 3
1
ZHANG 2
WANG 3
LI 4
ZHAO 5
WU -1
0
1
2
3
4
5
6
0
1
2
3
4
5
6
修改前 （插入 chen,删除 zhao)修改后用一维数组描述线性链表静态链表
定义
#define MaxSize 100 //静态链表大小
typedef int ListData;
typedef struct node { //静态链表结点
ListData data;
int link;
} SNode;
typedef struct { //静态链表
SNode Nodes[MaxSize];
int newptr; //当前可分配空间首地址
} SLinkList;
链表空间初始化
void InitList ( SLinkList SL ) {
SL.Nodes[0].link = 1;
SL.newptr = 1; //当前可分配空间从 1 开始
//建立带表头结点的空链表
for ( int i = 1; i < MaxSize-1; i++ )
SL.Nodes[i].link = i+1; //构成空闲链接表
SL.Nodes[MaxSize-1].link = -1;
//链表收尾
}
在静态链表中查找具有给定值的结点
int Find ( SLinkList SL,ListData x ) {
int p = SL.Nodes[0].link; //指针 p 指向链表第一个结点
while ( p != -1 )//逐个查找有给定值的结点
if ( SL.Nodes[p].data != x)
p = SL.Nodes[p].link;
else break;
return p;
}
在静态链表中查找第 i 个结点
int Locate ( SLinkList SL,int i ) {
if ( i < 0 ) return -1;//参数不合理
int j = 0,p = SL.Nodes[0].link;
while ( p != -1 && j < i ) {//循环查找第 i 号结点
p = SL.Nodes[p].link;
j++;
}
if ( i == 0 ) return 0;
return p;
}
在静态链表第 i 个结点处插入一个新结点
int Insert ( SLinkList SL,int i,ListData x ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.newptr; //分配结点
SL.newptr = SL.Nodes[SL.newptr].link;
SL.Nodes[q].data = x;
SL.Nodes[q].link = SL.Nodes[p].link;
SL.Nodes[p].link = q; //插入
return 1;
}
在静态链表中释放第 i 个结点
int Remove ( SLinkList SL,int i ) {
int p = Locate ( SL,i-1 );
if ( p == -1 ) return 0; //找不到结点
int q = SL.Nodes[p].link; //第 i 号结点
SL.Nodes[p].link = SL.Nodes[q].link;
SL.Nodes[q].link = SL.newptr; //释放
SL.newptr = q;
return 1;
}
2.4 一元多项式的表示及其相加
多项式的链表
struct Polynode
{
int coef;
int exp;
struct Polynode *next;
} Polynode,* Polylist;
优点是：
– 多项式的项数可以动态地增长，不存在存储溢出问题。
– 插入、删除方便，不移动元素。
通过键盘输入一组多项式的系数和指数,以输入系数 0为结束标志,并约定建立多项式链表时,总是按指数从大到小的顺序排列 。
算法描述,从键盘接受输入的系数和指数； 用尾插法建立一元多项式的链表 。
Polylist polycreate( )
{
Polynode *head,*rear,*s;
int c,e;
h=(Polynode*)malloc(sizeof(Polynode)); /*建立多项式的头结点 */
rear=head; /* rear 始终指向单链表的尾,便于尾插法建表 */
scanf(″%d,%d″,&c,&e); /*键入多项式的系数和指数项 */
while(c! =0) /*若 c=0,则代表多项式的输入结束 */
{ s=(Polynode*)malloc(sizeof(Polynode)); /*申请新的结点 */
s->coef=c ;
s->exp=e ;
rear->next=s ; /*在当前表尾做插入 */
rear=s;
scanf(″%d,%d″,&c,&e);
}
rear->next=NULL; /*将表的最后一个结点的 next置 NULL,以示表结束 */
return(head);
}
多项式链表的相加多项式 A(x)=7+3x+9x8+5x17 多项式 B(x)=8x+22x7-9x8
－ 1 7 0 3 1 9 8 5 17p o l y a
－ 1 8 1 22 7 － 9 8p o l y b － 1 7 0 11 1 9 8 5 17p o l y a
－ 1 8 1 22 7 － 9 8
因 3x ＋ 8x ＝ 1 1 x而得因 9x
8
＋ ( － 9 ) x
8
＝ 0 而被删除并释放合并后释放
p o l y b 的头结点因 3x ＋ 8x ＝ 1 1 x 被并到
p o l y a 中,该结点被删除并释放
void polyadd(Polylist polya; Polylist polyb)
/*此函数用于将两个多项式相加,然后将和多项式存放在多项式 polya中,
并将多项式 ployb删除 */
{
Polynode *p,*q,*pre; *temp;
int sum;
p=polya->next ; // 令 p和 q分别指向 polya和 polyb多项式链表中
q=polyb->next ; //的第一个结点 */
pre=polya; /* pre指向和多项式的尾结点 */
while（ p! =NULL && q! =NULL） /* 当两个多项式均未扫描结束时 */
{ if （ p->exp< q->exp）
{ pre->next=p; pre=pre->next; p=p->next；
}
else if ( p->exp==q->exp） /*若指数相等,则相应的系数相加 */
{ sum=p->coef + q->coef ;
if (sum!=0)
{ p->coef=sum; pre->next=p; pre=pre->next;
p=p->next; temp=q->next; free(q); q=temp ;
}
else
{ temp=p->next ; free(p); p=temp ;
temp=q->next; free(q); q=temp ;
}
}
//如果 p指向的多项式项的指数小于 q的指数,将 p结点加入到和多项式中
/* 若系数和为零,则删除结点 p与 q,并将指针指向下一个结点 */
else
{ pre->next=q; pre=pre->next; /* 将 q结点加入到和多项式中 */
q =q->next;
} // if
} // while结束
if(p! =NULL) /* 多项式 A中还有剩余,则将剩余的结点加入到和多项式中 */
pre->next=p;
else /* 否则,将 B中的结点加入到和多项式中 */
pre->next=q;
}
//如果 p指向的多项式项的指数大于 q的指数,将 q结点加入到和多项式中顺序表与链表的比较基于空间的比较
存储分配的方式
顺序表的存储空间是静态分配的
链表的存储空间是动态分配的
存储密度 = 结点数据本身所占的存储量 /结点结构所占的存储总量
顺序表的存储密度 = 1
链表的存储密度 < 1
顺序表与链表的比较基于时间的比较
存取方式
顺序表可以随机存取，也可以顺序存取
链表是顺序存取的
插入 /删除时移动元素个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针结 束
