1. 基础操作
/** * 遍历输出单链表 */void print(LinkList H) { LinkList p = H->next; while (p) { printf("%c", p->data); p = p->next; }}/** * 初始化链表 */void initList(LinkList *H) { /* 产生头结点,并使L指向此头结点 */ *H = (LinkList)malloc(sizeof (List)); (* H)->next = NULL;}/** * 初始条件：顺序线性表L已存在。 * 操作结果：若L为空表，则返回TRUE，否则返回FALSE */int listEmpty(LinkList L) { if(L->next) { return ERROR; } else { return OK; }}/** * 初始条件：顺序线性表L已存在。 * 操作结果：将L重置为空表 */int clearList(LinkList *L) { LinkList p,q; p = (*L)->next; /* p指向第一个结点 */ while(p) { /* 没到表尾 */ q = p->next; free(p); p = q; } (*L)->next = NULL; /* 头结点指针域为空 */ return OK;}/** * 初始条件：顺序线性表L已存在。 * 操作结果：返回L中数据元素个数 */int listLength(LinkList L) { int i = 0; LinkList p = L->next; /* p指向第一个结点 */ while(p) { i++; p = p->next; } return i;} 2、以头插法建立单链表
/** * 以头插法建立单链表 * 以"#"符为结束符 */void createFromHead(LinkList H) { List *node; ElementType type; int flag = 1; while (flag) { type = getchar(); if ('#' != type) { node = (List *)malloc(sizeof(List)); node->data = type; node->next = H->next; H->next = node; } else { flag = 0; } }} 3、以尾插法建立单链表
/** * 以尾插法建立单链表 * 以"#"符为结束符 */void createFromEnd(LinkList H) { List *node; ElementType type; int flag = 1; while(flag) { type = getchar(); if ('#' != type ) { node = (List *)malloc(sizeof(List)); node->data = type; H->next = node; H = node; } else { flag = 0; H->next = NULL; } }} 4、在单链表L中查找第i个结点
/** * 在单链表L中查找第i个结点 */List *get(LinkList L, int i) { List *list = L->next; int index = 1; while (index != i && list->next != NULL) { index++; list = list->next; } return list;} 5、在单链表L中查找值等于key的个结点
/** * 在单链表L中查找值等于key的个结点 */List *locate(LinkList L, ElementType key) { List *list = L->next; while (list->data != key && list->next != NULL) { list = list->next; } return list;} 6、在单链表的第i位插入元素e
/** * 在单链表的第i位插入元素e */int insertList(LinkList L, int i, ElementType e) { List *list = L, *p; int index = 0; while (index < i - 1 && list->next != NULL) { index++; list = list->next; } /** * 跳出循环是因为list在链表最后或i<1，所以一定是插入位置不合法 */ if (index != i -1) { printf("插入位置不合法！"); return ERROR; } p = (List *)malloc(sizeof(List)); p->data = e; p->next = list->next; list->next = p; return OK;} 7、删除单链表的第i位元素
/** * 删除单链表的第i位元素,并将删除的元素保存至元素e中 */int deleteList(LinkList L, int i, ElementType *e) { List *list = L, *p; int index = 0; while (index < i - 1 && list->next != NULL) { index++; list = list->next; } /** * 跳出循环是因为list在链表最后或i<1，所以一定是位置不合法 */ if (index != i -1) { printf("位置不合法！"); return ERROR; } p = list->next; *e = p->data; list->next = p->next; /*一定要记得释放删除的结点所占内存空间*/ free(p); return OK;} 8、完整实例
#include#include #define OK 1#define ERROR 0typedef char ElementType;typedef struct Node { ElementType data; struct Node * next;} List, *LinkList;void print(LinkList H);void initList(LinkList *H);int listEmpty(LinkList L);int clearList(LinkList *L);int listLength(LinkList L);void createFromHead(LinkList H);void createFromEnd(LinkList H);List *get(LinkList L, int i);List *locate(LinkList L, ElementType key);int insertList(LinkList L, int i, ElementType e);int deleteList(LinkList L, int i, ElementType *e);int main(int argc, char *argv[]) { LinkList H; initList(&H); printf("头插法实现链表：\n"); createFromHead(H); printf("头插法结果：\n"); print(H); List *result = get(H, 3); printf("\n查找第3位元素，结果：%c\n", result->data); printf("\n尾插法实现链表：\n"); createFromEnd(H); printf("尾插法结果：\n"); print(H); printf("\n往链表的第3位插入元素F：\n"); char element = 'F'; insertList(H, 3, element); printf("插入结果：\n"); print(H); char e; deleteList(H, 4, &e); printf("\n删除链表的第4位元素：%c\n", e); print(H); int i = clearList(&H); printf("\n遍历清空后的链表：\n"); print(H); printf("链表的长度length(H) = %d\n", listLength(H)); return 0;}/** * 遍历输出单链表 */void print(LinkList H) { LinkList p = H->next; while (p) { printf("%c", p->data); p = p->next; }}/** * 初始化链表 */void initList(LinkList *H) { /* 产生头结点,并使L指向此头结点 */ *H = (LinkList)malloc(sizeof (List)); (* H)->next = NULL;}/** * 初始条件：顺序线性表L已存在。 * 操作结果：若L为空表，则返回TRUE，否则返回FALSE */int listEmpty(LinkList L) { if(L->next) { return ERROR; } else { return OK; }}/** * 初始条件：顺序线性表L已存在。 * 操作结果：将L重置为空表 */int clearList(LinkList *L) { LinkList p,q; p = (*L)->next; /* p指向第一个结点 */ while(p) { /* 没到表尾 */ q = p->next; free(p); p = q; } (*L)->next = NULL; /* 头结点指针域为空 */ return OK;}/** * 初始条件：顺序线性表L已存在。 * 操作结果：返回L中数据元素个数 */int listLength(LinkList L) { int i = 0; LinkList p = L->next; /* p指向第一个结点 */ while(p) { i++; p = p->next; } return i;}/** * 以头插法建立单链表 * 以"#"符为结束符 */void createFromHead(LinkList H) { List *node; ElementType type; int flag = 1; while (flag) { type = getchar(); if ('#' != type) { node = (List *)malloc(sizeof(List)); node->data = type; node->next = H->next; H->next = node; } else { flag = 0; } }}/** * 以尾插法建立单链表 * 以"#"符为结束符 */void createFromEnd(LinkList H) { List *node; ElementType type; int flag = 1; while(flag) { type = getchar(); if ('#' != type ) { node = (List *)malloc(sizeof(List)); node->data = type; H->next = node; H = node; } else { flag = 0; H->next = NULL; } }}/** * 在单链表L中查找第i个结点 */List *get(LinkList L, int i) { List *list = L->next; int index = 1; while (index != i && list->next != NULL) { index++; list = list->next; } return list;}/** * 在单链表L中查找值等于key的个结点 */List *locate(LinkList L, ElementType key) { List *list = L->next; while (list->data != key && list->next != NULL) { list = list->next; } return list;}/** * 在单链表的第i位插入元素e */int insertList(LinkList L, int i, ElementType e) { List *list = L, *p; int index = 0; while (index < i - 1 && list->next != NULL) { index++; list = list->next; } /** * 跳出循环是因为list在链表最后或i<1，所以一定是插入位置不合法 */ if (index != i -1) { printf("插入位置不合法！"); return ERROR; } p = (List *)malloc(sizeof(List)); p->data = e; p->next = list->next; list->next = p; return OK;}/** * 删除单链表的第i位元素,并将删除的元素保存至元素e中 */int deleteList(LinkList L, int i, ElementType *e) { List *list = L, *p; int index = 0; while (index < i - 1 && list->next != NULL) { index++; list = list->next; } /** * 跳出循环是因为list在链表最后或i<1，所以一定是位置不合法 */ if (index != i -1) { printf("位置不合法！"); return ERROR; } p = list->next; *e = p->data; list->next = p->next; /*一定要记得释放删除的结点所占内存空间*/ free(p); return OK;}
9、总结
- 一定要理清结点之间的关系
- 删除结点后要注意释放内存空间
- 插入结点或new 结点后，需要申请内存空间