数据结构单链表-LinkList 参考书：《数据结构（C语言）》作者：严蔚敏
文中的LinkList无头结点。
如果发现错误，请帮忙指正，谢谢。
转载请注明@author vaneng
LinkList.h
/*单链表*/
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next_ptr;
}LNode, *LinkList;
/*author vaneng*/
LNode *makeNode(ElemType e);
void freeNode(LNode *n_ptr);
void destroyList(LinkList list);
void clearList(LinkList list);
void insertFirst(LinkList *l_ptr, LNode node);
void deleteFirst(LinkList *l_ptr, LNode *aN_ptr);
void append(LinkList *l_ptr, LNode node);
void removeLast(LinkList *l_ptr, LNode *n_ptr); //删除尾结点，将结果存储到n_ptr
void insertBefore(LinkList *l_ptr, LNode *aN_ptr, LNode node);
void insertAfter(LNode *aN_ptr, LNode node);
void setCurElem(LNode *n_ptr, ElemType e);
ElemType getCurElem(LNode *n_ptr);
int listEmpty(LinkList list);
int listLength(LinkList list);
LNode *getHead(LinkList list);
LNode *getLast(LinkList list);
LNode *priorPos(LinkList list, LNode *aN_ptr);
LNode *nextPos(LinkList list, LNode *n_ptr);
void locatePos(LinkList list, int i, LNode *aN_ptr);
LNode *locateElem(LinkList list, ElemType e, int (*compare)(ElemType, ElemType));
void listTraverse(LinkList list);
void error(char *name, char *msg); //显示错误信息msg
void warning(char *msg);
LinkList.c
#include "LinkList.h"
#include <malloc.h>
#include <stdio.h>
/*author vaneng*/
LNode *makeNode(ElemType e){
LNode *n_ptr = (LNode *)malloc(sizeof(LNode));
if(!n_ptr){
error("makeNode", "Malloc failed");
return 0;
}
n_ptr->data = e;
n_ptr->next_ptr = 0;
return n_ptr;
}
void freeNode(LNode *n_ptr){
warning("Please make sure that the next_ptr of n_ptr is null");
n_ptr->next_ptr = 0;
free(n_ptr);
}
/*LNode *initList()
在这种数据结构下没有意义
*/
void destroyList(LinkList list){
LNode *n_ptr = list;
while(list){
list = list->next_ptr;
n_ptr->next_ptr=0;
free(n_ptr);
n_ptr=list;
}
}
void clearList(LinkList list){
/*我觉得在这种数据结构下和destroy没有区别吧*/
}
void insertFirst(LinkList *l_ptr, LNode node){
/*因为可能修改头指针，所以用LinkList *l_ptr
值传递，l_ptr这个值是没法修改的。
*/
LNode *n_ptr = (LNode *)malloc(sizeof(LNode));
*n_ptr = node;
//n_ptr->data = aNode.data;
/*next_ptr是一个指针，*l_ptr也是一个指针*/
n_ptr->next_ptr = *l_ptr;
*l_ptr = n_ptr;
}
void deleteFirst(LinkList *l_ptr, LNode *aN_ptr){
LNode *n_ptr = *l_ptr;
*aN_ptr = **l_ptr;
*l_ptr = (*l_ptr)->next_ptr;
free(n_ptr);
n_ptr = 0;
}
void append(LinkList *l_ptr, LNode node){
LNode *n_ptr = (LNode *)malloc(sizeof(LNode));
LNode *cursor_ptr = *l_ptr;
*n_ptr = node;
n_ptr->next_ptr = 0;
if(!cursor_ptr) /*l_ptr所指向指针（list）是一个null*/
insertFirst(l_ptr, node);
else{
while(cursor_ptr->next_ptr){
cursor_ptr = cursor_ptr->next_ptr;
}
cursor_ptr->next_ptr = n_ptr;
}
}
void removeLast(LinkList *l_ptr, LNode *n_ptr){
LNode *cursor_ptr = *l_ptr;
if(!cursor_ptr){
error("remove", "There is no node in the list!");
return;
}
if(!cursor_ptr->next_ptr)
deleteFirst(l_ptr, n_ptr);
else{
while(cursor_ptr->next_ptr->next_ptr){
cursor_ptr = cursor_ptr->next_ptr;
}
free(cursor_ptr->next_ptr);
cursor_ptr->next_ptr=0;
}
}
void insertBefore(LinkList *l_ptr, LNode *aN_ptr, LNode node){
LNode *cursor_ptr = *l_ptr;
LNode *n_ptr = (LNode *)malloc(sizeof(LNode));
n_ptr->data = node.data;
n_ptr->next_ptr = aN_ptr;
if(cursor_ptr == n_ptr)
insertFirst(l_ptr, node);
else{
while(cursor_ptr->next_ptr!=aN_ptr)
cursor_ptr = cursor_ptr->next_ptr;
cursor_ptr->next_ptr = n_ptr;
}
}
void insertAfter(LNode *aN_ptr, LNode node){
LNode *n_ptr = (LNode *)malloc(sizeof(LNode));
n_ptr->data = node.data;
if(!aN_ptr){
error("insertAfter", "aN_ptr is null");
return;
}
n_ptr->next_ptr = aN_ptr->next_ptr;
aN_ptr->next_ptr = n_ptr;
}
void setCurElem(LNode *n_ptr, ElemType e){
if(!n_ptr){
error("setCurElem", "n_ptr is null");
return;
}
n_ptr->data = e;
}
ElemType getCurElem(LNode *n_ptr){
if(!n_ptr){
error("getCurElem", "n_ptr is null");
return 0;
}
return n_ptr->data;
}
int listEmpty(LinkList list){
return list?1:0;
}
int listLength(LinkList list){
LNode *n_ptr = list;
int length = 0;
while(n_ptr&&++length)
n_ptr = n_ptr->next_ptr;
return length;
}
LNode *getHead(LinkList list){
return list;
}
LNode *getLast(LinkList list){
LNode *n_ptr = list;
if(!n_ptr){
error("getLast", "n_ptr is null");
return 0;
}
while(n_ptr->next_ptr){
n_ptr = n_ptr->next_ptr;
}
return n_ptr;
}
LNode *priorPos(LinkList list, LNode *aN_ptr){
LNode *n_ptr = list;
if(aN_ptr == list){
error("priorPos", "aN_ptr is the first node");
return 0;
}
while(n_ptr&&n_ptr->next_ptr!=aN_ptr)
n_ptr = n_ptr->next_ptr;
if(n_ptr){
return n_ptr;
}else{
error("priorPos", "aN_ptr is not in the list");
return 0;
}
}
LNode *nextPos(LinkList list, LNode *n_ptr){
if(n_ptr)
return n_ptr->next_ptr;
error("nextPos", "n_ptr is null");
return 0;
}
void locatePos(LinkList list, int i, LNode *aN_ptr){
LNode *n_ptr = list;
int cursor = 0;
while(n_ptr&&cursor!=i){
n_ptr = n_ptr->next_ptr;
}
*aN_ptr = *n_ptr;
}
LNode *locateElem(LinkList list, ElemType e, int (*compare)(ElemType, ElemType)){
LNode *n_ptr = list;
while(n_ptr&&!compare(n_ptr->data, e)){
n_ptr = n_ptr->next_ptr;
}
if(n_ptr)
return n_ptr;
else{
return 0;
}
}
void listTraverse(LinkList list){
LNode *n_ptr = list;
printf("\nlist: ");
while(n_ptr){
printf("%2d ", n_ptr->data);
n_ptr = n_ptr->next_ptr;
}
printf("\n");
}
void error(char *name, char *msg){
printf("-----Errors occured in \"%s\"!-----\n", name);
printf(" %s!\n",msg);
printf("\n");
}
void warning(char *msg){
printf("\n %s!\n\n");
}
test.c
#include "LinkList.h"
int compare(ElemType e1, ElemType e2){
return e1==e2?1:0;
}
int main(){
LinkList list;
LNode node;
LNode *n_ptr;
node.data = 0;
node.next_ptr = 0;
list = makeNode(1);
//listTraverse(list);
insertFirst(&list, node);
//listTraverse(list);
deleteFirst(&list, &node);
//listTraverse(list);
insertFirst(&list, node);
//listTraverse(list);
node.data = 2;
append(&list, node);
listTraverse(list);
removeLast(&list, &node);
//listTraverse(list);
append(&list, node);
listTraverse(list);
node.data = 3;
append(&list, node);
node.data = 4;
append(&list, node);
node.data = 5;
append(&list, node);
node.data = 6;
append(&list, node);
node.data = 7;
append(&list, node);
listTraverse(list);
n_ptr = locateElem(list, 5, compare);
node.data = 8;
insertBefore(&list, n_ptr, node);
node.data = 9;
insertAfter(n_ptr, node);
setCurElem(n_ptr, 10);
setCurElem(getHead(list), 11);
setCurElem(getLast(list), 12);
setCurElem(priorPos(list, n_ptr), 13);
setCurElem(nextPos(list, n_ptr), 14);
printf("getCur: %d %d\n", getCurElem(n_ptr), listLength(list));
listTraverse(list);
}
分享到：
相关推荐
void DeleteList(LinkList *head, char *key) { ListNode *p, *r, *q = head; p = LocateNode(head, key); // 查找指定key的节点 if (p == NULL) { printf("position error"); exit(0); } while (q->next != ...
} LNode, *LinkList; ``` 在此基础上，我们可以通过一系列函数来实现链表的基本操作。例如，建立链表的函数`createtail()`通过循环输入数据，当输入结束标志时停止，并将每个数据存储在链表的新节点中。该函数会...
双向链表是一种数据结构，它在单链表的基础上增加了一个指向前一个节点的指针，允许双向遍历。 在Java中，双向链表的实现通常涉及到自定义一个节点类，该类包含三个属性：数据、指向下一个节点的引用和指向前一个...
//定义单链表 typedef char ElemType; typedef struct LNode // 结点类型定义 { ElemType data; struct LNode * next; }LNode, *LinkList;//LinkList为结构指针类型 //定义关于单链表的若干操作 //初始化--建空...
`LinkList`类表示整个链表，包括构造函数`LinkList()`用于初始化链表，析构函数`~LinkList()`用于释放链表占用的内存，以及`Sort()`、`Input()`、`Output()`和`Gethead()`等方法，分别对应链表的排序、输入、输出和...
本文实例讲述了C#数据结构之单链表(LinkList)实现方法。分享给大家供大家参考，具体如下： 这里我们来看下“单链表(LinkList)”。在上一篇《C#数据结构之顺序表(SeqList)实例详解》的最后，我们指出了：顺序表要求...
单链表是计算机科学中数据结构的基础之一，它在C语言中的实现涉及到内存管理、指针操作以及数据结构的设计。本篇文章将详细讲解C语言如何实现单链表及其相关操作，并通过实际测试来验证其正确性。 首先，单链表是由...
在本例中，我们关注的是“List List”单链表，它是一个简单的链式存储结构，每个节点包含数据和指向下一个节点的指针。我们将探讨链表的实现、添加和删除操作，以及如何遍历并排序链表。 首先，让我们深入理解...
2）定义单链表类模板，例如LinkList，封装单链表的操作算法，包括 a.创建 b.释放 c.按值查找 d.按序号查找 e.第i个位置插入和删除元素 f.求链表长度 g.输出单链表所有元素 h.原地置逆单链表 i.判断单链表是否...
单链表. template class LinkList { public: LinkList(); //无参构造函数，建立只有头结点的空链表 LinkList(T a[], int n); //有参构造函数，建立由n个元素的单链表 ~LinkList(); //析构函数 int Length(); //...
单链表（计算机）linklist.cpp
- 定义链表类型`LinkList`，通常是指向链表头结点的指针。 2. **具体函数实现**： - **定位节点函数`LocateNode`**：根据键值查找链表中的节点。 - 参数：链表头指针`head`，键值`key`。 - 返回值：指向键值为`...
使用数据结构中的方法，实现链式存储结构，达到节省空间的目的
在给定的文件"LinkList.h"和"LinkList.c"中，我们可以预期它们包含了单链表的定义和操作函数。`LinkList.h`通常会定义链表节点的结构体以及相关的函数声明，而`LinkList.c`则实现这些函数的具体逻辑。 首先，结构体...
根据提供的文件信息，我们可以深入探讨数据结构实验中的关键知识点，主要围绕单链表的基本操作，包括单链表的建立与输出、合并、删除重复值以及逆置等方面。 ### 数据结构实验链栈代码详解 #### 一、单链表的基础...
C语言实现单链表（常规操作） LinkList CreateHeadListH(); // 头插法创建单链表 LinkList CreateHeadListT(); // 尾插法创建单链表 int ListEmpty(); // 单链表判空 int ListLength(); // 求单链表长度...
单链表实现：Status InitList(Linklist l);//初始化链表 Status CreateList(Linklist l,ElemType a[],int n);//创建链表 void InsertList(Linklist l,int i,ElemType e);//在第i个位置上插入e void DelList(Linklist...
**数据结构：双向链表** 双向链表是一种高级的数据结构，它在单链表的基础上进行了扩展，每个...在"Doubly linklist"这个项目中，你可以找到具体的实现细节和示例代码，这将有助于你直观地了解双向链表的工作原理。