1.线性表的抽象数据类型描述
类型名称：线性表（list）
数据对象集： 线性表是n个元素构成的有序序列
操作集：
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。
2.利用数组的连续性存储空间顺序存储线性表的各元素。
typedef struct{
ElementType Data[MAXSIZE];
int Last; } List;
List L, *PtrL;
访问下标为 i 的元素:L.Data[i] 或 PtrL->Data[I]
线性表的长度:L.Last+1 或 PtrL->Last+1
2.1 数组类型 主要操作实现
//初始化
List {
}
*MakeEmpty( )
List *PtrL;
PtrL = (List *)malloc( sizeof(List) );
PtrL->Last = -1;
return PtrL;
//查找
int Find( ElementType X, List *PtrL ) { int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X ) I++;
if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
else return i; /* 找到后返回的是存储位置 */ }
// 插入 （从后往前循环）
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-- )
/* 表空间已满，不能插入*/ 平均移动次数为 n /2，
/*检查插入位置的合法性*/ 平均时间性能为 O(n)
PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai~ an倒序向后移动*/
PtrL->Data[i-1] = X; /*新元素插入*/
PtrL->Last++; /*Last仍指向最后元素*/
return;
}
//删除 （从前往后循环）
void Delete( int i, List *PtrL ) { intj;
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];
PtrL->Last--;
return; }
- 线性表的链式存储实现
不要求逻辑上相邻的两个元素物理上也相邻，通过“链”建立元素间关系。
插入和删除不需要移动数据元素，只需要修改链。
typedef struct Node{
ElementType Data;
struct Node *Next;
} List;
List L, *PtrL;
3.1 链表的主要操作实现
// 求表长度，用循环遍历
int Length ( List *PtrL )
{
List *p = PtrL;
int j=0;
while ( p ) {
p = p->Next; j++;
/* p指向表的第一个结点*/
/* 当前p指向的是第 j 个结点*/
}
return j;
}
//按照 值查找
List *Find( ElementType X, List
*PtrL ) {
List *p = PtrL;
while ( p!=NULL && p->Data != X )
p = p->Next; return p;
}
//按照序号查找
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;
else return Null;
}
插入操作原理
List *Insert( ElementType X, int i, List *PtrL )
{
List *p,*s;
if ( i == 1 ) {
s = (List *)malloc(sizeof(List));
s->Data = X;
s->Next = PtrL;
return s;
}
p = FindKth( i-1, PtrL );
if ( p == NULL ) {
printf("参数i错");
return NULL;
}else {
s = (List *)malloc(sizeof(List));
s->Data = X;
s->Next = p->Next;
p->Next = s;
return PtrL;
}
删除原理
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 ); if ( p == NULL ) {
printf(“第%d个结点不存在”, i-1);
return NULL;
} else if ( p->Next == NULL ){
printf(“第%d个结点不存在”, i);
return NULL;
}else {
s = p->Next;
p->Next = s->Next;
free(s);
return PtrL;
4.广义表
广义表是线性表的推广
对于线性表而言， n个元素都是基本的单元素;
广义表中，这些元素不仅可以是单元素也可以是另一个广义表
typedef struct GNode{
int Tag; /*标志域:0表示结点是单元素，1表示结点是广义表 */
union { /* 子表指针域Sublist与单元素数据域Data复用，即共用存储空间 */
ElementType Data;
struct GNode *SubList;
} URegion;
struct GNode *Next; /* 指向后继结点 */
} GList;
多重链表:链表中的节点可能同时隶属于多个链
多重链表中结点的指针域会有多个，如前面例子包含了Next和 SubList两个指针域;
但包含两个指针域的链表并不一定是多重链表，比如双向链表 不是多重链表。
多重链表有广泛的用途: 基本上如树、图这样相对 复杂的数据结构都可以采 用多重链表方式实现存储
网友评论