#ifndef List_H
#define List_H
#endif
typedef int Item;
typedef struct node * PNode;
typedef struct node
{
Item item;
PNode next;
} Node;
typedef PNode Position;
typedef PNode List;
/*
功能
n生空链表L
*/
List MakeEmpty(List L);
/*
功能
判定链表是否为空
*/
int IsEmpty(List L);
/*
功能
判定位置P的节点是否为尾节点
*/
int IsLast(Position P);
/*
功能
在链表L中查找数据项为X的第一个节点
*/
Position Find(Item X, List L);
/*
功能
在链表L中删除数据项为X的第一个节点
*/
void Delte(Item X, List L);
/*
功能
在链表L中查找数据项为X的第一个节点的前驱位置
*/
Position FindPrevious(Item X, List L);
/*
功能
在链表L中查找数据项为X的第一个节点的后继位置
*/
Position FindNext(Item X, List L);
/*
功能
在链表L中P位置插入数据项为X的节点
*/
void Insert(Item X, List L, Position P);
/*
功能
删除链表L初头节点外的所有节点
*/
void DelteList(List L);
/*
功能
获得链表L中头节点位置
*/
Position Header(List L);
/*
功能
获得链表L中第一个数据节点位置
*/
Position First(List L);
/*
功能
获得位置P的后继节点位置
*/
Position Advance(Position P);
/*
功能
获得P位置节点的数据项
*/
Item Retrieve(Position P);
list.c
#include "list.h"
#include <malloc.h>
#include <stdlib.h>
List MakeEmpty(List L)
{
L = (PNode)malloc(sizeof(Node));
L->item = 0;
L->next = NULL;
return L;
}
int IsEmpty(List L)
{
return L->next == NULL;
}
int IsLast(Position P)
{
return P->next == NULL;
}
Position Find(Item X, List L)
{
Position P;
P = L->next;
while(P!=NULL && P->item!=X)
{
P = P->next;
}
return P;
}
void Delete(Item X, List L)
{
Position P, temp;
P = FindPrevious(X,L);
if(!IsLast(P))
{
temp = P->next;
P->next = temp->next;
free(temp);
}
}
Position FindPrevious(Item X, List L)
{
Position P;
P = L;
while(P->next!=NULL && P->next->item != X)
{
P= P->next;
}
return P;
}
Position FindNext(Item X, List L)
{
Position P;
P = L;
while(P!=NULL && P->item != X)
{
P = P->next;
}
return P->next;
}
void Insert(Item X, List L, Position P)
{
Position tmp;
tmp = malloc(sizeof(Node));
if(tmp == NULL)
exit(0);
tmp->item = X;
tmp->next = P->next;
P->next = tmp;
}
void DeleteList(List L)
{
Position P, tmp;
P=L->next;
L->next = NULL;
while(P!=NULL)
{
tmp = P->next;
free(P);
P = tmp;
}
}
Position Header(List L)
{
return L;
}
Position Fist(List L)
{
if(L->next != NULL)
return L->next;
}
Position Advance(Position P)
{
if(P!=NULL)
return P->next;
}
Item Retrieve(Position P)
{
if(P!=NULL)
return P->item;
}
testlist.c
#include "list.h"
#include <stdlib.h>
#include <stdio.h>
int main()
{
List list=NULL;
Position P, currentP;
int i, num;
num = 10;
list = MakeEmpty(list);
if(IsEmpty(list)){
printf("list is NULL \n");
}
P = list;
for(i=0;i<num;i++)
{
Insert(i*i,list,P);
P = Advance(P);
printf("already insert %d \n",Retrieve(P));
}
currentP = Find(25, list);
printf("currentP is %d \n", currentP->item);
P = FindNext(currentP->item,list);
printf("next of number 25 is: %d \n",Retrieve(P));
P = FindPrevious(currentP->item,list);
printf("preview of number 25 is: %d \n",Retrieve(P));
Delete(currentP->item,list);
P=list;
for(i=0;i<num;i++)
{
P = Advance(P);
printf("after delete %d \n",Retrieve(P));
}
DeleteList(list);
printf("already deleted list\n");
if(IsEmpty(list))
printf("list is NULL\n");
}
测试环境Fedora 20, gcc (GCC) 4.8.3 20140624
编译命令：gcc list.c testlist.c -o output.out
以下是同一个例子，但在前一个基础上添加了一些头元素与尾元素的校验，目前只实现了新建，初使化，校验长度，在链表头与尾添加元素，删除某个元素，及清除整个链表功能；
功能都已经在实际电脑上测试通过；
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
typedef int Item;
typedef struct SingleNode * PNode;
typedef struct SingleNode{
Item item;
PNode next;
} Node;
//创建一个链表中位置指针
typedef PNode Position;
//创建一个链表集合，实际也是一个指针，指向链表第一个元素的指针
typedef PNode List;
/*
创建一个链表，并初使化为一个包含0值的元素
*/
List createEmpty(List L)
{
L = (PNode)malloc(sizeof(Node));
L->item = 0;//创建了一个值为0的表头
L->next = NULL;
return L;
}
/*
x打印元素清单
*/
void
printList(List L)
{
int i=0;
Position P;
P = L;
while(P!=NULL)
{
printf("number %d of this list is: %d\n",i,P->item);
P = P->next;
i++;
}
}
/*
插入链表新的元素
*/
void
insertElement(Item X, List L, Position P)
{
Position tmp;
tmp = malloc(sizeof(Node));
if(tmp == NULL)
exit(0);
tmp->next = P->next;
tmp->item = X;
P->next = tmp;
}
/*
返回链表第一个元素
*/
Position
getFirst( List L)
{
if(L->next!=NULL)
return L->next;
}
/*
返回链表的最后一个元素
*/
Position
getLast(List L)
{
Position P;
P = L;
while(P->next!=NULL)
P = P->next;
return P;
}
/*
在链表头部插入元素
*/
void
insertElementAtStart(Item X, List L)
{
insertElement(X,L,L);
}
/*
在链表尾部插入元素
*/
void insertElementAtEnd(Item X, List L)
{
Position end, P;
P = L;
end = getLast(P);
insertElement(X,L,end);
}
Position
getPosition(Item X,const List L)
{
Position P;
P = L;
while(P!=NULL && P->item != X)
{
P=P->next;
}
return P;
}
/*
获得当前元素的前一个元素
*/
Position
getPreviewElement(Item X, const List L)
{
Position P, tmpX;
P = L;
if(isFirst(X,P))
return NULL;
while(P->next!=NULL && P->next->item != X)
{
P = P->next;
}
return P;
}
/*
获取链表当前元素的下一个元素
*/
Position
getNextElement(Item X,const List L)
{
Position P,tmpX;
P = L;
if(isLast(X,P))
return NULL;
while(P != NULL && P->item != X)
{
P = P->next;
}
return P->next;//返回当前元素的下一个元素
}
/*
获取链表长度
*/
int
getLength(const List L)
{
Position P;
P = L;
int j = 0;
while(P != NULL)
{
P = P->next;
j++;
}
return j;
}
/*
判断是否是最后一个节点
*/
int
isLast(Item X,const List L)
{
Position P;
P = L;
while(P!=NULL && P->item != X)
P = P->next;
return P->next == NULL;
}
/*
判断是否是第一个元素
*/
int
isFirst(Item X, const List L)
{
return L!=NULL && (L->item == X);
}
/*
判断当前链表是否为空
*/
int
isEmpty(List L)
{
return L->next == NULL;
}
/*
获取当前元素的下一个节点指针
*/
Position
advance(Position P)
{
if(P != NULL)
return P->next;
}
/*
获取当前元素的元素值
*/
Item
retrieve(Position P)
{
if(P!=NULL)
return P->item;
}
/*
删除指定值的元素
**/
void deleteElement(Item X, List L)
{
Position tmp,P;
if(isFirst(X,L))
{
P = L;
tmp = P;
L->next = tmp->next->next;//因测试前执行了P2=P2->next去掉过表头
free(tmp);
}
else
{
P = getPreviewElement(X, L);
tmp = P->next;
P->next = tmp->next;
free(tmp);
}
}
/*
删除除表头外所有元素
*/
void deleteList(List L)
{
Position P, tmp;
P = L;
while(P!=NULL)
{
printf("p is: %d\n",P->item);
tmp = P->next;
free(P);
P = tmp;
}
L->next = NULL;
}
/*
打印测试
*/
void
printTest(Item X, List list)
{
printList(list);
printf("the length of this list is: %d\n", getLength(list));
Position previewE = getPreviewElement(X, list);
if(previewE == NULL)
printf("item %d is the first item, no preview element exist!\n", X);
else
printf("the previews of item %d is: %d\n", X, previewE->item);
Position nextE = getNextElement(X, list);
if(nextE == NULL)
printf("item %d is the last item, no next element exist!\n",X);
else
printf("the next of item %d is: %d\n", X, nextE->item);
}
int
main()
{
List list = NULL;
Position P,P1,P2,P3;
int i, num;
Item item = 16;
num = 10;
list = createEmpty(list);
if(isEmpty(list))
P = list;
//创建及打印某元素的前置与后继元素及长度
for(i=0;i<num;i++)
{
insertElement(i*i, list, P);
P = advance(P);
}
printf("创建链表完成后打印\n");
P1 = list->next;//跳过表头
printTest(item, P1);
//链表头插入元素及打印元素的前置与后继元素及长度
Item startItem = 100;
P2 = list;
insertElementAtStart(startItem,P2);
printf("头部插入元素newItem：%d 后的打印\n",startItem);
P2 = P2->next;//跳过表头
printTest(startItem,P2);
//链表尾插入元素及打印元素的前置与后继元素及长度
Item endItem = 110;
insertElementAtEnd(endItem,P2);
printf("尾部插入元素newItem：%d 后的打印\n",endItem);
printTest(endItem,P2);
//删除元素及打印元素的前置与后继元素及长度
Item deleteItem = 16;//测试过头元素100, 尾元素100,均删除正常
deleteElement(deleteItem,P2);
printf("删除元素 %d 后的打印\n",deleteItem);
printTest(9,P2);
//删除链表除表头外所有元素,删除后加上表头链表长度为1
deleteList(P2);
printf("删除所有元素后打印");
printList(P2);
printf("删除后链表长度为：%d\n",getLength(P2));
}
相关推荐
本篇文章将详细讲解C语言如何实现单链表及其相关操作，并通过实际测试来验证其正确性。 首先，单链表是由一系列节点组成的数据结构，每个节点包含两部分：数据域和指针域。数据域用于存储数据，指针域则保存下一个...
创建`LinkedList_HeadNode-code`文件夹中的代码可以按照这些函数模板进行编写，以便进行编译和测试。这些操作是单链表的基础，通过它们可以构建更复杂的链表数据结构和算法，例如双向链表、循环链表以及各种搜索和...
1、实现软件：Dev-C++ 2、详细的测试页面可见我《资源》专栏下的《C语言系统资源测试》。 3、适合新手下载学习。 4、基于C语言的单链表实现。 5、代码共255行 6、注释多，排版有序
在VS2008环境下，你可以编写这些函数，然后创建一个主函数来测试它们，如创建链表，插入、删除、修改元素，然后打印出链表的状态。通过这种方式，你可以直观地看到操作的效果。 总结起来，这个项目的核心是理解和...
总之，这个项目是一个很好的练习，涵盖了C语言的基本语法、数据结构（单链表）的应用，以及在Linux环境下的程序开发。通过完成这个项目，开发者不仅可以提升编程技能，还能加深对数据结构和操作系统接口的理解。
在实验中，我们使用C语言编写了单链表的插入和删除操作，并进行了测试。测试结果表明，插入和删除操作都能正确地执行。 总结 单链表是一种基本的数据结构，它的基本操作包括插入、删除、查找和表的合并等运算。...
8. 调试与测试：在编写链表相关的代码时，需要对代码进行严格的调试和测试，确保链表的插入、删除等操作的正确性，以及内存分配与释放的正确性，避免内存泄漏。 综上所述，头插法创建单链表涉及了结构体的定义、...
【图书信息管理系统（C语言编写）】是一款基于C语言实现的简单信息管理软件，主要用于图书馆的日常运营，如书籍信息的录入、查询、修改、删除等操作。在大学的计算机科学教育中，这类课程设计是让学生熟悉编程逻辑、...
### C语言编写的文本编辑器知识点总结 #### 实验背景与目标 - **实验课程**：数据结构 - **实验项目**：文本编辑器的实现 - **指导教师**：李莉丽 - **学生姓名**：陈德怀 - **学生学号**：2009053035 - **班级**...
学生需要使用C语言编写程序，实现单链表的基本操作，并编写报告书，详细介绍设计思路、实现过程和测试结果。 3. 设计环境 本课程设计的开发环境是Windows操作系统，使用Visual Studio 2010作为开发工具，编程语言...
在“C语言数据结构邻接表课程设计”中，我们将深入探讨如何利用...通过理解和实践这些内容，你可以更好地掌握C语言中邻接表的实现和图的遍历算法。这不仅对课程设计有帮助，也是提升编程技能和理解数据结构的重要步骤。
最后，编写主函数用于测试以上各个功能。 ```c int main() { UserType a[N] = {8, 2, 9, 4, 5}; SLink *sl; CreateList(sl, a, N); PrintList(sl); SortLink(sl); PrintList(sl); return 0; } ``` ...
总之，C语言实现集合并交差是通过自定义单链表数据结构并编写相应的操作函数来完成的。这种方法不仅有助于理解数据结构和算法，还能在实际项目中灵活应用。在进行集合操作时，要特别注意内存管理，确保正确分配和...
⑵ 编写集合元素输入并插入到单链表中的函数INSERT_SET，保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中； ⑶ 编写集合元素输出函数，对建立的集合链表按非递增方式输出； ⑷ 编写求集合A、B的交C=A∩...
在这个“数据结构单链表实例一个简单的小程序”中，我们可以推测作者实现了一个用C语言编写的单链表操作程序，可能包括创建、插入、删除和遍历等基本操作。 单链表的特点在于它的每个节点只有一个指向后继节点的...
6. **错误处理**：在编写C语言程序时，必须考虑可能出现的错误情况，如内存分配失败、文件打开失败、无效的用户输入等，并通过适当的错误处理代码来确保程序的健壮性。 7. **实验报告**：这部分内容通常包括对项目...
在这个问题中，我们关注的是链式存储，具体是单链表的实现，用C语言编写。 单链表是一种线性表的链式存储结构，每个节点包含数据域和指针域，指针域指向下一个节点。在C语言中，我们可以定义一个结构体来表示链表的...
2. **实现单链表的基本操作**：学会如何通过C语言实现单链表的创建、插入和删除操作。 3. **提高编程能力**：通过上机实验，加深对C语言的理解，特别是指针的应用。 #### 实验内容与步骤 1. **分析和理解程序**：...