/** * 插入操作,在表 L ,第 i 个位置插入指定元素 e * * @param L * @param i * @param e * @return */ boolListInsert(SqList &L, int i, ElemType e) { // 判断 i 的取值范围是否有效( 1<=i<=L.length) if (i < 1 || i > L.length) { returnfalse; }
// 当存储空间已满,不能插入 if (i >= MaxSize) { returnfalse; }
/** * 删除操作,删除线性表 L 第 i 个位置的元素,并用 e 返回被删除元素的 * * @param L * @param i * @param e * @return */ boolListDelete(SqList &L, int i, ElemType &e){ // i 的值必须合法 if (Empty(L)) { returnfalse; }
// 判断 i 的取值范围是否有效( 1<=i<=L.length) if (i < 1 || i > L.length) { returnfalse; }
/** * 按值查找 * * @param L * @param e * @return */ intLocateElem(SqList L, ElemType e){ for (int i = 0; i < L.length; ++i) { if (L.data[i] == e) { // 下标为 i 的元素等于 e,返回其位序为 i+1 return i+1; } }
return0; };
/** * 按位查找 * * @param L * @param i * @return */ ElemType GetElem(SqList L, int i){ // 判断 i 的取值范围是否有效( 1<=i<=L.length) if (i < 1 || i > L.length) { return-1; }
return L.data[i-1]; };
/** * 打印线性表所有元素 * * @param L */ voidPrintList(SqList L){ for (int i = 0; i < L.length; ++i) { printf("%d ", L.data[i]); } printf("\n"); };
/** * 判断是否为空 * * @param L * @return */ boolEmpty(SqList L){ if (L.length == 0) { returntrue; }
/** * 头插法建立单链表 * 思路:建立新的结点分配内存空间,将新结点插入到当前链表的表头 * * @param L * @param a * @param n * @return */ LinkList List_HeadInsert(LinkList &L, int a[], int n){ // 创建头结点 L = (LinkList) malloc(sizeof (LNode)); // 初始化链表 L->next = NULL;
LNode *s; for (int i = 0; i < n; i++) { // 申请一个新空间给 s s = (LNode *) malloc(sizeof (LNode)); s->data = a[i]; s->next = L->next; L->next = s; } return L; };
/** * 尾插法建立单链表 * 思路:建立新的结点分配内存空间,将新结点插入到当前链表的表尾 * * @param L * @return */ LinkList List_TailInsert(LinkList &L, int a[], int n){ L = (LinkList) malloc(sizeof(ElemType)); L->next = NULL;
LinkList s, r = L; for (int i = 0; i < n; ++i) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = a[i];
// r 指向新的表尾结点 r->next = s; // 这一步的目的是保证 r 的 next 指针指向新空间 r = s; // 这一步的目的是保证 r 是链表的尾部 } r->next = NULL; return L; }
/** * 按位查找操作。获取表 L 中第 i 个位置的元素的值。 * 思路:在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。 * * @param L * @param i * @return */ LNode *GetElem(LinkList L, int i){ int j = 1; // 让 P 指向第一个指针 LNode *p = L->next; if (i == 0) { // 如果 i = 0,返回头结点 return L; }
if (i < 1) { // 如果 i 小于零,返回 NULL returnNULL; }
while (p && j < i) { p = p->next; j ++; } return p; };
/** * 按值查找操作。在表 L 中查找具有给定关键宇值的元素。 * 思路:从单链表第一个结点开始,由前往后依次比较表中各结点数据域的值,若某结点数据域的值等于给定值e,则返回该结点的指针 * 若整个单链表中没有这样的结点,则返回NULL。 * * @param L * @param e * @return */ LinkList LocateElem(LinkList L, ElemType e){ L = L->next; while (L) { if (L->data == e) { break; } L = L->next; } return L; }
/** * 获取链表长度 * * @param L * @return */ intLength(LNode *L){ L = L->next; int i = 0; while (L) { i++; L = L->next; } return i; }
/** * 打印链表 * * @param L */ voidPrintLinkList(LinkList L) { L = L->next; while (L != NULL) { printf("%3d", L->data); L = L->next; } printf("\n"); }