网站关键词优化办法,代加工网站有哪些,建设银行个人客户,写小说赚钱的网站文章目录 逻辑结构存储结构顺序存储链式存储单链表双链表循环单链表循环双链表静态链表 数据的操作顺序结构链式结构单链表双链表 逻辑结构
线性表是具有相同数据类型的 n ( n ≥ 0 ) n(n≥0) n(n≥0)个数据元素的有限序列#xff0c;其中 n n n为表长#xff0c;当 n 0 n0… 文章目录 逻辑结构存储结构顺序存储链式存储单链表双链表循环单链表循环双链表静态链表 数据的操作顺序结构链式结构单链表双链表 逻辑结构
线性表是具有相同数据类型的 n ( n ≥ 0 ) n(n≥0) n(n≥0)个数据元素的有限序列其中 n n n为表长当 n 0 n0 n0时线性表是一个空表。若用 L L L命名线性表则其一般表示为 L ( a 1 , a 2 , ⋯ , a i , a i 1 , ⋯ , a n ) L\left(a_1, a_2, \cdots, a_i, a_{i1}, \cdots, a_n\right) L(a1,a2,⋯,ai,ai1,⋯,an)
式中 a 1 a_1 a1是唯一的“第一个”数据元素又称表头元素 a n a_n an是唯一的“最后一个”数据元素又称表尾元素。除第一个元素外每个元素有且仅有一个直接前驱。除最后一个元素外每个元素有且仅有一个直接后继。
线性表有以下特性
表中元素的个数有限。表中元素具有逻辑上的顺序性表中元素有其先后次序。表中元素都是数据元素每个元素都是单个元素。表中元素的数据类型都相同这意味着每个元素占有相同大小的存储空间。表中元素具有抽象性即仅讨论元素间的逻辑关系而不考虑元素究竟表示什么内容。
存储结构
顺序存储
它是用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置第i个元素的存储位置后面紧接着存储的是第 i 1 i1 i1个元素称 i i i为元素 a i a_i ai在顺序表中的位序。因此顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。
假设顺序表L存储的起始位置为LOC(A),sizeof(ElemType)是每个数据元素所占用存储空间的大小。 typedef struct {ElemType data[Maxsize];int length;
} SqList;存在的问题
需要大量连续的存储空间插入删除时时间复杂度高顺序表一旦确定大小后续将不可扩充
链式存储
链式存储线性表时不需要使用地址连续的存储单元即不要求逻辑上相邻的元素在物理位置上也相邻它通过“链”建立元素之间的逻辑关系因此插入和删除操作不需要移动元素而只需修改指针但也会失去顺序表可随机存取的优点。
单链表 typedef struct LNode {ElemType data;struct LNode *next;
} LNode, *LinkList;存在的问题
失去了顺序存储中随机存取的特性求表长的时间复杂度高访问前驱结点的时间复杂度高
双链表
在单链表中要访问某个结点的前驱(插入、删除操作时),只能从头开始遍历访问前驱的时间复杂度为 O ( n ) O(n) O(n)。为了克服单链表的这个缺点引入了双链表双链表结点中有两个指针prior和next,分别指向其直接前驱和直接后继。表头结点的 prior域和尾结点的 next 域都是 NULL。 typedef struct DNode {ElemType data;struct DNode *next, prior;
} DNode, *DLinkList;循环单链表
循环单链表和单链表的区别在于表中最后一个结点的指针不是NULL,而改为指向头结点从而整个链表形成一个环。 循环双链表
由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中头结点的prior指针还要指向表尾结点。 静态链表
静态链表是用数组来描述线性表的链式存储结构结点也有数据域data 和指针域 next,与前面所讲的链表中的指针不同的是这里的指针是结点在数组中的相对地址(数组下标),又称游标。 typedef struct {ElemType data;int next;
} SLinkList[Maxsize];数据的操作
顺序结构
初始化
void InitList(SqList L)
{L.length 0;
}判满
bool isFull(SqList L)
{if (L.length Maxsize) return true;return false;
}判空
bool isEmpty(SqList L)
{if (L.length 0) return true;return false;
}插入操作
bool ListInsert(SqList L, int i, ElemType e)
{if (i 1 || i L.length 1) // 无效的插入位置return false;if (isFull(L)) return false; // 存储空间已满for (int j L.length; j i; j -- )L.data[j] L.data[j - 1];L.data[i - 1] e;L.length ;return true;
}删除操作
bool ListDelete(SqList L, int i, ElemType e)
{if (i 1 || i L.length 1) // 无效的删除位置return false;if (isEmpty(L)) return false; // 数组是空的e L.data[i - 1];for (int j i; j L.length; j )L.data[j - 1] L.data[j];L.length -- ;return true;
}按值查找
int LocateElem(SqList L, ElemType e)
{for (int i 0; i L.length; i )if (L.data[i] e)return i 1;return -1;
}链式结构
单链表
初始化
void InitList(LinkList L)
{L (LNode *) malloc (sizeof(LNode));L-next NULL;
}求表长
int Length(LinkList L)
{LNode *p L-next;int cnt 0; // 记录长度while (p){cnt ;p p-next;}return cnt;
}按序号查找结点
LNode * GetElem(LinkList L, int i)
{LNode *p L-next;int cnt 0; // 记录当前遍历到第几个结点了while (p){cnt ;if (cnt i)return p;p p-next;}return NULL;
}按值查找
LNode * LocateElem(LinkList L, ElemType e)
{LNode *p L-next;while (p){if (p-data e)return p;p p-next;}return NULL;
}插入结点 bool ListInsert(LinkList L, int i, ElemType e)
{LNode *p L;int j 0;while (p j i - 1){p p-next;j ;}if (p NULL) return false; // 位置不合法LNode *s (LNode *) malloc (sizeof(LNode));/*插入结点*/s-data e;s-next p-next;p-next s;return true;
}删除结点
bool ListDelete(LinkList L, int i, ElemType e)
{LNode *p L;int j 0;while (p j i - 1){p p-next;j ;}if (p NULL || p-next NULL) return false; // 位置不合法LNode *q p-next;/*删除结点q*/e q-data;p-next q-next;free(q);return true;
}采用头插法建立链表 LinkList List_HeadInsert(LinkList L)
{LNode *s;int x;L (LNode *) malloc (sizeof(LNode));L-next NULL;scanf(%d, x);while (x ! 9999) // 输入9999停止{s (LNode *) malloc (sizeof(LNode));s - data x;s-next L-next;L-next s;scanf(%d, x);}return L;
}采用尾插法建立链表 LinkList List_TailInsert(LinkList L)
{int x;L (LNode *) malloc (sizeof(LNode));LNode *s, *r L; // r是表尾指针scanf(%d, x);while (x ! 9999) // 输入9999停止{s (LNode *) malloc (sizeof(LNode));s - data x;r-next s;r s;scanf(%d, x);}r-next NULL;return L;
}双链表
初始化
void InitList(DLinkList L)
{L (DNode *) malloc (sizeof(DNode));L-next L-prior NULL;
}插入结点 bool ListInsert(DLinkList L, int i, ElemType e)
{DNode *p L;int j 0;while (p j i - 1){p p-next;j ;}if (p NULL) return false; // 位置不合法DNode *s (DNode *) malloc (sizeof(DNode));/*插入结点*/s-data e;s-next p-next;p-next-prior s;s-prior p;p-next s;return true;
}删除结点
bool ListDelete(DinkList L, int i, ElemType e)
{DNode *p L;int j 0;while (p j i - 1){p p-next;j ;}if (p NULL || p-next NULL) return false; // 位置不合法DNode *q p-next;/*删除结点q*/e q-data;p-next q-next;q-next-prior p;free(q);return true;
}
