前言：
眼前姐妹们对“typedef struct lnode list”大约比较注重，同学们都需要学习一些“typedef struct lnode list”的相关知识。那么小编同时在网摘上搜集了一些关于“typedef struct lnode list””的相关资讯，希望同学们能喜欢，兄弟们一起来了解一下吧！2.1 线性表及其实现
类型名称：（ 线性表（List ）
数据对象集：是 线性表是 n (≥0) 个元素构成的有序序列( a 1 , a 2 , ,a n )
操作集：表 线性表L List ，整数i 表示位置，元素X ElementType ，
线性表基本操作主要有：
1 、List MakeEmpty()： ： 初始化一个空线性表L ；
2 、ElementType FindKth( int K, List L ) ：根据位序K ，返回相应元素 ；
3 、int Find( ElementType X, List L ) ：在线性表L 中查找X 的第一次出现位置；
4 、void Insert( ElementType X, int i, List L) ：在位序i 前插入一个新元素X ；
5 、void Delete( int i, List L ) ：删除指定位序i 的元素；
6 、int Length( List L ) ：返回线性表L 的长度n 。
线性表的抽象数据类型描述
利用数组的 连续存储空间顺序存放素 线性表的各元素
typedef struct LNode *List;
struct LNode{
ElementType Data[MAXSIZE];
int Last;
} ;
struct LNode L;
List PtrL;
下标i 0 1 …… i-1 i …… n-1 …… MAXSIZE-1
Data a a 1 1 a a 2 2 …… a a i i a a i+1
…… a a n n …… - -
t Last
访问下标为 i 的元素：L.Data[i] 或 PtrL->Data[i]
线性表的长度：L.Last+1 或 PtrL->Last+1
线性表的顺序存储实现
1. 初始化（建立空的顺序表）
主要操作的 实现
List MakeEmpty( ( ) )
{ { List PtrL; ;
PtrL = = (List ) ) malloc( ( sizeof( ( struct LNode) ) ) ); ;
PtrL- -> > Last = = - -1 1; ;
return PtrL; ;
} }
2. 查找
int Find( ElementType X, List PtrL ) )
{ { int i i = = 0 0; ;
while( ( i i <= PtrL- - >Last && PtrL- - >Data[i i ]!= X X ) )
i i ++; ;
if ( (i i > > PtrL- -> > Last) return - -1 1; ; /* 如果没找到 ， 返回- -1 1 */
else return i i; ; /* 找到后返回的是存储位置 */
} }
查找成功的平均比较次数为
(n +1)/2 ，平均时间性能为
O(n) 。
下标
i i
0 0 1 1 …… i i- -1 1 i i …… n n- -1 1 …… MAXSIZE- -1 1
Data a a 1 1 a a 2 2 …… a a i i a a i+1
…… a a n n …… - -
t Last
下标
i i
0 0 1 1 …… i i- -1 1 i i 1 i+1 …… n … ……
SIZE
- -1 1
Data a a 1 1 a a 2 2 …… a a i i a a i+1
… …… a a n n … …… - -
t Last
3. 插入 （第 i (1≤i≤n+1) 个位置上插入一个值为X 的新元素)
先移动，再插入
X
void Insert( ElementType X, int i, List PtrL )
{ int j;
if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不能插入*/
printf( ＂表满＂);
return;
}
if ( i < 1 || i > PtrL->Last+2) { /* 检查插入位置的合法性*/
printf( ＂位置不合法＂);
return;
}
for ( j = PtrL->Last; j >= i-1; j-- )
PtrL->Data[j+1] = PtrL->Data[j]; /* 将 a i ～ ～ a n 倒序向后移动*/
PtrL->Data[i-1] = X; /* 新元素插入*/
PtrL->Last++; /*Last 仍指向最后元素*/
return;
}
平均移动次数为 n /2， ，
平均时间性能为 O(n)
4. 删除 （删除表的第 i (1≤i≤n) 个位置上的元素)
后面的元素依次前移
void Delete( int i, List PtrL )
{ int j;
if( i < 1 || i > PtrL->Last+1 ) { /* 检查空表及删除位置的合法性*/
printf (“ 不存在第%d 个元素”, i );
return ;
}
for ( j = i; j <= PtrL->Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j]; /* 将 a i+1 ～ ～ a n 动 顺序向前移动*/
PtrL->Last--; /*Last 仍指向最后元素*/
return;
}
平均移动次数为 (n-1) /2， ，
平均时间性能为 O(n)
4. 删除操作实现
不要求逻辑上相邻的两个元素物理上也相邻 ；通过“链”建
。 立起数据元素之间的逻辑关系。
• 插入、删除不需要移动数据元素，只需要修改“链”。 。
typedef struct LNode *List;
struct LNode{
ElementType Data;
List Next;
};
struct Lnode L;
List PtrL;
访问序号为 i 的元素？
求线性表的长度？
线性表的链式存储实现
1. 求表长
主要操作的 实现
int Length ( List PtrL )
{ List p = PtrL; /* p 指向表的第一个结点*/
int j = 0;
while ( p ) {
p = p->Next;
j++; /* 当前p 指向的是第 j 个结点*/
}
return j;
}
时间性能为 O(n) 。
2. 查找
List FindKth( int K, List PtrL )
{ List p = PtrL;
int i = 1;
while (p !=NULL && i < K ){
p = p->Next;
i++;
}
if ( i == K ) return p;
/* 找到第K 个，返回指针 */
else return NULL;
/* 否则返回空 */
}
List Find( ElementType X, List PtrL )
{
List p = PtrL;
while ( p!=NULL && p->Data != X )
p = p->Next;
return p;
}
（ （1 ）按序号查找: FindKth; （ （2 ）按值查找: Find
平均时间性能为 O(n)
3. 插入 （在第 i-1(1≤i≤n+1) 个结点后插入一个值为X 的新结点)
（ （1 ）先构造一个 新结点 ，用s 指向；
（ （2 ）再找到链表的第 i-1 个结点，用p 指向；
（ （3 ）然后修改指针，插入结点 ( p 之后插入新结点是 是 s)
head ……
p p
s s
s s- - >Next = p- - >Next;
p p- - >Next = s;
考 思考: 修改指针的两个步骤如果交换一下，将会发生什么?
3. 插入操作实现
List Insert( ElementType X, int i, List PtrL )
{ List p, s;
if ( i == 1 ) { /* 新结点插入在表头 */
s = (List)malloc(sizeof(struct LNode)); /* 申请、填装结点*/
s->Data = X;
s->Next = PtrL;
return s; /* 返回新表头指针*/
}
p = FindKth( i-1, PtrL ); /* 查找第i-1 个结点 */
if ( p == NULL ) { /* 第i-1 个不存在，不能插入 */
printf( ＂参数i 错＂);
return NULL;
}else {
s = (List)malloc(sizeof(struct LNode)); /* 申请、填装结点*/
s->Data = X;
s->Next = p->Next; /* 新结点插入在第i-1 个结点的后面*/
p->Next = s;
return PtrL;
}
}
平均查找次数为 n /2 ，平均
时间性能为 O(n)
（ （1 ）先找到链表的第 i-1 个结点，用p 指向；
（ （2 ）再用指针s 指向要被删除的结点（p 的下一个结点）;
head ……
p p
s = p- - >Next;
4. 删除 （删除链表的第 i (1≤i≤n) 个位置上的结点)
（ （3 ）然后修改指针，删除s 所指结点;
（ （4 ）最后释放s 所指结点的空间。
p p- - >Next = s- - >Next;
free （s s ）; ;
考 思考: 操作指针的几个步骤如果随意改变，将会发生什么?
List Delete( int i, List PtrL )
{ List p, s;
if ( i == 1 ) { /* 若要删除的是表的第一个结点 */
s = PtrL; /*s 指向第1 个结点*/
if (PtrL!=NULL) PtrL = PtrL->Next; /* 从链表中删除*/
else return NULL;
free(s); /* 释放被删除结点 */
return PtrL;
}
p = FindKth( i-1, PtrL ); /* 查找第i-1 个结点*/
if ( p == NULL ) {
printf(“ 第%d 个结点不存在”, i-1); return NULL;
} else if ( p->Next == NULL ){
printf(“ 第%d 个结点不存在”, i); return NULL;
} else {
s = p->Next; /*s 指向第i 个结点*/
p->Next = s->Next; /* 从链表中删除*/
free(s); /* 释放被删除结点 */
return PtrL;
}
}
平均查找次数为 n /2， ，
平均时间性能为 O(n)
