下面为单向链表的一些基础知识： 单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表，链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指列表中的下一个结点
列表是由结点构成，由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针 如下图： 下面为代码的实现：
linklist.h #ifndef __LINKLIST_H__ #define __LINKLIST_H__ #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int DataType; typedef struct Node//链表的构造 { DataType data; struct Node*next; }Node, *pNode, *pList; void initLinkList(pList*pplist); //初始化链表，用二级指针指向一级指针的地址改变其内容 void PushFront(pList*pplist, DataType d); //链表的头插 void popFront(pList*pplist); //链表的头删 void display(pList p1); //链表的打印 pNode BuyNode(DataType d);//创建链表节点 void PushBack(pList *pplist, DataType d);//尾插 void PopBack(pList *pplist);//尾删 pNode Find(pList pl, DataType d); //查找d void Remove(pList *pplist, DataType d);//删除指定的一个元素 void RemoveAll(pList *pplist, DataType d);//删除指定的所有元素 void Insert(pList *pplist, pNode pos, DataType d);//指定位置的后面插入 //void Delpos(pList *pplist, pNode pos);//指定位置删除 pNode BuyNode(DataType d);//创建链表节点 void DestroyList(pList *pplist); #endif //__LINKLIST_H__ linklist.c #include"LinkList.h" void initLinkList(pList*pplist) { assert(pplist != NULL); *pplist = NULL; } pNode BuyNode(DataType d)//创建链表节点 { pNode newnode = (pNode)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc"); exit(EXIT_FAILURE); } newnode->data = d; newnode->next = NULL; return newnode; } void PushFront(pList*pplist, DataType d) //头插 { assert(pplist); pNode ps = BuyNode(d); //调用创的新节点函数 ps->next = *pplist; //将*pplist赋给新的节点 *pplist = ps; } void display(pList pl) //打印 { assert(pl); while (pl != NULL) { printf("%d ", pl->data); pl = pl->next; } printf("\n"); } void popFront(pList*pplist)//头部删除 { pNode cur = *pplist; assert(pplist); //链表为空 if (*pplist == NULL) { return; } *pplist = cur->next; free(cur); cur = NULL; } void PushBack(pList *pplist, DataType d)//尾插 { assert(pplist != NULL); pNode ps = BuyNode(d); //调用创的新节点函数 pNode head = *pplist; if (head == NULL)//空链表处理 { *pplist = ps; return; } while (head->next != NULL)//非空链表处理 { head = head->next; } head->next = ps; } void PopBack(pList *pplist) //尾删 { pNode cur = *pplist; pNode prev = NULL; assert(pplist); //链表没有节点 if (*pplist == NULL) { return; } //链表有一个节点 if (cur->next == NULL) { free(*pplist); *pplist = NULL; return; } //链表有两个及两个以上节点 while (cur->next != NULL) { prev = cur;//prev中保存的是cur之前的那个节点 cur = cur->next; } prev ->next = NULL; free(cur); } pNode Find(pList pl, DataType d) { pNode tmp = pl; while (tmp != NULL) { if (tmp->data == d) { return tmp; } tmp = tmp->next; } return NULL; } void Remove(pList *pplist, DataType d)//删除指定的一个元素 { assert(pplist != NULL); pNode del = NULL; pNode cur = Find(*pplist, d); if (cur == NULL) { return; } del = cur->next; cur->data = del->data; cur->next = del->next; free(del); del= NULL; } void RemoveAll(pList *pplist, DataType d) //删除指定的所有元素 { pNode pos = NULL; pNode del = NULL; assert(pplist); pNode cur = *pplist; while (cur) { if (cur->data == d) { del = cur; if (cur == *pplist) { *pplist = cur->next; } else { pos->next = cur->next; } cur = cur->next; free(del); del = NULL; } else { pos = cur; cur = cur->next; } } } void Insert(pList *pplist, pNode pos, DataType d)//指定位置的后面插入 { assert(pplist != NULL); pNode cur = NULL; pNode tmp = BuyNode(d); pNode head = *pplist; while ((head->next != NULL) && (pos--)) { cur = head; head = head->next; } cur->next = tmp; tmp ->next= head; } //void Delpos(pList *pplist, pNode pos)//指定位置删除 //{ // assert(pplist); // assert(pos); // //要删除的是尾节点 // if (pos->next == NULL) // { // PopBack(pplist); // } // //删除的是非尾节点 // else // { // pNode del = pos->next; // pos->data = pos->next->data; // pos->next = pos->next->next; // free(del); // del = NULL; // } //} void DestroyList(pList *pplist)//销毁链表 { assert(pplist); pNode cur = *pplist; while (cur!=NULL) { pNode del = cur; cur = cur->next; free(del); del = NULL; } }下面为实现区：为test.c
test.c #include"LinkList.h" //void test1() //{ // pList List; // initLinkList(&List); // PushFront(&List, 4); // PushFront(&List, 3); // PushFront(&List, 2); // PushFront(&List, 1); // display(List); // popFront(&List); // popFront(&List); // display(List); // DestroyList(&List); //} //void test2() //{ // pList List; // initLinkList(&List); // PushBack(&List, 6); // PushBack(&List, 5); // PushBack(&List, 4); // PushBack(&List, 3); // PushBack(&List, 2); // PushBack(&List, 1); // display(List); // PopBack(&List); // PopBack(&List); // PopBack(&List); // PopBack(&List); // display(List); // DestroyList(&List); //} //void test3() //{ // pList List; // initLinkList(&List); // PushFront(&List, 4); // PushFront(&List, 3); // PushFront(&List, 2); // PushFront(&List, 1); // display(List); // pNode ret = Find(List, 2); // { // if (ret == NULL) // { // printf("找不到"); // } // else // { // printf("%d\n", ret->data); // } // } // DestroyList(&List); //} //void test4() //{ // pList List; // initLinkList(&List); // PushFront(&List, 4); // PushFront(&List, 3); // PushFront(&List, 2); // PushFront(&List, 1); // display(List); // Remove(&List, 1); // display(List); // DestroyList(&List); //} //void test5() //{ // pList List; // initLinkList(&List); // PushFront(&List, 4); // PushFront(&List, 3); // PushFront(&List, 2); // PushFront(&List, 1); // display(List); // Insert(&List,4, 2); // display(List); // DestroyList(&List); //} void test6() { pList List; initLinkList(&List); PushFront(&List, 4); PushFront(&List, 3); PushFront(&List, 2); PushFront(&List, 1); PushFront(&List, 1); RemoveAll(&List, 1); display(List); DestroyList(&List); } int main() { /*test1(); test2(); test3(); test4(); test5();*/ test6(); system("pause"); return 0; }本人是新手，希望得到大家的意见和建议。
