大话数据结构03---第三章线性表
知识图谱
待补充—
线性表的顺序存储结构—代码3.1
读取操作
// 得到数据元素，返回状态的指示，指针传递，结构体
#define Ok 1
#define ERROR 0
typedef int Status
Status GetElem(SqList L, int i, ElemType *e)
{
if(L.length == 0 || i<1 || i>L.length)
{
return ERROR;
}
else{
*e = L.data[i-1]
return OK;
}
}
插入操作
在第i个位置插入元素应该如何操作？
插入算法思路： 1.如果插入位置不合理，抛出异常 2.如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量 3.从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置 4.将要插入的元素填入位置处。 5.表长加1。
/*初始条件：顺序线性表 L 已存在，1<=i<=ListLength(L)*/
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
if(L->length >= MAXSIZE)
{
return ERROR;
}
if(i < 1 || i >L->length)
{
return ERROR;
}
if(i <= L->length)
{
for(k = L->length-1; k>=i-1; k--)
{
L->data[k+1] = L->data[k]
}
L->data[i-1] = e;
L->length++;
}
return OK;
}
删除操作( O(n) )
算法思路： （1）如果删除位置不合理，抛出异常 （2）取出删除元素 （3）表长减1
Status ListDelete(Sqlist *L, int i, ElemType *e)
{
int k;
if(L->length == 0)
{
return ERROR; //线性为空
}
if(i < 1 || i>L->length)
return ERROR; //删除位置不正确
*e = L->data[i-1]; //取出元素
if(i< L->length)
{
for(k = i; k < L->length; k++)
{
L->data[k-1] = L->data[k]
}
}
L->length--;
return OK;
}
线性表的链式存储结构代码描述 3.6.4
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
单链表的读取（工作指针后移）
思路：（1）声明一个指针p指向链表的第一个结点，初始化从 j 开始； （2）当 j < i 时，就遍历链表，让p的指针向后移动，不断移向下一个结点，j 累加 1； （3）若到链表末尾p为空，则说明第 i 个结点不存在； （4）否则查找成功，返回结点p的数据。
Status GetElem(LinkList L, int i, ElemType *e)
{
int j;
LinkList p;
p = L->next;
j=1;
while( p && j<i) //循环不为空且小于 加加 一直循环 **工作指针后移**
{
p = p->next;
++j;
}
if(!p || j>i)
{
return ERROR;
}
*e = p->data; // j==i
return OK;
}
