数据结构和算法-1-线性结构数据结构和算法-1-线性结构

定义和逻辑特征
文章图片
定义和逻辑特征物理特征

连续存储使用数组存储线性表的元素，即用一组连续的存储单元依次存储线性表的数据元素。
不连续存储是使用链表存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素。

一般线性表顺序表示与实现

C语言结构类型定义顺序表类型

# define LIST_INIT_SIZE100//存储空间初始分配量 # define LISTINCREMENT10 //存储空间分配增量 typedefstruct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 } SqList;

线性表的初始化

StatusInitList_Sq(SqList &L) { L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); ? //构造一个空的线性表 if (!L.elem) exit(OVERFLOW); //存储分配失败? L.length = 0; //空表长度为0? L.listsize = LIST_INIT_SIZE; //初始存储容量? return OK; }// InitList_Sq

插入

Status ListInsert_Sq(SqList &L, int i, ElemType e) { //在顺序线性表L中第i个位置前插入新的元素e // i的合法值为1≤i ≤ListLength_Sq(L)+1 if (i<1 || i >L.length + 1) return ERROR; // i 值不合法 if (L.length >= L.listsize) { //当前存储空间已满，增加分配 newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType); if (!newbase)exit(OVERFLOW); //存储分配失效 L.elem = newbase; // 新基址 L.listsize+=LISTINCREMENT; // 增加存储容量 } q = &(L.elem[i - 1]); // q为插入位置 for (p = &L.elem[L.length - 1]; p >= q; --p) *(p + 1) = *p; // 插入位置及之后元素右移 *p = e; ++L.length; //插入e，表长加1 return OK; }//ListInsert_Sq

删除

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { //在顺序线性表L中删除第i个元素，并用e返回其值 // i的合法值为1≤i ≤ListLength_Sq(L) if (i<1 || i >L.length)return ERROR; // i 值不合法 p = &(L.elem[i - 1]); //p为被删除元素的位置 e = *p; //被删除元素的值赋给e q = L.elem + L.length - 1; //表尾元素的位置 for (++p; p <= q; ++p) *(p - 1) = *p; //被删除元素之后的元素左移 --L.length; return OK; }

链式表示与实现

文章图片
链表节点结构

单链表是由头指针唯一确定，在单链表的第一个结点之前附加一个结点，称之为头结点，其数据域可以为空，指针域存储指向第一个结点的指针。
用C语言中的“结构指针”描述的单链表如下：

typedefstructLNode { ElemTypedata; structLNode*next; }LNode, *LinkList;

插入

文章图片
单链表插入

StatusListInsert_L(LinkList&L, int i, ElemType e) { // 在带头结点的单链线性表L中的第i个位置之前插入元素e p = L; j = 0; // 初始化，p指向L中的头结点,j为计数器? while (p && j < i - 1) {//p指向插入位置之前的结点 p = p->next; ++j; }//寻找第i-1个结点,p指向第i-1个结点? if (!p || j > i - 1) return false; //i大于表长+1或小于1? s = (LinkList)malloc(sizeof(LNode)); //生成新结点 s->data = https://www.it610.com/article/e; s->next = p->next; // 插入L中 p->next = s; return OK; }

删除

文章图片
单链表删除

ElemTypeListDelete_L(LinkList&L, int i, ElemType &e) { // 在带头结点的单链线性表L中,删除第i个元素，并由e返回其值 p = L; j = 0; // 初始化，p指向L中的头结点,j 为计数器? while (p->next && j < i - 1) {//寻找第i个结点，并令p指向其前驱? p = p->next; ++j; // p指向被删除结点的前一个结点，所以 //p->next不能为空，否则i值错误 } ?if (!(p->next) || j > i - 1) return NULL; //删除位置不合理? q = p->next; p->next = q->next; //删除并释放结点 e = q->data; free(q); return OK; }// ListDelete_L

顺序表和链表的比较顺序表的三个优点： 【数据结构和算法-1-线性结构】方法简单，各种高级语言中都有数组，容易实现。
不用为表示结点间的逻辑关系而增加额外的存储开销。
顺序表具有按元素序号随机访问的特点。
顺序表的两个缺点：做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。
需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
链表的优缺点恰好与顺序表相反。
特殊线性表栈