将链表（ADT LinkList）的数据对象，数据关系及基本操作（函数）用C语言实现，并测试。
手机用户点击代码查看未显示内容
LinkList.h内容
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; int LinkListInit(LinkList &L); int LinkListOutput(LinkList L); int LinkListInsert(LinkList &L,int i,ElemType e); int LinkListDelete(LinkList &L,int i,ElemType &e); void LinkListReverse(LinkList &L); void LinkListMerge(LinkList &Lc, LinkList &La, LinkList &Lb); void DestroyLinklist(LinkList &L); void ClearLinkList(LinkList &L); int GetLinkListLength(LinkList L); |
函数具体实现
① 链表的初始化
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
int LinkListInit(LinkList &L) { LinkList tail, p; int n; p = (LNode*)malloc(sizeof(LNode)); L = tail = p; L->next = NULL; printf("输入链表的初始长度:\n"); scanf("%d", &n); L->data = n; printf("请输入%d个值:\n",n); while (n--) { p = (LNode*)malloc(sizeof(LNode)); scanf("%d", &p->data); p->next = NULL; tail->next = p; tail = p; } p->next = NULL; printf("链表创建成功！\n"); return OK; } |
② 链表的输出
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int LinkListOutput(LinkList L) { LinkList p = L->next; if (p == NULL) return ERROR; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); return OK; } |
③ 插入一个值到链表中
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int LinkListInsert(LinkList &L, int i, ElemType e) { LinkList p = L; LinkList s; int j = 0; while (p&&j < i - 1) { p = p->next; ++j; } if (!p || j>i - 1)return ERROR; s = (LinkList)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; L->data++; return OK; } |
④ 删除链表中的一个值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int LinkListDelete(LinkList &L, int i, ElemType &e) { LinkList p = L; LinkList q; int j = 0; while (p&&j < i - 1) { p = p->next; ++j; } if (!(p->next) || j>i - 1)return ERROR; q = p->next; p->next = q->next; e = q->data; free(q); L->data--; return OK; } |
⑤ 链表的逆置
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void LinkListReverse(LinkList &L) { LinkList p, q, r; q = r = NULL; p=L->next; while (p->next) { q = p->next; p->next = r; r = p; p = q; } p->next = r; L->next->next = NULL; L->next = p; } |
注释：在此使用的插入法逆置时间效率O（n）
⑥ 两个非递减链表的归并函数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void LinkListMerge(LinkList &Lc, LinkList &La, LinkList &Lb) { LinkList pa, pb, pc; pa = La->next; pb = Lb->next; Lc = pc = La; while (pa&&pb) { if (pa->data <= pb->data) { pc->next = (LNode*)malloc(sizeof(LNode)); pc->next = pa; pc = pa; pa = pc->next; } else { pc->next = (LNode*)malloc(sizeof(LNode)); pc->next = pb; pc = pb; pb = pb->next; } } pc = (LNode*)malloc(sizeof(LNode)); pc->next = pa ? pa : pb; free(Lb); }//非递减排列合并 |
⑦ 链表的清除和销毁
清除：
|
1 2 3 4 5 6 7 8 9 10 11 |
void ClearLinkList(LinkList &L){ LinkList p, q; p = L->next; while (p) { q = p->next; free(p); p = q; } L->next = NULL; } |
销毁：
|
1 2 3 4 5 6 7 8 9 10 |
void DestroyLinklist(LinkList &L) { LinkList p; while (L) { p = L->next; free(L); L = p; } } |
注释：注意链表的清除和销毁的区别，将在实验小结中展现。
MAIN函数
|
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 |
#include "stdafx.h" #include "LinkList.h" int main() { LinkList L, M,N; int p; ElemType e; char flag1,flag2; printf("------------------------------------------\n"); printf("创建链表1:\n"); LinkListInit(L); printf("------------------------------------------\n"); printf("输出当前链表1:\n"); LinkListOutput(L); printf("链表的长度为：%d\n", GetLinkListLength(L)); printf("------------------------------------------\n"); printf("插入一个值到链表1中:\n"); printf("输入插入位置："); scanf("%d", &p); printf("输入插入的值："); scanf("%d", &e); LinkListInsert(L, p, e); printf("插入后输出链表1：\n"); LinkListOutput(L); printf("链表的长度为：%d\n", GetLinkListLength(L)); printf("------------------------------------------\n"); printf("删除链表中的一个值:\n"); printf("输入删除位置："); scanf("%d", &p); LinkListDelete(L, p, e); printf("删除的值为%d：", e); printf("删除后输出链表1：\n"); LinkListOutput(L); printf("链表的长度为：%d\n", GetLinkListLength(L)); printf("------------------------------------------\n"); printf("是否需要逆置链表（Y/N)?"); getchar(); flag1 = getchar(); if (flag1 == 'Y') { printf("链表逆置:\n"); LinkListReverse(L); LinkListOutput(L); } printf("------------------------------------------\n"); printf("若当前链表1非递减请创建新非递减链表2并使用递增合并函数(Y/N)?"); getchar(); scanf("%c", &flag2); if (flag2 == 'Y') { LinkListInit(M); printf("递增合并函数:\n"); LinkListMerge(N, L, M); LinkListOutput(N); } printf("------------------------------------------\n"); printf("\n链表清除中......\n"); ClearLinkList(L); printf("------------------------------------------\n"); printf("\n链表销毁中......\n"); DestroyLinklist(L); printf("------------------------------------------\n"); system("pause"); return 0; } |
小结
1. 注意在定义链表的时候，是否要带头结点，本人的链表实现的是带头结点的优化链表，即在链表初始化的时候给链表增加一个头结点，而不是像书上多使用一个typedef语句，同时，头结点的L->data元素存的是链表的长度，由此省去了定义Link-length。
2. 非递减链表的归并函数Merge要注意函数内部有初始化和赋值新链表，每增加一个都要为p->next申请空间。
3. 在插入和删除函数中要对链表的length动态更改。
4. 链表的逆置函数时间复杂度为0（n）,要注意为了使其它函数能够使用，链表的逆置不光简单地调换位置，要注意头结点指向第一个元素，尾元素的下一个位置为NULL。即要增加 p->next = r; L->next->next = NULL;L->next = p;语句。
注意当p->next==NULL时，L->next仍然指向先前链表的第一个元素，而新链表该元素变为最后一个，因此要加L->next->next==NULL。
5. 关于链表的清除与销毁的区别。链表的清除销毁其它节点保留头结点，销毁全部free掉。
原创非商业转载请注明出处，商业转载请联系。
