链式实现线性表,可以很方便的插入、删除操作,但索引就没有哪么方便。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; /* 查找 */ #define ERROR NULL Position Find( List L, ElementType X ) { Position p = L; /* p指向L的第1个结点 */ while ( p && p->Data!=X ) p = p->Next; /* 下列语句可以用 return p; 替换 */ if ( p ) return p; else return ERROR; } /* 带头结点的插入 */ /*P是链表结点指针,在P之前插入新结点 */ bool Insert( List L, ElementType X, Position P ) { /* 这里默认L有头结点 */ Position tmp, pre; /* 查找P的前一个结点 */ for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; if ( pre==NULL ) { /* P所指的结点不在L中 */ printf("插入位置参数错误\n"); return false; } else { /* 找到了P的前一个结点pre */ /* 在P前插入新结点 */ tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */ tmp->Data = X; tmp->Next = P; pre->Next = tmp; return true; } } /* 带头结点的删除 */ /*P是拟删除结点指针 */ bool Delete( List L, Position P ) { /* 这里默认L有头结点 */ Position tmp, pre; /* 查找P的前一个结点 */ for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */ printf("删除位置参数错误\n"); return false; } else { /* 找到了P的前一个结点pre */ /* 将P位置的结点删除 */ pre->Next = P->Next; free(P); return true; } } |